40 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0)
46 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0),
data(val)
50 template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
59 class pre_order_iterator;
60 class post_order_iterator;
61 class sibling_iterator;
66 tree(
const iterator_base&);
73 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t> {
81 typedef size_t size_type;
82 typedef ptrdiff_t difference_type;
83 typedef std::bidirectional_iterator_tag iterator_category;
89 T* operator->()
const;
93 void skip_children(
bool skip);
95 unsigned int number_of_children()
const;
102 bool skip_current_children_;
158 std::queue<tree_node *> traversal_queue;
163 typedef breadth_first_queued_iterator breadth_first_iterator;
203 tree_node *range_first()
const;
204 tree_node *range_last()
const;
260 template<
typename iter>
static iter parent(iter);
262 template<
typename iter> iter previous_sibling(iter)
const;
264 template<
typename iter> iter next_sibling(iter)
const;
266 template<
typename iter> iter next_at_same_depth(iter)
const;
271 template<
typename iter> iter erase(iter);
276 template<
typename iter> iter append_child(iter position);
277 template<
typename iter> iter prepend_child(iter position);
279 template<
typename iter> iter append_child(iter position,
const T& x);
280 template<
typename iter> iter prepend_child(iter position,
const T& x);
282 template<
typename iter> iter append_child(iter position, iter other_position);
283 template<
typename iter> iter prepend_child(iter position, iter other_position);
291 template<
typename iter> iter insert(iter position,
const T& x);
295 template<
typename iter> iter insert_subtree(iter position,
const iterator_base& subtree);
297 template<
typename iter> iter insert_after(iter position,
const T& x);
299 template<
typename iter> iter insert_subtree_after(iter position,
const iterator_base& subtree);
302 template<
typename iter> iter replace(iter position,
const T& x);
304 template<
typename iter> iter replace(iter position,
const iterator_base& from);
310 template<
typename iter> iter flatten(iter position);
314 template<
typename iter> iter reparent(iter position, iter from);
317 template<
typename iter> iter wrap(iter position,
const T& x);
320 template<
typename iter> iter move_after(iter target, iter source);
322 template<
typename iter> iter move_before(iter target, iter source);
325 template<
typename iter> iter move_ontop(iter target, iter source);
329 bool duplicate_leaves=
false);
332 template<
class StrictWeakOrdering>
335 template<
typename iter>
336 bool equal(
const iter& one,
const iter& two,
const iter& three)
const;
337 template<
typename iter,
class BinaryPredicate>
338 bool equal(
const iter& one,
const iter& two,
const iter& three, BinaryPredicate)
const;
339 template<
typename iter>
340 bool equal_subtree(
const iter& one,
const iter& two)
const;
341 template<
typename iter,
class BinaryPredicate>
342 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
349 void swap(iterator, iterator);
361 int max_depth()
const;
365 static unsigned int number_of_children(
const iterator_base&);
386 void debug_verify_consistency()
const;
394 return one.node < two.node;
397 tree_node *head, *feet;
399 tree_node_allocator alloc_;
400 void head_initialise_();
404 template<
class StrictWeakOrdering>
405 class compare_nodes {
407 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
409 bool operator()(
const tree_node *a,
const tree_node *b)
411 return comp_(a->data, b->data);
414 StrictWeakOrdering comp_;
460 template <
class T,
class tree_node_allocator>
466 template <
class T,
class tree_node_allocator>
473 template <
class T,
class tree_node_allocator>
478 replace(begin(), other);
481 template <
class T,
class tree_node_allocator>
485 alloc_.destroy(head);
486 alloc_.destroy(feet);
487 alloc_.deallocate(head,1);
488 alloc_.deallocate(feet,1);
491 template <
class T,
class tree_node_allocator>
494 head = alloc_.allocate(1,0);
495 feet = alloc_.allocate(1,0);
502 head->prev_sibling=0;
503 head->next_sibling=feet;
508 feet->prev_sibling=head;
509 feet->next_sibling=0;
512 template <
class T,
class tree_node_allocator>
520 template <
class T,
class tree_node_allocator>
527 template <
class T,
class tree_node_allocator>
532 while(it!=other.
end()) {
533 to=insert(to, (*it));
539 while(it!=other.
end()) {
548 template <
class T,
class tree_node_allocator>
552 while(head->next_sibling!=feet)
556 template<
class T,
class tree_node_allocator>
560 if(it.node==0)
return;
562 tree_node *cur=it.node->first_child;
567 cur=cur->next_sibling;
570 alloc_.destroy(prev);
571 alloc_.deallocate(prev,1);
573 it.node->first_child=0;
574 it.node->last_child=0;
578 template<
class T,
class tree_node_allocator>
582 tree_node *cur=it.node;
588 if(cur->prev_sibling==0) {
589 cur->parent->first_child=cur->next_sibling;
592 cur->prev_sibling->next_sibling=cur->next_sibling;
594 if(cur->next_sibling==0) {
595 cur->parent->last_child=cur->prev_sibling;
598 cur->next_sibling->prev_sibling=cur->prev_sibling;
603 alloc_.deallocate(cur,1);
607 template <
class T,
class tree_node_allocator>
613 template <
class T,
class tree_node_allocator>
619 template <
class T,
class tree_node_allocator>
625 template <
class T,
class tree_node_allocator>
631 template <
class T,
class tree_node_allocator>
634 tree_node *tmp=head->next_sibling;
636 while(tmp->first_child)
637 tmp=tmp->first_child;
642 template <
class T,
class tree_node_allocator>
648 template <
class T,
class tree_node_allocator>
652 ret.top_node=pos.node;
654 tree_node *tmp=pos.node;
655 unsigned int curdepth=0;
657 while(tmp->first_child==0) {
658 if(tmp->next_sibling==0) {
661 if(tmp==ret.top_node)
662 throw std::range_error(
"tree: begin_fixed out of range");
665 throw std::range_error(
"tree: begin_fixed out of range");
667 }
while(tmp->next_sibling==0);
669 tmp=tmp->next_sibling;
671 tmp=tmp->first_child;
679 template <
class T,
class tree_node_allocator>
683 tree_node *tmp=pos.node;
684 unsigned int curdepth=1;
686 while(tmp->first_child==0) {
687 tmp=tmp->next_sibling;
689 throw std::range_error(
"tree: end_fixed out of range");
691 tmp=tmp->first_child;
697 template <
class T,
class tree_node_allocator>
701 if(pos.node->first_child==0) {
704 return pos.node->first_child;
707 template <
class T,
class tree_node_allocator>
711 ret.parent_=pos.node;
715 template <
class T,
class tree_node_allocator>
718 tree_node *tmp=head->next_sibling;
720 while(tmp->first_child)
721 tmp=tmp->first_child;
726 template <
class T,
class tree_node_allocator>
732 template <
class T,
class tree_node_allocator>
735 tree_node *tmp=top.node;
736 while(tmp->first_child)
737 tmp=tmp->first_child;
741 template <
class T,
class tree_node_allocator>
747 template <
class T,
class tree_node_allocator>
748 template <
typename iter>
751 assert(position.node!=0);
752 return iter(position.node->parent);
755 template <
class T,
class tree_node_allocator>
756 template <
typename iter>
759 assert(position.node!=0);
761 ret.node=position.node->prev_sibling;
765 template <
class T,
class tree_node_allocator>
766 template <
typename iter>
769 assert(position.node!=0);
771 ret.node=position.node->next_sibling;
775 template <
class T,
class tree_node_allocator>
776 template <
typename iter>
820 template <
class T,
class tree_node_allocator>
821 template <
typename iter>
824 assert(position.node!=head);
825 assert(position.node!=feet);
826 assert(position.node);
828 tree_node *tmp=alloc_.allocate(1,0);
834 tmp->parent=position.node;
835 if(position.node->last_child!=0) {
836 position.node->last_child->next_sibling=tmp;
839 position.node->first_child=tmp;
841 tmp->prev_sibling=position.node->last_child;
842 position.node->last_child=tmp;
847 template <
class T,
class tree_node_allocator>
848 template <
typename iter>
851 assert(position.node!=head);
852 assert(position.node!=feet);
853 assert(position.node);
855 tree_node *tmp=alloc_.allocate(1,0);
861 tmp->parent=position.node;
862 if(position.node->first_child!=0) {
863 position.node->first_child->prev_sibling=tmp;
866 position.node->last_child=tmp;
868 tmp->next_sibling=position.node->first_child;
869 position.node->prev_child=tmp;
874 template <
class T,
class tree_node_allocator>
875 template <
class iter>
882 assert(position.node!=head);
883 assert(position.node!=feet);
884 assert(position.node);
886 tree_node* tmp = alloc_.allocate(1,0);
887 alloc_.construct(tmp, x);
892 tmp->parent=position.node;
893 if(position.node->last_child!=0) {
894 position.node->last_child->next_sibling=tmp;
897 position.node->first_child=tmp;
899 tmp->prev_sibling=position.node->last_child;
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!=feet);
911 assert(position.node);
913 tree_node* tmp = alloc_.allocate(1,0);
914 alloc_.construct(tmp, x);
919 tmp->parent=position.node;
920 if(position.node->first_child!=0) {
921 position.node->first_child->prev_sibling=tmp;
924 position.node->last_child=tmp;
926 tmp->next_sibling=position.node->first_child;
927 position.node->first_child=tmp;
932 template <
class T,
class tree_node_allocator>
933 template <
class iter>
936 assert(position.node!=head);
937 assert(position.node!=feet);
938 assert(position.node);
941 return replace(aargh, other);
944 template <
class T,
class tree_node_allocator>
945 template <
class iter>
948 assert(position.node!=head);
949 assert(position.node!=feet);
950 assert(position.node);
953 return replace(aargh, other);
956 template <
class T,
class tree_node_allocator>
957 template <
class iter>
960 assert(position.node!=head);
961 assert(position.node!=feet);
962 assert(position.node);
967 insert_subtree(position.end(), from);
973 template <
class T,
class tree_node_allocator>
974 template <
class iter>
977 assert(position.node!=head);
978 assert(position.node!=feet);
979 assert(position.node);
984 insert_subtree(position.begin(), from);
990 template <
class T,
class tree_node_allocator>
993 assert(head->next_sibling==feet);
997 template <
class T,
class tree_node_allocator>
998 template <
class iter>
1001 if(position.node==0) {
1005 tree_node* tmp = alloc_.allocate(1,0);
1006 alloc_.construct(tmp, x);
1011 tmp->parent=position.node->parent;
1012 tmp->next_sibling=position.node;
1013 tmp->prev_sibling=position.node->prev_sibling;
1014 position.node->prev_sibling=tmp;
1016 if(tmp->prev_sibling==0) {
1018 tmp->parent->first_child=tmp;
1021 tmp->prev_sibling->next_sibling=tmp;
1025 template <
class T,
class tree_node_allocator>
1028 tree_node* tmp = alloc_.allocate(1,0);
1029 alloc_.construct(tmp, x);
1034 tmp->next_sibling=position.node;
1035 if(position.node==0) {
1036 tmp->parent=position.parent_;
1037 tmp->prev_sibling=position.range_last();
1038 tmp->parent->last_child=tmp;
1041 tmp->parent=position.node->parent;
1042 tmp->prev_sibling=position.node->prev_sibling;
1043 position.node->prev_sibling=tmp;
1046 if(tmp->prev_sibling==0) {
1048 tmp->parent->first_child=tmp;
1051 tmp->prev_sibling->next_sibling=tmp;
1055 template <
class T,
class tree_node_allocator>
1056 template <
class iter>
1059 tree_node* tmp = alloc_.allocate(1,0);
1060 alloc_.construct(tmp, x);
1065 tmp->parent=position.node->parent;
1066 tmp->prev_sibling=position.node;
1067 tmp->next_sibling=position.node->next_sibling;
1068 position.node->next_sibling=tmp;
1070 if(tmp->next_sibling==0) {
1072 tmp->parent->last_child=tmp;
1075 tmp->next_sibling->prev_sibling=tmp;
1080 template <
class T,
class tree_node_allocator>
1081 template <
class iter>
1085 iter it=insert(position, value_type());
1087 return replace(it, subtree);
1090 template <
class T,
class tree_node_allocator>
1091 template <
class iter>
1095 iter it=insert_after(position, value_type());
1097 return replace(it, subtree);
1110 template <
class T,
class tree_node_allocator>
1111 template <
class iter>
1116 position.node->data=x;
1122 template <
class T,
class tree_node_allocator>
1123 template <
class iter>
1126 assert(position.node!=head);
1127 tree_node *current_from=from.node;
1128 tree_node *start_from=from.node;
1129 tree_node *current_to =position.node;
1133 erase_children(position);
1135 tree_node* tmp = alloc_.allocate(1,0);
1136 alloc_.construct(tmp, (*from));
1140 if(current_to->prev_sibling==0) {
1141 if(current_to->parent!=0)
1142 current_to->parent->first_child=tmp;
1145 current_to->prev_sibling->next_sibling=tmp;
1147 tmp->prev_sibling=current_to->prev_sibling;
1148 if(current_to->next_sibling==0) {
1149 if(current_to->parent!=0)
1150 current_to->parent->last_child=tmp;
1153 current_to->next_sibling->prev_sibling=tmp;
1155 tmp->next_sibling=current_to->next_sibling;
1156 tmp->parent=current_to->parent;
1158 alloc_.destroy(current_to);
1159 alloc_.deallocate(current_to,1);
1163 tree_node *last=from.node->next_sibling;
1168 assert(current_from!=0);
1169 if(current_from->first_child != 0) {
1170 current_from=current_from->first_child;
1171 toit=append_child(toit, current_from->data);
1174 while(current_from->next_sibling==0 && current_from!=start_from) {
1175 current_from=current_from->parent;
1177 assert(current_from!=0);
1179 current_from=current_from->next_sibling;
1180 if(current_from!=last) {
1181 toit=append_child(parent(toit), current_from->data);
1184 }
while(current_from!=last);
1189 template <
class T,
class tree_node_allocator>
1196 tree_node *orig_first=orig_begin.node;
1197 tree_node *new_first=new_begin.node;
1198 tree_node *orig_last=orig_first;
1199 while((++orig_begin)!=orig_end)
1200 orig_last=orig_last->next_sibling;
1201 tree_node *new_last=new_first;
1202 while((++new_begin)!=new_end)
1203 new_last=new_last->next_sibling;
1214 if(new_first==new_last)
1216 new_first=new_first->next_sibling;
1221 tree_node *next=orig_first;
1225 next=next->next_sibling;
1234 template <
class T,
class tree_node_allocator>
1235 template <
typename iter>
1238 if(position.node->first_child==0)
1241 tree_node *tmp=position.node->first_child;
1243 tmp->parent=position.node->parent;
1244 tmp=tmp->next_sibling;
1246 if(position.node->next_sibling) {
1247 position.node->last_child->next_sibling=position.node->next_sibling;
1248 position.node->next_sibling->prev_sibling=position.node->last_child;
1251 position.node->parent->last_child=position.node->last_child;
1253 position.node->next_sibling=position.node->first_child;
1254 position.node->next_sibling->prev_sibling=position.node;
1255 position.node->first_child=0;
1256 position.node->last_child=0;
1262 template <
class T,
class tree_node_allocator>
1263 template <
typename iter>
1266 tree_node *first=begin.node;
1267 tree_node *last=first;
1269 assert(first!=position.node);
1271 if(begin==end)
return begin;
1273 while((++begin)!=end) {
1274 last=last->next_sibling;
1277 if(first->prev_sibling==0) {
1278 first->parent->first_child=last->next_sibling;
1281 first->prev_sibling->next_sibling=last->next_sibling;
1283 if(last->next_sibling==0) {
1284 last->parent->last_child=first->prev_sibling;
1287 last->next_sibling->prev_sibling=first->prev_sibling;
1289 if(position.node->first_child==0) {
1290 position.node->first_child=first;
1291 position.node->last_child=last;
1292 first->prev_sibling=0;
1295 position.node->last_child->next_sibling=first;
1296 first->prev_sibling=position.node->last_child;
1297 position.node->last_child=last;
1299 last->next_sibling=0;
1301 tree_node *pos=first;
1303 pos->parent=position.node;
1304 if(pos==last)
break;
1305 pos=pos->next_sibling;
1311 template <
class T,
class tree_node_allocator>
1314 if(from.node->first_child==0)
return position;
1315 return reparent(position, from.node->first_child, end(from));
1318 template <
class T,
class tree_node_allocator>
1321 assert(position.node!=0);
1324 iter ret = insert(position, x);
1325 reparent(ret, fr, to);
1329 template <
class T,
class tree_node_allocator>
1332 tree_node *dst=target.node;
1333 tree_node *src=source.node;
1337 if(dst==src)
return source;
1338 if(dst->next_sibling)
1339 if(dst->next_sibling==src)
1343 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1344 else src->parent->first_child=src->next_sibling;
1345 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1346 else src->parent->last_child=src->prev_sibling;
1349 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1350 else dst->parent->last_child=src;
1351 src->next_sibling=dst->next_sibling;
1352 dst->next_sibling=src;
1353 src->prev_sibling=dst;
1354 src->parent=dst->parent;
1358 template <
class T,
class tree_node_allocator>
1361 tree_node *dst=target.node;
1362 tree_node *src=source.node;
1366 if(dst==src)
return source;
1367 if(dst->prev_sibling)
1368 if(dst->prev_sibling==src)
1372 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1373 else src->parent->first_child=src->next_sibling;
1374 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1375 else src->parent->last_child=src->prev_sibling;
1378 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1379 else dst->parent->first_child=src;
1380 src->prev_sibling=dst->prev_sibling;
1381 dst->prev_sibling=src;
1382 src->next_sibling=dst;
1383 src->parent=dst->parent;
1388 template <
class T,
class tree_node_allocator>
1392 tree_node *dst=target.node;
1393 tree_node *src=source.node;
1394 tree_node *dst_prev_sibling;
1396 dst_prev_sibling=target.parent_->last_child;
1397 assert(dst_prev_sibling);
1399 else dst_prev_sibling=dst->prev_sibling;
1402 if(dst==src)
return source;
1403 if(dst_prev_sibling)
1404 if(dst_prev_sibling==src)
1408 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1409 else src->parent->first_child=src->next_sibling;
1410 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1411 else src->parent->last_child=src->prev_sibling;
1414 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1415 else target.parent_->first_child=src;
1416 src->prev_sibling=dst_prev_sibling;
1418 dst->prev_sibling=src;
1419 src->parent=dst->parent;
1421 src->next_sibling=dst;
1425 template <
class T,
class tree_node_allocator>
1428 tree_node *dst=target.node;
1429 tree_node *src=source.node;
1433 if(dst==src)
return source;
1440 tree_node *b_prev_sibling=dst->prev_sibling;
1441 tree_node *b_next_sibling=dst->next_sibling;
1442 tree_node *b_parent=dst->parent;
1448 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1449 else src->parent->first_child=src->next_sibling;
1450 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1451 else src->parent->last_child=src->prev_sibling;
1454 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1455 else b_parent->first_child=src;
1456 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1457 else b_parent->last_child=src;
1458 src->prev_sibling=b_prev_sibling;
1459 src->next_sibling=b_next_sibling;
1460 src->parent=b_parent;
1464 template <
class T,
class tree_node_allocator>
1467 bool duplicate_leaves)
1470 while(from1!=from2) {
1471 if((fnd=std::find(to1, to2, (*from1))) != to2) {
1472 if(from1.begin()==from1.end()) {
1473 if(duplicate_leaves)
1474 append_child(parent(to1), (*from1));
1477 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1481 insert_subtree(to2, from1);
1488 template <
class T,
class tree_node_allocator>
1492 sort(from, to, comp, deep);
1495 template <
class T,
class tree_node_allocator>
1496 template <
class StrictWeakOrdering>
1498 StrictWeakOrdering comp,
bool deep)
1500 if(from==to)
return;
1504 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1507 nodes.insert(it.node);
1514 tree_node *prev=from.node->prev_sibling;
1515 tree_node *next=it2.node->next_sibling;
1516 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >
::iterator nit=nodes.begin(), eit=nodes.end();
1518 if((*nit)->parent!=0)
1519 (*nit)->parent->first_child=(*nit);
1521 else prev->next_sibling=(*nit);
1525 (*nit)->prev_sibling=prev;
1527 prev->next_sibling=(*nit);
1533 prev->next_sibling=(*eit);
1536 (*eit)->next_sibling=next;
1537 (*eit)->prev_sibling=prev;
1539 if((*eit)->parent!=0)
1540 (*eit)->parent->last_child=(*eit);
1542 else next->prev_sibling=(*eit);
1549 sort(begin(bcs), end(bcs), comp, deep);
1555 template <
class T,
class tree_node_allocator>
1556 template <
typename iter>
1559 std::equal_to<T> comp;
1560 return equal(one_, two, three_, comp);
1563 template <
class T,
class tree_node_allocator>
1564 template <
typename iter>
1567 std::equal_to<T> comp;
1568 return equal_subtree(one_, two_, comp);
1571 template <
class T,
class tree_node_allocator>
1572 template <
typename iter,
class BinaryPredicate>
1579 while(one!=two && is_valid(three)) {
1580 if(!fun(*one,*three))
1590 template <
class T,
class tree_node_allocator>
1591 template <
typename iter,
class BinaryPredicate>
1596 if(!fun(*one,*two))
return false;
1597 if(number_of_children(one)!=number_of_children(two))
return false;
1598 return equal(begin(one),end(one),begin(two),fun);
1601 template <
class T,
class tree_node_allocator>
1610 template <
class T,
class tree_node_allocator>
1617 template <
class T,
class tree_node_allocator>
1629 template <
class T,
class tree_node_allocator>
1634 eit.skip_children();
1643 template <
class T,
class tree_node_allocator>
1650 template <
class T,
class tree_node_allocator>
1653 tree_node* pos=it.node;
1656 while(pos->parent!=0) {
1663 template <
class T,
class tree_node_allocator>
1666 tree_node* pos=it.node;
1669 while(pos->parent!=0 && pos!=root.node) {
1676 template <
class T,
class tree_node_allocator>
1680 for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
1681 maxd=std::max(maxd, max_depth(it));
1687 template <
class T,
class tree_node_allocator>
1690 tree_node *tmp=pos.node;
1692 if(tmp==0 || tmp==head || tmp==feet)
return -1;
1694 int curdepth=0, maxdepth=0;
1696 while(tmp->first_child==0) {
1697 if(tmp==pos.node)
return maxdepth;
1698 if(tmp->next_sibling==0) {
1702 if(tmp==0)
return maxdepth;
1704 }
while(tmp->next_sibling==0);
1706 if(tmp==pos.node)
return maxdepth;
1707 tmp=tmp->next_sibling;
1709 tmp=tmp->first_child;
1711 maxdepth=std::max(curdepth, maxdepth);
1715 template <
class T,
class tree_node_allocator>
1718 tree_node *pos=it.node->first_child;
1719 if(pos==0)
return 0;
1726 while((pos=pos->next_sibling))
1731 template <
class T,
class tree_node_allocator>
1734 tree_node *pos=it.node;
1737 while(pos->next_sibling &&
1738 pos->next_sibling!=head &&
1739 pos->next_sibling!=feet) {
1741 pos=pos->next_sibling;
1745 while(pos->prev_sibling &&
1746 pos->prev_sibling!=head &&
1747 pos->prev_sibling!=feet) {
1749 pos=pos->prev_sibling;
1755 template <
class T,
class tree_node_allocator>
1758 tree_node *nxt=it.node->next_sibling;
1760 if(it.node->prev_sibling)
1761 it.node->prev_sibling->next_sibling=nxt;
1763 it.node->parent->first_child=nxt;
1764 nxt->prev_sibling=it.node->prev_sibling;
1765 tree_node *nxtnxt=nxt->next_sibling;
1767 nxtnxt->prev_sibling=it.node;
1769 it.node->parent->last_child=it.node;
1770 nxt->next_sibling=it.node;
1771 it.node->prev_sibling=nxt;
1772 it.node->next_sibling=nxtnxt;
1776 template <
class T,
class tree_node_allocator>
1780 if(one.node->next_sibling==two.node) swap(one);
1781 else if(two.node->next_sibling==one.node) swap(two);
1783 tree_node *nxt1=one.node->next_sibling;
1784 tree_node *nxt2=two.node->next_sibling;
1785 tree_node *pre1=one.node->prev_sibling;
1786 tree_node *pre2=two.node->prev_sibling;
1787 tree_node *par1=one.node->parent;
1788 tree_node *par2=two.node->parent;
1791 one.node->parent=par2;
1792 one.node->next_sibling=nxt2;
1793 if(nxt2) nxt2->prev_sibling=one.node;
1794 else par2->last_child=one.node;
1795 one.node->prev_sibling=pre2;
1796 if(pre2) pre2->next_sibling=one.node;
1797 else par2->first_child=one.node;
1799 two.node->parent=par1;
1800 two.node->next_sibling=nxt1;
1801 if(nxt1) nxt1->prev_sibling=two.node;
1802 else par1->last_child=two.node;
1803 two.node->prev_sibling=pre1;
1804 if(pre1) pre1->next_sibling=two.node;
1805 else par1->first_child=two.node;
1823 template <
class T,
class tree_node_allocator>
1830 if(tmp==it)
return true;
1836 template <
class T,
class tree_node_allocator>
1839 if(it.node==0 || it.node==feet || it.node==head)
return false;
1843 template <
class T,
class tree_node_allocator>
1847 std::set<iterator, iterator_base_less> parents;
1853 parents.insert(walk);
1854 }
while( is_valid(parent(walk)) );
1860 if(parents.find(walk) != parents.end())
break;
1861 }
while( is_valid(parent(walk)) );
1866 template <
class T,
class tree_node_allocator>
1870 if(it.node->parent==0) {
1871 while(it.node->prev_sibling!=head) {
1872 it.node=it.node->prev_sibling;
1877 while(it.node->prev_sibling!=0) {
1878 it.node=it.node->prev_sibling;
1885 template <
class T,
class tree_node_allocator>
1889 if(it.node->parent==0) {
1890 tmp=head->next_sibling;
1892 tmp = tmp->next_sibling;
1897 tmp=it.node->parent->first_child;
1900 tmp = tmp->next_sibling;
1907 template <
class T,
class tree_node_allocator>
1912 if(it.node->parent!=0) {
1913 if(it.node->prev_sibling==0)
1914 assert(it.node->parent->first_child==it.node);
1916 assert(it.node->prev_sibling->next_sibling==it.node);
1917 if(it.node->next_sibling==0)
1918 assert(it.node->parent->last_child==it.node);
1920 assert(it.node->next_sibling->prev_sibling==it.node);
1926 template <
class T,
class tree_node_allocator>
1929 tree_node *tmp=it.node->first_child;
1932 tmp=tmp->next_sibling;
1942 template <
class T,
class tree_node_allocator>
1944 : node(0), skip_current_children_(
false)
1948 template <
class T,
class tree_node_allocator>
1950 : node(tn), skip_current_children_(
false)
1954 template <
class T,
class tree_node_allocator>
1960 template <
class T,
class tree_node_allocator>
1963 return &(node->data);
1966 template <
class T,
class tree_node_allocator>
1969 if(other.node!=this->node)
return true;
1973 template <
class T,
class tree_node_allocator>
1976 if(other.node==this->node)
return true;
1980 template <
class T,
class tree_node_allocator>
1983 if(other.node!=this->node)
return true;
1987 template <
class T,
class tree_node_allocator>
1990 if(other.node==this->node)
return true;
1994 template <
class T,
class tree_node_allocator>
1997 if(other.node!=this->node)
return true;
2001 template <
class T,
class tree_node_allocator>
2004 if(other.node==this->node)
return true;
2008 template <
class T,
class tree_node_allocator>
2011 if(other.node!=this->node)
return true;
2015 template <
class T,
class tree_node_allocator>
2018 if(other.node==this->node && other.top_node==this->top_node)
return true;
2022 template <
class T,
class tree_node_allocator>
2025 if(node->first_child==0)
2029 ret.parent_=this->node;
2033 template <
class T,
class tree_node_allocator>
2041 template <
class T,
class tree_node_allocator>
2044 skip_current_children_=
true;
2047 template <
class T,
class tree_node_allocator>
2050 skip_current_children_=skip;
2053 template <
class T,
class tree_node_allocator>
2056 tree_node *pos=node->first_child;
2057 if(pos==0)
return 0;
2060 while(pos!=node->last_child) {
2062 pos=pos->next_sibling;
2071 template <
class T,
class tree_node_allocator>
2077 template <
class T,
class tree_node_allocator>
2083 template <
class T,
class tree_node_allocator>
2089 template <
class T,
class tree_node_allocator>
2094 if(other.range_last()!=0)
2095 this->node=other.range_last();
2097 this->node=other.parent_;
2098 this->skip_children();
2103 template <
class T,
class tree_node_allocator>
2106 assert(this->node!=0);
2107 if(!this->skip_current_children_ && this->node->first_child != 0) {
2108 this->node=this->node->first_child;
2111 this->skip_current_children_=
false;
2112 while(this->node->next_sibling==0) {
2113 this->node=this->node->parent;
2117 this->node=this->node->next_sibling;
2122 template <
class T,
class tree_node_allocator>
2125 assert(this->node!=0);
2126 if(this->node->prev_sibling) {
2127 this->node=this->node->prev_sibling;
2128 while(this->node->last_child)
2129 this->node=this->node->last_child;
2132 this->node=this->node->parent;
2139 template <
class T,
class tree_node_allocator>
2147 template <
class T,
class tree_node_allocator>
2155 template <
class T,
class tree_node_allocator>
2165 template <
class T,
class tree_node_allocator>
2179 template <
class T,
class tree_node_allocator>
2185 template <
class T,
class tree_node_allocator>
2191 template <
class T,
class tree_node_allocator>
2197 template <
class T,
class tree_node_allocator>
2202 if(other.range_last()!=0)
2203 this->node=other.range_last();
2205 this->node=other.parent_;
2206 this->skip_children();
2211 template <
class T,
class tree_node_allocator>
2214 assert(this->node!=0);
2215 if(this->node->next_sibling==0) {
2216 this->node=this->node->parent;
2217 this->skip_current_children_=
false;
2220 this->node=this->node->next_sibling;
2221 if(this->skip_current_children_) {
2222 this->skip_current_children_=
false;
2225 while(this->node->first_child)
2226 this->node=this->node->first_child;
2232 template <
class T,
class tree_node_allocator>
2235 assert(this->node!=0);
2236 if(this->skip_current_children_ || this->node->last_child==0) {
2237 this->skip_current_children_=
false;
2238 while(this->node->prev_sibling==0)
2239 this->node=this->node->parent;
2240 this->node=this->node->prev_sibling;
2243 this->node=this->node->last_child;
2248 template <
class T,
class tree_node_allocator>
2256 template <
class T,
class tree_node_allocator>
2265 template <
class T,
class tree_node_allocator>
2275 template <
class T,
class tree_node_allocator>
2285 template <
class T,
class tree_node_allocator>
2288 assert(this->node!=0);
2289 while(this->node->first_child)
2290 this->node=this->node->first_child;
2296 template <
class T,
class tree_node_allocator>
2302 template <
class T,
class tree_node_allocator>
2306 traversal_queue.push(tn);
2309 template <
class T,
class tree_node_allocator>
2313 traversal_queue.push(other.node);
2316 template <
class T,
class tree_node_allocator>
2319 if(other.node!=this->node)
return true;
2323 template <
class T,
class tree_node_allocator>
2326 if(other.node==this->node)
return true;
2330 template <
class T,
class tree_node_allocator>
2333 assert(this->node!=0);
2337 while(sib!=this->end()) {
2338 traversal_queue.push(sib.node);
2341 traversal_queue.pop();
2342 if(traversal_queue.size()>0)
2343 this->node=traversal_queue.front();
2349 template <
class T,
class tree_node_allocator>
2357 template <
class T,
class tree_node_allocator>
2371 template <
class T,
class tree_node_allocator>
2377 template <
class T,
class tree_node_allocator>
2383 template <
class T,
class tree_node_allocator>
2389 template <
class T,
class tree_node_allocator>
2395 template <
class T,
class tree_node_allocator>
2401 template <
class T,
class tree_node_allocator>
2404 if(other.node==this->node && other.top_node==top_node)
return true;
2408 template <
class T,
class tree_node_allocator>
2411 if(other.node!=this->node || other.top_node!=top_node)
return true;
2415 template <
class T,
class tree_node_allocator>
2418 assert(this->node!=0);
2420 if(this->node->next_sibling) {
2421 this->node=this->node->next_sibling;
2424 int relative_depth=0;
2427 if(this->node==this->top_node) {
2431 this->node=this->node->parent;
2432 if(this->node==0)
return *
this;
2434 }
while(this->node->next_sibling==0);
2436 this->node=this->node->next_sibling;
2437 while(this->node->first_child==0) {
2438 if(this->node->next_sibling==0)
2440 this->node=this->node->next_sibling;
2441 if(this->node==0)
return *
this;
2443 while(relative_depth<0 && this->node->first_child!=0) {
2444 this->node=this->node->first_child;
2447 if(relative_depth<0) {
2448 if(this->node->next_sibling==0)
goto upper;
2455 template <
class T,
class tree_node_allocator>
2458 assert(this->node!=0);
2460 if(this->node->prev_sibling) {
2461 this->node=this->node->prev_sibling;
2464 int relative_depth=0;
2467 if(this->node==this->top_node) {
2471 this->node=this->node->parent;
2472 if(this->node==0)
return *
this;
2474 }
while(this->node->prev_sibling==0);
2476 this->node=this->node->prev_sibling;
2477 while(this->node->last_child==0) {
2478 if(this->node->prev_sibling==0)
2480 this->node=this->node->prev_sibling;
2481 if(this->node==0)
return *
this;
2483 while(relative_depth<0 && this->node->last_child!=0) {
2484 this->node=this->node->last_child;
2487 if(relative_depth<0) {
2488 if(this->node->prev_sibling==0)
goto upper;
2517 template <
class T,
class tree_node_allocator>
2525 template <
class T,
class tree_node_allocator>
2533 template <
class T,
class tree_node_allocator>
2543 template <
class T,
class tree_node_allocator>
2556 template <
class T,
class tree_node_allocator>
2563 template <
class T,
class tree_node_allocator>
2570 template <
class T,
class tree_node_allocator>
2577 template <
class T,
class tree_node_allocator>
2583 template <
class T,
class tree_node_allocator>
2587 if(this->node==0)
return;
2588 if(this->node->parent!=0)
2589 parent_=this->node->
parent;
2592 template <
class T,
class tree_node_allocator>
2600 template <
class T,
class tree_node_allocator>
2603 if(this->node) this->node=this->node->prev_sibling;
2606 this->node=parent_->last_child;
2611 template <
class T,
class tree_node_allocator>
2619 template <
class T,
class tree_node_allocator>
2627 template <
class T,
class tree_node_allocator>
2637 template <
class T,
class tree_node_allocator>
2647 template <
class T,
class tree_node_allocator>
2650 tree_node *tmp=parent_->first_child;
2654 template <
class T,
class tree_node_allocator>
2657 return parent_->last_child;
2662 template <
class T,
class tree_node_allocator>
2668 template <
class T,
class tree_node_allocator>
2674 template <
class T,
class tree_node_allocator>
2680 template <
class T,
class tree_node_allocator>
2685 if(other.range_last()!=0)
2686 this->node=other.range_last();
2688 this->node=other.parent_;
2693 template <
class T,
class tree_node_allocator>
2696 assert(this->node!=0);
2697 if(this->node->first_child!=0) {
2698 while(this->node->first_child)
2699 this->node=this->node->first_child;
2702 while(this->node->next_sibling==0) {
2703 if (this->node->parent==0)
return *
this;
2704 this->node=this->node->parent;
2705 if (top_node != 0 && this->node==top_node)
return *
this;
2707 this->node=this->node->next_sibling;
2708 while(this->node->first_child)
2709 this->node=this->node->first_child;
2714 template <
class T,
class tree_node_allocator>
2717 assert(this->node!=0);
2718 while (this->node->prev_sibling==0) {
2719 if (this->node->parent==0)
return *
this;
2720 this->node=this->node->parent;
2721 if (top_node !=0 && this->node==top_node)
return *
this;
2723 this->node=this->node->prev_sibling;
2724 while(this->node->last_child)
2725 this->node=this->node->last_child;
2729 template <
class T,
class tree_node_allocator>
2737 template <
class T,
class tree_node_allocator>
2746 template <
class T,
class tree_node_allocator>
2756 template <
class T,
class tree_node_allocator>
void clear()
Erase all nodes of the tree.
Definition: tree.hh:549
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid...
Definition: tree.hh:1112
Breadth-first iterator, using a queue.
Definition: tree.hh:145
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.hh:1756
fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const
Return fixed-depth end iterator.
Definition: tree.hh:680
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.hh:557
iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
Move nodes in range to be children of 'position'.
Definition: tree.hh:1264
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.hh:632
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.hh:580
int max_depth() const
Determine the maximal depth of the tree. An empty tree has max_depth=-1.
Definition: tree.hh:1677
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.hh:2054
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.hh:991
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.hh:2042
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.hh:1236
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
Definition: tree.hh:1716
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:1602
static int depth(const iterator_base &)
Compute the depth to the root or to a fixed other iterator.
Definition: tree.hh:1651
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.hh:1359
bool empty() const
Check if tree is empty.
Definition: tree.hh:1644
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.hh:187
leaf_iterator end_leaf() const
Return leaf end iterator for entire tree.
Definition: tree.hh:727
sibling_iterator sibling(const iterator_base &position, unsigned int)
Return iterator to the sibling indicated by index.
Definition: tree.hh:1886
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.hh:614
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.hh:1927
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.hh:1057
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.hh:27
post_order_iterator end_post() const
Return post-order end iterator of the tree.
Definition: tree.hh:643
breadth_first_queued_iterator begin_breadth_first() const
Return breadth-first iterator to the first node at a given depth.
Definition: tree.hh:620
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.hh:75
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.hh:608
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.hh:757
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:1082
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.hh:767
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:1557
Iterator which traverses only the leaves.
Definition: tree.hh:211
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:1824
void debug_verify_consistency() const
Definition: tree.hh:1908
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.hh:2286
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:1837
leaf_iterator begin_leaf() const
Return leaf iterator to the first leaf of the tree.
Definition: tree.hh:716
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:1465
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.hh:124
T value_type
Value of the data stored at a node.
Definition: tree.hh:56
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.hh:1732
iter append_child(iter position)
Insert empty node as last/first child of node pointed to by position.
Definition: tree.hh:822
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.hh:999
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:1867
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:1489
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:1319
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.hh:166
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:649
static iter parent(iter)
Return iterator to the parent of a node.
Definition: tree.hh:749
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:1426
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:1092
Depth-first iterator, first accessing the node, then its children.
Definition: tree.hh:106
Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
Definition: tree.hh:389
breadth_first_queued_iterator end_breadth_first() const
Return breadth-first end iterator.
Definition: tree.hh:626
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:958
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.hh:1330
pre_order_iterator iterator
The default iterator types throughout the tree class.
Definition: tree.hh:162
size_t size() const
Count the total number of nodes.
Definition: tree.hh:1618
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.hh:777
iterator lowest_common_ancestor(const iterator_base &, const iterator_base &) const
Definition: tree.hh:1844
Definition: BackgroundRecLigth.h:20