COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1809:029cc4f638d1

Last change on this file since 1809:029cc4f638d1 was 1805:d284f81f02a5, checked in by Alpar Juttner, 14 years ago

Iterable Bool maps can count the number of true and false values.

File size: 12.5 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::MapSet::iterator i=cref.mapSet().begin();
140          i!=cref.mapSet().end();
141          ++i) {
142        i->second=sep;
143        vals.push_back(i->first);
144        sep++;
145      }
146      if(init) sep=0;
147    }
148    ///\e
149    RefType operator[] (Key k) { return RefType(*this,k);} 
150    ///\e
151    Value operator[] (Key k) const { return isTrue(k);} 
152  };
153
154
155
156
157  /// \addtogroup graph_maps
158  /// @{
159
160  /// Iterable bool NodeMap
161
162  /// This map can be used in the same way
163  /// as the standard NodeMap<bool> of the
164  /// given graph \c Graph.
165  /// In addition, this class provides two iterators called \ref TrueIt
166  /// and \ref FalseIt to iterate through the "true" and "false" nodes.
167  template <class Graph>
168  class IterableBoolNodeMap
169  {
170    typename Graph::template NodeMap<int> cmap;
171 
172  public:
173 
174    typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
175    BimType imap;
176
177
178    typedef typename BimType::RefType RefType;
179    typedef typename Graph::Node Key;
180    typedef bool Value;
181 
182    friend class FalseIt;
183    friend class TrueIt;
184 
185    ///\e
186    IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
187
188  public:
189    ///\e
190    void set(Key k, bool v) { imap.set(k,v);}
191    ///Number of \c true items in the map
192
193    ///Returns the number of \c true values in the map.
194    ///This is a constant time operation.
195    int countTrue() { return imap.countTrue(); }
196    ///Number of \c false items in the map
197
198    ///Returns the number of \c false values in the map.
199    ///This is a constant time operation.
200    int countFalse() { return imap.countFalse(); }
201#ifdef DOXYGEN
202    ///\e
203    bool &operator[](Key k) { return imap[k];} 
204    ///\e
205    const bool &operator[](Key k) const { return imap[k];} 
206#else
207    Value operator[](Key k) const { return imap[k];} 
208    RefType operator[](Key k) { return imap[k];} 
209#endif
210    ///Iterator for the "false" nodes
211    class FalseIt : public BimType::FalseIt
212    {
213    public:
214      ///\e
215      explicit FalseIt(const IterableBoolNodeMap &m)
216        : BimType::FalseIt(m.imap) { }
217      ///\e
218      FalseIt(Invalid i) : BimType::FalseIt(i) { }
219    };
220    ///Iterator for the "true" nodes
221    class TrueIt : public BimType::TrueIt
222    {
223    public:
224      ///\e
225      explicit TrueIt(const IterableBoolNodeMap &m)
226        : BimType::TrueIt(m.imap) { }
227      ///\e
228      TrueIt(Invalid i) : BimType::TrueIt(i) { }
229    }; 
230  };
231
232  /// Iterable bool EdgeMap
233
234  /// This map can be used in the same way
235  /// as the standard EdgeMap<bool> of the
236  /// given graph \c Graph.
237  /// In addition, this class provides two iterators called \ref TrueIt
238  /// and \ref FalseIt to iterate through the "true" and "false" edges.
239  template <class Graph>
240  class IterableBoolEdgeMap
241  {
242    typename Graph::template EdgeMap<int> cmap;
243 
244  public:
245 
246    typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
247    BimType imap;
248
249
250    typedef typename BimType::RefType RefType;
251    typedef typename Graph::Edge Key;
252    typedef bool Value;
253 
254    friend class FalseIt;
255    friend class TrueIt;
256 
257    ///\e
258    IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
259
260  public:
261    ///\e
262    void set(Key k, bool v) { imap.set(k,v);}
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" edges
281    class FalseIt : public BimType::FalseIt
282    {
283    public:
284      ///\e
285      explicit FalseIt(const IterableBoolEdgeMap &m)
286        : BimType::FalseIt(m.imap) { }
287      ///\e
288      FalseIt(Invalid i) : BimType::FalseIt(i) { }
289    };
290    ///Iterator for the "true" edges
291    class TrueIt : public BimType::TrueIt
292    {
293    public:
294      ///\e
295      explicit TrueIt(const IterableBoolEdgeMap &m)
296        : BimType::TrueIt(m.imap) { }
297      ///\e
298      TrueIt(Invalid i) : BimType::TrueIt(i) { }
299    }; 
300  };
301
302
303  namespace _iterable_maps_bits {
304    template <typename Item>
305    struct IterableIntMapNode {
306      IterableIntMapNode() : value(-1) {}
307      Item prev, next;
308      int value;
309    };
310  }
311
312  ///\ingroup maps
313  ///
314  /// \brief Dynamic iterable integer map.
315  ///
316  /// \todo Document please
317  template <typename _Graph, typename _Item>
318  class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
319  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
320  public:
321    typedef typename ItemSetTraits<_Graph, _Item>
322    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
323    ::Parent Parent;
324
325    typedef _Item Key;
326    typedef int Value;
327    typedef _Graph Graph;
328
329    explicit IterableIntMap(const Graph& graph) : Parent(graph) {}
330
331  private:
332   
333    void unlace(const Key& key) {
334      typename Parent::Value& node = Parent::operator[](key);
335      if (node.value < 0) return;
336      if (node.prev != INVALID) {
337        Parent::operator[](node.prev).next = node.next;
338      } else {
339        first[node.value] = node.next;
340      }
341      if (node.next != INVALID) {
342        Parent::operator[](node.next).prev = node.prev;
343      }
344      while (!first.empty() && first.back() == INVALID) {
345        first.pop_back();
346      }
347    }
348
349    void lace(const Key& key) {
350      typename Parent::Value& node = Parent::operator[](key);
351      if (node.value < 0) return;
352      if (node.value >= (int)first.size()) {
353        first.resize(node.value + 1, INVALID);
354      }
355      node.prev = INVALID;
356      node.next = first[node.value];
357      if (node.next != INVALID) {
358        Parent::operator[](node.next).prev = key;       
359      }
360      first[node.value] = key;
361    }
362
363  public:
364
365    typedef True ReferenceMapTag;
366
367    class Reference {
368      friend class IterableIntMap;
369    private:
370      Reference(IterableIntMap& map, const Key& key)
371        : _key(key), _map(map) {}
372    public:
373
374      Reference& operator=(const Reference& value) {
375        _map.set(_key, (const int&)value);
376        return *this;
377      }
378
379      operator const int&() const {
380        return static_cast<const IterableIntMap&>(_map)[_key];
381      }
382
383      Reference& operator=(int value) {
384        _map.set(_key, value);
385        return *this;
386      }
387      Reference& operator++() {
388        _map.set(_key, _map[_key] + 1);
389        return *this;   
390      }
391      int operator++(int) {
392        int value = _map[_key];
393        _map.set(_key, value + 1);
394        return value;   
395      }
396      Reference& operator--() {
397        _map.set(_key, _map[_key] - 1);
398        return *this;   
399      }
400      int operator--(int) {
401        int value = _map[_key];
402        _map.set(_key, value - 1);
403        return value;   
404      }
405      Reference& operator+=(int value) {
406        _map.set(_key, _map[_key] + value);
407        return *this;
408      }
409      Reference& operator-=(int value) {
410        _map.set(_key, _map[_key] - value);
411        return *this;
412      }
413      Reference& operator*=(int value) {
414        _map.set(_key, _map[_key] * value);
415        return *this;
416      }
417      Reference& operator/=(int value) {
418        _map.set(_key, _map[_key] / value);
419        return *this;
420      }
421      Reference& operator%=(int value) {
422        _map.set(_key, _map[_key] % value);
423        return *this;
424      }
425      Reference& operator&=(int value) {
426        _map.set(_key, _map[_key] & value);
427        return *this;
428      }
429      Reference& operator|=(int value) {
430        _map.set(_key, _map[_key] | value);
431        return *this;
432      }
433      Reference& operator^=(int value) {
434        _map.set(_key, _map[_key] ^ value);
435        return *this;
436      }
437      Reference& operator<<=(int value) {
438        _map.set(_key, _map[_key] << value);
439        return *this;
440      }
441      Reference& operator>>=(int value) {
442        _map.set(_key, _map[_key] >> value);
443        return *this;
444      }
445
446    private:
447      Key _key;
448      IterableIntMap& _map;
449    };
450   
451    typedef const Value& ConstReference;
452
453    int size() const {
454      return (int)first.size();
455    }
456   
457    void set(const Key& key, const Value& value) {
458      unlace(key);
459      Parent::operator[](key).value = value;
460      lace(key);
461    }
462
463    const Value& operator[](const Key& key) const {
464      return Parent::operator[](key).value;
465    }
466
467    Reference operator[](const Key& key) {
468      return Reference(*this, key);
469    }
470
471    class ItemIt : public _Item {
472    public:
473      typedef _Item Parent;
474
475      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
476
477      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
478        if (value < 0 || value >= (int)_map->first.size()) {     
479          Parent::operator=(INVALID);
480        } else {
481          Parent::operator=(_map->first[value]);
482        }
483      }
484
485      ItemIt& operator++() {
486        Parent::operator=(_map->IterableIntMap::Parent::
487                          operator[](static_cast<Parent&>(*this)).next);
488        return *this;
489      }
490
491
492    private:
493      const IterableIntMap* _map;
494    };
495
496  protected:
497   
498    virtual void erase(const Key& key) {
499      unlace(key);
500      Parent::erase(key);
501    }
502
503    virtual void clear() {
504      first.clear();
505      Parent::clear();
506    }
507
508  private:
509    std::vector<_Item> first;
510  };
511
512  /// @}
513}
Note: See TracBrowser for help on using the repository browser.