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 / [721:99124ea4f048:720:6e8c27ee9079] in lemon-main


Ignore:
Files:
3 deleted
5 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r681 r667  
    6060        lemon/bfs.h \
    6161        lemon/bin_heap.h \
    62         lemon/bucket_heap.h \
    6362        lemon/cbc.h \
    6463        lemon/circulation.h \
    … …  
    7877        lemon/error.h \
    7978        lemon/euler.h \
    80         lemon/fib_heap.h \
    8179        lemon/full_graph.h \
    8280        lemon/glpk.h \
    … …  
    102100        lemon/path.h \
    103101        lemon/preflow.h \
    104         lemon/radix_heap.h \
    105102        lemon/radix_sort.h \
    106103        lemon/random.h \

  • lemon/bin_heap.h

    r683 r584  
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure.
    37   ///
     36  ///This class implements the \e binary \e heap data structure. 
     37  /// 
    3838  ///A \e heap is a data structure for storing items with specified values
    3939  ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c CMP specifies the ordering of the priorities.
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
    4141  ///In a heap one can change the priority of an item, add or erase an
    4242  ///item, etc.
    … …  
    4545  ///\tparam IM A read and writable item map with int values, used internally
    4646  ///to handle the cross references.
    47   ///\tparam CMP A functor class for the ordering of the priorities.
     47  ///\tparam Comp A functor class for the ordering of the priorities.
    4848  ///The default is \c std::less<PR>.
    4949  ///
    5050  ///\sa FibHeap
    5151  ///\sa Dijkstra
    52   template <typename PR, typename IM, typename CMP = std::less<PR> >
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    5353  class BinHeap {
    5454
    … …  
    6363    typedef std::pair<Item,Prio> Pair;
    6464    ///\e
    65     typedef CMP Compare;
     65    typedef Comp Compare;
    6666
    6767    /// \brief Type to represent the items states.

  • lemon/maps.h

    r721 r720  
    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
    … …  
    22812282
    22822283    /// \brief Gives back the item belonging to a \e RangeId
    2283     ///
     2284    /// 
    22842285    /// Gives back the item belonging to a \e RangeId.
    22852286    Item operator()(int id) const {
    … …  
    23382339  };
    23392340
    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 
    32372341  /// \brief Map of the source nodes of arcs in a digraph.
    32382342  ///
    … …  
    34042508  /// whenever the digraph changes.
    34052509  ///
    3406   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2510  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    34072511  /// may provide alternative ways to modify the digraph.
    34082512  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    34202524
    34212525  public:
    3422 
     2526   
    34232527    /// The graph type of InDegMap
    34242528    typedef GR Graph;
    … …  
    35342638  /// whenever the digraph changes.
    35352639  ///
    3536   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2640  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    35372641  /// may provide alternative ways to modify the digraph.
    35382642  /// The correct behavior of OutDegMap is not guarantied if these additional

  • test/heap_test.cc

    r681 r440  
    3232
    3333#include <lemon/bin_heap.h>
    34 #include <lemon/fib_heap.h>
    35 #include <lemon/radix_heap.h>
    36 #include <lemon/bucket_heap.h>
    3734
    3835#include "test_tools.h"
    … …  
    187184  }
    188185
    189   {
    190     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    192     heapSortTest<IntHeap>();
    193     heapIncreaseTest<IntHeap>();
    194 
    195     typedef FibHeap<Prio, IntNodeMap > NodeHeap;
    196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    198   }
    199 
    200   {
    201     typedef RadixHeap<ItemIntMap> IntHeap;
    202     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    203     heapSortTest<IntHeap>();
    204     heapIncreaseTest<IntHeap>();
    205 
    206     typedef RadixHeap<IntNodeMap > NodeHeap;
    207     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    208     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    209   }
    210 
    211   {
    212     typedef BucketHeap<ItemIntMap> IntHeap;
    213     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    214     heapSortTest<IntHeap>();
    215     heapIncreaseTest<IntHeap>();
    216 
    217     typedef BucketHeap<IntNodeMap > NodeHeap;
    218     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    219     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    220   }
    221 
    222 
    223186  return 0;
    224187}

  • test/maps_test.cc

    r721 r720  
    2424#include <lemon/maps.h>
    2525#include <lemon/list_graph.h>
    26 #include <lemon/smart_graph.h>
    2726
    2827#include "test_tools.h"
    … …  
    496495  }
    497496
    498   // Iterable bool map
    499   {
    500     typedef SmartGraph Graph;
    501     typedef SmartGraph::Node Item;
    502 
    503     typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
    504     checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
    505 
    506     const int num = 10;
    507     Graph g;
    508     std::vector<Item> items;
    509     for (int i = 0; i < num; ++i) {
    510       items.push_back(g.addNode());
    511     }
    512 
    513     Ibm map1(g, true);
    514     int n = 0;
    515     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    516       check(map1[static_cast<Item>(it)], "Wrong TrueIt");
    517       ++n;
    518     }
    519     check(n == num, "Wrong number");
    520 
    521     n = 0;
    522     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    523         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    524         ++n;
    525     }
    526     check(n == num, "Wrong number");
    527     check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
    528     check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
    529 
    530     map1[items[5]] = true;
    531 
    532     n = 0;
    533     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    534         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    535         ++n;
    536     }
    537     check(n == num, "Wrong number");
    538 
    539     map1[items[num / 2]] = false;
    540     check(map1[items[num / 2]] == false, "Wrong map value");
    541 
    542     n = 0;
    543     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    544         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    545         ++n;
    546     }
    547     check(n == num - 1, "Wrong number");
    548 
    549     n = 0;
    550     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    551         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    552         ++n;
    553     }
    554     check(n == 1, "Wrong number");
    555 
    556     map1[items[0]] = false;
    557     check(map1[items[0]] == false, "Wrong map value");
    558 
    559     map1[items[num - 1]] = false;
    560     check(map1[items[num - 1]] == false, "Wrong map value");
    561 
    562     n = 0;
    563     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    564         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    565         ++n;
    566     }
    567     check(n == num - 3, "Wrong number");
    568     check(map1.trueNum() == num - 3, "Wrong number");
    569 
    570     n = 0;
    571     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    572         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    573         ++n;
    574     }
    575     check(n == 3, "Wrong number");
    576     check(map1.falseNum() == 3, "Wrong number");
    577   }
    578 
    579   // Iterable int map
    580   {
    581     typedef SmartGraph Graph;
    582     typedef SmartGraph::Node Item;
    583     typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
    584 
    585     checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
    586 
    587     const int num = 10;
    588     Graph g;
    589     std::vector<Item> items;
    590     for (int i = 0; i < num; ++i) {
    591       items.push_back(g.addNode());
    592     }
    593 
    594     Iim map1(g);
    595     check(map1.size() == 0, "Wrong size");
    596 
    597     for (int i = 0; i < num; ++i) {
    598       map1[items[i]] = i;
    599     }
    600     check(map1.size() == num, "Wrong size");
    601 
    602     for (int i = 0; i < num; ++i) {
    603       Iim::ItemIt it(map1, i);
    604       check(static_cast<Item>(it) == items[i], "Wrong value");
    605       ++it;
    606       check(static_cast<Item>(it) == INVALID, "Wrong value");
    607     }
    608 
    609     for (int i = 0; i < num; ++i) {
    610       map1[items[i]] = i % 2;
    611     }
    612     check(map1.size() == 2, "Wrong size");
    613 
    614     int n = 0;
    615     for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
    616       check(map1[static_cast<Item>(it)] == 0, "Wrong value");
    617       ++n;
    618     }
    619     check(n == (num + 1) / 2, "Wrong number");
    620 
    621     for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
    622       check(map1[static_cast<Item>(it)] == 1, "Wrong value");
    623       ++n;
    624     }
    625     check(n == num, "Wrong number");
    626 
    627   }
    628 
    629   // Iterable value map
    630   {
    631     typedef SmartGraph Graph;
    632     typedef SmartGraph::Node Item;
    633     typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
    634 
    635     checkConcept<ReadWriteMap<Item, double>, Ivm>();
    636 
    637     const int num = 10;
    638     Graph g;
    639     std::vector<Item> items;
    640     for (int i = 0; i < num; ++i) {
    641       items.push_back(g.addNode());
    642     }
    643 
    644     Ivm map1(g, 0.0);
    645     check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
    646     check(*map1.beginValue() == 0.0, "Wrong value");
    647 
    648     for (int i = 0; i < num; ++i) {
    649       map1.set(items[i], static_cast<double>(i));
    650     }
    651     check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
    652 
    653     for (int i = 0; i < num; ++i) {
    654       Ivm::ItemIt it(map1, static_cast<double>(i));
    655       check(static_cast<Item>(it) == items[i], "Wrong value");
    656       ++it;
    657       check(static_cast<Item>(it) == INVALID, "Wrong value");
    658     }
    659 
    660     for (Ivm::ValueIterator vit = map1.beginValue();
    661          vit != map1.endValue(); ++vit) {
    662       check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
    663             "Wrong ValueIterator");
    664     }
    665 
    666     for (int i = 0; i < num; ++i) {
    667       map1.set(items[i], static_cast<double>(i % 2));
    668     }
    669     check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
    670 
    671     int n = 0;
    672     for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
    673       check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
    674       ++n;
    675     }
    676     check(n == (num + 1) / 2, "Wrong number");
    677 
    678     for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
    679       check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
    680       ++n;
    681     }
    682     check(n == num, "Wrong number");
    683 
    684   }
    685497  return 0;
    686498}
Note: See TracChangeset for help on using the changeset viewer.