76 template <
class T1,
class T2>
79 new ((
void *) p) T1(val);
106 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;
122 tree(
const iterator_base&);
128 #ifdef __SGI_STL_PORT 129 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t> {
144 T& operator*()
const;
145 T* operator->()
const;
148 void skip_children();
150 unsigned int number_of_children()
const;
240 void set_first_parent_();
241 void find_leftmost_parent_();
261 tree_node *range_first()
const;
262 tree_node *range_last()
const;
312 template<
typename iter>
static iter parent(iter);
314 template<
typename iter> iter previous_sibling(iter)
const;
316 template<
typename iter> iter next_sibling(iter)
const;
318 template<
typename iter> iter next_at_same_depth(iter)
const;
323 template<
typename iter> iter erase(iter);
328 template<
typename iter> iter append_child(iter position);
329 template<
typename iter> iter prepend_child(iter position);
331 template<
typename iter> iter append_child(iter position,
const T& x);
332 template<
typename iter> iter prepend_child(iter position,
const T& x);
334 template<
typename iter> iter append_child(iter position, iter other_position);
335 template<
typename iter> iter prepend_child(iter position, iter other_position);
343 template<
typename iter> iter insert(iter position,
const T& x);
347 template<
typename iter> iter insert_subtree(iter position,
const iterator_base& subtree);
349 template<
typename iter> iter insert_after(iter position,
const T& x);
351 template<
typename iter> iter insert_subtree_after(iter position,
const iterator_base& subtree);
354 template<
typename iter> iter replace(iter position,
const T& x);
356 template<
typename iter> iter replace(iter position,
const iterator_base& from);
362 template<
typename iter> iter flatten(iter position);
366 template<
typename iter> iter reparent(iter position, iter from);
369 template<
typename iter> iter wrap(iter position,
const T& x);
372 template<
typename iter> iter move_after(iter target, iter source);
374 template<
typename iter> iter move_before(iter target, iter source);
377 template<
typename iter> iter move_ontop(iter target, iter source);
381 bool duplicate_leaves=
false);
384 template<
class StrictWeakOrdering>
387 template<
typename iter>
388 bool equal(
const iter& one,
const iter& two,
const iter& three)
const;
389 template<
typename iter,
class BinaryPredicate>
390 bool equal(
const iter& one,
const iter& two,
const iter& three, BinaryPredicate)
const;
391 template<
typename iter>
392 bool equal_subtree(
const iter& one,
const iter& two)
const;
393 template<
typename iter,
class BinaryPredicate>
394 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
401 void swap(iterator, iterator);
412 int max_depth()
const;
416 static unsigned int number_of_children(
const iterator_base&);
442 void head_initialise_();
446 template<
class StrictWeakOrdering>
453 static StrictWeakOrdering comp;
503 template <
class T,
class tree_node_allocator>
509 template <
class T,
class tree_node_allocator>
516 template <
class T,
class tree_node_allocator>
521 replace(begin(), other);
524 template <
class T,
class tree_node_allocator>
528 alloc_.deallocate(head,1);
529 alloc_.deallocate(feet,1);
532 template <
class T,
class tree_node_allocator>
535 head = alloc_.allocate(1,0);
536 feet = alloc_.allocate(1,0);
541 head->prev_sibling=0;
542 head->next_sibling=feet;
547 feet->prev_sibling=head;
548 feet->next_sibling=0;
551 template <
class T,
class tree_node_allocator>
557 template <
class T,
class tree_node_allocator>
564 template <
class T,
class tree_node_allocator>
568 pre_order_iterator it=other.
begin(), to=begin();
569 while(it!=other.
end()) {
570 to=insert(to, (*it));
576 while(it!=other.
end()) {
585 template <
class T,
class tree_node_allocator>
589 while(head->next_sibling!=feet)
590 erase(pre_order_iterator(head->next_sibling));
593 template<
class T,
class tree_node_allocator>
597 if(it.node==0)
return;
599 tree_node *cur=it.node->first_child;
605 erase_children(pre_order_iterator(prev));
607 alloc_.deallocate(prev,1);
609 it.node->first_child=0;
610 it.node->last_child=0;
614 template<
class T,
class tree_node_allocator>
618 tree_node *cur=it.node;
638 alloc_.deallocate(cur,1);
642 template <
class T,
class tree_node_allocator>
645 return pre_order_iterator(head->next_sibling);
648 template <
class T,
class tree_node_allocator>
651 return pre_order_iterator(feet);
654 template <
class T,
class tree_node_allocator>
657 return breadth_first_queued_iterator(head->next_sibling);
660 template <
class T,
class tree_node_allocator>
663 return breadth_first_queued_iterator();
666 template <
class T,
class tree_node_allocator>
669 tree_node *tmp=head->next_sibling;
674 return post_order_iterator(tmp);
677 template <
class T,
class tree_node_allocator>
680 return post_order_iterator(feet);
683 template <
class T,
class tree_node_allocator>
686 tree_node *tmp=pos.node;
687 unsigned int curdepth=0;
695 throw std::range_error(
"tree: begin_fixed out of range");
707 template <
class T,
class tree_node_allocator>
711 tree_node *tmp=pos.node;
712 unsigned int curdepth=1;
717 throw std::range_error(
"tree: end_fixed out of range");
725 template <
class T,
class tree_node_allocator>
729 if(pos.node->first_child==0) {
732 return pos.node->first_child;
735 template <
class T,
class tree_node_allocator>
738 sibling_iterator ret(0);
739 ret.parent_=pos.node;
743 template <
class T,
class tree_node_allocator>
746 tree_node *tmp=head->next_sibling;
751 return leaf_iterator(tmp);
754 template <
class T,
class tree_node_allocator>
757 return leaf_iterator(feet);
760 template <
class T,
class tree_node_allocator>
761 template <
typename iter>
764 assert(position.node!=0);
765 return iter(position.node->parent);
768 template <
class T,
class tree_node_allocator>
769 template <
typename iter>
772 assert(position.node!=0);
774 ret.node=position.node->prev_sibling;
778 template <
class T,
class tree_node_allocator>
779 template <
typename iter>
782 assert(position.node!=0);
784 ret.node=position.node->next_sibling;
788 template <
class T,
class tree_node_allocator>
789 template <
typename iter>
792 assert(position.node!=0);
795 if(position.node->next_sibling) {
796 ret.node=position.node->next_sibling;
799 int relative_depth=0;
802 ret.node=ret.node->parent;
803 if(ret.node==0)
return ret;
805 }
while(ret.node->next_sibling==0);
807 ret.node=ret.node->next_sibling;
808 while(ret.node->first_child==0) {
809 if(ret.node->next_sibling==0)
811 ret.node=ret.node->next_sibling;
812 if(ret.node==0)
return ret;
814 while(relative_depth<0 && ret.node->first_child!=0) {
815 ret.node=ret.node->first_child;
818 if(relative_depth<0) {
819 if(ret.node->next_sibling==0)
goto upper;
826 template <
class T,
class tree_node_allocator>
827 template <
typename iter>
830 assert(position.node!=head);
831 assert(position.node);
833 tree_node *tmp=alloc_.allocate(1,0);
838 tmp->
parent=position.node;
839 if(position.node->last_child!=0) {
840 position.node->last_child->next_sibling=tmp;
846 position.node->last_child=tmp;
851 template <
class T,
class tree_node_allocator>
852 template <
typename iter>
855 assert(position.node!=head);
856 assert(position.node);
858 tree_node *tmp=alloc_.allocate(1,0);
863 tmp->
parent=position.node;
864 if(position.node->first_child!=0) {
865 position.node->first_child->prev_sibling=tmp;
871 position.node->prev_child=tmp;
876 template <
class T,
class tree_node_allocator>
877 template <
class iter>
884 assert(position.node!=head);
885 assert(position.node);
887 tree_node* tmp = alloc_.allocate(1,0);
892 tmp->
parent=position.node;
893 if(position.node->last_child!=0) {
894 position.node->last_child->next_sibling=tmp;
900 position.node->last_child=tmp;
905 template <
class T,
class tree_node_allocator>
906 template <
class iter>
909 assert(position.node!=head);
910 assert(position.node);
912 tree_node* tmp = alloc_.allocate(1,0);
917 tmp->
parent=position.node;
918 if(position.node->first_child!=0) {
919 position.node->first_child->prev_sibling=tmp;
925 position.node->first_child=tmp;
930 template <
class T,
class tree_node_allocator>
931 template <
class iter>
934 assert(position.node!=head);
935 assert(position.node);
937 sibling_iterator aargh=append_child(position, value_type());
938 return replace(aargh, other);
941 template <
class T,
class tree_node_allocator>
942 template <
class iter>
945 assert(position.node!=head);
946 assert(position.node);
948 sibling_iterator aargh=prepend_child(position, value_type());
949 return replace(aargh, other);
952 template <
class T,
class tree_node_allocator>
953 template <
class iter>
956 assert(position.node!=head);
957 assert(position.node);
962 insert_subtree(position.end(), from);
968 template <
class T,
class tree_node_allocator>
969 template <
class iter>
972 assert(position.node!=head);
973 assert(position.node);
978 insert_subtree(position.begin(), from);
984 template <
class T,
class tree_node_allocator>
987 assert(head->next_sibling==feet);
991 template <
class T,
class tree_node_allocator>
992 template <
class iter>
995 if(position.node==0) {
999 tree_node* tmp = alloc_.allocate(1,0);
1004 tmp->
parent=position.node->parent;
1007 position.node->prev_sibling=tmp;
1011 tmp->
parent->first_child=tmp;
1018 template <
class T,
class tree_node_allocator>
1021 tree_node* tmp = alloc_.allocate(1,0);
1027 if(position.node==0) {
1028 tmp->
parent=position.parent_;
1030 tmp->
parent->last_child=tmp;
1033 tmp->
parent=position.node->parent;
1035 position.node->prev_sibling=tmp;
1040 tmp->
parent->first_child=tmp;
1047 template <
class T,
class tree_node_allocator>
1048 template <
class iter>
1051 tree_node* tmp = alloc_.allocate(1,0);
1056 tmp->
parent=position.node->parent;
1059 position.node->next_sibling=tmp;
1063 tmp->
parent->last_child=tmp;
1071 template <
class T,
class tree_node_allocator>
1072 template <
class iter>
1076 iter it=insert(position, value_type());
1078 return replace(it, subtree);
1081 template <
class T,
class tree_node_allocator>
1082 template <
class iter>
1086 iter it=insert_after(position, value_type());
1088 return replace(it, subtree);
1101 template <
class T,
class tree_node_allocator>
1102 template <
class iter>
1110 template <
class T,
class tree_node_allocator>
1111 template <
class iter>
1114 assert(position.node!=head);
1115 tree_node *current_from=from.node;
1116 tree_node *start_from=from.node;
1117 tree_node *current_to =position.node;
1121 erase_children(position);
1123 tree_node* tmp = alloc_.allocate(1,0);
1128 if(current_to->
parent!=0)
1129 current_to->
parent->first_child=tmp;
1136 if(current_to->
parent!=0)
1137 current_to->
parent->last_child=tmp;
1145 alloc_.deallocate(current_to,1);
1149 tree_node *last=from.node->next_sibling;
1151 pre_order_iterator toit=tmp;
1154 assert(current_from!=0);
1157 toit=append_child(toit, current_from->
data);
1160 while(current_from->
next_sibling==0 && current_from!=start_from) {
1161 current_from=current_from->
parent;
1163 assert(current_from!=0);
1166 if(current_from!=last) {
1167 toit=append_child(parent(toit), current_from->
data);
1170 }
while(current_from!=last);
1175 template <
class T,
class tree_node_allocator>
1177 sibling_iterator orig_begin,
1178 sibling_iterator orig_end,
1179 sibling_iterator new_begin,
1180 sibling_iterator new_end)
1182 tree_node *orig_first=orig_begin.node;
1183 tree_node *new_first=new_begin.node;
1184 tree_node *orig_last=orig_first;
1185 while((++orig_begin)!=orig_end)
1187 tree_node *new_last=new_first;
1188 while((++new_begin)!=new_end)
1193 pre_order_iterator ret;
1195 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1200 if(new_first==new_last)
1207 tree_node *next=orig_first;
1212 erase((pre_order_iterator)orig_first);
1220 template <
class T,
class tree_node_allocator>
1221 template <
typename iter>
1224 if(position.node->first_child==0)
1227 tree_node *tmp=position.node->first_child;
1229 tmp->
parent=position.node->parent;
1232 if(position.node->next_sibling) {
1233 position.node->last_child->next_sibling=position.node->next_sibling;
1234 position.node->next_sibling->prev_sibling=position.node->last_child;
1237 position.node->parent->last_child=position.node->last_child;
1239 position.node->next_sibling=position.node->first_child;
1240 position.node->next_sibling->prev_sibling=position.node;
1241 position.node->first_child=0;
1242 position.node->last_child=0;
1248 template <
class T,
class tree_node_allocator>
1249 template <
typename iter>
1252 tree_node *first=begin.node;
1253 tree_node *last=first;
1255 assert(first!=position.node);
1257 if(begin==end)
return begin;
1259 while((++begin)!=end) {
1275 if(position.node->first_child==0) {
1276 position.node->first_child=first;
1281 position.node->last_child->next_sibling=first;
1283 position.node->last_child=last;
1287 tree_node *pos=first;
1289 pos->
parent=position.node;
1290 if(pos==last)
break;
1297 template <
class T,
class tree_node_allocator>
1300 if(from.node->first_child==0)
return position;
1301 return reparent(position, from.node->first_child, end(from));
1304 template <
class T,
class tree_node_allocator>
1307 assert(position.node!=0);
1308 sibling_iterator fr=position, to=position;
1310 iter ret = insert(position, x);
1311 reparent(ret, fr, to);
1315 template <
class T,
class tree_node_allocator>
1318 tree_node *dst=target.node;
1319 tree_node *src=source.node;
1323 if(dst==src)
return source;
1336 else dst->
parent->last_child=src;
1344 template <
class T,
class tree_node_allocator>
1347 tree_node *dst=target.node;
1348 tree_node *src=source.node;
1352 if(dst==src)
return source;
1365 else dst->
parent->first_child=src;
1374 template <
class T,
class tree_node_allocator>
1376 sibling_iterator source)
1378 tree_node *dst=target.node;
1379 tree_node *src=source.node;
1380 tree_node *dst_prev_sibling;
1383 assert(dst_prev_sibling);
1388 if(dst==src)
return source;
1389 if(dst_prev_sibling)
1390 if(dst_prev_sibling==src)
1400 if(dst_prev_sibling!=0) dst_prev_sibling->
next_sibling=src;
1411 template <
class T,
class tree_node_allocator>
1414 tree_node *dst=target.node;
1415 tree_node *src=source.node;
1419 if(dst==src)
return source;
1424 tree_node *b_parent=dst->
parent;
1436 if(b_prev_sibling!=0) b_prev_sibling->
next_sibling=src;
1438 if(b_next_sibling!=0) b_next_sibling->
prev_sibling=src;
1446 template <
class T,
class tree_node_allocator>
1448 sibling_iterator from1, sibling_iterator from2,
1449 bool duplicate_leaves)
1451 sibling_iterator fnd;
1452 while(from1!=from2) {
1453 if((fnd=std::find(to1, to2, (*from1))) != to2) {
1454 if(from1.begin()==from1.end()) {
1455 if(duplicate_leaves)
1456 append_child(parent(to1), (*from1));
1459 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1463 insert_subtree(to2, from1);
1470 template <
class T,
class tree_node_allocator>
1474 sort(from, to, comp, deep);
1477 template <
class T,
class tree_node_allocator>
1478 template <
class StrictWeakOrdering>
1480 StrictWeakOrdering comp,
bool deep)
1482 if(from==to)
return;
1486 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1487 sibling_iterator it=from, it2=to;
1489 nodes.insert(it.node);
1496 tree_node *prev=from.node->prev_sibling;
1497 tree_node *next=it2.node->next_sibling;
1498 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >
::iterator nit=nodes.begin(), eit=nodes.end();
1500 if((*nit)->parent!=0)
1501 (*nit)->parent->first_child=(*nit);
1507 (*nit)->prev_sibling=prev;
1518 (*eit)->next_sibling=next;
1521 if((*eit)->parent!=0)
1522 (*eit)->
parent->last_child=(*eit);
1527 sibling_iterator bcs(*nodes.begin());
1528 sibling_iterator ecs(*eit);
1531 sort(begin(bcs), end(bcs), comp, deep);
1537 template <
class T,
class tree_node_allocator>
1538 template <
typename iter>
1541 std::equal_to<T> comp;
1542 return equal(one_, two, three_, comp);
1545 template <
class T,
class tree_node_allocator>
1546 template <
typename iter>
1549 std::equal_to<T> comp;
1550 return equal_subtree(one_, two_, comp);
1553 template <
class T,
class tree_node_allocator>
1554 template <
typename iter,
class BinaryPredicate>
1557 pre_order_iterator one(one_), three(three_);
1561 while(one!=two && is_valid(three)) {
1562 if(!fun(*one,*three))
1564 if(one.number_of_children()!=three.number_of_children())
1572 template <
class T,
class tree_node_allocator>
1573 template <
typename iter,
class BinaryPredicate>
1576 pre_order_iterator one(one_), two(two_);
1578 if(!fun(*one,*two))
return false;
1579 if(number_of_children(one)!=number_of_children(two))
return false;
1580 return equal(begin(one),end(one),begin(two),fun);
1583 template <
class T,
class tree_node_allocator>
1592 template <
class T,
class tree_node_allocator>
1599 template <
class T,
class tree_node_allocator>
1603 pre_order_iterator it=begin(), eit=end();
1611 template <
class T,
class tree_node_allocator>
1615 pre_order_iterator it=top, eit=top;
1616 eit.skip_children();
1625 template <
class T,
class tree_node_allocator>
1628 pre_order_iterator it=begin(), eit=end();
1632 template <
class T,
class tree_node_allocator>
1635 tree_node* pos=it.node;
1645 template <
class T,
class tree_node_allocator>
1648 return max_depth(begin());
1652 template <
class T,
class tree_node_allocator>
1655 tree_node *tmp=pos.node;
1656 int curdepth=0, maxdepth=0;
1659 if(tmp==pos.node)
return maxdepth;
1664 if(tmp==0)
return maxdepth;
1668 if(tmp==pos.node)
return maxdepth;
1673 maxdepth=std::max(curdepth, maxdepth);
1677 template <
class T,
class tree_node_allocator>
1680 tree_node *pos=it.node->first_child;
1681 if(pos==0)
return 0;
1693 template <
class T,
class tree_node_allocator>
1696 tree_node *pos=it.node;
1717 template <
class T,
class tree_node_allocator>
1720 tree_node *nxt=it.node->next_sibling;
1722 if(it.node->prev_sibling)
1723 it.node->prev_sibling->next_sibling=nxt;
1725 it.node->
parent->first_child=nxt;
1731 it.node->parent->last_child=it.node;
1733 it.node->prev_sibling=nxt;
1738 template <
class T,
class tree_node_allocator>
1742 if(one.node->next_sibling==two.node) swap(one);
1743 else if(two.node->next_sibling==one.node) swap(two);
1745 tree_node *nxt1=one.node->next_sibling;
1746 tree_node *nxt2=two.node->next_sibling;
1747 tree_node *pre1=one.node->prev_sibling;
1748 tree_node *pre2=two.node->prev_sibling;
1749 tree_node *par1=one.node->parent;
1750 tree_node *par2=two.node->parent;
1753 one.node->parent=par2;
1757 one.node->prev_sibling=pre2;
1761 two.node->parent=par1;
1765 two.node->prev_sibling=pre1;
1785 template <
class T,
class tree_node_allocator>
1787 const iterator_base& end)
const 1790 pre_order_iterator tmp=begin;
1792 if(tmp==it)
return true;
1798 template <
class T,
class tree_node_allocator>
1801 if(it.node==0 || it.node==feet || it.node==head)
return false;
1805 template <
class T,
class tree_node_allocator>
1809 if(it.node->parent==0) {
1810 while(it.node->prev_sibling!=head) {
1811 it.node=it.node->prev_sibling;
1816 while(it.node->prev_sibling!=0) {
1817 it.node=it.node->prev_sibling;
1825 template <
class T,
class tree_node_allocator>
1828 tree_node *tmp=it.node->first_child;
1841 template <
class T,
class tree_node_allocator>
1843 : node(0), skip_current_children_(false)
1847 template <
class T,
class tree_node_allocator>
1853 template <
class T,
class tree_node_allocator>
1859 template <
class T,
class tree_node_allocator>
1865 template <
class T,
class tree_node_allocator>
1868 if(other.
node!=this->node)
return true;
1872 template <
class T,
class tree_node_allocator>
1875 if(other.
node==this->node)
return true;
1879 template <
class T,
class tree_node_allocator>
1882 if(other.
node!=this->node)
return true;
1886 template <
class T,
class tree_node_allocator>
1889 if(other.
node==this->node)
return true;
1893 template <
class T,
class tree_node_allocator>
1896 if(other.
node!=this->node)
return true;
1900 template <
class T,
class tree_node_allocator>
1903 if(other.
node==this->node)
return true;
1907 template <
class T,
class tree_node_allocator>
1910 if(other.
node!=this->node)
return true;
1914 template <
class T,
class tree_node_allocator>
1917 if(other.
node==this->node)
return true;
1921 template <
class T,
class tree_node_allocator>
1932 template <
class T,
class tree_node_allocator>
1940 template <
class T,
class tree_node_allocator>
1946 template <
class T,
class tree_node_allocator>
1950 if(pos==0)
return 0;
1964 template <
class T,
class tree_node_allocator>
1970 template <
class T,
class tree_node_allocator>
1976 template <
class T,
class tree_node_allocator>
1982 template <
class T,
class tree_node_allocator>
1996 template <
class T,
class tree_node_allocator>
1999 assert(this->
node!=0);
2015 template <
class T,
class tree_node_allocator>
2018 assert(this->
node!=0);
2032 template <
class T,
class tree_node_allocator>
2040 template <
class T,
class tree_node_allocator>
2048 template <
class T,
class tree_node_allocator>
2058 template <
class T,
class tree_node_allocator>
2072 template <
class T,
class tree_node_allocator>
2078 template <
class T,
class tree_node_allocator>
2084 template <
class T,
class tree_node_allocator>
2090 template <
class T,
class tree_node_allocator>
2104 template <
class T,
class tree_node_allocator>
2107 assert(this->
node!=0);
2125 template <
class T,
class tree_node_allocator>
2128 assert(this->
node!=0);
2141 template <
class T,
class tree_node_allocator>
2149 template <
class T,
class tree_node_allocator>
2158 template <
class T,
class tree_node_allocator>
2168 template <
class T,
class tree_node_allocator>
2178 template <
class T,
class tree_node_allocator>
2181 assert(this->
node!=0);
2189 template <
class T,
class tree_node_allocator>
2195 template <
class T,
class tree_node_allocator>
2202 template <
class T,
class tree_node_allocator>
2209 template <
class T,
class tree_node_allocator>
2212 if(other.
node!=this->node)
return true;
2216 template <
class T,
class tree_node_allocator>
2219 if(other.
node==this->node)
return true;
2223 template <
class T,
class tree_node_allocator>
2226 assert(this->
node!=0);
2230 while(sib!=this->
end()) {
2242 template <
class T,
class tree_node_allocator>
2250 template <
class T,
class tree_node_allocator>
2264 template <
class T,
class tree_node_allocator>
2271 template <
class T,
class tree_node_allocator>
2278 template <
class T,
class tree_node_allocator>
2285 template <
class T,
class tree_node_allocator>
2292 template <
class T,
class tree_node_allocator>
2298 template <
class T,
class tree_node_allocator>
2305 template <
class T,
class tree_node_allocator>
2312 template <
class T,
class tree_node_allocator>
2318 if(this->
node==0)
return;
2325 template <
class T,
class tree_node_allocator>
2337 template <
class T,
class tree_node_allocator>
2340 assert(this->
node!=0);
2346 int relative_depth=0;
2350 if(this->
node==0)
return *
this;
2359 if(this->
node==0)
return *
this;
2365 if(relative_depth<0) {
2392 template <
class T,
class tree_node_allocator>
2395 assert(this->
node!=0);
2398 assert(this->
node!=0);
2399 if(this->
node->
parent==0 && this->node->prev_sibling==0)
2416 template <
class T,
class tree_node_allocator>
2424 template <
class T,
class tree_node_allocator>
2432 template <
class T,
class tree_node_allocator>
2442 template <
class T,
class tree_node_allocator>
2457 template <
class T,
class tree_node_allocator>
2464 template <
class T,
class tree_node_allocator>
2471 template <
class T,
class tree_node_allocator>
2478 template <
class T,
class tree_node_allocator>
2484 template <
class T,
class tree_node_allocator>
2488 if(this->
node==0)
return;
2493 template <
class T,
class tree_node_allocator>
2501 template <
class T,
class tree_node_allocator>
2512 template <
class T,
class tree_node_allocator>
2520 template <
class T,
class tree_node_allocator>
2528 template <
class T,
class tree_node_allocator>
2538 template <
class T,
class tree_node_allocator>
2548 template <
class T,
class tree_node_allocator>
2555 template <
class T,
class tree_node_allocator>
2563 template <
class T,
class tree_node_allocator>
2569 template <
class T,
class tree_node_allocator>
2575 template <
class T,
class tree_node_allocator>
2581 template <
class T,
class tree_node_allocator>
2594 template <
class T,
class tree_node_allocator>
2597 assert(this->
node!=0);
2608 template <
class T,
class tree_node_allocator>
2611 assert(this->
node!=0);
2622 template <
class T,
class tree_node_allocator>
2630 template <
class T,
class tree_node_allocator>
2639 template <
class T,
class tree_node_allocator>
2649 template <
class T,
class tree_node_allocator>
bool operator!=(const post_order_iterator &) const
Definition: tree.hh:1866
bool operator!=(const breadth_first_queued_iterator &) const
Definition: tree.hh:2210
void clear()
Erase all nodes of the tree.
Definition: tree.hh:586
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid...
Definition: tree.hh:1103
Breadth-first iterator, using a queue.
Definition: tree.hh:200
sibling_iterator & operator-=(unsigned int)
Definition: tree.hh:2539
breadth_first_queued_iterator & operator++()
Definition: tree.hh:2224
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.hh:1718
fixed_depth_iterator & operator-=(unsigned int)
Definition: tree.hh:2433
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.hh:1947
breadth_first_queued_iterator end_breadth_first() const
Return breadth-first iterator to end of the nodes at given depth.
Definition: tree.hh:661
pre_order_iterator & operator++()
Definition: tree.hh:1997
leaf_iterator & operator++()
Definition: tree.hh:2595
bool operator==(const post_order_iterator &) const
Definition: tree.hh:1873
breadth_first_queued_iterator()
Definition: tree.hh:2190
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.hh:594
T * pointer
Definition: tree.hh:135
tree_node_< T > * prev_sibling
Definition: tree.hh:102
bool operator!=(const pre_order_iterator &) const
Definition: tree.hh:1880
tree()
Definition: tree.hh:504
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition: tree.hh:1250
tree_node * range_first() const
Definition: tree.hh:2549
bool operator!=(const leaf_iterator &) const
Definition: tree.hh:1908
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.hh:616
tree_node * range_last() const
Definition: tree.hh:2556
iterator_base()
Definition: tree.hh:1842
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.hh:643
void destructor(T1 *p)
Definition: tree.hh:89
pre_order_iterator & operator--()
Definition: tree.hh:2016
size_t size_type
Definition: tree.hh:137
fixed_depth_iterator & operator++()
Definition: tree.hh:2338
leaf_iterator end_leaf() const
Return leaf iterator to the last leaf of the tree.
Definition: tree.hh:755
sibling_iterator end() const
Definition: tree.hh:1933
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.
Definition: tree.hh:1786
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.hh:985
bool operator()(const typename tree< T, tree_node_allocator >::iterator_base &one, const typename tree< T, tree_node_allocator >::iterator_base &two) const
Definition: tree.hh:433
~tree()
Definition: tree.hh:525
tree_node_allocator alloc_
Definition: tree.hh:441
void copy_(const tree< T, tree_node_allocator > &other)
Definition: tree.hh:565
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.hh:1941
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.hh:1222
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
Definition: tree.hh:1678
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
Definition: tree.hh:1694
pre_order_iterator()
Definition: tree.hh:1965
sibling_iterator & operator+=(unsigned int)
Definition: tree.hh:2529
tree_node * node
Definition: tree.hh:155
post_order_iterator & operator--()
Definition: tree.hh:2126
bool operator==(const breadth_first_queued_iterator &) const
Definition: tree.hh:2217
tree_node * head
Definition: tree.hh:439
Comparator class for two nodes of a tree (used for sorting and searching).
Definition: tree.hh:447
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.hh:1345
bool operator!=(const fixed_depth_iterator &) const
Definition: tree.hh:2306
sibling_iterator & operator++()
Definition: tree.hh:2494
bool operator==(const fixed_depth_iterator &) const
Definition: tree.hh:2299
tree_node_< T > * next_sibling
Definition: tree.hh:102
T value_type
Definition: tree.hh:134
post_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2159
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.hh:780
int depth(const iterator_base &) const
Compute the depth to the root.
Definition: tree.hh:1633
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.hh:245
post_order_iterator()
Definition: tree.hh:2073
breadth_first_queued_iterator begin_breadth_first() const
Return breadth-first iterator to the first node at a given depth.
Definition: tree.hh:655
tree_node_< T > * first_child
Definition: tree.hh:101
void operator=(const tree< T, tree_node_allocator > &)
Definition: tree.hh:552
fixed_depth_iterator()
Definition: tree.hh:2265
sibling_iterator & operator--()
Definition: tree.hh:2502
bool equal_subtree(const iter &one, const iter &two) const
Definition: tree.hh:1547
T data
Definition: tree.hh:103
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.hh:1049
fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to the first node at a given depth from the given iterator.
Definition: tree.hh:684
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.hh:98
bool operator==(const sibling_iterator &) const
Definition: tree.hh:1901
leaf_iterator()
Definition: tree.hh:2564
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.hh:667
tree_node * parent_
Definition: tree.hh:263
void find_leftmost_parent_()
Definition: tree.hh:2326
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.hh:131
pre_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2059
tree_node_< T > * last_child
Definition: tree.hh:101
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...
Definition: tree.hh:1073
sibling_iterator begin() const
Definition: tree.hh:1922
Iterator which traverses only the leaves.
Definition: tree.hh:269
breadth_first_queued_iterator breadth_first_iterator
Definition: tree.hh:218
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.hh:770
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.hh:649
leaf_iterator & operator-=(unsigned int)
Definition: tree.hh:2650
sibling_iterator child(const iterator_base &position, unsigned int) const
Inverse of 'index': return the n-th child of the node at position.
Definition: tree.hh:1826
bool operator()(const tree_node *a, const tree_node *b)
Definition: tree.hh:451
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.hh:2179
sibling_iterator()
Definition: tree.hh:2458
tree_node * first_parent_
Definition: tree.hh:238
T * operator->() const
Definition: tree.hh:1860
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.hh:790
leaf_iterator & operator+=(unsigned int)
Definition: tree.hh:2640
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...
Definition: tree.hh:1447
fixed_depth_iterator & operator--()
Definition: tree.hh:2393
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.hh:179
T value_type
Value of the data stored at a node.
Definition: tree.hh:112
post_order_iterator & operator++()
Definition: tree.hh:2105
ptrdiff_t difference_type
Definition: tree.hh:138
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
Definition: tree.hh:678
breadth_first_queued_iterator & operator+=(unsigned int)
Definition: tree.hh:2251
iter append_child(iter position)
Insert empty node as last/first child of node pointed to by position.
Definition: tree.hh:828
bool operator==(const leaf_iterator &) const
Definition: tree.hh:1915
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.hh:993
void constructor(T1 *p, T2 &val)
Definition: tree.hh:77
bool equal(const iter &one, const iter &two, const iter &three) const
Compare two ranges of nodes (compares nodes as well as tree structure).
Definition: tree.hh:1539
bool skip_current_children_
Definition: tree.hh:157
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth iterator to end of the nodes at given depth from the given iterator.
Definition: tree.hh:708
std::bidirectional_iterator_tag iterator_category
Definition: tree.hh:139
post_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2169
T & operator*() const
Definition: tree.hh:1854
tree subtree(sibling_iterator from, sibling_iterator to) const
Extract a new tree formed by the range of siblings plus all their children.
Definition: tree.hh:1584
bool operator!=(const sibling_iterator &) const
Definition: tree.hh:1894
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).
Definition: tree.hh:1471
unsigned int index(sibling_iterator it) const
Determine the index of a node in the range of siblings to which it belongs.
Definition: tree.hh:1806
iter wrap(iter position, const T &x)
Replace node with a new node, making the old node a child of the new node.
Definition: tree.hh:1305
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.hh:221
tree_node_< T > tree_node
Definition: tree.hh:109
void head_initialise_()
Definition: tree.hh:533
static iter parent(iter)
Return iterator to the parent of a node.
Definition: tree.hh:762
bool operator==(const pre_order_iterator &) const
Definition: tree.hh:1887
iter move_ontop(iter target, iter source)
Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target')...
Definition: tree.hh:1412
iter insert_subtree_after(iter position, const iterator_base &subtree)
Insert node (with children) pointed to by subtree as next sibling of node pointed to by position...
Definition: tree.hh:1083
void set_first_parent_()
Definition: tree.hh:2313
tree_node_< T > * parent
Definition: tree.hh:100
Depth-first iterator, first accessing the node, then its children.
Definition: tree.hh:161
leaf_iterator & operator--()
Definition: tree.hh:2609
bool is_valid(const iterator_base &) const
Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node...
Definition: tree.hh:1799
fixed_depth_iterator & operator+=(unsigned int)
Definition: tree.hh:2443
Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
Definition: tree.hh:431
iter prepend_children(iter position, sibling_iterator from, sibling_iterator to)
Definition: tree.hh:970
int size() const
Count the total number of nodes.
Definition: tree.hh:1600
iter append_children(iter position, sibling_iterator from, sibling_iterator to)
Append the nodes in the from-to range (plus their children) as last/first children of position...
Definition: tree.hh:954
iter prepend_child(iter position)
Definition: tree.hh:853
compare_nodes(StrictWeakOrdering comp)
Definition: tree.hh:449
StrictWeakOrdering comp_
Definition: tree.hh:457
void set_parent_()
Definition: tree.hh:2485
pre_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2049
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.hh:1316
pre_order_iterator iterator
The default iterator types throughout the tree class.
Definition: tree.hh:217
int max_depth() const
Determine the maximal depth of the tree.
Definition: tree.hh:1646
std::queue< tree_node * > traversal_queue
Definition: tree.hh:213
leaf_iterator begin_leaf() const
Return leaf iterator to the first leaf of the tree.
Definition: tree.hh:744
T & reference
Definition: tree.hh:136
bool empty() const
Check if tree is empty.
Definition: tree.hh:1626