COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1752:dce1f28ac595

Last change on this file since 1752:dce1f28ac595 was 1752:dce1f28ac595, checked in by Balazs Dezso, 18 years ago

IterableIntMap?

todo: documentation need

File size: 10.8 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    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+=(int value) {
337        _map.set(_key, _map[_key] + value);
338        return *this;
339      }
340      Reference& operator-=(int value) {
341        _map.set(_key, _map[_key] - value);
342        return *this;
343      }
344      Reference& operator*=(int value) {
345        _map.set(_key, _map[_key] * value);
346        return *this;
347      }
348      Reference& operator/=(int value) {
349        _map.set(_key, _map[_key] / value);
350        return *this;
351      }
352      Reference& operator%=(int value) {
353        _map.set(_key, _map[_key] % value);
354        return *this;
355      }
356      Reference& operator&=(int value) {
357        _map.set(_key, _map[_key] & value);
358        return *this;
359      }
360      Reference& operator|=(int value) {
361        _map.set(_key, _map[_key] | value);
362        return *this;
363      }
364      Reference& operator^=(int value) {
365        _map.set(_key, _map[_key] ^ value);
366        return *this;
367      }
368      Reference& operator<<=(int value) {
369        _map.set(_key, _map[_key] << value);
370        return *this;
371      }
372      Reference& operator>>=(int value) {
373        _map.set(_key, _map[_key] >> value);
374        return *this;
375      }
376
377    private:
378      Key _key;
379      IterableIntMap& _map;
380    };
381   
382    typedef const Value& ConstReference;
383
384    int size() const {
385      return (int)first.size();
386    }
387   
388    void set(const Key& key, const Value& value) {
389      unlace(key);
390      Parent::operator[](key).value = value;
391      lace(key);
392    }
393
394    const Value& operator[](const Key& key) const {
395      return Parent::operator[](key).value;
396    }
397
398    Reference operator[](const Key& key) {
399      return Reference(*this, key);
400    }
401
402    class ItemIt : public _Item {
403    public:
404      typedef _Item Parent;
405
406      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
407
408      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
409        if (value < 0 || value >= (int)_map->first.size()) {     
410          Parent::operator=(INVALID);
411        } else {
412          Parent::operator=(_map->first[value]);
413        }
414      }
415
416      ItemIt& operator++() {
417        Parent::operator=(_map->IterableIntMap::Parent::
418                          operator[](static_cast<Parent&>(*this)).next);
419        return *this;
420      }
421
422
423    private:
424      const IterableIntMap* _map;
425    };
426
427  protected:
428   
429    virtual void erase(const Key& key) {
430      unlace(key);
431      Parent::erase(key);
432    }
433
434    virtual void clear() {
435      first.clear();
436      Parent::clear();
437    }
438
439  private:
440    std::vector<_Item> first;
441  };
442
443  /// @}
444}
Note: See TracBrowser for help on using the repository browser.