Milena (Olena)
User documentation 2.0a Id
|
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_TREE_FAST_HH 00027 # define MLN_UTIL_TREE_FAST_HH 00028 00029 # include <vector> 00030 # include <mln/core/contract.hh> 00031 00035 00036 00037 namespace mln 00038 { 00039 00040 namespace util 00041 { 00042 00043 template <typename T> 00044 struct tree_fast 00045 { 00049 tree_fast(); 00050 00055 tree_fast(T& elt); 00056 00061 unsigned size() const; 00062 00063 00068 bool has (T& elt) const; 00069 00070 00077 unsigned search (T& elt) const; 00078 00079 00084 bool is_root (unsigned i) const; 00085 00086 00091 unsigned add_child (unsigned i, T& elt); 00092 00093 00098 unsigned add_parent (T& elt); 00099 00101 std::vector<T> data_; 00102 00104 std::vector<unsigned> parent_; 00105 00107 std::vector<std::vector<unsigned> > child_; 00108 00110 unsigned root_; 00111 }; 00112 00113 00114 00115 # ifndef MLN_INCLUDE_ONLY 00116 00117 template <typename T> 00118 inline 00119 tree_fast<T>::tree_fast() 00120 { 00121 } 00122 00123 template <typename T> 00124 inline 00125 tree_fast<T>::tree_fast(T& elt) 00126 { 00127 std::vector<unsigned> v; 00128 data_.push_back(elt); 00129 parent_.push_back(0); 00130 child_.push_back(v); 00131 root_ = 0; 00132 } 00133 00134 template <typename T> 00135 inline 00136 unsigned 00137 tree_fast<T>::size() const 00138 { 00139 return (data_.size ()); 00140 } 00141 00142 00143 template <typename T> 00144 inline 00145 bool 00146 tree_fast<T>::has (T& elt) const 00147 { 00148 for (unsigned i = 0; i < data_.size (); ++i) 00149 if (data_[i] == elt) 00150 return true; 00151 00152 return false; 00153 } 00154 00155 template <typename T> 00156 inline 00157 unsigned 00158 tree_fast<T>::search (T& elt) const 00159 { 00160 for (unsigned i = 0; i < data_.size (); ++i) 00161 if (data_[i] == elt) 00162 return i; 00163 00165 mln_assertion (false); 00166 return (unsigned)(-1); 00167 } 00168 00169 template <typename T> 00170 inline 00171 bool 00172 tree_fast<T>::is_root (unsigned i) const 00173 { 00174 return (root_ == i); 00175 } 00176 00177 template <typename T> 00178 inline 00179 unsigned 00180 tree_fast<T>::add_child (unsigned i, T& elt) 00181 { 00182 mln_assertion (i < data_.size ()); 00183 std::vector<unsigned> v; 00184 data_.push_back(elt); 00185 parent_.push_back(i); 00186 child_.push_back(v); 00187 child_[i].push_back(data_.size () - 1); 00188 return (data_.size () - 1); 00189 } 00190 00191 template <typename T> 00192 inline 00193 unsigned 00194 tree_fast<T>::add_parent (T& elt) 00195 { 00196 data_.push_back(elt); 00197 parent_.push_back(data_.size () - 1); 00198 std::vector<unsigned> v; 00199 v.push_back (root_); 00200 child_.push_back(v); 00201 parent_[root_] = data_.size () - 1; 00202 root_ = data_.size () - 1; 00203 return (data_.size () - 1); 00204 } 00205 00206 00207 00208 00209 # endif // ! MLN_INCLUDE_ONLY 00210 00211 } // end of namespace mln::util 00212 00213 } // end of namespace mln 00214 00215 00216 #endif // ! MLN_UTIL_TREE_FAST_HH