76template <
class T1,
class T2>
79 new ((
void *) p) T1(val);
106template <
class T,
class tree_node_allocator = std::allocator<tree_node_<T> > >
129 class iterator_base :
public stlport::bidirectional_iterator<T, ptrdiff_t> {
153 sibling_iterator
end()
const;
163 pre_order_iterator();
166 pre_order_iterator(
const sibling_iterator&);
168 bool operator==(
const pre_order_iterator&)
const;
169 bool operator!=(
const pre_order_iterator&)
const;
170 pre_order_iterator& operator++();
171 pre_order_iterator& operator--();
172 pre_order_iterator operator++(
int);
173 pre_order_iterator operator--(
int);
174 pre_order_iterator& operator+=(
unsigned int);
175 pre_order_iterator& operator-=(
unsigned int);
181 post_order_iterator();
184 post_order_iterator(
const sibling_iterator&);
186 bool operator==(
const post_order_iterator&)
const;
187 bool operator!=(
const post_order_iterator&)
const;
188 post_order_iterator& operator++();
189 post_order_iterator& operator--();
190 post_order_iterator operator++(
int);
191 post_order_iterator operator--(
int);
192 post_order_iterator& operator+=(
unsigned int);
193 post_order_iterator& operator-=(
unsigned int);
202 breadth_first_queued_iterator();
206 bool operator==(
const breadth_first_queued_iterator&)
const;
207 bool operator!=(
const breadth_first_queued_iterator&)
const;
208 breadth_first_queued_iterator& operator++();
209 breadth_first_queued_iterator operator++(
int);
210 breadth_first_queued_iterator& operator+=(
unsigned int);
223 fixed_depth_iterator();
226 fixed_depth_iterator(
const sibling_iterator&);
227 fixed_depth_iterator(
const fixed_depth_iterator&);
229 bool operator==(
const fixed_depth_iterator&)
const;
230 bool operator!=(
const fixed_depth_iterator&)
const;
231 fixed_depth_iterator& operator++();
232 fixed_depth_iterator& operator--();
233 fixed_depth_iterator operator++(
int);
234 fixed_depth_iterator operator--(
int);
235 fixed_depth_iterator& operator+=(
unsigned int);
236 fixed_depth_iterator& operator-=(
unsigned int);
240 void set_first_parent_();
241 void find_leftmost_parent_();
249 sibling_iterator(
const sibling_iterator&);
252 bool operator==(
const sibling_iterator&)
const;
253 bool operator!=(
const sibling_iterator&)
const;
254 sibling_iterator& operator++();
255 sibling_iterator& operator--();
256 sibling_iterator operator++(
int);
257 sibling_iterator operator--(
int);
258 sibling_iterator& operator+=(
unsigned int);
259 sibling_iterator& operator-=(
unsigned int);
273 leaf_iterator(
const sibling_iterator&);
276 bool operator==(
const leaf_iterator&)
const;
277 bool operator!=(
const leaf_iterator&)
const;
278 leaf_iterator& operator++();
279 leaf_iterator& operator--();
280 leaf_iterator operator++(
int);
281 leaf_iterator operator--(
int);
282 leaf_iterator& operator+=(
unsigned int);
283 leaf_iterator& operator-=(
unsigned int);
287 inline pre_order_iterator
begin()
const;
289 inline pre_order_iterator
end()
const;
312 template<
typename iter>
static iter
parent(iter);
323 template<
typename iter> iter
erase(iter);
334 template<
typename iter> iter
append_child(iter position, iter other_position);
335 template<
typename iter> iter
prepend_child(iter position, iter other_position);
337 template<
typename iter> iter
append_children(iter position, sibling_iterator from, sibling_iterator to);
338 template<
typename iter> iter
prepend_children(iter position, sibling_iterator from, sibling_iterator to);
343 template<
typename iter> iter
insert(iter position,
const T& x);
345 sibling_iterator
insert(sibling_iterator position,
const T& x);
354 template<
typename iter> iter
replace(iter position,
const T& x);
358 sibling_iterator
replace(sibling_iterator orig_begin, sibling_iterator orig_end,
359 sibling_iterator new_begin, sibling_iterator new_end);
362 template<
typename iter> iter
flatten(iter position);
364 template<
typename iter> iter
reparent(iter position, sibling_iterator
begin, sibling_iterator
end);
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);
375 sibling_iterator
move_before(sibling_iterator target, sibling_iterator source);
377 template<
typename iter> iter
move_ontop(iter target, iter source);
380 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
381 bool duplicate_leaves=
false);
383 void sort(sibling_iterator from, sibling_iterator to,
bool deep=
false);
384 template<
class StrictWeakOrdering>
385 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp,
bool deep=
false);
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>
393 template<
typename iter,
class BinaryPredicate>
394 bool equal_subtree(
const iter& one,
const iter& two, BinaryPredicate)
const;
397 void subtree(
tree&, sibling_iterator from, sibling_iterator to)
const;
399 void swap(sibling_iterator it);
426 unsigned int index(sibling_iterator it)
const;
446 template<
class StrictWeakOrdering>
453 static StrictWeakOrdering comp;
503template <
class T,
class tree_node_allocator>
509template <
class T,
class tree_node_allocator>
516template <
class T,
class tree_node_allocator>
524template <
class T,
class tree_node_allocator>
532template <
class T,
class tree_node_allocator>
551template <
class T,
class tree_node_allocator>
557template <
class T,
class tree_node_allocator>
564template <
class T,
class tree_node_allocator>
569 while(it!=other.
end()) {
576 while(it!=other.
end()) {
585template <
class T,
class tree_node_allocator>
593template<
class T,
class tree_node_allocator>
597 if(it.node==0)
return;
607 alloc_.deallocate(prev,1);
609 it.node->first_child=0;
610 it.node->last_child=0;
614template<
class T,
class tree_node_allocator>
642template <
class T,
class tree_node_allocator>
648template <
class T,
class tree_node_allocator>
654template <
class T,
class tree_node_allocator>
660template <
class T,
class tree_node_allocator>
666template <
class T,
class tree_node_allocator>
677template <
class T,
class tree_node_allocator>
683template <
class T,
class tree_node_allocator>
687 unsigned int curdepth=0;
695 throw std::range_error(
"tree: begin_fixed out of range");
707template <
class T,
class tree_node_allocator>
712 unsigned int curdepth=1;
717 throw std::range_error(
"tree: end_fixed out of range");
725template <
class T,
class tree_node_allocator>
729 if(pos.node->first_child==0) {
732 return pos.node->first_child;
735template <
class T,
class tree_node_allocator>
743template <
class T,
class tree_node_allocator>
754template <
class T,
class tree_node_allocator>
760template <
class T,
class tree_node_allocator>
761template <
typename iter>
764 assert(position.node!=0);
765 return iter(position.node->parent);
768template <
class T,
class tree_node_allocator>
769template <
typename iter>
772 assert(position.node!=0);
774 ret.node=position.node->prev_sibling;
778template <
class T,
class tree_node_allocator>
779template <
typename iter>
782 assert(position.node!=0);
784 ret.node=position.node->next_sibling;
788template <
class T,
class tree_node_allocator>
789template <
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;
826template <
class T,
class tree_node_allocator>
827template <
typename iter>
830 assert(position.node!=
head);
831 assert(position.node);
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;
851template <
class T,
class tree_node_allocator>
852template <
typename iter>
855 assert(position.node!=
head);
856 assert(position.node);
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;
876template <
class T,
class tree_node_allocator>
884 assert(position.node!=
head);
885 assert(position.node);
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;
905template <
class T,
class tree_node_allocator>
909 assert(position.node!=
head);
910 assert(position.node);
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;
930template <
class T,
class tree_node_allocator>
934 assert(position.node!=
head);
935 assert(position.node);
941template <
class T,
class tree_node_allocator>
945 assert(position.node!=
head);
946 assert(position.node);
952template <
class T,
class tree_node_allocator>
956 assert(position.node!=
head);
957 assert(position.node);
968template <
class T,
class tree_node_allocator>
972 assert(position.node!=
head);
973 assert(position.node);
984template <
class T,
class tree_node_allocator>
991template <
class T,
class tree_node_allocator>
995 if(position.node==0) {
1004 tmp->
parent=position.node->parent;
1007 position.node->prev_sibling=tmp;
1011 tmp->
parent->first_child=tmp;
1018template <
class T,
class tree_node_allocator>
1027 if(position.
node==0) {
1030 tmp->
parent->last_child=tmp;
1040 tmp->
parent->first_child=tmp;
1047template <
class T,
class tree_node_allocator>
1048template <
class iter>
1056 tmp->
parent=position.node->parent;
1059 position.node->next_sibling=tmp;
1063 tmp->
parent->last_child=tmp;
1071template <
class T,
class tree_node_allocator>
1072template <
class iter>
1081template <
class T,
class tree_node_allocator>
1082template <
class iter>
1101template <
class T,
class tree_node_allocator>
1102template <
class iter>
1110template <
class T,
class tree_node_allocator>
1111template <
class iter>
1114 assert(position.node!=
head);
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);
1154 assert(current_from!=0);
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) {
1170 }
while(current_from!=last);
1175template <
class T,
class tree_node_allocator>
1185 while((++orig_begin)!=orig_end)
1188 while((++new_begin)!=new_end)
1200 if(new_first==new_last)
1220template <
class T,
class tree_node_allocator>
1221template <
typename iter>
1224 if(position.node->first_child==0)
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;
1248template <
class T,
class tree_node_allocator>
1249template <
typename iter>
1255 assert(first!=position.node);
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;
1289 pos->
parent=position.node;
1290 if(pos==last)
break;
1297template <
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));
1304template <
class T,
class tree_node_allocator>
1307 assert(position.node!=0);
1310 iter ret =
insert(position, x);
1315template <
class T,
class tree_node_allocator>
1323 if(dst==src)
return source;
1336 else dst->
parent->last_child=src;
1344template <
class T,
class tree_node_allocator>
1352 if(dst==src)
return source;
1365 else dst->
parent->first_child=src;
1374template <
class T,
class tree_node_allocator>
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;
1411template <
class T,
class tree_node_allocator>
1419 if(dst==src)
return source;
1436 if(b_prev_sibling!=0) b_prev_sibling->
next_sibling=src;
1438 if(b_next_sibling!=0) b_next_sibling->
prev_sibling=src;
1446template <
class T,
class tree_node_allocator>
1449 bool duplicate_leaves)
1452 while(from1!=from2) {
1453 if((fnd=std::find(to1, to2, (*from1))) != to2) {
1455 if(duplicate_leaves)
1470template <
class T,
class tree_node_allocator>
1474 sort(from, to, comp, deep);
1477template <
class T,
class tree_node_allocator>
1478template <
class StrictWeakOrdering>
1480 StrictWeakOrdering comp,
bool deep)
1482 if(from==to)
return;
1486 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1489 nodes.insert(it.
node);
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);
1537template <
class T,
class tree_node_allocator>
1538template <
typename iter>
1541 std::equal_to<T> comp;
1542 return equal(one_, two, three_, comp);
1545template <
class T,
class tree_node_allocator>
1546template <
typename iter>
1549 std::equal_to<T> comp;
1553template <
class T,
class tree_node_allocator>
1554template <
typename iter,
class BinaryPredicate>
1561 while(one!=two &&
is_valid(three)) {
1562 if(!fun(*one,*three))
1572template <
class T,
class tree_node_allocator>
1573template <
typename iter,
class BinaryPredicate>
1578 if(!fun(*one,*two))
return false;
1583template <
class T,
class tree_node_allocator>
1592template <
class T,
class tree_node_allocator>
1599template <
class T,
class tree_node_allocator>
1611template <
class T,
class tree_node_allocator>
1625template <
class T,
class tree_node_allocator>
1632template <
class T,
class tree_node_allocator>
1645template <
class T,
class tree_node_allocator>
1652template <
class T,
class tree_node_allocator>
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);
1677template <
class T,
class tree_node_allocator>
1681 if(pos==0)
return 0;
1693template <
class T,
class tree_node_allocator>
1717template <
class T,
class tree_node_allocator>
1738template <
class T,
class tree_node_allocator>
1785template <
class T,
class tree_node_allocator>
1792 if(tmp==it)
return true;
1798template <
class T,
class tree_node_allocator>
1801 if(it.node==0 || it.node==
feet || it.node==
head)
return false;
1805template <
class T,
class tree_node_allocator>
1825template <
class T,
class tree_node_allocator>
1841template <
class T,
class tree_node_allocator>
1843 : node(0), skip_current_children_(false)
1847template <
class T,
class tree_node_allocator>
1849 : node(tn), skip_current_children_(false)
1853template <
class T,
class tree_node_allocator>
1859template <
class T,
class tree_node_allocator>
1862 return &(node->data);
1865template <
class T,
class tree_node_allocator>
1868 if(other.
node!=this->node)
return true;
1872template <
class T,
class tree_node_allocator>
1875 if(other.
node==this->node)
return true;
1879template <
class T,
class tree_node_allocator>
1882 if(other.
node!=this->node)
return true;
1886template <
class T,
class tree_node_allocator>
1889 if(other.
node==this->node)
return true;
1893template <
class T,
class tree_node_allocator>
1896 if(other.
node!=this->node)
return true;
1900template <
class T,
class tree_node_allocator>
1903 if(other.
node==this->node)
return true;
1907template <
class T,
class tree_node_allocator>
1910 if(other.
node!=this->node)
return true;
1914template <
class T,
class tree_node_allocator>
1917 if(other.
node==this->node)
return true;
1921template <
class T,
class tree_node_allocator>
1924 if(node->first_child==0)
1932template <
class T,
class tree_node_allocator>
1940template <
class T,
class tree_node_allocator>
1943 skip_current_children_=
true;
1946template <
class T,
class tree_node_allocator>
1950 if(pos==0)
return 0;
1964template <
class T,
class tree_node_allocator>
1970template <
class T,
class tree_node_allocator>
1976template <
class T,
class tree_node_allocator>
1982template <
class T,
class tree_node_allocator>
1996template <
class T,
class tree_node_allocator>
1999 assert(this->node!=0);
2000 if(!this->skip_current_children_ && this->node->first_child != 0) {
2001 this->node=this->node->first_child;
2004 this->skip_current_children_=
false;
2005 while(this->node->next_sibling==0) {
2006 this->node=this->node->parent;
2010 this->node=this->node->next_sibling;
2015template <
class T,
class tree_node_allocator>
2018 assert(this->node!=0);
2019 if(this->node->prev_sibling) {
2020 this->node=this->node->prev_sibling;
2021 while(this->node->last_child)
2022 this->node=this->node->last_child;
2025 this->node=this->node->parent;
2032template <
class T,
class tree_node_allocator>
2040template <
class T,
class tree_node_allocator>
2048template <
class T,
class tree_node_allocator>
2058template <
class T,
class tree_node_allocator>
2072template <
class T,
class tree_node_allocator>
2078template <
class T,
class tree_node_allocator>
2084template <
class T,
class tree_node_allocator>
2090template <
class T,
class tree_node_allocator>
2104template <
class T,
class tree_node_allocator>
2107 assert(this->node!=0);
2108 if(this->node->next_sibling==0) {
2109 this->node=this->node->parent;
2110 this->skip_current_children_=
false;
2113 this->node=this->node->next_sibling;
2114 if(this->skip_current_children_) {
2115 this->skip_current_children_=
false;
2118 while(this->node->first_child)
2119 this->node=this->node->first_child;
2125template <
class T,
class tree_node_allocator>
2128 assert(this->node!=0);
2129 if(this->skip_current_children_ || this->node->last_child==0) {
2130 this->skip_current_children_=
false;
2131 while(this->node->prev_sibling==0)
2132 this->node=this->node->parent;
2133 this->node=this->node->prev_sibling;
2136 this->node=this->node->last_child;
2141template <
class T,
class tree_node_allocator>
2149template <
class T,
class tree_node_allocator>
2158template <
class T,
class tree_node_allocator>
2168template <
class T,
class tree_node_allocator>
2178template <
class T,
class tree_node_allocator>
2181 assert(this->node!=0);
2182 while(this->node->first_child)
2183 this->node=this->node->first_child;
2189template <
class T,
class tree_node_allocator>
2195template <
class T,
class tree_node_allocator>
2202template <
class T,
class tree_node_allocator>
2209template <
class T,
class tree_node_allocator>
2212 if(other.
node!=this->node)
return true;
2216template <
class T,
class tree_node_allocator>
2219 if(other.
node==this->node)
return true;
2223template <
class T,
class tree_node_allocator>
2226 assert(this->node!=0);
2230 while(sib!=this->
end()) {
2231 traversal_queue.push(sib.
node);
2234 traversal_queue.pop();
2235 if(traversal_queue.size()>0)
2236 this->node=traversal_queue.front();
2242template <
class T,
class tree_node_allocator>
2250template <
class T,
class tree_node_allocator>
2264template <
class T,
class tree_node_allocator>
2271template <
class T,
class tree_node_allocator>
2278template <
class T,
class tree_node_allocator>
2285template <
class T,
class tree_node_allocator>
2292template <
class T,
class tree_node_allocator>
2294 :
iterator_base(other.node), first_parent_(other.first_parent_)
2298template <
class T,
class tree_node_allocator>
2305template <
class T,
class tree_node_allocator>
2312template <
class T,
class tree_node_allocator>
2318 if(this->node==0)
return;
2319 if(this->node->parent!=0)
2320 first_parent_=this->node->parent;
2322 find_leftmost_parent_();
2325template <
class T,
class tree_node_allocator>
2333 first_parent_=tmppar;
2337template <
class T,
class tree_node_allocator>
2340 assert(this->node!=0);
2342 if(this->node->next_sibling) {
2343 this->node=this->node->next_sibling;
2346 int relative_depth=0;
2349 this->node=this->node->parent;
2350 if(this->node==0)
return *
this;
2352 }
while(this->node->next_sibling==0);
2354 this->node=this->node->next_sibling;
2355 while(this->node->first_child==0) {
2356 if(this->node->next_sibling==0)
2358 this->node=this->node->next_sibling;
2359 if(this->node==0)
return *
this;
2361 while(relative_depth<0 && this->node->first_child!=0) {
2362 this->node=this->node->first_child;
2365 if(relative_depth<0) {
2366 if(this->node->next_sibling==0)
goto upper;
2392template <
class T,
class tree_node_allocator>
2395 assert(this->node!=0);
2396 if(this->node->prev_sibling!=0) {
2397 this->node=this->node->prev_sibling;
2398 assert(this->node!=0);
2399 if(this->node->parent==0 && this->node->prev_sibling==0)
2416template <
class T,
class tree_node_allocator>
2424template <
class T,
class tree_node_allocator>
2432template <
class T,
class tree_node_allocator>
2442template <
class T,
class tree_node_allocator>
2457template <
class T,
class tree_node_allocator>
2464template <
class T,
class tree_node_allocator>
2471template <
class T,
class tree_node_allocator>
2478template <
class T,
class tree_node_allocator>
2484template <
class T,
class tree_node_allocator>
2488 if(this->node==0)
return;
2489 if(this->node->parent!=0)
2490 parent_=this->node->parent;
2493template <
class T,
class tree_node_allocator>
2497 this->node=this->node->next_sibling;
2501template <
class T,
class tree_node_allocator>
2504 if(this->node) this->node=this->node->prev_sibling;
2507 this->node=parent_->last_child;
2512template <
class T,
class tree_node_allocator>
2520template <
class T,
class tree_node_allocator>
2528template <
class T,
class tree_node_allocator>
2538template <
class T,
class tree_node_allocator>
2548template <
class T,
class tree_node_allocator>
2555template <
class T,
class tree_node_allocator>
2563template <
class T,
class tree_node_allocator>
2569template <
class T,
class tree_node_allocator>
2575template <
class T,
class tree_node_allocator>
2581template <
class T,
class tree_node_allocator>
2594template <
class T,
class tree_node_allocator>
2597 assert(this->node!=0);
2598 while(this->node->next_sibling==0) {
2599 if (this->node->parent==0)
return *
this;
2600 this->node=this->node->parent;
2602 this->node=this->node->next_sibling;
2603 while(this->node->first_child)
2604 this->node=this->node->first_child;
2608template <
class T,
class tree_node_allocator>
2611 assert(this->node!=0);
2612 while (this->node->prev_sibling==0) {
2613 if (this->node->parent==0)
return *
this;
2614 this->node=this->node->parent;
2616 this->node=this->node->prev_sibling;
2617 while(this->node->last_child)
2618 this->node=this->node->last_child;
2622template <
class T,
class tree_node_allocator>
2630template <
class T,
class tree_node_allocator>
2639template <
class T,
class tree_node_allocator>
2649template <
class T,
class tree_node_allocator>
Breadth-first iterator, using a queue.
Definition: tree.hh:200
bool operator!=(const breadth_first_queued_iterator &) const
Definition: tree.hh:2210
breadth_first_queued_iterator()
Definition: tree.hh:2190
std::queue< tree_node * > traversal_queue
Definition: tree.hh:213
bool operator==(const breadth_first_queued_iterator &) const
Definition: tree.hh:2217
breadth_first_queued_iterator & operator++()
Definition: tree.hh:2224
breadth_first_queued_iterator & operator+=(unsigned int)
Definition: tree.hh:2251
Comparator class for two nodes of a tree (used for sorting and searching).
Definition: tree.hh:447
StrictWeakOrdering comp_
Definition: tree.hh:457
bool operator()(const tree_node *a, const tree_node *b)
Definition: tree.hh:451
compare_nodes(StrictWeakOrdering comp)
Definition: tree.hh:449
Iterator which traverses only the nodes at a given depth from the root.
Definition: tree.hh:221
fixed_depth_iterator()
Definition: tree.hh:2265
fixed_depth_iterator & operator--()
Definition: tree.hh:2393
bool operator!=(const fixed_depth_iterator &) const
Definition: tree.hh:2306
tree_node * first_parent_
Definition: tree.hh:238
fixed_depth_iterator & operator+=(unsigned int)
Definition: tree.hh:2443
fixed_depth_iterator & operator++()
Definition: tree.hh:2338
void find_leftmost_parent_()
Definition: tree.hh:2326
bool operator==(const fixed_depth_iterator &) const
Definition: tree.hh:2299
void set_first_parent_()
Definition: tree.hh:2313
fixed_depth_iterator & operator-=(unsigned int)
Definition: tree.hh:2433
Comparator class for iterators (compares pointer values; why doesn't this work automatically?...
Definition: tree.hh:431
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
Base class for iterators, only pointers stored, no traversal logic.
Definition: tree.hh:131
T & reference
Definition: tree.hh:136
T * pointer
Definition: tree.hh:135
iterator_base()
Definition: tree.hh:1842
sibling_iterator end() const
Definition: tree.hh:1933
std::bidirectional_iterator_tag iterator_category
Definition: tree.hh:139
bool skip_current_children_
Definition: tree.hh:157
tree_node * node
Definition: tree.hh:155
T * operator->() const
Definition: tree.hh:1860
void skip_children()
When called, the next increment/decrement skips children of this node.
Definition: tree.hh:1941
size_t size_type
Definition: tree.hh:137
T value_type
Definition: tree.hh:134
T & operator*() const
Definition: tree.hh:1854
unsigned int number_of_children() const
Number of children of the node pointed to by the iterator.
Definition: tree.hh:1947
sibling_iterator begin() const
Definition: tree.hh:1922
ptrdiff_t difference_type
Definition: tree.hh:138
Iterator which traverses only the leaves.
Definition: tree.hh:269
bool operator!=(const leaf_iterator &) const
Definition: tree.hh:1908
leaf_iterator & operator--()
Definition: tree.hh:2609
leaf_iterator()
Definition: tree.hh:2564
bool operator==(const leaf_iterator &) const
Definition: tree.hh:1915
leaf_iterator & operator++()
Definition: tree.hh:2595
leaf_iterator & operator-=(unsigned int)
Definition: tree.hh:2650
leaf_iterator & operator+=(unsigned int)
Definition: tree.hh:2640
Depth-first iterator, first accessing the children, then the node itself.
Definition: tree.hh:179
post_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2159
post_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2169
post_order_iterator & operator++()
Definition: tree.hh:2105
bool operator!=(const post_order_iterator &) const
Definition: tree.hh:1866
bool operator==(const post_order_iterator &) const
Definition: tree.hh:1873
void descend_all()
Set iterator to the first child as deep as possible down the tree.
Definition: tree.hh:2179
post_order_iterator()
Definition: tree.hh:2073
post_order_iterator & operator--()
Definition: tree.hh:2126
Depth-first iterator, first accessing the node, then its children.
Definition: tree.hh:161
pre_order_iterator & operator++()
Definition: tree.hh:1997
pre_order_iterator & operator--()
Definition: tree.hh:2016
pre_order_iterator & operator+=(unsigned int)
Definition: tree.hh:2049
bool operator==(const pre_order_iterator &) const
Definition: tree.hh:1887
pre_order_iterator & operator-=(unsigned int)
Definition: tree.hh:2059
bool operator!=(const pre_order_iterator &) const
Definition: tree.hh:1880
pre_order_iterator()
Definition: tree.hh:1965
Iterator which traverses only the nodes which are siblings of each other.
Definition: tree.hh:245
void set_parent_()
Definition: tree.hh:2485
tree_node * parent_
Definition: tree.hh:263
tree_node * range_first() const
Definition: tree.hh:2549
sibling_iterator & operator--()
Definition: tree.hh:2502
tree_node * range_last() const
Definition: tree.hh:2556
sibling_iterator & operator++()
Definition: tree.hh:2494
bool operator!=(const sibling_iterator &) const
Definition: tree.hh:1894
bool operator==(const sibling_iterator &) const
Definition: tree.hh:1901
sibling_iterator & operator+=(unsigned int)
Definition: tree.hh:2529
sibling_iterator()
Definition: tree.hh:2458
sibling_iterator & operator-=(unsigned int)
Definition: tree.hh:2539
A node in the tree, combining links to other nodes as well as the actual data.
Definition: tree.hh:98
tree_node_< T > * next_sibling
Definition: tree.hh:102
T data
Definition: tree.hh:103
tree_node_< T > * parent
Definition: tree.hh:100
tree_node_< T > * last_child
Definition: tree.hh:101
tree_node_< T > * first_child
Definition: tree.hh:101
tree_node_< T > * prev_sibling
Definition: tree.hh:102
post_order_iterator begin_post() const
Return post-order iterator to the beginning of the tree.
Definition: tree.hh:667
void erase_children(const iterator_base &)
Erase all children of the node pointed to by iterator.
Definition: tree.hh:594
bool equal_subtree(const iter &one, const iter &two) const
Definition: tree.hh:1547
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
tree_node * head
Definition: tree.hh:439
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
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
T value_type
Value of the data stored at a node.
Definition: tree.hh:112
pre_order_iterator iterator
The default iterator types throughout the tree class.
Definition: tree.hh:217
static unsigned int number_of_children(const iterator_base &)
Count the number of children of node at position.
Definition: tree.hh:1678
iter insert_after(iter position, const T &x)
Insert node as next sibling of node pointed to by position.
Definition: tree.hh:1049
void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
Definition: tree.hh:1479
sibling_iterator move_before(sibling_iterator target, sibling_iterator source)
Definition: tree.hh:1375
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
void copy_(const tree< T, tree_node_allocator > &other)
Definition: tree.hh:565
leaf_iterator end_leaf() const
Return leaf iterator to the last leaf of the tree.
Definition: tree.hh:755
sibling_iterator insert(sibling_iterator position, const T &x)
Specialisation of previous member.
Definition: tree.hh:1019
static iter parent(iter)
Return iterator to the parent of a node.
Definition: tree.hh:762
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
iter previous_sibling(iter) const
Return iterator to the previous sibling of a node.
Definition: tree.hh:770
void head_initialise_()
Definition: tree.hh:533
tree(const T &)
Definition: tree.hh:510
breadth_first_queued_iterator breadth_first_iterator
Definition: tree.hh:218
tree_node_< T > tree_node
Definition: tree.hh:109
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
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
tree_node_allocator alloc_
Definition: tree.hh:441
iter reparent(iter position, iter from)
Move all child nodes of 'from' to be children of 'position'.
Definition: tree.hh:1298
int depth(const iterator_base &) const
Compute the depth to the root.
Definition: tree.hh:1633
sibling_iterator end(const iterator_base &) const
Return sibling iterator to the end of the children of a given node.
Definition: tree.hh:736
breadth_first_queued_iterator end_breadth_first() const
Return breadth-first iterator to end of the nodes at given depth.
Definition: tree.hh:661
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
iter append_child(iter position, iter other_position)
Append the node (plus its children) at other_position as last/first child of position.
Definition: tree.hh:932
post_order_iterator end_post() const
Return post-order iterator to the end of the tree.
Definition: tree.hh:678
void operator=(const tree< T, tree_node_allocator > &)
Definition: tree.hh:552
iter append_child(iter position)
Insert empty node as last/first child of node pointed to by position.
Definition: tree.hh:828
iter next_sibling(iter) const
Return iterator to the next sibling of a node.
Definition: tree.hh:780
iter prepend_child(iter position, const T &x)
Definition: tree.hh:907
tree()
Definition: tree.hh:504
iter prepend_child(iter position)
Definition: tree.hh:853
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
void subtree(tree &, sibling_iterator from, sibling_iterator to) const
Definition: tree.hh:1593
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
void clear()
Erase all nodes of the tree.
Definition: tree.hh:586
sibling_iterator begin(const iterator_base &) const
Return sibling iterator to the first child of given node.
Definition: tree.hh:726
leaf_iterator begin_leaf() const
Return leaf iterator to the first leaf of the tree.
Definition: tree.hh:744
iter prepend_children(iter position, sibling_iterator from, sibling_iterator to)
Definition: tree.hh:970
iter replace(iter position, const T &x)
Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
Definition: tree.hh:1103
iter move_after(iter target, iter source)
Move 'source' node (plus its children) to become the next sibling of 'target'.
Definition: tree.hh:1316
bool equal(const iter &one, const iter &two, const iter &three, BinaryPredicate) const
Definition: tree.hh:1555
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
tree(const iterator_base &)
Definition: tree.hh:517
pre_order_iterator begin() const
Return iterator to the beginning of the tree.
Definition: tree.hh:643
int size(const iterator_base &) const
Count the total number of nodes below the indicated node (plus one).
Definition: tree.hh:1612
iter insert(iter position, const T &x)
Insert node as previous sibling of node pointed to by position.
Definition: tree.hh:993
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
int max_depth() const
Determine the maximal depth of the tree.
Definition: tree.hh:1646
breadth_first_queued_iterator begin_breadth_first() const
Return breadth-first iterator to the first node at a given depth.
Definition: tree.hh:655
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
bool equal_subtree(const iter &one, const iter &two, BinaryPredicate) const
Definition: tree.hh:1574
iter prepend_child(iter position, iter other_position)
Definition: tree.hh:943
void swap(iterator, iterator)
Exchange two nodes (plus subtrees)
Definition: tree.hh:1739
iter append_child(iter position, const T &x)
Insert node as last/first child of node pointed to by position.
Definition: tree.hh:878
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 * feet
Definition: tree.hh:439
bool empty() const
Check if tree is empty.
Definition: tree.hh:1626
void swap(sibling_iterator it)
Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
Definition: tree.hh:1718
tree(const tree< T, tree_node_allocator > &)
Definition: tree.hh:558
int max_depth(const iterator_base &) const
Determine the maximal depth of the tree below a given one.
Definition: tree.hh:1653
int size() const
Count the total number of nodes.
Definition: tree.hh:1600
~tree()
Definition: tree.hh:525
pre_order_iterator set_head(const T &x)
Short-hand to insert topmost node in otherwise empty tree.
Definition: tree.hh:985
iter flatten(iter position)
Move all children of node at 'position' to be siblings, returns position.
Definition: tree.hh:1222
iter replace(iter position, const iterator_base &from)
Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see abov...
Definition: tree.hh:1112
unsigned int number_of_siblings(const iterator_base &) const
Count the number of 'next' siblings of node at iterator.
Definition: tree.hh:1694
iter erase(iter)
Erase element at position pointed to by iterator, return incremented iterator.
Definition: tree.hh:616
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
iter next_at_same_depth(iter) const
Return iterator to the next node at a given depth.
Definition: tree.hh:790
pre_order_iterator end() const
Return iterator to the end of the tree.
Definition: tree.hh:649
sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
Replace string of siblings (plus their children) with copy of a new string (with children); see above...
Definition: tree.hh:1176
iter move_before(iter target, iter source)
Move 'source' node (plus its children) to become the previous sibling of 'target'.
Definition: tree.hh:1345
void destructor(T1 *p)
Definition: tree.hh:89
void constructor(T1 *p, T2 &val)
Definition: tree.hh:77