NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #include <lemon/traits.h>
18 #include <lemon/invalid.h>
24 ///\brief Maps that makes it possible to iterate through the keys having
32 ///\todo This is only a static map!
33 ///\todo Undocumented.
34 ///\param BaseMap is an interger map.
35 template<class BaseMap>
40 typedef typename BaseMap::Key Key;
49 std::vector<Key> vals;
50 int sep; //map[e] is true <=> cref[e]>=sep
52 bool isTrue(Key k) {return cref[k]>=sep;}
53 void swap(Key k, int s)
58 cref[tk]=ti; vals[ti]=tk;
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++; } }
66 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
67 ///Number of \c true items in the map
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 map
74 ///Returns the number of \c false values in the map.
75 ///This is a constant time operation.
76 int countFalse() { return sep; }
81 const IterableBoolMap &M;
85 explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
88 : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
90 FalseIt &operator++() { ++i; return *this;}
92 operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
94 bool operator !=(Invalid) const { return i<M.sep; }
96 bool operator ==(Invalid) const { return i>=M.sep; }
101 const IterableBoolMap &M;
105 explicit TrueIt(const IterableBoolMap &_M)
106 : M(_M), i(M.vals.size()-1) { }
109 : M(*((IterableBoolMap*)(0))), i(-1) { }
111 TrueIt &operator++() { --i; return *this;}
113 operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
115 bool operator !=(Invalid) const { return i>=M.sep; }
117 bool operator ==(Invalid) const { return i<M.sep; }
126 RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
128 operator Value() const
132 Value operator = (Value v) const { M.set(k,v); return v; }
136 explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
139 for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) {
147 RefType operator[] (Key k) { return RefType(*this,k);}
149 Value operator[] (Key k) const { return isTrue(k);}
155 /// \addtogroup graph_maps
158 /// Iterable bool NodeMap
160 /// This map can be used in the same way
161 /// as the standard NodeMap<bool> of the
162 /// given graph \c Graph.
163 /// In addition, this class provides two iterators called \ref TrueIt
164 /// and \ref FalseIt to iterate through the "true" and "false" nodes.
165 template <class Graph>
166 class IterableBoolNodeMap
168 typename Graph::template NodeMap<int> cmap;
172 typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
176 typedef typename BimType::RefType RefType;
177 typedef typename Graph::Node Key;
180 friend class FalseIt;
184 IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
188 void set(Key k, bool v) { imap.set(k,v);}
189 ///Number of \c true items in the map
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 map
196 ///Returns the number of \c false values in the map.
197 ///This is a constant time operation.
198 int countFalse() { return imap.countFalse(); }
201 bool &operator[](Key k) { return imap[k];}
203 const bool &operator[](Key k) const { return imap[k];}
205 Value operator[](Key k) const { return imap[k];}
206 RefType operator[](Key k) { return imap[k];}
208 ///Iterator for the "false" nodes
209 class FalseIt : public BimType::FalseIt
213 explicit FalseIt(const IterableBoolNodeMap &m)
214 : BimType::FalseIt(m.imap) { }
216 FalseIt(Invalid i) : BimType::FalseIt(i) { }
218 ///Iterator for the "true" nodes
219 class TrueIt : public BimType::TrueIt
223 explicit TrueIt(const IterableBoolNodeMap &m)
224 : BimType::TrueIt(m.imap) { }
226 TrueIt(Invalid i) : BimType::TrueIt(i) { }
230 /// Iterable bool EdgeMap
232 /// This map can be used in the same way
233 /// as the standard EdgeMap<bool> of the
234 /// given graph \c Graph.
235 /// In addition, this class provides two iterators called \ref TrueIt
236 /// and \ref FalseIt to iterate through the "true" and "false" edges.
237 template <class Graph>
238 class IterableBoolEdgeMap
240 typename Graph::template EdgeMap<int> cmap;
244 typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
248 typedef typename BimType::RefType RefType;
249 typedef typename Graph::Edge Key;
252 friend class FalseIt;
256 IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
260 void set(Key k, bool v) { imap.set(k,v);}
261 ///Returns the number of \c true values in the map.
262 ///This is a constant time operation.
263 int countTrue() { return imap.countTrue(); }
264 ///Number of \c false items in the map
266 ///Returns the number of \c false values in the map.
267 ///This is a constant time operation.
268 int countFalse() { return imap.countFalse(); }
271 bool &operator[](Key k) { return imap[k];}
273 const bool &operator[](Key k) const { return imap[k];}
275 Value operator[](Key k) const { return imap[k];}
276 RefType operator[](Key k) { return imap[k];}
278 ///Iterator for the "false" edges
279 class FalseIt : public BimType::FalseIt
283 explicit FalseIt(const IterableBoolEdgeMap &m)
284 : BimType::FalseIt(m.imap) { }
286 FalseIt(Invalid i) : BimType::FalseIt(i) { }
288 ///Iterator for the "true" edges
289 class TrueIt : public BimType::TrueIt
293 explicit TrueIt(const IterableBoolEdgeMap &m)
294 : BimType::TrueIt(m.imap) { }
296 TrueIt(Invalid i) : BimType::TrueIt(i) { }
301 namespace _iterable_maps_bits {
302 template <typename Item>
303 struct IterableIntMapNode {
304 IterableIntMapNode() {}
305 IterableIntMapNode(int _value) : value(_value) {}
313 /// \brief Dynamic iterable integer map.
315 /// This class provides a special graph map type which can store
316 /// for each graph item(node, edge, etc.) an integer value. For each
317 /// non negative value it is possible to iterate on the keys which
318 /// mapped to the given value.
320 /// \param _Graph The graph type.
321 /// \param _Item One of the graph's item type, the key of the map.
322 template <typename _Graph, typename _Item>
323 class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
324 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
326 typedef typename ItemSetTraits<_Graph, _Item>
327 ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
335 typedef _Graph Graph;
337 /// \brief Constructor of the Map.
339 /// Constructor of the Map. It set all values -1.
340 explicit IterableIntMap(const Graph& graph)
341 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}
343 /// \brief Constructor of the Map with a given value.
345 /// Constructor of the Map with a given value.
346 explicit IterableIntMap(const Graph& graph, int value)
347 : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
349 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
357 void unlace(const Key& key) {
358 typename Parent::Value& node = Parent::operator[](key);
359 if (node.value < 0) return;
360 if (node.prev != INVALID) {
361 Parent::operator[](node.prev).next = node.next;
363 first[node.value] = node.next;
365 if (node.next != INVALID) {
366 Parent::operator[](node.next).prev = node.prev;
368 while (!first.empty() && first.back() == INVALID) {
373 void lace(const Key& key) {
374 typename Parent::Value& node = Parent::operator[](key);
375 if (node.value < 0) return;
376 if (node.value >= (int)first.size()) {
377 first.resize(node.value + 1, INVALID);
380 node.next = first[node.value];
381 if (node.next != INVALID) {
382 Parent::operator[](node.next).prev = key;
384 first[node.value] = key;
389 /// Indicates that the map if reference map.
390 typedef True ReferenceMapTag;
392 /// \brief Refernce to the value of the map.
394 /// This class is near to similar to the int type. It can
395 /// be converted to int and it has the same operators.
397 friend class IterableIntMap;
399 Reference(IterableIntMap& map, const Key& key)
400 : _key(key), _map(map) {}
403 Reference& operator=(const Reference& value) {
404 _map.set(_key, (const int&)value);
408 operator const int&() const {
409 return static_cast<const IterableIntMap&>(_map)[_key];
412 Reference& operator=(int value) {
413 _map.set(_key, value);
416 Reference& operator++() {
417 _map.set(_key, _map[_key] + 1);
420 int operator++(int) {
421 int value = _map[_key];
422 _map.set(_key, value + 1);
425 Reference& operator--() {
426 _map.set(_key, _map[_key] - 1);
429 int operator--(int) {
430 int value = _map[_key];
431 _map.set(_key, value - 1);
434 Reference& operator+=(int value) {
435 _map.set(_key, _map[_key] + value);
438 Reference& operator-=(int value) {
439 _map.set(_key, _map[_key] - value);
442 Reference& operator*=(int value) {
443 _map.set(_key, _map[_key] * value);
446 Reference& operator/=(int value) {
447 _map.set(_key, _map[_key] / value);
450 Reference& operator%=(int value) {
451 _map.set(_key, _map[_key] % value);
454 Reference& operator&=(int value) {
455 _map.set(_key, _map[_key] & value);
458 Reference& operator|=(int value) {
459 _map.set(_key, _map[_key] | value);
462 Reference& operator^=(int value) {
463 _map.set(_key, _map[_key] ^ value);
466 Reference& operator<<=(int value) {
467 _map.set(_key, _map[_key] << value);
470 Reference& operator>>=(int value) {
471 _map.set(_key, _map[_key] >> value);
477 IterableIntMap& _map;
480 /// The const reference type.
481 typedef const Value& ConstReference;
483 /// \brief Gives back the maximal value plus one.
485 /// Gives back the maximal value plus one.
487 return (int)first.size();
490 /// \brief Set operation of the map.
492 /// Set operation of the map.
493 void set(const Key& key, const Value& value) {
495 Parent::operator[](key).value = value;
499 /// \brief Const subscript operator of the map.
501 /// Const subscript operator of the map.
502 const Value& operator[](const Key& key) const {
503 return Parent::operator[](key).value;
506 /// \brief Subscript operator of the map.
508 /// Subscript operator of the map.
509 Reference operator[](const Key& key) {
510 return Reference(*this, key);
513 /// \brief Iterator for the keys with the same value.
515 /// Iterator for the keys with the same value. It works
516 /// like a graph item iterator in the map, it can be converted
517 /// the item type of the map, incremented with \c ++ operator, and
518 /// if the iterator leave the last valid item it will be equal to
520 class ItemIt : public _Item {
522 typedef _Item Parent;
524 /// \brief Invalid constructor \& conversion.
526 /// This constructor initializes the item to be invalid.
527 /// \sa Invalid for more details.
528 ItemIt(Invalid) : Parent(INVALID), _map(0) {}
530 /// \brief Creates an iterator with a value.
532 /// Creates an iterator with a value. It iterates on the
533 /// keys which have the given value.
534 /// \param map The IterableIntMap
535 /// \param value The value
536 ItemIt(const IterableIntMap& map, int value) : _map(&map) {
537 if (value < 0 || value >= (int)_map->first.size()) {
538 Parent::operator=(INVALID);
540 Parent::operator=(_map->first[value]);
544 /// \brief Increment operator.
546 /// Increment Operator.
547 ItemIt& operator++() {
548 Parent::operator=(_map->IterableIntMap::Parent::
549 operator[](static_cast<Parent&>(*this)).next);
555 const IterableIntMap* _map;
560 virtual void erase(const Key& key) {
565 virtual void clear() {
571 std::vector<_Item> first;