00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 // First : list of children. 00177 // Second : i; 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 } // end of namespace mln 00221 00222 00223 #endif // ! MLN_UTIL_BRANCH_ITER_IND_HH