COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1747:bccf2379b5dd

Last change on this file since 1747:bccf2379b5dd was 1685:5b37a10234bc, checked in by Balazs Dezso, 19 years ago

Some bugfixes

File size: 6.4 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 <vector>
18#include <limits>
19
20///\ingroup maps
21///\file
22///\brief Maps that makes it possible to iterate through the keys having
23///a certain value
24///
25///
26
27
28namespace lemon {
29 
30  ///\todo This is only a static map!
31  ///\param BaseMap is an interger map.
32  template<class BaseMap>
33  class IterableBoolMap
34  {
35  public:
36 
37    typedef typename BaseMap::Key Key;
38    typedef bool Value;
39 
40    friend class RefType;
41    friend class FalseIt;
42    friend class TrueIt;
43
44  private:
45    BaseMap &cref;
46    std::vector<Key> vals;
47    int sep;           //map[e] is true <=> cref[e]>=sep
48 
49    bool isTrue(Key k) {return cref[k]>=sep;}
50    void swap(Key k, int s)
51    {
52      int ti=cref[k];
53      Key tk=vals[s];
54      cref[k]=s; vals[s]=k;
55      cref[tk]=ti; vals[ti]=tk;
56    } 
57
58    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
59    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
60 
61  public:
62    ///\e
63    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
64
65    ///\e
66    class FalseIt
67    {
68      const IterableBoolMap &M;
69      int i;
70    public:
71      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
72      FalseIt(Invalid)
73        : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
74      FalseIt &operator++() { ++i; return *this;}
75      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
76      bool operator !=(Invalid) const { return i<M.sep; }
77      bool operator ==(Invalid) const { return i>=M.sep; }
78    };
79    ///\e
80    class TrueIt
81    {
82      const IterableBoolMap &M;
83      int i;
84    public:
85      explicit TrueIt(const IterableBoolMap &_M)
86        : M(_M), i(M.vals.size()-1) { }
87      TrueIt(Invalid)
88        : M(*((IterableBoolMap*)(0))), i(-1) { }
89      TrueIt &operator++() { --i; return *this;}
90      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
91      bool operator !=(Invalid) const { return i>=M.sep; }
92      bool operator ==(Invalid) const { return i<M.sep; }
93    };
94 
95    ///\e
96    class RefType
97    {
98      IterableBoolMap &M;
99      Key k;
100    public:
101      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
102   
103      operator Value() const
104      {
105        return M.isTrue(k);
106      }
107      Value operator = (Value v) const { M.set(k,v); return v; }
108    };
109 
110  public:
111    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
112    {
113      sep=0;
114      for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
115          i!=cref.mapSet().end();
116          ++i) {
117        i->second=sep;
118        vals.push_back(i->first);
119        sep++;
120      }
121      if(init) sep=0;
122    }
123    RefType operator[] (Key k) { return RefType(*this,k);} 
124    Value operator[] (Key k) const { return isTrue(k);} 
125  };
126
127
128
129
130  /// \addtogroup graph_maps
131  /// @{
132
133  /// Iterable bool NodeMap
134
135  /// This map can be used in the same way
136  /// as the standard NodeMap<bool> of the
137  /// given graph \c Graph.
138  /// In addition, this class provides two iterators called \ref TrueIt
139  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
140  template <class Graph>
141  class IterableBoolNodeMap
142  {
143    typename Graph::template NodeMap<int> cmap;
144 
145  public:
146 
147    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
148    BimType imap;
149
150
151    typedef typename BimType::RefType RefType;
152    typedef typename Graph::Node Key;
153    typedef bool Value;
154 
155    friend class FalseIt;
156    friend class TrueIt;
157 
158    ///\e
159    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
160
161  public:
162    ///\e
163    void set(Key k, bool v) { imap.set(k,v);}
164#ifdef DOXYGEN
165    ///\e
166    bool &operator[](Key k) { return imap[k];} 
167    ///\e
168    const bool &operator[](Key k) const { return imap[k];} 
169#else
170    Value operator[](Key k) const { return imap[k];} 
171    RefType operator[](Key k) { return imap[k];} 
172#endif
173    ///Iterator for the "false" nodes
174    class FalseIt : public BimType::FalseIt
175    {
176    public:
177      explicit FalseIt(const IterableBoolNodeMap &m)
178        : BimType::FalseIt(m.imap) { }
179      FalseIt(Invalid i) : BimType::FalseIt(i) { }
180    };
181    ///Iterator for the "true" nodes
182    class TrueIt : public BimType::TrueIt
183    {
184    public:
185      explicit TrueIt(const IterableBoolNodeMap &m)
186        : BimType::TrueIt(m.imap) { }
187      TrueIt(Invalid i) : BimType::TrueIt(i) { }
188    }; 
189  };
190
191  /// Iterable bool EdgeMap
192
193  /// This map can be used in the same way
194  /// as the standard EdgeMap<bool> of the
195  /// given graph \c Graph.
196  /// In addition, this class provides two iterators called \ref TrueIt
197  /// and \ref FalseIt to iterate through the "true" and "false" edges.
198  template <class Graph>
199  class IterableBoolEdgeMap
200  {
201    typename Graph::template EdgeMap<int> cmap;
202 
203  public:
204 
205    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
206    BimType imap;
207
208
209    typedef typename BimType::RefType RefType;
210    typedef typename Graph::Edge Key;
211    typedef bool Value;
212 
213    friend class FalseIt;
214    friend class TrueIt;
215 
216    ///\e
217    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
218
219  public:
220    ///\e
221    void set(Key k, bool v) { imap.set(k,v);}
222#ifdef DOXYGEN
223    ///\e
224    bool &operator[](Key k) { return imap[k];} 
225    ///\e
226    const bool &operator[](Key k) const { return imap[k];} 
227#else
228    Value operator[](Key k) const { return imap[k];} 
229    RefType operator[](Key k) { return imap[k];} 
230#endif
231    ///Iterator for the "false" edges
232    class FalseIt : public BimType::FalseIt
233    {
234    public:
235      explicit FalseIt(const IterableBoolEdgeMap &m)
236        : BimType::FalseIt(m.imap) { }
237      FalseIt(Invalid i) : BimType::FalseIt(i) { }
238    };
239    ///Iterator for the "true" edges
240    class TrueIt : public BimType::TrueIt
241    {
242    public:
243      explicit TrueIt(const IterableBoolEdgeMap &m)
244        : BimType::TrueIt(m.imap) { }
245      TrueIt(Invalid i) : BimType::TrueIt(i) { }
246    }; 
247  };
248
249  /// @}
250}
Note: See TracBrowser for help on using the repository browser.