COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1920:e9e27c5a53bf

Last change on this file since 1920:e9e27c5a53bf was 1913:49fe71fce7fb, checked in by Balazs Dezso, 18 years ago

Making iterable bool map dynamic
Changed interface

File size: 16.2 KB
Line 
1/* -*- C++ -*-
2 * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 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  ///\ingroup maps
33  ///
34  /// \brief Dynamic iterable bool map.
35  ///
36  /// This class provides a special graph map type which can store
37  /// for each graph item(node, edge, etc.) a bool value. For both
38  /// the true and the false it is possible to iterate on the keys which
39  /// mapped to the given value.
40  ///
41  /// \param _Graph The graph type.
42  /// \param _Item One of the graph's item type, the key of the map.
43  template <typename _Graph, typename _Item>
44  class IterableBoolMap
45    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
46  private:
47    typedef _Graph Graph;
48    typedef _Item Item;
49   
50    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
51    typedef typename ItemSetTraits<Graph, Item>
52    ::template Map<int>::Parent Parent;
53   
54    std::vector<Item> array;
55    int sep;
56
57    const Graph& graph;
58
59  private:
60
61    int position(const Item& item) const {
62      return Parent::operator[](item);
63    }
64
65  public:
66
67    /// Indicates that the map if reference map.
68    typedef True ReferenceMapTag;
69
70    /// The key type
71    typedef Item Key;
72    /// The value type
73    typedef bool Value;
74    /// The const reference type.   
75    typedef const Value& ConstReference;
76
77
78    /// \brief Refernce to the value of the map.
79    ///
80    /// This class is near to similar to the bool type. It can
81    /// be converted to bool and it has the same operators.
82    class Reference {
83      friend class IterableBoolMap;
84    private:
85      Reference(IterableBoolMap& map, const Key& key)
86        : _key(key), _map(map) {}
87    public:
88
89      Reference& operator=(const Reference& value) {
90        _map.set(_key, (bool)value);
91        return *this;
92      }
93
94      operator bool() const {
95        return static_cast<const IterableBoolMap&>(_map)[_key];
96      }
97
98      Reference& operator=(bool value) {
99        _map.set(_key, value);
100        return *this;
101      }
102      Reference& operator&=(bool value) {
103        _map.set(_key, _map[_key] & value);
104        return *this;   
105      }
106      Reference& operator|=(bool value) {
107        _map.set(_key, _map[_key] | value);
108        return *this;   
109      }
110      Reference& operator^=(bool value) {
111        _map.set(_key, _map[_key] ^ value);
112        return *this;   
113      }
114    private:
115      Key _key;
116      IterableBoolMap& _map;
117    };
118   
119    /// \brief Constructor of the Map with a default value.
120    ///
121    /// Constructor of the Map with a default value.
122    IterableBoolMap(const Graph& _graph, bool def = false)
123      : Parent(_graph), graph(_graph) {
124      for (ItemIt it(graph); it != INVALID; ++it) {
125        Parent::set(it, array.size());
126        array.push_back(it);
127      }
128      sep = (def ? array.size() : 0);
129    }
130
131    /// \brief Const subscript operator of the map.
132    ///
133    /// Const subscript operator of the map.
134    bool operator[](const Item& item) const {
135      return position(item) < sep;
136    }
137
138    /// \brief Subscript operator of the map.
139    ///
140    /// Subscript operator of the map.
141    Reference operator[](const Item& item) {
142      return Reference(*this, item);
143    }
144
145    /// \brief Set operation of the map.
146    ///
147    /// Set operation of the map.
148    void set(const Item& item, bool value) {
149      int pos = position(item);
150      if (value) {
151        if (pos < sep) return;
152        Item tmp = array[sep];
153        array[sep] = item;
154        Parent::set(item, sep);
155        array[pos] = tmp;
156        Parent::set(tmp, pos);
157        ++sep;
158      } else {
159        if (pos >= sep) return;
160        --sep;
161        Item tmp = array[sep];
162        array[sep] = item;
163        Parent::set(item, sep);
164        array[pos] = tmp;
165        Parent::set(tmp, pos);
166      }
167    }
168
169    /// \brief Returns the number of the items mapped to true.
170    ///
171    /// Returns the number of the items mapped to true.
172    int trueNum() const {
173      return sep;
174    }
175   
176    /// \brief Returns the number of the items mapped to false.
177    ///
178    /// Returns the number of the items mapped to false.
179    int falseNum() const {
180      return array.size() - sep;
181    }
182
183    /// \brief Iterator for the keys mapped to true.
184    ///
185    /// Iterator for the keys mapped to true. It works
186    /// like a graph item iterator in the map, it can be converted
187    /// the item type of the map, incremented with \c ++ operator, and
188    /// if the iterator leave the last valid item it will be equal to
189    /// \c INVALID.
190    class TrueIt : public Item {
191    public:
192      typedef Item Parent;
193     
194      /// \brief Creates an iterator.
195      ///
196      /// Creates an iterator. It iterates on the
197      /// keys which mapped to true.
198      /// \param map The IterableIntMap
199      TrueIt(const IterableBoolMap& _map)
200        : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
201          map(&_map) {}
202
203      /// \brief Invalid constructor \& conversion.
204      ///
205      /// This constructor initializes the item to be invalid.
206      /// \sa Invalid for more details.
207      TrueIt(Invalid) : Parent(INVALID), map(0) {}
208
209      /// \brief Increment operator.
210      ///
211      /// Increment Operator.
212      TrueIt& operator++() {
213        int pos = map->position(*this);
214        Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
215        return *this;
216      }
217
218     
219    private:
220      const IterableBoolMap* map;
221    };
222
223    /// \brief Iterator for the keys mapped to false.
224    ///
225    /// Iterator for the keys mapped to false. It works
226    /// like a graph item iterator in the map, it can be converted
227    /// the item type of the map, incremented with \c ++ operator, and
228    /// if the iterator leave the last valid item it will be equal to
229    /// \c INVALID.
230    class FalseIt : public Item {
231    public:
232      typedef Item Parent;
233     
234      /// \brief Creates an iterator.
235      ///
236      /// Creates an iterator. It iterates on the
237      /// keys which mapped to false.
238      /// \param map The IterableIntMap
239      FalseIt(const IterableBoolMap& _map)
240        : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),
241          map(&_map) {}
242
243      /// \brief Invalid constructor \& conversion.
244      ///
245      /// This constructor initializes the item to be invalid.
246      /// \sa Invalid for more details.
247      FalseIt(Invalid) : Parent(INVALID), map(0) {}
248
249      /// \brief Increment operator.
250      ///
251      /// Increment Operator.
252      FalseIt& operator++() {
253        int pos = map->position(*this);
254        Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
255        return *this;
256      }
257
258    private:
259      const IterableBoolMap* map;
260    };
261
262  protected:
263   
264    virtual void add(const Item& item) {
265      Parent::add(item);
266      Parent::set(item, array.size());
267      array.push_back(item);
268    }
269
270    virtual void add(const std::vector<Item>& items) {
271      Parent::add(items);
272      for (int i = 0; i < (int)items.size(); ++i) {
273        Parent::set(items[i], array.size());
274        array.push_back(items[i]);
275      }
276    }
277
278    virtual void erase(const Item& item) {
279      int pos = position(item);
280      if (pos < sep) {
281        --sep;
282        Parent::set(array[sep], pos);
283        array[pos] = array[sep];
284        Parent::set(array.back(), sep);
285        array[sep] = array.back();
286        array.pop_back();
287      } else {
288        Parent::set(array.back(), pos);
289        array[pos] = array.back();
290        array.pop_back();
291      }
292      Parent::erase(item);
293    }
294
295    virtual void erase(const std::vector<Item>& items) {
296      for (int i = 0; i < (int)items.size(); ++i) {
297        int pos = position(items[i]);
298        if (pos < sep) {
299          --sep;
300          Parent::set(array[sep], pos);
301          array[pos] = array[sep];
302          Parent::set(array.back(), sep);
303          array[sep] = array.back();
304          array.pop_back();
305        } else {
306          Parent::set(array.back(), pos);
307          array[pos] = array.back();
308          array.pop_back();
309        }
310      }
311      Parent::erase(items);
312    }   
313
314    virtual void build() {
315      Parent::build();
316      for (ItemIt it(graph); it != INVALID; ++it) {
317        Parent::set(it, array.size());
318        array.push_back(it);
319      }
320      sep = 0;     
321    }
322
323    virtual void clear() {
324      array.clear();
325      sep = 0;
326      Parent::clear();
327    }
328   
329  };
330 
331
332  namespace _iterable_maps_bits {
333    template <typename Item>
334    struct IterableIntMapNode {
335      IterableIntMapNode() : value(-1) {}
336      IterableIntMapNode(int _value) : value(_value) {}
337      Item prev, next;
338      int value;
339    };
340  }
341
342  ///\ingroup maps
343  ///
344  /// \brief Dynamic iterable integer map.
345  ///
346  /// This class provides a special graph map type which can store
347  /// for each graph item(node, edge, etc.) an integer value. For each
348  /// non negative value it is possible to iterate on the keys which
349  /// mapped to the given value.
350  ///
351  /// \param _Graph The graph type.
352  /// \param _Item One of the graph's item type, the key of the map.
353  template <typename _Graph, typename _Item>
354  class IterableIntMap : protected ItemSetTraits<_Graph, _Item>
355  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
356  public:
357    typedef typename ItemSetTraits<_Graph, _Item>
358    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
359    ::Parent Parent;
360
361    /// The key type
362    typedef _Item Key;
363    /// The value type
364    typedef int Value;
365    /// The graph type
366    typedef _Graph Graph;
367
368    /// \brief Constructor of the Map.
369    ///
370    /// Constructor of the Map. It set all values -1.
371    explicit IterableIntMap(const Graph& graph)
372      : Parent(graph) {}
373
374    /// \brief Constructor of the Map with a given value.
375    ///
376    /// Constructor of the Map with a given value.
377    explicit IterableIntMap(const Graph& graph, int value)
378      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
379      if (value >= 0) {
380        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
381          lace(it);
382        }
383      }
384    }
385
386  private:
387   
388    void unlace(const Key& key) {
389      typename Parent::Value& node = Parent::operator[](key);
390      if (node.value < 0) return;
391      if (node.prev != INVALID) {
392        Parent::operator[](node.prev).next = node.next;
393      } else {
394        first[node.value] = node.next;
395      }
396      if (node.next != INVALID) {
397        Parent::operator[](node.next).prev = node.prev;
398      }
399      while (!first.empty() && first.back() == INVALID) {
400        first.pop_back();
401      }
402    }
403
404    void lace(const Key& key) {
405      typename Parent::Value& node = Parent::operator[](key);
406      if (node.value < 0) return;
407      if (node.value >= (int)first.size()) {
408        first.resize(node.value + 1, INVALID);
409      }
410      node.prev = INVALID;
411      node.next = first[node.value];
412      if (node.next != INVALID) {
413        Parent::operator[](node.next).prev = key;       
414      }
415      first[node.value] = key;
416    }
417
418  public:
419
420    /// Indicates that the map if reference map.
421    typedef True ReferenceMapTag;
422
423    /// \brief Refernce to the value of the map.
424    ///
425    /// This class is near to similar to the int type. It can
426    /// be converted to int and it has the same operators.
427    class Reference {
428      friend class IterableIntMap;
429    private:
430      Reference(IterableIntMap& map, const Key& key)
431        : _key(key), _map(map) {}
432    public:
433
434      Reference& operator=(const Reference& value) {
435        _map.set(_key, (const int&)value);
436        return *this;
437      }
438
439      operator const int&() const {
440        return static_cast<const IterableIntMap&>(_map)[_key];
441      }
442
443      Reference& operator=(int value) {
444        _map.set(_key, value);
445        return *this;
446      }
447      Reference& operator++() {
448        _map.set(_key, _map[_key] + 1);
449        return *this;   
450      }
451      int operator++(int) {
452        int value = _map[_key];
453        _map.set(_key, value + 1);
454        return value;   
455      }
456      Reference& operator--() {
457        _map.set(_key, _map[_key] - 1);
458        return *this;   
459      }
460      int operator--(int) {
461        int value = _map[_key];
462        _map.set(_key, value - 1);
463        return value;   
464      }
465      Reference& operator+=(int value) {
466        _map.set(_key, _map[_key] + value);
467        return *this;
468      }
469      Reference& operator-=(int value) {
470        _map.set(_key, _map[_key] - value);
471        return *this;
472      }
473      Reference& operator*=(int value) {
474        _map.set(_key, _map[_key] * value);
475        return *this;
476      }
477      Reference& operator/=(int value) {
478        _map.set(_key, _map[_key] / value);
479        return *this;
480      }
481      Reference& operator%=(int value) {
482        _map.set(_key, _map[_key] % value);
483        return *this;
484      }
485      Reference& operator&=(int value) {
486        _map.set(_key, _map[_key] & value);
487        return *this;
488      }
489      Reference& operator|=(int value) {
490        _map.set(_key, _map[_key] | value);
491        return *this;
492      }
493      Reference& operator^=(int value) {
494        _map.set(_key, _map[_key] ^ value);
495        return *this;
496      }
497      Reference& operator<<=(int value) {
498        _map.set(_key, _map[_key] << value);
499        return *this;
500      }
501      Reference& operator>>=(int value) {
502        _map.set(_key, _map[_key] >> value);
503        return *this;
504      }
505
506    private:
507      Key _key;
508      IterableIntMap& _map;
509    };
510
511    /// The const reference type.   
512    typedef const Value& ConstReference;
513
514    /// \brief Gives back the maximal value plus one.
515    ///
516    /// Gives back the maximal value plus one.
517    int size() const {
518      return (int)first.size();
519    }
520   
521    /// \brief Set operation of the map.
522    ///
523    /// Set operation of the map.
524    void set(const Key& key, const Value& value) {
525      unlace(key);
526      Parent::operator[](key).value = value;
527      lace(key);
528    }
529
530    /// \brief Const subscript operator of the map.
531    ///
532    /// Const subscript operator of the map.
533    const Value& operator[](const Key& key) const {
534      return Parent::operator[](key).value;
535    }
536
537    /// \brief Subscript operator of the map.
538    ///
539    /// Subscript operator of the map.
540    Reference operator[](const Key& key) {
541      return Reference(*this, key);
542    }
543
544    /// \brief Iterator for the keys with the same value.
545    ///
546    /// Iterator for the keys with the same value. It works
547    /// like a graph item iterator in the map, it can be converted
548    /// the item type of the map, incremented with \c ++ operator, and
549    /// if the iterator leave the last valid item it will be equal to
550    /// \c INVALID.
551    class ItemIt : public _Item {
552    public:
553      typedef _Item Parent;
554
555      /// \brief Invalid constructor \& conversion.
556      ///
557      /// This constructor initializes the item to be invalid.
558      /// \sa Invalid for more details.
559      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
560
561      /// \brief Creates an iterator with a value.
562      ///
563      /// Creates an iterator with a value. It iterates on the
564      /// keys which have the given value.
565      /// \param map The IterableIntMap
566      /// \param value The value
567      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
568        if (value < 0 || value >= (int)_map->first.size()) {     
569          Parent::operator=(INVALID);
570        } else {
571          Parent::operator=(_map->first[value]);
572        }
573      }
574
575      /// \brief Increment operator.
576      ///
577      /// Increment Operator.
578      ItemIt& operator++() {
579        Parent::operator=(_map->IterableIntMap::Parent::
580                          operator[](static_cast<Parent&>(*this)).next);
581        return *this;
582      }
583
584
585    private:
586      const IterableIntMap* _map;
587    };
588
589  protected:
590   
591    virtual void erase(const Key& key) {
592      unlace(key);
593      Parent::erase(key);
594    }
595
596    virtual void erase(const std::vector<Key>& keys) {
597      for (int i = 0; i < keys.size(); ++i) {
598        unlace(keys[i]);
599      }
600      Parent::erase(keys);
601    }
602
603    virtual void clear() {
604      first.clear();
605      Parent::clear();
606    }
607
608  private:
609    std::vector<_Item> first;
610  };
611
612  /// @}
613}
Note: See TracBrowser for help on using the repository browser.