73 template <
class T1,
class T2>
74 void constructor(T1* p, T2& val)
76 new ((
void *) p) T1(val);
80 void constructor(T1* p)
86 void destructor(T1* p)
104 template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
114 class pre_order_iterator;
115 class post_order_iterator;
116 class sibling_iterator;
120 tree(
const iterator_base&);
126 #ifdef __SGI_STL_PORT
127 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t>
134 typedef T value_type;
136 typedef T& reference;
137 typedef size_t size_type;
138 typedef ptrdiff_t difference_type;
139 typedef std::bidirectional_iterator_tag iterator_category;
144 T& operator*()
const;
145 T* operator->()
const;
157 bool skip_current_children_;
225 void set_first_parent_();
226 void find_leftmost_parent_();
272 template<
typename iter> iter
parent(iter)
const;
283 template<
typename iter> iter
erase(iter);
323 template<
typename iter> iter
move_after(iter target, iter source);
325 template<
typename iter> iter
move_before(iter target, iter source);
327 template<
typename iter> iter
move_ontop(iter target, iter source);
331 bool duplicate_leaves =
false);
334 template<
class StrictWeakOrdering>
337 template<
typename iter>
338 bool equal(
const iter& one,
const iter& two,
const iter& three)
const;
339 template<
typename iter,
class BinaryPredicate>
340 bool equal(
const iter& one,
const iter& two,
const iter& three, BinaryPredicate)
const;
341 template<
typename iter>
342 bool equal_subtree(
const iter& one,
const iter& two)
const;
343 template<
typename iter,
class BinaryPredicate>
344 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
379 return one.node < two.node;
384 tree_node_allocator alloc_;
385 void head_initialise_();
389 template<
class StrictWeakOrdering>
393 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
395 bool operator()(
const tree_node *a,
const tree_node *b)
397 static StrictWeakOrdering comp;
398 return comp(a->data, b->data);
401 StrictWeakOrdering comp_;
425 template <
class T,
class tree_node_allocator>
429 if (one.node > two.node)
return true;
437 template <
class T,
class tree_node_allocator>
443 template <
class T,
class tree_node_allocator>
450 template <
class T,
class tree_node_allocator>
458 template <
class T,
class tree_node_allocator>
462 alloc_.deallocate(head, 1);
463 alloc_.deallocate(feet, 1);
466 template <
class T,
class tree_node_allocator>
469 head = alloc_.allocate(1, 0);
470 feet = alloc_.allocate(1, 0);
473 head->first_child = 0;
474 head->last_child = 0;
475 head->prev_sibling = 0;
476 head->next_sibling = feet;
479 feet->first_child = 0;
480 feet->last_child = 0;
481 feet->prev_sibling = head;
482 feet->next_sibling = 0;
485 template <
class T,
class tree_node_allocator>
491 template <
class T,
class tree_node_allocator>
498 template <
class T,
class tree_node_allocator>
502 pre_order_iterator it = other.
begin(), to =
begin();
503 while (it != other.
end())
511 while (it != other.
end())
521 template <
class T,
class tree_node_allocator>
525 while (head->next_sibling != feet)
526 erase(pre_order_iterator(head->next_sibling));
529 template<
class T,
class tree_node_allocator>
538 cur = cur->next_sibling;
540 kp::destructor(&prev->data);
541 alloc_.deallocate(prev, 1);
543 it.node->first_child = 0;
544 it.node->last_child = 0;
547 template<
class T,
class tree_node_allocator>
557 if (cur->prev_sibling == 0)
559 cur->parent->first_child = cur->next_sibling;
563 cur->prev_sibling->next_sibling = cur->next_sibling;
565 if (cur->next_sibling == 0)
567 cur->parent->last_child = cur->prev_sibling;
571 cur->next_sibling->prev_sibling = cur->prev_sibling;
574 kp::destructor(&cur->data);
575 alloc_.deallocate(cur, 1);
579 template <
class T,
class tree_node_allocator>
582 return pre_order_iterator(head->next_sibling);
585 template <
class T,
class tree_node_allocator>
588 return pre_order_iterator(feet);
591 template <
class T,
class tree_node_allocator>
597 while (tmp->first_child)
598 tmp = tmp->first_child;
600 return post_order_iterator(tmp);
603 template <
class T,
class tree_node_allocator>
606 return post_order_iterator(feet);
609 template <
class T,
class tree_node_allocator>
613 unsigned int curdepth = 0;
614 while (curdepth < dp)
616 while (tmp->first_child == 0)
618 tmp = tmp->next_sibling;
620 throw std::range_error(
"tree: begin_fixed out of range");
622 tmp = tmp->first_child;
628 template <
class T,
class tree_node_allocator>
633 unsigned int curdepth = 1;
634 while (curdepth < dp)
636 while (tmp->first_child == 0)
638 tmp = tmp->next_sibling;
640 throw std::range_error(
"tree: end_fixed out of range");
642 tmp = tmp->first_child;
648 template <
class T,
class tree_node_allocator>
651 if (pos.node->first_child == 0)
655 return pos.node->first_child;
658 template <
class T,
class tree_node_allocator>
661 sibling_iterator ret(0);
662 ret.parent_ = pos.node;
666 template <
class T,
class tree_node_allocator>
667 template <
typename iter>
674 template <
class T,
class tree_node_allocator>
675 template <
typename iter>
680 ret.node =
position.node->prev_sibling;
684 template <
class T,
class tree_node_allocator>
685 template <
typename iter>
690 ret.node =
position.node->next_sibling;
694 template <
class T,
class tree_node_allocator>
695 template <
typename iter>
703 ret.node =
position.node->next_sibling;
707 int relative_depth = 0;
711 ret.node = ret.node->parent;
712 if (ret.node == 0)
return ret;
715 while (ret.node->next_sibling == 0);
717 ret.node = ret.node->next_sibling;
718 while (ret.node->first_child == 0)
720 if (ret.node->next_sibling == 0)
722 ret.node = ret.node->next_sibling;
723 if (ret.node == 0)
return ret;
725 while (relative_depth < 0 && ret.node->first_child != 0)
727 ret.node = ret.node->first_child;
730 if (relative_depth < 0)
732 if (ret.node->next_sibling == 0)
goto upper;
739 template <
class T,
class tree_node_allocator>
740 template <
typename iter>
746 kp::constructor(&tmp->data);
747 tmp->first_child = 0;
753 position.node->last_child->next_sibling = tmp;
759 tmp->prev_sibling =
position.node->last_child;
761 tmp->next_sibling = 0;
765 template <
class T,
class tree_node_allocator>
766 template <
class iter>
776 kp::constructor(&tmp->data, x);
777 tmp->first_child = 0;
783 position.node->last_child->next_sibling = tmp;
789 tmp->prev_sibling =
position.node->last_child;
791 tmp->next_sibling = 0;
795 template <
class T,
class tree_node_allocator>
796 template <
class iter>
805 template <
class T,
class tree_node_allocator>
806 template <
class iter>
819 template <
class T,
class tree_node_allocator>
822 assert(head->next_sibling == feet);
826 template <
class T,
class tree_node_allocator>
827 template <
class iter>
836 kp::constructor(&tmp->data, x);
837 tmp->first_child = 0;
840 tmp->parent =
position.node->parent;
842 tmp->prev_sibling =
position.node->prev_sibling;
845 if (tmp->prev_sibling == 0)
848 tmp->parent->first_child = tmp;
851 tmp->prev_sibling->next_sibling = tmp;
855 template <
class T,
class tree_node_allocator>
859 kp::constructor(&tmp->data, x);
860 tmp->first_child = 0;
867 tmp->prev_sibling =
position.range_last();
868 tmp->parent->last_child = tmp;
872 tmp->parent =
position.node->parent;
873 tmp->prev_sibling =
position.node->prev_sibling;
877 if (tmp->prev_sibling == 0)
880 tmp->parent->first_child = tmp;
883 tmp->prev_sibling->next_sibling = tmp;
887 template <
class T,
class tree_node_allocator>
888 template <
class iter>
892 kp::constructor(&tmp->data, x);
893 tmp->first_child = 0;
896 tmp->parent =
position.node->parent;
898 tmp->next_sibling =
position.node->next_sibling;
901 if (tmp->next_sibling == 0)
904 tmp->parent->last_child = tmp;
908 tmp->next_sibling->prev_sibling = tmp;
913 template <
class T,
class tree_node_allocator>
914 template <
class iter>
933 template <
class T,
class tree_node_allocator>
934 template <
class iter>
937 kp::destructor(&
position.node->data);
938 kp::constructor(&
position.node->data, x);
942 template <
class T,
class tree_node_allocator>
943 template <
class iter>
954 kp::constructor(&tmp->data, (*from));
955 tmp->first_child = 0;
957 if (current_to->prev_sibling == 0)
959 current_to->parent->first_child = tmp;
963 current_to->prev_sibling->next_sibling = tmp;
965 tmp->prev_sibling = current_to->prev_sibling;
966 if (current_to->next_sibling == 0)
968 current_to->parent->last_child = tmp;
972 current_to->next_sibling->prev_sibling = tmp;
974 tmp->next_sibling = current_to->next_sibling;
975 tmp->parent = current_to->parent;
976 kp::destructor(¤t_to->data);
977 alloc_.deallocate(current_to, 1);
981 tree_node *last = from.node->next_sibling;
983 pre_order_iterator toit = tmp;
987 assert(current_from != 0);
988 if (current_from->first_child != 0)
990 current_from = current_from->first_child;
995 while (current_from->next_sibling == 0 && current_from != start_from)
997 current_from = current_from->parent;
999 assert(current_from != 0);
1001 current_from = current_from->next_sibling;
1002 if (current_from != last)
1008 while (current_from != last);
1013 template <
class T,
class tree_node_allocator>
1015 sibling_iterator orig_begin,
1016 sibling_iterator orig_end,
1017 sibling_iterator new_begin,
1018 sibling_iterator new_end)
1020 tree_node *orig_first = orig_begin.node;
1023 while ((++orig_begin) != orig_end)
1024 orig_last = orig_last->next_sibling;
1026 while ((++new_begin) != new_end)
1027 new_last = new_last->next_sibling;
1031 pre_order_iterator ret;
1034 pre_order_iterator tt =
insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1040 if (new_first == new_last)
1042 new_first = new_first->next_sibling;
1050 if (next == orig_last)
1052 next = next->next_sibling;
1053 erase((pre_order_iterator)orig_first);
1061 template <
class T,
class tree_node_allocator>
1062 template <
typename iter>
1065 if (
position.node->first_child == 0)
1071 tmp->parent =
position.node->parent;
1072 tmp = tmp->next_sibling;
1092 template <
class T,
class tree_node_allocator>
1093 template <
typename iter>
1102 last = last->next_sibling;
1105 if (first->prev_sibling == 0)
1107 first->parent->first_child = last->next_sibling;
1111 first->prev_sibling->next_sibling = last->next_sibling;
1113 if (last->next_sibling == 0)
1115 last->parent->last_child = first->prev_sibling;
1119 last->next_sibling->prev_sibling = first->prev_sibling;
1121 if (
position.node->first_child == 0)
1123 position.node->first_child = first;
1125 first->prev_sibling = 0;
1129 position.node->last_child->next_sibling = first;
1130 first->prev_sibling =
position.node->last_child;
1133 last->next_sibling = 0;
1139 if (pos == last)
break;
1140 pos = pos->next_sibling;
1146 template <
class T,
class tree_node_allocator>
1149 if (from.node->first_child == 0)
return position;
1153 template <
class T,
class tree_node_allocator>
1161 if (dst == src)
return source;
1164 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1165 else src->parent->first_child = src->next_sibling;
1166 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1167 else src->parent->last_child = src->prev_sibling;
1170 if (dst->next_sibling != 0) dst->next_sibling->prev_sibling = src;
1171 else dst->parent->last_child = src;
1172 src->next_sibling = dst->next_sibling;
1173 dst->next_sibling = src;
1174 src->prev_sibling = dst;
1175 src->parent = dst->parent;
1180 template <
class T,
class tree_node_allocator>
1188 if (dst == src)
return source;
1191 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1192 else src->parent->first_child = src->next_sibling;
1193 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1194 else src->parent->last_child = src->prev_sibling;
1197 if (dst->prev_sibling != 0) dst->prev_sibling->next_sibling = src;
1198 else dst->parent->first_child = src;
1199 src->prev_sibling = dst->prev_sibling;
1200 dst->prev_sibling = src;
1201 src->next_sibling = dst;
1202 src->parent = dst->parent;
1206 template <
class T,
class tree_node_allocator>
1214 if (dst == src)
return source;
1217 tree_node *b_prev_sibling = dst->prev_sibling;
1218 tree_node *b_next_sibling = dst->next_sibling;
1225 if (src->prev_sibling != 0) src->prev_sibling->next_sibling = src->next_sibling;
1226 else src->parent->first_child = src->next_sibling;
1227 if (src->next_sibling != 0) src->next_sibling->prev_sibling = src->prev_sibling;
1228 else src->parent->last_child = src->prev_sibling;
1231 if (b_prev_sibling != 0) b_prev_sibling->next_sibling = src;
1232 else b_parent->first_child = src;
1233 if (b_next_sibling != 0) b_next_sibling->prev_sibling = src;
1234 else b_parent->last_child = src;
1235 src->prev_sibling = b_prev_sibling;
1236 src->next_sibling = b_next_sibling;
1237 src->parent = b_parent;
1241 template <
class T,
class tree_node_allocator>
1243 sibling_iterator from1, sibling_iterator from2,
1244 bool duplicate_leaves)
1246 sibling_iterator fnd;
1247 while (from1 != from2)
1249 if ((fnd = std::find(to1, to2, (*from1))) != to2)
1251 if (from1.begin() == from1.end())
1253 if (duplicate_leaves)
1258 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1270 template <
class T,
class tree_node_allocator>
1274 sort(from, to, comp, deep);
1277 template <
class T,
class tree_node_allocator>
1278 template <
class StrictWeakOrdering>
1280 StrictWeakOrdering comp,
bool deep)
1282 if (from == to)
return;
1286 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1287 sibling_iterator it = from, it2 = to;
1290 nodes.insert(it.node);
1297 tree_node *prev = from.node->prev_sibling;
1298 tree_node *next = it2.node->next_sibling;
1299 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >
::iterator nit = nodes.begin(), eit = nodes.end();
1302 if ((*nit)->parent != 0)
1303 (*nit)->parent->first_child = (*nit);
1305 else prev->next_sibling = (*nit);
1310 (*nit)->prev_sibling = prev;
1312 prev->next_sibling = (*nit);
1318 prev->next_sibling = (*eit);
1321 (*eit)->next_sibling = next;
1322 (*eit)->prev_sibling = prev;
1325 if ((*eit)->parent != 0)
1326 (*eit)->parent->last_child = (*eit);
1328 else next->prev_sibling = (*eit);
1332 sibling_iterator bcs(*nodes.begin());
1333 sibling_iterator ecs(*eit);
1343 template <
class T,
class tree_node_allocator>
1344 template <
typename iter>
1347 std::equal_to<T> comp;
1348 return equal(one_, two, three_, comp);
1351 template <
class T,
class tree_node_allocator>
1352 template <
typename iter>
1355 std::equal_to<T> comp;
1356 return equal_subtree(one_, two_, comp);
1359 template <
class T,
class tree_node_allocator>
1360 template <
typename iter,
class BinaryPredicate>
1363 pre_order_iterator one(one_), three(three_);
1367 while (one != two &&
is_valid(three))
1369 if (!fun(*one, *three))
1379 template <
class T,
class tree_node_allocator>
1380 template <
typename iter,
class BinaryPredicate>
1383 pre_order_iterator one(one_), two(two_);
1385 if (!fun(*one, *two))
return false;
1390 template <
class T,
class tree_node_allocator>
1399 template <
class T,
class tree_node_allocator>
1406 template <
class T,
class tree_node_allocator>
1410 pre_order_iterator it =
begin(), eit =
end();
1419 template <
class T,
class tree_node_allocator>
1422 pre_order_iterator it =
begin(), eit =
end();
1426 template <
class T,
class tree_node_allocator>
1432 while (pos->parent != 0)
1440 template <
class T,
class tree_node_allocator>
1444 if (pos == 0)
return 0;
1446 unsigned int ret = 1;
1451 while ((pos = pos->next_sibling))
1456 template <
class T,
class tree_node_allocator>
1460 unsigned int ret = 0;
1461 while (pos->next_sibling &&
1462 pos->next_sibling != head &&
1463 pos->next_sibling != feet)
1466 pos = pos->next_sibling;
1471 template <
class T,
class tree_node_allocator>
1477 if (it.node->prev_sibling)
1478 it.node->prev_sibling->next_sibling = nxt;
1480 it.node->parent->first_child = nxt;
1481 nxt->prev_sibling = it.node->prev_sibling;
1484 nxtnxt->prev_sibling = it.node;
1486 it.node->parent->last_child = it.node;
1487 nxt->next_sibling = it.node;
1488 it.node->prev_sibling = nxt;
1489 it.node->next_sibling = nxtnxt;
1507 template <
class T,
class tree_node_allocator>
1509 const iterator_base&
end)
const
1512 pre_order_iterator tmp =
begin;
1515 if (tmp == it)
return true;
1521 template <
class T,
class tree_node_allocator>
1524 if (it.node == 0 || it.node == feet)
return false;
1528 template <
class T,
class tree_node_allocator>
1531 unsigned int ind = 0;
1532 if (it.node->parent == 0)
1534 while (it.node->prev_sibling != head)
1536 it.node = it.node->prev_sibling;
1542 while (it.node->prev_sibling != 0)
1544 it.node = it.node->prev_sibling;
1552 template <
class T,
class tree_node_allocator>
1559 tmp = tmp->next_sibling;
1569 template <
class T,
class tree_node_allocator>
1571 : node(0), skip_current_children_(false)
1575 template <
class T,
class tree_node_allocator>
1577 : node(tn), skip_current_children_(false)
1581 template <
class T,
class tree_node_allocator>
1587 template <
class T,
class tree_node_allocator>
1590 return &(node->data);
1593 template <
class T,
class tree_node_allocator>
1596 if (other.node != this->node)
return true;
1600 template <
class T,
class tree_node_allocator>
1603 if (other.node == this->node)
return true;
1607 template <
class T,
class tree_node_allocator>
1610 if (other.node != this->node)
return true;
1614 template <
class T,
class tree_node_allocator>
1617 if (other.node == this->node)
return true;
1621 template <
class T,
class tree_node_allocator>
1624 if (other.node != this->node)
return true;
1628 template <
class T,
class tree_node_allocator>
1631 if (other.node == this->node)
return true;
1635 template <
class T,
class tree_node_allocator>
1638 sibling_iterator ret(node->first_child);
1639 ret.parent_ = this->node;
1643 template <
class T,
class tree_node_allocator>
1646 sibling_iterator ret(0);
1651 template <
class T,
class tree_node_allocator>
1654 skip_current_children_ =
true;
1657 template <
class T,
class tree_node_allocator>
1661 if (pos == 0)
return 0;
1663 unsigned int ret = 1;
1664 while (pos != node->last_child)
1667 pos = pos->next_sibling;
1676 template <
class T,
class tree_node_allocator>
1682 template <
class T,
class tree_node_allocator>
1688 template <
class T,
class tree_node_allocator>
1690 : iterator_base(other.node)
1694 template <
class T,
class tree_node_allocator>
1696 : iterator_base(other.node)
1698 if (this->node == 0)
1700 if (other.range_last() != 0)
1701 this->node = other.range_last();
1703 this->node = other.parent_;
1709 template <
class T,
class tree_node_allocator>
1712 assert(this->node != 0);
1713 if (!this->skip_current_children_ && this->node->first_child != 0)
1715 this->node = this->node->first_child;
1719 this->skip_current_children_ =
false;
1720 while (this->node->next_sibling == 0)
1722 this->node = this->node->parent;
1723 if (this->node == 0)
1726 this->node = this->node->next_sibling;
1731 template <
class T,
class tree_node_allocator>
1734 assert(this->node != 0);
1735 if (this->node->prev_sibling)
1737 this->node = this->node->prev_sibling;
1738 while (this->node->last_child)
1739 this->node = this->node->last_child;
1743 this->node = this->node->parent;
1744 if (this->node == 0)
1750 template <
class T,
class tree_node_allocator>
1753 pre_order_iterator copy = *
this;
1758 template <
class T,
class tree_node_allocator>
1761 pre_order_iterator copy = *
this;
1766 template <
class T,
class tree_node_allocator>
1777 template <
class T,
class tree_node_allocator>
1792 template <
class T,
class tree_node_allocator>
1798 template <
class T,
class tree_node_allocator>
1804 template <
class T,
class tree_node_allocator>
1806 : iterator_base(other.node)
1810 template <
class T,
class tree_node_allocator>
1812 : iterator_base(other.node)
1814 if (this->node == 0)
1816 if (other.range_last() != 0)
1817 this->node = other.range_last();
1819 this->node = other.parent_;
1825 template <
class T,
class tree_node_allocator>
1828 assert(this->node != 0);
1829 if (this->node->next_sibling == 0)
1831 this->node = this->node->parent;
1832 this->skip_current_children_ =
false;
1836 this->node = this->node->next_sibling;
1837 if (this->skip_current_children_)
1839 this->skip_current_children_ =
false;
1843 while (this->node->first_child)
1844 this->node = this->node->first_child;
1850 template <
class T,
class tree_node_allocator>
1853 assert(this->node != 0);
1854 if (this->skip_current_children_ || this->node->last_child == 0)
1856 this->skip_current_children_ =
false;
1857 while (this->node->prev_sibling == 0)
1858 this->node = this->node->parent;
1859 this->node = this->node->prev_sibling;
1863 this->node = this->node->last_child;
1868 template <
class T,
class tree_node_allocator>
1871 post_order_iterator copy = *
this;
1876 template <
class T,
class tree_node_allocator>
1879 post_order_iterator copy = *
this;
1885 template <
class T,
class tree_node_allocator>
1896 template <
class T,
class tree_node_allocator>
1907 template <
class T,
class tree_node_allocator>
1910 assert(this->node != 0);
1911 while (this->node->first_child)
1912 this->node = this->node->first_child;
1918 template <
class T,
class tree_node_allocator>
1922 set_first_parent_();
1925 template <
class T,
class tree_node_allocator>
1929 set_first_parent_();
1932 template <
class T,
class tree_node_allocator>
1934 : iterator_base(other.node)
1936 set_first_parent_();
1939 template <
class T,
class tree_node_allocator>
1941 : iterator_base(other.node), first_parent_(other.parent_)
1943 find_leftmost_parent_();
1946 template <
class T,
class tree_node_allocator>
1948 : iterator_base(other.node), first_parent_(other.first_parent_)
1952 template <
class T,
class tree_node_allocator>
1958 if (this->node == 0)
return;
1959 if (this->node->parent != 0)
1960 first_parent_ = this->node->
parent;
1962 find_leftmost_parent_();
1965 template <
class T,
class tree_node_allocator>
1969 tree_node *tmppar = first_parent_;
1970 while (tmppar->prev_sibling)
1972 tmppar = tmppar->prev_sibling;
1973 if (tmppar->first_child)
1974 first_parent_ = tmppar;
1978 template <
class T,
class tree_node_allocator>
1981 assert(this->node != 0);
1983 if (this->node->next_sibling)
1985 this->node = this->node->next_sibling;
1989 int relative_depth = 0;
1993 this->node = this->node->parent;
1994 if (this->node == 0)
return *
this;
1997 while (this->node->next_sibling == 0);
1999 this->node = this->node->next_sibling;
2000 while (this->node->first_child == 0)
2002 if (this->node->next_sibling == 0)
2004 this->node = this->node->next_sibling;
2005 if (this->node == 0)
return *
this;
2007 while (relative_depth < 0 && this->node->first_child != 0)
2009 this->node = this->node->first_child;
2012 if (relative_depth < 0)
2014 if (this->node->next_sibling == 0)
goto upper;
2040 template <
class T,
class tree_node_allocator>
2043 assert(this->node != 0);
2044 if (this->node->prev_sibling != 0)
2046 this->node = this->node->prev_sibling;
2047 assert(this->node != 0);
2048 if (this->node->parent == 0 && this->node->prev_sibling == 0)
2053 tree_node *par = this->node->parent;
2056 par = par->prev_sibling;
2063 while (par->last_child == 0);
2064 this->node = par->last_child;
2069 template <
class T,
class tree_node_allocator>
2072 fixed_depth_iterator copy = *
this;
2077 template <
class T,
class tree_node_allocator>
2080 fixed_depth_iterator copy = *
this;
2085 template <
class T,
class tree_node_allocator>
2096 template <
class T,
class tree_node_allocator>
2112 template <
class T,
class tree_node_allocator>
2119 template <
class T,
class tree_node_allocator>
2126 template <
class T,
class tree_node_allocator>
2128 : iterator_base(other.node)
2133 template <
class T,
class tree_node_allocator>
2135 : iterator_base(other), parent_(other.parent_)
2139 template <
class T,
class tree_node_allocator>
2143 if (this->node == 0)
return;
2144 if (this->node->parent != 0)
2145 parent_ = this->node->
parent;
2148 template <
class T,
class tree_node_allocator>
2156 template <
class T,
class tree_node_allocator>
2159 if (this->node) this->node = this->node->prev_sibling;
2163 this->node = parent_->last_child;
2168 template <
class T,
class tree_node_allocator>
2171 sibling_iterator copy = *
this;
2176 template <
class T,
class tree_node_allocator>
2179 sibling_iterator copy = *
this;
2184 template <
class T,
class tree_node_allocator>
2195 template <
class T,
class tree_node_allocator>
2206 template <
class T,
class tree_node_allocator>
2209 tree_node *tmp = parent_->first_child;
2213 template <
class T,
class tree_node_allocator>
2216 return parent_->last_child;