369 unsigned int index(sibling_iterator it)
const;
380 return one.node < two.node;
383 tree_node *head, *feet;
385 tree_node_allocator alloc_;
386 void head_initialise_();
387 void copy_(
const tree<T, tree_node_allocator>& other);
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_;
426template <
class T,
class tree_node_allocator>
427bool operator>(
const typename tree<T, tree_node_allocator>::iterator_base& one,
428 const typename tree<T, tree_node_allocator>::iterator_base& two)
430 if (one.node > two.node)
return true;
438template <
class T,
class tree_node_allocator>
439tree<T, tree_node_allocator>::tree()
444template <
class T,
class tree_node_allocator>
445tree<T, tree_node_allocator>::tree(
const T& x)
451template <
class T,
class tree_node_allocator>
452tree<T, tree_node_allocator>::tree(
const iterator_base& other)
459template <
class T,
class tree_node_allocator>
460tree<T, tree_node_allocator>::~tree()
463 alloc_.deallocate(head, 1);
464 alloc_.deallocate(feet, 1);
467template <
class T,
class tree_node_allocator>
468void tree<T, tree_node_allocator>::head_initialise_()
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;
486template <
class T,
class tree_node_allocator>
487void tree<T, tree_node_allocator>::operator=(
const tree<T, tree_node_allocator>& other)
492template <
class T,
class tree_node_allocator>
493tree<T, tree_node_allocator>::tree(
const tree<T, tree_node_allocator>& other)
499template <
class T,
class tree_node_allocator>
500void tree<T, tree_node_allocator>::copy_(
const tree<T, tree_node_allocator>& other)
504 while (it != other.
end())
512 while (it != other.
end())
522template <
class T,
class tree_node_allocator>
526 while (head->next_sibling != feet)
530template<
class T,
class tree_node_allocator>
533 tree_node *cur = it.node->first_child;
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;
548template<
class T,
class tree_node_allocator>
552 tree_node *cur = it.node;
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);
580template <
class T,
class tree_node_allocator>
586template <
class T,
class tree_node_allocator>
592template <
class T,
class tree_node_allocator>
595 tree_node *tmp = head->next_sibling;
598 while (tmp->first_child)
599 tmp = tmp->first_child;
604template <
class T,
class tree_node_allocator>
610template <
class T,
class tree_node_allocator>
613 tree_node *tmp = pos.node;
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;
629template <
class T,
class tree_node_allocator>
633 tree_node *tmp = pos.node;
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;
649template <
class T,
class tree_node_allocator>
652 if (pos.node->first_child == 0)
656 return pos.node->first_child;
659template <
class T,
class tree_node_allocator>
663 ret.parent_ = pos.node;
667template <
class T,
class tree_node_allocator>
668template <
typename iter>
675template <
class T,
class tree_node_allocator>
676template <
typename iter>
681 ret.node =
position.node->prev_sibling;
685template <
class T,
class tree_node_allocator>
686template <
typename iter>
691 ret.node =
position.node->next_sibling;
695template <
class T,
class tree_node_allocator>
696template <
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;
740template <
class T,
class tree_node_allocator>
741template <
typename iter>
746 tree_node* tmp = alloc_.allocate(1, 0);
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;
766template <
class T,
class tree_node_allocator>
776 tree_node* tmp = alloc_.allocate(1, 0);
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;
796template <
class T,
class tree_node_allocator>
806template <
class T,
class tree_node_allocator>
820template <
class T,
class tree_node_allocator>
823 assert(head->next_sibling == feet);
827template <
class T,
class tree_node_allocator>
836 tree_node* tmp = alloc_.allocate(1, 0);
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;
856template <
class T,
class tree_node_allocator>
859 tree_node* tmp = alloc_.allocate(1, 0);
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;
888template <
class T,
class tree_node_allocator>
892 tree_node* tmp = alloc_.allocate(1, 0);
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;
914template <
class T,
class tree_node_allocator>
934template <
class T,
class tree_node_allocator>
938 kp::destructor(&
position.node->data);
939 kp::constructor(&
position.node->data, x);
943template <
class T,
class tree_node_allocator>
948 tree_node *current_from = from.node;
949 tree_node *start_from = from.node;
950 tree_node *current_to =
position.node;
954 tree_node* tmp = alloc_.allocate(1, 0);
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;
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);
1014template <
class T,
class tree_node_allocator>
1021 tree_node *orig_first = orig_begin.node;
1022 tree_node *new_first = new_begin.node;
1023 tree_node *orig_last = orig_first;
1024 while ((++orig_begin) != orig_end)
1025 orig_last = orig_last->next_sibling;
1026 tree_node *new_last = new_first;
1027 while ((++new_begin) != new_end)
1028 new_last = new_last->next_sibling;
1041 if (new_first == new_last)
1043 new_first = new_first->next_sibling;
1048 tree_node *next = orig_first;
1051 if (next == orig_last)
1053 next = next->next_sibling;
1062template <
class T,
class tree_node_allocator>
1063template <
typename iter>
1066 if (
position.node->first_child == 0)
1069 tree_node *tmp =
position.node->first_child;
1072 tmp->parent =
position.node->parent;
1073 tmp = tmp->next_sibling;
1093template <
class T,
class tree_node_allocator>
1094template <
typename iter>
1097 tree_node *first =
begin.node;
1098 tree_node *last = first;
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;
1136 tree_node *pos = first;
1140 if (pos == last)
break;
1141 pos = pos->next_sibling;
1147template <
class T,
class tree_node_allocator>
1150 if (from.node->first_child == 0)
return position;
1154template <
class T,
class tree_node_allocator>
1157 tree_node *dst = target.node;
1158 tree_node *src = source.node;
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;
1181template <
class T,
class tree_node_allocator>
1184 tree_node *dst = target.node;
1185 tree_node *src = source.node;
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;
1207template <
class T,
class tree_node_allocator>
1210 tree_node *dst = target.node;
1211 tree_node *src = source.node;
1215 if (dst == src)
return source;
1218 tree_node *b_prev_sibling = dst->prev_sibling;
1219 tree_node *b_next_sibling = dst->next_sibling;
1220 tree_node *b_parent = dst->parent;
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;
1242template <
class T,
class tree_node_allocator>
1245 bool duplicate_leaves)
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);
1271template <
class T,
class tree_node_allocator>
1275 sort(from, to, comp, deep);
1278template <
class T,
class tree_node_allocator>
1279template <
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);
1344template <
class T,
class tree_node_allocator>
1345template <
typename iter>
1348 std::equal_to<T> comp;
1349 return equal(one_, two, three_, comp);
1352template <
class T,
class tree_node_allocator>
1353template <
typename iter>
1354bool tree<T, tree_node_allocator>::equal_subtree(
const iter& one_,
const iter& two_)
const
1356 std::equal_to<T> comp;
1357 return equal_subtree(one_, two_, comp);
1360template <
class T,
class tree_node_allocator>
1361template <
typename iter,
class BinaryPredicate>
1368 while (one != two &&
is_valid(three))
1370 if (!fun(*one, *three))
1380template <
class T,
class tree_node_allocator>
1381template <
typename iter,
class BinaryPredicate>
1382bool tree<T, tree_node_allocator>::equal_subtree(
const iter& one_,
const iter& two_, BinaryPredicate fun)
const
1386 if (!fun(*one, *two))
return false;
1391template <
class T,
class tree_node_allocator>
1400template <
class T,
class tree_node_allocator>
1407template <
class T,
class tree_node_allocator>
1420template <
class T,
class tree_node_allocator>
1427template <
class T,
class tree_node_allocator>
1430 tree_node* pos = it.node;
1433 while (pos->parent != 0)
1441template <
class T,
class tree_node_allocator>
1444 tree_node *pos = it.node->first_child;
1445 if (pos == 0)
return 0;
1447 unsigned int ret = 1;
1452 while ((pos = pos->next_sibling))
1457template <
class T,
class tree_node_allocator>
1460 tree_node *pos = it.node;
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;
1472template <
class T,
class tree_node_allocator>
1475 tree_node *nxt = it.node->next_sibling;
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;
1483 tree_node *nxtnxt = nxt->next_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;
1508template <
class T,
class tree_node_allocator>
1516 if (tmp == it)
return true;
1522template <
class T,
class tree_node_allocator>
1525 if (it.node == 0 || it.node == feet)
return false;
1529template <
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;
1553template <
class T,
class tree_node_allocator>
1556 tree_node *tmp = it.node->first_child;
1560 tmp = tmp->next_sibling;
1570template <
class T,
class tree_node_allocator>
1571tree<T, tree_node_allocator>::iterator_base::iterator_base()
1572 : node(0), skip_current_children_(false)
1576template <
class T,
class tree_node_allocator>
1577tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
1578 : node(tn), skip_current_children_(false)
1582template <
class T,
class tree_node_allocator>
1583T& tree<T, tree_node_allocator>::iterator_base::operator*()
const
1588template <
class T,
class tree_node_allocator>
1589T* tree<T, tree_node_allocator>::iterator_base::operator->()
const
1591 return &(node->data);
1594template <
class T,
class tree_node_allocator>
1595bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(
const post_order_iterator& other)
const
1597 if (other.node != this->node)
return true;
1601template <
class T,
class tree_node_allocator>
1602bool tree<T, tree_node_allocator>::post_order_iterator::operator==(
const post_order_iterator& other)
const
1604 if (other.node == this->node)
return true;
1608template <
class T,
class tree_node_allocator>
1609bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(
const pre_order_iterator& other)
const
1611 if (other.node != this->node)
return true;
1615template <
class T,
class tree_node_allocator>
1616bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(
const pre_order_iterator& other)
const
1618 if (other.node == this->node)
return true;
1622template <
class T,
class tree_node_allocator>
1623bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(
const sibling_iterator& other)
const
1625 if (other.node != this->node)
return true;
1629template <
class T,
class tree_node_allocator>
1630bool tree<T, tree_node_allocator>::sibling_iterator::operator==(
const sibling_iterator& other)
const
1632 if (other.node == this->node)
return true;
1636template <
class T,
class tree_node_allocator>
1637typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin()
const
1640 ret.parent_ = this->node;
1644template <
class T,
class tree_node_allocator>
1645typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end()
const
1652template <
class T,
class tree_node_allocator>
1655 skip_current_children_ =
true;
1658template <
class T,
class tree_node_allocator>
1661 tree_node *pos = node->first_child;
1662 if (pos == 0)
return 0;
1664 unsigned int ret = 1;
1665 while (pos != node->last_child)
1668 pos = pos->next_sibling;
1677template <
class T,
class tree_node_allocator>
1678tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
1683template <
class T,
class tree_node_allocator>
1684tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
1689template <
class T,
class tree_node_allocator>
1690tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(
const iterator_base &other)
1695template <
class T,
class tree_node_allocator>
1696tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(
const sibling_iterator& other)
1699 if (this->node == 0)
1701 if (other.range_last() != 0)
1702 this->node = other.range_last();
1704 this->node = other.parent_;
1710template <
class T,
class tree_node_allocator>
1711typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
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;
1732template <
class T,
class tree_node_allocator>
1733typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
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)
1751template <
class T,
class tree_node_allocator>
1752typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(
int n)
1759template <
class T,
class tree_node_allocator>
1760typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(
int n)
1767template <
class T,
class tree_node_allocator>
1768typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(
unsigned int num)
1778template <
class T,
class tree_node_allocator>
1779typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(
unsigned int num)
1793template <
class T,
class tree_node_allocator>
1794tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
1799template <
class T,
class tree_node_allocator>
1800tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
1805template <
class T,
class tree_node_allocator>
1806tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(
const iterator_base &other)
1811template <
class T,
class tree_node_allocator>
1812tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(
const sibling_iterator& other)
1815 if (this->node == 0)
1817 if (other.range_last() != 0)
1818 this->node = other.range_last();
1820 this->node = other.parent_;
1826template <
class T,
class tree_node_allocator>
1827typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
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;
1851template <
class T,
class tree_node_allocator>
1852typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
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;
1869template <
class T,
class tree_node_allocator>
1870typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(
int)
1877template <
class T,
class tree_node_allocator>
1878typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(
int)
1886template <
class T,
class tree_node_allocator>
1887typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(
unsigned int num)
1897template <
class T,
class tree_node_allocator>
1898typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(
unsigned int num)
1908template <
class T,
class tree_node_allocator>
1911 assert(this->node != 0);
1912 while (this->node->first_child)
1913 this->node = this->node->first_child;
1919template <
class T,
class tree_node_allocator>
1920tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
1923 set_first_parent_();
1926template <
class T,
class tree_node_allocator>
1927tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
1930 set_first_parent_();
1933template <
class T,
class tree_node_allocator>
1934tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const iterator_base& other)
1937 set_first_parent_();
1940template <
class T,
class tree_node_allocator>
1941tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const sibling_iterator& other)
1944 find_leftmost_parent_();
1947template <
class T,
class tree_node_allocator>
1948tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(
const fixed_depth_iterator& other)
1949 :
iterator_base(other.node), first_parent_(other.first_parent_)
1953template <
class T,
class tree_node_allocator>
1954void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
1959 if (this->node == 0)
return;
1960 if (this->node->parent != 0)
1961 first_parent_ = this->node->parent;
1963 find_leftmost_parent_();
1966template <
class T,
class tree_node_allocator>
1967void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
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;
1979template <
class T,
class tree_node_allocator>
1980typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
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;
2041template <
class T,
class tree_node_allocator>
2042typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
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;
2070template <
class T,
class tree_node_allocator>
2071typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(
int)
2078template <
class T,
class tree_node_allocator>
2079typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(
int)
2086template <
class T,
class tree_node_allocator>
2087typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(
unsigned int num)
2097template <
class T,
class tree_node_allocator>
2098typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(
unsigned int num)
2113template <
class T,
class tree_node_allocator>
2114tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
2120template <
class T,
class tree_node_allocator>
2121tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
2127template <
class T,
class tree_node_allocator>
2128tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(
const iterator_base& other)
2134template <
class T,
class tree_node_allocator>
2135tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(
const sibling_iterator& other)
2140template <
class T,
class tree_node_allocator>
2141void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
2144 if (this->node == 0)
return;
2145 if (this->node->parent != 0)
2146 parent_ = this->node->parent;
2149template <
class T,
class tree_node_allocator>
2150typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
2153 this->node = this->node->next_sibling;
2157template <
class T,
class tree_node_allocator>
2158typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
2160 if (this->node) this->node = this->node->prev_sibling;
2164 this->node = parent_->last_child;
2169template <
class T,
class tree_node_allocator>
2170typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(
int)
2177template <
class T,
class tree_node_allocator>
2178typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(
int)
2185template <
class T,
class tree_node_allocator>
2186typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(
unsigned int num)
2196template <
class T,
class tree_node_allocator>
2197typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(
unsigned int num)
2207template <
class T,
class tree_node_allocator>
2208typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first()
const
2210 tree_node *tmp = parent_->first_child;
2214template <
class T,
class tree_node_allocator>
2215typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last()
const
2217 return parent_->last_child;