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_HH
00027 # define MLN_UTIL_BRANCH_ITER_HH
00028
00036 # include <stack>
00037 # include <mln/util/tree.hh>
00038
00039 namespace mln
00040 {
00041
00042 namespace util
00043 {
00044
00051 template <typename T>
00052 class branch_iter
00053 {
00054 public:
00055 branch_iter(branch<T> branch);
00056
00058 operator util::tree_node<T>&() const;
00059 util::tree_node<T>& operator *();
00060
00062 bool is_valid() const;
00063
00065 void invalidate();
00066
00068 void start();
00069
00071 void next();
00072
00074 unsigned deepness() const;
00075 private:
00077 util::branch<T> branch_;
00078
00079 typedef typename std::vector< util::tree_node<T>* >::iterator child_iter;
00080 typedef std::pair<child_iter, child_iter> iter_pair;
00082 std::stack< iter_pair > s_;
00083
00084 util::tree_node<T>* n_;
00085 };
00086
00087
00088 # ifndef MLN_INCLUDE_ONLY
00089
00090
00091 template <typename T>
00092 inline
00093 branch_iter<T>::branch_iter(branch<T> branch)
00094 : branch_(branch)
00095 {
00096 invalidate();
00097 }
00098
00099 template <typename T>
00100 inline
00101 branch_iter<T>::operator util::tree_node<T>&() const
00102 {
00103 mln_assertion(n_);
00104 return *n_;
00105 }
00106
00107 template <typename T>
00108 inline
00109 util::tree_node<T>&
00110 branch_iter<T>::operator*()
00111 {
00112 mln_assertion(n_);
00113 return *n_;
00114 }
00115
00116 template <typename T>
00117 inline
00118 unsigned
00119 branch_iter<T>::deepness() const
00120 {
00121 mln_assertion(is_valid());
00122 unsigned i = 0;
00123 tree_node<T>* p = n_;
00124 while (p)
00125 {
00126 p = p->parent();
00127 i++;
00128 }
00129 return i;
00130 }
00131
00132 template <typename T>
00133 inline
00134 bool
00135 branch_iter<T>::is_valid() const
00136 {
00137 return n_ != 0;
00138 }
00139
00140 template <typename T>
00141 inline
00142 void
00143 branch_iter<T>::invalidate()
00144 {
00145 n_ = 0;
00146 }
00147
00148
00149 template <typename T>
00150 inline
00151 void
00152 branch_iter<T>::start()
00153 {
00154 s_.push(iter_pair(branch_.apex().children().begin(),
00155 branch_.apex().children().end()));
00156 n_ = &branch_.apex();
00157 }
00158
00159 template <typename T>
00160 inline
00161 void
00162 branch_iter<T>::next()
00163 {
00164 if (s_.size() == 0)
00165 invalidate();
00166 else
00167 {
00168 if (s_.top().first == s_.top().second)
00169 {
00170 s_.pop();
00171 next();
00172 return;
00173 }
00174 else
00175 {
00176 n_ = *(s_.top().first);
00177 s_.top().first++;
00178
00179 if (!n_)
00180 {
00181 next();
00182 return;
00183 }
00184
00185 mln_assertion(n_);
00186 if (n_->children().size() > 0)
00187 {
00188 s_.push(iter_pair(n_->children().begin(),
00189 n_->children().end()));
00190 }
00191 return;
00192 }
00193 }
00194 }
00195
00196 # endif // ! MLN_INCLUDE_ONLY
00197
00198
00199 }
00200
00201 }
00202
00203
00204 #endif // ! MLN_UTIL_BRANCH_ITER_HH