40 template <
class T1,
class T2>
41 void constructor(T1* p, T2& val)
43 new ((
void *) p) T1(val);
47 void constructor(T1* p)
53 void destructor(T1* p)
70 template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
93 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t> {
100 typedef T& reference;
101 typedef size_t size_type;
102 typedef ptrdiff_t difference_type;
103 typedef std::bidirectional_iterator_tag iterator_category;
108 T& operator*()
const;
109 T* operator->()
const;
122 bool skip_current_children_;
178 std::queue<tree_node *> traversal_queue;
280 template<
typename iter>
static iter
parent(iter);
291 template<
typename iter> iter
erase(iter);
296 template<
typename iter> iter
append_child(iter position);
297 template<
typename iter> iter prepend_child(iter position);
299 template<
typename iter> iter
append_child(iter position,
const T& x);
300 template<
typename iter> iter prepend_child(iter position,
const T& x);
302 template<
typename iter> iter
append_child(iter position, iter other_position);
303 template<
typename iter> iter prepend_child(iter position, iter other_position);
311 template<
typename iter> iter
insert(iter position,
const T& x);
317 template<
typename iter> iter
insert_after(iter position,
const T& x);
322 template<
typename iter> iter
replace(iter position,
const T& x);
330 template<
typename iter> iter
flatten(iter position);
334 template<
typename iter> iter
reparent(iter position, iter from);
337 template<
typename iter> iter
wrap(iter position,
const T& x);
340 template<
typename iter> iter
move_after(iter target, iter source);
342 template<
typename iter> iter
move_before(iter target, iter source);
345 template<
typename iter> iter
move_ontop(iter target, iter source);
349 bool duplicate_leaves=
false);
352 template<
class StrictWeakOrdering>
355 template<
typename iter>
356 bool equal(
const iter& one,
const iter& two,
const iter& three)
const;
357 template<
typename iter,
class BinaryPredicate>
358 bool equal(
const iter& one,
const iter& two,
const iter& three, BinaryPredicate)
const;
359 template<
typename iter>
360 bool equal_subtree(
const iter& one,
const iter& two)
const;
361 template<
typename iter,
class BinaryPredicate>
362 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
407 return one.node < two.node;
412 tree_node_allocator alloc_;
413 void head_initialise_();
417 template<
class StrictWeakOrdering>
418 class compare_nodes {
420 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
422 bool operator()(
const tree_node *a,
const tree_node *b)
424 return comp_(a->data, b->data);
427 StrictWeakOrdering comp_;
473 template <
class T,
class tree_node_allocator>
479 template <
class T,
class tree_node_allocator>
486 template <
class T,
class tree_node_allocator>
494 template <
class T,
class tree_node_allocator>
498 alloc_.deallocate(head,1);
499 alloc_.deallocate(feet,1);
502 template <
class T,
class tree_node_allocator>
505 head = alloc_.allocate(1,0);
506 feet = alloc_.allocate(1,0);
511 head->prev_sibling=0;
512 head->next_sibling=feet;
517 feet->prev_sibling=head;
518 feet->next_sibling=0;
521 template <
class T,
class tree_node_allocator>
527 template <
class T,
class tree_node_allocator>
534 template <
class T,
class tree_node_allocator>
538 pre_order_iterator it=other.
begin(), to=
begin();
539 while(it!=other.
end()) {
546 while(it!=other.
end()) {
555 template <
class T,
class tree_node_allocator>
559 while(head->next_sibling!=feet)
563 template<
class T,
class tree_node_allocator>
567 if(it.node==0)
return;
574 cur=cur->next_sibling;
576 kp::destructor(&prev->data);
577 alloc_.deallocate(prev,1);
579 it.node->first_child=0;
580 it.node->last_child=0;
584 template<
class T,
class tree_node_allocator>
594 if(cur->prev_sibling==0) {
595 cur->parent->first_child=cur->next_sibling;
598 cur->prev_sibling->next_sibling=cur->next_sibling;
600 if(cur->next_sibling==0) {
601 cur->parent->last_child=cur->prev_sibling;
604 cur->next_sibling->prev_sibling=cur->prev_sibling;
607 kp::destructor(&cur->data);
608 alloc_.deallocate(cur,1);
612 template <
class T,
class tree_node_allocator>
618 template <
class T,
class tree_node_allocator>
624 template <
class T,
class tree_node_allocator>
630 template <
class T,
class tree_node_allocator>
636 template <
class T,
class tree_node_allocator>
641 while(tmp->first_child)
642 tmp=tmp->first_child;
647 template <
class T,
class tree_node_allocator>
653 template <
class T,
class tree_node_allocator>
657 ret.top_node=pos.node;
660 unsigned int curdepth=0;
662 while(tmp->first_child==0) {
663 if(tmp->next_sibling==0) {
666 if(tmp==ret.top_node)
667 throw std::range_error(
"tree: begin_fixed out of range");
670 throw std::range_error(
"tree: begin_fixed out of range");
672 }
while(tmp->next_sibling==0);
674 tmp=tmp->next_sibling;
676 tmp=tmp->first_child;
684 template <
class T,
class tree_node_allocator>
689 unsigned int curdepth=1;
691 while(tmp->first_child==0) {
692 tmp=tmp->next_sibling;
694 throw std::range_error(
"tree: end_fixed out of range");
696 tmp=tmp->first_child;
702 template <
class T,
class tree_node_allocator>
706 if(pos.node->first_child==0) {
709 return pos.node->first_child;
712 template <
class T,
class tree_node_allocator>
716 ret.parent_=pos.node;
720 template <
class T,
class tree_node_allocator>
725 while(tmp->first_child)
726 tmp=tmp->first_child;
731 template <
class T,
class tree_node_allocator>
737 template <
class T,
class tree_node_allocator>
741 while(tmp->first_child)
742 tmp=tmp->first_child;
746 template <
class T,
class tree_node_allocator>
752 template <
class T,
class tree_node_allocator>
753 template <
typename iter>
756 assert(position.node!=0);
757 return iter(position.node->parent);
760 template <
class T,
class tree_node_allocator>
761 template <
typename iter>
764 assert(position.node!=0);
766 ret.node=position.node->prev_sibling;
770 template <
class T,
class tree_node_allocator>
771 template <
typename iter>
774 assert(position.node!=0);
776 ret.node=position.node->next_sibling;
780 template <
class T,
class tree_node_allocator>
781 template <
typename iter>
825 template <
class T,
class tree_node_allocator>
826 template <
typename iter>
829 assert(position.node!=head);
830 assert(position.node);
833 kp::constructor(&tmp->data);
837 tmp->parent=position.node;
838 if(position.node->last_child!=0) {
839 position.node->last_child->next_sibling=tmp;
842 position.node->first_child=tmp;
844 tmp->prev_sibling=position.node->last_child;
845 position.node->last_child=tmp;
850 template <
class T,
class tree_node_allocator>
851 template <
typename iter>
854 assert(position.node!=head);
855 assert(position.node);
857 tree_node *tmp=alloc_.allocate(1,0);
858 kp::constructor(&tmp->data);
862 tmp->parent=position.node;
863 if(position.node->first_child!=0) {
864 position.node->first_child->prev_sibling=tmp;
867 position.node->last_child=tmp;
869 tmp->next_sibling=position.node->first_child;
870 position.node->prev_child=tmp;
875 template <
class T,
class tree_node_allocator>
876 template <
class iter>
883 assert(position.node!=head);
884 assert(position.node);
887 kp::constructor(&tmp->data, x);
891 tmp->parent=position.node;
892 if(position.node->last_child!=0) {
893 position.node->last_child->next_sibling=tmp;
896 position.node->first_child=tmp;
898 tmp->prev_sibling=position.node->last_child;
899 position.node->last_child=tmp;
904 template <
class T,
class tree_node_allocator>
905 template <
class iter>
908 assert(position.node!=head);
909 assert(position.node);
911 tree_node* tmp = alloc_.allocate(1,0);
912 kp::constructor(&tmp->data, x);
916 tmp->parent=position.node;
917 if(position.node->first_child!=0) {
918 position.node->first_child->prev_sibling=tmp;
921 position.node->last_child=tmp;
923 tmp->next_sibling=position.node->first_child;
924 position.node->first_child=tmp;
929 template <
class T,
class tree_node_allocator>
930 template <
class iter>
933 assert(position.node!=head);
934 assert(position.node);
940 template <
class T,
class tree_node_allocator>
941 template <
class iter>
944 assert(position.node!=head);
945 assert(position.node);
947 sibling_iterator aargh=prepend_child(position,
value_type());
951 template <
class T,
class tree_node_allocator>
952 template <
class iter>
955 assert(position.node!=head);
956 assert(position.node);
967 template <
class T,
class tree_node_allocator>
968 template <
class iter>
971 assert(position.node!=head);
972 assert(position.node);
983 template <
class T,
class tree_node_allocator>
986 assert(head->next_sibling==feet);
990 template <
class T,
class tree_node_allocator>
991 template <
class iter>
994 if(position.node==0) {
999 kp::constructor(&tmp->data, x);
1003 tmp->parent=position.node->parent;
1004 tmp->next_sibling=position.node;
1005 tmp->prev_sibling=position.node->prev_sibling;
1006 position.node->prev_sibling=tmp;
1008 if(tmp->prev_sibling==0) {
1010 tmp->parent->first_child=tmp;
1013 tmp->prev_sibling->next_sibling=tmp;
1017 template <
class T,
class tree_node_allocator>
1021 kp::constructor(&tmp->data, x);
1025 tmp->next_sibling=position.node;
1026 if(position.node==0) {
1027 tmp->parent=position.parent_;
1028 tmp->prev_sibling=position.range_last();
1029 tmp->parent->last_child=tmp;
1032 tmp->parent=position.node->parent;
1033 tmp->prev_sibling=position.node->prev_sibling;
1034 position.node->prev_sibling=tmp;
1037 if(tmp->prev_sibling==0) {
1039 tmp->parent->first_child=tmp;
1042 tmp->prev_sibling->next_sibling=tmp;
1046 template <
class T,
class tree_node_allocator>
1047 template <
class iter>
1051 kp::constructor(&tmp->data, x);
1055 tmp->parent=position.node->parent;
1056 tmp->prev_sibling=position.node;
1057 tmp->next_sibling=position.node->next_sibling;
1058 position.node->next_sibling=tmp;
1060 if(tmp->next_sibling==0) {
1062 tmp->parent->last_child=tmp;
1065 tmp->next_sibling->prev_sibling=tmp;
1070 template <
class T,
class tree_node_allocator>
1071 template <
class iter>
1080 template <
class T,
class tree_node_allocator>
1081 template <
class iter>
1100 template <
class T,
class tree_node_allocator>
1101 template <
class iter>
1104 kp::destructor(&position.node->data);
1105 kp::constructor(&position.node->data, x);
1109 template <
class T,
class tree_node_allocator>
1110 template <
class iter>
1113 assert(position.node!=head);
1123 kp::constructor(&tmp->data, (*from));
1126 if(current_to->prev_sibling==0) {
1127 if(current_to->parent!=0)
1128 current_to->parent->first_child=tmp;
1131 current_to->prev_sibling->next_sibling=tmp;
1133 tmp->prev_sibling=current_to->prev_sibling;
1134 if(current_to->next_sibling==0) {
1135 if(current_to->parent!=0)
1136 current_to->parent->last_child=tmp;
1139 current_to->next_sibling->prev_sibling=tmp;
1141 tmp->next_sibling=current_to->next_sibling;
1142 tmp->parent=current_to->parent;
1143 kp::destructor(¤t_to->data);
1144 alloc_.deallocate(current_to,1);
1148 tree_node *last=from.node->next_sibling;
1153 assert(current_from!=0);
1154 if(current_from->first_child != 0) {
1155 current_from=current_from->first_child;
1159 while(current_from->next_sibling==0 && current_from!=start_from) {
1160 current_from=current_from->parent;
1162 assert(current_from!=0);
1164 current_from=current_from->next_sibling;
1165 if(current_from!=last) {
1169 }
while(current_from!=last);
1174 template <
class T,
class tree_node_allocator>
1184 while((++orig_begin)!=orig_end)
1185 orig_last=orig_last->next_sibling;
1187 while((++new_begin)!=new_end)
1188 new_last=new_last->next_sibling;
1199 if(new_first==new_last)
1201 new_first=new_first->next_sibling;
1210 next=next->next_sibling;
1219 template <
class T,
class tree_node_allocator>
1220 template <
typename iter>
1223 if(position.node->first_child==0)
1226 tree_node *tmp=position.node->first_child;
1228 tmp->parent=position.node->parent;
1229 tmp=tmp->next_sibling;
1231 if(position.node->next_sibling) {
1232 position.node->last_child->next_sibling=position.node->next_sibling;
1233 position.node->next_sibling->prev_sibling=position.node->last_child;
1236 position.node->parent->last_child=position.node->last_child;
1238 position.node->next_sibling=position.node->first_child;
1239 position.node->next_sibling->prev_sibling=position.node;
1240 position.node->first_child=0;
1241 position.node->last_child=0;
1247 template <
class T,
class tree_node_allocator>
1248 template <
typename iter>
1254 assert(first!=position.node);
1256 if(begin==end)
return begin;
1258 while((++begin)!=end) {
1259 last=last->next_sibling;
1262 if(first->prev_sibling==0) {
1263 first->parent->first_child=last->next_sibling;
1266 first->prev_sibling->next_sibling=last->next_sibling;
1268 if(last->next_sibling==0) {
1269 last->parent->last_child=first->prev_sibling;
1272 last->next_sibling->prev_sibling=first->prev_sibling;
1274 if(position.node->first_child==0) {
1275 position.node->first_child=first;
1276 position.node->last_child=last;
1277 first->prev_sibling=0;
1280 position.node->last_child->next_sibling=first;
1281 first->prev_sibling=position.node->last_child;
1282 position.node->last_child=last;
1284 last->next_sibling=0;
1288 pos->parent=position.node;
1289 if(pos==last)
break;
1290 pos=pos->next_sibling;
1296 template <
class T,
class tree_node_allocator>
1299 if(from.node->first_child==0)
return position;
1300 return reparent(position, from.node->first_child,
end(from));
1303 template <
class T,
class tree_node_allocator>
1306 assert(position.node!=0);
1309 iter ret =
insert(position, x);
1314 template <
class T,
class tree_node_allocator>
1322 if(dst==src)
return source;
1323 if(dst->next_sibling)
1324 if(dst->next_sibling==src)
1328 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1329 else src->parent->first_child=src->next_sibling;
1330 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1331 else src->parent->last_child=src->prev_sibling;
1334 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1335 else dst->parent->last_child=src;
1336 src->next_sibling=dst->next_sibling;
1337 dst->next_sibling=src;
1338 src->prev_sibling=dst;
1339 src->parent=dst->parent;
1343 template <
class T,
class tree_node_allocator>
1351 if(dst==src)
return source;
1352 if(dst->prev_sibling)
1353 if(dst->prev_sibling==src)
1357 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1358 else src->parent->first_child=src->next_sibling;
1359 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1360 else src->parent->last_child=src->prev_sibling;
1363 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1364 else dst->parent->first_child=src;
1365 src->prev_sibling=dst->prev_sibling;
1366 dst->prev_sibling=src;
1367 src->next_sibling=dst;
1368 src->parent=dst->parent;
1373 template <
class T,
class tree_node_allocator>
1375 sibling_iterator source)
1377 tree_node *dst=target.node;
1378 tree_node *src=source.node;
1379 tree_node *dst_prev_sibling;
1381 dst_prev_sibling=target.parent_->last_child;
1382 assert(dst_prev_sibling);
1384 else dst_prev_sibling=dst->prev_sibling;
1387 if(dst==src)
return source;
1388 if(dst_prev_sibling)
1389 if(dst_prev_sibling==src)
1393 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1394 else src->parent->first_child=src->next_sibling;
1395 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1396 else src->parent->last_child=src->prev_sibling;
1399 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1400 else target.parent_->first_child=src;
1401 src->prev_sibling=dst_prev_sibling;
1403 dst->prev_sibling=src;
1404 src->parent=dst->parent;
1406 src->next_sibling=dst;
1410 template <
class T,
class tree_node_allocator>
1418 if(dst==src)
return source;
1421 tree_node *b_prev_sibling=dst->prev_sibling;
1422 tree_node *b_next_sibling=dst->next_sibling;
1429 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1430 else src->parent->first_child=src->next_sibling;
1431 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1432 else src->parent->last_child=src->prev_sibling;
1435 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1436 else b_parent->first_child=src;
1437 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1438 else b_parent->last_child=src;
1439 src->prev_sibling=b_prev_sibling;
1440 src->next_sibling=b_next_sibling;
1441 src->parent=b_parent;
1445 template <
class T,
class tree_node_allocator>
1448 bool duplicate_leaves)
1451 while(from1!=from2) {
1452 if((fnd=std::find(to1, to2, (*from1))) != to2) {
1453 if(from1.begin()==from1.end()) {
1454 if(duplicate_leaves)
1458 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1469 template <
class T,
class tree_node_allocator>
1473 sort(from, to, comp, deep);
1476 template <
class T,
class tree_node_allocator>
1477 template <
class StrictWeakOrdering>
1479 StrictWeakOrdering comp,
bool deep)
1481 if(from==to)
return;
1485 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1486 sibling_iterator it=from, it2=to;
1488 nodes.insert(it.node);
1495 tree_node *prev=from.node->prev_sibling;
1496 tree_node *next=it2.node->next_sibling;
1497 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >
::iterator nit=nodes.begin(), eit=nodes.end();
1499 if((*nit)->parent!=0)
1500 (*nit)->parent->first_child=(*nit);
1502 else prev->next_sibling=(*nit);
1506 (*nit)->prev_sibling=prev;
1508 prev->next_sibling=(*nit);
1514 prev->next_sibling=(*eit);
1517 (*eit)->next_sibling=next;
1518 (*eit)->prev_sibling=prev;
1520 if((*eit)->parent!=0)
1521 (*eit)->parent->last_child=(*eit);
1523 else next->prev_sibling=(*eit);
1526 sibling_iterator bcs(*nodes.begin());
1527 sibling_iterator ecs(*eit);
1536 template <
class T,
class tree_node_allocator>
1537 template <
typename iter>
1540 std::equal_to<T> comp;
1541 return equal(one_, two, three_, comp);
1544 template <
class T,
class tree_node_allocator>
1545 template <
typename iter>
1548 std::equal_to<T> comp;
1549 return equal_subtree(one_, two_, comp);
1552 template <
class T,
class tree_node_allocator>
1553 template <
typename iter,
class BinaryPredicate>
1556 pre_order_iterator one(one_), three(three_);
1560 while(one!=two &&
is_valid(three)) {
1561 if(!fun(*one,*three))
1563 if(one.number_of_children()!=three.number_of_children())
1571 template <
class T,
class tree_node_allocator>
1572 template <
typename iter,
class BinaryPredicate>
1575 pre_order_iterator one(one_), two(two_);
1577 if(!fun(*one,*two))
return false;
1582 template <
class T,
class tree_node_allocator>
1591 template <
class T,
class tree_node_allocator>
1598 template <
class T,
class tree_node_allocator>
1610 template <
class T,
class tree_node_allocator>
1624 template <
class T,
class tree_node_allocator>
1631 template <
class T,
class tree_node_allocator>
1637 while(pos->parent!=0) {
1644 template <
class T,
class tree_node_allocator>
1647 tree_node* pos=it.node;
1650 while(pos->parent!=0 && pos!=root.node) {
1657 template <
class T,
class tree_node_allocator>
1661 for(
tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
1668 template <
class T,
class tree_node_allocator>
1673 if(tmp==0 || tmp==head || tmp==feet)
return -1;
1675 int curdepth=0, maxdepth=0;
1677 while(tmp->first_child==0) {
1678 if(tmp==pos.node)
return maxdepth;
1679 if(tmp->next_sibling==0) {
1683 if(tmp==0)
return maxdepth;
1685 }
while(tmp->next_sibling==0);
1687 if(tmp==pos.node)
return maxdepth;
1688 tmp=tmp->next_sibling;
1690 tmp=tmp->first_child;
1692 maxdepth=std::max(curdepth, maxdepth);
1696 template <
class T,
class tree_node_allocator>
1700 if(pos==0)
return 0;
1707 while((pos=pos->next_sibling))
1712 template <
class T,
class tree_node_allocator>
1718 while(pos->next_sibling &&
1719 pos->next_sibling!=head &&
1720 pos->next_sibling!=feet) {
1722 pos=pos->next_sibling;
1726 while(pos->prev_sibling &&
1727 pos->prev_sibling!=head &&
1728 pos->prev_sibling!=feet) {
1730 pos=pos->prev_sibling;
1736 template <
class T,
class tree_node_allocator>
1741 if(it.node->prev_sibling)
1742 it.node->prev_sibling->next_sibling=nxt;
1744 it.node->parent->first_child=nxt;
1745 nxt->prev_sibling=it.node->prev_sibling;
1748 nxtnxt->prev_sibling=it.node;
1750 it.node->parent->last_child=it.node;
1751 nxt->next_sibling=it.node;
1752 it.node->prev_sibling=nxt;
1753 it.node->next_sibling=nxtnxt;
1757 template <
class T,
class tree_node_allocator>
1761 if(one.node->next_sibling==two.node)
swap(one);
1762 else if(two.node->next_sibling==one.node)
swap(two);
1772 one.node->parent=par2;
1773 one.node->next_sibling=nxt2;
1774 if(nxt2) nxt2->prev_sibling=one.node;
1775 else par2->last_child=one.node;
1776 one.node->prev_sibling=pre2;
1777 if(pre2) pre2->next_sibling=one.node;
1778 else par2->first_child=one.node;
1780 two.node->parent=par1;
1781 two.node->next_sibling=nxt1;
1782 if(nxt1) nxt1->prev_sibling=two.node;
1783 else par1->last_child=two.node;
1784 two.node->prev_sibling=pre1;
1785 if(pre1) pre1->next_sibling=two.node;
1786 else par1->first_child=two.node;
1804 template <
class T,
class tree_node_allocator>
1811 if(tmp==it)
return true;
1817 template <
class T,
class tree_node_allocator>
1820 if(it.node==0 || it.node==feet || it.node==head)
return false;
1824 template <
class T,
class tree_node_allocator>
1828 if(it.node->parent==0) {
1829 while(it.node->prev_sibling!=head) {
1830 it.node=it.node->prev_sibling;
1835 while(it.node->prev_sibling!=0) {
1836 it.node=it.node->prev_sibling;
1843 template <
class T,
class tree_node_allocator>
1847 if(it.node->parent==0) {
1848 tmp=head->next_sibling;
1850 tmp = tmp->next_sibling;
1855 tmp=it.node->parent->first_child;
1858 tmp = tmp->next_sibling;
1866 template <
class T,
class tree_node_allocator>
1872 tmp=tmp->next_sibling;
1882 template <
class T,
class tree_node_allocator>
1884 : node(0), skip_current_children_(false)
1888 template <
class T,
class tree_node_allocator>
1890 : node(tn), skip_current_children_(false)
1894 template <
class T,
class tree_node_allocator>
1900 template <
class T,
class tree_node_allocator>
1903 return &(node->data);
1906 template <
class T,
class tree_node_allocator>
1909 if(other.node!=this->node)
return true;
1913 template <
class T,
class tree_node_allocator>
1916 if(other.node==this->node)
return true;
1920 template <
class T,
class tree_node_allocator>
1923 if(other.node!=this->node)
return true;
1927 template <
class T,
class tree_node_allocator>
1930 if(other.node==this->node)
return true;
1934 template <
class T,
class tree_node_allocator>
1937 if(other.node!=this->node)
return true;
1941 template <
class T,
class tree_node_allocator>
1944 if(other.node==this->node)
return true;
1948 template <
class T,
class tree_node_allocator>
1951 if(other.node!=this->node)
return true;
1955 template <
class T,
class tree_node_allocator>
1958 if(other.node==this->node && other.top_node==this->top_node)
return true;
1962 template <
class T,
class tree_node_allocator>
1965 if(node->first_child==0)
1968 sibling_iterator ret(node->first_child);
1969 ret.parent_=this->node;
1973 template <
class T,
class tree_node_allocator>
1976 sibling_iterator ret(0);
1981 template <
class T,
class tree_node_allocator>
1984 skip_current_children_=
true;
1987 template <
class T,
class tree_node_allocator>
1990 skip_current_children_=skip;
1993 template <
class T,
class tree_node_allocator>
1997 if(pos==0)
return 0;
2000 while(pos!=node->last_child) {
2002 pos=pos->next_sibling;
2011 template <
class T,
class tree_node_allocator>
2017 template <
class T,
class tree_node_allocator>
2023 template <
class T,
class tree_node_allocator>
2025 : iterator_base(other.node)
2029 template <
class T,
class tree_node_allocator>
2031 : iterator_base(other.node)
2034 if(other.range_last()!=0)
2035 this->node=other.range_last();
2037 this->node=other.parent_;
2043 template <
class T,
class tree_node_allocator>
2046 assert(this->node!=0);
2047 if(!this->skip_current_children_ && this->node->first_child != 0) {
2048 this->node=this->node->first_child;
2051 this->skip_current_children_=
false;
2052 while(this->node->next_sibling==0) {
2053 this->node=this->node->parent;
2057 this->node=this->node->next_sibling;
2062 template <
class T,
class tree_node_allocator>
2065 assert(this->node!=0);
2066 if(this->node->prev_sibling) {
2067 this->node=this->node->prev_sibling;
2068 while(this->node->last_child)
2069 this->node=this->node->last_child;
2072 this->node=this->node->parent;
2079 template <
class T,
class tree_node_allocator>
2082 pre_order_iterator copy = *
this;
2087 template <
class T,
class tree_node_allocator>
2090 pre_order_iterator copy = *
this;
2095 template <
class T,
class tree_node_allocator>
2105 template <
class T,
class tree_node_allocator>
2119 template <
class T,
class tree_node_allocator>
2125 template <
class T,
class tree_node_allocator>
2131 template <
class T,
class tree_node_allocator>
2133 : iterator_base(other.node)
2137 template <
class T,
class tree_node_allocator>
2139 : iterator_base(other.node)
2142 if(other.range_last()!=0)
2143 this->node=other.range_last();
2145 this->node=other.parent_;
2151 template <
class T,
class tree_node_allocator>
2154 assert(this->node!=0);
2155 if(this->node->next_sibling==0) {
2156 this->node=this->node->parent;
2157 this->skip_current_children_=
false;
2160 this->node=this->node->next_sibling;
2161 if(this->skip_current_children_) {
2162 this->skip_current_children_=
false;
2165 while(this->node->first_child)
2166 this->node=this->node->first_child;
2172 template <
class T,
class tree_node_allocator>
2175 assert(this->node!=0);
2176 if(this->skip_current_children_ || this->node->last_child==0) {
2177 this->skip_current_children_=
false;
2178 while(this->node->prev_sibling==0)
2179 this->node=this->node->parent;
2180 this->node=this->node->prev_sibling;
2183 this->node=this->node->last_child;
2188 template <
class T,
class tree_node_allocator>
2191 post_order_iterator copy = *
this;
2196 template <
class T,
class tree_node_allocator>
2199 post_order_iterator copy = *
this;
2205 template <
class T,
class tree_node_allocator>
2215 template <
class T,
class tree_node_allocator>
2225 template <
class T,
class tree_node_allocator>
2228 assert(this->node!=0);
2229 while(this->node->first_child)
2230 this->node=this->node->first_child;
2236 template <
class T,
class tree_node_allocator>
2242 template <
class T,
class tree_node_allocator>
2246 traversal_queue.push(tn);
2249 template <
class T,
class tree_node_allocator>
2251 : iterator_base(other.node)
2253 traversal_queue.push(other.node);
2256 template <
class T,
class tree_node_allocator>
2259 if(other.node!=this->node)
return true;
2263 template <
class T,
class tree_node_allocator>
2266 if(other.node==this->node)
return true;
2270 template <
class T,
class tree_node_allocator>
2273 assert(this->node!=0);
2276 sibling_iterator sib=this->
begin();
2277 while(sib!=this->
end()) {
2278 traversal_queue.push(sib.node);
2281 traversal_queue.pop();
2282 if(traversal_queue.size()>0)
2283 this->node=traversal_queue.front();
2289 template <
class T,
class tree_node_allocator>
2292 breadth_first_queued_iterator copy = *
this;
2297 template <
class T,
class tree_node_allocator>
2311 template <
class T,
class tree_node_allocator>
2317 template <
class T,
class tree_node_allocator>
2319 : iterator_base(tn), top_node(0)
2323 template <
class T,
class tree_node_allocator>
2325 : iterator_base(other.node), top_node(0)
2329 template <
class T,
class tree_node_allocator>
2331 : iterator_base(other.node), top_node(0)
2335 template <
class T,
class tree_node_allocator>
2337 : iterator_base(other.node), top_node(other.top_node)
2341 template <
class T,
class tree_node_allocator>
2344 if(other.node==this->node && other.top_node==top_node)
return true;
2348 template <
class T,
class tree_node_allocator>
2351 if(other.node!=this->node || other.top_node!=top_node)
return true;
2355 template <
class T,
class tree_node_allocator>
2358 assert(this->node!=0);
2360 if(this->node->next_sibling) {
2361 this->node=this->node->next_sibling;
2364 int relative_depth=0;
2367 if(this->node==this->top_node) {
2371 this->node=this->node->parent;
2372 if(this->node==0)
return *
this;
2374 }
while(this->node->next_sibling==0);
2376 this->node=this->node->next_sibling;
2377 while(this->node->first_child==0) {
2378 if(this->node->next_sibling==0)
2380 this->node=this->node->next_sibling;
2381 if(this->node==0)
return *
this;
2383 while(relative_depth<0 && this->node->first_child!=0) {
2384 this->node=this->node->first_child;
2387 if(relative_depth<0) {
2388 if(this->node->next_sibling==0)
goto upper;
2395 template <
class T,
class tree_node_allocator>
2398 assert(this->node!=0);
2400 if(this->node->prev_sibling) {
2401 this->node=this->node->prev_sibling;
2404 int relative_depth=0;
2407 if(this->node==this->top_node) {
2411 this->node=this->node->parent;
2412 if(this->node==0)
return *
this;
2414 }
while(this->node->prev_sibling==0);
2416 this->node=this->node->prev_sibling;
2417 while(this->node->last_child==0) {
2418 if(this->node->prev_sibling==0)
2420 this->node=this->node->prev_sibling;
2421 if(this->node==0)
return *
this;
2423 while(relative_depth<0 && this->node->last_child!=0) {
2424 this->node=this->node->last_child;
2427 if(relative_depth<0) {
2428 if(this->node->prev_sibling==0)
goto upper;
2457 template <
class T,
class tree_node_allocator>
2460 fixed_depth_iterator copy = *
this;
2465 template <
class T,
class tree_node_allocator>
2468 fixed_depth_iterator copy = *
this;
2473 template <
class T,
class tree_node_allocator>
2483 template <
class T,
class tree_node_allocator>
2496 template <
class T,
class tree_node_allocator>
2503 template <
class T,
class tree_node_allocator>
2510 template <
class T,
class tree_node_allocator>
2512 : iterator_base(other.node)
2517 template <
class T,
class tree_node_allocator>
2519 : iterator_base(other), parent_(other.parent_)
2523 template <
class T,
class tree_node_allocator>
2527 if(this->node==0)
return;
2528 if(this->node->parent!=0)
2529 parent_=this->node->
parent;
2532 template <
class T,
class tree_node_allocator>
2540 template <
class T,
class tree_node_allocator>
2543 if(this->node) this->node=this->node->prev_sibling;
2546 this->node=parent_->last_child;
2551 template <
class T,
class tree_node_allocator>
2554 sibling_iterator copy = *
this;
2559 template <
class T,
class tree_node_allocator>
2562 sibling_iterator copy = *
this;
2567 template <
class T,
class tree_node_allocator>
2577 template <
class T,
class tree_node_allocator>
2587 template <
class T,
class tree_node_allocator>
2590 tree_node *tmp=parent_->first_child;
2594 template <
class T,
class tree_node_allocator>
2597 return parent_->last_child;
2602 template <
class T,
class tree_node_allocator>
2604 : iterator_base(0), top_node(0)
2608 template <
class T,
class tree_node_allocator>
2610 : iterator_base(tn), top_node(top)
2614 template <
class T,
class tree_node_allocator>
2616 : iterator_base(other.node), top_node(0)
2620 template <
class T,
class tree_node_allocator>
2622 : iterator_base(other.node), top_node(0)
2625 if(other.range_last()!=0)
2626 this->node=other.range_last();
2628 this->node=other.parent_;
2633 template <
class T,
class tree_node_allocator>
2636 assert(this->node!=0);
2637 if(this->node->first_child!=0) {
2638 while(this->node->first_child)
2639 this->node=this->node->first_child;
2642 while(this->node->next_sibling==0) {
2643 if (this->node->parent==0)
return *
this;
2644 this->node=this->node->parent;
2645 if (top_node != 0 && this->node==top_node)
return *
this;
2647 this->node=this->node->next_sibling;
2648 while(this->node->first_child)
2649 this->node=this->node->first_child;
2654 template <
class T,
class tree_node_allocator>
2657 assert(this->node!=0);
2658 while (this->node->prev_sibling==0) {
2659 if (this->node->parent==0)
return *
this;
2660 this->node=this->node->parent;
2661 if (top_node !=0 && this->node==top_node)
return *
this;
2663 this->node=this->node->prev_sibling;
2664 while(this->node->last_child)
2665 this->node=this->node->last_child;
2669 template <
class T,
class tree_node_allocator>
2672 leaf_iterator copy = *
this;
2677 template <
class T,
class tree_node_allocator>
2680 leaf_iterator copy = *
this;
2686 template <
class T,
class tree_node_allocator>
2696 template <
class T,
class tree_node_allocator>
void clear()
Erase all nodes of the tree.
Definition: tree.h:556
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid...
Definition: tree.h:1102
Breadth-first iterator, using a queue.
Definition: tree.h:165
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.h:1737
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth end iterator.
Definition: tree.h:685
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.h:564
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition: tree.h:1249
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.h:637
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.h:586
int max_depth() const
Determine the maximal depth of the tree. An empty tree has max_depth=-1.
Definition: tree.h:1658
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.h:1994
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.h:984
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.h:1982
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.h:1221
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
Definition: tree.h:1697
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.h:1583
static int depth(const iterator_base &)
Compute the depth to the root or to a fixed other iterator.
Definition: tree.h:1632
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.h:1344
bool empty() const
Check if tree is empty.
Definition: tree.h:1625
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.h:207
leaf_iterator end_leaf() const
Return leaf end iterator for entire tree.
Definition: tree.h:732
sibling_iterator sibling(const iterator_base &position, unsigned int)
Return iterator to the sibling indicated by index.
Definition: tree.h:1844
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.h:619
static sibling_iterator child(const iterator_base &position, unsigned int)
Inverse of 'index': return the n-th child of the node at position.
Definition: tree.h:1867
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.h:1048
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.h:62
post_order_iterator end_post() const
Return post-order end iterator of the tree.
Definition: tree.h:648
breadth_first_queued_iterator begin_breadth_first() const
Return breadth-first iterator to the first node at a given depth.
Definition: tree.h:625
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.h:95
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.h:613
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.h:762
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.h:1072
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.h:772
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.h:1538
Iterator which traverses only the leaves.
Definition: tree.h:231
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.h:1805
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.h:2226
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.h:1818
leaf_iterator begin_leaf() const
Return leaf iterator to the first leaf of the tree.
Definition: tree.h:721
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.h:1446
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.h:144
T value_type
Value of the data stored at a node.
Definition: tree.h:76
unsigned int number_of_siblings(const iterator_base &) const
Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1...
Definition: tree.h:1713
iter append_child(iter position)
Insert empty node as last/first child of node pointed to by position.
Definition: tree.h:827
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.h:992
unsigned int index(sibling_iterator it) const
Determine the index of a node in the range of siblings to which it belongs.
Definition: tree.h:1825
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.h:1470
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.h:1304
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.h:186
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.h:654
static iter parent(iter)
Return iterator to the parent of a node.
Definition: tree.h:754
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.h:1411
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.h:1082
Depth-first iterator, first accessing the node, then its children.
Definition: tree.h:126
Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
Definition: tree.h:402
breadth_first_queued_iterator end_breadth_first() const
Return breadth-first end iterator.
Definition: tree.h:631
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.h:953
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.h:1315
pre_order_iterator iterator
The default iterator types throughout the tree class.
Definition: tree.h:182
size_t size() const
Count the total number of nodes.
Definition: tree.h:1599
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.h:782