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> > >
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;
153 sibling_iterator begin()
const;
154 sibling_iterator end()
const;
158 bool skip_current_children_;
226 void set_first_parent_();
227 void find_leftmost_parent_();
256 inline pre_order_iterator
begin()
const;
258 inline pre_order_iterator
end()
const;
264 fixed_depth_iterator
begin_fixed(
const iterator_base&,
unsigned int)
const;
266 fixed_depth_iterator
end_fixed(
const iterator_base&,
unsigned int)
const;
268 sibling_iterator
begin(
const iterator_base&)
const;
270 sibling_iterator
end(
const iterator_base&)
const;
273 template<
typename iter> iter
parent(iter)
const;
284 template<
typename iter> iter
erase(iter);
313 sibling_iterator
replace(sibling_iterator orig_begin, sibling_iterator orig_end,
314 sibling_iterator new_begin, sibling_iterator new_end);
319 template<
typename iter> iter
reparent(iter
position, sibling_iterator begin, sibling_iterator end);
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);
331 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
332 bool duplicate_leaves =
false);
334 void sort(sibling_iterator from, sibling_iterator to,
bool deep =
false);
335 template<
class StrictWeakOrdering>
336 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp,
bool deep =
false);
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;
348 void subtree(
tree&, sibling_iterator from, sibling_iterator to)
const;
350 void swap(sibling_iterator it);
357 int depth(
const iterator_base&)
const;
364 const iterator_base& end)
const;
369 unsigned int index(sibling_iterator it)
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)
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>
586 template <
class T,
class tree_node_allocator>
592 template <
class T,
class tree_node_allocator>
598 while (tmp->first_child)
599 tmp = tmp->first_child;
604 template <
class T,
class tree_node_allocator>
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>
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;
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>
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;
1041 if (new_first == new_last)
1043 new_first = new_first->next_sibling;
1051 if (next == orig_last)
1053 next = next->next_sibling;
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>
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);
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>
1420 template <
class T,
class tree_node_allocator>
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>
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;
Iterator which traverses only the nodes at a given depth from the root.
Comparator class for iterators (compares the actual node content, not pointer values).
Base class for iterators, only pointers stored, no traversal logic.
void skip_children()
When called, the next increment/decrement skips children of this node.
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Depth-first iterator, first accessing the children, then the node itself.
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Depth-first iterator, first accessing the node, then its children.
Iterator which traverses only the nodes which are siblings of each other.
A node in the tree, combining links to other nodes as well as the actual data.
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
bool equal(const iter &one, const iter &two, const iter &three) const
Compare two ranges of nodes (compares nodes as well as tree structure).
sibling_iterator child(const iterator_base &position, unsigned int) const
Inverse of 'index': return the n-th child of the node at position.
void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
Merge with other tree, creating new branches and leaves only if they are not already present.
T value_type
Value of the data stored at a node.
pre_order_iterator iterator
The default iterator type throughout the tree class.
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
iter move_ontop(iter target, iter source)
Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
sibling_iterator insert(sibling_iterator position, const T &x)
Specialisation of previous member.
void sort(sibling_iterator from, sibling_iterator to, bool deep=false)
Sort (std::sort only moves values of nodes, this one moves children as well).
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
iter insert_subtree(iter position, const iterator_base &subtree)
Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
iter reparent(iter position, iter from)
Move all child nodes of 'from' to be children of 'position'.
int depth(const iterator_base &) const
Compute the depth to the root.
sibling_iterator end(const iterator_base &) const
Return sibling iterator to the end of the children of a given node.
iter parent(iter) const
Return iterator to the parent of a node.
bool is_valid(const iterator_base &) const
Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
iter append_child(iter position, iter other_position)
Append the node (plus its children) at other_position as a child of position.
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
iter append_child(iter position)
Insert empty node as last child of node pointed to by position.
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
unsigned int index(sibling_iterator it) const
Determine the index of a node in the range of siblings to which it belongs.
bool is_in_subtree(const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
Determine whether node at position is in the subtrees with root in the range.
void clear()
Erase all nodes of the tree.
sibling_iterator begin(const iterator_base &) const
Return sibling iterator to the first child of given node.
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
iter append_children(iter position, sibling_iterator from, sibling_iterator to)
Append the nodes in the from-to range (plus their children) as children of position.
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to the first node at a given depth.
unsigned int number_of_children(const iterator_base &) const
Count the number of children of node at position.
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to end of the nodes at given depth.
iter append_child(iter position, const T &x)
Insert node as last child of node pointed to by position.
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
bool empty() const
Check if tree is empty.
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
int size() const
Count the total number of nodes.
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
iter replace(iter position, const iterator_base &from)
Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see abov...
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
tree subtree(sibling_iterator from, sibling_iterator to) const
Extract a new tree formed by the range of siblings plus all their children.
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
pre_order_iterator end() const
Return iterator to the end of the tree.
sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
Replace string of siblings (plus their children) with copy of a new string (with children); see above...
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
SGMLApplication::Position position