COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1953:d4f411003580

Last change on this file since 1953:d4f411003580 was 1953:d4f411003580, checked in by Alpar Juttner, 14 years ago

Polish the doc.

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.