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_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 } // end of namespace mln 00202 00203 00204 #endif // ! MLN_UTIL_BRANCH_ITER_HH