COIN-OR::LEMON - Graph Library

Changeset 830:89dfa3bece81 in lemon-0.x


Ignore:
Timestamp:
09/12/04 21:32:21 (20 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1128
Message:

KeySet? and ValueSet? are inserted into the map structures.
They makes possible the iterating on the keys or values only.

Location:
src/hugo
Files:
1 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/Makefile.am

    r829 r830  
    2424        smart_graph.h                                                   \
    2525        sym_map.h                                                       \
    26         sym_map_factory.h                                               \
    2726        time_measure.h                                                  \
    2827        unionfind.h                                                     \
  • src/hugo/array_map.h

    r822 r830  
    252252    }
    253253
     254    /// The KeySet of the Map.
     255    typedef MapConstKeySet<ArrayMap> ConstKeySet;
     256
     257    /// KeySet getter function.
     258    ConstKeySet keySet() const {
     259      return ConstKeySet(*this);
     260    }
     261
     262    /// The ConstValueSet of the Map.
     263    typedef MapConstValueSet<ArrayMap> ConstValueSet;
     264
     265    /// ConstValueSet getter function.
     266    ConstValueSet valueSet() const {
     267      return ConstValueSet(*this);
     268    }
     269
     270    /// The ValueSet of the Map.
     271    typedef MapValueSet<ArrayMap> ValueSet;
     272
     273    /// ValueSet getter function.
     274    ValueSet valueSet() {
     275      return ValueSet(*this);
     276    }
     277
    254278  private:
    255279     
  • src/hugo/map_iterator.h

    r822 r830  
    55#include <hugo/extended_pair.h>
    66
     7///\ingroup graphmaps
     8///\file
     9///\brief Iterators on the maps.
     10
    711namespace hugo {
    812
    9 
    10   template <typename Map>
    11   class MapIterator;
    12 
    13   template <typename Map>
    14   class MapConstIterator;
    15 
    16   /** Compatible iterator with the stl maps' iterators.
    17    *  It iterates on pairs of a key and a value.
    18    */
    19   template <typename Map> 
    20   class MapIterator {
    21     //    friend class Map;
    22     friend class MapConstIterator<Map>;
    23 
    24   public:
    25 
     13  /// \addtogroup graphmaps
     14  /// @{
     15
     16  /** The base class all of the map iterators.
     17   *  The class defines the typedefs of the iterators,
     18   *  simple step functions and equality operators.
     19   */
     20
     21  template <typename Map>
     22  class MapIteratorBase {
     23
     24  public:
    2625    /// The key type of the iterator.
    2726    typedef typename Map::KeyType KeyType;
     
    4241    /// The pointer type of the iterator.
    4342    typedef typename Map::ConstPointerType ConstPointerType;
     43
     44  protected:
     45
     46    KeyIt it;
     47
     48    /// Default constructor.
     49    MapIteratorBase() {}
     50
     51    /// KeyIt initialized MapIteratorBase constructor.
     52    MapIteratorBase(const KeyIt pit) : it(pit) {}
     53
     54  public:
     55
     56    /// Stepping forward in the map.   
     57    void increment() {
     58      ++it;
     59    }
     60
     61    /// The equality operator of the map.
     62    bool operator==(const MapIteratorBase& pit) const {
     63      return pit.it == it;
     64    }
     65       
     66    /// The not-equality operator of the map.
     67    bool operator!=(const MapIteratorBase& pit) const {
     68      return !(*this == pit);
     69    }
     70  };
     71
     72  template <typename Map> class MapConstIterator;
     73
     74  /** Compatible iterator with the stl maps' iterators.
     75   * It iterates on pairs of a key and a value.
     76   */
     77  template <typename Map> 
     78  class MapIterator : public MapIteratorBase<Map> {
     79
     80    friend class MapConstIterator<Map>;
     81
     82  public:
     83
     84    /// The key type of the iterator.
     85    typedef typename Map::KeyType KeyType;
     86    /// The iterator to iterate on the keys.
     87    typedef typename Map::KeyIt KeyIt;
     88
     89    /// The value type of the iterator.
     90    typedef typename Map::ValueType ValueType;
     91    /// The reference type of the iterator.
     92    typedef typename Map::ReferenceType ReferenceType;
     93    /// The pointer type of the iterator.
     94    typedef typename Map::PointerType PointerType;
     95
     96    /// The const value type of the iterator.
     97    typedef typename Map::ConstValueType ConstValueType;
     98    /// The const reference type of the iterator.
     99    typedef typename Map::ConstReferenceType ConstReferenceType;
     100    /// The pointer type of the iterator.
     101    typedef typename Map::ConstPointerType ConstPointerType;
    44102   
    45103  public:
    46104
    47     /** Constructor to initalize the the iterators returned
    48      *  by the begin() and end().
    49      */
    50     MapIterator (Map& pmap, const KeyIt& pit)
    51       : map(&pmap), it(pit) {}
    52 
    53   public:
    54 
    55     /** Default constructor.
    56      */
    57     MapIterator() {}
    58 
     105    /// The reference type of the iterator.
    59106    typedef extended_pair<const KeyType&, const KeyType&,
    60107      ReferenceType, ReferenceType> PairReferenceType;
    61108
    62     /** Dereference operator for map.
    63      */ 
     109    /// Default constructor.
     110    MapIterator() {}
     111
     112    /// Constructor to initalize the iterators returned
     113    /// by the begin() and end().
     114    MapIterator(Map& pmap, const KeyIt& pit)
     115      : MapIteratorBase<Map>(pit), map(&pmap) {}
     116
     117    /// Dereference operator for the iterator.
    64118    PairReferenceType operator*() {
    65119      return PairReferenceType(it, (*map)[it]);
    66120    }
    67121
     122    /// The pointer type of the iterator.
    68123    class PairPointerType {
    69124      friend class MapIterator;
     
    76131    };
    77132
    78     /** Arrow operator for map.
    79      */ 
     133    /// Arrow operator for the iterator.
    80134    PairPointerType operator->() {
    81135      return PairPointerType(it, ((*map)[it]));
    82136    }
    83 
    84     /** The pre increment operator of the map.
    85      */
     137       
     138    /// The pre increment operator of the iterator.
    86139    MapIterator& operator++() {
    87       ++it;
     140      increment();
    88141      return *this;
    89142    }
    90143
    91     /** The post increment operator of the map.
    92      */
     144    /// The post increment operator of the iterator.
    93145    MapIterator operator++(int) {
    94146      MapIterator tmp(it);
    95       ++it;
     147      increment();
    96148      return tmp;
    97149    }
    98150
    99     /** The equality operator of the map.
    100      */
    101     bool operator==(const MapIterator& p_it) const {
    102       return p_it.it == it;
    103     }
    104        
    105     /** The not-equality operator of the map.
    106      */
    107     bool operator!=(const MapIterator& p_it) const {
    108       return !(*this == p_it);
    109     }
    110 
    111     /** The equality operator of the map.
    112      */
    113     bool operator==(const MapConstIterator<Map>& p_it) const {
    114       return p_it.it == it;
    115     }
    116        
    117     /** The not-equality operator of the map.
    118      */
    119     bool operator!=(const MapConstIterator<Map>& p_it) const {
    120       return !(*this == p_it);
    121     }
    122        
    123151  private:
    124152    Map* map;
    125     KeyIt it;
    126153  };
    127154
     
    130157   */
    131158  template <typename Map>
    132   class MapConstIterator {
    133     // friend class Map;
    134     friend class MapIterator<Map>;
    135 
     159  class MapConstIterator : public MapIteratorBase<Map> {
     160   
    136161  public:
    137162
     
    157182  public:   
    158183
    159     /** Constructor to initalize the the iterators returned
    160      *  by the begin() and end().
    161      */
    162 
    163     MapConstIterator (const Map& pmap, const KeyIt& pit)
    164       : map(&pmap), it(pit) {}
    165 
    166   public:
    167 
    168     /** Default constructor.
    169      */
     184    /// Default constructor.
    170185    MapConstIterator() {}
    171186
     187    /// Constructor to initalize the the iterators returned
     188    ///  by the begin() and end().
     189    MapConstIterator(const Map& pmap, const KeyIt& pit)
     190      : MapIteratorBase<Map>(pit), map(&pmap) {}
     191
     192    /// Constructor to create const iterator from a non const.
     193    MapConstIterator(const MapIterator<Map>& pit) {
     194      it = pit.it;
     195      map = pit.map;
     196    }
     197
     198    /// The reference type of map.
    172199    typedef extended_pair<const KeyType&, const KeyType&,
    173200      ConstReferenceType, ConstReferenceType> PairReferenceType;
    174201
    175     /** Dereference operator for map.
    176      */ 
     202    /// Dereference operator for the iterator.
    177203    PairReferenceType operator*() {
    178204      return PairReferenceType(it, (*map)[it]);
    179205    }
    180206
     207    /// The pointer type of the iterator.
    181208    class PairPointerType {
    182209      friend class MapConstIterator;
     
    189216    };
    190217
    191     /** Arrow operator for map.
    192      */ 
     218    /// Arrow operator for the iterator.
    193219    PairPointerType operator->() {
    194220      return PairPointerType(it, ((*map)[it]));
    195221    }
    196222
    197     /** The pre increment operator of the map.
    198      */
     223    /// The pre increment operator of the iterator.
    199224    MapConstIterator& operator++() {
    200       ++it;
     225      increment();
    201226      return *this;
    202227    }
    203228
    204     /** The post increment operator of the map.
    205      */
     229    /// The post increment operator of the iterator.
    206230    MapConstIterator operator++(int) {
    207231      MapConstIterator<Map> tmp(it);
    208       ++it;
     232      increment();
    209233      return tmp;
    210234    }
    211235
    212     /** The equality operator of the map.
    213      */
    214     bool operator==(const MapIterator<Map>& p_it) const {
    215       return p_it.it == it;
    216     }
    217        
    218     /** The not-equality operator of the map.
    219      */
    220     bool operator!=(const MapIterator<Map>& p_it) const {
    221       return !(*this == p_it);
    222     }
    223 
    224     /** The equality operator of the map.
    225      */
    226     bool operator==(const MapConstIterator& p_it) const {
    227       return p_it.it == it;
    228     }
    229        
    230     /** The not-equality operator of the map.
    231      */
    232     bool operator!=(const MapConstIterator& p_it) const {
    233       return !(*this == p_it);
    234     }
    235        
    236236  private:
    237237    const Map* map;
    238     KeyIt it;
    239   };
     238  };
     239
     240  /** The class makes the KeyIt to an stl compatible iterator
     241   *  with dereferencing operator.
     242   */
     243  template <typename Map>
     244  class MapKeyIterator : public MapIteratorBase<Map> {
     245
     246  public:
     247
     248    /// The key type of the iterator.
     249    typedef typename Map::KeyType KeyType;
     250    /// The iterator to iterate on the keys.
     251    typedef typename Map::KeyIt KeyIt;
     252
     253  public:
     254
     255    /// Default constructor.
     256    MapKeyIterator() {}
     257
     258    /// KeyIt initialized iterator.
     259    MapKeyIterator(const KeyIt& pit) : MapIteratorBase<Map>(pit) {}
     260
     261    /// The pre increment operator of the iterator.
     262    MapKeyIterator& operator++() {
     263      increment();
     264      return *this;
     265    }
     266
     267    /// The post increment operator of the iterator.
     268    MapKeyIterator operator++(int) {
     269      MapKeyIterator tmp(*this);
     270      increment();
     271      return tmp;
     272    }
     273
     274    /// The dereferencing operator of the iterator.
     275    KeyType operator*() const {
     276      return static_cast<KeyType>(it);
     277    }
     278  };
     279
     280  template <typename Map> class MapConstValueIterator;
     281
     282  template <typename Map>
     283  class MapValueIterator : public MapIteratorBase<Map> {
     284
     285    friend class MapConstValueIterator<Map>;
     286
     287  public:
     288
     289    /// The key type of the iterator.
     290    typedef typename Map::KeyType KeyType;
     291    /// The iterator to iterate on the keys.
     292    typedef typename Map::KeyIt KeyIt;
     293
     294
     295    /// The value type of the iterator.
     296    typedef typename Map::ValueType ValueType;
     297    /// The reference type of the iterator.
     298    typedef typename Map::ReferenceType ReferenceType;
     299    /// The pointer type of the iterator.
     300    typedef typename Map::PointerType PointerType;
     301
     302    /// The const value type of the iterator.
     303    typedef typename Map::ConstValueType ConstValueType;
     304    /// The const reference type of the iterator.
     305    typedef typename Map::ConstReferenceType ConstReferenceType;
     306    /// The pointer type of the iterator.
     307    typedef typename Map::ConstPointerType ConstPointerType;
     308
     309  private:
     310
     311    Map* map;
     312
     313  public:
     314
     315    /// Default constructor.
     316    MapValueIterator() {}
     317
     318    /// Map and KeyIt initialized iterator.
     319    MapValueIterator(Map& pmap, const KeyIt& pit)
     320      : MapIteratorBase<Map>(pit), map(&pmap) {}
     321   
     322
     323    /// The pre increment operator of the iterator.
     324    MapValueIterator& operator++() {
     325      increment();
     326      return *this;
     327    }
     328
     329    /// The post increment operator of the iterator.
     330    MapValueIterator operator++(int) {
     331      MapValueIterator tmp(*this);
     332      increment();
     333      return tmp;
     334    }
     335
     336    /// The dereferencing operator of the iterator.
     337    ReferenceType operator*() const {
     338      return (*map)[it];
     339    }
     340
     341    /// The arrow operator of the iterator.
     342    PointerType operator->() const {
     343      return &(operator*());
     344    }
     345
     346  };
     347
     348
     349  template <typename Map>
     350  class MapConstValueIterator : public MapIteratorBase<Map> {
     351
     352  public:
     353
     354    /// The key type of the iterator.
     355    typedef typename Map::KeyType KeyType;
     356    /// The iterator to iterate on the keys.
     357    typedef typename Map::KeyIt KeyIt;
     358
     359
     360    /// The value type of the iterator.
     361    typedef typename Map::ValueType ValueType;
     362    /// The reference type of the iterator.
     363    typedef typename Map::ReferenceType ReferenceType;
     364    /// The pointer type of the iterator.
     365    typedef typename Map::PointerType PointerType;
     366
     367    /// The const value type of the iterator.
     368    typedef typename Map::ConstValueType ConstValueType;
     369    /// The const reference type of the iterator.
     370    typedef typename Map::ConstReferenceType ConstReferenceType;
     371    /// The pointer type of the iterator.
     372    typedef typename Map::ConstPointerType ConstPointerType;
     373
     374  private:
     375
     376    const Map* map;
     377
     378  public:
     379
     380    /// Default constructor.
     381    MapConstValueIterator() {}
     382
     383    /// Constructor to create const iterator from a non const.
     384    MapConstValueIterator(const MapValueIterator<Map>& pit) {
     385      it = pit.it;
     386      map = pit.map;
     387    }
     388
     389    /// Map and KeyIt initialized iterator.
     390    MapConstValueIterator(const Map& pmap, const KeyIt& pit)
     391      : MapIteratorBase<Map>(pit), map(&pmap) {}
     392
     393    /// The pre increment operator of the iterator.
     394    MapConstValueIterator& operator++() {
     395      increment();
     396      return *this;
     397    }
     398
     399    /// The post increment operator of the iterator.
     400    MapConstValueIterator operator++(int) {
     401      MapConstValueIterator tmp(*this);
     402      increment();
     403      return tmp;
     404    }
     405
     406    /// The dereferencing operator of the iterator.
     407    ConstReferenceType operator*() const {
     408      return (*map)[it];
     409    }
     410
     411    /// The arrow operator of the iterator.
     412    ConstPointerType operator->() const {
     413      return &(operator*());
     414    }
     415
     416  };
     417
     418
     419  /** This class makes from a map an iteratable set
     420   *  which contains all the keys of the map.
     421   */
     422  template <typename Map>
     423  class MapConstKeySet {
     424
     425    const Map* map;
     426
     427  public:
     428
     429    /// The key type of the iterator.
     430    typedef typename Map::KeyType KeyType;
     431    /// The iterator to iterate on the keys.
     432    typedef typename Map::KeyIt KeyIt;
     433
     434    /// The map initialized const key set.
     435    MapConstKeySet(const Map& pmap) : map(&pmap) {}
     436
     437    /// The const iterator of the set.
     438    typedef MapKeyIterator<Map> ConstIterator;
     439
     440    /// It gives back the const iterator pointed to the first element.
     441    ConstIterator begin() const {
     442      return ConstIterator(KeyIt(*map->getGraph()));
     443    }
     444           
     445    /// It gives back the const iterator pointed to the first ivalid element.
     446    ConstIterator end() const {
     447      return ConstIterator(KeyIt(INVALID));
     448    }
     449  };
     450
     451  /** This class makes from a map an iteratable set
     452   *  which contains all the values of the map.
     453   *  The values cannot be modified.
     454   */
     455  template <typename Map>
     456  class MapConstValueSet {
     457
     458    const Map* map;
     459
     460  public:
     461
     462    /// The key type of the iterator.
     463    typedef typename Map::KeyType KeyType;
     464    /// The iterator to iterate on the keys.
     465    typedef typename Map::KeyIt KeyIt;
     466
     467    /// The map initialized const value set.
     468    MapConstValueSet(const Map& pmap) : map(&pmap) {}
     469
     470    /// The const iterator of the set.
     471    typedef MapConstValueIterator<Map> ConstIterator;
     472
     473    /// It gives back the const iterator pointed to the first element.
     474    ConstIterator begin() const {
     475      return ConstIterator(*map, KeyIt(*map->getGraph()));
     476    }
     477
     478    /// It gives back the const iterator pointed to the first invalid element.
     479    ConstIterator end() const {
     480      return ConstIterator(*map, KeyIt(INVALID));
     481    }
     482  };
     483
     484
     485  /** This class makes from a map an iteratable set
     486   *  which contains all the values of the map.
     487   *  The values can be modified.
     488   */
     489  template <typename Map>
     490  class MapValueSet {
     491
     492    Map* map;
     493
     494  public:
     495
     496    /// The key type of the iterator.
     497    typedef typename Map::KeyType KeyType;
     498    /// The iterator to iterate on the keys.
     499    typedef typename Map::KeyIt KeyIt;
     500
     501    /// The map initialized value set.
     502    MapValueSet(Map& pmap) : map(&pmap) {}
     503
     504    /// The const iterator of the set.
     505    typedef MapConstValueIterator<Map> ConstIterator;
     506
     507    /// It gives back the const iterator pointed to the first element.
     508    ConstIterator begin() const {
     509      return ConstIterator(*map, KeyIt(*map->getGraph()));
     510    }
     511
     512    /// It gives back the const iterator pointed to the first invalid element.
     513    ConstIterator end() const {
     514      return ConstIterator(*map, KeyIt(INVALID));
     515    }
     516
     517    /// The iterator of the set.
     518    typedef MapValueIterator<Map> Iterator;
     519
     520    /// It gives back the iterator pointed to the first element.
     521    Iterator begin() {
     522      return Iterator(*map, KeyIt(*map->getGraph()));
     523    }
     524
     525    /// It gives back the iterator pointed to the first invalid element.
     526    Iterator end() {
     527      return Iterator(*map, KeyIt(INVALID));
     528    }
     529           
     530  };
     531
     532  /// @}
    240533
    241534}
  • src/hugo/vector_map.h

    r822 r830  
    203203    }
    204204
     205    /// The KeySet of the Map.
     206    typedef MapConstKeySet<VectorMap> ConstKeySet;
     207
     208    /// KeySet getter function.
     209    ConstKeySet keySet() const {
     210      return ConstKeySet(*this);
     211    }
     212
     213    /// The ConstValueSet of the Map.
     214    typedef MapConstValueSet<VectorMap> ConstValueSet;
     215
     216    /// ConstValueSet getter function.
     217    ConstValueSet valueSet() const {
     218      return ConstValueSet(*this);
     219    }
     220
     221    /// The ValueSet of the Map.
     222    typedef MapValueSet<VectorMap> ValueSet;
     223
     224    /// ValueSet getter function.
     225    ValueSet valueSet() {
     226      return ValueSet(*this);
     227    }
     228
     229
    205230  private:
    206231               
Note: See TracChangeset for help on using the changeset viewer.