Changeset 740:7bda7860e0a8 in lemon
- Timestamp:
- 06/27/09 13:07:26 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r664 r740 25 25 26 26 #include <lemon/core.h> 27 #include <lemon/smart_graph.h> 27 28 28 29 ///\file … … 1819 1820 /// 1820 1821 /// 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 1822 1823 /// - \b unique: different items get different ids, 1823 1824 /// - \b immutable: the id of an item does not change (even if you … … 2005 2006 _inv_map.erase(it); 2006 2007 } 2007 _inv_map.insert( make_pair(val, key));2008 _inv_map.insert(std::make_pair(val, key)); 2008 2009 Map::set(key, val); 2009 2010 } … … 2255 2256 2256 2257 /// \brief Gives back the item belonging to a \e RangeId 2257 /// 2258 /// 2258 2259 /// Gives back the item belonging to a \e RangeId. 2259 2260 Item operator()(int id) const { … … 2312 2313 }; 2313 2314 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 2314 3203 /// \brief Map of the source nodes of arcs in a digraph. 2315 3204 /// … … 2481 3370 /// whenever the digraph changes. 2482 3371 /// 2483 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3372 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2484 3373 /// may provide alternative ways to modify the digraph. 2485 3374 /// The correct behavior of InDegMap is not guarantied if these additional … … 2497 3386 2498 3387 public: 2499 3388 2500 3389 /// The graph type of InDegMap 2501 3390 typedef GR Graph; … … 2611 3500 /// whenever the digraph changes. 2612 3501 /// 2613 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3502 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2614 3503 /// may provide alternative ways to modify the digraph. 2615 3504 /// The correct behavior of OutDegMap is not guarantied if these additional -
test/maps_test.cc
r554 r740 350 350 } 351 351 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 } 352 539 return 0; 353 540 }
Note: See TracChangeset
for help on using the changeset viewer.