COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1865:dcefd1d1377f

Last change on this file since 1865:dcefd1d1377f was 1810:474d093466a5, checked in by Balazs Dezso, 14 years ago

Modified iterators on graph maps
Other iterators for not graph maps

File size: 14.9 KB
Line 
1/* -*- C++ -*-
2 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#include <lemon/traits.h>
18#include <lemon/invalid.h>
19#include <vector>
20#include <limits>
21
22///\ingroup maps
23///\file
24///\brief Maps that makes it possible to iterate through the keys having
25///a certain value
26///
27///
28
29
30namespace lemon {
31 
32  ///\todo This is only a static map!
33  ///\todo Undocumented.
34  ///\param BaseMap is an interger map.
35  template<class BaseMap>
36  class IterableBoolMap
37  {
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]>=sep
51 
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    ///\e
66    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
67    ///Number of \c true items in the map
68
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
73
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    ///\e
79    class FalseIt
80    {
81      const IterableBoolMap &M;
82      int i;
83    public:
84      ///\e
85      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
86      ///\e
87      FalseIt(Invalid)
88        : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
89      ///\e
90      FalseIt &operator++() { ++i; return *this;}
91      ///\e
92      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
93      ///\e
94      bool operator !=(Invalid) const { return i<M.sep; }
95      ///\e
96      bool operator ==(Invalid) const { return i>=M.sep; }
97    };
98    ///\e
99    class TrueIt
100    {
101      const IterableBoolMap &M;
102      int i;
103    public:
104      ///\e
105      explicit TrueIt(const IterableBoolMap &_M)
106        : M(_M), i(M.vals.size()-1) { }
107      ///\e
108      TrueIt(Invalid)
109        : M(*((IterableBoolMap*)(0))), i(-1) { }
110      ///\e
111      TrueIt &operator++() { --i; return *this;}
112      ///\e
113      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
114      ///\e
115      bool operator !=(Invalid) const { return i>=M.sep; }
116      ///\e
117      bool operator ==(Invalid) const { return i<M.sep; }
118    };
119 
120    ///\e
121    class RefType
122    {
123      IterableBoolMap &M;
124      Key k;
125    public:
126      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
127   
128      operator Value() const
129      {
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    ///\e
147    RefType operator[] (Key k) { return RefType(*this,k);} 
148    ///\e
149    Value operator[] (Key k) const { return isTrue(k);} 
150  };
151
152
153
154
155  /// \addtogroup graph_maps
156  /// @{
157
158  /// Iterable bool NodeMap
159
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
167  {
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    ///\e
184    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
185
186  public:
187    ///\e
188    void set(Key k, bool v) { imap.set(k,v);}
189    ///Number of \c true items in the map
190
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
195
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 DOXYGEN
200    ///\e
201    bool &operator[](Key k) { return imap[k];} 
202    ///\e
203    const bool &operator[](Key k) const { return imap[k];} 
204#else
205    Value operator[](Key k) const { return imap[k];} 
206    RefType operator[](Key k) { return imap[k];} 
207#endif
208    ///Iterator for the "false" nodes
209    class FalseIt : public BimType::FalseIt
210    {
211    public:
212      ///\e
213      explicit FalseIt(const IterableBoolNodeMap &m)
214        : BimType::FalseIt(m.imap) { }
215      ///\e
216      FalseIt(Invalid i) : BimType::FalseIt(i) { }
217    };
218    ///Iterator for the "true" nodes
219    class TrueIt : public BimType::TrueIt
220    {
221    public:
222      ///\e
223      explicit TrueIt(const IterableBoolNodeMap &m)
224        : BimType::TrueIt(m.imap) { }
225      ///\e
226      TrueIt(Invalid i) : BimType::TrueIt(i) { }
227    }; 
228  };
229
230  /// Iterable bool EdgeMap
231
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
239  {
240    typename Graph::template EdgeMap<int> cmap;
241 
242  public:
243 
244    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
245    BimType imap;
246
247
248    typedef typename BimType::RefType RefType;
249    typedef typename Graph::Edge Key;
250    typedef bool Value;
251 
252    friend class FalseIt;
253    friend class TrueIt;
254 
255    ///\e
256    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
257
258  public:
259    ///\e
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
265
266    ///Returns the number of \c false values in the map.
267    ///This is a constant time operation.
268    int countFalse() { return imap.countFalse(); }
269#ifdef DOXYGEN
270    ///\e
271    bool &operator[](Key k) { return imap[k];} 
272    ///\e
273    const bool &operator[](Key k) const { return imap[k];} 
274#else
275    Value operator[](Key k) const { return imap[k];} 
276    RefType operator[](Key k) { return imap[k];} 
277#endif
278    ///Iterator for the "false" edges
279    class FalseIt : public BimType::FalseIt
280    {
281    public:
282      ///\e
283      explicit FalseIt(const IterableBoolEdgeMap &m)
284        : BimType::FalseIt(m.imap) { }
285      ///\e
286      FalseIt(Invalid i) : BimType::FalseIt(i) { }
287    };
288    ///Iterator for the "true" edges
289    class TrueIt : public BimType::TrueIt
290    {
291    public:
292      ///\e
293      explicit TrueIt(const IterableBoolEdgeMap &m)
294        : BimType::TrueIt(m.imap) { }
295      ///\e
296      TrueIt(Invalid i) : BimType::TrueIt(i) { }
297    }; 
298  };
299
300
301  namespace _iterable_maps_bits {
302    template <typename Item>
303    struct IterableIntMapNode {
304      IterableIntMapNode() {}
305      IterableIntMapNode(int _value) : value(_value) {}
306      Item prev, next;
307      int value;
308    };
309  }
310
311  ///\ingroup maps
312  ///
313  /// \brief Dynamic iterable integer map.
314  ///
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.
319  ///
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 {
325  public:
326    typedef typename ItemSetTraits<_Graph, _Item>
327    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
328    ::Parent Parent;
329
330    /// The key type
331    typedef _Item Key;
332    /// The value type
333    typedef int Value;
334    /// The graph type
335    typedef _Graph Graph;
336
337    /// \brief Constructor of the Map.
338    ///
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)) {}
342
343    /// \brief Constructor of the Map with a given value.
344    ///
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)) {
348      if (value >= 0) {
349        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
350          lace(it);
351        }
352      }
353    }
354
355  private:
356   
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;
362      } else {
363        first[node.value] = node.next;
364      }
365      if (node.next != INVALID) {
366        Parent::operator[](node.next).prev = node.prev;
367      }
368      while (!first.empty() && first.back() == INVALID) {
369        first.pop_back();
370      }
371    }
372
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);
378      }
379      node.prev = INVALID;
380      node.next = first[node.value];
381      if (node.next != INVALID) {
382        Parent::operator[](node.next).prev = key;       
383      }
384      first[node.value] = key;
385    }
386
387  public:
388
389    /// Indicates that the map if reference map.
390    typedef True ReferenceMapTag;
391
392    /// \brief Refernce to the value of the map.
393    ///
394    /// This class is near to similar to the int type. It can
395    /// be converted to int and it has the same operators.
396    class Reference {
397      friend class IterableIntMap;
398    private:
399      Reference(IterableIntMap& map, const Key& key)
400        : _key(key), _map(map) {}
401    public:
402
403      Reference& operator=(const Reference& value) {
404        _map.set(_key, (const int&)value);
405        return *this;
406      }
407
408      operator const int&() const {
409        return static_cast<const IterableIntMap&>(_map)[_key];
410      }
411
412      Reference& operator=(int value) {
413        _map.set(_key, value);
414        return *this;
415      }
416      Reference& operator++() {
417        _map.set(_key, _map[_key] + 1);
418        return *this;   
419      }
420      int operator++(int) {
421        int value = _map[_key];
422        _map.set(_key, value + 1);
423        return value;   
424      }
425      Reference& operator--() {
426        _map.set(_key, _map[_key] - 1);
427        return *this;   
428      }
429      int operator--(int) {
430        int value = _map[_key];
431        _map.set(_key, value - 1);
432        return value;   
433      }
434      Reference& operator+=(int value) {
435        _map.set(_key, _map[_key] + value);
436        return *this;
437      }
438      Reference& operator-=(int value) {
439        _map.set(_key, _map[_key] - value);
440        return *this;
441      }
442      Reference& operator*=(int value) {
443        _map.set(_key, _map[_key] * value);
444        return *this;
445      }
446      Reference& operator/=(int value) {
447        _map.set(_key, _map[_key] / value);
448        return *this;
449      }
450      Reference& operator%=(int value) {
451        _map.set(_key, _map[_key] % value);
452        return *this;
453      }
454      Reference& operator&=(int value) {
455        _map.set(_key, _map[_key] & value);
456        return *this;
457      }
458      Reference& operator|=(int value) {
459        _map.set(_key, _map[_key] | value);
460        return *this;
461      }
462      Reference& operator^=(int value) {
463        _map.set(_key, _map[_key] ^ value);
464        return *this;
465      }
466      Reference& operator<<=(int value) {
467        _map.set(_key, _map[_key] << value);
468        return *this;
469      }
470      Reference& operator>>=(int value) {
471        _map.set(_key, _map[_key] >> value);
472        return *this;
473      }
474
475    private:
476      Key _key;
477      IterableIntMap& _map;
478    };
479
480    /// The const reference type.   
481    typedef const Value& ConstReference;
482
483    /// \brief Gives back the maximal value plus one.
484    ///
485    /// Gives back the maximal value plus one.
486    int size() const {
487      return (int)first.size();
488    }
489   
490    /// \brief Set operation of the map.
491    ///
492    /// Set operation of the map.
493    void set(const Key& key, const Value& value) {
494      unlace(key);
495      Parent::operator[](key).value = value;
496      lace(key);
497    }
498
499    /// \brief Const subscript operator of the map.
500    ///
501    /// Const subscript operator of the map.
502    const Value& operator[](const Key& key) const {
503      return Parent::operator[](key).value;
504    }
505
506    /// \brief Subscript operator of the map.
507    ///
508    /// Subscript operator of the map.
509    Reference operator[](const Key& key) {
510      return Reference(*this, key);
511    }
512
513    /// \brief Iterator for the keys with the same value.
514    ///
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
519    /// \c INVALID.
520    class ItemIt : public _Item {
521    public:
522      typedef _Item Parent;
523
524      /// \brief Invalid constructor \& conversion.
525      ///
526      /// This constructor initializes the item to be invalid.
527      /// \sa Invalid for more details.
528      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
529
530      /// \brief Creates an iterator with a value.
531      ///
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);
539        } else {
540          Parent::operator=(_map->first[value]);
541        }
542      }
543
544      /// \brief Increment operator.
545      ///
546      /// Increment Operator.
547      ItemIt& operator++() {
548        Parent::operator=(_map->IterableIntMap::Parent::
549                          operator[](static_cast<Parent&>(*this)).next);
550        return *this;
551      }
552
553
554    private:
555      const IterableIntMap* _map;
556    };
557
558  protected:
559   
560    virtual void erase(const Key& key) {
561      unlace(key);
562      Parent::erase(key);
563    }
564
565    virtual void clear() {
566      first.clear();
567      Parent::clear();
568    }
569
570  private:
571    std::vector<_Item> first;
572  };
573
574  /// @}
575}
Note: See TracBrowser for help on using the repository browser.