COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 25.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_ITERABLE_MAPS_H
20#define LEMON_ITERABLE_MAPS_H
21
22#include <lemon/bits/traits.h>
23#include <lemon/bits/invalid.h>
24
25#include <lemon/bits/default_map.h>
26#include <lemon/bits/map_extender.h>
27
28#include <vector>
29#include <map>
30
31#include <iterator>
32#include <limits>
33
34///\ingroup maps
35///\file
36///\brief Maps that makes it possible to iterate through the keys having
37///a certain value
38///
39///
40
41
42namespace lemon {
43
44  ///\ingroup graph_maps
45  ///
46  /// \brief Dynamic iterable bool map.
47  ///
48  /// This class provides a special graph map type which can store
49  /// for each graph item(node, edge, etc.) a bool value. For both
50  /// the true and the false it is possible to iterate on the keys which
51  /// mapped to the given value.
52  ///
53  /// \param _Graph The graph type.
54  /// \param _Item One of the graph's item type, the key of the map.
55  template <typename _Graph, typename _Item>
56  class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
57  private:
58    typedef _Graph Graph;
59   
60    typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
61    typedef DefaultMap<_Graph, _Item, int> Parent;
62   
63    std::vector<_Item> array;
64    int sep;
65
66    const Graph& graph;
67
68  public:
69
70    /// Indicates that the map if reference map.
71    typedef True ReferenceMapTag;
72
73    /// The key type
74    typedef _Item Key;
75    /// The value type
76    typedef bool Value;
77    /// The const reference type.   
78    typedef const Value& ConstReference;
79
80  private:
81
82    int position(const Key& key) const {
83      return Parent::operator[](key);
84    }
85
86  public:
87
88    /// \brief Refernce to the value of the map.
89    ///
90    /// This class is near to similar to the bool type. It can
91    /// be converted to bool and it has the same operators.
92    class Reference {
93      friend class IterableBoolMap;
94    private:
95      Reference(IterableBoolMap& map, const Key& key)
96        : _key(key), _map(map) {}
97    public:
98
99      Reference& operator=(const Reference& value) {
100        _map.set(_key, static_cast<bool>(value));
101        return *this;
102      }
103
104      operator bool() const {
105        return static_cast<const IterableBoolMap&>(_map)[_key];
106      }
107
108      Reference& operator=(bool value) {
109        _map.set(_key, value);
110        return *this;
111      }
112      Reference& operator&=(bool value) {
113        _map.set(_key, _map[_key] & value);
114        return *this;   
115      }
116      Reference& operator|=(bool value) {
117        _map.set(_key, _map[_key] | value);
118        return *this;   
119      }
120      Reference& operator^=(bool value) {
121        _map.set(_key, _map[_key] ^ value);
122        return *this;   
123      }
124    private:
125      Key _key;
126      IterableBoolMap& _map;
127    };
128   
129    /// \brief Constructor of the Map with a default value.
130    ///
131    /// Constructor of the Map with a default value.
132    explicit IterableBoolMap(const Graph& _graph, bool def = false)
133      : Parent(_graph), graph(_graph) {
134      for (KeyIt it(graph); it != INVALID; ++it) {
135        Parent::set(it, array.size());
136        array.push_back(it);
137      }
138      sep = (def ? array.size() : 0);
139    }
140
141    /// \brief Const subscript operator of the map.
142    ///
143    /// Const subscript operator of the map.
144    bool operator[](const Key& key) const {
145      return position(key) < sep;
146    }
147
148    /// \brief Subscript operator of the map.
149    ///
150    /// Subscript operator of the map.
151    Reference operator[](const Key& key) {
152      return Reference(*this, key);
153    }
154
155    /// \brief Set operation of the map.
156    ///
157    /// Set operation of the map.
158    void set(const Key& key, bool value) {
159      int pos = position(key);
160      if (value) {
161        if (pos < sep) return;
162        Key tmp = array[sep];
163        array[sep] = key;
164        Parent::set(key, sep);
165        array[pos] = tmp;
166        Parent::set(tmp, pos);
167        ++sep;
168      } else {
169        if (pos >= sep) return;
170        --sep;
171        Key tmp = array[sep];
172        array[sep] = key;
173        Parent::set(key, sep);
174        array[pos] = tmp;
175        Parent::set(tmp, pos);
176      }
177    }
178
179    /// \brief Set all items.
180    ///
181    /// Set all items in the map.
182    /// \note Constant time operation.
183    void setAll(bool value) {
184      sep = (value ? array.size() : 0);     
185    }
186
187    /// \brief Returns the number of the keys mapped to true.
188    ///
189    /// Returns the number of the keys mapped to true.
190    int trueNum() const {
191      return sep;
192    }
193   
194    /// \brief Returns the number of the keys mapped to false.
195    ///
196    /// Returns the number of the keys mapped to false.
197    int falseNum() const {
198      return array.size() - sep;
199    }
200
201    /// \brief Iterator for the keys mapped to true.
202    ///
203    /// Iterator for the keys mapped to true. It works
204    /// like a graph item iterator in the map, it can be converted
205    /// the key type of the map, incremented with \c ++ operator, and
206    /// if the iterator leave the last valid key it will be equal to
207    /// \c INVALID.
208    class TrueIt : public Key {
209    public:
210      typedef Key Parent;
211     
212      /// \brief Creates an iterator.
213      ///
214      /// Creates an iterator. It iterates on the
215      /// keys which mapped to true.
216      /// \param _map The IterableIntMap
217      explicit TrueIt(const IterableBoolMap& _map)
218        : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
219          map(&_map) {}
220
221      /// \brief Invalid constructor \& conversion.
222      ///
223      /// This constructor initializes the key to be invalid.
224      /// \sa Invalid for more details.
225      TrueIt(Invalid) : Parent(INVALID), map(0) {}
226
227      /// \brief Increment operator.
228      ///
229      /// Increment Operator.
230      TrueIt& operator++() {
231        int pos = map->position(*this);
232        Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
233        return *this;
234      }
235
236     
237    private:
238      const IterableBoolMap* map;
239    };
240
241    /// \brief Iterator for the keys mapped to false.
242    ///
243    /// Iterator for the keys mapped to false. It works
244    /// like a graph item iterator in the map, it can be converted
245    /// the key type of the map, incremented with \c ++ operator, and
246    /// if the iterator leave the last valid key it will be equal to
247    /// \c INVALID.
248    class FalseIt : public Key {
249    public:
250      typedef Key Parent;
251     
252      /// \brief Creates an iterator.
253      ///
254      /// Creates an iterator. It iterates on the
255      /// keys which mapped to false.
256      /// \param _map The IterableIntMap
257      explicit FalseIt(const IterableBoolMap& _map)
258        : Parent(_map.sep < int(_map.array.size()) ?
259                 _map.array.back() : INVALID), map(&_map) {}
260
261      /// \brief Invalid constructor \& conversion.
262      ///
263      /// This constructor initializes the key to be invalid.
264      /// \sa Invalid for more details.
265      FalseIt(Invalid) : Parent(INVALID), map(0) {}
266
267      /// \brief Increment operator.
268      ///
269      /// Increment Operator.
270      FalseIt& operator++() {
271        int pos = map->position(*this);
272        Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
273        return *this;
274      }
275
276    private:
277      const IterableBoolMap* map;
278    };
279
280    /// \brief Iterator for the keys mapped to a given value.
281    ///
282    /// Iterator for the keys mapped to a given value. It works
283    /// like a graph item iterator in the map, it can be converted
284    /// the key type of the map, incremented with \c ++ operator, and
285    /// if the iterator leave the last valid key it will be equal to
286    /// \c INVALID.
287    class ItemIt : public Key {
288    public:
289      typedef Key Parent;
290     
291      /// \brief Creates an iterator.
292      ///
293      /// Creates an iterator. It iterates on the
294      /// keys which mapped to false.
295      /// \param _map The IterableIntMap
296      /// \param value Which elements should be iterated.
297      ItemIt(const IterableBoolMap& _map, bool value)
298        : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
299                 (_map.sep < int(_map.array.size()) ?
300                  _map.array.back() : INVALID)), map(&_map) {}
301
302      /// \brief Invalid constructor \& conversion.
303      ///
304      /// This constructor initializes the key to be invalid.
305      /// \sa Invalid for more details.
306      ItemIt(Invalid) : Parent(INVALID), map(0) {}
307
308      /// \brief Increment operator.
309      ///
310      /// Increment Operator.
311      ItemIt& operator++() {
312        int pos = map->position(*this);
313        int sep = pos >= map->sep ? map->sep : 0;
314        Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
315        return *this;
316      }
317
318    private:
319      const IterableBoolMap* map;
320    };
321
322  protected:
323   
324    virtual void add(const Key& key) {
325      Parent::add(key);
326      Parent::set(key, array.size());
327      array.push_back(key);
328    }
329
330    virtual void add(const std::vector<Key>& keys) {
331      Parent::add(keys);
332      for (int i = 0; i < int(keys.size()); ++i) {
333        Parent::set(keys[i], array.size());
334        array.push_back(keys[i]);
335      }
336    }
337
338    virtual void erase(const Key& key) {
339      int pos = position(key);
340      if (pos < sep) {
341        --sep;
342        Parent::set(array[sep], pos);
343        array[pos] = array[sep];
344        Parent::set(array.back(), sep);
345        array[sep] = array.back();
346        array.pop_back();
347      } else {
348        Parent::set(array.back(), pos);
349        array[pos] = array.back();
350        array.pop_back();
351      }
352      Parent::erase(key);
353    }
354
355    virtual void erase(const std::vector<Key>& keys) {
356      for (int i = 0; i < int(keys.size()); ++i) {
357        int pos = position(keys[i]);
358        if (pos < sep) {
359          --sep;
360          Parent::set(array[sep], pos);
361          array[pos] = array[sep];
362          Parent::set(array.back(), sep);
363          array[sep] = array.back();
364          array.pop_back();
365        } else {
366          Parent::set(array.back(), pos);
367          array[pos] = array.back();
368          array.pop_back();
369        }
370      }
371      Parent::erase(keys);
372    }   
373
374    virtual void build() {
375      Parent::build();
376      for (KeyIt it(graph); it != INVALID; ++it) {
377        Parent::set(it, array.size());
378        array.push_back(it);
379      }
380      sep = 0;     
381    }
382
383    virtual void clear() {
384      array.clear();
385      sep = 0;
386      Parent::clear();
387    }
388   
389  };
390 
391
392  namespace _iterable_maps_bits {
393    template <typename Item>
394    struct IterableIntMapNode {
395      IterableIntMapNode() : value(-1) {}
396      IterableIntMapNode(int _value) : value(_value) {}
397      Item prev, next;
398      int value;
399    };
400  }
401
402  ///\ingroup graph_maps
403  ///
404  /// \brief Dynamic iterable integer map.
405  ///
406  /// This class provides a special graph map type which can store
407  /// for each graph item(node, edge, etc.) an integer value. For each
408  /// non negative value it is possible to iterate on the keys which
409  /// mapped to the given value.
410  ///
411  /// \param _Graph The graph type.
412  /// \param _Item One of the graph's item type, the key of the map.
413  template <typename _Graph, typename _Item>
414  class IterableIntMap
415    : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
416                                       IterableIntMapNode<_Item> > >{
417  public:
418    typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
419                                   IterableIntMapNode<_Item> > > Parent;
420
421    /// The key type
422    typedef _Item Key;
423    /// The value type
424    typedef int Value;
425    /// The graph type
426    typedef _Graph Graph;
427
428    /// \brief Constructor of the Map.
429    ///
430    /// Constructor of the Map. It set all values -1.
431    explicit IterableIntMap(const Graph& graph)
432      : Parent(graph) {}
433
434    /// \brief Constructor of the Map with a given value.
435    ///
436    /// Constructor of the Map with a given value.
437    explicit IterableIntMap(const Graph& graph, int value)
438      : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
439      if (value >= 0) {
440        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
441          lace(it);
442        }
443      }
444    }
445
446  private:
447   
448    void unlace(const Key& key) {
449      typename Parent::Value& node = Parent::operator[](key);
450      if (node.value < 0) return;
451      if (node.prev != INVALID) {
452        Parent::operator[](node.prev).next = node.next;
453      } else {
454        first[node.value] = node.next;
455      }
456      if (node.next != INVALID) {
457        Parent::operator[](node.next).prev = node.prev;
458      }
459      while (!first.empty() && first.back() == INVALID) {
460        first.pop_back();
461      }
462    }
463
464    void lace(const Key& key) {
465      typename Parent::Value& node = Parent::operator[](key);
466      if (node.value < 0) return;
467      if (node.value >= int(first.size())) {
468        first.resize(node.value + 1, INVALID);
469      }
470      node.prev = INVALID;
471      node.next = first[node.value];
472      if (node.next != INVALID) {
473        Parent::operator[](node.next).prev = key;       
474      }
475      first[node.value] = key;
476    }
477
478  public:
479
480    /// Indicates that the map if reference map.
481    typedef True ReferenceMapTag;
482
483    /// \brief Refernce to the value of the map.
484    ///
485    /// This class is near to similar to the int type. It can
486    /// be converted to int and it has the same operators.
487    class Reference {
488      friend class IterableIntMap;
489    private:
490      Reference(IterableIntMap& map, const Key& key)
491        : _key(key), _map(map) {}
492    public:
493
494      Reference& operator=(const Reference& value) {
495        _map.set(_key, static_cast<const int&>(value));
496        return *this;
497      }
498
499      operator const int&() const {
500        return static_cast<const IterableIntMap&>(_map)[_key];
501      }
502
503      Reference& operator=(int value) {
504        _map.set(_key, value);
505        return *this;
506      }
507      Reference& operator++() {
508        _map.set(_key, _map[_key] + 1);
509        return *this;   
510      }
511      int operator++(int) {
512        int value = _map[_key];
513        _map.set(_key, value + 1);
514        return value;   
515      }
516      Reference& operator--() {
517        _map.set(_key, _map[_key] - 1);
518        return *this;   
519      }
520      int operator--(int) {
521        int value = _map[_key];
522        _map.set(_key, value - 1);
523        return value;   
524      }
525      Reference& operator+=(int value) {
526        _map.set(_key, _map[_key] + value);
527        return *this;
528      }
529      Reference& operator-=(int value) {
530        _map.set(_key, _map[_key] - value);
531        return *this;
532      }
533      Reference& operator*=(int value) {
534        _map.set(_key, _map[_key] * value);
535        return *this;
536      }
537      Reference& operator/=(int value) {
538        _map.set(_key, _map[_key] / value);
539        return *this;
540      }
541      Reference& operator%=(int value) {
542        _map.set(_key, _map[_key] % value);
543        return *this;
544      }
545      Reference& operator&=(int value) {
546        _map.set(_key, _map[_key] & value);
547        return *this;
548      }
549      Reference& operator|=(int value) {
550        _map.set(_key, _map[_key] | value);
551        return *this;
552      }
553      Reference& operator^=(int value) {
554        _map.set(_key, _map[_key] ^ value);
555        return *this;
556      }
557      Reference& operator<<=(int value) {
558        _map.set(_key, _map[_key] << value);
559        return *this;
560      }
561      Reference& operator>>=(int value) {
562        _map.set(_key, _map[_key] >> value);
563        return *this;
564      }
565
566    private:
567      Key _key;
568      IterableIntMap& _map;
569    };
570
571    /// The const reference type.   
572    typedef const Value& ConstReference;
573
574    /// \brief Gives back the maximal value plus one.
575    ///
576    /// Gives back the maximal value plus one.
577    unsigned int size() const {
578      return first.size();
579    }
580   
581    /// \brief Set operation of the map.
582    ///
583    /// Set operation of the map.
584    void set(const Key& key, const Value& value) {
585      unlace(key);
586      Parent::operator[](key).value = value;
587      lace(key);
588    }
589
590    /// \brief Const subscript operator of the map.
591    ///
592    /// Const subscript operator of the map.
593    const Value& operator[](const Key& key) const {
594      return Parent::operator[](key).value;
595    }
596
597    /// \brief Subscript operator of the map.
598    ///
599    /// Subscript operator of the map.
600    Reference operator[](const Key& key) {
601      return Reference(*this, key);
602    }
603
604    /// \brief Iterator for the keys with the same value.
605    ///
606    /// Iterator for the keys with the same value. It works
607    /// like a graph item iterator in the map, it can be converted
608    /// the item type of the map, incremented with \c ++ operator, and
609    /// if the iterator leave the last valid item it will be equal to
610    /// \c INVALID.
611    class ItemIt : public _Item {
612    public:
613      typedef _Item Parent;
614
615      /// \brief Invalid constructor \& conversion.
616      ///
617      /// This constructor initializes the item to be invalid.
618      /// \sa Invalid for more details.
619      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
620
621      /// \brief Creates an iterator with a value.
622      ///
623      /// Creates an iterator with a value. It iterates on the
624      /// keys which have the given value.
625      /// \param map The IterableIntMap
626      /// \param value The value
627      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
628        if (value < 0 || value >= int(_map->first.size())) {     
629          Parent::operator=(INVALID);
630        } else {
631          Parent::operator=(_map->first[value]);
632        }
633      }
634
635      /// \brief Increment operator.
636      ///
637      /// Increment Operator.
638      ItemIt& operator++() {
639        Parent::operator=(_map->IterableIntMap::Parent::
640                          operator[](static_cast<Parent&>(*this)).next);
641        return *this;
642      }
643
644
645    private:
646      const IterableIntMap* _map;
647    };
648
649  protected:
650   
651    virtual void erase(const Key& key) {
652      unlace(key);
653      Parent::erase(key);
654    }
655
656    virtual void erase(const std::vector<Key>& keys) {
657      for (int i = 0; i < int(keys.size()); ++i) {
658        unlace(keys[i]);
659      }
660      Parent::erase(keys);
661    }
662
663    virtual void clear() {
664      first.clear();
665      Parent::clear();
666    }
667
668  private:
669    std::vector<_Item> first;
670  };
671
672  namespace _iterable_maps_bits {
673    template <typename Item, typename Value>
674    struct IterableValueMapNode {
675      IterableValueMapNode(Value _value = Value()) : value(_value) {}
676      Item prev, next;
677      Value value;
678    };
679  }
680
681  ///\ingroup graph_maps
682  ///
683  /// \brief Dynamic iterable map for comparable values.
684  ///
685  /// This class provides a special graph map type which can store
686  /// for each graph item(node, edge, etc.) a value. For each
687  /// value it is possible to iterate on the keys which mapped to the
688  /// given value. The type stores for each value a linked list with
689  /// the items which mapped to the value, and the values are stored
690  /// in balanced binary tree. The values of the map can be accessed
691  /// with stl compatible forward iterator.
692  ///
693  /// This type is not reference map so it cannot be modified with
694  /// the subscription operator.
695  ///
696  /// \see InvertableMap
697  ///
698  /// \param _Graph The graph type.
699  /// \param _Item One of the graph's item type, the key of the map.
700  /// \param _Value Any comparable value type.
701  template <typename _Graph, typename _Item, typename _Value>
702  class IterableValueMap
703    : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
704                                       IterableValueMapNode<_Item, _Value> > >{
705  public:
706    typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
707                                   IterableValueMapNode<_Item, _Value> > >
708    Parent;
709
710    /// The key type
711    typedef _Item Key;
712    /// The value type
713    typedef _Value Value;
714    /// The graph type
715    typedef _Graph Graph;
716
717  public:
718
719    /// \brief Constructor of the Map with a given value.
720    ///
721    /// Constructor of the Map with a given value.
722    explicit IterableValueMap(const Graph& graph,
723                              const Value& value = Value())
724      : Parent(graph, _iterable_maps_bits::
725               IterableValueMapNode<_Item, _Value>(value)) {
726      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
727        lace(it);
728      }
729    }
730
731  protected:
732   
733    void unlace(const Key& key) {
734      typename Parent::Value& node = Parent::operator[](key);
735      if (node.prev != INVALID) {
736        Parent::operator[](node.prev).next = node.next;
737      } else {
738        if (node.next != INVALID) {
739          first[node.value] = node.next;
740        } else {
741          first.erase(node.value);
742        }
743      }
744      if (node.next != INVALID) {
745        Parent::operator[](node.next).prev = node.prev;
746      }
747    }
748
749    void lace(const Key& key) {
750      typename Parent::Value& node = Parent::operator[](key);
751      typename std::map<Value, Key>::iterator it = first.find(node.value);
752      if (it == first.end()) {
753        node.prev = node.next = INVALID;
754        if (node.next != INVALID) {
755          Parent::operator[](node.next).prev = key;     
756        }
757        first.insert(make_pair(node.value, key));
758      } else {
759        node.prev = INVALID;
760        node.next = it->second;
761        if (node.next != INVALID) {
762          Parent::operator[](node.next).prev = key;     
763        }
764        it->second = key;
765      }
766    }
767
768  public:
769
770    /// \brief Forward iterator for values.
771    ///
772    /// This iterator is an stl compatible forward
773    /// iterator on the values of the map. The values can
774    /// be accessed in the [beginValue, endValue) range.
775    ///
776    class ValueIterator
777      : public std::iterator<std::forward_iterator_tag, Value> {
778      friend class IterableValueMap;
779    private:
780      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
781        : it(_it) {}
782    public:
783     
784      ValueIterator() {}
785
786      ValueIterator& operator++() { ++it; return *this; }
787      ValueIterator operator++(int) {
788        ValueIterator tmp(*this);
789        operator++();
790        return tmp;
791      }
792
793      const Value& operator*() const { return it->first; }
794      const Value* operator->() const { return &(it->first); }
795
796      bool operator==(ValueIterator jt) const { return it == jt.it; }
797      bool operator!=(ValueIterator jt) const { return it != jt.it; }
798     
799    private:
800      typename std::map<Value, Key>::const_iterator it;
801    };
802
803    /// \brief Returns an iterator to the first value.
804    ///
805    /// Returns an stl compatible iterator to the
806    /// first value of the map. The values of the
807    /// map can be accessed in the [beginValue, endValue)
808    /// range.
809    ValueIterator beginValue() const {
810      return ValueIterator(first.begin());
811    }
812
813    /// \brief Returns an iterator after the last value.
814    ///
815    /// Returns an stl compatible iterator after the
816    /// last value of the map. The values of the
817    /// map can be accessed in the [beginValue, endValue)
818    /// range.
819    ValueIterator endValue() const {
820      return ValueIterator(first.end());
821    }
822
823    /// \brief Set operation of the map.
824    ///
825    /// Set operation of the map.
826    void set(const Key& key, const Value& value) {
827      unlace(key);
828      Parent::operator[](key).value = value;
829      lace(key);
830    }
831
832    /// \brief Const subscript operator of the map.
833    ///
834    /// Const subscript operator of the map.
835    const Value& operator[](const Key& key) const {
836      return Parent::operator[](key).value;
837    }
838
839    /// \brief Iterator for the keys with the same value.
840    ///
841    /// Iterator for the keys with the same value. It works
842    /// like a graph item iterator in the map, it can be converted
843    /// the item type of the map, incremented with \c ++ operator, and
844    /// if the iterator leave the last valid item it will be equal to
845    /// \c INVALID.
846    class ItemIt : public _Item {
847    public:
848      typedef _Item Parent;
849
850      /// \brief Invalid constructor \& conversion.
851      ///
852      /// This constructor initializes the item to be invalid.
853      /// \sa Invalid for more details.
854      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
855
856      /// \brief Creates an iterator with a value.
857      ///
858      /// Creates an iterator with a value. It iterates on the
859      /// keys which have the given value.
860      /// \param map The IterableValueMap
861      /// \param value The value
862      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
863        typename std::map<Value, Key>::const_iterator it =
864          map.first.find(value);
865        if (it == map.first.end()) {     
866          Parent::operator=(INVALID);
867        } else {
868          Parent::operator=(it->second);
869        }
870      }
871
872      /// \brief Increment operator.
873      ///
874      /// Increment Operator.
875      ItemIt& operator++() {
876        Parent::operator=(_map->IterableValueMap::Parent::
877                          operator[](static_cast<Parent&>(*this)).next);
878        return *this;
879      }
880
881
882    private:
883      const IterableValueMap* _map;
884    };
885
886  protected:
887   
888    virtual void add(const Key& key) {
889      Parent::add(key);
890      unlace(key);
891    }
892
893    virtual void add(const std::vector<Key>& keys) {
894      Parent::add(keys);
895      for (int i = 0; i < int(keys.size()); ++i) {
896        lace(keys[i]);
897      }
898    }
899
900    virtual void erase(const Key& key) {
901      unlace(key);
902      Parent::erase(key);
903    }
904
905    virtual void erase(const std::vector<Key>& keys) {
906      for (int i = 0; i < int(keys.size()); ++i) {
907        unlace(keys[i]);
908      }
909      Parent::erase(keys);
910    }
911
912    virtual void build() {
913      Parent::build();
914      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
915        lace(it);
916      }
917    }
918
919    virtual void clear() {
920      first.clear();
921      Parent::clear();
922    }
923
924  private:
925    std::map<Value, Key> first;
926  };
927
928  /// @}
929}
930
931#endif
Note: See TracBrowser for help on using the repository browser.