32template <
typename T>
class EXP treeIterator :
public std::iterator<std::input_iterator_tag, T>
35 typedef typename std::vector<T>::iterator nodes_iterator;
36 typedef std::pair<nodes_iterator, T> state;
38 std::stack<state> fStack;
40 nodes_iterator fCurrentIterator;
44 treeIterator(
const T& t,
bool end=
false) {
46 if (end) fCurrentIterator = t->elements().end();
47 else forward_down (t);
49 treeIterator(
const treeIterator& a) { *
this = a; }
50 virtual ~treeIterator() {}
52 T operator *()
const {
return *fCurrentIterator; }
53 T operator ->()
const {
return *fCurrentIterator; }
56 T getParent()
const {
return fStack.size() ? fStack.top().second : fRootElement; }
60 virtual void forward_down(
const T& t) {
61 fCurrentIterator = t->elements().begin();
62 if (fCurrentIterator != t->elements().end())
63 fStack.push( make_pair(fCurrentIterator+1, t));
69 while (fStack.size()) {
70 state s = fStack.top();
73 fCurrentIterator = s.first;
74 if (fCurrentIterator != s.second->elements().end()) {
75 fStack.push( make_pair(fCurrentIterator+1, s.second));
84 if ((*fCurrentIterator)->size()) forward_down(*fCurrentIterator);
87 treeIterator& operator ++() { forward();
return *
this; }
88 treeIterator& operator ++(
int) { forward();
return *
this; }
91 treeIterator& erase() {
92 T parent = getParent();
93 fCurrentIterator = parent->elements().erase(fCurrentIterator);
94 if (fStack.size()) fStack.pop();
95 if (fCurrentIterator != parent->elements().end()) {
96 fStack.push( make_pair(fCurrentIterator+1, parent));
103 treeIterator& insert(
const T& value) {
104 T parent = getParent();
105 fCurrentIterator = parent->elements().insert(fCurrentIterator, value);
106 if (fStack.size()) fStack.pop();
107 fStack.push( make_pair(fCurrentIterator+1, parent));
112 bool operator ==(
const treeIterator& i)
const {
114 return getParent() == i.getParent() ? ( fCurrentIterator==i.fCurrentIterator ) :
false;
116 bool operator !=(
const treeIterator& i)
const {
return !(*
this == i); }
123template <
typename T>
class EXP ctree :
virtual public smartable
131 static treePtr new_tree() { ctree<T>* o =
new ctree<T>; assert(o!=0);
return o; }
133 branchs& elements() {
return fElements; }
134 const branchs& elements()
const {
return fElements; }
135 virtual void push (
const treePtr& t) { fElements.push_back(t); }
136 virtual int size ()
const {
return int(fElements.size()); }
137 virtual bool empty ()
const {
return fElements.size()==0; }
139 iterator begin() { treePtr start=
dynamic_cast<T*
>(
this);
return iterator(start); }
140 iterator end() { treePtr start=
dynamic_cast<T*
>(
this);
return iterator(start,
true); }
141 iterator erase(iterator i) {
return i.erase(); }
142 iterator insert(iterator before,
const treePtr& value) {
return before.insert(value); }
144 literator lbegin() {
return fElements.begin(); }
145 literator lend() {
return fElements.end(); }