COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1759:0bb3fb3baffd

Last change on this file since 1759:0bb3fb3baffd was 1759:0bb3fb3baffd, checked in by Balazs Dezso, 14 years ago

Increment and decrement operator for IterableIntMap::Reference

File size: 11.2 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  ///\param BaseMap is an interger map.
34  template<class BaseMap>
35  class IterableBoolMap
36  {
37  public:
38 
39    typedef typename BaseMap::Key Key;
40    typedef bool Value;
41 
42    friend class RefType;
43    friend class FalseIt;
44    friend class TrueIt;
45
46  private:
47    BaseMap &cref;
48    std::vector<Key> vals;
49    int sep;           //map[e] is true <=> cref[e]>=sep
50 
51    bool isTrue(Key k) {return cref[k]>=sep;}
52    void swap(Key k, int s)
53    {
54      int ti=cref[k];
55      Key tk=vals[s];
56      cref[k]=s; vals[s]=k;
57      cref[tk]=ti; vals[ti]=tk;
58    } 
59
60    void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
61    void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
62 
63  public:
64    ///\e
65    void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
66
67    ///\e
68    class FalseIt
69    {
70      const IterableBoolMap &M;
71      int i;
72    public:
73      explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
74      FalseIt(Invalid)
75        : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
76      FalseIt &operator++() { ++i; return *this;}
77      operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
78      bool operator !=(Invalid) const { return i<M.sep; }
79      bool operator ==(Invalid) const { return i>=M.sep; }
80    };
81    ///\e
82    class TrueIt
83    {
84      const IterableBoolMap &M;
85      int i;
86    public:
87      explicit TrueIt(const IterableBoolMap &_M)
88        : M(_M), i(M.vals.size()-1) { }
89      TrueIt(Invalid)
90        : M(*((IterableBoolMap*)(0))), i(-1) { }
91      TrueIt &operator++() { --i; return *this;}
92      operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
93      bool operator !=(Invalid) const { return i>=M.sep; }
94      bool operator ==(Invalid) const { return i<M.sep; }
95    };
96 
97    ///\e
98    class RefType
99    {
100      IterableBoolMap &M;
101      Key k;
102    public:
103      RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
104   
105      operator Value() const
106      {
107        return M.isTrue(k);
108      }
109      Value operator = (Value v) const { M.set(k,v); return v; }
110    };
111 
112  public:
113    explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
114    {
115      sep=0;
116      for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
117          i!=cref.mapSet().end();
118          ++i) {
119        i->second=sep;
120        vals.push_back(i->first);
121        sep++;
122      }
123      if(init) sep=0;
124    }
125    RefType operator[] (Key k) { return RefType(*this,k);} 
126    Value operator[] (Key k) const { return isTrue(k);} 
127  };
128
129
130
131
132  /// \addtogroup graph_maps
133  /// @{
134
135  /// Iterable bool NodeMap
136
137  /// This map can be used in the same way
138  /// as the standard NodeMap<bool> of the
139  /// given graph \c Graph.
140  /// In addition, this class provides two iterators called \ref TrueIt
141  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
142  template <class Graph>
143  class IterableBoolNodeMap
144  {
145    typename Graph::template NodeMap<int> cmap;
146 
147  public:
148 
149    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
150    BimType imap;
151
152
153    typedef typename BimType::RefType RefType;
154    typedef typename Graph::Node Key;
155    typedef bool Value;
156 
157    friend class FalseIt;
158    friend class TrueIt;
159 
160    ///\e
161    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
162
163  public:
164    ///\e
165    void set(Key k, bool v) { imap.set(k,v);}
166#ifdef DOXYGEN
167    ///\e
168    bool &operator[](Key k) { return imap[k];} 
169    ///\e
170    const bool &operator[](Key k) const { return imap[k];} 
171#else
172    Value operator[](Key k) const { return imap[k];} 
173    RefType operator[](Key k) { return imap[k];} 
174#endif
175    ///Iterator for the "false" nodes
176    class FalseIt : public BimType::FalseIt
177    {
178    public:
179      explicit FalseIt(const IterableBoolNodeMap &m)
180        : BimType::FalseIt(m.imap) { }
181      FalseIt(Invalid i) : BimType::FalseIt(i) { }
182    };
183    ///Iterator for the "true" nodes
184    class TrueIt : public BimType::TrueIt
185    {
186    public:
187      explicit TrueIt(const IterableBoolNodeMap &m)
188        : BimType::TrueIt(m.imap) { }
189      TrueIt(Invalid i) : BimType::TrueIt(i) { }
190    }; 
191  };
192
193  /// Iterable bool EdgeMap
194
195  /// This map can be used in the same way
196  /// as the standard EdgeMap<bool> of the
197  /// given graph \c Graph.
198  /// In addition, this class provides two iterators called \ref TrueIt
199  /// and \ref FalseIt to iterate through the "true" and "false" edges.
200  template <class Graph>
201  class IterableBoolEdgeMap
202  {
203    typename Graph::template EdgeMap<int> cmap;
204 
205  public:
206 
207    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
208    BimType imap;
209
210
211    typedef typename BimType::RefType RefType;
212    typedef typename Graph::Edge Key;
213    typedef bool Value;
214 
215    friend class FalseIt;
216    friend class TrueIt;
217 
218    ///\e
219    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
220
221  public:
222    ///\e
223    void set(Key k, bool v) { imap.set(k,v);}
224#ifdef DOXYGEN
225    ///\e
226    bool &operator[](Key k) { return imap[k];} 
227    ///\e
228    const bool &operator[](Key k) const { return imap[k];} 
229#else
230    Value operator[](Key k) const { return imap[k];} 
231    RefType operator[](Key k) { return imap[k];} 
232#endif
233    ///Iterator for the "false" edges
234    class FalseIt : public BimType::FalseIt
235    {
236    public:
237      explicit FalseIt(const IterableBoolEdgeMap &m)
238        : BimType::FalseIt(m.imap) { }
239      FalseIt(Invalid i) : BimType::FalseIt(i) { }
240    };
241    ///Iterator for the "true" edges
242    class TrueIt : public BimType::TrueIt
243    {
244    public:
245      explicit TrueIt(const IterableBoolEdgeMap &m)
246        : BimType::TrueIt(m.imap) { }
247      TrueIt(Invalid i) : BimType::TrueIt(i) { }
248    }; 
249  };
250
251
252  namespace _iterable_maps_bits {
253    template <typename Item>
254    struct IterableIntMapNode {
255      IterableIntMapNode() : value(-1) {}
256      Item prev, next;
257      int value;
258    };
259  }
260
261  ///\ingroup maps
262  ///
263  /// \brief Dynamic iterable integer map.
264  ///
265  /// \todo Document please
266  template <typename _Graph, typename _Item>
267  class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
268  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
269  public:
270    typedef typename ItemSetTraits<_Graph, _Item>
271    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
272    ::Parent Parent;
273
274    typedef _Item Key;
275    typedef int Value;
276    typedef _Graph Graph;
277
278    explicit IterableIntMap(const Graph& graph) : Parent(graph) {}
279
280  private:
281   
282    void unlace(const Key& key) {
283      typename Parent::Value& node = Parent::operator[](key);
284      if (node.value < 0) return;
285      if (node.prev != INVALID) {
286        Parent::operator[](node.prev).next = node.next;
287      } else {
288        first[node.value] = node.next;
289      }
290      if (node.next != INVALID) {
291        Parent::operator[](node.next).prev = node.prev;
292      }
293      while (!first.empty() && first.back() == INVALID) {
294        first.pop_back();
295      }
296    }
297
298    void lace(const Key& key) {
299      typename Parent::Value& node = Parent::operator[](key);
300      if (node.value < 0) return;
301      if (node.value >= (int)first.size()) {
302        first.resize(node.value + 1, INVALID);
303      }
304      node.prev = INVALID;
305      node.next = first[node.value];
306      if (node.next != INVALID) {
307        Parent::operator[](node.next).prev = key;       
308      }
309      first[node.value] = key;
310    }
311
312  public:
313
314    typedef True ReferenceMapTag;
315
316    class Reference {
317      friend class IterableIntMap;
318    private:
319      Reference(IterableIntMap& map, const Key& key)
320        : _key(key), _map(map) {}
321    public:
322
323      Reference& operator=(const Reference& value) {
324        _map.set(_key, (const int&)value);
325        return *this;
326      }
327
328      operator const int&() const {
329        return static_cast<const IterableIntMap&>(_map)[_key];
330      }
331
332      Reference& operator=(int value) {
333        _map.set(_key, value);
334        return *this;
335      }
336      Reference& operator++() {
337        _map.set(_key, _map[_key] + 1);
338        return *this;   
339      }
340      int operator++(int) {
341        int value = _map[_key];
342        _map.set(_key, value + 1);
343        return value;   
344      }
345      Reference& operator--() {
346        _map.set(_key, _map[_key] - 1);
347        return *this;   
348      }
349      int operator--(int) {
350        int value = _map[_key];
351        _map.set(_key, value - 1);
352        return value;   
353      }
354      Reference& operator+=(int value) {
355        _map.set(_key, _map[_key] + value);
356        return *this;
357      }
358      Reference& operator-=(int value) {
359        _map.set(_key, _map[_key] - value);
360        return *this;
361      }
362      Reference& operator*=(int value) {
363        _map.set(_key, _map[_key] * value);
364        return *this;
365      }
366      Reference& operator/=(int value) {
367        _map.set(_key, _map[_key] / value);
368        return *this;
369      }
370      Reference& operator%=(int value) {
371        _map.set(_key, _map[_key] % value);
372        return *this;
373      }
374      Reference& operator&=(int value) {
375        _map.set(_key, _map[_key] & value);
376        return *this;
377      }
378      Reference& operator|=(int value) {
379        _map.set(_key, _map[_key] | value);
380        return *this;
381      }
382      Reference& operator^=(int value) {
383        _map.set(_key, _map[_key] ^ value);
384        return *this;
385      }
386      Reference& operator<<=(int value) {
387        _map.set(_key, _map[_key] << value);
388        return *this;
389      }
390      Reference& operator>>=(int value) {
391        _map.set(_key, _map[_key] >> value);
392        return *this;
393      }
394
395    private:
396      Key _key;
397      IterableIntMap& _map;
398    };
399   
400    typedef const Value& ConstReference;
401
402    int size() const {
403      return (int)first.size();
404    }
405   
406    void set(const Key& key, const Value& value) {
407      unlace(key);
408      Parent::operator[](key).value = value;
409      lace(key);
410    }
411
412    const Value& operator[](const Key& key) const {
413      return Parent::operator[](key).value;
414    }
415
416    Reference operator[](const Key& key) {
417      return Reference(*this, key);
418    }
419
420    class ItemIt : public _Item {
421    public:
422      typedef _Item Parent;
423
424      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
425
426      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
427        if (value < 0 || value >= (int)_map->first.size()) {     
428          Parent::operator=(INVALID);
429        } else {
430          Parent::operator=(_map->first[value]);
431        }
432      }
433
434      ItemIt& operator++() {
435        Parent::operator=(_map->IterableIntMap::Parent::
436                          operator[](static_cast<Parent&>(*this)).next);
437        return *this;
438      }
439
440
441    private:
442      const IterableIntMap* _map;
443    };
444
445  protected:
446   
447    virtual void erase(const Key& key) {
448      unlace(key);
449      Parent::erase(key);
450    }
451
452    virtual void clear() {
453      first.clear();
454      Parent::clear();
455    }
456
457  private:
458    std::vector<_Item> first;
459  };
460
461  /// @}
462}
Note: See TracBrowser for help on using the repository browser.