Changeset 768:99124ea4f048 in lemon for lemon/maps.h
- Timestamp:
- 08/02/09 13:44:45 (15 years ago)
- Branch:
- default
- Parents:
- 767:6e8c27ee9079 (diff), 741:71939d63ae77 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r741 r768 1826 1826 /// the items stored in the graph, which is returned by the \c id() 1827 1827 /// function of the graph. This map can be inverted with its member 1828 /// class \c InverseMap or with the \c operator() member.1828 /// class \c InverseMap or with the \c operator()() member. 1829 1829 /// 1830 1830 /// \tparam GR The graph type. … … 1902 1902 1903 1903 /// This class provides simple invertable graph maps. 1904 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" 1905 /// and if a key is set to a new value then store it 1906 /// in the inverse map. 1904 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) 1905 /// and if a key is set to a new value, then stores it in the inverse map. 1907 1906 /// The values of the map can be accessed 1908 1907 /// with stl compatible forward iterator. 1909 1908 /// 1910 1909 /// This type is not reference map, so it cannot be modified with 1911 /// the subscript ionoperator.1910 /// the subscript operator. 1912 1911 /// 1913 1912 /// \tparam GR The graph type. … … 1925 1924 template Map<V>::Type Map; 1926 1925 1927 typedef std::m ap<V, K> Container;1926 typedef std::multimap<V, K> Container; 1928 1927 Container _inv_map; 1929 1928 … … 1950 1949 /// iterator on the values of the map. The values can 1951 1950 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1951 /// They are considered with multiplicity, so each value is 1952 /// traversed for each item it is assigned to. 1952 1953 class ValueIterator 1953 1954 : public std::iterator<std::forward_iterator_tag, Value> { … … 2002 2003 void set(const Key& key, const Value& val) { 2003 2004 Value oldval = Map::operator[](key); 2004 typename Container::iterator it = _inv_map.find(oldval); 2005 if (it != _inv_map.end() && it->second == key) { 2006 _inv_map.erase(it); 2005 typename Container::iterator it; 2006 for (it = _inv_map.equal_range(oldval).first; 2007 it != _inv_map.equal_range(oldval).second; ++it) { 2008 if (it->second == key) { 2009 _inv_map.erase(it); 2010 break; 2011 } 2007 2012 } 2008 2013 _inv_map.insert(std::make_pair(val, key)); … … 2018 2023 } 2019 2024 2020 /// \brief Gives back the item by its value. 2021 /// 2022 /// Gives back the item by its value. 2023 Key operator()(const Value& key) const { 2024 typename Container::const_iterator it = _inv_map.find(key); 2025 /// \brief Gives back an item by its value. 2026 /// 2027 /// This function gives back an item that is assigned to 2028 /// the given value or \c INVALID if no such item exists. 2029 /// If there are more items with the same associated value, 2030 /// only one of them is returned. 2031 Key operator()(const Value& val) const { 2032 typename Container::const_iterator it = _inv_map.find(val); 2025 2033 return it != _inv_map.end() ? it->second : INVALID; 2034 } 2035 2036 /// \brief Returns the number of items with the given value. 2037 /// 2038 /// This function returns the number of items with the given value 2039 /// associated with it. 2040 int count(const Value &val) const { 2041 return _inv_map.count(val); 2026 2042 } 2027 2043 … … 2034 2050 virtual void erase(const Key& key) { 2035 2051 Value val = Map::operator[](key); 2036 typename Container::iterator it = _inv_map.find(val); 2037 if (it != _inv_map.end() && it->second == key) { 2038 _inv_map.erase(it); 2052 typename Container::iterator it; 2053 for (it = _inv_map.equal_range(val).first; 2054 it != _inv_map.equal_range(val).second; ++it) { 2055 if (it->second == key) { 2056 _inv_map.erase(it); 2057 break; 2058 } 2039 2059 } 2040 2060 Map::erase(key); … … 2048 2068 for (int i = 0; i < int(keys.size()); ++i) { 2049 2069 Value val = Map::operator[](keys[i]); 2050 typename Container::iterator it = _inv_map.find(val); 2051 if (it != _inv_map.end() && it->second == keys[i]) { 2052 _inv_map.erase(it); 2070 typename Container::iterator it; 2071 for (it = _inv_map.equal_range(val).first; 2072 it != _inv_map.equal_range(val).second; ++it) { 2073 if (it->second == keys[i]) { 2074 _inv_map.erase(it); 2075 break; 2076 } 2053 2077 } 2054 2078 } … … 2086 2110 /// \brief Subscript operator. 2087 2111 /// 2088 /// Subscript operator. It gives back the item 2089 /// that was last assigned to the given value. 2112 /// Subscript operator. It gives back an item 2113 /// that is assigned to the given value or \c INVALID 2114 /// if no such item exists. 2090 2115 Value operator[](const Key& key) const { 2091 2116 return _inverted(key); … … 2105 2130 }; 2106 2131 2107 /// \brief Provides continuous and unique IDfor the2132 /// \brief Provides continuous and unique id for the 2108 2133 /// items of a graph. 2109 2134 /// 2110 2135 /// RangeIdMap provides a unique and continuous 2111 /// IDfor each item of a given type (\c Node, \c Arc or2136 /// id for each item of a given type (\c Node, \c Arc or 2112 2137 /// \c Edge) in a graph. This id is 2113 2138 /// - \b unique: different items get different ids, … … 2120 2145 /// the \c id() function of the graph or \ref IdMap. 2121 2146 /// This map can be inverted with its member class \c InverseMap, 2122 /// or with the \c operator() member.2147 /// or with the \c operator()() member. 2123 2148 /// 2124 2149 /// \tparam GR The graph type. -
lemon/maps.h
r767 r768 23 23 #include <functional> 24 24 #include <vector> 25 #include <map> 25 26 26 27 #include <lemon/core.h> … … 29 30 ///\ingroup maps 30 31 ///\brief Miscellaneous property maps 31 32 #include <map>33 32 34 33 namespace lemon { … … 1819 1818 /// 1820 1819 /// IdMap provides a unique and immutable id for each item of the 1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1820 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1822 1821 /// - \b unique: different items get different ids, 1823 1822 /// - \b immutable: the id of an item does not change (even if you … … 2282 2281 2283 2282 /// \brief Gives back the item belonging to a \e RangeId 2284 /// 2283 /// 2285 2284 /// Gives back the item belonging to a \e RangeId. 2286 2285 Item operator()(int id) const { … … 2339 2338 }; 2340 2339 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 2341 3237 /// \brief Map of the source nodes of arcs in a digraph. 2342 3238 /// … … 2508 3404 /// whenever the digraph changes. 2509 3405 /// 2510 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3406 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2511 3407 /// may provide alternative ways to modify the digraph. 2512 3408 /// The correct behavior of InDegMap is not guarantied if these additional … … 2524 3420 2525 3421 public: 2526 3422 2527 3423 /// The graph type of InDegMap 2528 3424 typedef GR Graph; … … 2638 3534 /// whenever the digraph changes. 2639 3535 /// 2640 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3536 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2641 3537 /// may provide alternative ways to modify the digraph. 2642 3538 /// The correct behavior of OutDegMap is not guarantied if these additional
Note: See TracChangeset
for help on using the changeset viewer.