74 template <
class T1,
class T2>
75 void constructor(T1* p, T2& val)
77 new ((
void *) p) T1(val);
81 void constructor(T1* p)
87 void destructor(T1* p)
105 template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
115 class pre_order_iterator;
116 class post_order_iterator;
117 class sibling_iterator;
121 tree(
const iterator_base&);
127 #ifdef __SGI_STL_PORT
128 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t>
135 typedef T value_type;
137 typedef T& reference;
138 typedef size_t size_type;
139 typedef ptrdiff_t difference_type;
140 typedef std::bidirectional_iterator_tag iterator_category;
145 T& operator*()
const;
146 T* operator->()
const;
158 bool skip_current_children_;
226 void set_first_parent_();
227 void find_leftmost_parent_();
273 template<
typename iter> iter
parent(iter)
const;
284 template<
typename iter> iter
erase(iter);
324 template<
typename iter> iter
move_after(iter target, iter source);
326 template<
typename iter> iter
move_before(iter target, iter source);
328 template<
typename iter> iter
move_ontop(iter target, iter source);
332 bool duplicate_leaves =
false);
335 template<
class StrictWeakOrdering>
338 template<
typename iter>
339 bool equal(
const iter& one,
const iter& two,
const iter& three)
const;
340 template<
typename iter,
class BinaryPredicate>
341 bool equal(
const iter& one,
const iter& two,
const iter& three, BinaryPredicate)
const;
342 template<
typename iter>
343 bool equal_subtree(
const iter& one,
const iter& two)
const;
344 template<
typename iter,
class BinaryPredicate>
345 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
380 return one.node < two.node;
385 tree_node_allocator alloc_;
386 void head_initialise_();
390 template<
class StrictWeakOrdering>
394 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
396 bool operator()(
const tree_node *a,
const tree_node *b)
398 static StrictWeakOrdering comp;
399 return comp(a->data, b->data);
402 StrictWeakOrdering comp_;
426 template <
class T,
class tree_node_allocator>
430 if (one.node > two.node)
return true;
438 template <
class T,
class tree_node_allocator>
444 template <
class T,
class tree_node_allocator>
451 template <
class T,
class tree_node_allocator>
459 template <
class T,
class tree_node_allocator>
463 alloc_.deallocate(head, 1);
464 alloc_.deallocate(feet, 1);
467 template <
class T,
class tree_node_allocator>
470 head = alloc_.allocate(1, 0);
471 feet = alloc_.allocate(1, 0);
474 head->first_child = 0;
475 head->last_child = 0;
476 head->prev_sibling = 0;
477 head->next_sibling = feet;
480 feet->first_child = 0;
481 feet->last_child = 0;
482 feet->prev_sibling = head;
483 feet->next_sibling = 0;
486 template <
class T,
class tree_node_allocator>
492 template <
class T,
class tree_node_allocator>
499 template <
class T,
class tree_node_allocator>
503 pre_order_iterator it = other.
begin(), to =
begin();
504 while (it != other.
end())
512 while (it != other.
end())
522 template <
class T,
class tree_node_allocator>
526 while (head->next_sibling != feet)
527 erase(pre_order_iterator(head->next_sibling));
530 template<
class T,
class tree_node_allocator>
539 cur = cur->next_sibling;
541 kp::destructor(&prev->data);
542 alloc_.deallocate(prev, 1);
544 it.node->first_child = 0;
545 it.node->last_child = 0;
548 template<
class T,
class tree_node_allocator>
558 if (cur->prev_sibling == 0)
560 cur->parent->first_child = cur->next_sibling;
564 cur->prev_sibling->next_sibling = cur->next_sibling;
566 if (cur->next_sibling == 0)
568 cur->parent->last_child = cur->prev_sibling;
572 cur->next_sibling->prev_sibling = cur->prev_sibling;
575 kp::destructor(&cur->data);
576 alloc_.deallocate(cur, 1);
580 template <
class T,
class tree_node_allocator>
583 return pre_order_iterator(head->next_sibling);
586 template <
class T,
class tree_node_allocator>
589 return pre_order_iterator(feet);
592 template <
class T,
class tree_node_allocator>
598 while (tmp->first_child)
599 tmp = tmp->first_child;
601 return post_order_iterator(tmp);
604 template <
class T,
class tree_node_allocator>
607 return post_order_iterator(feet);
610 template <
class T,
class tree_node_allocator>
614 unsigned int curdepth = 0;
615 while (curdepth < dp)
617 while (tmp->first_child == 0)
619 tmp = tmp->next_sibling;
621 throw std::range_error(
"tree: begin_fixed out of range");
623 tmp = tmp->first_child;
629 template <
class T,
class tree_node_allocator>
634 unsigned int curdepth = 1;
635 while (curdepth < dp)
637 while (tmp->first_child == 0)
639 tmp = tmp->next_sibling;
641 throw std::range_error(
"tree: end_fixed out of range");
643 tmp = tmp->first_child;
649 template <
class T,
class tree_node_allocator>
652 if (pos.node->first_child == 0)
656 return pos.node->first_child;
659 template <
class T,
class tree_node_allocator>
662 sibling_iterator ret(0);
663 ret.parent_ = pos.node;
667 template <
class T,
class tree_node_allocator>
668 template <
typename iter>
675 template <
class T,
class tree_node_allocator>
676 template <
typename iter>
681 ret.node =
position.node->prev_sibling;
685 template <
class T,
class tree_node_allocator>
686 template <
typename iter>
691 ret.node =
position.node->next_sibling;
695 template <
class T,
class tree_node_allocator>
696 template <
typename iter>
704 ret.node =
position.node->next_sibling;
708 int relative_depth = 0;
712 ret.node = ret.node->parent;
713 if (ret.node == 0)
return ret;
716 while (ret.node->next_sibling == 0);
718 ret.node = ret.node->next_sibling;
719 while (ret.node->first_child == 0)
721 if (ret.node->next_sibling == 0)
723 ret.node = ret.node->next_sibling;
724 if (ret.node == 0)
return ret;
726 while (relative_depth < 0 && ret.node->first_child != 0)
728 ret.node = ret.node->first_child;
731 if (relative_depth < 0)
733 if (ret.node->next_sibling == 0)
goto upper;
740 template <
class T,
class tree_node_allocator>
741 template <
typename iter>
747 kp::constructor(&tmp->data);
748 tmp->first_child = 0;
754 position.node->last_child->next_sibling = tmp;
760 tmp->prev_sibling =
position.node->last_child;
762 tmp->next_sibling = 0;
766 template <
class T,
class tree_node_allocator>
767 template <
class iter>
777 kp::constructor(&tmp->data, x);
778 tmp->first_child = 0;
784 position.node->last_child->next_sibling = tmp;
790 tmp->prev_sibling =
position.node->last_child;
792 tmp->next_sibling = 0;
796 template <
class T,
class tree_node_allocator>
797 template <
class iter>
806 template <
class T,
class tree_node_allocator>
807 template <
class iter>
820 template <
class T,
class tree_node_allocator>
823 assert(head->next_sibling == feet);
827 template <
class T,
class tree_node_allocator>
828 template <
class iter>
837 kp::constructor(&tmp->data, x);
838 tmp->first_child = 0;
841 tmp->parent =
position.node->parent;
843 tmp->prev_sibling =
position.node->prev_sibling;
846 if (tmp->prev_sibling == 0)
849 tmp->parent->first_child = tmp;
852 tmp->prev_sibling->next_sibling = tmp;
856 template <
class T,
class tree_node_allocator>
860 kp::constructor(&tmp->data, x);
861 tmp->first_child = 0;
868 tmp->prev_sibling =
position.range_last();
869 tmp->parent->last_child = tmp;
873 tmp->parent =
position.node->parent;
874 tmp->prev_sibling =
position.node->prev_sibling;
878 if (tmp->prev_sibling == 0)
881 tmp->parent->first_child = tmp;
884 tmp->prev_sibling->next_sibling = tmp;
888 template <
class T,
class tree_node_allocator>
889 template <
class iter>
893 kp::constructor(&tmp->data, x);
894 tmp->first_child = 0;
897 tmp->parent =
position.node->parent;
899 tmp->next_sibling =
position.node->next_sibling;
902 if (tmp->next_sibling == 0)
905 tmp->parent->last_child = tmp;
909 tmp->next_sibling->prev_sibling = tmp;
914 template <
class T,
class tree_node_allocator>
915 template <
class iter>
934 template <
class T,
class tree_node_allocator>
935 template <
class iter>
938 kp::destructor(&
position.node->data);
939 kp::constructor(&
position.node->data, x);
943 template <
class T,
class tree_node_allocator>
944 template <
class iter>
955 kp::constructor(&tmp->data, (*from));
956 tmp->first_child = 0;
958 if (current_to->prev_sibling == 0)
960 current_to->parent->first_child = tmp;
964 current_to->prev_sibling->next_sibling = tmp;
966 tmp->prev_sibling = current_to->prev_sibling;
967 if (current_to->next_sibling == 0)
969 current_to->parent->last_child = tmp;
973 current_to->next_sibling->prev_sibling = tmp;
975 tmp->next_sibling = current_to->next_sibling;
976 tmp->parent = current_to->parent;
977 kp::destructor(¤t_to->data);
978 alloc_.deallocate(current_to, 1);
982 tree_node *last = from.node->next_sibling;
984 pre_order_iterator toit = tmp;
988 assert(current_from != 0);
989 if (current_from->first_child != 0)
991 current_from = current_from->first_child;
996 while (current_from->next_sibling == 0 && current_from != start_from)
998 current_from = current_from->parent;
1000 assert(current_from != 0);
1002 current_from = current_from->next_sibling;
1003 if (current_from != last)
1009 while (current_from != last);
1014 template <
class T,
class tree_node_allocator>
1016 sibling_iterator orig_begin,
1017 sibling_iterator orig_end,
1018 sibling_iterator new_begin,
1019 sibling_iterator new_end)
1021 tree_node *orig_first = orig_begin.node;
1024 while ((++orig_begin) != orig_end)
1025 orig_last = orig_last->next_sibling;
1027 while ((++new_begin) != new_end)
1028 new_last = new_last->next_sibling;
1032 pre_order_iterator ret;
1035 pre_order_iterator tt =
insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1041 if (new_first == new_last)
1043 new_first = new_first->next_sibling;
1051 if (next == orig_last)
1053 next = next->next_sibling;
1054 erase((pre_order_iterator)orig_first);
1062 template <
class T,
class tree_node_allocator>
1063 template <
typename iter>
1066 if (
position.node->first_child == 0)
1072 tmp->parent =
position.node->parent;
1073 tmp = tmp->next_sibling;
1093 template <
class T,
class tree_node_allocator>
1094 template <
typename iter>
1103 last = last->next_sibling;
1106 if (first->prev_sibling == 0)
1108 first->parent->first_child = last->next_sibling;
1112 first->prev_sibling->next_sibling = last->next_sibling;
1114 if (last->next_sibling == 0)
1116 last->parent->last_child = first->prev_sibling;
1120 last->next_sibling->prev_sibling = first->prev_sibling;
1122 if (
position.node->first_child == 0)
1124 position.node->first_child = first;
1126 first->prev_sibling = 0;
1130 position.node->last_child->next_sibling = first;
1131 first->prev_sibling =
position.node->last_child;
1134 last->next_sibling = 0;
1140 if (pos == last)
break;
1141 pos = pos->next_sibling;
1147 template <
class T,
class tree_node_allocator>
1150 if (from.node->first_child == 0)
return position;
1154 template <
class T,
class tree_node_allocator>
1162 if (dst == src)
return source;
1165 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1166 else src->parent->first_child = src->next_sibling;
1167 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1168 else src->parent->last_child = src->prev_sibling;
1171 if (dst->next_sibling != 0) dst->next_sibling->prev_sibling = src;
1172 else dst->parent->last_child = src;
1173 src->next_sibling = dst->next_sibling;
1174 dst->next_sibling = src;
1175 src->prev_sibling = dst;
1176 src->parent = dst->parent;
1181 template <
class T,
class tree_node_allocator>
1189 if (dst == src)
return source;
1192 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1193 else src->parent->first_child = src->next_sibling;
1194 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1195 else src->parent->last_child = src->prev_sibling;
1198 if (dst->prev_sibling != 0) dst->prev_sibling->next_sibling = src;
1199 else dst->parent->first_child = src;
1200 src->prev_sibling = dst->prev_sibling;
1201 dst->prev_sibling = src;
1202 src->next_sibling = dst;
1203 src->parent = dst->parent;
1207 template <
class T,
class tree_node_allocator>
1215 if (dst == src)
return source;
1218 tree_node *b_prev_sibling = dst->prev_sibling;
1219 tree_node *b_next_sibling = dst->next_sibling;
1226 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1227 else src->parent->first_child = src->next_sibling;
1228 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1229 else src->parent->last_child = src->prev_sibling;
1232 if (b_prev_sibling != 0) b_prev_sibling->next_sibling = src;
1233 else b_parent->first_child = src;
1234 if (b_next_sibling != 0) b_next_sibling->prev_sibling = src;
1235 else b_parent->last_child = src;
1236 src->prev_sibling = b_prev_sibling;
1237 src->next_sibling = b_next_sibling;
1238 src->parent = b_parent;
1242 template <
class T,
class tree_node_allocator>
1244 sibling_iterator from1, sibling_iterator from2,
1245 bool duplicate_leaves)
1247 sibling_iterator fnd;
1248 while (from1 != from2)
1250 if ((fnd = std::find(to1, to2, (*from1))) != to2)
1252 if (from1.begin() == from1.end())
1254 if (duplicate_leaves)
1259 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1271 template <
class T,
class tree_node_allocator>
1275 sort(from, to, comp, deep);
1278 template <
class T,
class tree_node_allocator>
1279 template <
class StrictWeakOrdering>
1281 StrictWeakOrdering comp,
bool deep)
1283 if (from == to)
return;
1287 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1288 sibling_iterator it = from, it2 = to;
1291 nodes.insert(it.node);
1298 tree_node *prev = from.node->prev_sibling;
1299 tree_node *next = it2.node->next_sibling;
1300 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >
::iterator nit = nodes.begin(), eit = nodes.end();
1303 if ((*nit)->parent != 0)
1304 (*nit)->parent->first_child = (*nit);
1306 else prev->next_sibling = (*nit);
1311 (*nit)->prev_sibling = prev;
1313 prev->next_sibling = (*nit);
1319 prev->next_sibling = (*eit);
1322 (*eit)->next_sibling = next;
1323 (*eit)->prev_sibling = prev;
1326 if ((*eit)->parent != 0)
1327 (*eit)->parent->last_child = (*eit);
1329 else next->prev_sibling = (*eit);
1333 sibling_iterator bcs(*nodes.begin());
1334 sibling_iterator ecs(*eit);
1344 template <
class T,
class tree_node_allocator>
1345 template <
typename iter>
1348 std::equal_to<T> comp;
1349 return equal(one_, two, three_, comp);
1352 template <
class T,
class tree_node_allocator>
1353 template <
typename iter>
1356 std::equal_to<T> comp;
1357 return equal_subtree(one_, two_, comp);
1360 template <
class T,
class tree_node_allocator>
1361 template <
typename iter,
class BinaryPredicate>
1364 pre_order_iterator one(one_), three(three_);
1368 while (one != two &&
is_valid(three))
1370 if (!fun(*one, *three))
1380 template <
class T,
class tree_node_allocator>
1381 template <
typename iter,
class BinaryPredicate>
1384 pre_order_iterator one(one_), two(two_);
1386 if (!fun(*one, *two))
return false;
1391 template <
class T,
class tree_node_allocator>
1400 template <
class T,
class tree_node_allocator>
1407 template <
class T,
class tree_node_allocator>
1411 pre_order_iterator it =
begin(), eit =
end();
1420 template <
class T,
class tree_node_allocator>
1423 pre_order_iterator it =
begin(), eit =
end();
1427 template <
class T,
class tree_node_allocator>
1433 while (pos->parent != 0)
1441 template <
class T,
class tree_node_allocator>
1445 if (pos == 0)
return 0;
1447 unsigned int ret = 1;
1452 while ((pos = pos->next_sibling))
1457 template <
class T,
class tree_node_allocator>
1461 unsigned int ret = 0;
1462 while (pos->next_sibling &&
1463 pos->next_sibling != head &&
1464 pos->next_sibling != feet)
1467 pos = pos->next_sibling;
1472 template <
class T,
class tree_node_allocator>
1478 if (it.node->prev_sibling)
1479 it.node->prev_sibling->next_sibling = nxt;
1481 it.node->parent->first_child = nxt;
1482 nxt->prev_sibling = it.node->prev_sibling;
1485 nxtnxt->prev_sibling = it.node;
1487 it.node->parent->last_child = it.node;
1488 nxt->next_sibling = it.node;
1489 it.node->prev_sibling = nxt;
1490 it.node->next_sibling = nxtnxt;
1508 template <
class T,
class tree_node_allocator>
1510 const iterator_base&
end)
const
1513 pre_order_iterator tmp =
begin;
1516 if (tmp == it)
return true;
1522 template <
class T,
class tree_node_allocator>
1525 if (it.node == 0 || it.node == feet)
return false;
1529 template <
class T,
class tree_node_allocator>
1532 unsigned int ind = 0;
1533 if (it.node->parent == 0)
1535 while (it.node->prev_sibling != head)
1537 it.node = it.node->prev_sibling;
1543 while (it.node->prev_sibling != 0)
1545 it.node = it.node->prev_sibling;
1553 template <
class T,
class tree_node_allocator>
1560 tmp = tmp->next_sibling;
1570 template <
class T,
class tree_node_allocator>
1572 : node(0), skip_current_children_(false)
1576 template <
class T,
class tree_node_allocator>
1578 : node(tn), skip_current_children_(false)
1582 template <
class T,
class tree_node_allocator>
1588 template <
class T,
class tree_node_allocator>
1591 return &(node->data);
1594 template <
class T,
class tree_node_allocator>
1597 if (other.node != this->node)
return true;
1601 template <
class T,
class tree_node_allocator>
1604 if (other.node == this->node)
return true;
1608 template <
class T,
class tree_node_allocator>
1611 if (other.node != this->node)
return true;
1615 template <
class T,
class tree_node_allocator>
1618 if (other.node == this->node)
return true;
1622 template <
class T,
class tree_node_allocator>
1625 if (other.node != this->node)
return true;
1629 template <
class T,
class tree_node_allocator>
1632 if (other.node == this->node)
return true;
1636 template <
class T,
class tree_node_allocator>
1639 sibling_iterator ret(node->first_child);
1640 ret.parent_ = this->node;
1644 template <
class T,
class tree_node_allocator>
1647 sibling_iterator ret(0);
1652 template <
class T,
class tree_node_allocator>
1655 skip_current_children_ =
true;
1658 template <
class T,
class tree_node_allocator>
1662 if (pos == 0)
return 0;
1664 unsigned int ret = 1;
1665 while (pos != node->last_child)
1668 pos = pos->next_sibling;
1677 template <
class T,
class tree_node_allocator>
1683 template <
class T,
class tree_node_allocator>
1689 template <
class T,
class tree_node_allocator>
1691 : iterator_base(other.node)
1695 template <
class T,
class tree_node_allocator>
1697 : iterator_base(other.node)
1699 if (this->node == 0)
1701 if (other.range_last() != 0)
1702 this->node = other.range_last();
1704 this->node = other.parent_;
1710 template <
class T,
class tree_node_allocator>
1713 assert(this->node != 0);
1714 if (!this->skip_current_children_ && this->node->first_child != 0)
1716 this->node = this->node->first_child;
1720 this->skip_current_children_ =
false;
1721 while (this->node->next_sibling == 0)
1723 this->node = this->node->parent;
1724 if (this->node == 0)
1727 this->node = this->node->next_sibling;
1732 template <
class T,
class tree_node_allocator>
1735 assert(this->node != 0);
1736 if (this->node->prev_sibling)
1738 this->node = this->node->prev_sibling;
1739 while (this->node->last_child)
1740 this->node = this->node->last_child;
1744 this->node = this->node->parent;
1745 if (this->node == 0)
1751 template <
class T,
class tree_node_allocator>
1754 pre_order_iterator copy = *
this;
1759 template <
class T,
class tree_node_allocator>
1762 pre_order_iterator copy = *
this;
1767 template <
class T,
class tree_node_allocator>
1778 template <
class T,
class tree_node_allocator>
1793 template <
class T,
class tree_node_allocator>
1799 template <
class T,
class tree_node_allocator>
1805 template <
class T,
class tree_node_allocator>
1807 : iterator_base(other.node)
1811 template <
class T,
class tree_node_allocator>
1813 : iterator_base(other.node)
1815 if (this->node == 0)
1817 if (other.range_last() != 0)
1818 this->node = other.range_last();
1820 this->node = other.parent_;
1826 template <
class T,
class tree_node_allocator>
1829 assert(this->node != 0);
1830 if (this->node->next_sibling == 0)
1832 this->node = this->node->parent;
1833 this->skip_current_children_ =
false;
1837 this->node = this->node->next_sibling;
1838 if (this->skip_current_children_)
1840 this->skip_current_children_ =
false;
1844 while (this->node->first_child)
1845 this->node = this->node->first_child;
1851 template <
class T,
class tree_node_allocator>
1854 assert(this->node != 0);
1855 if (this->skip_current_children_ || this->node->last_child == 0)
1857 this->skip_current_children_ =
false;
1858 while (this->node->prev_sibling == 0)
1859 this->node = this->node->parent;
1860 this->node = this->node->prev_sibling;
1864 this->node = this->node->last_child;
1869 template <
class T,
class tree_node_allocator>
1872 post_order_iterator copy = *
this;
1877 template <
class T,
class tree_node_allocator>
1880 post_order_iterator copy = *
this;
1886 template <
class T,
class tree_node_allocator>
1897 template <
class T,
class tree_node_allocator>
1908 template <
class T,
class tree_node_allocator>
1911 assert(this->node != 0);
1912 while (this->node->first_child)
1913 this->node = this->node->first_child;
1919 template <
class T,
class tree_node_allocator>
1923 set_first_parent_();
1926 template <
class T,
class tree_node_allocator>
1930 set_first_parent_();
1933 template <
class T,
class tree_node_allocator>
1935 : iterator_base(other.node)
1937 set_first_parent_();
1940 template <
class T,
class tree_node_allocator>
1942 : iterator_base(other.node), first_parent_(other.parent_)
1944 find_leftmost_parent_();
1947 template <
class T,
class tree_node_allocator>
1949 : iterator_base(other.node), first_parent_(other.first_parent_)
1953 template <
class T,
class tree_node_allocator>
1959 if (this->node == 0)
return;
1960 if (this->node->parent != 0)
1961 first_parent_ = this->node->
parent;
1963 find_leftmost_parent_();
1966 template <
class T,
class tree_node_allocator>
1970 tree_node *tmppar = first_parent_;
1971 while (tmppar->prev_sibling)
1973 tmppar = tmppar->prev_sibling;
1974 if (tmppar->first_child)
1975 first_parent_ = tmppar;
1979 template <
class T,
class tree_node_allocator>
1982 assert(this->node != 0);
1984 if (this->node->next_sibling)
1986 this->node = this->node->next_sibling;
1990 int relative_depth = 0;
1994 this->node = this->node->parent;
1995 if (this->node == 0)
return *
this;
1998 while (this->node->next_sibling == 0);
2000 this->node = this->node->next_sibling;
2001 while (this->node->first_child == 0)
2003 if (this->node->next_sibling == 0)
2005 this->node = this->node->next_sibling;
2006 if (this->node == 0)
return *
this;
2008 while (relative_depth < 0 && this->node->first_child != 0)
2010 this->node = this->node->first_child;
2013 if (relative_depth < 0)
2015 if (this->node->next_sibling == 0)
goto upper;
2041 template <
class T,
class tree_node_allocator>
2044 assert(this->node != 0);
2045 if (this->node->prev_sibling != 0)
2047 this->node = this->node->prev_sibling;
2048 assert(this->node != 0);
2049 if (this->node->parent == 0 && this->node->prev_sibling == 0)
2054 tree_node *par = this->node->parent;
2057 par = par->prev_sibling;
2064 while (par->last_child == 0);
2065 this->node = par->last_child;
2070 template <
class T,
class tree_node_allocator>
2073 fixed_depth_iterator copy = *
this;
2078 template <
class T,
class tree_node_allocator>
2081 fixed_depth_iterator copy = *
this;
2086 template <
class T,
class tree_node_allocator>
2097 template <
class T,
class tree_node_allocator>
2113 template <
class T,
class tree_node_allocator>
2120 template <
class T,
class tree_node_allocator>
2127 template <
class T,
class tree_node_allocator>
2129 : iterator_base(other.node)
2134 template <
class T,
class tree_node_allocator>
2136 : iterator_base(other), parent_(other.parent_)
2140 template <
class T,
class tree_node_allocator>
2144 if (this->node == 0)
return;
2145 if (this->node->parent != 0)
2146 parent_ = this->node->
parent;
2149 template <
class T,
class tree_node_allocator>
2157 template <
class T,
class tree_node_allocator>
2160 if (this->node) this->node = this->node->prev_sibling;
2164 this->node = parent_->last_child;
2169 template <
class T,
class tree_node_allocator>
2172 sibling_iterator copy = *
this;
2177 template <
class T,
class tree_node_allocator>
2180 sibling_iterator copy = *
this;
2185 template <
class T,
class tree_node_allocator>
2196 template <
class T,
class tree_node_allocator>
2207 template <
class T,
class tree_node_allocator>
2210 tree_node *tmp = parent_->first_child;
2214 template <
class T,
class tree_node_allocator>
2217 return parent_->last_child;