COIN-OR::LEMON - Graph Library

Changeset 768:99124ea4f048 in lemon for lemon/maps.h


Ignore:
Timestamp:
08/02/09 13:44:45 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Parents:
767:6e8c27ee9079 (diff), 741: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

    r741 r768  
    18261826  /// the items stored in the graph, which is returned by the \c id()
    18271827  /// function of the graph. This map can be inverted with its member
    1828   /// class \c InverseMap or with the \c operator() member.
     1828  /// class \c InverseMap or with the \c operator()() member.
    18291829  ///
    18301830  /// \tparam GR The graph type.
     
    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;
     2034    }
     2035   
     2036    /// \brief Returns the number of items with the given value.
     2037    ///
     2038    /// This function returns the number of items with the given value
     2039    /// associated with it.
     2040    int count(const Value &val) const {
     2041      return _inv_map.count(val);
    20262042    }
    20272043
     
    20342050    virtual void erase(const Key& key) {
    20352051      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);
     2052      typename Container::iterator it;
     2053      for (it = _inv_map.equal_range(val).first;
     2054           it != _inv_map.equal_range(val).second; ++it) {
     2055        if (it->second == key) {
     2056          _inv_map.erase(it);
     2057          break;
     2058        }
    20392059      }
    20402060      Map::erase(key);
     
    20482068      for (int i = 0; i < int(keys.size()); ++i) {
    20492069        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);
     2070        typename Container::iterator it;
     2071        for (it = _inv_map.equal_range(val).first;
     2072             it != _inv_map.equal_range(val).second; ++it) {
     2073          if (it->second == keys[i]) {
     2074            _inv_map.erase(it);
     2075            break;
     2076          }
    20532077        }
    20542078      }
     
    20862110      /// \brief Subscript operator.
    20872111      ///
    2088       /// Subscript operator. It gives back the item
    2089       /// that was last assigned to the given value.
     2112      /// Subscript operator. It gives back an item
     2113      /// that is assigned to the given value or \c INVALID
     2114      /// if no such item exists.
    20902115      Value operator[](const Key& key) const {
    20912116        return _inverted(key);
     
    21052130  };
    21062131
    2107   /// \brief Provides continuous and unique ID for the
     2132  /// \brief Provides continuous and unique id for the
    21082133  /// items of a graph.
    21092134  ///
    21102135  /// RangeIdMap provides a unique and continuous
    2111   /// ID for each item of a given type (\c Node, \c Arc or
     2136  /// id for each item of a given type (\c Node, \c Arc or
    21122137  /// \c Edge) in a graph. This id is
    21132138  ///  - \b unique: different items get different ids,
     
    21202145  /// the \c id() function of the graph or \ref IdMap.
    21212146  /// This map can be inverted with its member class \c InverseMap,
    2122   /// or with the \c operator() member.
     2147  /// or with the \c operator()() member.
    21232148  ///
    21242149  /// \tparam GR The graph type.
  • lemon/maps.h

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