COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1874:396831fa7012

Last change on this file since 1874:396831fa7012 was 1873:d73c7f115f53, checked in by Alpar Juttner, 14 years ago

IterableBool?{Upper/Lower?}NodeMaps?

File size: 18.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 UpperNodeMap
231
232  /// This map can be used in the same way
233  /// as the standard UpperNodeMap<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" nodes.
237  template <class Graph>
238  class IterableBoolUpperNodeMap
239  {
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    ///\e
256    IterableBoolUpperNodeMap(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    ///Number of \c true items in the map
262
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 map
267
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 DOXYGEN
272    ///\e
273    bool &operator[](Key k) { return imap[k];} 
274    ///\e
275    const bool &operator[](Key k) const { return imap[k];} 
276#else
277    Value operator[](Key k) const { return imap[k];} 
278    RefType operator[](Key k) { return imap[k];} 
279#endif
280    ///Iterator for the "false" nodes
281    class FalseIt : public BimType::FalseIt
282    {
283    public:
284      ///\e
285      explicit FalseIt(const IterableBoolUpperNodeMap &m)
286        : BimType::FalseIt(m.imap) { }
287      ///\e
288      FalseIt(Invalid i) : BimType::FalseIt(i) { }
289    };
290    ///Iterator for the "true" nodes
291    class TrueIt : public BimType::TrueIt
292    {
293    public:
294      ///\e
295      explicit TrueIt(const IterableBoolUpperNodeMap &m)
296        : BimType::TrueIt(m.imap) { }
297      ///\e
298      TrueIt(Invalid i) : BimType::TrueIt(i) { }
299    }; 
300  };
301
302  /// Iterable bool LowerNodeMap
303
304  /// This map can be used in the same way
305  /// as the standard LowerNodeMap<bool> of the
306  /// given graph \c Graph.
307  /// In addition, this class provides two iterators called \ref TrueIt
308  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
309  template <class Graph>
310  class IterableBoolLowerNodeMap
311  {
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    ///\e
328    IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
329
330  public:
331    ///\e
332    void set(Key k, bool v) { imap.set(k,v);}
333    ///Number of \c true items in the map
334
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 map
339
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 DOXYGEN
344    ///\e
345    bool &operator[](Key k) { return imap[k];} 
346    ///\e
347    const bool &operator[](Key k) const { return imap[k];} 
348#else
349    Value operator[](Key k) const { return imap[k];} 
350    RefType operator[](Key k) { return imap[k];} 
351#endif
352    ///Iterator for the "false" nodes
353    class FalseIt : public BimType::FalseIt
354    {
355    public:
356      ///\e
357      explicit FalseIt(const IterableBoolLowerNodeMap &m)
358        : BimType::FalseIt(m.imap) { }
359      ///\e
360      FalseIt(Invalid i) : BimType::FalseIt(i) { }
361    };
362    ///Iterator for the "true" nodes
363    class TrueIt : public BimType::TrueIt
364    {
365    public:
366      ///\e
367      explicit TrueIt(const IterableBoolLowerNodeMap &m)
368        : BimType::TrueIt(m.imap) { }
369      ///\e
370      TrueIt(Invalid i) : BimType::TrueIt(i) { }
371    }; 
372  };
373
374  /// Iterable bool EdgeMap
375
376  /// This map can be used in the same way
377  /// as the standard EdgeMap<bool> of the
378  /// given graph \c Graph.
379  /// In addition, this class provides two iterators called \ref TrueIt
380  /// and \ref FalseIt to iterate through the "true" and "false" edges.
381  template <class Graph>
382  class IterableBoolEdgeMap
383  {
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    ///\e
400    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
401
402  public:
403    ///\e
404    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 map
409
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 DOXYGEN
414    ///\e
415    bool &operator[](Key k) { return imap[k];} 
416    ///\e
417    const bool &operator[](Key k) const { return imap[k];} 
418#else
419    Value operator[](Key k) const { return imap[k];} 
420    RefType operator[](Key k) { return imap[k];} 
421#endif
422    ///Iterator for the "false" edges
423    class FalseIt : public BimType::FalseIt
424    {
425    public:
426      ///\e
427      explicit FalseIt(const IterableBoolEdgeMap &m)
428        : BimType::FalseIt(m.imap) { }
429      ///\e
430      FalseIt(Invalid i) : BimType::FalseIt(i) { }
431    };
432    ///Iterator for the "true" edges
433    class TrueIt : public BimType::TrueIt
434    {
435    public:
436      ///\e
437      explicit TrueIt(const IterableBoolEdgeMap &m)
438        : BimType::TrueIt(m.imap) { }
439      ///\e
440      TrueIt(Invalid i) : BimType::TrueIt(i) { }
441    }; 
442  };
443
444
445  namespace _iterable_maps_bits {
446    template <typename Item>
447    struct IterableIntMapNode {
448      IterableIntMapNode() {}
449      IterableIntMapNode(int _value) : value(_value) {}
450      Item prev, next;
451      int value;
452    };
453  }
454
455  ///\ingroup maps
456  ///
457  /// \brief Dynamic iterable integer map.
458  ///
459  /// This class provides a special graph map type which can store
460  /// for each graph item(node, edge, etc.) an integer value. For each
461  /// non negative value it is possible to iterate on the keys which
462  /// mapped to the given value.
463  ///
464  /// \param _Graph The graph type.
465  /// \param _Item One of the graph's item type, the key of the map.
466  template <typename _Graph, typename _Item>
467  class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
468  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
469  public:
470    typedef typename ItemSetTraits<_Graph, _Item>
471    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
472    ::Parent Parent;
473
474    /// The key type
475    typedef _Item Key;
476    /// The value type
477    typedef int Value;
478    /// The graph type
479    typedef _Graph Graph;
480
481    /// \brief Constructor of the Map.
482    ///
483    /// Constructor of the Map. It set all values -1.
484    explicit IterableIntMap(const Graph& graph)
485      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}
486
487    /// \brief Constructor of the Map with a given value.
488    ///
489    /// Constructor of the Map with a given value.
490    explicit IterableIntMap(const Graph& graph, int value)
491      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
492      if (value >= 0) {
493        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
494          lace(it);
495        }
496      }
497    }
498
499  private:
500   
501    void unlace(const Key& key) {
502      typename Parent::Value& node = Parent::operator[](key);
503      if (node.value < 0) return;
504      if (node.prev != INVALID) {
505        Parent::operator[](node.prev).next = node.next;
506      } else {
507        first[node.value] = node.next;
508      }
509      if (node.next != INVALID) {
510        Parent::operator[](node.next).prev = node.prev;
511      }
512      while (!first.empty() && first.back() == INVALID) {
513        first.pop_back();
514      }
515    }
516
517    void lace(const Key& key) {
518      typename Parent::Value& node = Parent::operator[](key);
519      if (node.value < 0) return;
520      if (node.value >= (int)first.size()) {
521        first.resize(node.value + 1, INVALID);
522      }
523      node.prev = INVALID;
524      node.next = first[node.value];
525      if (node.next != INVALID) {
526        Parent::operator[](node.next).prev = key;       
527      }
528      first[node.value] = key;
529    }
530
531  public:
532
533    /// Indicates that the map if reference map.
534    typedef True ReferenceMapTag;
535
536    /// \brief Refernce to the value of the map.
537    ///
538    /// This class is near to similar to the int type. It can
539    /// be converted to int and it has the same operators.
540    class Reference {
541      friend class IterableIntMap;
542    private:
543      Reference(IterableIntMap& map, const Key& key)
544        : _key(key), _map(map) {}
545    public:
546
547      Reference& operator=(const Reference& value) {
548        _map.set(_key, (const int&)value);
549        return *this;
550      }
551
552      operator const int&() const {
553        return static_cast<const IterableIntMap&>(_map)[_key];
554      }
555
556      Reference& operator=(int value) {
557        _map.set(_key, value);
558        return *this;
559      }
560      Reference& operator++() {
561        _map.set(_key, _map[_key] + 1);
562        return *this;   
563      }
564      int operator++(int) {
565        int value = _map[_key];
566        _map.set(_key, value + 1);
567        return value;   
568      }
569      Reference& operator--() {
570        _map.set(_key, _map[_key] - 1);
571        return *this;   
572      }
573      int operator--(int) {
574        int value = _map[_key];
575        _map.set(_key, value - 1);
576        return value;   
577      }
578      Reference& operator+=(int value) {
579        _map.set(_key, _map[_key] + value);
580        return *this;
581      }
582      Reference& operator-=(int value) {
583        _map.set(_key, _map[_key] - value);
584        return *this;
585      }
586      Reference& operator*=(int value) {
587        _map.set(_key, _map[_key] * value);
588        return *this;
589      }
590      Reference& operator/=(int value) {
591        _map.set(_key, _map[_key] / value);
592        return *this;
593      }
594      Reference& operator%=(int value) {
595        _map.set(_key, _map[_key] % value);
596        return *this;
597      }
598      Reference& operator&=(int value) {
599        _map.set(_key, _map[_key] & value);
600        return *this;
601      }
602      Reference& operator|=(int value) {
603        _map.set(_key, _map[_key] | value);
604        return *this;
605      }
606      Reference& operator^=(int value) {
607        _map.set(_key, _map[_key] ^ value);
608        return *this;
609      }
610      Reference& operator<<=(int value) {
611        _map.set(_key, _map[_key] << value);
612        return *this;
613      }
614      Reference& operator>>=(int value) {
615        _map.set(_key, _map[_key] >> value);
616        return *this;
617      }
618
619    private:
620      Key _key;
621      IterableIntMap& _map;
622    };
623
624    /// The const reference type.   
625    typedef const Value& ConstReference;
626
627    /// \brief Gives back the maximal value plus one.
628    ///
629    /// Gives back the maximal value plus one.
630    int size() const {
631      return (int)first.size();
632    }
633   
634    /// \brief Set operation of the map.
635    ///
636    /// Set operation of the map.
637    void set(const Key& key, const Value& value) {
638      unlace(key);
639      Parent::operator[](key).value = value;
640      lace(key);
641    }
642
643    /// \brief Const subscript operator of the map.
644    ///
645    /// Const subscript operator of the map.
646    const Value& operator[](const Key& key) const {
647      return Parent::operator[](key).value;
648    }
649
650    /// \brief Subscript operator of the map.
651    ///
652    /// Subscript operator of the map.
653    Reference operator[](const Key& key) {
654      return Reference(*this, key);
655    }
656
657    /// \brief Iterator for the keys with the same value.
658    ///
659    /// Iterator for the keys with the same value. It works
660    /// like a graph item iterator in the map, it can be converted
661    /// the item type of the map, incremented with \c ++ operator, and
662    /// if the iterator leave the last valid item it will be equal to
663    /// \c INVALID.
664    class ItemIt : public _Item {
665    public:
666      typedef _Item Parent;
667
668      /// \brief Invalid constructor \& conversion.
669      ///
670      /// This constructor initializes the item to be invalid.
671      /// \sa Invalid for more details.
672      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
673
674      /// \brief Creates an iterator with a value.
675      ///
676      /// Creates an iterator with a value. It iterates on the
677      /// keys which have the given value.
678      /// \param map The IterableIntMap
679      /// \param value The value
680      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
681        if (value < 0 || value >= (int)_map->first.size()) {     
682          Parent::operator=(INVALID);
683        } else {
684          Parent::operator=(_map->first[value]);
685        }
686      }
687
688      /// \brief Increment operator.
689      ///
690      /// Increment Operator.
691      ItemIt& operator++() {
692        Parent::operator=(_map->IterableIntMap::Parent::
693                          operator[](static_cast<Parent&>(*this)).next);
694        return *this;
695      }
696
697
698    private:
699      const IterableIntMap* _map;
700    };
701
702  protected:
703   
704    virtual void erase(const Key& key) {
705      unlace(key);
706      Parent::erase(key);
707    }
708
709    virtual void clear() {
710      first.clear();
711      Parent::clear();
712    }
713
714  private:
715    std::vector<_Item> first;
716  };
717
718  /// @}
719}
Note: See TracBrowser for help on using the repository browser.