COIN-OR::LEMON - Graph Library

Changeset 740:7bda7860e0a8 in lemon


Ignore:
Timestamp:
06/27/09 13:07:26 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Port iterable maps from SVN 3509 (#73)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

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

    r554 r740  
    350350  }
    351351
     352  // Iterable bool map
     353  {
     354    typedef SmartGraph Graph;
     355    typedef SmartGraph::Node Item;
     356
     357    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
     358    checkConcept<ReadWriteMap<Item, int>, Ibm>();
     359
     360    const int num = 10;
     361    Graph g;
     362    std::vector<Item> items;
     363    for (int i = 0; i < num; ++i) {
     364      items.push_back(g.addNode());
     365    }
     366
     367    Ibm map1(g, true);
     368    int n = 0;
     369    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     370      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
     371      ++n;
     372    }
     373    check(n == num, "Wrong number");
     374
     375    n = 0;
     376    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     377        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     378        ++n;
     379    }
     380    check(n == num, "Wrong number");
     381    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
     382    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
     383
     384    map1[items[5]] = true;
     385
     386    n = 0;
     387    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     388        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     389        ++n;
     390    }
     391    check(n == num, "Wrong number");
     392
     393    map1[items[num / 2]] = false;
     394    check(map1[items[num / 2]] == false, "Wrong map value");
     395
     396    n = 0;
     397    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     398        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     399        ++n;
     400    }
     401    check(n == num - 1, "Wrong number");
     402
     403    n = 0;
     404    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     405        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     406        ++n;
     407    }
     408    check(n == 1, "Wrong number");
     409
     410    map1[items[0]] = false;
     411    check(map1[items[0]] == false, "Wrong map value");
     412
     413    map1[items[num - 1]] = false;
     414    check(map1[items[num - 1]] == false, "Wrong map value");
     415
     416    n = 0;
     417    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     418        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     419        ++n;
     420    }
     421    check(n == num - 3, "Wrong number");
     422    check(map1.trueNum() == num - 3, "Wrong number");
     423
     424    n = 0;
     425    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     426        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     427        ++n;
     428    }
     429    check(n == 3, "Wrong number");
     430    check(map1.falseNum() == 3, "Wrong number");
     431  }
     432
     433  // Iterable int map
     434  {
     435    typedef SmartGraph Graph;
     436    typedef SmartGraph::Node Item;
     437    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
     438
     439    checkConcept<ReadWriteMap<Item, int>, Iim>();
     440
     441    const int num = 10;
     442    Graph g;
     443    std::vector<Item> items;
     444    for (int i = 0; i < num; ++i) {
     445      items.push_back(g.addNode());
     446    }
     447
     448    Iim map1(g);
     449    check(map1.size() == 0, "Wrong size");
     450
     451    for (int i = 0; i < num; ++i) {
     452      map1[items[i]] = i;
     453    }
     454    check(map1.size() == num, "Wrong size");
     455
     456    for (int i = 0; i < num; ++i) {
     457      Iim::ItemIt it(map1, i);
     458      check(static_cast<Item>(it) == items[i], "Wrong value");
     459      ++it;
     460      check(static_cast<Item>(it) == INVALID, "Wrong value");
     461    }
     462
     463    for (int i = 0; i < num; ++i) {
     464      map1[items[i]] = i % 2;
     465    }
     466    check(map1.size() == 2, "Wrong size");
     467
     468    int n = 0;
     469    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
     470      check(map1[static_cast<Item>(it)] == 0, "Wrong Value");
     471      ++n;
     472    }
     473    check(n == (num + 1) / 2, "Wrong number");
     474
     475    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
     476      check(map1[static_cast<Item>(it)] == 1, "Wrong Value");
     477      ++n;
     478    }
     479    check(n == num, "Wrong number");
     480
     481  }
     482
     483  // Iterable value map
     484  {
     485    typedef SmartGraph Graph;
     486    typedef SmartGraph::Node Item;
     487    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
     488
     489    checkConcept<ReadWriteMap<Item, double>, Ivm>();
     490
     491    const int num = 10;
     492    Graph g;
     493    std::vector<Item> items;
     494    for (int i = 0; i < num; ++i) {
     495      items.push_back(g.addNode());
     496    }
     497
     498    Ivm map1(g, 0.0);
     499    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
     500    check(*map1.beginValue() == 0.0, "Wrong value");
     501
     502    for (int i = 0; i < num; ++i) {
     503      map1.set(items[i], static_cast<double>(i));
     504    }
     505    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
     506
     507    for (int i = 0; i < num; ++i) {
     508      Ivm::ItemIt it(map1, static_cast<double>(i));
     509      check(static_cast<Item>(it) == items[i], "Wrong value");
     510      ++it;
     511      check(static_cast<Item>(it) == INVALID, "Wrong value");
     512    }
     513
     514    for (Ivm::ValueIterator vit = map1.beginValue();
     515         vit != map1.endValue(); ++vit) {
     516      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
     517            "Wrong ValueIterator");
     518    }
     519
     520    for (int i = 0; i < num; ++i) {
     521      map1.set(items[i], static_cast<double>(i % 2));
     522    }
     523    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
     524
     525    int n = 0;
     526    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
     527      check(map1[static_cast<Item>(it)] == 0.0, "Wrong Value");
     528      ++n;
     529    }
     530    check(n == (num + 1) / 2, "Wrong number");
     531
     532    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
     533      check(map1[static_cast<Item>(it)] == 1.0, "Wrong Value");
     534      ++n;
     535    }
     536    check(n == num, "Wrong number");
     537
     538  }
    352539  return 0;
    353540}
Note: See TracChangeset for help on using the changeset viewer.