[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnash-commit] gnash ChangeLog libbase/Makefile.am libbase/tre...
|
From: |
Sandro Santilli |
|
Subject: |
[Gnash-commit] gnash ChangeLog libbase/Makefile.am libbase/tre... |
|
Date: |
Fri, 24 Aug 2007 10:07:41 +0000 |
CVSROOT: /sources/gnash
Module name: gnash
Changes by: Sandro Santilli <strk> 07/08/24 10:07:41
Modified files:
. : ChangeLog
libbase : Makefile.am
Added files:
libbase : tree.hh
Removed files:
libbase : tree.hpp
Log message:
* libbase/: tree.hpp => tree.hh: don't change original name of
external source code.
* libbase/Makefile.am: distribute tree.hh
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gnash/ChangeLog?cvsroot=gnash&r1=1.4092&r2=1.4093
http://cvs.savannah.gnu.org/viewcvs/gnash/libbase/Makefile.am?cvsroot=gnash&r1=1.78&r2=1.79
http://cvs.savannah.gnu.org/viewcvs/gnash/libbase/tree.hh?cvsroot=gnash&rev=1.3
http://cvs.savannah.gnu.org/viewcvs/gnash/libbase/tree.hpp?cvsroot=gnash&r1=1.1&r2=0
Patches:
Index: ChangeLog
===================================================================
RCS file: /sources/gnash/gnash/ChangeLog,v
retrieving revision 1.4092
retrieving revision 1.4093
diff -u -b -r1.4092 -r1.4093
--- ChangeLog 24 Aug 2007 10:05:57 -0000 1.4092
+++ ChangeLog 24 Aug 2007 10:07:40 -0000 1.4093
@@ -1,5 +1,11 @@
2007-08-24 Sandro Santilli <address@hidden>
+ * libbase/: tree.hpp => tree.hh: don't change original name of
+ external source code.
+ * libbase/Makefile.am: distribute tree.hh
+
+2007-08-24 Sandro Santilli <address@hidden>
+
* testsuite/actionscript.all/MovieClip.as: test that '_root' and
'_level0' can be accessed as members of a movieclip, while 'this'
cannot.
Index: libbase/Makefile.am
===================================================================
RCS file: /sources/gnash/gnash/libbase/Makefile.am,v
retrieving revision 1.78
retrieving revision 1.79
diff -u -b -r1.78 -r1.79
--- libbase/Makefile.am 10 Aug 2007 04:36:13 -0000 1.78
+++ libbase/Makefile.am 24 Aug 2007 10:07:41 -0000 1.79
@@ -130,6 +130,7 @@
ref_counted.h \
smart_ptr.h \
sharedlib.h \
+ tree.hh \
triangulate.h \
triangulate_impl.h \
tu_config.h \
Index: libbase/tree.hh
===================================================================
RCS file: libbase/tree.hh
diff -N libbase/tree.hh
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ libbase/tree.hh 24 Aug 2007 10:07:41 -0000 1.3
@@ -0,0 +1,2620 @@
+/*
+
+ $Id: tree.hh,v 1.3 2007/08/24 10:07:41 strk Exp $
+
+ STL-like templated tree class.
+ Copyright (C) 2001-2006 Kasper Peeters <address@hidden>.
+
+*/
+
+/** \mainpage tree.hh
+ \author Kasper Peeters
+ \version 2.31
+ \date 21-Aug-2007
+ \see http://www.aei.mpg.de/~peekas/tree/
+ \see http://www.aei.mpg.de/~peekas/tree/ChangeLog
+
+ The tree.hh library for C++ provides an STL-like container class
+ for n-ary trees, templated over the data stored at the
+ nodes. Various types of iterators are provided (post-order,
+ pre-order, and others). Where possible the access methods are
+ compatible with the STL or alternative algorithms are
+ available.
+*/
+
+
+/*
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 or 3.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+/** \todo
+ - New-style move members are not completely finished yet.
+ - It would be good to have an iterator which can iterate over all
+ nodes below a given node.
+ - Fixed depth iterators do not iterate over the entire range if there
+ are 'holes' in the tree.
+ - If a range uses const iter_base& as end iterator, things will
+ inevitably go wrong, because upcast from iter_base to a non-sibling_iter
+ is incorrect. This upcast should be removed (and then all illegal uses
+ as previously in 'equal' will be flagged by the compiler). This requires
+ new copy constructors though.
+ - There's a bug in replace(sibling_iterator, ...) when the ranges
+ sit next to each other. Turned up in append_child(iter,iter)
+ but has been avoided now.
+ - "std::operator<" does not work correctly on our iterators, and for some
+ reason a globally defined template operator< did not get picked up.
+ Using a comparison class now, but this should be investigated.
+*/
+
+#ifndef tree_hh_
+#define tree_hh_
+
+#include <cassert>
+#include <memory>
+#include <stdexcept>
+#include <iterator>
+#include <set>
+#include <queue>
+#include <iostream>
+
+// HP-style construct/destroy have gone from the standard,
+// so here is a copy.
+
+namespace kp {
+
+template <class T1, class T2>
+void constructor(T1* p, T2& val)
+ {
+ new ((void *) p) T1(val);
+ }
+
+template <class T1>
+void constructor(T1* p)
+ {
+ new ((void *) p) T1;
+ }
+
+template <class T1>
+void destructor(T1* p)
+ {
+ p->~T1();
+ }
+
+};
+
+/// A node in the tree, combining links to other nodes as well as the actual
data.
+template<class T>
+class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
+ public:
+ tree_node_<T> *parent;
+ tree_node_<T> *first_child, *last_child;
+ tree_node_<T> *prev_sibling, *next_sibling;
+ T data;
+}; // __attribute__((packed));
+
+template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
+class tree {
+ protected:
+ typedef tree_node_<T> tree_node;
+ public:
+ /// Value of the data stored at a node.
+ typedef T value_type;
+
+ class iterator_base;
+ class pre_order_iterator;
+ class post_order_iterator;
+ class sibling_iterator;
+ class leaf_iterator;
+
+ tree();
+ tree(const T&);
+ tree(const iterator_base&);
+ tree(const tree<T, tree_node_allocator>&);
+ ~tree();
+ void operator=(const tree<T, tree_node_allocator>&);
+
+ /// Base class for iterators, only pointers stored, no traversal logic.
+#ifdef __SGI_STL_PORT
+ class iterator_base : public stlport::bidirectional_iterator<T,
ptrdiff_t> {
+#else
+ class iterator_base {
+#endif
+ public:
+ typedef T value_type;
+ typedef T* pointer;
+ typedef T& reference;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef std::bidirectional_iterator_tag iterator_category;
+
+ iterator_base();
+ iterator_base(tree_node *);
+
+ T& operator*() const;
+ T* operator->() const;
+
+ /// When called, the next increment/decrement skips children of
this node.
+ void skip_children();
+ /// Number of children of the node pointed to by the iterator.
+ unsigned int number_of_children() const;
+
+ sibling_iterator begin() const;
+ sibling_iterator end() const;
+
+ tree_node *node;
+ protected:
+ bool skip_current_children_;
+ };
+
+ /// Depth-first iterator, first accessing the node, then its children.
+ class pre_order_iterator : public iterator_base {
+ public:
+ pre_order_iterator();
+ pre_order_iterator(tree_node *);
+ pre_order_iterator(const iterator_base&);
+ pre_order_iterator(const sibling_iterator&);
+
+ bool operator==(const pre_order_iterator&) const;
+ bool operator!=(const pre_order_iterator&) const;
+ pre_order_iterator& operator++();
+ pre_order_iterator& operator--();
+ pre_order_iterator operator++(int);
+ pre_order_iterator operator--(int);
+ pre_order_iterator& operator+=(unsigned int);
+ pre_order_iterator& operator-=(unsigned int);
+ };
+
+ /// Depth-first iterator, first accessing the children, then the node
itself.
+ class post_order_iterator : public iterator_base {
+ public:
+ post_order_iterator();
+ post_order_iterator(tree_node *);
+ post_order_iterator(const iterator_base&);
+ post_order_iterator(const sibling_iterator&);
+
+ bool operator==(const post_order_iterator&) const;
+ bool operator!=(const post_order_iterator&) const;
+ post_order_iterator& operator++();
+ post_order_iterator& operator--();
+ post_order_iterator operator++(int);
+ post_order_iterator operator--(int);
+ post_order_iterator& operator+=(unsigned int);
+ post_order_iterator& operator-=(unsigned int);
+
+ /// Set iterator to the first child as deep as possible down the
tree.
+ void descend_all();
+ };
+
+ /// Breadth-first iterator, using a queue
+ class breadth_first_queued_iterator : public iterator_base {
+ public:
+ breadth_first_queued_iterator();
+ breadth_first_queued_iterator(tree_node *);
+ breadth_first_queued_iterator(const iterator_base&);
+
+ bool operator==(const breadth_first_queued_iterator&) const;
+ bool operator!=(const breadth_first_queued_iterator&) const;
+ breadth_first_queued_iterator& operator++();
+ breadth_first_queued_iterator operator++(int);
+ breadth_first_queued_iterator& operator+=(unsigned int);
+
+ private:
+ std::queue<tree_node *> traversal_queue;
+ };
+
+ /// The default iterator types throughout the tree class.
+ typedef pre_order_iterator iterator;
+ typedef breadth_first_queued_iterator breadth_first_iterator;
+
+ /// Iterator which traverses only the nodes at a given depth from the
root.
+ class fixed_depth_iterator : public iterator_base {
+ public:
+ fixed_depth_iterator();
+ fixed_depth_iterator(tree_node *);
+ fixed_depth_iterator(const iterator_base&);
+ fixed_depth_iterator(const sibling_iterator&);
+ fixed_depth_iterator(const fixed_depth_iterator&);
+
+ bool operator==(const fixed_depth_iterator&) const;
+ bool operator!=(const fixed_depth_iterator&) const;
+ fixed_depth_iterator& operator++();
+ fixed_depth_iterator& operator--();
+ fixed_depth_iterator operator++(int);
+ fixed_depth_iterator operator--(int);
+ fixed_depth_iterator& operator+=(unsigned int);
+ fixed_depth_iterator& operator-=(unsigned int);
+
+ tree_node *first_parent_;
+ private:
+ void set_first_parent_();
+ void find_leftmost_parent_();
+ };
+
+ /// Iterator which traverses only the nodes which are siblings of each
other.
+ class sibling_iterator : public iterator_base {
+ public:
+ sibling_iterator();
+ sibling_iterator(tree_node *);
+ sibling_iterator(const sibling_iterator&);
+ sibling_iterator(const iterator_base&);
+
+ bool operator==(const sibling_iterator&) const;
+ bool operator!=(const sibling_iterator&) const;
+ sibling_iterator& operator++();
+ sibling_iterator& operator--();
+ sibling_iterator operator++(int);
+ sibling_iterator operator--(int);
+ sibling_iterator& operator+=(unsigned int);
+ sibling_iterator& operator-=(unsigned int);
+
+ tree_node *range_first() const;
+ tree_node *range_last() const;
+ tree_node *parent_;
+ private:
+ void set_parent_();
+ };
+
+ /// Iterator which traverses only the leaves.
+ class leaf_iterator : public iterator_base {
+ public:
+ leaf_iterator();
+ leaf_iterator(tree_node *);
+ leaf_iterator(const sibling_iterator&);
+ leaf_iterator(const iterator_base&);
+
+ bool operator==(const leaf_iterator&) const;
+ bool operator!=(const leaf_iterator&) const;
+ leaf_iterator& operator++();
+ leaf_iterator& operator--();
+ leaf_iterator operator++(int);
+ leaf_iterator operator--(int);
+ leaf_iterator& operator+=(unsigned int);
+ leaf_iterator& operator-=(unsigned int);
+ };
+
+ /// Return iterator to the beginning of the tree.
+ inline pre_order_iterator begin() const;
+ /// Return iterator to the end of the tree.
+ inline pre_order_iterator end() const;
+ /// Return post-order iterator to the beginning of the tree.
+ post_order_iterator begin_post() const;
+ /// Return post-order iterator to the end of the tree.
+ post_order_iterator end_post() const;
+ /// Return fixed-depth iterator to the first node at a given depth.
+ fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int)
const;
+ /// Return fixed-depth iterator to end of the nodes at given depth.
+ fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
+ /// Return breadth-first iterator to the first node at a given depth.
+ breadth_first_queued_iterator begin_breadth_first() const;
+ /// Return breadth-first iterator to end of the nodes at given depth.
+ breadth_first_queued_iterator end_breadth_first() const;
+ /// Return sibling iterator to the first child of given node.
+ sibling_iterator begin(const iterator_base&) const;
+ /// Return sibling iterator to the end of the children of a given node.
+ sibling_iterator end(const iterator_base&) const;
+ /// Return leaf iterator to the first leaf of the tree.
+ leaf_iterator begin_leaf() const;
+ /// Return leaf iterator to the last leaf of the tree.
+ leaf_iterator end_leaf() const;
+
+ /// Return iterator to the parent of a node.
+ template<typename iter> static iter parent(iter);
+ /// Return iterator to the previous sibling of a node.
+ template<typename iter> iter previous_sibling(iter) const;
+ /// Return iterator to the next sibling of a node.
+ template<typename iter> iter next_sibling(iter) const;
+ /// Return iterator to the next node at a given depth.
+ template<typename iter> iter next_at_same_depth(iter) const;
+
+ /// Erase all nodes of the tree.
+ void clear();
+ /// Erase element at position pointed to by iterator, return incremented
iterator.
+ template<typename iter> iter erase(iter);
+ /// Erase all children of the node pointed to by iterator.
+ void erase_children(const iterator_base&);
+
+ /// Insert empty node as last/first child of node pointed to by position.
+ template<typename iter> iter append_child(iter position);
+ template<typename iter> iter prepend_child(iter position);
+ /// Insert node as last/first child of node pointed to by position.
+ template<typename iter> iter append_child(iter position, const T& x);
+ template<typename iter> iter prepend_child(iter position, const T& x);
+ /// Append the node (plus its children) at other_position as last/first
child of position.
+ template<typename iter> iter append_child(iter position, iter
other_position);
+ template<typename iter> iter prepend_child(iter position, iter
other_position);
+ /// Append the nodes in the from-to range (plus their children) as
last/first children of position.
+ template<typename iter> iter append_children(iter position,
sibling_iterator from, sibling_iterator to);
+ template<typename iter> iter prepend_children(iter position,
sibling_iterator from, sibling_iterator to);
+
+ /// Short-hand to insert topmost node in otherwise empty tree.
+ pre_order_iterator set_head(const T& x);
+ /// Insert node as previous sibling of node pointed to by position.
+ template<typename iter> iter insert(iter position, const T& x);
+ /// Specialisation of previous member.
+ sibling_iterator insert(sibling_iterator position, const T& x);
+ /// Insert node (with children) pointed to by subtree as previous
sibling of node pointed to by position.
+ template<typename iter> iter insert_subtree(iter position, const
iterator_base& subtree);
+ /// Insert node as next sibling of node pointed to by position.
+ template<typename iter> iter insert_after(iter position, const T& x);
+ /// Insert node (with children) pointed to by subtree as next sibling of
node pointed to by position.
+ template<typename iter> iter insert_subtree_after(iter position, const
iterator_base& subtree);
+
+ /// Replace node at 'position' with other node (keeping same children);
'position' becomes invalid.
+ template<typename iter> iter replace(iter position, const T& x);
+ /// Replace node at 'position' with subtree starting at 'from' (do not
erase subtree at 'from'); see above.
+ template<typename iter> iter replace(iter position, const iterator_base&
from);
+ /// Replace string of siblings (plus their children) with copy of a new
string (with children); see above
+ sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator
orig_end,
+ sibling_iterator new_begin, sibling_iterator
new_end);
+
+ /// Move all children of node at 'position' to be siblings, returns
position.
+ template<typename iter> iter flatten(iter position);
+ /// Move nodes in range to be children of 'position'.
+ template<typename iter> iter reparent(iter position, sibling_iterator
begin, sibling_iterator end);
+ /// Move all child nodes of 'from' to be children of 'position'.
+ template<typename iter> iter reparent(iter position, iter from);
+
+ /// Replace node with a new node, making the old node a child of the new
node.
+ template<typename iter> iter wrap(iter position, const T& x);
+
+ /// Move 'source' node (plus its children) to become the next sibling of
'target'.
+ template<typename iter> iter move_after(iter target, iter source);
+ /// Move 'source' node (plus its children) to become the previous
sibling of 'target'.
+ template<typename iter> iter move_before(iter target, iter source);
+ sibling_iterator move_before(sibling_iterator target, sibling_iterator
source);
+ /// Move 'source' node (plus its children) to become the node at
'target' (erasing the node at 'target').
+ template<typename iter> iter move_ontop(iter target, iter source);
+
+ /// Merge with other tree, creating new branches and leaves only if they
are not already present.
+ void merge(sibling_iterator, sibling_iterator, sibling_iterator,
sibling_iterator,
+ bool duplicate_leaves=false);
+ /// Sort (std::sort only moves values of nodes, this one moves children
as well).
+ void sort(sibling_iterator from, sibling_iterator to, bool
deep=false);
+ template<class StrictWeakOrdering>
+ void sort(sibling_iterator from, sibling_iterator to,
StrictWeakOrdering comp, bool deep=false);
+ /// Compare two ranges of nodes (compares nodes as well as tree
structure).
+ template<typename iter>
+ bool equal(const iter& one, const iter& two, const iter& three)
const;
+ template<typename iter, class BinaryPredicate>
+ bool equal(const iter& one, const iter& two, const iter& three,
BinaryPredicate) const;
+ template<typename iter>
+ bool equal_subtree(const iter& one, const iter& two) const;
+ template<typename iter, class BinaryPredicate>
+ bool equal_subtree(const iter& one, const iter& two,
BinaryPredicate) const;
+ /// Extract a new tree formed by the range of siblings plus all their
children.
+ tree subtree(sibling_iterator from, sibling_iterator to) const;
+ void subtree(tree&, sibling_iterator from, sibling_iterator to)
const;
+ /// Exchange the node (plus subtree) with its sibling node (do nothing
if no sibling present).
+ void swap(sibling_iterator it);
+ /// Exchange two nodes (plus subtrees)
+ void swap(iterator, iterator);
+
+ /// Count the total number of nodes.
+ int size() const;
+ /// Count the total number of nodes below the indicated node (plus one).
+ int size(const iterator_base&) const;
+ /// Check if tree is empty.
+ bool empty() const;
+ /// Compute the depth to the root.
+ int depth(const iterator_base&) const;
+ /// Count the number of children of node at position.
+ static unsigned int number_of_children(const iterator_base&);
+ /// Count the number of 'next' siblings of node at iterator.
+ unsigned int number_of_siblings(const iterator_base&) const;
+ /// Determine whether node at position is in the subtrees with root in
the range.
+ bool is_in_subtree(const iterator_base& position, const
iterator_base& begin,
+ const iterator_base& end) const;
+ /// Determine whether the iterator is an 'end' iterator and thus not
actually pointing to a node.
+ bool is_valid(const iterator_base&) const;
+
+ /// Determine the index of a node in the range of siblings to which it
belongs.
+ unsigned int index(sibling_iterator it) const;
+ /// Inverse of 'index': return the n-th child of the node at position.
+ sibling_iterator child(const iterator_base& position, unsigned int)
const;
+
+ /// Comparator class for iterators (compares pointer values; why doesn't
this work automatically?)
+ class iterator_base_less {
+ public:
+ bool operator()(const typename tree<T,
tree_node_allocator>::iterator_base& one,
+ const typename tree<T,
tree_node_allocator>::iterator_base& two) const
+ {
+ return one.node < two.node;
+ }
+ };
+ tree_node *head, *feet; // head/feet are always dummy; if an iterator
points to them it is invalid
+ private:
+ tree_node_allocator alloc_;
+ void head_initialise_();
+ void copy_(const tree<T, tree_node_allocator>& other);
+
+ /// Comparator class for two nodes of a tree (used for sorting and
searching).
+ template<class StrictWeakOrdering>
+ class compare_nodes {
+ public:
+ compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
+
+ bool operator()(const tree_node *a, const tree_node *b)
+ {
+ static StrictWeakOrdering comp;
+ return comp(a->data, b->data);
+ }
+ private:
+ StrictWeakOrdering comp_;
+ };
+};
+
+//template <class T, class tree_node_allocator>
+//class iterator_base_less {
+// public:
+// bool operator()(const typename tree<T,
tree_node_allocator>::iterator_base& one,
+// const typename tree<T,
tree_node_allocator>::iterator_base& two) const
+// {
+// txtout << "operatorclass<" << one.node < two.node << std::endl;
+// return one.node < two.node;
+// }
+//};
+
+// template <class T, class tree_node_allocator>
+// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
+// const typename tree<T, tree_node_allocator>::iterator& two)
+// {
+// txtout << "operator< " << one.node < two.node << std::endl;
+// if(one.node < two.node) return true;
+// return false;
+// }
+//
+// template <class T, class tree_node_allocator>
+// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
+// const typename tree<T, tree_node_allocator>::iterator& two)
+// {
+// txtout << "operator== " << one.node == two.node << std::endl;
+// if(one.node == two.node) return true;
+// return false;
+// }
+//
+// template <class T, class tree_node_allocator>
+// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base&
one,
+// const typename tree<T, tree_node_allocator>::iterator_base&
two)
+// {
+// txtout << "operator> " << one.node < two.node << std::endl;
+// if(one.node > two.node) return true;
+// return false;
+// }
+
+
+
+// Tree
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::tree()
+ {
+ head_initialise_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::tree(const T& x)
+ {
+ head_initialise_();
+ set_head(x);
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::tree(const iterator_base& other)
+ {
+ head_initialise_();
+ set_head((*other));
+ replace(begin(), other);
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::~tree()
+ {
+ clear();
+ alloc_.deallocate(head,1);
+ alloc_.deallocate(feet,1);
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::head_initialise_()
+ {
+ head = alloc_.allocate(1,0); // MSVC does not have default second argument
+ feet = alloc_.allocate(1,0);
+
+ head->parent=0;
+ head->first_child=0;
+ head->last_child=0;
+ head->prev_sibling=0; //head;
+ head->next_sibling=feet; //head;
+
+ feet->parent=0;
+ feet->first_child=0;
+ feet->last_child=0;
+ feet->prev_sibling=head;
+ feet->next_sibling=0;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::operator=(const tree<T,
tree_node_allocator>& other)
+ {
+ copy_(other);
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
+ {
+ head_initialise_();
+ copy_(other);
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>&
other)
+ {
+ clear();
+ pre_order_iterator it=other.begin(), to=begin();
+ while(it!=other.end()) {
+ to=insert(to, (*it));
+ it.skip_children();
+ ++it;
+ }
+ to=begin();
+ it=other.begin();
+ while(it!=other.end()) {
+ to=replace(to, it);
+ to.skip_children();
+ it.skip_children();
+ ++to;
+ ++it;
+ }
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::clear()
+ {
+ if(head)
+ while(head->next_sibling!=feet)
+ erase(pre_order_iterator(head->next_sibling));
+ }
+
+template<class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
+ {
+// std::cout << "erase_children " << it.node << std::endl;
+ if(it.node==0) return;
+
+ tree_node *cur=it.node->first_child;
+ tree_node *prev=0;
+
+ while(cur!=0) {
+ prev=cur;
+ cur=cur->next_sibling;
+ erase_children(pre_order_iterator(prev));
+ kp::destructor(&prev->data);
+ alloc_.deallocate(prev,1);
+ }
+ it.node->first_child=0;
+ it.node->last_child=0;
+// std::cout << "exit" << std::endl;
+ }
+
+template<class T, class tree_node_allocator>
+template<class iter>
+iter tree<T, tree_node_allocator>::erase(iter it)
+ {
+ tree_node *cur=it.node;
+ assert(cur!=head);
+ iter ret=it;
+ ret.skip_children();
+ ++ret;
+ erase_children(it);
+ if(cur->prev_sibling==0) {
+ cur->parent->first_child=cur->next_sibling;
+ }
+ else {
+ cur->prev_sibling->next_sibling=cur->next_sibling;
+ }
+ if(cur->next_sibling==0) {
+ cur->parent->last_child=cur->prev_sibling;
+ }
+ else {
+ cur->next_sibling->prev_sibling=cur->prev_sibling;
+ }
+
+ kp::destructor(&cur->data);
+ alloc_.deallocate(cur,1);
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::begin() const
+ {
+ return pre_order_iterator(head->next_sibling);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::end() const
+ {
+ return pre_order_iterator(feet);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::begin_breadth_first() const
+ {
+ return breadth_first_queued_iterator(head->next_sibling);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::end_breadth_first() const
+ {
+ return breadth_first_queued_iterator();
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::begin_post() const
+ {
+ tree_node *tmp=head->next_sibling;
+ if(tmp!=feet) {
+ while(tmp->first_child)
+ tmp=tmp->first_child;
+ }
+ return post_order_iterator(tmp);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::end_post() const
+ {
+ return post_order_iterator(feet);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp)
const
+ {
+ tree_node *tmp=pos.node;
+ unsigned int curdepth=0;
+ while(curdepth<dp) { // go down one level
+ while(tmp->first_child==0) {
+ tmp=tmp->next_sibling;
+ if(tmp==0)
+ throw std::range_error("tree: begin_fixed out of range");
+ }
+ tmp=tmp->first_child;
+ ++curdepth;
+ }
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
+ {
+ assert(1==0); // FIXME: not correct yet
+ tree_node *tmp=pos.node;
+ unsigned int curdepth=1;
+ while(curdepth<dp) { // go down one level
+ while(tmp->first_child==0) {
+ tmp=tmp->next_sibling;
+ if(tmp==0)
+ throw std::range_error("tree: end_fixed out of range");
+ }
+ tmp=tmp->first_child;
+ ++curdepth;
+ }
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::begin(const iterator_base& pos) const
+ {
+ assert(pos.node!=0);
+ if(pos.node->first_child==0) {
+ return end(pos);
+ }
+ return pos.node->first_child;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::end(const iterator_base& pos) const
+ {
+ sibling_iterator ret(0);
+ ret.parent_=pos.node;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::begin_leaf() const
+ {
+ tree_node *tmp=head->next_sibling;
+ if(tmp!=feet) {
+ while(tmp->first_child)
+ tmp=tmp->first_child;
+ }
+ return leaf_iterator(tmp);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::end_leaf() const
+ {
+ return leaf_iterator(feet);
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::parent(iter position)
+ {
+ assert(position.node!=0);
+ return iter(position.node->parent);
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
+ {
+ assert(position.node!=0);
+ iter ret(position);
+ ret.node=position.node->prev_sibling;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::next_sibling(iter position) const
+ {
+ assert(position.node!=0);
+ iter ret(position);
+ ret.node=position.node->next_sibling;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
+ {
+ assert(position.node!=0);
+ iter ret(position);
+
+ if(position.node->next_sibling) {
+ ret.node=position.node->next_sibling;
+ }
+ else {
+ int relative_depth=0;
+ upper:
+ do {
+ ret.node=ret.node->parent;
+ if(ret.node==0) return ret;
+ --relative_depth;
+ } while(ret.node->next_sibling==0);
+ lower:
+ ret.node=ret.node->next_sibling;
+ while(ret.node->first_child==0) {
+ if(ret.node->next_sibling==0)
+ goto upper;
+ ret.node=ret.node->next_sibling;
+ if(ret.node==0) return ret;
+ }
+ while(relative_depth<0 && ret.node->first_child!=0) {
+ ret.node=ret.node->first_child;
+ ++relative_depth;
+ }
+ if(relative_depth<0) {
+ if(ret.node->next_sibling==0) goto upper;
+ else goto lower;
+ }
+ }
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::append_child(iter position)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ tree_node *tmp=alloc_.allocate(1,0);
+ kp::constructor(&tmp->data);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node;
+ if(position.node->last_child!=0) {
+ position.node->last_child->next_sibling=tmp;
+ }
+ else {
+ position.node->first_child=tmp;
+ }
+ tmp->prev_sibling=position.node->last_child;
+ position.node->last_child=tmp;
+ tmp->next_sibling=0;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::prepend_child(iter position)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ tree_node *tmp=alloc_.allocate(1,0);
+ kp::constructor(&tmp->data);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node;
+ if(position.node->first_child!=0) {
+ position.node->first_child->prev_sibling=tmp;
+ }
+ else {
+ position.node->last_child=tmp;
+ }
+ tmp->next_sibling=position.node->first_child;
+ position.node->prev_child=tmp;
+ tmp->prev_sibling=0;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
+ {
+ // If your program fails here you probably used 'append_child' to add the
top
+ // node to an empty tree. From version 1.45 the top element should be added
+ // using 'insert'. See the documentation for further information, and sorry
about
+ // the API change.
+ assert(position.node!=head);
+ assert(position.node);
+
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, x);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node;
+ if(position.node->last_child!=0) {
+ position.node->last_child->next_sibling=tmp;
+ }
+ else {
+ position.node->first_child=tmp;
+ }
+ tmp->prev_sibling=position.node->last_child;
+ position.node->last_child=tmp;
+ tmp->next_sibling=0;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, x);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node;
+ if(position.node->first_child!=0) {
+ position.node->first_child->prev_sibling=tmp;
+ }
+ else {
+ position.node->last_child=tmp;
+ }
+ tmp->next_sibling=position.node->first_child;
+ position.node->first_child=tmp;
+ tmp->prev_sibling=0;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ sibling_iterator aargh=append_child(position, value_type());
+ return replace(aargh, other);
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ sibling_iterator aargh=prepend_child(position, value_type());
+ return replace(aargh, other);
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::append_children(iter position,
sibling_iterator from, sibling_iterator to)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ iter ret=from;
+
+ while(from!=to) {
+ insert_subtree(position.end(), from);
+ ++from;
+ }
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::prepend_children(iter position,
sibling_iterator from, sibling_iterator to)
+ {
+ assert(position.node!=head);
+ assert(position.node);
+
+ iter ret=from;
+
+ while(from!=to) {
+ insert_subtree(position.begin(), from);
+ ++from;
+ }
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::set_head(const T& x)
+ {
+ assert(head->next_sibling==feet);
+ return insert(iterator(feet), x);
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
+ {
+ if(position.node==0) {
+ position.node=feet; // Backward compatibility: when calling insert on a
null node,
+ // insert before the feet.
+ }
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, x);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node->parent;
+ tmp->next_sibling=position.node;
+ tmp->prev_sibling=position.node->prev_sibling;
+ position.node->prev_sibling=tmp;
+
+ if(tmp->prev_sibling==0) {
+ if(tmp->parent) // when inserting nodes at the head, there is no parent
+ tmp->parent->first_child=tmp;
+ }
+ else
+ tmp->prev_sibling->next_sibling=tmp;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::insert(sibling_iterator position, const T& x)
+ {
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, x);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->next_sibling=position.node;
+ if(position.node==0) { // iterator points to end of a subtree
+ tmp->parent=position.parent_;
+ tmp->prev_sibling=position.range_last();
+ tmp->parent->last_child=tmp;
+ }
+ else {
+ tmp->parent=position.node->parent;
+ tmp->prev_sibling=position.node->prev_sibling;
+ position.node->prev_sibling=tmp;
+ }
+
+ if(tmp->prev_sibling==0) {
+ if(tmp->parent) // when inserting nodes at the head, there is no parent
+ tmp->parent->first_child=tmp;
+ }
+ else
+ tmp->prev_sibling->next_sibling=tmp;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
+ {
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, x);
+ tmp->first_child=0;
+ tmp->last_child=0;
+
+ tmp->parent=position.node->parent;
+ tmp->prev_sibling=position.node;
+ tmp->next_sibling=position.node->next_sibling;
+ position.node->next_sibling=tmp;
+
+ if(tmp->next_sibling==0) {
+ if(tmp->parent) // when inserting nodes at the head, there is no parent
+ tmp->parent->last_child=tmp;
+ }
+ else {
+ tmp->next_sibling->prev_sibling=tmp;
+ }
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::insert_subtree(iter position, const
iterator_base& subtree)
+ {
+ // insert dummy
+ iter it=insert(position, value_type());
+ // replace dummy with subtree
+ return replace(it, subtree);
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const
iterator_base& subtree)
+ {
+ // insert dummy
+ iter it=insert_after(position, value_type());
+ // replace dummy with subtree
+ return replace(it, subtree);
+ }
+
+// template <class T, class tree_node_allocator>
+// template <class iter>
+// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator
position, iter subtree)
+// {
+// // insert dummy
+// iter it(insert(position, value_type()));
+// // replace dummy with subtree
+// return replace(it, subtree);
+// }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
+ {
+ kp::destructor(&position.node->data);
+ kp::constructor(&position.node->data, x);
+ return position;
+ }
+
+template <class T, class tree_node_allocator>
+template <class iter>
+iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base&
from)
+ {
+ assert(position.node!=head);
+ tree_node *current_from=from.node;
+ tree_node *start_from=from.node;
+ tree_node *current_to =position.node;
+
+ // replace the node at position with head of the replacement tree at from
+// std::cout << "warning!" << position.node << std::endl;
+ erase_children(position);
+// std::cout << "no warning!" << std::endl;
+ tree_node* tmp = alloc_.allocate(1,0);
+ kp::constructor(&tmp->data, (*from));
+ tmp->first_child=0;
+ tmp->last_child=0;
+ if(current_to->prev_sibling==0) {
+ if(current_to->parent!=0)
+ current_to->parent->first_child=tmp;
+ }
+ else {
+ current_to->prev_sibling->next_sibling=tmp;
+ }
+ tmp->prev_sibling=current_to->prev_sibling;
+ if(current_to->next_sibling==0) {
+ if(current_to->parent!=0)
+ current_to->parent->last_child=tmp;
+ }
+ else {
+ current_to->next_sibling->prev_sibling=tmp;
+ }
+ tmp->next_sibling=current_to->next_sibling;
+ tmp->parent=current_to->parent;
+ kp::destructor(¤t_to->data);
+ alloc_.deallocate(current_to,1);
+ current_to=tmp;
+
+ // only at this stage can we fix 'last'
+ tree_node *last=from.node->next_sibling;
+
+ pre_order_iterator toit=tmp;
+ // copy all children
+ do {
+ assert(current_from!=0);
+ if(current_from->first_child != 0) {
+ current_from=current_from->first_child;
+ toit=append_child(toit, current_from->data);
+ }
+ else {
+ while(current_from->next_sibling==0 && current_from!=start_from) {
+ current_from=current_from->parent;
+ toit=parent(toit);
+ assert(current_from!=0);
+ }
+ current_from=current_from->next_sibling;
+ if(current_from!=last) {
+ toit=append_child(parent(toit), current_from->data);
+ }
+ }
+ } while(current_from!=last);
+
+ return current_to;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::replace(
+ sibling_iterator orig_begin,
+ sibling_iterator orig_end,
+ sibling_iterator new_begin,
+ sibling_iterator new_end)
+ {
+ tree_node *orig_first=orig_begin.node;
+ tree_node *new_first=new_begin.node;
+ tree_node *orig_last=orig_first;
+ while((++orig_begin)!=orig_end)
+ orig_last=orig_last->next_sibling;
+ tree_node *new_last=new_first;
+ while((++new_begin)!=new_end)
+ new_last=new_last->next_sibling;
+
+ // insert all siblings in new_first..new_last before orig_first
+ bool first=true;
+ pre_order_iterator ret;
+ while(1==1) {
+ pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first),
pre_order_iterator(new_first));
+ if(first) {
+ ret=tt;
+ first=false;
+ }
+ if(new_first==new_last)
+ break;
+ new_first=new_first->next_sibling;
+ }
+
+ // erase old range of siblings
+ bool last=false;
+ tree_node *next=orig_first;
+ while(1==1) {
+ if(next==orig_last)
+ last=true;
+ next=next->next_sibling;
+ erase((pre_order_iterator)orig_first);
+ if(last)
+ break;
+ orig_first=next;
+ }
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::flatten(iter position)
+ {
+ if(position.node->first_child==0)
+ return position;
+
+ tree_node *tmp=position.node->first_child;
+ while(tmp) {
+ tmp->parent=position.node->parent;
+ tmp=tmp->next_sibling;
+ }
+ if(position.node->next_sibling) {
+ position.node->last_child->next_sibling=position.node->next_sibling;
+ position.node->next_sibling->prev_sibling=position.node->last_child;
+ }
+ else {
+ position.node->parent->last_child=position.node->last_child;
+ }
+ position.node->next_sibling=position.node->first_child;
+ position.node->next_sibling->prev_sibling=position.node;
+ position.node->first_child=0;
+ position.node->last_child=0;
+
+ return position;
+ }
+
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator
begin, sibling_iterator end)
+ {
+ tree_node *first=begin.node;
+ tree_node *last=first;
+
+ assert(first!=position.node);
+
+ if(begin==end) return begin;
+ // determine last node
+ while((++begin)!=end) {
+ last=last->next_sibling;
+ }
+ // move subtree
+ if(first->prev_sibling==0) {
+ first->parent->first_child=last->next_sibling;
+ }
+ else {
+ first->prev_sibling->next_sibling=last->next_sibling;
+ }
+ if(last->next_sibling==0) {
+ last->parent->last_child=first->prev_sibling;
+ }
+ else {
+ last->next_sibling->prev_sibling=first->prev_sibling;
+ }
+ if(position.node->first_child==0) {
+ position.node->first_child=first;
+ position.node->last_child=last;
+ first->prev_sibling=0;
+ }
+ else {
+ position.node->last_child->next_sibling=first;
+ first->prev_sibling=position.node->last_child;
+ position.node->last_child=last;
+ }
+ last->next_sibling=0;
+
+ tree_node *pos=first;
+ while(1==1) {
+ pos->parent=position.node;
+ if(pos==last) break;
+ pos=pos->next_sibling;
+ }
+
+ return first;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter
position, iter from)
+ {
+ if(from.node->first_child==0) return position;
+ return reparent(position, from.node->first_child, end(from));
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter
position, const T& x)
+ {
+ assert(position.node!=0);
+ sibling_iterator fr=position, to=position;
+ ++to;
+ iter ret = insert(position, x);
+ reparent(ret, fr, to);
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter
target, iter source)
+ {
+ tree_node *dst=target.node;
+ tree_node *src=source.node;
+ assert(dst);
+ assert(src);
+
+ if(dst==src) return source;
+ if(dst->next_sibling)
+ if(dst->next_sibling==src) // already in the right spot
+ return source;
+
+ // take src out of the tree
+ if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
+ else src->parent->first_child=src->next_sibling;
+ if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
+ else src->parent->last_child=src->prev_sibling;
+
+ // connect it to the new point
+ if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
+ else dst->parent->last_child=src;
+ src->next_sibling=dst->next_sibling;
+ dst->next_sibling=src;
+ src->prev_sibling=dst;
+ src->parent=dst->parent;
+ return src;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter
target, iter source)
+ {
+ tree_node *dst=target.node;
+ tree_node *src=source.node;
+ assert(dst);
+ assert(src);
+
+ if(dst==src) return source;
+ if(dst->prev_sibling)
+ if(dst->prev_sibling==src) // already in the right spot
+ return source;
+
+ // take src out of the tree
+ if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
+ else src->parent->first_child=src->next_sibling;
+ if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
+ else src->parent->last_child=src->prev_sibling;
+
+ // connect it to the new point
+ if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
+ else dst->parent->first_child=src;
+ src->prev_sibling=dst->prev_sibling;
+ dst->prev_sibling=src;
+ src->next_sibling=dst;
+ src->parent=dst->parent;
+ return src;
+ }
+
+// specialisation for sibling_iterators
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::move_before(sibling_iterator target,
+
sibling_iterator source)
+ {
+ tree_node *dst=target.node;
+ tree_node *src=source.node;
+ tree_node *dst_prev_sibling;
+ if(dst==0) { // must then be an end iterator
+ dst_prev_sibling=target.parent_->last_child;
+ assert(dst_prev_sibling);
+ }
+ else dst_prev_sibling=dst->prev_sibling;
+ assert(src);
+
+ if(dst==src) return source;
+ if(dst_prev_sibling)
+ if(dst_prev_sibling==src) // already in the right spot
+ return source;
+
+ // take src out of the tree
+ if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
+ else src->parent->first_child=src->next_sibling;
+ if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
+ else src->parent->last_child=src->prev_sibling;
+
+ // connect it to the new point
+ if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
+ else target.parent_->first_child=src;
+ src->prev_sibling=dst_prev_sibling;
+ if(dst) {
+ dst->prev_sibling=src;
+ src->parent=dst->parent;
+ }
+ src->next_sibling=dst;
+ return src;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter
target, iter source)
+ {
+ tree_node *dst=target.node;
+ tree_node *src=source.node;
+ assert(dst);
+ assert(src);
+
+ if(dst==src) return source;
+
+ // remember connection points
+ tree_node *b_prev_sibling=dst->prev_sibling;
+ tree_node *b_next_sibling=dst->next_sibling;
+ tree_node *b_parent=dst->parent;
+
+ // remove target
+ erase(target);
+
+ // take src out of the tree
+ if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
+ else src->parent->first_child=src->next_sibling;
+ if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
+ else src->parent->last_child=src->prev_sibling;
+
+ // connect it to the new point
+ if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
+ else b_parent->first_child=src;
+ if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
+ else b_parent->last_child=src;
+ src->prev_sibling=b_prev_sibling;
+ src->next_sibling=b_next_sibling;
+ src->parent=b_parent;
+ return src;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::merge(sibling_iterator to1,
sibling_iterator to2,
+ sibling_iterator from1,
sibling_iterator from2,
+ bool duplicate_leaves)
+ {
+ sibling_iterator fnd;
+ while(from1!=from2) {
+ if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
+ if(from1.begin()==from1.end()) { // full depth reached
+ if(duplicate_leaves)
+ append_child(parent(to1), (*from1));
+ }
+ else { // descend further
+ merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(),
duplicate_leaves);
+ }
+ }
+ else { // element missing
+ insert_subtree(to2, from1);
+ }
+ ++from1;
+ }
+ }
+
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::sort(sibling_iterator from,
sibling_iterator to, bool deep)
+ {
+ std::less<T> comp;
+ sort(from, to, comp, deep);
+ }
+
+template <class T, class tree_node_allocator>
+template <class StrictWeakOrdering>
+void tree<T, tree_node_allocator>::sort(sibling_iterator from,
sibling_iterator to,
+ StrictWeakOrdering comp, bool deep)
+ {
+ if(from==to) return;
+ // make list of sorted nodes
+ // CHECK: if multiset stores equivalent nodes in the order in which they
+ // are inserted, then this routine should be called 'stable_sort'.
+ std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
+ sibling_iterator it=from, it2=to;
+ while(it != to) {
+ nodes.insert(it.node);
+ ++it;
+ }
+ // reassemble
+ --it2;
+
+ // prev and next are the nodes before and after the sorted range
+ tree_node *prev=from.node->prev_sibling;
+ tree_node *next=it2.node->next_sibling;
+ typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering>
>::iterator nit=nodes.begin(), eit=nodes.end();
+ if(prev==0) {
+ if((*nit)->parent!=0) // to catch "sorting the head" situations, when
there is no parent
+ (*nit)->parent->first_child=(*nit);
+ }
+ else prev->next_sibling=(*nit);
+
+ --eit;
+ while(nit!=eit) {
+ (*nit)->prev_sibling=prev;
+ if(prev)
+ prev->next_sibling=(*nit);
+ prev=(*nit);
+ ++nit;
+ }
+ // prev now points to the last-but-one node in the sorted range
+ if(prev)
+ prev->next_sibling=(*eit);
+
+ // eit points to the last node in the sorted range.
+ (*eit)->next_sibling=next;
+ (*eit)->prev_sibling=prev; // missed in the loop above
+ if(next==0) {
+ if((*eit)->parent!=0) // to catch "sorting the head" situations, when
there is no parent
+ (*eit)->parent->last_child=(*eit);
+ }
+ else next->prev_sibling=(*eit);
+
+ if(deep) { // sort the children of each node too
+ sibling_iterator bcs(*nodes.begin());
+ sibling_iterator ecs(*eit);
+ ++ecs;
+ while(bcs!=ecs) {
+ sort(begin(bcs), end(bcs), comp, deep);
+ ++bcs;
+ }
+ }
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two,
const iter& three_) const
+ {
+ std::equal_to<T> comp;
+ return equal(one_, two, three_, comp);
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter>
+bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter&
two_) const
+ {
+ std::equal_to<T> comp;
+ return equal_subtree(one_, two_, comp);
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter, class BinaryPredicate>
+bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two,
const iter& three_, BinaryPredicate fun) const
+ {
+ pre_order_iterator one(one_), three(three_);
+
+// if(one==two && is_valid(three) && three.number_of_children()!=0)
+// return false;
+ while(one!=two && is_valid(three)) {
+ if(!fun(*one,*three))
+ return false;
+ if(one.number_of_children()!=three.number_of_children())
+ return false;
+ ++one;
+ ++three;
+ }
+ return true;
+ }
+
+template <class T, class tree_node_allocator>
+template <typename iter, class BinaryPredicate>
+bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter&
two_, BinaryPredicate fun) const
+ {
+ pre_order_iterator one(one_), two(two_);
+
+ if(!fun(*one,*two)) return false;
+ if(number_of_children(one)!=number_of_children(two)) return false;
+ return equal(begin(one),end(one),begin(two),fun);
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator> tree<T,
tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
+ {
+ tree tmp;
+ tmp.set_head(value_type());
+ tmp.replace(tmp.begin(), tmp.end(), from, to);
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from,
sibling_iterator to) const
+ {
+ tmp.set_head(value_type());
+ tmp.replace(tmp.begin(), tmp.end(), from, to);
+ }
+
+template <class T, class tree_node_allocator>
+int tree<T, tree_node_allocator>::size() const
+ {
+ int i=0;
+ pre_order_iterator it=begin(), eit=end();
+ while(it!=eit) {
+ ++i;
+ ++it;
+ }
+ return i;
+ }
+
+template <class T, class tree_node_allocator>
+int tree<T, tree_node_allocator>::size(const iterator_base& top) const
+ {
+ int i=0;
+ pre_order_iterator it=top, eit=top;
+ eit.skip_children();
+ ++eit;
+ while(it!=eit) {
+ ++i;
+ ++it;
+ }
+ return i;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::empty() const
+ {
+ pre_order_iterator it=begin(), eit=end();
+ return (it==eit);
+ }
+
+template <class T, class tree_node_allocator>
+int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
+ {
+ tree_node* pos=it.node;
+ assert(pos!=0);
+ int ret=0;
+ while(pos->parent!=0) {
+ pos=pos->parent;
+ ++ret;
+ }
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+unsigned int tree<T, tree_node_allocator>::number_of_children(const
iterator_base& it)
+ {
+ tree_node *pos=it.node->first_child;
+ if(pos==0) return 0;
+
+ unsigned int ret=1;
+// while(pos!=it.node->last_child) {
+// ++ret;
+// pos=pos->next_sibling;
+// }
+ while((pos=pos->next_sibling))
+ ++ret;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+unsigned int tree<T, tree_node_allocator>::number_of_siblings(const
iterator_base& it) const
+ {
+ tree_node *pos=it.node;
+ unsigned int ret=0;
+ // count forward
+ while(pos->next_sibling &&
+ pos->next_sibling!=head &&
+ pos->next_sibling!=feet) {
+ ++ret;
+ pos=pos->next_sibling;
+ }
+ // count backward
+ pos=it.node;
+ while(pos->prev_sibling &&
+ pos->prev_sibling!=head &&
+ pos->prev_sibling!=feet) {
+ ++ret;
+ pos=pos->prev_sibling;
+ }
+
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::swap(sibling_iterator it)
+ {
+ tree_node *nxt=it.node->next_sibling;
+ if(nxt) {
+ if(it.node->prev_sibling)
+ it.node->prev_sibling->next_sibling=nxt;
+ else
+ it.node->parent->first_child=nxt;
+ nxt->prev_sibling=it.node->prev_sibling;
+ tree_node *nxtnxt=nxt->next_sibling;
+ if(nxtnxt)
+ nxtnxt->prev_sibling=it.node;
+ else
+ it.node->parent->last_child=it.node;
+ nxt->next_sibling=it.node;
+ it.node->prev_sibling=nxt;
+ it.node->next_sibling=nxtnxt;
+ }
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
+ {
+ // if one and two are adjacent siblings, use the sibling swap
+ if(one.node->next_sibling==two.node) swap(one);
+ else if(two.node->next_sibling==one.node) swap(two);
+ else {
+ tree_node *nxt1=one.node->next_sibling;
+ tree_node *nxt2=two.node->next_sibling;
+ tree_node *pre1=one.node->prev_sibling;
+ tree_node *pre2=two.node->prev_sibling;
+ tree_node *par1=one.node->parent;
+ tree_node *par2=two.node->parent;
+
+ // reconnect
+ one.node->parent=par2;
+ one.node->next_sibling=nxt2;
+ if(nxt2) nxt2->prev_sibling=one.node;
+ else par2->last_child=one.node;
+ one.node->prev_sibling=pre2;
+ if(pre2) pre2->next_sibling=one.node;
+ else par2->first_child=one.node;
+
+ two.node->parent=par1;
+ two.node->next_sibling=nxt1;
+ if(nxt1) nxt1->prev_sibling=two.node;
+ else par1->last_child=two.node;
+ two.node->prev_sibling=pre1;
+ if(pre1) pre1->next_sibling=two.node;
+ else par1->first_child=two.node;
+ }
+ }
+
+// template <class BinaryPredicate>
+// tree<T, tree_node_allocator>::iterator tree<T,
tree_node_allocator>::find_subtree(
+// sibling_iterator subfrom, sibling_iterator subto, iterator from,
iterator to,
+// BinaryPredicate fun) const
+// {
+// assert(1==0); // this routine is not finished yet.
+// while(from!=to) {
+// if(fun(*subfrom, *from)) {
+//
+// }
+// }
+// return to;
+// }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it,
const iterator_base& begin,
+ const iterator_base& end)
const
+ {
+ // FIXME: this should be optimised.
+ pre_order_iterator tmp=begin;
+ while(tmp!=end) {
+ if(tmp==it) return true;
+ ++tmp;
+ }
+ return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
+ {
+ if(it.node==0 || it.node==feet || it.node==head) return false;
+ else return true;
+ }
+
+template <class T, class tree_node_allocator>
+unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
+ {
+ unsigned int ind=0;
+ if(it.node->parent==0) {
+ while(it.node->prev_sibling!=head) {
+ it.node=it.node->prev_sibling;
+ ++ind;
+ }
+ }
+ else {
+ while(it.node->prev_sibling!=0) {
+ it.node=it.node->prev_sibling;
+ ++ind;
+ }
+ }
+ return ind;
+ }
+
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
+ {
+ tree_node *tmp=it.node->first_child;
+ while(num--) {
+ assert(tmp!=0);
+ tmp=tmp->next_sibling;
+ }
+ return tmp;
+ }
+
+
+
+
+// Iterator base
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::iterator_base::iterator_base()
+ : node(0), skip_current_children_(false)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
+ : node(tn), skip_current_children_(false)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+T& tree<T, tree_node_allocator>::iterator_base::operator*() const
+ {
+ return node->data;
+ }
+
+template <class T, class tree_node_allocator>
+T* tree<T, tree_node_allocator>::iterator_base::operator->() const
+ {
+ return &(node->data);
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const
post_order_iterator& other) const
+ {
+ if(other.node!=this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const
post_order_iterator& other) const
+ {
+ if(other.node==this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const
pre_order_iterator& other) const
+ {
+ if(other.node!=this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const
pre_order_iterator& other) const
+ {
+ if(other.node==this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const
sibling_iterator& other) const
+ {
+ if(other.node!=this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const
sibling_iterator& other) const
+ {
+ if(other.node==this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const
leaf_iterator& other) const
+ {
+ if(other.node!=this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const
leaf_iterator& other) const
+ {
+ if(other.node==this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::iterator_base::begin() const
+ {
+ if(node->first_child==0)
+ return end();
+
+ sibling_iterator ret(node->first_child);
+ ret.parent_=this->node;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::iterator_base::end() const
+ {
+ sibling_iterator ret(0);
+ ret.parent_=node;
+ return ret;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::iterator_base::skip_children()
+ {
+ skip_current_children_=true;
+ }
+
+template <class T, class tree_node_allocator>
+unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children()
const
+ {
+ tree_node *pos=node->first_child;
+ if(pos==0) return 0;
+
+ unsigned int ret=1;
+ while(pos!=node->last_child) {
+ ++ret;
+ pos=pos->next_sibling;
+ }
+ return ret;
+ }
+
+
+
+// Pre-order iterator
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
+ : iterator_base(0)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node
*tn)
+ : iterator_base(tn)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const
iterator_base &other)
+ : iterator_base(other.node)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const
sibling_iterator& other)
+ : iterator_base(other.node)
+ {
+ if(this->node==0) {
+ if(other.range_last()!=0)
+ this->node=other.range_last();
+ else
+ this->node=other.parent_;
+ this->skip_children();
+ ++(*this);
+ }
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator++()
+ {
+ assert(this->node!=0);
+ if(!this->skip_current_children_ && this->node->first_child != 0) {
+ this->node=this->node->first_child;
+ }
+ else {
+ this->skip_current_children_=false;
+ while(this->node->next_sibling==0) {
+ this->node=this->node->parent;
+ if(this->node==0)
+ return *this;
+ }
+ this->node=this->node->next_sibling;
+ }
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator--()
+ {
+ assert(this->node!=0);
+ if(this->node->prev_sibling) {
+ this->node=this->node->prev_sibling;
+ while(this->node->last_child)
+ this->node=this->node->last_child;
+ }
+ else {
+ this->node=this->node->parent;
+ if(this->node==0)
+ return *this;
+ }
+ return *this;
+}
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::pre_order_iterator::operator++(int n)
+ {
+ pre_order_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::pre_order_iterator::operator--(int n)
+{
+ pre_order_iterator copy = *this;
+ --(*this);
+ return copy;
+}
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
+ {
+ while(num>0) {
+ ++(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
+ {
+ while(num>0) {
+ --(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+
+
+// Post-order iterator
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
+ : iterator_base(0)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T,
tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
+ : iterator_base(tn)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const
iterator_base &other)
+ : iterator_base(other.node)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const
sibling_iterator& other)
+ : iterator_base(other.node)
+ {
+ if(this->node==0) {
+ if(other.range_last()!=0)
+ this->node=other.range_last();
+ else
+ this->node=other.parent_;
+ this->skip_children();
+ ++(*this);
+ }
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator++()
+ {
+ assert(this->node!=0);
+ if(this->node->next_sibling==0) {
+ this->node=this->node->parent;
+ this->skip_current_children_=false;
+ }
+ else {
+ this->node=this->node->next_sibling;
+ if(this->skip_current_children_) {
+ this->skip_current_children_=false;
+ }
+ else {
+ while(this->node->first_child)
+ this->node=this->node->first_child;
+ }
+ }
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator--()
+ {
+ assert(this->node!=0);
+ if(this->skip_current_children_ || this->node->last_child==0) {
+ this->skip_current_children_=false;
+ while(this->node->prev_sibling==0)
+ this->node=this->node->parent;
+ this->node=this->node->prev_sibling;
+ }
+ else {
+ this->node=this->node->last_child;
+ }
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::post_order_iterator::operator++(int)
+ {
+ post_order_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::post_order_iterator::operator--(int)
+ {
+ post_order_iterator copy = *this;
+ --(*this);
+ return copy;
+ }
+
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
+ {
+ while(num>0) {
+ ++(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
+ {
+ while(num>0) {
+ --(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
+ {
+ assert(this->node!=0);
+ while(this->node->first_child)
+ this->node=this->node->first_child;
+ }
+
+
+// Breadth-first iterator
+
+template <class T, class tree_node_allocator>
+tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
+ : iterator_base()
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node
*tn)
+ : iterator_base(tn)
+ {
+ traversal_queue.push(tn);
+ }
+
+template <class T, class tree_node_allocator>
+tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const
iterator_base& other)
+ : iterator_base(other.node)
+ {
+ traversal_queue.push(other.node);
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator!=(const
breadth_first_queued_iterator& other) const
+ {
+ if(other.node!=this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator==(const
breadth_first_queued_iterator& other) const
+ {
+ if(other.node==this->node) return true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator++()
+ {
+ assert(this->node!=0);
+
+ // Add child nodes and pop current node
+ sibling_iterator sib=this->begin();
+ while(sib!=this->end()) {
+ traversal_queue.push(sib.node);
+ ++sib;
+ }
+ traversal_queue.pop();
+ if(traversal_queue.size()>0)
+ this->node=traversal_queue.front();
+ else
+ this->node=0;
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator++(int n)
+ {
+ breadth_first_queued_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int
num)
+ {
+ while(num>0) {
+ ++(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+
+
+// Fixed depth iterator
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
+ : iterator_base()
+ {
+ set_first_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T,
tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
+ : iterator_base(tn)
+ {
+ set_first_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
iterator_base& other)
+ : iterator_base(other.node)
+ {
+ set_first_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
sibling_iterator& other)
+ : iterator_base(other.node), first_parent_(other.parent_)
+ {
+ find_leftmost_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
fixed_depth_iterator& other)
+ : iterator_base(other.node), first_parent_(other.first_parent_)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const
fixed_depth_iterator& other) const
+ {
+ if(other.node==this->node && other.first_parent_==first_parent_) return
true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const
fixed_depth_iterator& other) const
+ {
+ if(other.node!=this->node || other.first_parent_!=first_parent_) return
true;
+ else return false;
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
+ {
+ return; // FIXME: we do not use first_parent_ yet, and it actually needs
some serious reworking if
+ // it is ever to work at the 'head' level.
+ first_parent_=0;
+ if(this->node==0) return;
+ if(this->node->parent!=0)
+ first_parent_=this->node->parent;
+ if(first_parent_)
+ find_leftmost_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T,
tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
+ {
+ return; // FIXME: see 'set_first_parent()'
+ tree_node *tmppar=first_parent_;
+ while(tmppar->prev_sibling) {
+ tmppar=tmppar->prev_sibling;
+ if(tmppar->first_child)
+ first_parent_=tmppar;
+ }
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator++()
+ {
+ assert(this->node!=0);
+
+ if(this->node->next_sibling) {
+ this->node=this->node->next_sibling;
+ }
+ else {
+ int relative_depth=0;
+ upper:
+ do {
+ this->node=this->node->parent;
+ if(this->node==0) return *this;
+ --relative_depth;
+ } while(this->node->next_sibling==0);
+ lower:
+ this->node=this->node->next_sibling;
+ while(this->node->first_child==0) {
+ if(this->node->next_sibling==0)
+ goto upper;
+ this->node=this->node->next_sibling;
+ if(this->node==0) return *this;
+ }
+ while(relative_depth<0 && this->node->first_child!=0) {
+ this->node=this->node->first_child;
+ ++relative_depth;
+ }
+ if(relative_depth<0) {
+ if(this->node->next_sibling==0) goto upper;
+ else goto lower;
+ }
+ }
+ return *this;
+
+// if(this->node->next_sibling!=0) {
+// this->node=this->node->next_sibling;
+// assert(this->node!=0);
+// if(this->node->parent==0 && this->node->next_sibling==0) // feet element
+// this->node=0;
+// }
+// else {
+// tree_node *par=this->node->parent;
+// do {
+// par=par->next_sibling;
+// if(par==0) { // FIXME: need to keep track of this!
+// this->node=0;
+// return *this;
+// }
+// } while(par->first_child==0);
+// this->node=par->first_child;
+// }
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator--()
+ {
+ assert(this->node!=0);
+ if(this->node->prev_sibling!=0) {
+ this->node=this->node->prev_sibling;
+ assert(this->node!=0);
+ if(this->node->parent==0 && this->node->prev_sibling==0) // head element
+ this->node=0;
+ }
+ else {
+ tree_node *par=this->node->parent;
+ do {
+ par=par->prev_sibling;
+ if(par==0) { // FIXME: need to keep track of this!
+ this->node=0;
+ return *this;
+ }
+ } while(par->last_child==0);
+ this->node=par->last_child;
+ }
+ return *this;
+}
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::fixed_depth_iterator::operator++(int)
+ {
+ fixed_depth_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::fixed_depth_iterator::operator--(int)
+{
+ fixed_depth_iterator copy = *this;
+ --(*this);
+ return copy;
+}
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
+ {
+ while(num>0) {
+ --(*this);
+ --(num);
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
+ {
+ while(num>0) {
+ ++(*this);
+ --(num);
+ }
+ return *this;
+ }
+
+// FIXME: add the other members of fixed_depth_iterator.
+
+
+// Sibling iterator
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
+ : iterator_base()
+ {
+ set_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
+ : iterator_base(tn)
+ {
+ set_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const
iterator_base& other)
+ : iterator_base(other.node)
+ {
+ set_parent_();
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const
sibling_iterator& other)
+ : iterator_base(other), parent_(other.parent_)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
+ {
+ parent_=0;
+ if(this->node==0) return;
+ if(this->node->parent!=0)
+ parent_=this->node->parent;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator++()
+ {
+ if(this->node)
+ this->node=this->node->next_sibling;
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator--()
+ {
+ if(this->node) this->node=this->node->prev_sibling;
+ else {
+ assert(parent_);
+ this->node=parent_->last_child;
+ }
+ return *this;
+}
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::sibling_iterator::operator++(int)
+ {
+ sibling_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::sibling_iterator::operator--(int)
+ {
+ sibling_iterator copy = *this;
+ --(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
+ {
+ while(num>0) {
+ ++(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
+ {
+ while(num>0) {
+ --(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::tree_node *tree<T,
tree_node_allocator>::sibling_iterator::range_first() const
+ {
+ tree_node *tmp=parent_->first_child;
+ return tmp;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::tree_node *tree<T,
tree_node_allocator>::sibling_iterator::range_last() const
+ {
+ return parent_->last_child;
+ }
+
+// Leaf iterator
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
+ : iterator_base(0)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn)
+ : iterator_base(tn)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base
&other)
+ : iterator_base(other.node)
+ {
+ }
+
+template <class T, class tree_node_allocator>
+tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const
sibling_iterator& other)
+ : iterator_base(other.node)
+ {
+ if(this->node==0) {
+ if(other.range_last()!=0)
+ this->node=other.range_last();
+ else
+ this->node=other.parent_;
+ ++(*this);
+ }
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator++()
+ {
+ assert(this->node!=0);
+ while(this->node->next_sibling==0) {
+ if (this->node->parent==0) return *this;
+ this->node=this->node->parent;
+ }
+ this->node=this->node->next_sibling;
+ while(this->node->first_child)
+ this->node=this->node->first_child;
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator--()
+ {
+ assert(this->node!=0);
+ while (this->node->prev_sibling==0) {
+ if (this->node->parent==0) return *this;
+ this->node=this->node->parent;
+ }
+ this->node=this->node->prev_sibling;
+ while(this->node->last_child)
+ this->node=this->node->last_child;
+ return *this;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::leaf_iterator::operator++(int)
+ {
+ leaf_iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::leaf_iterator::operator--(int)
+ {
+ leaf_iterator copy = *this;
+ --(*this);
+ return copy;
+ }
+
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
+ {
+ while(num>0) {
+ ++(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+template <class T, class tree_node_allocator>
+typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
+ {
+ while(num>0) {
+ --(*this);
+ --num;
+ }
+ return (*this);
+ }
+
+#endif
+
+// Local variables:
+// default-tab-width: 3
+// End:
Index: libbase/tree.hpp
===================================================================
RCS file: libbase/tree.hpp
diff -N libbase/tree.hpp
--- libbase/tree.hpp 24 Aug 2007 03:10:56 -0000 1.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,2620 +0,0 @@
-/*
-
- $Id: tree.hpp,v 1.1 2007/08/24 03:10:56 nihilus Exp $
-
- STL-like templated tree class.
- Copyright (C) 2001-2006 Kasper Peeters <address@hidden>.
-
-*/
-
-/** \mainpage tree.hh
- \author Kasper Peeters
- \version 2.31
- \date 21-Aug-2007
- \see http://www.aei.mpg.de/~peekas/tree/
- \see http://www.aei.mpg.de/~peekas/tree/ChangeLog
-
- The tree.hh library for C++ provides an STL-like container class
- for n-ary trees, templated over the data stored at the
- nodes. Various types of iterators are provided (post-order,
- pre-order, and others). Where possible the access methods are
- compatible with the STL or alternative algorithms are
- available.
-*/
-
-
-/*
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; version 2 or 3.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-*/
-
-/** \todo
- - New-style move members are not completely finished yet.
- - It would be good to have an iterator which can iterate over all
- nodes below a given node.
- - Fixed depth iterators do not iterate over the entire range if there
- are 'holes' in the tree.
- - If a range uses const iter_base& as end iterator, things will
- inevitably go wrong, because upcast from iter_base to a non-sibling_iter
- is incorrect. This upcast should be removed (and then all illegal uses
- as previously in 'equal' will be flagged by the compiler). This requires
- new copy constructors though.
- - There's a bug in replace(sibling_iterator, ...) when the ranges
- sit next to each other. Turned up in append_child(iter,iter)
- but has been avoided now.
- - "std::operator<" does not work correctly on our iterators, and for some
- reason a globally defined template operator< did not get picked up.
- Using a comparison class now, but this should be investigated.
-*/
-
-#ifndef tree_hh_
-#define tree_hh_
-
-#include <cassert>
-#include <memory>
-#include <stdexcept>
-#include <iterator>
-#include <set>
-#include <queue>
-#include <iostream>
-
-// HP-style construct/destroy have gone from the standard,
-// so here is a copy.
-
-namespace kp {
-
-template <class T1, class T2>
-void constructor(T1* p, T2& val)
- {
- new ((void *) p) T1(val);
- }
-
-template <class T1>
-void constructor(T1* p)
- {
- new ((void *) p) T1;
- }
-
-template <class T1>
-void destructor(T1* p)
- {
- p->~T1();
- }
-
-};
-
-/// A node in the tree, combining links to other nodes as well as the actual
data.
-template<class T>
-class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
- public:
- tree_node_<T> *parent;
- tree_node_<T> *first_child, *last_child;
- tree_node_<T> *prev_sibling, *next_sibling;
- T data;
-}; // __attribute__((packed));
-
-template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
-class tree {
- protected:
- typedef tree_node_<T> tree_node;
- public:
- /// Value of the data stored at a node.
- typedef T value_type;
-
- class iterator_base;
- class pre_order_iterator;
- class post_order_iterator;
- class sibling_iterator;
- class leaf_iterator;
-
- tree();
- tree(const T&);
- tree(const iterator_base&);
- tree(const tree<T, tree_node_allocator>&);
- ~tree();
- void operator=(const tree<T, tree_node_allocator>&);
-
- /// Base class for iterators, only pointers stored, no traversal logic.
-#ifdef __SGI_STL_PORT
- class iterator_base : public stlport::bidirectional_iterator<T,
ptrdiff_t> {
-#else
- class iterator_base {
-#endif
- public:
- typedef T value_type;
- typedef T* pointer;
- typedef T& reference;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
- typedef std::bidirectional_iterator_tag iterator_category;
-
- iterator_base();
- iterator_base(tree_node *);
-
- T& operator*() const;
- T* operator->() const;
-
- /// When called, the next increment/decrement skips children of
this node.
- void skip_children();
- /// Number of children of the node pointed to by the iterator.
- unsigned int number_of_children() const;
-
- sibling_iterator begin() const;
- sibling_iterator end() const;
-
- tree_node *node;
- protected:
- bool skip_current_children_;
- };
-
- /// Depth-first iterator, first accessing the node, then its children.
- class pre_order_iterator : public iterator_base {
- public:
- pre_order_iterator();
- pre_order_iterator(tree_node *);
- pre_order_iterator(const iterator_base&);
- pre_order_iterator(const sibling_iterator&);
-
- bool operator==(const pre_order_iterator&) const;
- bool operator!=(const pre_order_iterator&) const;
- pre_order_iterator& operator++();
- pre_order_iterator& operator--();
- pre_order_iterator operator++(int);
- pre_order_iterator operator--(int);
- pre_order_iterator& operator+=(unsigned int);
- pre_order_iterator& operator-=(unsigned int);
- };
-
- /// Depth-first iterator, first accessing the children, then the node
itself.
- class post_order_iterator : public iterator_base {
- public:
- post_order_iterator();
- post_order_iterator(tree_node *);
- post_order_iterator(const iterator_base&);
- post_order_iterator(const sibling_iterator&);
-
- bool operator==(const post_order_iterator&) const;
- bool operator!=(const post_order_iterator&) const;
- post_order_iterator& operator++();
- post_order_iterator& operator--();
- post_order_iterator operator++(int);
- post_order_iterator operator--(int);
- post_order_iterator& operator+=(unsigned int);
- post_order_iterator& operator-=(unsigned int);
-
- /// Set iterator to the first child as deep as possible down the
tree.
- void descend_all();
- };
-
- /// Breadth-first iterator, using a queue
- class breadth_first_queued_iterator : public iterator_base {
- public:
- breadth_first_queued_iterator();
- breadth_first_queued_iterator(tree_node *);
- breadth_first_queued_iterator(const iterator_base&);
-
- bool operator==(const breadth_first_queued_iterator&) const;
- bool operator!=(const breadth_first_queued_iterator&) const;
- breadth_first_queued_iterator& operator++();
- breadth_first_queued_iterator operator++(int);
- breadth_first_queued_iterator& operator+=(unsigned int);
-
- private:
- std::queue<tree_node *> traversal_queue;
- };
-
- /// The default iterator types throughout the tree class.
- typedef pre_order_iterator iterator;
- typedef breadth_first_queued_iterator breadth_first_iterator;
-
- /// Iterator which traverses only the nodes at a given depth from the
root.
- class fixed_depth_iterator : public iterator_base {
- public:
- fixed_depth_iterator();
- fixed_depth_iterator(tree_node *);
- fixed_depth_iterator(const iterator_base&);
- fixed_depth_iterator(const sibling_iterator&);
- fixed_depth_iterator(const fixed_depth_iterator&);
-
- bool operator==(const fixed_depth_iterator&) const;
- bool operator!=(const fixed_depth_iterator&) const;
- fixed_depth_iterator& operator++();
- fixed_depth_iterator& operator--();
- fixed_depth_iterator operator++(int);
- fixed_depth_iterator operator--(int);
- fixed_depth_iterator& operator+=(unsigned int);
- fixed_depth_iterator& operator-=(unsigned int);
-
- tree_node *first_parent_;
- private:
- void set_first_parent_();
- void find_leftmost_parent_();
- };
-
- /// Iterator which traverses only the nodes which are siblings of each
other.
- class sibling_iterator : public iterator_base {
- public:
- sibling_iterator();
- sibling_iterator(tree_node *);
- sibling_iterator(const sibling_iterator&);
- sibling_iterator(const iterator_base&);
-
- bool operator==(const sibling_iterator&) const;
- bool operator!=(const sibling_iterator&) const;
- sibling_iterator& operator++();
- sibling_iterator& operator--();
- sibling_iterator operator++(int);
- sibling_iterator operator--(int);
- sibling_iterator& operator+=(unsigned int);
- sibling_iterator& operator-=(unsigned int);
-
- tree_node *range_first() const;
- tree_node *range_last() const;
- tree_node *parent_;
- private:
- void set_parent_();
- };
-
- /// Iterator which traverses only the leaves.
- class leaf_iterator : public iterator_base {
- public:
- leaf_iterator();
- leaf_iterator(tree_node *);
- leaf_iterator(const sibling_iterator&);
- leaf_iterator(const iterator_base&);
-
- bool operator==(const leaf_iterator&) const;
- bool operator!=(const leaf_iterator&) const;
- leaf_iterator& operator++();
- leaf_iterator& operator--();
- leaf_iterator operator++(int);
- leaf_iterator operator--(int);
- leaf_iterator& operator+=(unsigned int);
- leaf_iterator& operator-=(unsigned int);
- };
-
- /// Return iterator to the beginning of the tree.
- inline pre_order_iterator begin() const;
- /// Return iterator to the end of the tree.
- inline pre_order_iterator end() const;
- /// Return post-order iterator to the beginning of the tree.
- post_order_iterator begin_post() const;
- /// Return post-order iterator to the end of the tree.
- post_order_iterator end_post() const;
- /// Return fixed-depth iterator to the first node at a given depth.
- fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int)
const;
- /// Return fixed-depth iterator to end of the nodes at given depth.
- fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
- /// Return breadth-first iterator to the first node at a given depth.
- breadth_first_queued_iterator begin_breadth_first() const;
- /// Return breadth-first iterator to end of the nodes at given depth.
- breadth_first_queued_iterator end_breadth_first() const;
- /// Return sibling iterator to the first child of given node.
- sibling_iterator begin(const iterator_base&) const;
- /// Return sibling iterator to the end of the children of a given node.
- sibling_iterator end(const iterator_base&) const;
- /// Return leaf iterator to the first leaf of the tree.
- leaf_iterator begin_leaf() const;
- /// Return leaf iterator to the last leaf of the tree.
- leaf_iterator end_leaf() const;
-
- /// Return iterator to the parent of a node.
- template<typename iter> static iter parent(iter);
- /// Return iterator to the previous sibling of a node.
- template<typename iter> iter previous_sibling(iter) const;
- /// Return iterator to the next sibling of a node.
- template<typename iter> iter next_sibling(iter) const;
- /// Return iterator to the next node at a given depth.
- template<typename iter> iter next_at_same_depth(iter) const;
-
- /// Erase all nodes of the tree.
- void clear();
- /// Erase element at position pointed to by iterator, return incremented
iterator.
- template<typename iter> iter erase(iter);
- /// Erase all children of the node pointed to by iterator.
- void erase_children(const iterator_base&);
-
- /// Insert empty node as last/first child of node pointed to by position.
- template<typename iter> iter append_child(iter position);
- template<typename iter> iter prepend_child(iter position);
- /// Insert node as last/first child of node pointed to by position.
- template<typename iter> iter append_child(iter position, const T& x);
- template<typename iter> iter prepend_child(iter position, const T& x);
- /// Append the node (plus its children) at other_position as last/first
child of position.
- template<typename iter> iter append_child(iter position, iter
other_position);
- template<typename iter> iter prepend_child(iter position, iter
other_position);
- /// Append the nodes in the from-to range (plus their children) as
last/first children of position.
- template<typename iter> iter append_children(iter position,
sibling_iterator from, sibling_iterator to);
- template<typename iter> iter prepend_children(iter position,
sibling_iterator from, sibling_iterator to);
-
- /// Short-hand to insert topmost node in otherwise empty tree.
- pre_order_iterator set_head(const T& x);
- /// Insert node as previous sibling of node pointed to by position.
- template<typename iter> iter insert(iter position, const T& x);
- /// Specialisation of previous member.
- sibling_iterator insert(sibling_iterator position, const T& x);
- /// Insert node (with children) pointed to by subtree as previous
sibling of node pointed to by position.
- template<typename iter> iter insert_subtree(iter position, const
iterator_base& subtree);
- /// Insert node as next sibling of node pointed to by position.
- template<typename iter> iter insert_after(iter position, const T& x);
- /// Insert node (with children) pointed to by subtree as next sibling of
node pointed to by position.
- template<typename iter> iter insert_subtree_after(iter position, const
iterator_base& subtree);
-
- /// Replace node at 'position' with other node (keeping same children);
'position' becomes invalid.
- template<typename iter> iter replace(iter position, const T& x);
- /// Replace node at 'position' with subtree starting at 'from' (do not
erase subtree at 'from'); see above.
- template<typename iter> iter replace(iter position, const iterator_base&
from);
- /// Replace string of siblings (plus their children) with copy of a new
string (with children); see above
- sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator
orig_end,
- sibling_iterator new_begin, sibling_iterator
new_end);
-
- /// Move all children of node at 'position' to be siblings, returns
position.
- template<typename iter> iter flatten(iter position);
- /// Move nodes in range to be children of 'position'.
- template<typename iter> iter reparent(iter position, sibling_iterator
begin, sibling_iterator end);
- /// Move all child nodes of 'from' to be children of 'position'.
- template<typename iter> iter reparent(iter position, iter from);
-
- /// Replace node with a new node, making the old node a child of the new
node.
- template<typename iter> iter wrap(iter position, const T& x);
-
- /// Move 'source' node (plus its children) to become the next sibling of
'target'.
- template<typename iter> iter move_after(iter target, iter source);
- /// Move 'source' node (plus its children) to become the previous
sibling of 'target'.
- template<typename iter> iter move_before(iter target, iter source);
- sibling_iterator move_before(sibling_iterator target, sibling_iterator
source);
- /// Move 'source' node (plus its children) to become the node at
'target' (erasing the node at 'target').
- template<typename iter> iter move_ontop(iter target, iter source);
-
- /// Merge with other tree, creating new branches and leaves only if they
are not already present.
- void merge(sibling_iterator, sibling_iterator, sibling_iterator,
sibling_iterator,
- bool duplicate_leaves=false);
- /// Sort (std::sort only moves values of nodes, this one moves children
as well).
- void sort(sibling_iterator from, sibling_iterator to, bool
deep=false);
- template<class StrictWeakOrdering>
- void sort(sibling_iterator from, sibling_iterator to,
StrictWeakOrdering comp, bool deep=false);
- /// Compare two ranges of nodes (compares nodes as well as tree
structure).
- template<typename iter>
- bool equal(const iter& one, const iter& two, const iter& three)
const;
- template<typename iter, class BinaryPredicate>
- bool equal(const iter& one, const iter& two, const iter& three,
BinaryPredicate) const;
- template<typename iter>
- bool equal_subtree(const iter& one, const iter& two) const;
- template<typename iter, class BinaryPredicate>
- bool equal_subtree(const iter& one, const iter& two,
BinaryPredicate) const;
- /// Extract a new tree formed by the range of siblings plus all their
children.
- tree subtree(sibling_iterator from, sibling_iterator to) const;
- void subtree(tree&, sibling_iterator from, sibling_iterator to)
const;
- /// Exchange the node (plus subtree) with its sibling node (do nothing
if no sibling present).
- void swap(sibling_iterator it);
- /// Exchange two nodes (plus subtrees)
- void swap(iterator, iterator);
-
- /// Count the total number of nodes.
- int size() const;
- /// Count the total number of nodes below the indicated node (plus one).
- int size(const iterator_base&) const;
- /// Check if tree is empty.
- bool empty() const;
- /// Compute the depth to the root.
- int depth(const iterator_base&) const;
- /// Count the number of children of node at position.
- static unsigned int number_of_children(const iterator_base&);
- /// Count the number of 'next' siblings of node at iterator.
- unsigned int number_of_siblings(const iterator_base&) const;
- /// Determine whether node at position is in the subtrees with root in
the range.
- bool is_in_subtree(const iterator_base& position, const
iterator_base& begin,
- const iterator_base& end) const;
- /// Determine whether the iterator is an 'end' iterator and thus not
actually pointing to a node.
- bool is_valid(const iterator_base&) const;
-
- /// Determine the index of a node in the range of siblings to which it
belongs.
- unsigned int index(sibling_iterator it) const;
- /// Inverse of 'index': return the n-th child of the node at position.
- sibling_iterator child(const iterator_base& position, unsigned int)
const;
-
- /// Comparator class for iterators (compares pointer values; why doesn't
this work automatically?)
- class iterator_base_less {
- public:
- bool operator()(const typename tree<T,
tree_node_allocator>::iterator_base& one,
- const typename tree<T,
tree_node_allocator>::iterator_base& two) const
- {
- return one.node < two.node;
- }
- };
- tree_node *head, *feet; // head/feet are always dummy; if an iterator
points to them it is invalid
- private:
- tree_node_allocator alloc_;
- void head_initialise_();
- void copy_(const tree<T, tree_node_allocator>& other);
-
- /// Comparator class for two nodes of a tree (used for sorting and
searching).
- template<class StrictWeakOrdering>
- class compare_nodes {
- public:
- compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
-
- bool operator()(const tree_node *a, const tree_node *b)
- {
- static StrictWeakOrdering comp;
- return comp(a->data, b->data);
- }
- private:
- StrictWeakOrdering comp_;
- };
-};
-
-//template <class T, class tree_node_allocator>
-//class iterator_base_less {
-// public:
-// bool operator()(const typename tree<T,
tree_node_allocator>::iterator_base& one,
-// const typename tree<T,
tree_node_allocator>::iterator_base& two) const
-// {
-// txtout << "operatorclass<" << one.node < two.node << std::endl;
-// return one.node < two.node;
-// }
-//};
-
-// template <class T, class tree_node_allocator>
-// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
-// const typename tree<T, tree_node_allocator>::iterator& two)
-// {
-// txtout << "operator< " << one.node < two.node << std::endl;
-// if(one.node < two.node) return true;
-// return false;
-// }
-//
-// template <class T, class tree_node_allocator>
-// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
-// const typename tree<T, tree_node_allocator>::iterator& two)
-// {
-// txtout << "operator== " << one.node == two.node << std::endl;
-// if(one.node == two.node) return true;
-// return false;
-// }
-//
-// template <class T, class tree_node_allocator>
-// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base&
one,
-// const typename tree<T, tree_node_allocator>::iterator_base&
two)
-// {
-// txtout << "operator> " << one.node < two.node << std::endl;
-// if(one.node > two.node) return true;
-// return false;
-// }
-
-
-
-// Tree
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::tree()
- {
- head_initialise_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::tree(const T& x)
- {
- head_initialise_();
- set_head(x);
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::tree(const iterator_base& other)
- {
- head_initialise_();
- set_head((*other));
- replace(begin(), other);
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::~tree()
- {
- clear();
- alloc_.deallocate(head,1);
- alloc_.deallocate(feet,1);
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::head_initialise_()
- {
- head = alloc_.allocate(1,0); // MSVC does not have default second argument
- feet = alloc_.allocate(1,0);
-
- head->parent=0;
- head->first_child=0;
- head->last_child=0;
- head->prev_sibling=0; //head;
- head->next_sibling=feet; //head;
-
- feet->parent=0;
- feet->first_child=0;
- feet->last_child=0;
- feet->prev_sibling=head;
- feet->next_sibling=0;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::operator=(const tree<T,
tree_node_allocator>& other)
- {
- copy_(other);
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
- {
- head_initialise_();
- copy_(other);
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>&
other)
- {
- clear();
- pre_order_iterator it=other.begin(), to=begin();
- while(it!=other.end()) {
- to=insert(to, (*it));
- it.skip_children();
- ++it;
- }
- to=begin();
- it=other.begin();
- while(it!=other.end()) {
- to=replace(to, it);
- to.skip_children();
- it.skip_children();
- ++to;
- ++it;
- }
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::clear()
- {
- if(head)
- while(head->next_sibling!=feet)
- erase(pre_order_iterator(head->next_sibling));
- }
-
-template<class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
- {
-// std::cout << "erase_children " << it.node << std::endl;
- if(it.node==0) return;
-
- tree_node *cur=it.node->first_child;
- tree_node *prev=0;
-
- while(cur!=0) {
- prev=cur;
- cur=cur->next_sibling;
- erase_children(pre_order_iterator(prev));
- kp::destructor(&prev->data);
- alloc_.deallocate(prev,1);
- }
- it.node->first_child=0;
- it.node->last_child=0;
-// std::cout << "exit" << std::endl;
- }
-
-template<class T, class tree_node_allocator>
-template<class iter>
-iter tree<T, tree_node_allocator>::erase(iter it)
- {
- tree_node *cur=it.node;
- assert(cur!=head);
- iter ret=it;
- ret.skip_children();
- ++ret;
- erase_children(it);
- if(cur->prev_sibling==0) {
- cur->parent->first_child=cur->next_sibling;
- }
- else {
- cur->prev_sibling->next_sibling=cur->next_sibling;
- }
- if(cur->next_sibling==0) {
- cur->parent->last_child=cur->prev_sibling;
- }
- else {
- cur->next_sibling->prev_sibling=cur->prev_sibling;
- }
-
- kp::destructor(&cur->data);
- alloc_.deallocate(cur,1);
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::begin() const
- {
- return pre_order_iterator(head->next_sibling);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::end() const
- {
- return pre_order_iterator(feet);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::begin_breadth_first() const
- {
- return breadth_first_queued_iterator(head->next_sibling);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::end_breadth_first() const
- {
- return breadth_first_queued_iterator();
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::begin_post() const
- {
- tree_node *tmp=head->next_sibling;
- if(tmp!=feet) {
- while(tmp->first_child)
- tmp=tmp->first_child;
- }
- return post_order_iterator(tmp);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::end_post() const
- {
- return post_order_iterator(feet);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp)
const
- {
- tree_node *tmp=pos.node;
- unsigned int curdepth=0;
- while(curdepth<dp) { // go down one level
- while(tmp->first_child==0) {
- tmp=tmp->next_sibling;
- if(tmp==0)
- throw std::range_error("tree: begin_fixed out of range");
- }
- tmp=tmp->first_child;
- ++curdepth;
- }
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
- {
- assert(1==0); // FIXME: not correct yet
- tree_node *tmp=pos.node;
- unsigned int curdepth=1;
- while(curdepth<dp) { // go down one level
- while(tmp->first_child==0) {
- tmp=tmp->next_sibling;
- if(tmp==0)
- throw std::range_error("tree: end_fixed out of range");
- }
- tmp=tmp->first_child;
- ++curdepth;
- }
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::begin(const iterator_base& pos) const
- {
- assert(pos.node!=0);
- if(pos.node->first_child==0) {
- return end(pos);
- }
- return pos.node->first_child;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::end(const iterator_base& pos) const
- {
- sibling_iterator ret(0);
- ret.parent_=pos.node;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::begin_leaf() const
- {
- tree_node *tmp=head->next_sibling;
- if(tmp!=feet) {
- while(tmp->first_child)
- tmp=tmp->first_child;
- }
- return leaf_iterator(tmp);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::end_leaf() const
- {
- return leaf_iterator(feet);
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::parent(iter position)
- {
- assert(position.node!=0);
- return iter(position.node->parent);
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
- {
- assert(position.node!=0);
- iter ret(position);
- ret.node=position.node->prev_sibling;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::next_sibling(iter position) const
- {
- assert(position.node!=0);
- iter ret(position);
- ret.node=position.node->next_sibling;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
- {
- assert(position.node!=0);
- iter ret(position);
-
- if(position.node->next_sibling) {
- ret.node=position.node->next_sibling;
- }
- else {
- int relative_depth=0;
- upper:
- do {
- ret.node=ret.node->parent;
- if(ret.node==0) return ret;
- --relative_depth;
- } while(ret.node->next_sibling==0);
- lower:
- ret.node=ret.node->next_sibling;
- while(ret.node->first_child==0) {
- if(ret.node->next_sibling==0)
- goto upper;
- ret.node=ret.node->next_sibling;
- if(ret.node==0) return ret;
- }
- while(relative_depth<0 && ret.node->first_child!=0) {
- ret.node=ret.node->first_child;
- ++relative_depth;
- }
- if(relative_depth<0) {
- if(ret.node->next_sibling==0) goto upper;
- else goto lower;
- }
- }
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::append_child(iter position)
- {
- assert(position.node!=head);
- assert(position.node);
-
- tree_node *tmp=alloc_.allocate(1,0);
- kp::constructor(&tmp->data);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node;
- if(position.node->last_child!=0) {
- position.node->last_child->next_sibling=tmp;
- }
- else {
- position.node->first_child=tmp;
- }
- tmp->prev_sibling=position.node->last_child;
- position.node->last_child=tmp;
- tmp->next_sibling=0;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::prepend_child(iter position)
- {
- assert(position.node!=head);
- assert(position.node);
-
- tree_node *tmp=alloc_.allocate(1,0);
- kp::constructor(&tmp->data);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node;
- if(position.node->first_child!=0) {
- position.node->first_child->prev_sibling=tmp;
- }
- else {
- position.node->last_child=tmp;
- }
- tmp->next_sibling=position.node->first_child;
- position.node->prev_child=tmp;
- tmp->prev_sibling=0;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
- {
- // If your program fails here you probably used 'append_child' to add the
top
- // node to an empty tree. From version 1.45 the top element should be added
- // using 'insert'. See the documentation for further information, and sorry
about
- // the API change.
- assert(position.node!=head);
- assert(position.node);
-
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, x);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node;
- if(position.node->last_child!=0) {
- position.node->last_child->next_sibling=tmp;
- }
- else {
- position.node->first_child=tmp;
- }
- tmp->prev_sibling=position.node->last_child;
- position.node->last_child=tmp;
- tmp->next_sibling=0;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
- {
- assert(position.node!=head);
- assert(position.node);
-
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, x);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node;
- if(position.node->first_child!=0) {
- position.node->first_child->prev_sibling=tmp;
- }
- else {
- position.node->last_child=tmp;
- }
- tmp->next_sibling=position.node->first_child;
- position.node->first_child=tmp;
- tmp->prev_sibling=0;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
- {
- assert(position.node!=head);
- assert(position.node);
-
- sibling_iterator aargh=append_child(position, value_type());
- return replace(aargh, other);
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
- {
- assert(position.node!=head);
- assert(position.node);
-
- sibling_iterator aargh=prepend_child(position, value_type());
- return replace(aargh, other);
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::append_children(iter position,
sibling_iterator from, sibling_iterator to)
- {
- assert(position.node!=head);
- assert(position.node);
-
- iter ret=from;
-
- while(from!=to) {
- insert_subtree(position.end(), from);
- ++from;
- }
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::prepend_children(iter position,
sibling_iterator from, sibling_iterator to)
- {
- assert(position.node!=head);
- assert(position.node);
-
- iter ret=from;
-
- while(from!=to) {
- insert_subtree(position.begin(), from);
- ++from;
- }
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::set_head(const T& x)
- {
- assert(head->next_sibling==feet);
- return insert(iterator(feet), x);
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
- {
- if(position.node==0) {
- position.node=feet; // Backward compatibility: when calling insert on a
null node,
- // insert before the feet.
- }
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, x);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node->parent;
- tmp->next_sibling=position.node;
- tmp->prev_sibling=position.node->prev_sibling;
- position.node->prev_sibling=tmp;
-
- if(tmp->prev_sibling==0) {
- if(tmp->parent) // when inserting nodes at the head, there is no parent
- tmp->parent->first_child=tmp;
- }
- else
- tmp->prev_sibling->next_sibling=tmp;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::insert(sibling_iterator position, const T& x)
- {
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, x);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->next_sibling=position.node;
- if(position.node==0) { // iterator points to end of a subtree
- tmp->parent=position.parent_;
- tmp->prev_sibling=position.range_last();
- tmp->parent->last_child=tmp;
- }
- else {
- tmp->parent=position.node->parent;
- tmp->prev_sibling=position.node->prev_sibling;
- position.node->prev_sibling=tmp;
- }
-
- if(tmp->prev_sibling==0) {
- if(tmp->parent) // when inserting nodes at the head, there is no parent
- tmp->parent->first_child=tmp;
- }
- else
- tmp->prev_sibling->next_sibling=tmp;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
- {
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, x);
- tmp->first_child=0;
- tmp->last_child=0;
-
- tmp->parent=position.node->parent;
- tmp->prev_sibling=position.node;
- tmp->next_sibling=position.node->next_sibling;
- position.node->next_sibling=tmp;
-
- if(tmp->next_sibling==0) {
- if(tmp->parent) // when inserting nodes at the head, there is no parent
- tmp->parent->last_child=tmp;
- }
- else {
- tmp->next_sibling->prev_sibling=tmp;
- }
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::insert_subtree(iter position, const
iterator_base& subtree)
- {
- // insert dummy
- iter it=insert(position, value_type());
- // replace dummy with subtree
- return replace(it, subtree);
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const
iterator_base& subtree)
- {
- // insert dummy
- iter it=insert_after(position, value_type());
- // replace dummy with subtree
- return replace(it, subtree);
- }
-
-// template <class T, class tree_node_allocator>
-// template <class iter>
-// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator
position, iter subtree)
-// {
-// // insert dummy
-// iter it(insert(position, value_type()));
-// // replace dummy with subtree
-// return replace(it, subtree);
-// }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
- {
- kp::destructor(&position.node->data);
- kp::constructor(&position.node->data, x);
- return position;
- }
-
-template <class T, class tree_node_allocator>
-template <class iter>
-iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base&
from)
- {
- assert(position.node!=head);
- tree_node *current_from=from.node;
- tree_node *start_from=from.node;
- tree_node *current_to =position.node;
-
- // replace the node at position with head of the replacement tree at from
-// std::cout << "warning!" << position.node << std::endl;
- erase_children(position);
-// std::cout << "no warning!" << std::endl;
- tree_node* tmp = alloc_.allocate(1,0);
- kp::constructor(&tmp->data, (*from));
- tmp->first_child=0;
- tmp->last_child=0;
- if(current_to->prev_sibling==0) {
- if(current_to->parent!=0)
- current_to->parent->first_child=tmp;
- }
- else {
- current_to->prev_sibling->next_sibling=tmp;
- }
- tmp->prev_sibling=current_to->prev_sibling;
- if(current_to->next_sibling==0) {
- if(current_to->parent!=0)
- current_to->parent->last_child=tmp;
- }
- else {
- current_to->next_sibling->prev_sibling=tmp;
- }
- tmp->next_sibling=current_to->next_sibling;
- tmp->parent=current_to->parent;
- kp::destructor(¤t_to->data);
- alloc_.deallocate(current_to,1);
- current_to=tmp;
-
- // only at this stage can we fix 'last'
- tree_node *last=from.node->next_sibling;
-
- pre_order_iterator toit=tmp;
- // copy all children
- do {
- assert(current_from!=0);
- if(current_from->first_child != 0) {
- current_from=current_from->first_child;
- toit=append_child(toit, current_from->data);
- }
- else {
- while(current_from->next_sibling==0 && current_from!=start_from) {
- current_from=current_from->parent;
- toit=parent(toit);
- assert(current_from!=0);
- }
- current_from=current_from->next_sibling;
- if(current_from!=last) {
- toit=append_child(parent(toit), current_from->data);
- }
- }
- } while(current_from!=last);
-
- return current_to;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::replace(
- sibling_iterator orig_begin,
- sibling_iterator orig_end,
- sibling_iterator new_begin,
- sibling_iterator new_end)
- {
- tree_node *orig_first=orig_begin.node;
- tree_node *new_first=new_begin.node;
- tree_node *orig_last=orig_first;
- while((++orig_begin)!=orig_end)
- orig_last=orig_last->next_sibling;
- tree_node *new_last=new_first;
- while((++new_begin)!=new_end)
- new_last=new_last->next_sibling;
-
- // insert all siblings in new_first..new_last before orig_first
- bool first=true;
- pre_order_iterator ret;
- while(1==1) {
- pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first),
pre_order_iterator(new_first));
- if(first) {
- ret=tt;
- first=false;
- }
- if(new_first==new_last)
- break;
- new_first=new_first->next_sibling;
- }
-
- // erase old range of siblings
- bool last=false;
- tree_node *next=orig_first;
- while(1==1) {
- if(next==orig_last)
- last=true;
- next=next->next_sibling;
- erase((pre_order_iterator)orig_first);
- if(last)
- break;
- orig_first=next;
- }
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::flatten(iter position)
- {
- if(position.node->first_child==0)
- return position;
-
- tree_node *tmp=position.node->first_child;
- while(tmp) {
- tmp->parent=position.node->parent;
- tmp=tmp->next_sibling;
- }
- if(position.node->next_sibling) {
- position.node->last_child->next_sibling=position.node->next_sibling;
- position.node->next_sibling->prev_sibling=position.node->last_child;
- }
- else {
- position.node->parent->last_child=position.node->last_child;
- }
- position.node->next_sibling=position.node->first_child;
- position.node->next_sibling->prev_sibling=position.node;
- position.node->first_child=0;
- position.node->last_child=0;
-
- return position;
- }
-
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator
begin, sibling_iterator end)
- {
- tree_node *first=begin.node;
- tree_node *last=first;
-
- assert(first!=position.node);
-
- if(begin==end) return begin;
- // determine last node
- while((++begin)!=end) {
- last=last->next_sibling;
- }
- // move subtree
- if(first->prev_sibling==0) {
- first->parent->first_child=last->next_sibling;
- }
- else {
- first->prev_sibling->next_sibling=last->next_sibling;
- }
- if(last->next_sibling==0) {
- last->parent->last_child=first->prev_sibling;
- }
- else {
- last->next_sibling->prev_sibling=first->prev_sibling;
- }
- if(position.node->first_child==0) {
- position.node->first_child=first;
- position.node->last_child=last;
- first->prev_sibling=0;
- }
- else {
- position.node->last_child->next_sibling=first;
- first->prev_sibling=position.node->last_child;
- position.node->last_child=last;
- }
- last->next_sibling=0;
-
- tree_node *pos=first;
- while(1==1) {
- pos->parent=position.node;
- if(pos==last) break;
- pos=pos->next_sibling;
- }
-
- return first;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter
position, iter from)
- {
- if(from.node->first_child==0) return position;
- return reparent(position, from.node->first_child, end(from));
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter
position, const T& x)
- {
- assert(position.node!=0);
- sibling_iterator fr=position, to=position;
- ++to;
- iter ret = insert(position, x);
- reparent(ret, fr, to);
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter
target, iter source)
- {
- tree_node *dst=target.node;
- tree_node *src=source.node;
- assert(dst);
- assert(src);
-
- if(dst==src) return source;
- if(dst->next_sibling)
- if(dst->next_sibling==src) // already in the right spot
- return source;
-
- // take src out of the tree
- if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
- else src->parent->first_child=src->next_sibling;
- if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
- else src->parent->last_child=src->prev_sibling;
-
- // connect it to the new point
- if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
- else dst->parent->last_child=src;
- src->next_sibling=dst->next_sibling;
- dst->next_sibling=src;
- src->prev_sibling=dst;
- src->parent=dst->parent;
- return src;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter
target, iter source)
- {
- tree_node *dst=target.node;
- tree_node *src=source.node;
- assert(dst);
- assert(src);
-
- if(dst==src) return source;
- if(dst->prev_sibling)
- if(dst->prev_sibling==src) // already in the right spot
- return source;
-
- // take src out of the tree
- if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
- else src->parent->first_child=src->next_sibling;
- if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
- else src->parent->last_child=src->prev_sibling;
-
- // connect it to the new point
- if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
- else dst->parent->first_child=src;
- src->prev_sibling=dst->prev_sibling;
- dst->prev_sibling=src;
- src->next_sibling=dst;
- src->parent=dst->parent;
- return src;
- }
-
-// specialisation for sibling_iterators
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::move_before(sibling_iterator target,
-
sibling_iterator source)
- {
- tree_node *dst=target.node;
- tree_node *src=source.node;
- tree_node *dst_prev_sibling;
- if(dst==0) { // must then be an end iterator
- dst_prev_sibling=target.parent_->last_child;
- assert(dst_prev_sibling);
- }
- else dst_prev_sibling=dst->prev_sibling;
- assert(src);
-
- if(dst==src) return source;
- if(dst_prev_sibling)
- if(dst_prev_sibling==src) // already in the right spot
- return source;
-
- // take src out of the tree
- if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
- else src->parent->first_child=src->next_sibling;
- if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
- else src->parent->last_child=src->prev_sibling;
-
- // connect it to the new point
- if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
- else target.parent_->first_child=src;
- src->prev_sibling=dst_prev_sibling;
- if(dst) {
- dst->prev_sibling=src;
- src->parent=dst->parent;
- }
- src->next_sibling=dst;
- return src;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter
target, iter source)
- {
- tree_node *dst=target.node;
- tree_node *src=source.node;
- assert(dst);
- assert(src);
-
- if(dst==src) return source;
-
- // remember connection points
- tree_node *b_prev_sibling=dst->prev_sibling;
- tree_node *b_next_sibling=dst->next_sibling;
- tree_node *b_parent=dst->parent;
-
- // remove target
- erase(target);
-
- // take src out of the tree
- if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
- else src->parent->first_child=src->next_sibling;
- if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
- else src->parent->last_child=src->prev_sibling;
-
- // connect it to the new point
- if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
- else b_parent->first_child=src;
- if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
- else b_parent->last_child=src;
- src->prev_sibling=b_prev_sibling;
- src->next_sibling=b_next_sibling;
- src->parent=b_parent;
- return src;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::merge(sibling_iterator to1,
sibling_iterator to2,
- sibling_iterator from1,
sibling_iterator from2,
- bool duplicate_leaves)
- {
- sibling_iterator fnd;
- while(from1!=from2) {
- if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
- if(from1.begin()==from1.end()) { // full depth reached
- if(duplicate_leaves)
- append_child(parent(to1), (*from1));
- }
- else { // descend further
- merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(),
duplicate_leaves);
- }
- }
- else { // element missing
- insert_subtree(to2, from1);
- }
- ++from1;
- }
- }
-
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::sort(sibling_iterator from,
sibling_iterator to, bool deep)
- {
- std::less<T> comp;
- sort(from, to, comp, deep);
- }
-
-template <class T, class tree_node_allocator>
-template <class StrictWeakOrdering>
-void tree<T, tree_node_allocator>::sort(sibling_iterator from,
sibling_iterator to,
- StrictWeakOrdering comp, bool deep)
- {
- if(from==to) return;
- // make list of sorted nodes
- // CHECK: if multiset stores equivalent nodes in the order in which they
- // are inserted, then this routine should be called 'stable_sort'.
- std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
- sibling_iterator it=from, it2=to;
- while(it != to) {
- nodes.insert(it.node);
- ++it;
- }
- // reassemble
- --it2;
-
- // prev and next are the nodes before and after the sorted range
- tree_node *prev=from.node->prev_sibling;
- tree_node *next=it2.node->next_sibling;
- typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering>
>::iterator nit=nodes.begin(), eit=nodes.end();
- if(prev==0) {
- if((*nit)->parent!=0) // to catch "sorting the head" situations, when
there is no parent
- (*nit)->parent->first_child=(*nit);
- }
- else prev->next_sibling=(*nit);
-
- --eit;
- while(nit!=eit) {
- (*nit)->prev_sibling=prev;
- if(prev)
- prev->next_sibling=(*nit);
- prev=(*nit);
- ++nit;
- }
- // prev now points to the last-but-one node in the sorted range
- if(prev)
- prev->next_sibling=(*eit);
-
- // eit points to the last node in the sorted range.
- (*eit)->next_sibling=next;
- (*eit)->prev_sibling=prev; // missed in the loop above
- if(next==0) {
- if((*eit)->parent!=0) // to catch "sorting the head" situations, when
there is no parent
- (*eit)->parent->last_child=(*eit);
- }
- else next->prev_sibling=(*eit);
-
- if(deep) { // sort the children of each node too
- sibling_iterator bcs(*nodes.begin());
- sibling_iterator ecs(*eit);
- ++ecs;
- while(bcs!=ecs) {
- sort(begin(bcs), end(bcs), comp, deep);
- ++bcs;
- }
- }
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two,
const iter& three_) const
- {
- std::equal_to<T> comp;
- return equal(one_, two, three_, comp);
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter>
-bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter&
two_) const
- {
- std::equal_to<T> comp;
- return equal_subtree(one_, two_, comp);
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter, class BinaryPredicate>
-bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two,
const iter& three_, BinaryPredicate fun) const
- {
- pre_order_iterator one(one_), three(three_);
-
-// if(one==two && is_valid(three) && three.number_of_children()!=0)
-// return false;
- while(one!=two && is_valid(three)) {
- if(!fun(*one,*three))
- return false;
- if(one.number_of_children()!=three.number_of_children())
- return false;
- ++one;
- ++three;
- }
- return true;
- }
-
-template <class T, class tree_node_allocator>
-template <typename iter, class BinaryPredicate>
-bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter&
two_, BinaryPredicate fun) const
- {
- pre_order_iterator one(one_), two(two_);
-
- if(!fun(*one,*two)) return false;
- if(number_of_children(one)!=number_of_children(two)) return false;
- return equal(begin(one),end(one),begin(two),fun);
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator> tree<T,
tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
- {
- tree tmp;
- tmp.set_head(value_type());
- tmp.replace(tmp.begin(), tmp.end(), from, to);
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from,
sibling_iterator to) const
- {
- tmp.set_head(value_type());
- tmp.replace(tmp.begin(), tmp.end(), from, to);
- }
-
-template <class T, class tree_node_allocator>
-int tree<T, tree_node_allocator>::size() const
- {
- int i=0;
- pre_order_iterator it=begin(), eit=end();
- while(it!=eit) {
- ++i;
- ++it;
- }
- return i;
- }
-
-template <class T, class tree_node_allocator>
-int tree<T, tree_node_allocator>::size(const iterator_base& top) const
- {
- int i=0;
- pre_order_iterator it=top, eit=top;
- eit.skip_children();
- ++eit;
- while(it!=eit) {
- ++i;
- ++it;
- }
- return i;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::empty() const
- {
- pre_order_iterator it=begin(), eit=end();
- return (it==eit);
- }
-
-template <class T, class tree_node_allocator>
-int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
- {
- tree_node* pos=it.node;
- assert(pos!=0);
- int ret=0;
- while(pos->parent!=0) {
- pos=pos->parent;
- ++ret;
- }
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-unsigned int tree<T, tree_node_allocator>::number_of_children(const
iterator_base& it)
- {
- tree_node *pos=it.node->first_child;
- if(pos==0) return 0;
-
- unsigned int ret=1;
-// while(pos!=it.node->last_child) {
-// ++ret;
-// pos=pos->next_sibling;
-// }
- while((pos=pos->next_sibling))
- ++ret;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-unsigned int tree<T, tree_node_allocator>::number_of_siblings(const
iterator_base& it) const
- {
- tree_node *pos=it.node;
- unsigned int ret=0;
- // count forward
- while(pos->next_sibling &&
- pos->next_sibling!=head &&
- pos->next_sibling!=feet) {
- ++ret;
- pos=pos->next_sibling;
- }
- // count backward
- pos=it.node;
- while(pos->prev_sibling &&
- pos->prev_sibling!=head &&
- pos->prev_sibling!=feet) {
- ++ret;
- pos=pos->prev_sibling;
- }
-
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::swap(sibling_iterator it)
- {
- tree_node *nxt=it.node->next_sibling;
- if(nxt) {
- if(it.node->prev_sibling)
- it.node->prev_sibling->next_sibling=nxt;
- else
- it.node->parent->first_child=nxt;
- nxt->prev_sibling=it.node->prev_sibling;
- tree_node *nxtnxt=nxt->next_sibling;
- if(nxtnxt)
- nxtnxt->prev_sibling=it.node;
- else
- it.node->parent->last_child=it.node;
- nxt->next_sibling=it.node;
- it.node->prev_sibling=nxt;
- it.node->next_sibling=nxtnxt;
- }
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
- {
- // if one and two are adjacent siblings, use the sibling swap
- if(one.node->next_sibling==two.node) swap(one);
- else if(two.node->next_sibling==one.node) swap(two);
- else {
- tree_node *nxt1=one.node->next_sibling;
- tree_node *nxt2=two.node->next_sibling;
- tree_node *pre1=one.node->prev_sibling;
- tree_node *pre2=two.node->prev_sibling;
- tree_node *par1=one.node->parent;
- tree_node *par2=two.node->parent;
-
- // reconnect
- one.node->parent=par2;
- one.node->next_sibling=nxt2;
- if(nxt2) nxt2->prev_sibling=one.node;
- else par2->last_child=one.node;
- one.node->prev_sibling=pre2;
- if(pre2) pre2->next_sibling=one.node;
- else par2->first_child=one.node;
-
- two.node->parent=par1;
- two.node->next_sibling=nxt1;
- if(nxt1) nxt1->prev_sibling=two.node;
- else par1->last_child=two.node;
- two.node->prev_sibling=pre1;
- if(pre1) pre1->next_sibling=two.node;
- else par1->first_child=two.node;
- }
- }
-
-// template <class BinaryPredicate>
-// tree<T, tree_node_allocator>::iterator tree<T,
tree_node_allocator>::find_subtree(
-// sibling_iterator subfrom, sibling_iterator subto, iterator from,
iterator to,
-// BinaryPredicate fun) const
-// {
-// assert(1==0); // this routine is not finished yet.
-// while(from!=to) {
-// if(fun(*subfrom, *from)) {
-//
-// }
-// }
-// return to;
-// }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it,
const iterator_base& begin,
- const iterator_base& end)
const
- {
- // FIXME: this should be optimised.
- pre_order_iterator tmp=begin;
- while(tmp!=end) {
- if(tmp==it) return true;
- ++tmp;
- }
- return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
- {
- if(it.node==0 || it.node==feet || it.node==head) return false;
- else return true;
- }
-
-template <class T, class tree_node_allocator>
-unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
- {
- unsigned int ind=0;
- if(it.node->parent==0) {
- while(it.node->prev_sibling!=head) {
- it.node=it.node->prev_sibling;
- ++ind;
- }
- }
- else {
- while(it.node->prev_sibling!=0) {
- it.node=it.node->prev_sibling;
- ++ind;
- }
- }
- return ind;
- }
-
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
- {
- tree_node *tmp=it.node->first_child;
- while(num--) {
- assert(tmp!=0);
- tmp=tmp->next_sibling;
- }
- return tmp;
- }
-
-
-
-
-// Iterator base
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::iterator_base::iterator_base()
- : node(0), skip_current_children_(false)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
- : node(tn), skip_current_children_(false)
- {
- }
-
-template <class T, class tree_node_allocator>
-T& tree<T, tree_node_allocator>::iterator_base::operator*() const
- {
- return node->data;
- }
-
-template <class T, class tree_node_allocator>
-T* tree<T, tree_node_allocator>::iterator_base::operator->() const
- {
- return &(node->data);
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const
post_order_iterator& other) const
- {
- if(other.node!=this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const
post_order_iterator& other) const
- {
- if(other.node==this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const
pre_order_iterator& other) const
- {
- if(other.node!=this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const
pre_order_iterator& other) const
- {
- if(other.node==this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const
sibling_iterator& other) const
- {
- if(other.node!=this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const
sibling_iterator& other) const
- {
- if(other.node==this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const
leaf_iterator& other) const
- {
- if(other.node!=this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const
leaf_iterator& other) const
- {
- if(other.node==this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::iterator_base::begin() const
- {
- if(node->first_child==0)
- return end();
-
- sibling_iterator ret(node->first_child);
- ret.parent_=this->node;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::iterator_base::end() const
- {
- sibling_iterator ret(0);
- ret.parent_=node;
- return ret;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::iterator_base::skip_children()
- {
- skip_current_children_=true;
- }
-
-template <class T, class tree_node_allocator>
-unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children()
const
- {
- tree_node *pos=node->first_child;
- if(pos==0) return 0;
-
- unsigned int ret=1;
- while(pos!=node->last_child) {
- ++ret;
- pos=pos->next_sibling;
- }
- return ret;
- }
-
-
-
-// Pre-order iterator
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
- : iterator_base(0)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node
*tn)
- : iterator_base(tn)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const
iterator_base &other)
- : iterator_base(other.node)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const
sibling_iterator& other)
- : iterator_base(other.node)
- {
- if(this->node==0) {
- if(other.range_last()!=0)
- this->node=other.range_last();
- else
- this->node=other.parent_;
- this->skip_children();
- ++(*this);
- }
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator++()
- {
- assert(this->node!=0);
- if(!this->skip_current_children_ && this->node->first_child != 0) {
- this->node=this->node->first_child;
- }
- else {
- this->skip_current_children_=false;
- while(this->node->next_sibling==0) {
- this->node=this->node->parent;
- if(this->node==0)
- return *this;
- }
- this->node=this->node->next_sibling;
- }
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator--()
- {
- assert(this->node!=0);
- if(this->node->prev_sibling) {
- this->node=this->node->prev_sibling;
- while(this->node->last_child)
- this->node=this->node->last_child;
- }
- else {
- this->node=this->node->parent;
- if(this->node==0)
- return *this;
- }
- return *this;
-}
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::pre_order_iterator::operator++(int n)
- {
- pre_order_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator tree<T,
tree_node_allocator>::pre_order_iterator::operator--(int n)
-{
- pre_order_iterator copy = *this;
- --(*this);
- return copy;
-}
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
- {
- while(num>0) {
- ++(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T,
tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
- {
- while(num>0) {
- --(*this);
- --num;
- }
- return (*this);
- }
-
-
-
-// Post-order iterator
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
- : iterator_base(0)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T,
tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
- : iterator_base(tn)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const
iterator_base &other)
- : iterator_base(other.node)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const
sibling_iterator& other)
- : iterator_base(other.node)
- {
- if(this->node==0) {
- if(other.range_last()!=0)
- this->node=other.range_last();
- else
- this->node=other.parent_;
- this->skip_children();
- ++(*this);
- }
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator++()
- {
- assert(this->node!=0);
- if(this->node->next_sibling==0) {
- this->node=this->node->parent;
- this->skip_current_children_=false;
- }
- else {
- this->node=this->node->next_sibling;
- if(this->skip_current_children_) {
- this->skip_current_children_=false;
- }
- else {
- while(this->node->first_child)
- this->node=this->node->first_child;
- }
- }
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator--()
- {
- assert(this->node!=0);
- if(this->skip_current_children_ || this->node->last_child==0) {
- this->skip_current_children_=false;
- while(this->node->prev_sibling==0)
- this->node=this->node->parent;
- this->node=this->node->prev_sibling;
- }
- else {
- this->node=this->node->last_child;
- }
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::post_order_iterator::operator++(int)
- {
- post_order_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator tree<T,
tree_node_allocator>::post_order_iterator::operator--(int)
- {
- post_order_iterator copy = *this;
- --(*this);
- return copy;
- }
-
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
- {
- while(num>0) {
- ++(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::post_order_iterator& tree<T,
tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
- {
- while(num>0) {
- --(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
- {
- assert(this->node!=0);
- while(this->node->first_child)
- this->node=this->node->first_child;
- }
-
-
-// Breadth-first iterator
-
-template <class T, class tree_node_allocator>
-tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
- : iterator_base()
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node
*tn)
- : iterator_base(tn)
- {
- traversal_queue.push(tn);
- }
-
-template <class T, class tree_node_allocator>
-tree<T,
tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const
iterator_base& other)
- : iterator_base(other.node)
- {
- traversal_queue.push(other.node);
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator!=(const
breadth_first_queued_iterator& other) const
- {
- if(other.node!=this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator==(const
breadth_first_queued_iterator& other) const
- {
- if(other.node==this->node) return true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator++()
- {
- assert(this->node!=0);
-
- // Add child nodes and pop current node
- sibling_iterator sib=this->begin();
- while(sib!=this->end()) {
- traversal_queue.push(sib.node);
- ++sib;
- }
- traversal_queue.pop();
- if(traversal_queue.size()>0)
- this->node=traversal_queue.front();
- else
- this->node=0;
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator++(int n)
- {
- breadth_first_queued_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T,
tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int
num)
- {
- while(num>0) {
- ++(*this);
- --num;
- }
- return (*this);
- }
-
-
-
-// Fixed depth iterator
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
- : iterator_base()
- {
- set_first_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T,
tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
- : iterator_base(tn)
- {
- set_first_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
iterator_base& other)
- : iterator_base(other.node)
- {
- set_first_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
sibling_iterator& other)
- : iterator_base(other.node), first_parent_(other.parent_)
- {
- find_leftmost_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const
fixed_depth_iterator& other)
- : iterator_base(other.node), first_parent_(other.first_parent_)
- {
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const
fixed_depth_iterator& other) const
- {
- if(other.node==this->node && other.first_parent_==first_parent_) return
true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const
fixed_depth_iterator& other) const
- {
- if(other.node!=this->node || other.first_parent_!=first_parent_) return
true;
- else return false;
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
- {
- return; // FIXME: we do not use first_parent_ yet, and it actually needs
some serious reworking if
- // it is ever to work at the 'head' level.
- first_parent_=0;
- if(this->node==0) return;
- if(this->node->parent!=0)
- first_parent_=this->node->parent;
- if(first_parent_)
- find_leftmost_parent_();
- }
-
-template <class T, class tree_node_allocator>
-void tree<T,
tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
- {
- return; // FIXME: see 'set_first_parent()'
- tree_node *tmppar=first_parent_;
- while(tmppar->prev_sibling) {
- tmppar=tmppar->prev_sibling;
- if(tmppar->first_child)
- first_parent_=tmppar;
- }
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator++()
- {
- assert(this->node!=0);
-
- if(this->node->next_sibling) {
- this->node=this->node->next_sibling;
- }
- else {
- int relative_depth=0;
- upper:
- do {
- this->node=this->node->parent;
- if(this->node==0) return *this;
- --relative_depth;
- } while(this->node->next_sibling==0);
- lower:
- this->node=this->node->next_sibling;
- while(this->node->first_child==0) {
- if(this->node->next_sibling==0)
- goto upper;
- this->node=this->node->next_sibling;
- if(this->node==0) return *this;
- }
- while(relative_depth<0 && this->node->first_child!=0) {
- this->node=this->node->first_child;
- ++relative_depth;
- }
- if(relative_depth<0) {
- if(this->node->next_sibling==0) goto upper;
- else goto lower;
- }
- }
- return *this;
-
-// if(this->node->next_sibling!=0) {
-// this->node=this->node->next_sibling;
-// assert(this->node!=0);
-// if(this->node->parent==0 && this->node->next_sibling==0) // feet element
-// this->node=0;
-// }
-// else {
-// tree_node *par=this->node->parent;
-// do {
-// par=par->next_sibling;
-// if(par==0) { // FIXME: need to keep track of this!
-// this->node=0;
-// return *this;
-// }
-// } while(par->first_child==0);
-// this->node=par->first_child;
-// }
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator--()
- {
- assert(this->node!=0);
- if(this->node->prev_sibling!=0) {
- this->node=this->node->prev_sibling;
- assert(this->node!=0);
- if(this->node->parent==0 && this->node->prev_sibling==0) // head element
- this->node=0;
- }
- else {
- tree_node *par=this->node->parent;
- do {
- par=par->prev_sibling;
- if(par==0) { // FIXME: need to keep track of this!
- this->node=0;
- return *this;
- }
- } while(par->last_child==0);
- this->node=par->last_child;
- }
- return *this;
-}
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::fixed_depth_iterator::operator++(int)
- {
- fixed_depth_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T,
tree_node_allocator>::fixed_depth_iterator::operator--(int)
-{
- fixed_depth_iterator copy = *this;
- --(*this);
- return copy;
-}
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
- {
- while(num>0) {
- --(*this);
- --(num);
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T,
tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
- {
- while(num>0) {
- ++(*this);
- --(num);
- }
- return *this;
- }
-
-// FIXME: add the other members of fixed_depth_iterator.
-
-
-// Sibling iterator
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
- : iterator_base()
- {
- set_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
- : iterator_base(tn)
- {
- set_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const
iterator_base& other)
- : iterator_base(other.node)
- {
- set_parent_();
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const
sibling_iterator& other)
- : iterator_base(other), parent_(other.parent_)
- {
- }
-
-template <class T, class tree_node_allocator>
-void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
- {
- parent_=0;
- if(this->node==0) return;
- if(this->node->parent!=0)
- parent_=this->node->parent;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator++()
- {
- if(this->node)
- this->node=this->node->next_sibling;
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator--()
- {
- if(this->node) this->node=this->node->prev_sibling;
- else {
- assert(parent_);
- this->node=parent_->last_child;
- }
- return *this;
-}
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::sibling_iterator::operator++(int)
- {
- sibling_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator tree<T,
tree_node_allocator>::sibling_iterator::operator--(int)
- {
- sibling_iterator copy = *this;
- --(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
- {
- while(num>0) {
- ++(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::sibling_iterator& tree<T,
tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
- {
- while(num>0) {
- --(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::tree_node *tree<T,
tree_node_allocator>::sibling_iterator::range_first() const
- {
- tree_node *tmp=parent_->first_child;
- return tmp;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::tree_node *tree<T,
tree_node_allocator>::sibling_iterator::range_last() const
- {
- return parent_->last_child;
- }
-
-// Leaf iterator
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
- : iterator_base(0)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn)
- : iterator_base(tn)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base
&other)
- : iterator_base(other.node)
- {
- }
-
-template <class T, class tree_node_allocator>
-tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const
sibling_iterator& other)
- : iterator_base(other.node)
- {
- if(this->node==0) {
- if(other.range_last()!=0)
- this->node=other.range_last();
- else
- this->node=other.parent_;
- ++(*this);
- }
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator++()
- {
- assert(this->node!=0);
- while(this->node->next_sibling==0) {
- if (this->node->parent==0) return *this;
- this->node=this->node->parent;
- }
- this->node=this->node->next_sibling;
- while(this->node->first_child)
- this->node=this->node->first_child;
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator--()
- {
- assert(this->node!=0);
- while (this->node->prev_sibling==0) {
- if (this->node->parent==0) return *this;
- this->node=this->node->parent;
- }
- this->node=this->node->prev_sibling;
- while(this->node->last_child)
- this->node=this->node->last_child;
- return *this;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::leaf_iterator::operator++(int)
- {
- leaf_iterator copy = *this;
- ++(*this);
- return copy;
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator tree<T,
tree_node_allocator>::leaf_iterator::operator--(int)
- {
- leaf_iterator copy = *this;
- --(*this);
- return copy;
- }
-
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
- {
- while(num>0) {
- ++(*this);
- --num;
- }
- return (*this);
- }
-
-template <class T, class tree_node_allocator>
-typename tree<T, tree_node_allocator>::leaf_iterator& tree<T,
tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
- {
- while(num>0) {
- --(*this);
- --num;
- }
- return (*this);
- }
-
-#endif
-
-// Local variables:
-// default-tab-width: 3
-// End:
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Gnash-commit] gnash ChangeLog libbase/Makefile.am libbase/tre...,
Sandro Santilli <=