COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 2339:c329fe995b40

Last change on this file since 2339:c329fe995b40 was 2210:25aab9493dd2, checked in by Balazs Dezso, 13 years ago

Add missing header sentry

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