Changes in lemon/maps.h [768:99124ea4f048:767:6e8c27ee9079] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r768 r767 23 23 #include <functional> 24 24 #include <vector> 25 #include <map>26 25 27 26 #include <lemon/core.h> … … 30 29 ///\ingroup maps 31 30 ///\brief Miscellaneous property maps 31 32 #include <map> 32 33 33 34 namespace lemon { … … 1818 1819 /// 1819 1820 /// IdMap provides a unique and immutable id for each item of the 1820 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 1821 1822 /// - \b unique: different items get different ids, 1822 1823 /// - \b immutable: the id of an item does not change (even if you … … 2281 2282 2282 2283 /// \brief Gives back the item belonging to a \e RangeId 2283 /// 2284 /// 2284 2285 /// Gives back the item belonging to a \e RangeId. 2285 2286 Item operator()(int id) const { … … 2338 2339 }; 2339 2340 2340 /// \brief Dynamic iterable \c bool map.2341 ///2342 /// This class provides a special graph map type which can store a2343 /// \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 on2345 /// the keys.2346 ///2347 /// This type is a reference map, so it can be modified with the2348 /// subscription operator.2349 ///2350 /// \tparam GR The graph type.2351 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or2352 /// \c GR::Edge).2353 ///2354 /// \see IterableIntMap, IterableValueMap2355 /// \see CrossRefMap2356 template <typename GR, typename K>2357 class IterableBoolMap2358 : 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 type2374 typedef K Key;2375 /// The value type2376 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 to2391 /// \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 works2506 /// like a graph item iterator, it can be converted to2507 /// the key type of the map, incremented with \c ++ operator, and2508 /// if the iterator leaves the last valid key, it will be equal to2509 /// \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 the2517 /// 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 works2545 /// like a graph item iterator, it can be converted to2546 /// the key type of the map, incremented with \c ++ operator, and2547 /// if the iterator leaves the last valid key, it will be equal to2548 /// \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 the2556 /// 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 works2584 /// like a graph item iterator, it can be converted to2585 /// the key type of the map, incremented with \c ++ operator, and2586 /// if the iterator leaves the last valid key, it will be equal to2587 /// \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 the2595 /// 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 an2710 /// 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 keys2712 /// mapped to the value.2713 ///2714 /// This type is a reference map, so it can be modified with the2715 /// subscription operator.2716 ///2717 /// \note The size of the data structure depends on the largest2718 /// 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 or2722 /// \c GR::Edge).2723 ///2724 /// \see IterableBoolMap, IterableValueMap2725 /// \see CrossRefMap2726 template <typename GR, typename K>2727 class IterableIntMap2728 : 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 type2735 typedef K Key;2736 /// The value type2737 typedef int Value;2738 /// The graph type2739 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 can2799 /// 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 works2920 /// like a graph item iterator, it can be converted to2921 /// the item type of the map, incremented with \c ++ operator, and2922 /// if the iterator leaves the last valid item, it will be equal to2923 /// \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 the2937 /// 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 an2996 /// 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 to2998 /// the value.2999 ///3000 /// The map stores for each value a linked list with3001 /// the items which mapped to the value, and the values are stored3002 /// in balanced binary tree. The values of the map can be accessed3003 /// with stl compatible forward iterator.3004 ///3005 /// This type is not reference map, so it cannot be modified with3006 /// 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 or3010 /// \c GR::Edge).3011 /// \tparam V The value type of the map. It can be any comparable3012 /// value type.3013 ///3014 /// \see IterableBoolMap, IterableIntMap3015 /// \see CrossRefMap3016 template <typename GR, typename K, typename V>3017 class IterableValueMap3018 : 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 type3025 typedef K Key;3026 /// The value type3027 typedef V Value;3028 /// The graph type3029 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 forward3083 /// iterator on the values of the map. The values can3084 /// be accessed in the <tt>[beginValue, endValue)</tt> range.3085 class ValueIterator3086 : 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 the3115 /// first value of the map. The values of the3116 /// 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 the3125 /// last value of the map. The values of the3126 /// 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 works3151 /// like a graph item iterator, it can be converted to3152 /// the item type of the map, incremented with \c ++ operator, and3153 /// if the iterator leaves the last valid item, it will be equal to3154 /// \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 the3168 /// keys which have the given value.3169 /// \param map The IterableValueMap3170 /// \param value The value3171 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 3237 2341 /// \brief Map of the source nodes of arcs in a digraph. 3238 2342 /// … … 3404 2508 /// whenever the digraph changes. 3405 2509 /// 3406 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2510 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3407 2511 /// may provide alternative ways to modify the digraph. 3408 2512 /// The correct behavior of InDegMap is not guarantied if these additional … … 3420 2524 3421 2525 public: 3422 2526 3423 2527 /// The graph type of InDegMap 3424 2528 typedef GR Graph; … … 3534 2638 /// whenever the digraph changes. 3535 2639 /// 3536 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 2640 /// \warning Besides \c addNode() and \c addArc(), a digraph structure 3537 2641 /// may provide alternative ways to modify the digraph. 3538 2642 /// The correct behavior of OutDegMap is not guarantied if these additional
Note: See TracChangeset
for help on using the changeset viewer.