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
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.