COIN-OR::LEMON - Graph Library

Changeset 741:71939d63ae77 in lemon for lemon/maps.h


Ignore:
Timestamp:
07/21/09 22:43:31 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
742:8dae88c5943e, 768:99124ea4f048
Phase:
public
Message:

Improvements for iterable maps (#73)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r740 r741  
    2323#include <functional>
    2424#include <vector>
     25#include <map>
    2526
    2627#include <lemon/core.h>
    27 #include <lemon/smart_graph.h>
    2828
    2929///\file
    3030///\ingroup maps
    3131///\brief Miscellaneous property maps
    32 
    33 #include <map>
    3432
    3533namespace lemon {
     
    19071905  /// and if a key is set to a new value then store it
    19081906  /// in the inverse map.
    1909   ///
    19101907  /// The values of the map can be accessed
    19111908  /// with stl compatible forward iterator.
     1909  ///
     1910  /// This type is not reference map, so it cannot be modified with
     1911  /// the subscription operator.
    19121912  ///
    19131913  /// \tparam GR The graph type.
     
    23132313  };
    23142314
    2315   /// \brief Dynamic iterable bool map.
    2316   ///
    2317   /// This class provides a special graph map type which can store for
    2318   /// each graph item(node, arc, edge, etc.) a bool value. For both
    2319   /// the true and the false values it is possible to iterate on the
    2320   /// keys.
    2321   ///
    2322   /// \param GR The graph type.
    2323   /// \param ITEM One of the graph's item types, the key of the map.
    2324   template <typename GR, typename ITEM>
     2315  /// \brief Dynamic iterable \c bool map.
     2316  ///
     2317  /// This class provides a special graph map type which can store a
     2318  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2319  /// For both \c true and \c false values it is possible to iterate on
     2320  /// the keys.
     2321  ///
     2322  /// This type is a reference map, so it can be modified with the
     2323  /// subscription operator.
     2324  ///
     2325  /// \tparam GR The graph type.
     2326  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2327  /// \c GR::Edge).
     2328  ///
     2329  /// \see IterableIntMap, IterableValueMap
     2330  /// \see CrossRefMap
     2331  template <typename GR, typename K>
    23252332  class IterableBoolMap
    2326     : protected ItemSetTraits<GR, ITEM>::template Map<int>::Type {
     2333    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
    23272334  private:
    23282335    typedef GR Graph;
    23292336
    2330     typedef typename ItemSetTraits<Graph, ITEM>::ItemIt KeyIt;
    2331     typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent;
    2332 
    2333     std::vector<ITEM> _array;
     2337    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2338    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2339
     2340    std::vector<K> _array;
    23342341    int _sep;
    23352342
    23362343  public:
    23372344
    2338     /// Indicates that the map if reference map.
     2345    /// Indicates that the map is reference map.
    23392346    typedef True ReferenceMapTag;
    23402347
    23412348    /// The key type
    2342     typedef ITEM Key;
     2349    typedef K Key;
    23432350    /// The value type
    23442351    typedef bool Value;
     
    23542361  public:
    23552362
    2356     /// \brief Refernce to the value of the map.
    2357     ///
    2358     /// This class is similar to the bool type. It can be converted to
    2359     /// bool and it provides the same operators.
     2363    /// \brief Reference to the value of the map.
     2364    ///
     2365    /// This class is similar to the \c bool type. It can be converted to
     2366    /// \c bool and it provides the same operators.
    23602367    class Reference {
    23612368      friend class IterableBoolMap;
     
    24552462    }
    24562463
    2457     /// \brief Returns the number of the keys mapped to true.
    2458     ///
    2459     /// Returns the number of the keys mapped to true.
     2464    /// \brief Returns the number of the keys mapped to \c true.
     2465    ///
     2466    /// Returns the number of the keys mapped to \c true.
    24602467    int trueNum() const {
    24612468      return _sep;
    24622469    }
    24632470
    2464     /// \brief Returns the number of the keys mapped to false.
    2465     ///
    2466     /// Returns the number of the keys mapped to false.
     2471    /// \brief Returns the number of the keys mapped to \c false.
     2472    ///
     2473    /// Returns the number of the keys mapped to \c false.
    24672474    int falseNum() const {
    24682475      return _array.size() - _sep;
    24692476    }
    24702477
    2471     /// \brief Iterator for the keys mapped to true.
    2472     ///
    2473     /// Iterator for the keys mapped to true. It works
    2474     /// like a graph item iterator in the map, it can be converted
     2478    /// \brief Iterator for the keys mapped to \c true.
     2479    ///
     2480    /// Iterator for the keys mapped to \c true. It works
     2481    /// like a graph item iterator, it can be converted to
    24752482    /// the key type of the map, incremented with \c ++ operator, and
    2476     /// if the iterator leave the last valid key it will be equal to
     2483    /// if the iterator leaves the last valid key, it will be equal to
    24772484    /// \c INVALID.
    24782485    class TrueIt : public Key {
     
    24832490      ///
    24842491      /// Creates an iterator. It iterates on the
    2485       /// keys which mapped to true.
    2486       /// \param map The IterableIntMap
     2492      /// keys mapped to \c true.
     2493      /// \param map The IterableBoolMap.
    24872494      explicit TrueIt(const IterableBoolMap& map)
    24882495        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     
    24912498      /// \brief Invalid constructor \& conversion.
    24922499      ///
    2493       /// This constructor initializes the key to be invalid.
     2500      /// This constructor initializes the iterator to be invalid.
    24942501      /// \sa Invalid for more details.
    24952502      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     
    24972504      /// \brief Increment operator.
    24982505      ///
    2499       /// Increment Operator.
     2506      /// Increment operator.
    25002507      TrueIt& operator++() {
    25012508        int pos = _map->position(*this);
     
    25042511      }
    25052512
    2506 
    25072513    private:
    25082514      const IterableBoolMap* _map;
    25092515    };
    25102516
    2511     /// \brief Iterator for the keys mapped to false.
    2512     ///
    2513     /// Iterator for the keys mapped to false. It works
    2514     /// like a graph item iterator in the map, it can be converted
     2517    /// \brief Iterator for the keys mapped to \c false.
     2518    ///
     2519    /// Iterator for the keys mapped to \c false. It works
     2520    /// like a graph item iterator, it can be converted to
    25152521    /// the key type of the map, incremented with \c ++ operator, and
    2516     /// if the iterator leave the last valid key it will be equal to
     2522    /// if the iterator leaves the last valid key, it will be equal to
    25172523    /// \c INVALID.
    25182524    class FalseIt : public Key {
     
    25232529      ///
    25242530      /// Creates an iterator. It iterates on the
    2525       /// keys which mapped to false.
    2526       /// \param map The IterableIntMap
     2531      /// keys mapped to \c false.
     2532      /// \param map The IterableBoolMap.
    25272533      explicit FalseIt(const IterableBoolMap& map)
    25282534        : Parent(map._sep < int(map._array.size()) ?
     
    25312537      /// \brief Invalid constructor \& conversion.
    25322538      ///
    2533       /// This constructor initializes the key to be invalid.
     2539      /// This constructor initializes the iterator to be invalid.
    25342540      /// \sa Invalid for more details.
    25352541      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     
    25372543      /// \brief Increment operator.
    25382544      ///
    2539       /// Increment Operator.
     2545      /// Increment operator.
    25402546      FalseIt& operator++() {
    25412547        int pos = _map->position(*this);
     
    25512557    ///
    25522558    /// Iterator for the keys mapped to a given value. It works
    2553     /// like a graph item iterator in the map, it can be converted
     2559    /// like a graph item iterator, it can be converted to
    25542560    /// the key type of the map, incremented with \c ++ operator, and
    2555     /// if the iterator leave the last valid key it will be equal to
     2561    /// if the iterator leaves the last valid key, it will be equal to
    25562562    /// \c INVALID.
    25572563    class ItemIt : public Key {
     
    25592565      typedef Key Parent;
    25602566
    2561       /// \brief Creates an iterator.
     2567      /// \brief Creates an iterator with a value.
    25622568      ///
    2563       /// Creates an iterator. It iterates on the
    2564       /// keys which mapped to false.
    2565       /// \param map The IterableIntMap
    2566       /// \param value Which elements should be iterated.
     2569      /// Creates an iterator with a value. It iterates on the
     2570      /// keys mapped to the given value.
     2571      /// \param map The IterableBoolMap.
     2572      /// \param value The value.
    25672573      ItemIt(const IterableBoolMap& map, bool value)
    25682574        : Parent(value ?
     
    25742580      /// \brief Invalid constructor \& conversion.
    25752581      ///
    2576       /// This constructor initializes the key to be invalid.
     2582      /// This constructor initializes the iterator to be invalid.
    25772583      /// \sa Invalid for more details.
    25782584      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     
    25802586      /// \brief Increment operator.
    25812587      ///
    2582       /// Increment Operator.
     2588      /// Increment operator.
    25832589      ItemIt& operator++() {
    25842590        int pos = _map->position(*this);
     
    26742680  }
    26752681
    2676   ///\ingroup graph_maps
    2677   ///
    26782682  /// \brief Dynamic iterable integer map.
    26792683  ///
    2680   /// This class provides a special graph map type which can store
    2681   /// for each graph item(node, edge, etc.) an integer value. For each
    2682   /// non negative value it is possible to iterate on the keys which
    2683   /// mapped to the given value.
    2684   ///
    2685   /// \note The size of the data structure depends on the highest
     2684  /// This class provides a special graph map type which can store an
     2685  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2686  /// For each non-negative value it is possible to iterate on the keys
     2687  /// mapped to the value.
     2688  ///
     2689  /// This type is a reference map, so it can be modified with the
     2690  /// subscription operator.
     2691  ///
     2692  /// \note The size of the data structure depends on the largest
    26862693  /// value in the map.
    26872694  ///
    2688   /// \param GR The graph type.
    2689   /// \param ITEM One of the graph's item type, the key of the map.
    2690   template <typename GR, typename ITEM>
     2695  /// \tparam GR The graph type.
     2696  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2697  /// \c GR::Edge).
     2698  ///
     2699  /// \see IterableBoolMap, IterableValueMap
     2700  /// \see CrossRefMap
     2701  template <typename GR, typename K>
    26912702  class IterableIntMap
    2692     : protected ItemSetTraits<GR, ITEM>::
    2693         template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type {
    2694   public:
    2695     typedef typename ItemSetTraits<GR, ITEM>::
    2696       template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type Parent;
     2703    : protected ItemSetTraits<GR, K>::
     2704        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2705  public:
     2706    typedef typename ItemSetTraits<GR, K>::
     2707      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
    26972708
    26982709    /// The key type
    2699     typedef ITEM Key;
     2710    typedef K Key;
    27002711    /// The value type
    27012712    typedef int Value;
     
    27052716    /// \brief Constructor of the map.
    27062717    ///
    2707     /// Constructor of the map. It set all values to -1.
     2718    /// Constructor of the map. It sets all values to -1.
    27082719    explicit IterableIntMap(const Graph& graph)
    27092720      : Parent(graph) {}
     
    27132724    /// Constructor of the map with a given value.
    27142725    explicit IterableIntMap(const Graph& graph, int value)
    2715       : Parent(graph, _maps_bits::IterableIntMapNode<ITEM>(value)) {
     2726      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
    27162727      if (value >= 0) {
    27172728        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     
    27552766  public:
    27562767
    2757     /// Indicates that the map if reference map.
     2768    /// Indicates that the map is reference map.
    27582769    typedef True ReferenceMapTag;
    27592770
    2760     /// \brief Refernce to the value of the map.
    2761     ///
    2762     /// This class is similar to the int type. It can
    2763     /// be converted to int and it has the same operators.
     2771    /// \brief Reference to the value of the map.
     2772    ///
     2773    /// This class is similar to the \c int type. It can
     2774    /// be converted to \c int and it has the same operators.
    27642775    class Reference {
    27652776      friend class IterableIntMap;
     
    28822893    ///
    28832894    /// Iterator for the keys with the same value. It works
    2884     /// like a graph item iterator in the map, it can be converted
     2895    /// like a graph item iterator, it can be converted to
    28852896    /// the item type of the map, incremented with \c ++ operator, and
    2886     /// if the iterator leave the last valid item it will be equal to
     2897    /// if the iterator leaves the last valid item, it will be equal to
    28872898    /// \c INVALID.
    2888     class ItemIt : public ITEM {
     2899    class ItemIt : public Key {
    28892900    public:
    2890       typedef ITEM Parent;
     2901      typedef Key Parent;
    28912902
    28922903      /// \brief Invalid constructor \& conversion.
    28932904      ///
    2894       /// This constructor initializes the item to be invalid.
     2905      /// This constructor initializes the iterator to be invalid.
    28952906      /// \sa Invalid for more details.
    28962907      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     
    28992910      ///
    29002911      /// Creates an iterator with a value. It iterates on the
    2901       /// keys which have the given value.
    2902       /// \param map The IterableIntMap
    2903       /// \param value The value
     2912      /// keys mapped to the given value.
     2913      /// \param map The IterableIntMap.
     2914      /// \param value The value.
    29042915      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
    29052916        if (value < 0 || value >= int(_map->_first.size())) {
     
    29122923      /// \brief Increment operator.
    29132924      ///
    2914       /// Increment Operator.
     2925      /// Increment operator.
    29152926      ItemIt& operator++() {
    29162927        Parent::operator=(_map->IterableIntMap::Parent::
     
    29192930      }
    29202931
    2921 
    29222932    private:
    29232933      const IterableIntMap* _map;
     
    29442954
    29452955  private:
    2946     std::vector<ITEM> _first;
     2956    std::vector<Key> _first;
    29472957  };
    29482958
     
    29562966  }
    29572967
    2958   ///\ingroup graph_maps
    2959   ///
    29602968  /// \brief Dynamic iterable map for comparable values.
    29612969  ///
    2962   /// This class provides a special graph map type which can store
    2963   /// for each graph item(node, edge, etc.) a value. For each
    2964   /// value it is possible to iterate on the keys which mapped to the
    2965   /// given value. The type stores for each value a linked list with
     2970  /// This class provides a special graph map type which can store an
     2971  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     2972  /// For each value it is possible to iterate on the keys mapped to
     2973  /// the value.
     2974  ///
     2975  /// The map stores for each value a linked list with
    29662976  /// the items which mapped to the value, and the values are stored
    29672977  /// in balanced binary tree. The values of the map can be accessed
    29682978  /// with stl compatible forward iterator.
    29692979  ///
    2970   /// This type is not reference map so it cannot be modified with
     2980  /// This type is not reference map, so it cannot be modified with
    29712981  /// the subscription operator.
    29722982  ///
    2973   /// \see InvertableMap
    2974   ///
    2975   /// \param GR The graph type.
    2976   /// \param ITEM One of the graph's item type, the key of the map.
    2977   /// \param VAL Any comparable value type.
    2978   template <typename GR, typename ITEM, typename VAL>
     2983  /// \tparam GR The graph type.
     2984  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2985  /// \c GR::Edge).
     2986  /// \tparam V The value type of the map. It can be any comparable
     2987  /// value type.
     2988  ///
     2989  /// \see IterableBoolMap, IterableIntMap
     2990  /// \see CrossRefMap
     2991  template <typename GR, typename K, typename V>
    29792992  class IterableValueMap
    2980     : protected ItemSetTraits<GR, ITEM>::
    2981         template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type {
    2982   public:
    2983     typedef typename ItemSetTraits<GR, ITEM>::
    2984       template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type Parent;
     2993    : protected ItemSetTraits<GR, K>::
     2994        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     2995  public:
     2996    typedef typename ItemSetTraits<GR, K>::
     2997      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
    29852998
    29862999    /// The key type
    2987     typedef ITEM Key;
     3000    typedef K Key;
    29883001    /// The value type
    2989     typedef VAL Value;
     3002    typedef V Value;
    29903003    /// The graph type
    29913004    typedef GR Graph;
     
    29933006  public:
    29943007
    2995     /// \brief Constructor of the Map with a given value.
    2996     ///
    2997     /// Constructor of the Map with a given value.
     3008    /// \brief Constructor of the map with a given value.
     3009    ///
     3010    /// Constructor of the map with a given value.
    29983011    explicit IterableValueMap(const Graph& graph,
    29993012                              const Value& value = Value())
    3000       : Parent(graph, _maps_bits::IterableValueMapNode<ITEM, VAL>(value)) {
     3013      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
    30013014      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
    30023015        lace(it);
     
    30273040      if (it == _first.end()) {
    30283041        node.prev = node.next = INVALID;
    3029         if (node.next != INVALID) {
    3030           Parent::operator[](node.next).prev = key;
    3031         }
    30323042        _first.insert(std::make_pair(node.value, key));
    30333043      } else {
     
    30473057    /// This iterator is an stl compatible forward
    30483058    /// iterator on the values of the map. The values can
    3049     /// be accessed in the [beginValue, endValue) range.
    3050     ///
     3059    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    30513060    class ValueIterator
    30523061      : public std::iterator<std::forward_iterator_tag, Value> {
     
    30803089    /// Returns an stl compatible iterator to the
    30813090    /// first value of the map. The values of the
    3082     /// map can be accessed in the [beginValue, endValue)
     3091    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    30833092    /// range.
    30843093    ValueIterator beginValue() const {
     
    30903099    /// Returns an stl compatible iterator after the
    30913100    /// last value of the map. The values of the
    3092     /// map can be accessed in the [beginValue, endValue)
     3101    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    30933102    /// range.
    30943103    ValueIterator endValue() const {
     
    31153124    ///
    31163125    /// Iterator for the keys with the same value. It works
    3117     /// like a graph item iterator in the map, it can be converted
     3126    /// like a graph item iterator, it can be converted to
    31183127    /// the item type of the map, incremented with \c ++ operator, and
    3119     /// if the iterator leave the last valid item it will be equal to
     3128    /// if the iterator leaves the last valid item, it will be equal to
    31203129    /// \c INVALID.
    3121     class ItemIt : public ITEM {
     3130    class ItemIt : public Key {
    31223131    public:
    3123       typedef ITEM Parent;
     3132      typedef Key Parent;
    31243133
    31253134      /// \brief Invalid constructor \& conversion.
    31263135      ///
    3127       /// This constructor initializes the item to be invalid.
     3136      /// This constructor initializes the iterator to be invalid.
    31283137      /// \sa Invalid for more details.
    31293138      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
Note: See TracChangeset for help on using the changeset viewer.