00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_UTIL_BRANCH_ITER_IND_HH
00027 # define MLN_UTIL_BRANCH_ITER_IND_HH
00028
00036 # include <stack>
00037 # include <mln/util/tree.hh>
00038
00039 namespace mln
00040 {
00041
00042 namespace util
00043 {
00044 template<typename T>
00045 struct bi_elt
00046 {
00047 typedef std::vector< util::tree_node<T>* > child_list;
00048
00049 bi_elt(child_list* list)
00050 : list_(list),
00051 previous_(0),
00052 pos_(-1) {}
00053
00054 child_list* list_;
00055 util::tree_node<T>* previous_;
00056 int pos_;
00057 };
00058
00065 template <typename T>
00066 class branch_iter_ind
00067 {
00068 public:
00069 branch_iter_ind(branch<T> branch);
00070
00072 operator util::tree_node<T>&() const;
00073 util::tree_node<T>& operator *();
00074
00076 bool is_valid() const;
00077
00079 void invalidate();
00080
00082 void start();
00083
00085 void next();
00086
00088 unsigned deepness() const;
00089
00090 private:
00092 util::branch<T> branch_;
00093
00095 std::stack< bi_elt<T> > s_;
00096
00097 util::tree_node<T>* n_;
00098 };
00099
00100 # ifndef MLN_INCLUDE_ONLY
00101
00102
00103 template <typename T>
00104 inline
00105 branch_iter_ind<T>::branch_iter_ind(branch<T> branch)
00106 : branch_(branch)
00107 {
00108 invalidate();
00109 }
00110
00111 template <typename T>
00112 inline
00113 branch_iter_ind<T>::operator util::tree_node<T>&() const
00114 {
00115 mln_assertion(n_);
00116 return *n_;
00117 }
00118
00119 template <typename T>
00120 inline
00121 util::tree_node<T>&
00122 branch_iter_ind<T>::operator*()
00123 {
00124 mln_assertion(n_);
00125 return *n_;
00126 }
00127
00128 template <typename T>
00129 inline
00130 unsigned
00131 branch_iter_ind<T>::deepness() const
00132 {
00133 mln_assertion(is_valid());
00134 unsigned i = 0;
00135 tree_node<T>* p = n_;
00136 while (p)
00137 {
00138 p = p->parent();
00139 i++;
00140 }
00141 return i;
00142 }
00143
00144 template <typename T>
00145 inline
00146 bool
00147 branch_iter_ind<T>::is_valid() const
00148 {
00149 return n_ != 0;
00150 }
00151
00152 template <typename T>
00153 inline
00154 void
00155 branch_iter_ind<T>::invalidate()
00156 {
00157 n_ = 0;
00158 }
00159
00160
00161 template <typename T>
00162 inline
00163 void
00164 branch_iter_ind<T>::start()
00165 {
00166 s_.push(bi_elt<T>(&branch_.apex().children()));
00167
00168 n_ = &branch_.apex();
00169 }
00170
00171 template <typename T>
00172 inline
00173 void
00174 branch_iter_ind<T>::next()
00175 {
00176
00177
00178
00179 if (s_.size() == 0)
00180 invalidate();
00181 else
00182 {
00183 s_.top().pos_++;
00184 if (s_.top().list_->size() == (unsigned)s_.top().pos_)
00185 {
00186 s_.pop();
00187 next();
00188 return;
00189 }
00190 else
00191 {
00192 mln_assertion(s_.top().list_->size() > (unsigned)s_.top().pos_);
00193 if (s_.top().previous_ != 0)
00194 mln_assertion(s_.top().previous_ == (*(s_.top().list_))[s_.top().pos_ - 1]);
00195
00196 n_ = (*(s_.top().list_))[s_.top().pos_];
00197 s_.top().previous_ = n_;
00198
00199 if (!n_)
00200 {
00201 next();
00202 return;
00203 }
00204
00205 mln_assertion(n_);
00206 if (n_->children().size() > 0)
00207 {
00208 s_.push(bi_elt<T>(&n_->children()));
00209 }
00210 return;
00211 }
00212 }
00213 }
00214
00215 # endif // ! MLN_INCLUDE_ONLY
00216
00217
00218 }
00219
00220 }
00221
00222
00223 #endif // ! MLN_UTIL_BRANCH_ITER_IND_HH