COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 2108:f2c532541730

Last change on this file since 2108:f2c532541730 was 2031:080d51024ac5, checked in by Balazs Dezso, 18 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

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