COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 2000:ebcc93ead7da

Last change on this file since 2000:ebcc93ead7da was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

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/bits/traits.h>
20#include <lemon/bits/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.