Changeset 1913:49fe71fce7fb in lemon0.x for lemon/iterable_maps.h
 Timestamp:
 01/27/06 09:18:47 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2488
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/iterable_maps.h
r1875 r1913 29 29 30 30 namespace lemon { 31 32 ///\ingroup maps 33 /// 34 /// \brief Dynamic iterable bool map. 35 /// 36 /// This class provides a special graph map type which can store 37 /// for each graph item(node, edge, etc.) a bool value. For both 38 /// the true and the false it is possible to iterate on the keys which 39 /// mapped to the given value. 40 /// 41 /// \param _Graph The graph type. 42 /// \param _Item One of the graph's item type, the key of the map. 43 template <typename _Graph, typename _Item> 44 class IterableBoolMap 45 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent { 46 private: 47 typedef _Graph Graph; 48 typedef _Item Item; 49 50 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 51 typedef typename ItemSetTraits<Graph, Item> 52 ::template Map<int>::Parent Parent; 53 54 std::vector<Item> array; 55 int sep; 56 57 const Graph& graph; 58 59 private: 60 61 int position(const Item& item) const { 62 return Parent::operator[](item); 63 } 64 65 public: 66 67 /// Indicates that the map if reference map. 68 typedef True ReferenceMapTag; 69 70 /// The key type 71 typedef Item Key; 72 /// The value type 73 typedef bool Value; 74 /// The const reference type. 75 typedef const Value& ConstReference; 76 77 78 /// \brief Refernce to the value of the map. 79 /// 80 /// This class is near to similar to the bool type. It can 81 /// be converted to bool and it has the same operators. 82 class Reference { 83 friend class IterableBoolMap; 84 private: 85 Reference(IterableBoolMap& map, const Key& key) 86 : _key(key), _map(map) {} 87 public: 88 89 Reference& operator=(const Reference& value) { 90 _map.set(_key, (bool)value); 91 return *this; 92 } 93 94 operator bool() const { 95 return static_cast<const IterableBoolMap&>(_map)[_key]; 96 } 97 98 Reference& operator=(bool value) { 99 _map.set(_key, value); 100 return *this; 101 } 102 Reference& operator&=(bool value) { 103 _map.set(_key, _map[_key] & value); 104 return *this; 105 } 106 Reference& operator=(bool value) { 107 _map.set(_key, _map[_key]  value); 108 return *this; 109 } 110 Reference& operator^=(bool value) { 111 _map.set(_key, _map[_key] ^ value); 112 return *this; 113 } 114 private: 115 Key _key; 116 IterableBoolMap& _map; 117 }; 118 119 /// \brief Constructor of the Map with a default value. 120 /// 121 /// Constructor of the Map with a default value. 122 IterableBoolMap(const Graph& _graph, bool def = false) 123 : Parent(_graph), graph(_graph) { 124 for (ItemIt it(graph); it != INVALID; ++it) { 125 Parent::set(it, array.size()); 126 array.push_back(it); 127 } 128 sep = (def ? array.size() : 0); 129 } 130 131 /// \brief Const subscript operator of the map. 132 /// 133 /// Const subscript operator of the map. 134 bool operator[](const Item& item) const { 135 return position(item) < sep; 136 } 137 138 /// \brief Subscript operator of the map. 139 /// 140 /// Subscript operator of the map. 141 Reference operator[](const Item& item) { 142 return Reference(*this, item); 143 } 144 145 /// \brief Set operation of the map. 146 /// 147 /// Set operation of the map. 148 void set(const Item& item, bool value) { 149 int pos = position(item); 150 if (value) { 151 if (pos < sep) return; 152 Item tmp = array[sep]; 153 array[sep] = item; 154 Parent::set(item, sep); 155 array[pos] = tmp; 156 Parent::set(tmp, pos); 157 ++sep; 158 } else { 159 if (pos >= sep) return; 160 sep; 161 Item tmp = array[sep]; 162 array[sep] = item; 163 Parent::set(item, sep); 164 array[pos] = tmp; 165 Parent::set(tmp, pos); 166 } 167 } 168 169 /// \brief Returns the number of the items mapped to true. 170 /// 171 /// Returns the number of the items mapped to true. 172 int trueNum() const { 173 return sep; 174 } 175 176 /// \brief Returns the number of the items mapped to false. 177 /// 178 /// Returns the number of the items mapped to false. 179 int falseNum() const { 180 return array.size()  sep; 181 } 182 183 /// \brief Iterator for the keys mapped to true. 184 /// 185 /// Iterator for the keys mapped to true. It works 186 /// like a graph item iterator in the map, it can be converted 187 /// the item type of the map, incremented with \c ++ operator, and 188 /// if the iterator leave the last valid item it will be equal to 189 /// \c INVALID. 190 class TrueIt : public Item { 191 public: 192 typedef Item Parent; 193 194 /// \brief Creates an iterator. 195 /// 196 /// Creates an iterator. It iterates on the 197 /// keys which mapped to true. 198 /// \param map The IterableIntMap 199 TrueIt(const IterableBoolMap& _map) 200 : Parent(_map.sep > 0 ? _map.array[_map.sep  1] : INVALID), 201 map(&_map) {} 202 203 /// \brief Invalid constructor \& conversion. 204 /// 205 /// This constructor initializes the item to be invalid. 206 /// \sa Invalid for more details. 207 TrueIt(Invalid) : Parent(INVALID), map(0) {} 208 209 /// \brief Increment operator. 210 /// 211 /// Increment Operator. 212 TrueIt& operator++() { 213 int pos = map>position(*this); 214 Parent::operator=(pos > 0 ? map>array[pos  1] : INVALID); 215 return *this; 216 } 217 218 219 private: 220 const IterableBoolMap* map; 221 }; 222 223 /// \brief Iterator for the keys mapped to false. 224 /// 225 /// Iterator for the keys mapped to false. It works 226 /// like a graph item iterator in the map, it can be converted 227 /// the item type of the map, incremented with \c ++ operator, and 228 /// if the iterator leave the last valid item it will be equal to 229 /// \c INVALID. 230 class FalseIt : public Item { 231 public: 232 typedef Item Parent; 233 234 /// \brief Creates an iterator. 235 /// 236 /// Creates an iterator. It iterates on the 237 /// keys which mapped to false. 238 /// \param map The IterableIntMap 239 FalseIt(const IterableBoolMap& _map) 240 : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID), 241 map(&_map) {} 242 243 /// \brief Invalid constructor \& conversion. 244 /// 245 /// This constructor initializes the item to be invalid. 246 /// \sa Invalid for more details. 247 FalseIt(Invalid) : Parent(INVALID), map(0) {} 248 249 /// \brief Increment operator. 250 /// 251 /// Increment Operator. 252 FalseIt& operator++() { 253 int pos = map>position(*this); 254 Parent::operator=(pos > map>sep ? map>array[pos  1] : INVALID); 255 return *this; 256 } 257 258 private: 259 const IterableBoolMap* map; 260 }; 261 262 protected: 263 264 virtual void add(const Item& item) { 265 Parent::add(item); 266 Parent::set(item, array.size()); 267 array.push_back(item); 268 } 269 270 virtual void add(const std::vector<Item>& items) { 271 Parent::add(items); 272 for (int i = 0; i < (int)items.size(); ++i) { 273 Parent::set(items[i], array.size()); 274 array.push_back(items[i]); 275 } 276 } 277 278 virtual void erase(const Item& item) { 279 int pos = position(item); 280 if (pos < sep) { 281 sep; 282 Parent::set(array[sep], pos); 283 array[pos] = array[sep]; 284 Parent::set(array.back(), sep); 285 array[sep] = array.back(); 286 array.pop_back(); 287 } else { 288 Parent::set(array.back(), pos); 289 array[pos] = array.back(); 290 array.pop_back(); 291 } 292 Parent::erase(item); 293 } 294 295 virtual void erase(const std::vector<Item>& items) { 296 for (int i = 0; i < (int)items.size(); ++i) { 297 int pos = position(items[i]); 298 if (pos < sep) { 299 sep; 300 Parent::set(array[sep], pos); 301 array[pos] = array[sep]; 302 Parent::set(array.back(), sep); 303 array[sep] = array.back(); 304 array.pop_back(); 305 } else { 306 Parent::set(array.back(), pos); 307 array[pos] = array.back(); 308 array.pop_back(); 309 } 310 } 311 Parent::erase(items); 312 } 313 314 virtual void build() { 315 Parent::build(); 316 for (ItemIt it(graph); it != INVALID; ++it) { 317 Parent::set(it, array.size()); 318 array.push_back(it); 319 } 320 sep = 0; 321 } 322 323 virtual void clear() { 324 array.clear(); 325 sep = 0; 326 Parent::clear(); 327 } 328 329 }; 31 330 32 ///\todo This is only a static map!33 ///\todo Undocumented.34 ///\param BaseMap is an interger map.35 template<class BaseMap>36 class IterableBoolMap37 {38 public:39 40 typedef typename BaseMap::Key Key;41 typedef bool Value;42 43 friend class RefType;44 friend class FalseIt;45 friend class TrueIt;46 47 private:48 BaseMap &cref;49 std::vector<Key> vals;50 int sep; //map[e] is true <=> cref[e]>=sep51 52 bool isTrue(Key k) {return cref[k]>=sep;}53 void swap(Key k, int s)54 {55 int ti=cref[k];56 Key tk=vals[s];57 cref[k]=s; vals[s]=k;58 cref[tk]=ti; vals[ti]=tk;59 }60 61 void setTrue(Key k) { if(cref[k]<sep) { sep; swap(k,sep); } }62 void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }63 64 public:65 ///\e66 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}67 ///Number of \c true items in the map68 69 ///Returns the number of \c true values in the map.70 ///This is a constant time operation.71 int countTrue() { return vals.size()sep; }72 ///Number of \c false items in the map73 74 ///Returns the number of \c false values in the map.75 ///This is a constant time operation.76 int countFalse() { return sep; }77 78 ///\e79 class FalseIt80 {81 const IterableBoolMap &M;82 int i;83 public:84 ///\e85 explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }86 ///\e87 FalseIt(Invalid)88 : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }89 ///\e90 FalseIt &operator++() { ++i; return *this;}91 ///\e92 operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }93 ///\e94 bool operator !=(Invalid) const { return i<M.sep; }95 ///\e96 bool operator ==(Invalid) const { return i>=M.sep; }97 };98 ///\e99 class TrueIt100 {101 const IterableBoolMap &M;102 int i;103 public:104 ///\e105 explicit TrueIt(const IterableBoolMap &_M)106 : M(_M), i(M.vals.size()1) { }107 ///\e108 TrueIt(Invalid)109 : M(*((IterableBoolMap*)(0))), i(1) { }110 ///\e111 TrueIt &operator++() { i; return *this;}112 ///\e113 operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }114 ///\e115 bool operator !=(Invalid) const { return i>=M.sep; }116 ///\e117 bool operator ==(Invalid) const { return i<M.sep; }118 };119 120 ///\e121 class RefType122 {123 IterableBoolMap &M;124 Key k;125 public:126 RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }127 128 operator Value() const129 {130 return M.isTrue(k);131 }132 Value operator = (Value v) const { M.set(k,v); return v; }133 };134 135 public:136 explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)137 {138 sep=0;139 for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) {140 i.set(sep);141 vals.push_back(i);142 sep++;143 }144 if(init) sep=0;145 }146 ///\e147 RefType operator[] (Key k) { return RefType(*this,k);}148 ///\e149 Value operator[] (Key k) const { return isTrue(k);}150 };151 152 153 154 155 /// \addtogroup graph_maps156 /// @{157 158 /// Iterable bool NodeMap159 160 /// This map can be used in the same way161 /// as the standard NodeMap<bool> of the162 /// given graph \c Graph.163 /// In addition, this class provides two iterators called \ref TrueIt164 /// and \ref FalseIt to iterate through the "true" and "false" nodes.165 template <class Graph>166 class IterableBoolNodeMap167 {168 typename Graph::template NodeMap<int> cmap;169 170 public:171 172 typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;173 BimType imap;174 175 176 typedef typename BimType::RefType RefType;177 typedef typename Graph::Node Key;178 typedef bool Value;179 180 friend class FalseIt;181 friend class TrueIt;182 183 ///\e184 IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}185 186 public:187 ///\e188 void set(Key k, bool v) { imap.set(k,v);}189 ///Number of \c true items in the map190 191 ///Returns the number of \c true values in the map.192 ///This is a constant time operation.193 int countTrue() { return imap.countTrue(); }194 ///Number of \c false items in the map195 196 ///Returns the number of \c false values in the map.197 ///This is a constant time operation.198 int countFalse() { return imap.countFalse(); }199 #ifdef DOXYGEN200 ///\e201 bool &operator[](Key k) { return imap[k];}202 ///\e203 const bool &operator[](Key k) const { return imap[k];}204 #else205 Value operator[](Key k) const { return imap[k];}206 RefType operator[](Key k) { return imap[k];}207 #endif208 ///Iterator for the "false" nodes209 class FalseIt : public BimType::FalseIt210 {211 public:212 ///\e213 explicit FalseIt(const IterableBoolNodeMap &m)214 : BimType::FalseIt(m.imap) { }215 ///\e216 FalseIt(Invalid i) : BimType::FalseIt(i) { }217 };218 ///Iterator for the "true" nodes219 class TrueIt : public BimType::TrueIt220 {221 public:222 ///\e223 explicit TrueIt(const IterableBoolNodeMap &m)224 : BimType::TrueIt(m.imap) { }225 ///\e226 TrueIt(Invalid i) : BimType::TrueIt(i) { }227 };228 };229 230 /// Iterable bool UpperNodeMap231 232 /// This map can be used in the same way233 /// as the standard UpperNodeMap<bool> of the234 /// given graph \c Graph.235 /// In addition, this class provides two iterators called \ref TrueIt236 /// and \ref FalseIt to iterate through the "true" and "false" nodes.237 template <class Graph>238 class IterableBoolUpperNodeMap239 {240 typename Graph::template UpperNodeMap<int> cmap;241 242 public:243 244 typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;245 BimType imap;246 247 248 typedef typename BimType::RefType RefType;249 typedef typename Graph::Node Key;250 typedef bool Value;251 252 friend class FalseIt;253 friend class TrueIt;254 255 ///\e256 IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}257 258 public:259 ///\e260 void set(Key k, bool v) { imap.set(k,v);}261 ///Number of \c true items in the map262 263 ///Returns the number of \c true values in the map.264 ///This is a constant time operation.265 int countTrue() { return imap.countTrue(); }266 ///Number of \c false items in the map267 268 ///Returns the number of \c false values in the map.269 ///This is a constant time operation.270 int countFalse() { return imap.countFalse(); }271 #ifdef DOXYGEN272 ///\e273 bool &operator[](Key k) { return imap[k];}274 ///\e275 const bool &operator[](Key k) const { return imap[k];}276 #else277 Value operator[](Key k) const { return imap[k];}278 RefType operator[](Key k) { return imap[k];}279 #endif280 ///Iterator for the "false" nodes281 class FalseIt : public BimType::FalseIt282 {283 public:284 ///\e285 explicit FalseIt(const IterableBoolUpperNodeMap &m)286 : BimType::FalseIt(m.imap) { }287 ///\e288 FalseIt(Invalid i) : BimType::FalseIt(i) { }289 };290 ///Iterator for the "true" nodes291 class TrueIt : public BimType::TrueIt292 {293 public:294 ///\e295 explicit TrueIt(const IterableBoolUpperNodeMap &m)296 : BimType::TrueIt(m.imap) { }297 ///\e298 TrueIt(Invalid i) : BimType::TrueIt(i) { }299 };300 };301 302 /// Iterable bool LowerNodeMap303 304 /// This map can be used in the same way305 /// as the standard LowerNodeMap<bool> of the306 /// given graph \c Graph.307 /// In addition, this class provides two iterators called \ref TrueIt308 /// and \ref FalseIt to iterate through the "true" and "false" nodes.309 template <class Graph>310 class IterableBoolLowerNodeMap311 {312 typename Graph::template LowerNodeMap<int> cmap;313 314 public:315 316 typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;317 BimType imap;318 319 320 typedef typename BimType::RefType RefType;321 typedef typename Graph::Node Key;322 typedef bool Value;323 324 friend class FalseIt;325 friend class TrueIt;326 327 ///\e328 IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}329 330 public:331 ///\e332 void set(Key k, bool v) { imap.set(k,v);}333 ///Number of \c true items in the map334 335 ///Returns the number of \c true values in the map.336 ///This is a constant time operation.337 int countTrue() { return imap.countTrue(); }338 ///Number of \c false items in the map339 340 ///Returns the number of \c false values in the map.341 ///This is a constant time operation.342 int countFalse() { return imap.countFalse(); }343 #ifdef DOXYGEN344 ///\e345 bool &operator[](Key k) { return imap[k];}346 ///\e347 const bool &operator[](Key k) const { return imap[k];}348 #else349 Value operator[](Key k) const { return imap[k];}350 RefType operator[](Key k) { return imap[k];}351 #endif352 ///Iterator for the "false" nodes353 class FalseIt : public BimType::FalseIt354 {355 public:356 ///\e357 explicit FalseIt(const IterableBoolLowerNodeMap &m)358 : BimType::FalseIt(m.imap) { }359 ///\e360 FalseIt(Invalid i) : BimType::FalseIt(i) { }361 };362 ///Iterator for the "true" nodes363 class TrueIt : public BimType::TrueIt364 {365 public:366 ///\e367 explicit TrueIt(const IterableBoolLowerNodeMap &m)368 : BimType::TrueIt(m.imap) { }369 ///\e370 TrueIt(Invalid i) : BimType::TrueIt(i) { }371 };372 };373 374 /// Iterable bool EdgeMap375 376 /// This map can be used in the same way377 /// as the standard EdgeMap<bool> of the378 /// given graph \c Graph.379 /// In addition, this class provides two iterators called \ref TrueIt380 /// and \ref FalseIt to iterate through the "true" and "false" edges.381 template <class Graph>382 class IterableBoolEdgeMap383 {384 typename Graph::template EdgeMap<int> cmap;385 386 public:387 388 typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;389 BimType imap;390 391 392 typedef typename BimType::RefType RefType;393 typedef typename Graph::Edge Key;394 typedef bool Value;395 396 friend class FalseIt;397 friend class TrueIt;398 399 ///\e400 IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}401 402 public:403 ///\e404 void set(Key k, bool v) { imap.set(k,v);}405 ///Returns the number of \c true values in the map.406 ///This is a constant time operation.407 int countTrue() { return imap.countTrue(); }408 ///Number of \c false items in the map409 410 ///Returns the number of \c false values in the map.411 ///This is a constant time operation.412 int countFalse() { return imap.countFalse(); }413 #ifdef DOXYGEN414 ///\e415 bool &operator[](Key k) { return imap[k];}416 ///\e417 const bool &operator[](Key k) const { return imap[k];}418 #else419 Value operator[](Key k) const { return imap[k];}420 RefType operator[](Key k) { return imap[k];}421 #endif422 ///Iterator for the "false" edges423 class FalseIt : public BimType::FalseIt424 {425 public:426 ///\e427 explicit FalseIt(const IterableBoolEdgeMap &m)428 : BimType::FalseIt(m.imap) { }429 ///\e430 FalseIt(Invalid i) : BimType::FalseIt(i) { }431 };432 ///Iterator for the "true" edges433 class TrueIt : public BimType::TrueIt434 {435 public:436 ///\e437 explicit TrueIt(const IterableBoolEdgeMap &m)438 : BimType::TrueIt(m.imap) { }439 ///\e440 TrueIt(Invalid i) : BimType::TrueIt(i) { }441 };442 };443 444 331 445 332 namespace _iterable_maps_bits { 446 333 template <typename Item> 447 334 struct IterableIntMapNode { 448 IterableIntMapNode() {}335 IterableIntMapNode() : value(1) {} 449 336 IterableIntMapNode(int _value) : value(_value) {} 450 337 Item prev, next; … … 483 370 /// Constructor of the Map. It set all values 1. 484 371 explicit IterableIntMap(const Graph& graph) 485 : Parent(graph , _iterable_maps_bits::IterableIntMapNode<_Item>(1)) {}372 : Parent(graph) {} 486 373 487 374 /// \brief Constructor of the Map with a given value. … … 707 594 } 708 595 596 virtual void erase(const std::vector<Key>& keys) { 597 for (int i = 0; i < keys.size(); ++i) { 598 unlace(keys[i]); 599 } 600 Parent::erase(keys); 601 } 602 709 603 virtual void clear() { 710 604 first.clear();
Note: See TracChangeset
for help on using the changeset viewer.