COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1931:6abf67b02ff5

Last change on this file since 1931:6abf67b02ff5 was 1931:6abf67b02ff5, checked in by Balazs Dezso, 14 years ago

New iterable map with comparable values

it uses linked lists and balanced binary tree

IterableBoolMap? has ItemIt? type as the other iterable maps

InvertableMap? got ValueIterator?

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