COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [695:8dae88c5943e:692:33f417de9e70] in lemon-1.2


Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/maps.h

    r695 r684  
    2323#include <functional>
    2424#include <vector>
    25 #include <map>
    2625
    2726#include <lemon/core.h>
    … …  
    3029///\ingroup maps
    3130///\brief Miscellaneous property maps
     31
     32#include <map>
    3233
    3334namespace lemon {
    … …  
    18181819  ///
    18191820  /// IdMap provides a unique and immutable id for each item of the
    1820   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
     1821  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
    18211822  ///  - \b unique: different items get different ids,
    18221823  ///  - \b immutable: the id of an item does not change (even if you
    … …  
    22732274
    22742275    /// \brief Gives back the item belonging to a \e RangeId
    2275     ///
     2276    /// 
    22762277    /// Gives back the item belonging to a \e RangeId.
    22772278    Item operator()(int id) const {
    … …  
    23302331  };
    23312332
    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 
    32292333  /// \brief Map of the source nodes of arcs in a digraph.
    32302334  ///
    … …  
    33962500  /// whenever the digraph changes.
    33972501  ///
    3398   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2502  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    33992503  /// may provide alternative ways to modify the digraph.
    34002504  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    34122516
    34132517  public:
    3414 
     2518   
    34152519    /// The graph type of InDegMap
    34162520    typedef GR Graph;
    … …  
    35262630  /// whenever the digraph changes.
    35272631  ///
    3528   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2632  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    35292633  /// may provide alternative ways to modify the digraph.
    35302634  /// The correct behavior of OutDegMap is not guarantied if these additional

  • test/maps_test.cc

    r695 r684  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
    25 #include <lemon/smart_graph.h>
     25#include <lemon/list_graph.h>
    2626
    2727#include "test_tools.h"
    … …  
    350350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    351351  }
    352 
     352 
    353353  // CrossRefMap
    354354  {
    355     typedef SmartDigraph Graph;
     355    typedef ListDigraph Graph;
    356356    DIGRAPH_TYPEDEFS(Graph);
    357357
    … …  
    384384          it == map.endValue(), "Wrong value iterator");
    385385  }
    386  
    387   // Iterable bool map
    388   {
    389     typedef SmartGraph Graph;
    390     typedef SmartGraph::Node Item;
    391 
    392     typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
    393     checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
    394 
    395     const int num = 10;
    396     Graph g;
    397     std::vector<Item> items;
    398     for (int i = 0; i < num; ++i) {
    399       items.push_back(g.addNode());
    400     }
    401 
    402     Ibm map1(g, true);
    403     int n = 0;
    404     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    405       check(map1[static_cast<Item>(it)], "Wrong TrueIt");
    406       ++n;
    407     }
    408     check(n == num, "Wrong number");
    409 
    410     n = 0;
    411     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    412         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    413         ++n;
    414     }
    415     check(n == num, "Wrong number");
    416     check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
    417     check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
    418 
    419     map1[items[5]] = true;
    420 
    421     n = 0;
    422     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    423         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    424         ++n;
    425     }
    426     check(n == num, "Wrong number");
    427 
    428     map1[items[num / 2]] = false;
    429     check(map1[items[num / 2]] == false, "Wrong map value");
    430 
    431     n = 0;
    432     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    433         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    434         ++n;
    435     }
    436     check(n == num - 1, "Wrong number");
    437 
    438     n = 0;
    439     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    440         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    441         ++n;
    442     }
    443     check(n == 1, "Wrong number");
    444 
    445     map1[items[0]] = false;
    446     check(map1[items[0]] == false, "Wrong map value");
    447 
    448     map1[items[num - 1]] = false;
    449     check(map1[items[num - 1]] == false, "Wrong map value");
    450 
    451     n = 0;
    452     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    453         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    454         ++n;
    455     }
    456     check(n == num - 3, "Wrong number");
    457     check(map1.trueNum() == num - 3, "Wrong number");
    458 
    459     n = 0;
    460     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    461         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    462         ++n;
    463     }
    464     check(n == 3, "Wrong number");
    465     check(map1.falseNum() == 3, "Wrong number");
    466   }
    467 
    468   // Iterable int map
    469   {
    470     typedef SmartGraph Graph;
    471     typedef SmartGraph::Node Item;
    472     typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
    473 
    474     checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
    475 
    476     const int num = 10;
    477     Graph g;
    478     std::vector<Item> items;
    479     for (int i = 0; i < num; ++i) {
    480       items.push_back(g.addNode());
    481     }
    482 
    483     Iim map1(g);
    484     check(map1.size() == 0, "Wrong size");
    485 
    486     for (int i = 0; i < num; ++i) {
    487       map1[items[i]] = i;
    488     }
    489     check(map1.size() == num, "Wrong size");
    490 
    491     for (int i = 0; i < num; ++i) {
    492       Iim::ItemIt it(map1, i);
    493       check(static_cast<Item>(it) == items[i], "Wrong value");
    494       ++it;
    495       check(static_cast<Item>(it) == INVALID, "Wrong value");
    496     }
    497 
    498     for (int i = 0; i < num; ++i) {
    499       map1[items[i]] = i % 2;
    500     }
    501     check(map1.size() == 2, "Wrong size");
    502 
    503     int n = 0;
    504     for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
    505       check(map1[static_cast<Item>(it)] == 0, "Wrong value");
    506       ++n;
    507     }
    508     check(n == (num + 1) / 2, "Wrong number");
    509 
    510     for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
    511       check(map1[static_cast<Item>(it)] == 1, "Wrong value");
    512       ++n;
    513     }
    514     check(n == num, "Wrong number");
    515 
    516   }
    517 
    518   // Iterable value map
    519   {
    520     typedef SmartGraph Graph;
    521     typedef SmartGraph::Node Item;
    522     typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
    523 
    524     checkConcept<ReadWriteMap<Item, double>, Ivm>();
    525 
    526     const int num = 10;
    527     Graph g;
    528     std::vector<Item> items;
    529     for (int i = 0; i < num; ++i) {
    530       items.push_back(g.addNode());
    531     }
    532 
    533     Ivm map1(g, 0.0);
    534     check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
    535     check(*map1.beginValue() == 0.0, "Wrong value");
    536 
    537     for (int i = 0; i < num; ++i) {
    538       map1.set(items[i], static_cast<double>(i));
    539     }
    540     check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
    541 
    542     for (int i = 0; i < num; ++i) {
    543       Ivm::ItemIt it(map1, static_cast<double>(i));
    544       check(static_cast<Item>(it) == items[i], "Wrong value");
    545       ++it;
    546       check(static_cast<Item>(it) == INVALID, "Wrong value");
    547     }
    548 
    549     for (Ivm::ValueIterator vit = map1.beginValue();
    550          vit != map1.endValue(); ++vit) {
    551       check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
    552             "Wrong ValueIterator");
    553     }
    554 
    555     for (int i = 0; i < num; ++i) {
    556       map1.set(items[i], static_cast<double>(i % 2));
    557     }
    558     check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
    559 
    560     int n = 0;
    561     for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
    562       check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
    563       ++n;
    564     }
    565     check(n == (num + 1) / 2, "Wrong number");
    566 
    567     for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
    568       check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
    569       ++n;
    570     }
    571     check(n == num, "Wrong number");
    572 
    573   }
     386
    574387  return 0;
    575388}
Note: See TracChangeset for help on using the changeset viewer.