COIN-OR::LEMON - Graph Library

Changeset 695:8dae88c5943e in lemon-1.2 for lemon


Ignore:
Timestamp:
08/31/09 08:25:33 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
692:33f417de9e70 (diff), 694:71939d63ae77 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r684 r695  
    2323#include <functional>
    2424#include <vector>
     25#include <map>
    2526
    2627#include <lemon/core.h>
     
    2930///\ingroup maps
    3031///\brief Miscellaneous property maps
    31 
    32 #include <map>
    3332
    3433namespace lemon {
     
    18191818  ///
    18201819  /// IdMap provides a unique and immutable id for each item of the
    1821   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
     1820  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    18221821  ///  - \b unique: different items get different ids,
    18231822  ///  - \b immutable: the id of an item does not change (even if you
     
    22742273
    22752274    /// \brief Gives back the item belonging to a \e RangeId
    2276     /// 
     2275    ///
    22772276    /// Gives back the item belonging to a \e RangeId.
    22782277    Item operator()(int id) const {
     
    23312330  };
    23322331
     2332  /// \brief Dynamic iterable \c bool map.
     2333  ///
     2334  /// This class provides a special graph map type which can store a
     2335  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2336  /// For both \c true and \c false values it is possible to iterate on
     2337  /// the keys.
     2338  ///
     2339  /// This type is a reference map, so it can be modified with the
     2340  /// subscript operator.
     2341  ///
     2342  /// \tparam GR The graph type.
     2343  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2344  /// \c GR::Edge).
     2345  ///
     2346  /// \see IterableIntMap, IterableValueMap
     2347  /// \see CrossRefMap
     2348  template <typename GR, typename K>
     2349  class IterableBoolMap
     2350    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2351  private:
     2352    typedef GR Graph;
     2353
     2354    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2355    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2356
     2357    std::vector<K> _array;
     2358    int _sep;
     2359
     2360  public:
     2361
     2362    /// Indicates that the map is reference map.
     2363    typedef True ReferenceMapTag;
     2364
     2365    /// The key type
     2366    typedef K Key;
     2367    /// The value type
     2368    typedef bool Value;
     2369    /// The const reference type.
     2370    typedef const Value& ConstReference;
     2371
     2372  private:
     2373
     2374    int position(const Key& key) const {
     2375      return Parent::operator[](key);
     2376    }
     2377
     2378  public:
     2379
     2380    /// \brief Reference to the value of the map.
     2381    ///
     2382    /// This class is similar to the \c bool type. It can be converted to
     2383    /// \c bool and it provides the same operators.
     2384    class Reference {
     2385      friend class IterableBoolMap;
     2386    private:
     2387      Reference(IterableBoolMap& map, const Key& key)
     2388        : _key(key), _map(map) {}
     2389    public:
     2390
     2391      Reference& operator=(const Reference& value) {
     2392        _map.set(_key, static_cast<bool>(value));
     2393         return *this;
     2394      }
     2395
     2396      operator bool() const {
     2397        return static_cast<const IterableBoolMap&>(_map)[_key];
     2398      }
     2399
     2400      Reference& operator=(bool value) {
     2401        _map.set(_key, value);
     2402        return *this;
     2403      }
     2404      Reference& operator&=(bool value) {
     2405        _map.set(_key, _map[_key] & value);
     2406        return *this;
     2407      }
     2408      Reference& operator|=(bool value) {
     2409        _map.set(_key, _map[_key] | value);
     2410        return *this;
     2411      }
     2412      Reference& operator^=(bool value) {
     2413        _map.set(_key, _map[_key] ^ value);
     2414        return *this;
     2415      }
     2416    private:
     2417      Key _key;
     2418      IterableBoolMap& _map;
     2419    };
     2420
     2421    /// \brief Constructor of the map with a default value.
     2422    ///
     2423    /// Constructor of the map with a default value.
     2424    explicit IterableBoolMap(const Graph& graph, bool def = false)
     2425      : Parent(graph) {
     2426      typename Parent::Notifier* nf = Parent::notifier();
     2427      Key it;
     2428      for (nf->first(it); it != INVALID; nf->next(it)) {
     2429        Parent::set(it, _array.size());
     2430        _array.push_back(it);
     2431      }
     2432      _sep = (def ? _array.size() : 0);
     2433    }
     2434
     2435    /// \brief Const subscript operator of the map.
     2436    ///
     2437    /// Const subscript operator of the map.
     2438    bool operator[](const Key& key) const {
     2439      return position(key) < _sep;
     2440    }
     2441
     2442    /// \brief Subscript operator of the map.
     2443    ///
     2444    /// Subscript operator of the map.
     2445    Reference operator[](const Key& key) {
     2446      return Reference(*this, key);
     2447    }
     2448
     2449    /// \brief Set operation of the map.
     2450    ///
     2451    /// Set operation of the map.
     2452    void set(const Key& key, bool value) {
     2453      int pos = position(key);
     2454      if (value) {
     2455        if (pos < _sep) return;
     2456        Key tmp = _array[_sep];
     2457        _array[_sep] = key;
     2458        Parent::set(key, _sep);
     2459        _array[pos] = tmp;
     2460        Parent::set(tmp, pos);
     2461        ++_sep;
     2462      } else {
     2463        if (pos >= _sep) return;
     2464        --_sep;
     2465        Key tmp = _array[_sep];
     2466        _array[_sep] = key;
     2467        Parent::set(key, _sep);
     2468        _array[pos] = tmp;
     2469        Parent::set(tmp, pos);
     2470      }
     2471    }
     2472
     2473    /// \brief Set all items.
     2474    ///
     2475    /// Set all items in the map.
     2476    /// \note Constant time operation.
     2477    void setAll(bool value) {
     2478      _sep = (value ? _array.size() : 0);
     2479    }
     2480
     2481    /// \brief Returns the number of the keys mapped to \c true.
     2482    ///
     2483    /// Returns the number of the keys mapped to \c true.
     2484    int trueNum() const {
     2485      return _sep;
     2486    }
     2487
     2488    /// \brief Returns the number of the keys mapped to \c false.
     2489    ///
     2490    /// Returns the number of the keys mapped to \c false.
     2491    int falseNum() const {
     2492      return _array.size() - _sep;
     2493    }
     2494
     2495    /// \brief Iterator for the keys mapped to \c true.
     2496    ///
     2497    /// Iterator for the keys mapped to \c true. It works
     2498    /// like a graph item iterator, it can be converted to
     2499    /// the key type of the map, incremented with \c ++ operator, and
     2500    /// if the iterator leaves the last valid key, it will be equal to
     2501    /// \c INVALID.
     2502    class TrueIt : public Key {
     2503    public:
     2504      typedef Key Parent;
     2505
     2506      /// \brief Creates an iterator.
     2507      ///
     2508      /// Creates an iterator. It iterates on the
     2509      /// keys mapped to \c true.
     2510      /// \param map The IterableBoolMap.
     2511      explicit TrueIt(const IterableBoolMap& map)
     2512        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     2513          _map(&map) {}
     2514
     2515      /// \brief Invalid constructor \& conversion.
     2516      ///
     2517      /// This constructor initializes the iterator to be invalid.
     2518      /// \sa Invalid for more details.
     2519      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     2520
     2521      /// \brief Increment operator.
     2522      ///
     2523      /// Increment operator.
     2524      TrueIt& operator++() {
     2525        int pos = _map->position(*this);
     2526        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
     2527        return *this;
     2528      }
     2529
     2530    private:
     2531      const IterableBoolMap* _map;
     2532    };
     2533
     2534    /// \brief Iterator for the keys mapped to \c false.
     2535    ///
     2536    /// Iterator for the keys mapped to \c false. It works
     2537    /// like a graph item iterator, it can be converted to
     2538    /// the key type of the map, incremented with \c ++ operator, and
     2539    /// if the iterator leaves the last valid key, it will be equal to
     2540    /// \c INVALID.
     2541    class FalseIt : public Key {
     2542    public:
     2543      typedef Key Parent;
     2544
     2545      /// \brief Creates an iterator.
     2546      ///
     2547      /// Creates an iterator. It iterates on the
     2548      /// keys mapped to \c false.
     2549      /// \param map The IterableBoolMap.
     2550      explicit FalseIt(const IterableBoolMap& map)
     2551        : Parent(map._sep < int(map._array.size()) ?
     2552                 map._array.back() : INVALID), _map(&map) {}
     2553
     2554      /// \brief Invalid constructor \& conversion.
     2555      ///
     2556      /// This constructor initializes the iterator to be invalid.
     2557      /// \sa Invalid for more details.
     2558      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     2559
     2560      /// \brief Increment operator.
     2561      ///
     2562      /// Increment operator.
     2563      FalseIt& operator++() {
     2564        int pos = _map->position(*this);
     2565        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
     2566        return *this;
     2567      }
     2568
     2569    private:
     2570      const IterableBoolMap* _map;
     2571    };
     2572
     2573    /// \brief Iterator for the keys mapped to a given value.
     2574    ///
     2575    /// Iterator for the keys mapped to a given value. It works
     2576    /// like a graph item iterator, it can be converted to
     2577    /// the key type of the map, incremented with \c ++ operator, and
     2578    /// if the iterator leaves the last valid key, it will be equal to
     2579    /// \c INVALID.
     2580    class ItemIt : public Key {
     2581    public:
     2582      typedef Key Parent;
     2583
     2584      /// \brief Creates an iterator with a value.
     2585      ///
     2586      /// Creates an iterator with a value. It iterates on the
     2587      /// keys mapped to the given value.
     2588      /// \param map The IterableBoolMap.
     2589      /// \param value The value.
     2590      ItemIt(const IterableBoolMap& map, bool value)
     2591        : Parent(value ?
     2592                 (map._sep > 0 ?
     2593                  map._array[map._sep - 1] : INVALID) :
     2594                 (map._sep < int(map._array.size()) ?
     2595                  map._array.back() : INVALID)), _map(&map) {}
     2596
     2597      /// \brief Invalid constructor \& conversion.
     2598      ///
     2599      /// This constructor initializes the iterator to be invalid.
     2600      /// \sa Invalid for more details.
     2601      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2602
     2603      /// \brief Increment operator.
     2604      ///
     2605      /// Increment operator.
     2606      ItemIt& operator++() {
     2607        int pos = _map->position(*this);
     2608        int _sep = pos >= _map->_sep ? _map->_sep : 0;
     2609        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
     2610        return *this;
     2611      }
     2612
     2613    private:
     2614      const IterableBoolMap* _map;
     2615    };
     2616
     2617  protected:
     2618
     2619    virtual void add(const Key& key) {
     2620      Parent::add(key);
     2621      Parent::set(key, _array.size());
     2622      _array.push_back(key);
     2623    }
     2624
     2625    virtual void add(const std::vector<Key>& keys) {
     2626      Parent::add(keys);
     2627      for (int i = 0; i < int(keys.size()); ++i) {
     2628        Parent::set(keys[i], _array.size());
     2629        _array.push_back(keys[i]);
     2630      }
     2631    }
     2632
     2633    virtual void erase(const Key& key) {
     2634      int pos = position(key);
     2635      if (pos < _sep) {
     2636        --_sep;
     2637        Parent::set(_array[_sep], pos);
     2638        _array[pos] = _array[_sep];
     2639        Parent::set(_array.back(), _sep);
     2640        _array[_sep] = _array.back();
     2641        _array.pop_back();
     2642      } else {
     2643        Parent::set(_array.back(), pos);
     2644        _array[pos] = _array.back();
     2645        _array.pop_back();
     2646      }
     2647      Parent::erase(key);
     2648    }
     2649
     2650    virtual void erase(const std::vector<Key>& keys) {
     2651      for (int i = 0; i < int(keys.size()); ++i) {
     2652        int pos = position(keys[i]);
     2653        if (pos < _sep) {
     2654          --_sep;
     2655          Parent::set(_array[_sep], pos);
     2656          _array[pos] = _array[_sep];
     2657          Parent::set(_array.back(), _sep);
     2658          _array[_sep] = _array.back();
     2659          _array.pop_back();
     2660        } else {
     2661          Parent::set(_array.back(), pos);
     2662          _array[pos] = _array.back();
     2663          _array.pop_back();
     2664        }
     2665      }
     2666      Parent::erase(keys);
     2667    }
     2668
     2669    virtual void build() {
     2670      Parent::build();
     2671      typename Parent::Notifier* nf = Parent::notifier();
     2672      Key it;
     2673      for (nf->first(it); it != INVALID; nf->next(it)) {
     2674        Parent::set(it, _array.size());
     2675        _array.push_back(it);
     2676      }
     2677      _sep = 0;
     2678    }
     2679
     2680    virtual void clear() {
     2681      _array.clear();
     2682      _sep = 0;
     2683      Parent::clear();
     2684    }
     2685
     2686  };
     2687
     2688
     2689  namespace _maps_bits {
     2690    template <typename Item>
     2691    struct IterableIntMapNode {
     2692      IterableIntMapNode() : value(-1) {}
     2693      IterableIntMapNode(int _value) : value(_value) {}
     2694      Item prev, next;
     2695      int value;
     2696    };
     2697  }
     2698
     2699  /// \brief Dynamic iterable integer map.
     2700  ///
     2701  /// This class provides a special graph map type which can store an
     2702  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2703  /// For each non-negative value it is possible to iterate on the keys
     2704  /// mapped to the value.
     2705  ///
     2706  /// This type is a reference map, so it can be modified with the
     2707  /// subscript operator.
     2708  ///
     2709  /// \note The size of the data structure depends on the largest
     2710  /// value in the map.
     2711  ///
     2712  /// \tparam GR The graph type.
     2713  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2714  /// \c GR::Edge).
     2715  ///
     2716  /// \see IterableBoolMap, IterableValueMap
     2717  /// \see CrossRefMap
     2718  template <typename GR, typename K>
     2719  class IterableIntMap
     2720    : protected ItemSetTraits<GR, K>::
     2721        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2722  public:
     2723    typedef typename ItemSetTraits<GR, K>::
     2724      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
     2725
     2726    /// The key type
     2727    typedef K Key;
     2728    /// The value type
     2729    typedef int Value;
     2730    /// The graph type
     2731    typedef GR Graph;
     2732
     2733    /// \brief Constructor of the map.
     2734    ///
     2735    /// Constructor of the map. It sets all values to -1.
     2736    explicit IterableIntMap(const Graph& graph)
     2737      : Parent(graph) {}
     2738
     2739    /// \brief Constructor of the map with a given value.
     2740    ///
     2741    /// Constructor of the map with a given value.
     2742    explicit IterableIntMap(const Graph& graph, int value)
     2743      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
     2744      if (value >= 0) {
     2745        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     2746          lace(it);
     2747        }
     2748      }
     2749    }
     2750
     2751  private:
     2752
     2753    void unlace(const Key& key) {
     2754      typename Parent::Value& node = Parent::operator[](key);
     2755      if (node.value < 0) return;
     2756      if (node.prev != INVALID) {
     2757        Parent::operator[](node.prev).next = node.next;
     2758      } else {
     2759        _first[node.value] = node.next;
     2760      }
     2761      if (node.next != INVALID) {
     2762        Parent::operator[](node.next).prev = node.prev;
     2763      }
     2764      while (!_first.empty() && _first.back() == INVALID) {
     2765        _first.pop_back();
     2766      }
     2767    }
     2768
     2769    void lace(const Key& key) {
     2770      typename Parent::Value& node = Parent::operator[](key);
     2771      if (node.value < 0) return;
     2772      if (node.value >= int(_first.size())) {
     2773        _first.resize(node.value + 1, INVALID);
     2774      }
     2775      node.prev = INVALID;
     2776      node.next = _first[node.value];
     2777      if (node.next != INVALID) {
     2778        Parent::operator[](node.next).prev = key;
     2779      }
     2780      _first[node.value] = key;
     2781    }
     2782
     2783  public:
     2784
     2785    /// Indicates that the map is reference map.
     2786    typedef True ReferenceMapTag;
     2787
     2788    /// \brief Reference to the value of the map.
     2789    ///
     2790    /// This class is similar to the \c int type. It can
     2791    /// be converted to \c int and it has the same operators.
     2792    class Reference {
     2793      friend class IterableIntMap;
     2794    private:
     2795      Reference(IterableIntMap& map, const Key& key)
     2796        : _key(key), _map(map) {}
     2797    public:
     2798
     2799      Reference& operator=(const Reference& value) {
     2800        _map.set(_key, static_cast<const int&>(value));
     2801         return *this;
     2802      }
     2803
     2804      operator const int&() const {
     2805        return static_cast<const IterableIntMap&>(_map)[_key];
     2806      }
     2807
     2808      Reference& operator=(int value) {
     2809        _map.set(_key, value);
     2810        return *this;
     2811      }
     2812      Reference& operator++() {
     2813        _map.set(_key, _map[_key] + 1);
     2814        return *this;
     2815      }
     2816      int operator++(int) {
     2817        int value = _map[_key];
     2818        _map.set(_key, value + 1);
     2819        return value;
     2820      }
     2821      Reference& operator--() {
     2822        _map.set(_key, _map[_key] - 1);
     2823        return *this;
     2824      }
     2825      int operator--(int) {
     2826        int value = _map[_key];
     2827        _map.set(_key, value - 1);
     2828        return value;
     2829      }
     2830      Reference& operator+=(int value) {
     2831        _map.set(_key, _map[_key] + value);
     2832        return *this;
     2833      }
     2834      Reference& operator-=(int value) {
     2835        _map.set(_key, _map[_key] - value);
     2836        return *this;
     2837      }
     2838      Reference& operator*=(int value) {
     2839        _map.set(_key, _map[_key] * value);
     2840        return *this;
     2841      }
     2842      Reference& operator/=(int value) {
     2843        _map.set(_key, _map[_key] / value);
     2844        return *this;
     2845      }
     2846      Reference& operator%=(int value) {
     2847        _map.set(_key, _map[_key] % value);
     2848        return *this;
     2849      }
     2850      Reference& operator&=(int value) {
     2851        _map.set(_key, _map[_key] & value);
     2852        return *this;
     2853      }
     2854      Reference& operator|=(int value) {
     2855        _map.set(_key, _map[_key] | value);
     2856        return *this;
     2857      }
     2858      Reference& operator^=(int value) {
     2859        _map.set(_key, _map[_key] ^ value);
     2860        return *this;
     2861      }
     2862      Reference& operator<<=(int value) {
     2863        _map.set(_key, _map[_key] << value);
     2864        return *this;
     2865      }
     2866      Reference& operator>>=(int value) {
     2867        _map.set(_key, _map[_key] >> value);
     2868        return *this;
     2869      }
     2870
     2871    private:
     2872      Key _key;
     2873      IterableIntMap& _map;
     2874    };
     2875
     2876    /// The const reference type.
     2877    typedef const Value& ConstReference;
     2878
     2879    /// \brief Gives back the maximal value plus one.
     2880    ///
     2881    /// Gives back the maximal value plus one.
     2882    int size() const {
     2883      return _first.size();
     2884    }
     2885
     2886    /// \brief Set operation of the map.
     2887    ///
     2888    /// Set operation of the map.
     2889    void set(const Key& key, const Value& value) {
     2890      unlace(key);
     2891      Parent::operator[](key).value = value;
     2892      lace(key);
     2893    }
     2894
     2895    /// \brief Const subscript operator of the map.
     2896    ///
     2897    /// Const subscript operator of the map.
     2898    const Value& operator[](const Key& key) const {
     2899      return Parent::operator[](key).value;
     2900    }
     2901
     2902    /// \brief Subscript operator of the map.
     2903    ///
     2904    /// Subscript operator of the map.
     2905    Reference operator[](const Key& key) {
     2906      return Reference(*this, key);
     2907    }
     2908
     2909    /// \brief Iterator for the keys with the same value.
     2910    ///
     2911    /// Iterator for the keys with the same value. It works
     2912    /// like a graph item iterator, it can be converted to
     2913    /// the item type of the map, incremented with \c ++ operator, and
     2914    /// if the iterator leaves the last valid item, it will be equal to
     2915    /// \c INVALID.
     2916    class ItemIt : public Key {
     2917    public:
     2918      typedef Key Parent;
     2919
     2920      /// \brief Invalid constructor \& conversion.
     2921      ///
     2922      /// This constructor initializes the iterator to be invalid.
     2923      /// \sa Invalid for more details.
     2924      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2925
     2926      /// \brief Creates an iterator with a value.
     2927      ///
     2928      /// Creates an iterator with a value. It iterates on the
     2929      /// keys mapped to the given value.
     2930      /// \param map The IterableIntMap.
     2931      /// \param value The value.
     2932      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     2933        if (value < 0 || value >= int(_map->_first.size())) {
     2934          Parent::operator=(INVALID);
     2935        } else {
     2936          Parent::operator=(_map->_first[value]);
     2937        }
     2938      }
     2939
     2940      /// \brief Increment operator.
     2941      ///
     2942      /// Increment operator.
     2943      ItemIt& operator++() {
     2944        Parent::operator=(_map->IterableIntMap::Parent::
     2945                          operator[](static_cast<Parent&>(*this)).next);
     2946        return *this;
     2947      }
     2948
     2949    private:
     2950      const IterableIntMap* _map;
     2951    };
     2952
     2953  protected:
     2954
     2955    virtual void erase(const Key& key) {
     2956      unlace(key);
     2957      Parent::erase(key);
     2958    }
     2959
     2960    virtual void erase(const std::vector<Key>& keys) {
     2961      for (int i = 0; i < int(keys.size()); ++i) {
     2962        unlace(keys[i]);
     2963      }
     2964      Parent::erase(keys);
     2965    }
     2966
     2967    virtual void clear() {
     2968      _first.clear();
     2969      Parent::clear();
     2970    }
     2971
     2972  private:
     2973    std::vector<Key> _first;
     2974  };
     2975
     2976  namespace _maps_bits {
     2977    template <typename Item, typename Value>
     2978    struct IterableValueMapNode {
     2979      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     2980      Item prev, next;
     2981      Value value;
     2982    };
     2983  }
     2984
     2985  /// \brief Dynamic iterable map for comparable values.
     2986  ///
     2987  /// This class provides a special graph map type which can store an
     2988  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     2989  /// For each value it is possible to iterate on the keys mapped to
     2990  /// the value.
     2991  ///
     2992  /// The map stores for each value a linked list with
     2993  /// the items which mapped to the value, and the values are stored
     2994  /// in balanced binary tree. The values of the map can be accessed
     2995  /// with stl compatible forward iterator.
     2996  ///
     2997  /// This type is not reference map, so it cannot be modified with
     2998  /// the subscript operator.
     2999  ///
     3000  /// \tparam GR The graph type.
     3001  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     3002  /// \c GR::Edge).
     3003  /// \tparam V The value type of the map. It can be any comparable
     3004  /// value type.
     3005  ///
     3006  /// \see IterableBoolMap, IterableIntMap
     3007  /// \see CrossRefMap
     3008  template <typename GR, typename K, typename V>
     3009  class IterableValueMap
     3010    : protected ItemSetTraits<GR, K>::
     3011        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     3012  public:
     3013    typedef typename ItemSetTraits<GR, K>::
     3014      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
     3015
     3016    /// The key type
     3017    typedef K Key;
     3018    /// The value type
     3019    typedef V Value;
     3020    /// The graph type
     3021    typedef GR Graph;
     3022
     3023  public:
     3024
     3025    /// \brief Constructor of the map with a given value.
     3026    ///
     3027    /// Constructor of the map with a given value.
     3028    explicit IterableValueMap(const Graph& graph,
     3029                              const Value& value = Value())
     3030      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
     3031      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3032        lace(it);
     3033      }
     3034    }
     3035
     3036  protected:
     3037
     3038    void unlace(const Key& key) {
     3039      typename Parent::Value& node = Parent::operator[](key);
     3040      if (node.prev != INVALID) {
     3041        Parent::operator[](node.prev).next = node.next;
     3042      } else {
     3043        if (node.next != INVALID) {
     3044          _first[node.value] = node.next;
     3045        } else {
     3046          _first.erase(node.value);
     3047        }
     3048      }
     3049      if (node.next != INVALID) {
     3050        Parent::operator[](node.next).prev = node.prev;
     3051      }
     3052    }
     3053
     3054    void lace(const Key& key) {
     3055      typename Parent::Value& node = Parent::operator[](key);
     3056      typename std::map<Value, Key>::iterator it = _first.find(node.value);
     3057      if (it == _first.end()) {
     3058        node.prev = node.next = INVALID;
     3059        _first.insert(std::make_pair(node.value, key));
     3060      } else {
     3061        node.prev = INVALID;
     3062        node.next = it->second;
     3063        if (node.next != INVALID) {
     3064          Parent::operator[](node.next).prev = key;
     3065        }
     3066        it->second = key;
     3067      }
     3068    }
     3069
     3070  public:
     3071
     3072    /// \brief Forward iterator for values.
     3073    ///
     3074    /// This iterator is an stl compatible forward
     3075    /// iterator on the values of the map. The values can
     3076    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     3077    class ValueIterator
     3078      : public std::iterator<std::forward_iterator_tag, Value> {
     3079      friend class IterableValueMap;
     3080    private:
     3081      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
     3082        : it(_it) {}
     3083    public:
     3084
     3085      ValueIterator() {}
     3086
     3087      ValueIterator& operator++() { ++it; return *this; }
     3088      ValueIterator operator++(int) {
     3089        ValueIterator tmp(*this);
     3090        operator++();
     3091        return tmp;
     3092      }
     3093
     3094      const Value& operator*() const { return it->first; }
     3095      const Value* operator->() const { return &(it->first); }
     3096
     3097      bool operator==(ValueIterator jt) const { return it == jt.it; }
     3098      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     3099
     3100    private:
     3101      typename std::map<Value, Key>::const_iterator it;
     3102    };
     3103
     3104    /// \brief Returns an iterator to the first value.
     3105    ///
     3106    /// Returns an stl compatible iterator to the
     3107    /// first value of the map. The values of the
     3108    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3109    /// range.
     3110    ValueIterator beginValue() const {
     3111      return ValueIterator(_first.begin());
     3112    }
     3113
     3114    /// \brief Returns an iterator after the last value.
     3115    ///
     3116    /// Returns an stl compatible iterator after the
     3117    /// last value of the map. The values of the
     3118    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3119    /// range.
     3120    ValueIterator endValue() const {
     3121      return ValueIterator(_first.end());
     3122    }
     3123
     3124    /// \brief Set operation of the map.
     3125    ///
     3126    /// Set operation of the map.
     3127    void set(const Key& key, const Value& value) {
     3128      unlace(key);
     3129      Parent::operator[](key).value = value;
     3130      lace(key);
     3131    }
     3132
     3133    /// \brief Const subscript operator of the map.
     3134    ///
     3135    /// Const subscript operator of the map.
     3136    const Value& operator[](const Key& key) const {
     3137      return Parent::operator[](key).value;
     3138    }
     3139
     3140    /// \brief Iterator for the keys with the same value.
     3141    ///
     3142    /// Iterator for the keys with the same value. It works
     3143    /// like a graph item iterator, it can be converted to
     3144    /// the item type of the map, incremented with \c ++ operator, and
     3145    /// if the iterator leaves the last valid item, it will be equal to
     3146    /// \c INVALID.
     3147    class ItemIt : public Key {
     3148    public:
     3149      typedef Key Parent;
     3150
     3151      /// \brief Invalid constructor \& conversion.
     3152      ///
     3153      /// This constructor initializes the iterator to be invalid.
     3154      /// \sa Invalid for more details.
     3155      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     3156
     3157      /// \brief Creates an iterator with a value.
     3158      ///
     3159      /// Creates an iterator with a value. It iterates on the
     3160      /// keys which have the given value.
     3161      /// \param map The IterableValueMap
     3162      /// \param value The value
     3163      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     3164        typename std::map<Value, Key>::const_iterator it =
     3165          map._first.find(value);
     3166        if (it == map._first.end()) {
     3167          Parent::operator=(INVALID);
     3168        } else {
     3169          Parent::operator=(it->second);
     3170        }
     3171      }
     3172
     3173      /// \brief Increment operator.
     3174      ///
     3175      /// Increment Operator.
     3176      ItemIt& operator++() {
     3177        Parent::operator=(_map->IterableValueMap::Parent::
     3178                          operator[](static_cast<Parent&>(*this)).next);
     3179        return *this;
     3180      }
     3181
     3182
     3183    private:
     3184      const IterableValueMap* _map;
     3185    };
     3186
     3187  protected:
     3188
     3189    virtual void add(const Key& key) {
     3190      Parent::add(key);
     3191      unlace(key);
     3192    }
     3193
     3194    virtual void add(const std::vector<Key>& keys) {
     3195      Parent::add(keys);
     3196      for (int i = 0; i < int(keys.size()); ++i) {
     3197        lace(keys[i]);
     3198      }
     3199    }
     3200
     3201    virtual void erase(const Key& key) {
     3202      unlace(key);
     3203      Parent::erase(key);
     3204    }
     3205
     3206    virtual void erase(const std::vector<Key>& keys) {
     3207      for (int i = 0; i < int(keys.size()); ++i) {
     3208        unlace(keys[i]);
     3209      }
     3210      Parent::erase(keys);
     3211    }
     3212
     3213    virtual void build() {
     3214      Parent::build();
     3215      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3216        lace(it);
     3217      }
     3218    }
     3219
     3220    virtual void clear() {
     3221      _first.clear();
     3222      Parent::clear();
     3223    }
     3224
     3225  private:
     3226    std::map<Value, Key> _first;
     3227  };
     3228
    23333229  /// \brief Map of the source nodes of arcs in a digraph.
    23343230  ///
     
    25003396  /// whenever the digraph changes.
    25013397  ///
    2502   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3398  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    25033399  /// may provide alternative ways to modify the digraph.
    25043400  /// The correct behavior of InDegMap is not guarantied if these additional
     
    25163412
    25173413  public:
    2518    
     3414
    25193415    /// The graph type of InDegMap
    25203416    typedef GR Graph;
     
    26303526  /// whenever the digraph changes.
    26313527  ///
    2632   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3528  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26333529  /// may provide alternative ways to modify the digraph.
    26343530  /// The correct behavior of OutDegMap is not guarantied if these additional
  • lemon/maps.h

    r694 r695  
    19021902
    19031903  /// This class provides simple invertable graph maps.
    1904   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    1905   /// and if a key is set to a new value then store it
    1906   /// in the inverse map.
     1904  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1905  /// and if a key is set to a new value, then stores it in the inverse map.
    19071906  /// The values of the map can be accessed
    19081907  /// with stl compatible forward iterator.
    19091908  ///
    19101909  /// This type is not reference map, so it cannot be modified with
    1911   /// the subscription operator.
     1910  /// the subscript operator.
    19121911  ///
    19131912  /// \tparam GR The graph type.
     
    19251924      template Map<V>::Type Map;
    19261925
    1927     typedef std::map<V, K> Container;
     1926    typedef std::multimap<V, K> Container;
    19281927    Container _inv_map;
    19291928
     
    19501949    /// iterator on the values of the map. The values can
    19511950    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1951    /// They are considered with multiplicity, so each value is
     1952    /// traversed for each item it is assigned to.
    19521953    class ValueIterator
    19531954      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20022003    void set(const Key& key, const Value& val) {
    20032004      Value oldval = Map::operator[](key);
    2004       typename Container::iterator it = _inv_map.find(oldval);
    2005       if (it != _inv_map.end() && it->second == key) {
    2006         _inv_map.erase(it);
     2005      typename Container::iterator it;
     2006      for (it = _inv_map.equal_range(oldval).first;
     2007           it != _inv_map.equal_range(oldval).second; ++it) {
     2008        if (it->second == key) {
     2009          _inv_map.erase(it);
     2010          break;
     2011        }
    20072012      }
    20082013      _inv_map.insert(std::make_pair(val, key));
     
    20182023    }
    20192024
    2020     /// \brief Gives back the item by its value.
    2021     ///
    2022     /// Gives back the item by its value.
    2023     Key operator()(const Value& key) const {
    2024       typename Container::const_iterator it = _inv_map.find(key);
     2025    /// \brief Gives back an item by its value.
     2026    ///
     2027    /// This function gives back an item that is assigned to
     2028    /// the given value or \c INVALID if no such item exists.
     2029    /// If there are more items with the same associated value,
     2030    /// only one of them is returned.
     2031    Key operator()(const Value& val) const {
     2032      typename Container::const_iterator it = _inv_map.find(val);
    20252033      return it != _inv_map.end() ? it->second : INVALID;
    20262034    }
     
    20342042    virtual void erase(const Key& key) {
    20352043      Value val = Map::operator[](key);
    2036       typename Container::iterator it = _inv_map.find(val);
    2037       if (it != _inv_map.end() && it->second == key) {
    2038         _inv_map.erase(it);
     2044      typename Container::iterator it;
     2045      for (it = _inv_map.equal_range(val).first;
     2046           it != _inv_map.equal_range(val).second; ++it) {
     2047        if (it->second == key) {
     2048          _inv_map.erase(it);
     2049          break;
     2050        }
    20392051      }
    20402052      Map::erase(key);
     
    20482060      for (int i = 0; i < int(keys.size()); ++i) {
    20492061        Value val = Map::operator[](keys[i]);
    2050         typename Container::iterator it = _inv_map.find(val);
    2051         if (it != _inv_map.end() && it->second == keys[i]) {
    2052           _inv_map.erase(it);
     2062        typename Container::iterator it;
     2063        for (it = _inv_map.equal_range(val).first;
     2064             it != _inv_map.equal_range(val).second; ++it) {
     2065          if (it->second == keys[i]) {
     2066            _inv_map.erase(it);
     2067            break;
     2068          }
    20532069        }
    20542070      }
     
    20862102      /// \brief Subscript operator.
    20872103      ///
    2088       /// Subscript operator. It gives back the item
    2089       /// that was last assigned to the given value.
     2104      /// Subscript operator. It gives back an item
     2105      /// that is assigned to the given value or \c INVALID
     2106      /// if no such item exists.
    20902107      Value operator[](const Key& key) const {
    20912108        return _inverted(key);
     
    23212338  ///
    23222339  /// This type is a reference map, so it can be modified with the
    2323   /// subscription operator.
     2340  /// subscript operator.
    23242341  ///
    23252342  /// \tparam GR The graph type.
     
    26882705  ///
    26892706  /// This type is a reference map, so it can be modified with the
    2690   /// subscription operator.
     2707  /// subscript operator.
    26912708  ///
    26922709  /// \note The size of the data structure depends on the largest
     
    29792996  ///
    29802997  /// This type is not reference map, so it cannot be modified with
    2981   /// the subscription operator.
     2998  /// the subscript operator.
    29822999  ///
    29833000  /// \tparam GR The graph type.
Note: See TracChangeset for help on using the changeset viewer.