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_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 }
00212
00213 }
00214
00215
00216 #endif // ! MLN_UTIL_TREE_FAST_HH