COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 1990:15fb7a4ea6be

Last change on this file since 1990:15fb7a4ea6be was 1990:15fb7a4ea6be, checked in by Balazs Dezso, 18 years ago

Some classes assumed that the GraphMaps? should be inherited
from an ObserverBase?. These classes parents replaced with
DefaultMap? which cause that the graph maps should not be
inherited from the ObserverBase?.

File size: 25.0 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/traits.h>
20#include <lemon/invalid.h>
21
22#include <lemon/bits/default_map.h>
23
24#include <vector>
25#include <map>
26
27#include <iterator>
28#include <limits>
29
30///\ingroup maps
31///\file
32///\brief Maps that makes it possible to iterate through the keys having
33///a certain value
34///
35///
36
37
38namespace lemon {
39
40  ///\ingroup graph_maps
41  ///
42  /// \brief Dynamic iterable bool map.
43  ///
44  /// This class provides a special graph map type which can store
45  /// for each graph item(node, edge, etc.) a bool value. For both
46  /// the true and the false it is possible to iterate on the keys which
47  /// mapped to the given value.
48  ///
49  /// \param _Graph The graph type.
50  /// \param _Item One of the graph's item type, the key of the map.
51  template <typename _Graph, typename _Item>
52  class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
53  private:
54    typedef _Graph Graph;
55   
56    typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
57    typedef DefaultMap<_Graph, _Item, int> Parent;
58   
59    std::vector<_Item> array;
60    int sep;
61
62    const Graph& graph;
63
64  public:
65
66    /// Indicates that the map if reference map.
67    typedef True ReferenceMapTag;
68
69    /// The key type
70    typedef _Item Key;
71    /// The value type
72    typedef bool Value;
73    /// The const reference type.   
74    typedef const Value& ConstReference;
75
76  private:
77
78    int position(const Key& key) const {
79      return Parent::operator[](key);
80    }
81
82  public:
83
84    /// \brief Refernce to the value of the map.
85    ///
86    /// This class is near to similar to the bool type. It can
87    /// be converted to bool and it has the same operators.
88    class Reference {
89      friend class IterableBoolMap;
90    private:
91      Reference(IterableBoolMap& map, const Key& key)
92        : _key(key), _map(map) {}
93    public:
94
95      Reference& operator=(const Reference& value) {
96        _map.set(_key, (bool)value);
97        return *this;
98      }
99
100      operator bool() const {
101        return static_cast<const IterableBoolMap&>(_map)[_key];
102      }
103
104      Reference& operator=(bool value) {
105        _map.set(_key, value);
106        return *this;
107      }
108      Reference& operator&=(bool value) {
109        _map.set(_key, _map[_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    private:
121      Key _key;
122      IterableBoolMap& _map;
123    };
124   
125    /// \brief Constructor of the Map with a default value.
126    ///
127    /// Constructor of the Map with a default value.
128    IterableBoolMap(const Graph& _graph, bool def = false)
129      : Parent(_graph), graph(_graph) {
130      for (KeyIt it(graph); it != INVALID; ++it) {
131        Parent::set(it, array.size());
132        array.push_back(it);
133      }
134      sep = (def ? array.size() : 0);
135    }
136
137    /// \brief Const subscript operator of the map.
138    ///
139    /// Const subscript operator of the map.
140    bool operator[](const Key& key) const {
141      return position(key) < sep;
142    }
143
144    /// \brief Subscript operator of the map.
145    ///
146    /// Subscript operator of the map.
147    Reference operator[](const Key& key) {
148      return Reference(*this, key);
149    }
150
151    /// \brief Set operation of the map.
152    ///
153    /// Set operation of the map.
154    void set(const Key& key, bool value) {
155      int pos = position(key);
156      if (value) {
157        if (pos < sep) return;
158        Key tmp = array[sep];
159        array[sep] = key;
160        Parent::set(key, sep);
161        array[pos] = tmp;
162        Parent::set(tmp, pos);
163        ++sep;
164      } else {
165        if (pos >= sep) return;
166        --sep;
167        Key tmp = array[sep];
168        array[sep] = key;
169        Parent::set(key, sep);
170        array[pos] = tmp;
171        Parent::set(tmp, pos);
172      }
173    }
174
175    /// \brief Returns the number of the keys mapped to true.
176    ///
177    /// Returns the number of the keys mapped to true.
178    int trueNum() const {
179      return sep;
180    }
181   
182    /// \brief Returns the number of the keys mapped to false.
183    ///
184    /// Returns the number of the keys mapped to false.
185    int falseNum() const {
186      return array.size() - sep;
187    }
188
189    /// \brief Iterator for the keys mapped to true.
190    ///
191    /// Iterator for the keys mapped to true. It works
192    /// like a graph item iterator in the map, it can be converted
193    /// the key type of the map, incremented with \c ++ operator, and
194    /// if the iterator leave the last valid key it will be equal to
195    /// \c INVALID.
196    class TrueIt : public Key {
197    public:
198      typedef Key Parent;
199     
200      /// \brief Creates an iterator.
201      ///
202      /// Creates an iterator. It iterates on the
203      /// keys which mapped to true.
204      /// \param _map The IterableIntMap
205      TrueIt(const IterableBoolMap& _map)
206        : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
207          map(&_map) {}
208
209      /// \brief Invalid constructor \& conversion.
210      ///
211      /// This constructor initializes the key to be invalid.
212      /// \sa Invalid for more details.
213      TrueIt(Invalid) : Parent(INVALID), map(0) {}
214
215      /// \brief Increment operator.
216      ///
217      /// Increment Operator.
218      TrueIt& operator++() {
219        int pos = map->position(*this);
220        Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
221        return *this;
222      }
223
224     
225    private:
226      const IterableBoolMap* map;
227    };
228
229    /// \brief Iterator for the keys mapped to false.
230    ///
231    /// Iterator for the keys mapped to false. It works
232    /// like a graph item iterator in the map, it can be converted
233    /// the key type of the map, incremented with \c ++ operator, and
234    /// if the iterator leave the last valid key it will be equal to
235    /// \c INVALID.
236    class FalseIt : public Key {
237    public:
238      typedef Key Parent;
239     
240      /// \brief Creates an iterator.
241      ///
242      /// Creates an iterator. It iterates on the
243      /// keys which mapped to false.
244      /// \param _map The IterableIntMap
245      FalseIt(const IterableBoolMap& _map)
246        : Parent(_map.sep < (int)_map.array.size() ?
247                 _map.array.back() : INVALID), map(&_map) {}
248
249      /// \brief Invalid constructor \& conversion.
250      ///
251      /// This constructor initializes the key to be invalid.
252      /// \sa Invalid for more details.
253      FalseIt(Invalid) : Parent(INVALID), map(0) {}
254
255      /// \brief Increment operator.
256      ///
257      /// Increment Operator.
258      FalseIt& operator++() {
259        int pos = map->position(*this);
260        Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
261        return *this;
262      }
263
264    private:
265      const IterableBoolMap* map;
266    };
267
268    /// \brief Iterator for the keys mapped to a given value.
269    ///
270    /// Iterator for the keys mapped to a given value. It works
271    /// like a graph item iterator in the map, it can be converted
272    /// the key type of the map, incremented with \c ++ operator, and
273    /// if the iterator leave the last valid key it will be equal to
274    /// \c INVALID.
275    class ItemIt : public Key {
276    public:
277      typedef Key Parent;
278     
279      /// \brief Creates an iterator.
280      ///
281      /// Creates an iterator. It iterates on the
282      /// keys which mapped to false.
283      /// \param _map The IterableIntMap
284      /// \param value Which elements should be iterated.
285      ItemIt(const IterableBoolMap& _map, bool value)
286        : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
287                 (_map.sep < (int)_map.array.size() ?
288                  _map.array.back() : INVALID)), map(&_map) {}
289
290      /// \brief Invalid constructor \& conversion.
291      ///
292      /// This constructor initializes the key to be invalid.
293      /// \sa Invalid for more details.
294      ItemIt(Invalid) : Parent(INVALID), map(0) {}
295
296      /// \brief Increment operator.
297      ///
298      /// Increment Operator.
299      ItemIt& operator++() {
300        int pos = map->position(*this);
301        int sep = pos >= map->sep ? map->sep : 0;
302        Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
303        return *this;
304      }
305
306    private:
307      const IterableBoolMap* map;
308    };
309
310  protected:
311   
312    virtual void add(const Key& key) {
313      Parent::add(key);
314      Parent::set(key, array.size());
315      array.push_back(key);
316    }
317
318    virtual void add(const std::vector<Key>& keys) {
319      Parent::add(keys);
320      for (int i = 0; i < (int)keys.size(); ++i) {
321        Parent::set(keys[i], array.size());
322        array.push_back(keys[i]);
323      }
324    }
325
326    virtual void erase(const Key& key) {
327      int pos = position(key);
328      if (pos < sep) {
329        --sep;
330        Parent::set(array[sep], pos);
331        array[pos] = array[sep];
332        Parent::set(array.back(), sep);
333        array[sep] = array.back();
334        array.pop_back();
335      } else {
336        Parent::set(array.back(), pos);
337        array[pos] = array.back();
338        array.pop_back();
339      }
340      Parent::erase(key);
341    }
342
343    virtual void erase(const std::vector<Key>& keys) {
344      for (int i = 0; i < (int)keys.size(); ++i) {
345        int pos = position(keys[i]);
346        if (pos < sep) {
347          --sep;
348          Parent::set(array[sep], pos);
349          array[pos] = array[sep];
350          Parent::set(array.back(), sep);
351          array[sep] = array.back();
352          array.pop_back();
353        } else {
354          Parent::set(array.back(), pos);
355          array[pos] = array.back();
356          array.pop_back();
357        }
358      }
359      Parent::erase(keys);
360    }   
361
362    virtual void build() {
363      Parent::build();
364      for (KeyIt it(graph); it != INVALID; ++it) {
365        Parent::set(it, array.size());
366        array.push_back(it);
367      }
368      sep = 0;     
369    }
370
371    virtual void clear() {
372      array.clear();
373      sep = 0;
374      Parent::clear();
375    }
376   
377  };
378 
379
380  namespace _iterable_maps_bits {
381    template <typename Item>
382    struct IterableIntMapNode {
383      IterableIntMapNode() : value(-1) {}
384      IterableIntMapNode(int _value) : value(_value) {}
385      Item prev, next;
386      int value;
387    };
388  }
389
390  ///\ingroup graph_maps
391  ///
392  /// \brief Dynamic iterable integer map.
393  ///
394  /// This class provides a special graph map type which can store
395  /// for each graph item(node, edge, etc.) an integer value. For each
396  /// non negative value it is possible to iterate on the keys which
397  /// mapped to the given value.
398  ///
399  /// \param _Graph The graph type.
400  /// \param _Item One of the graph's item type, the key of the map.
401  template <typename _Graph, typename _Item>
402  class IterableIntMap
403    : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
404                           IterableIntMapNode<_Item> > {
405  public:
406    typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
407                       IterableIntMapNode<_Item> >
408    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 DefaultMap<_Graph, _Item, _iterable_maps_bits::
693                           IterableValueMapNode<_Item, _Value> > {
694  public:
695    typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
696                       IterableValueMapNode<_Item, _Value> > Parent;
697
698    /// The key type
699    typedef _Item Key;
700    /// The value type
701    typedef _Value Value;
702    /// The graph type
703    typedef _Graph Graph;
704
705  protected:
706
707    typedef typename ItemSetTraits<_Graph, Key>::ItemIt KeyIt;
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 (KeyIt it(*Parent::getGraph()); 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 (KeyIt it(*Parent::getGraph()); 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}
Note: See TracBrowser for help on using the repository browser.