lemon/maps.h
changeset 797 30cb42e3e43a
parent 684 7b1a6e963018
parent 694 71939d63ae77
child 717 684964884a2e
equal deleted inserted replaced
33:d3ddbcf08d47 36:66471a18b9b8
    20 #define LEMON_MAPS_H
    20 #define LEMON_MAPS_H
    21 
    21 
    22 #include <iterator>
    22 #include <iterator>
    23 #include <functional>
    23 #include <functional>
    24 #include <vector>
    24 #include <vector>
       
    25 #include <map>
    25 
    26 
    26 #include <lemon/core.h>
    27 #include <lemon/core.h>
    27 
    28 
    28 ///\file
    29 ///\file
    29 ///\ingroup maps
    30 ///\ingroup maps
    30 ///\brief Miscellaneous property maps
    31 ///\brief Miscellaneous property maps
    31 
       
    32 #include <map>
       
    33 
    32 
    34 namespace lemon {
    33 namespace lemon {
    35 
    34 
    36   /// \addtogroup maps
    35   /// \addtogroup maps
    37   /// @{
    36   /// @{
  1816   /// @{
  1815   /// @{
  1817 
  1816 
  1818   /// \brief Provides an immutable and unique id for each item in a graph.
  1817   /// \brief Provides an immutable and unique id for each item in a graph.
  1819   ///
  1818   ///
  1820   /// IdMap provides a unique and immutable id for each item of the
  1819   /// 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
  1822   ///  - \b unique: different items get different ids,
  1821   ///  - \b unique: different items get different ids,
  1823   ///  - \b immutable: the id of an item does not change (even if you
  1822   ///  - \b immutable: the id of an item does not change (even if you
  1824   ///    delete other nodes).
  1823   ///    delete other nodes).
  1825   ///
  1824   ///
  1826   /// Using this map you get access (i.e. can read) the inner id values of
  1825   /// Using this map you get access (i.e. can read) the inner id values of
  2271     int operator[](const Item& item) const {
  2270     int operator[](const Item& item) const {
  2272       return Map::operator[](item);
  2271       return Map::operator[](item);
  2273     }
  2272     }
  2274 
  2273 
  2275     /// \brief Gives back the item belonging to a \e RangeId
  2274     /// \brief Gives back the item belonging to a \e RangeId
  2276     /// 
  2275     ///
  2277     /// Gives back the item belonging to a \e RangeId.
  2276     /// Gives back the item belonging to a \e RangeId.
  2278     Item operator()(int id) const {
  2277     Item operator()(int id) const {
  2279       return _inv_map[id];
  2278       return _inv_map[id];
  2280     }
  2279     }
  2281 
  2280 
  2328     const InverseMap inverse() const {
  2327     const InverseMap inverse() const {
  2329       return InverseMap(*this);
  2328       return InverseMap(*this);
  2330     }
  2329     }
  2331   };
  2330   };
  2332 
  2331 
       
  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 
  2333   /// \brief Map of the source nodes of arcs in a digraph.
  3229   /// \brief Map of the source nodes of arcs in a digraph.
  2334   ///
  3230   ///
  2335   /// SourceMap provides access for the source node of each arc in a digraph,
  3231   /// SourceMap provides access for the source node of each arc in a digraph,
  2336   /// which is returned by the \c source() function of the digraph.
  3232   /// which is returned by the \c source() function of the digraph.
  2337   /// \tparam GR The digraph type.
  3233   /// \tparam GR The digraph type.
  2497   /// This map returns the in-degree of a node. Once it is constructed,
  3393   /// This map returns the in-degree of a node. Once it is constructed,
  2498   /// the degrees are stored in a standard \c NodeMap, so each query is done
  3394   /// the degrees are stored in a standard \c NodeMap, so each query is done
  2499   /// in constant time. On the other hand, the values are updated automatically
  3395   /// in constant time. On the other hand, the values are updated automatically
  2500   /// whenever the digraph changes.
  3396   /// whenever the digraph changes.
  2501   ///
  3397   ///
  2502   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
  3398   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
  2503   /// may provide alternative ways to modify the digraph.
  3399   /// may provide alternative ways to modify the digraph.
  2504   /// The correct behavior of InDegMap is not guarantied if these additional
  3400   /// The correct behavior of InDegMap is not guarantied if these additional
  2505   /// features are used. For example the functions
  3401   /// features are used. For example the functions
  2506   /// \ref ListDigraph::changeSource() "changeSource()",
  3402   /// \ref ListDigraph::changeSource() "changeSource()",
  2507   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  3403   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  2513   class InDegMap
  3409   class InDegMap
  2514     : protected ItemSetTraits<GR, typename GR::Arc>
  3410     : protected ItemSetTraits<GR, typename GR::Arc>
  2515       ::ItemNotifier::ObserverBase {
  3411       ::ItemNotifier::ObserverBase {
  2516 
  3412 
  2517   public:
  3413   public:
  2518     
  3414 
  2519     /// The graph type of InDegMap
  3415     /// The graph type of InDegMap
  2520     typedef GR Graph;
  3416     typedef GR Graph;
  2521     typedef GR Digraph;
  3417     typedef GR Digraph;
  2522     /// The key type
  3418     /// The key type
  2523     typedef typename Digraph::Node Key;
  3419     typedef typename Digraph::Node Key;
  2627   /// This map returns the out-degree of a node. Once it is constructed,
  3523   /// This map returns the out-degree of a node. Once it is constructed,
  2628   /// the degrees are stored in a standard \c NodeMap, so each query is done
  3524   /// the degrees are stored in a standard \c NodeMap, so each query is done
  2629   /// in constant time. On the other hand, the values are updated automatically
  3525   /// in constant time. On the other hand, the values are updated automatically
  2630   /// whenever the digraph changes.
  3526   /// whenever the digraph changes.
  2631   ///
  3527   ///
  2632   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
  3528   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
  2633   /// may provide alternative ways to modify the digraph.
  3529   /// may provide alternative ways to modify the digraph.
  2634   /// The correct behavior of OutDegMap is not guarantied if these additional
  3530   /// The correct behavior of OutDegMap is not guarantied if these additional
  2635   /// features are used. For example the functions
  3531   /// features are used. For example the functions
  2636   /// \ref ListDigraph::changeSource() "changeSource()",
  3532   /// \ref ListDigraph::changeSource() "changeSource()",
  2637   /// \ref ListDigraph::changeTarget() "changeTarget()" and
  3533   /// \ref ListDigraph::changeTarget() "changeTarget()" and