COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/iterable_maps.h @ 2158:0b620ff10e7c

Last change on this file since 2158:0b620ff10e7c was 2112:f27dfd29c5c0, checked in by Balazs Dezso, 18 years ago

Make explicit constructors

File size: 25.1 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#include <lemon/bits/map_extender.h>
24
25#include <vector>
26#include <map>
27
28#include <iterator>
29#include <limits>
30
31///\ingroup maps
32///\file
33///\brief Maps that makes it possible to iterate through the keys having
34///a certain value
35///
36///
37
38
39namespace lemon {
40
41  ///\ingroup graph_maps
42  ///
43  /// \brief Dynamic iterable bool map.
44  ///
45  /// This class provides a special graph map type which can store
46  /// for each graph item(node, edge, etc.) a bool value. For both
47  /// the true and the false it is possible to iterate on the keys which
48  /// mapped to the given value.
49  ///
50  /// \param _Graph The graph type.
51  /// \param _Item One of the graph's item type, the key of the map.
52  template <typename _Graph, typename _Item>
53  class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
54  private:
55    typedef _Graph Graph;
56   
57    typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
58    typedef DefaultMap<_Graph, _Item, int> Parent;
59   
60    std::vector<_Item> array;
61    int sep;
62
63    const Graph& graph;
64
65  public:
66
67    /// Indicates that the map if reference map.
68    typedef True ReferenceMapTag;
69
70    /// The key type
71    typedef _Item Key;
72    /// The value type
73    typedef bool Value;
74    /// The const reference type.   
75    typedef const Value& ConstReference;
76
77  private:
78
79    int position(const Key& key) const {
80      return Parent::operator[](key);
81    }
82
83  public:
84
85    /// \brief Refernce to the value of the map.
86    ///
87    /// This class is near to similar to the bool type. It can
88    /// be converted to bool and it has the same operators.
89    class Reference {
90      friend class IterableBoolMap;
91    private:
92      Reference(IterableBoolMap& map, const Key& key)
93        : _key(key), _map(map) {}
94    public:
95
96      Reference& operator=(const Reference& value) {
97        _map.set(_key, (bool)value);
98        return *this;
99      }
100
101      operator bool() const {
102        return static_cast<const IterableBoolMap&>(_map)[_key];
103      }
104
105      Reference& operator=(bool value) {
106        _map.set(_key, value);
107        return *this;
108      }
109      Reference& operator&=(bool value) {
110        _map.set(_key, _map[_key] & value);
111        return *this;   
112      }
113      Reference& operator|=(bool value) {
114        _map.set(_key, _map[_key] | value);
115        return *this;   
116      }
117      Reference& operator^=(bool value) {
118        _map.set(_key, _map[_key] ^ value);
119        return *this;   
120      }
121    private:
122      Key _key;
123      IterableBoolMap& _map;
124    };
125   
126    /// \brief Constructor of the Map with a default value.
127    ///
128    /// Constructor of the Map with a default value.
129    explicit IterableBoolMap(const Graph& _graph, bool def = false)
130      : Parent(_graph), graph(_graph) {
131      for (KeyIt it(graph); it != INVALID; ++it) {
132        Parent::set(it, array.size());
133        array.push_back(it);
134      }
135      sep = (def ? array.size() : 0);
136    }
137
138    /// \brief Const subscript operator of the map.
139    ///
140    /// Const subscript operator of the map.
141    bool operator[](const Key& key) const {
142      return position(key) < sep;
143    }
144
145    /// \brief Subscript operator of the map.
146    ///
147    /// Subscript operator of the map.
148    Reference operator[](const Key& key) {
149      return Reference(*this, key);
150    }
151
152    /// \brief Set operation of the map.
153    ///
154    /// Set operation of the map.
155    void set(const Key& key, bool value) {
156      int pos = position(key);
157      if (value) {
158        if (pos < sep) return;
159        Key tmp = array[sep];
160        array[sep] = key;
161        Parent::set(key, sep);
162        array[pos] = tmp;
163        Parent::set(tmp, pos);
164        ++sep;
165      } else {
166        if (pos >= sep) return;
167        --sep;
168        Key tmp = array[sep];
169        array[sep] = key;
170        Parent::set(key, sep);
171        array[pos] = tmp;
172        Parent::set(tmp, pos);
173      }
174    }
175
176    /// \brief Returns the number of the keys mapped to true.
177    ///
178    /// Returns the number of the keys mapped to true.
179    int trueNum() const {
180      return sep;
181    }
182   
183    /// \brief Returns the number of the keys mapped to false.
184    ///
185    /// Returns the number of the keys mapped to false.
186    int falseNum() const {
187      return array.size() - sep;
188    }
189
190    /// \brief Iterator for the keys mapped to true.
191    ///
192    /// Iterator for the keys mapped to true. It works
193    /// like a graph item iterator in the map, it can be converted
194    /// the key type of the map, incremented with \c ++ operator, and
195    /// if the iterator leave the last valid key it will be equal to
196    /// \c INVALID.
197    class TrueIt : public Key {
198    public:
199      typedef Key Parent;
200     
201      /// \brief Creates an iterator.
202      ///
203      /// Creates an iterator. It iterates on the
204      /// keys which mapped to true.
205      /// \param _map The IterableIntMap
206      explicit TrueIt(const IterableBoolMap& _map)
207        : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
208          map(&_map) {}
209
210      /// \brief Invalid constructor \& conversion.
211      ///
212      /// This constructor initializes the key to be invalid.
213      /// \sa Invalid for more details.
214      TrueIt(Invalid) : Parent(INVALID), map(0) {}
215
216      /// \brief Increment operator.
217      ///
218      /// Increment Operator.
219      TrueIt& operator++() {
220        int pos = map->position(*this);
221        Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
222        return *this;
223      }
224
225     
226    private:
227      const IterableBoolMap* map;
228    };
229
230    /// \brief Iterator for the keys mapped to false.
231    ///
232    /// Iterator for the keys mapped to false. It works
233    /// like a graph item iterator in the map, it can be converted
234    /// the key type of the map, incremented with \c ++ operator, and
235    /// if the iterator leave the last valid key it will be equal to
236    /// \c INVALID.
237    class FalseIt : public Key {
238    public:
239      typedef Key Parent;
240     
241      /// \brief Creates an iterator.
242      ///
243      /// Creates an iterator. It iterates on the
244      /// keys which mapped to false.
245      /// \param _map The IterableIntMap
246      explicit FalseIt(const IterableBoolMap& _map)
247        : Parent(_map.sep < (int)_map.array.size() ?
248                 _map.array.back() : INVALID), map(&_map) {}
249
250      /// \brief Invalid constructor \& conversion.
251      ///
252      /// This constructor initializes the key to be invalid.
253      /// \sa Invalid for more details.
254      FalseIt(Invalid) : Parent(INVALID), map(0) {}
255
256      /// \brief Increment operator.
257      ///
258      /// Increment Operator.
259      FalseIt& operator++() {
260        int pos = map->position(*this);
261        Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
262        return *this;
263      }
264
265    private:
266      const IterableBoolMap* map;
267    };
268
269    /// \brief Iterator for the keys mapped to a given value.
270    ///
271    /// Iterator for the keys mapped to a given value. It works
272    /// like a graph item iterator in the map, it can be converted
273    /// the key type of the map, incremented with \c ++ operator, and
274    /// if the iterator leave the last valid key it will be equal to
275    /// \c INVALID.
276    class ItemIt : public Key {
277    public:
278      typedef Key Parent;
279     
280      /// \brief Creates an iterator.
281      ///
282      /// Creates an iterator. It iterates on the
283      /// keys which mapped to false.
284      /// \param _map The IterableIntMap
285      /// \param value Which elements should be iterated.
286      ItemIt(const IterableBoolMap& _map, bool value)
287        : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
288                 (_map.sep < (int)_map.array.size() ?
289                  _map.array.back() : INVALID)), map(&_map) {}
290
291      /// \brief Invalid constructor \& conversion.
292      ///
293      /// This constructor initializes the key to be invalid.
294      /// \sa Invalid for more details.
295      ItemIt(Invalid) : Parent(INVALID), map(0) {}
296
297      /// \brief Increment operator.
298      ///
299      /// Increment Operator.
300      ItemIt& operator++() {
301        int pos = map->position(*this);
302        int sep = pos >= map->sep ? map->sep : 0;
303        Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
304        return *this;
305      }
306
307    private:
308      const IterableBoolMap* map;
309    };
310
311  protected:
312   
313    virtual void add(const Key& key) {
314      Parent::add(key);
315      Parent::set(key, array.size());
316      array.push_back(key);
317    }
318
319    virtual void add(const std::vector<Key>& keys) {
320      Parent::add(keys);
321      for (int i = 0; i < (int)keys.size(); ++i) {
322        Parent::set(keys[i], array.size());
323        array.push_back(keys[i]);
324      }
325    }
326
327    virtual void erase(const Key& key) {
328      int pos = position(key);
329      if (pos < sep) {
330        --sep;
331        Parent::set(array[sep], pos);
332        array[pos] = array[sep];
333        Parent::set(array.back(), sep);
334        array[sep] = array.back();
335        array.pop_back();
336      } else {
337        Parent::set(array.back(), pos);
338        array[pos] = array.back();
339        array.pop_back();
340      }
341      Parent::erase(key);
342    }
343
344    virtual void erase(const std::vector<Key>& keys) {
345      for (int i = 0; i < (int)keys.size(); ++i) {
346        int pos = position(keys[i]);
347        if (pos < sep) {
348          --sep;
349          Parent::set(array[sep], pos);
350          array[pos] = array[sep];
351          Parent::set(array.back(), sep);
352          array[sep] = array.back();
353          array.pop_back();
354        } else {
355          Parent::set(array.back(), pos);
356          array[pos] = array.back();
357          array.pop_back();
358        }
359      }
360      Parent::erase(keys);
361    }   
362
363    virtual void build() {
364      Parent::build();
365      for (KeyIt it(graph); it != INVALID; ++it) {
366        Parent::set(it, array.size());
367        array.push_back(it);
368      }
369      sep = 0;     
370    }
371
372    virtual void clear() {
373      array.clear();
374      sep = 0;
375      Parent::clear();
376    }
377   
378  };
379 
380
381  namespace _iterable_maps_bits {
382    template <typename Item>
383    struct IterableIntMapNode {
384      IterableIntMapNode() : value(-1) {}
385      IterableIntMapNode(int _value) : value(_value) {}
386      Item prev, next;
387      int value;
388    };
389  }
390
391  ///\ingroup graph_maps
392  ///
393  /// \brief Dynamic iterable integer map.
394  ///
395  /// This class provides a special graph map type which can store
396  /// for each graph item(node, edge, etc.) an integer value. For each
397  /// non negative value it is possible to iterate on the keys which
398  /// mapped to the given value.
399  ///
400  /// \param _Graph The graph type.
401  /// \param _Item One of the graph's item type, the key of the map.
402  template <typename _Graph, typename _Item>
403  class IterableIntMap
404    : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
405                                       IterableIntMapNode<_Item> > >{
406  public:
407    typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
408                                   IterableIntMapNode<_Item> > > 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 MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
693                                       IterableValueMapNode<_Item, _Value> > >{
694  public:
695    typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
696                                   IterableValueMapNode<_Item, _Value> > >
697    Parent;
698
699    /// The key type
700    typedef _Item Key;
701    /// The value type
702    typedef _Value Value;
703    /// The graph type
704    typedef _Graph Graph;
705
706  public:
707
708    /// \brief Constructor of the Map with a given value.
709    ///
710    /// Constructor of the Map with a given value.
711    explicit IterableValueMap(const Graph& graph,
712                              const Value& value = Value())
713      : Parent(graph, _iterable_maps_bits::
714               IterableValueMapNode<_Item, _Value>(value)) {
715      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
716        lace(it);
717      }
718    }
719
720  protected:
721   
722    void unlace(const Key& key) {
723      typename Parent::Value& node = Parent::operator[](key);
724      if (node.prev != INVALID) {
725        Parent::operator[](node.prev).next = node.next;
726      } else {
727        if (node.next != INVALID) {
728          first[node.value] = node.next;
729        } else {
730          first.erase(node.value);
731        }
732      }
733      if (node.next != INVALID) {
734        Parent::operator[](node.next).prev = node.prev;
735      }
736    }
737
738    void lace(const Key& key) {
739      typename Parent::Value& node = Parent::operator[](key);
740      typename std::map<Value, Key>::iterator it = first.find(node.value);
741      if (it == first.end()) {
742        node.prev = node.next = INVALID;
743        if (node.next != INVALID) {
744          Parent::operator[](node.next).prev = key;     
745        }
746        first.insert(make_pair(node.value, key));
747      } else {
748        node.prev = INVALID;
749        node.next = it->second;
750        if (node.next != INVALID) {
751          Parent::operator[](node.next).prev = key;     
752        }
753        it->second = key;
754      }
755    }
756
757  public:
758
759    /// \brief Forward iterator for values.
760    ///
761    /// This iterator is an stl compatible forward
762    /// iterator on the values of the map. The values can
763    /// be accessed in the [beginValue, endValue) range.
764    ///
765    class ValueIterator
766      : public std::iterator<std::forward_iterator_tag, Value> {
767      friend class IterableValueMap;
768    private:
769      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
770        : it(_it) {}
771    public:
772     
773      ValueIterator() {}
774
775      ValueIterator& operator++() { ++it; return *this; }
776      ValueIterator operator++(int) {
777        ValueIterator tmp(*this);
778        operator++();
779        return tmp;
780      }
781
782      const Value& operator*() const { return it->first; }
783      const Value* operator->() const { return &(it->first); }
784
785      bool operator==(ValueIterator jt) const { return it == jt.it; }
786      bool operator!=(ValueIterator jt) const { return it != jt.it; }
787     
788    private:
789      typename std::map<Value, Key>::const_iterator it;
790    };
791
792    /// \brief Returns an iterator to the first value.
793    ///
794    /// Returns an stl compatible iterator to the
795    /// first value of the map. The values of the
796    /// map can be accessed in the [beginValue, endValue)
797    /// range.
798    ValueIterator beginValue() const {
799      return ValueIterator(first.begin());
800    }
801
802    /// \brief Returns an iterator after the last value.
803    ///
804    /// Returns an stl compatible iterator after the
805    /// last value of the map. The values of the
806    /// map can be accessed in the [beginValue, endValue)
807    /// range.
808    ValueIterator endValue() const {
809      return ValueIterator(first.end());
810    }
811
812    /// \brief Set operation of the map.
813    ///
814    /// Set operation of the map.
815    void set(const Key& key, const Value& value) {
816      unlace(key);
817      Parent::operator[](key).value = value;
818      lace(key);
819    }
820
821    /// \brief Const subscript operator of the map.
822    ///
823    /// Const subscript operator of the map.
824    const Value& operator[](const Key& key) const {
825      return Parent::operator[](key).value;
826    }
827
828    /// \brief Iterator for the keys with the same value.
829    ///
830    /// Iterator for the keys with the same value. It works
831    /// like a graph item iterator in the map, it can be converted
832    /// the item type of the map, incremented with \c ++ operator, and
833    /// if the iterator leave the last valid item it will be equal to
834    /// \c INVALID.
835    class ItemIt : public _Item {
836    public:
837      typedef _Item Parent;
838
839      /// \brief Invalid constructor \& conversion.
840      ///
841      /// This constructor initializes the item to be invalid.
842      /// \sa Invalid for more details.
843      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
844
845      /// \brief Creates an iterator with a value.
846      ///
847      /// Creates an iterator with a value. It iterates on the
848      /// keys which have the given value.
849      /// \param map The IterableValueMap
850      /// \param value The value
851      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
852        typename std::map<Value, Key>::const_iterator it =
853          map.first.find(value);
854        if (it == map.first.end()) {     
855          Parent::operator=(INVALID);
856        } else {
857          Parent::operator=(it->second);
858        }
859      }
860
861      /// \brief Increment operator.
862      ///
863      /// Increment Operator.
864      ItemIt& operator++() {
865        Parent::operator=(_map->IterableValueMap::Parent::
866                          operator[](static_cast<Parent&>(*this)).next);
867        return *this;
868      }
869
870
871    private:
872      const IterableValueMap* _map;
873    };
874
875  protected:
876   
877    virtual void add(const Key& key) {
878      Parent::add(key);
879      unlace(key);
880    }
881
882    virtual void add(const std::vector<Key>& keys) {
883      Parent::add(keys);
884      for (int i = 0; i < (int)keys.size(); ++i) {
885        lace(keys[i]);
886      }
887    }
888
889    virtual void erase(const Key& key) {
890      unlace(key);
891      Parent::erase(key);
892    }
893
894    virtual void erase(const std::vector<Key>& keys) {
895      for (int i = 0; i < (int)keys.size(); ++i) {
896        unlace(keys[i]);
897      }
898      Parent::erase(keys);
899    }
900
901    virtual void build() {
902      Parent::build();
903      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
904        lace(it);
905      }
906    }
907
908    virtual void clear() {
909      first.clear();
910      Parent::clear();
911    }
912
913  private:
914    std::map<Value, Key> first;
915  };
916
917  /// @}
918}
Note: See TracBrowser for help on using the repository browser.