Changeset 694:71939d63ae77 in lemon-main
- Timestamp:
- 07/21/09 22:43:31 (15 years ago)
- Branch:
- default
- Children:
- 695:8dae88c5943e, 721:99124ea4f048
- Phase:
- public
- Files:
-
- 2 edited
-
lemon/maps.h (modified) (32 diffs)
-
test/maps_test.cc (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r693 r694 23 23 #include <functional> 24 24 #include <vector> 25 #include <map> 25 26 26 27 #include <lemon/core.h> 27 #include <lemon/smart_graph.h>28 28 29 29 ///\file 30 30 ///\ingroup maps 31 31 ///\brief Miscellaneous property maps 32 33 #include <map>34 32 35 33 namespace lemon { … … 1907 1905 /// and if a key is set to a new value then store it 1908 1906 /// in the inverse map. 1909 ///1910 1907 /// The values of the map can be accessed 1911 1908 /// with stl compatible forward iterator. 1909 /// 1910 /// This type is not reference map, so it cannot be modified with 1911 /// the subscription operator. 1912 1912 /// 1913 1913 /// \tparam GR The graph type. … … 2313 2313 }; 2314 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> 2315 /// \brief Dynamic iterable \c bool map. 2316 /// 2317 /// This class provides a special graph map type which can store a 2318 /// \c bool value for graph items (\c Node, \c Arc or \c Edge). 2319 /// For both \c true and \c false values it is possible to iterate on 2320 /// the keys. 2321 /// 2322 /// This type is a reference map, so it can be modified with the 2323 /// subscription operator. 2324 /// 2325 /// \tparam GR The graph type. 2326 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2327 /// \c GR::Edge). 2328 /// 2329 /// \see IterableIntMap, IterableValueMap 2330 /// \see CrossRefMap 2331 template <typename GR, typename K> 2325 2332 class IterableBoolMap 2326 : protected ItemSetTraits<GR, ITEM>::template Map<int>::Type {2333 : protected ItemSetTraits<GR, K>::template Map<int>::Type { 2327 2334 private: 2328 2335 typedef GR Graph; 2329 2336 2330 typedef typename ItemSetTraits<G raph, ITEM>::ItemIt KeyIt;2331 typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent;2332 2333 std::vector< ITEM> _array;2337 typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt; 2338 typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent; 2339 2340 std::vector<K> _array; 2334 2341 int _sep; 2335 2342 2336 2343 public: 2337 2344 2338 /// Indicates that the map i freference map.2345 /// Indicates that the map is reference map. 2339 2346 typedef True ReferenceMapTag; 2340 2347 2341 2348 /// The key type 2342 typedef ITEMKey;2349 typedef K Key; 2343 2350 /// The value type 2344 2351 typedef bool Value; … … 2354 2361 public: 2355 2362 2356 /// \brief Refer nce to the value of the map.2357 /// 2358 /// This class is similar to the bool type. It can be converted to2359 /// bool and it provides the same operators.2363 /// \brief Reference to the value of the map. 2364 /// 2365 /// This class is similar to the \c bool type. It can be converted to 2366 /// \c bool and it provides the same operators. 2360 2367 class Reference { 2361 2368 friend class IterableBoolMap; … … 2455 2462 } 2456 2463 2457 /// \brief Returns the number of the keys mapped to true.2458 /// 2459 /// Returns the number of the keys mapped to true.2464 /// \brief Returns the number of the keys mapped to \c true. 2465 /// 2466 /// Returns the number of the keys mapped to \c true. 2460 2467 int trueNum() const { 2461 2468 return _sep; 2462 2469 } 2463 2470 2464 /// \brief Returns the number of the keys mapped to false.2465 /// 2466 /// Returns the number of the keys mapped to false.2471 /// \brief Returns the number of the keys mapped to \c false. 2472 /// 2473 /// Returns the number of the keys mapped to \c false. 2467 2474 int falseNum() const { 2468 2475 return _array.size() - _sep; 2469 2476 } 2470 2477 2471 /// \brief Iterator for the keys mapped to true.2472 /// 2473 /// Iterator for the keys mapped to true. It works2474 /// like a graph item iterator in the map, it can be converted2478 /// \brief Iterator for the keys mapped to \c true. 2479 /// 2480 /// Iterator for the keys mapped to \c true. It works 2481 /// like a graph item iterator, it can be converted to 2475 2482 /// the key type of the map, incremented with \c ++ operator, and 2476 /// if the iterator leave the last valid keyit will be equal to2483 /// if the iterator leaves the last valid key, it will be equal to 2477 2484 /// \c INVALID. 2478 2485 class TrueIt : public Key { … … 2483 2490 /// 2484 2491 /// Creates an iterator. It iterates on the 2485 /// keys which mapped totrue.2486 /// \param map The Iterable IntMap2492 /// keys mapped to \c true. 2493 /// \param map The IterableBoolMap. 2487 2494 explicit TrueIt(const IterableBoolMap& map) 2488 2495 : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), … … 2491 2498 /// \brief Invalid constructor \& conversion. 2492 2499 /// 2493 /// This constructor initializes the keyto be invalid.2500 /// This constructor initializes the iterator to be invalid. 2494 2501 /// \sa Invalid for more details. 2495 2502 TrueIt(Invalid) : Parent(INVALID), _map(0) {} … … 2497 2504 /// \brief Increment operator. 2498 2505 /// 2499 /// Increment Operator.2506 /// Increment operator. 2500 2507 TrueIt& operator++() { 2501 2508 int pos = _map->position(*this); … … 2504 2511 } 2505 2512 2506 2507 2513 private: 2508 2514 const IterableBoolMap* _map; 2509 2515 }; 2510 2516 2511 /// \brief Iterator for the keys mapped to false.2512 /// 2513 /// Iterator for the keys mapped to false. It works2514 /// like a graph item iterator in the map, it can be converted2517 /// \brief Iterator for the keys mapped to \c false. 2518 /// 2519 /// Iterator for the keys mapped to \c false. It works 2520 /// like a graph item iterator, it can be converted to 2515 2521 /// the key type of the map, incremented with \c ++ operator, and 2516 /// if the iterator leave the last valid keyit will be equal to2522 /// if the iterator leaves the last valid key, it will be equal to 2517 2523 /// \c INVALID. 2518 2524 class FalseIt : public Key { … … 2523 2529 /// 2524 2530 /// Creates an iterator. It iterates on the 2525 /// keys which mapped tofalse.2526 /// \param map The Iterable IntMap2531 /// keys mapped to \c false. 2532 /// \param map The IterableBoolMap. 2527 2533 explicit FalseIt(const IterableBoolMap& map) 2528 2534 : Parent(map._sep < int(map._array.size()) ? … … 2531 2537 /// \brief Invalid constructor \& conversion. 2532 2538 /// 2533 /// This constructor initializes the keyto be invalid.2539 /// This constructor initializes the iterator to be invalid. 2534 2540 /// \sa Invalid for more details. 2535 2541 FalseIt(Invalid) : Parent(INVALID), _map(0) {} … … 2537 2543 /// \brief Increment operator. 2538 2544 /// 2539 /// Increment Operator.2545 /// Increment operator. 2540 2546 FalseIt& operator++() { 2541 2547 int pos = _map->position(*this); … … 2551 2557 /// 2552 2558 /// Iterator for the keys mapped to a given value. It works 2553 /// like a graph item iterator in the map, it can be converted2559 /// like a graph item iterator, it can be converted to 2554 2560 /// the key type of the map, incremented with \c ++ operator, and 2555 /// if the iterator leave the last valid keyit will be equal to2561 /// if the iterator leaves the last valid key, it will be equal to 2556 2562 /// \c INVALID. 2557 2563 class ItemIt : public Key { … … 2559 2565 typedef Key Parent; 2560 2566 2561 /// \brief Creates an iterator .2567 /// \brief Creates an iterator with a value. 2562 2568 /// 2563 /// Creates an iterator . It iterates on the2564 /// keys which mapped to false.2565 /// \param map The Iterable IntMap2566 /// \param value Which elements should be iterated.2569 /// Creates an iterator with a value. It iterates on the 2570 /// keys mapped to the given value. 2571 /// \param map The IterableBoolMap. 2572 /// \param value The value. 2567 2573 ItemIt(const IterableBoolMap& map, bool value) 2568 2574 : Parent(value ? … … 2574 2580 /// \brief Invalid constructor \& conversion. 2575 2581 /// 2576 /// This constructor initializes the keyto be invalid.2582 /// This constructor initializes the iterator to be invalid. 2577 2583 /// \sa Invalid for more details. 2578 2584 ItemIt(Invalid) : Parent(INVALID), _map(0) {} … … 2580 2586 /// \brief Increment operator. 2581 2587 /// 2582 /// Increment Operator.2588 /// Increment operator. 2583 2589 ItemIt& operator++() { 2584 2590 int pos = _map->position(*this); … … 2674 2680 } 2675 2681 2676 ///\ingroup graph_maps2677 ///2678 2682 /// \brief Dynamic iterable integer map. 2679 2683 /// 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 2684 /// This class provides a special graph map type which can store an 2685 /// integer value for graph items (\c Node, \c Arc or \c Edge). 2686 /// For each non-negative value it is possible to iterate on the keys 2687 /// mapped to the value. 2688 /// 2689 /// This type is a reference map, so it can be modified with the 2690 /// subscription operator. 2691 /// 2692 /// \note The size of the data structure depends on the largest 2686 2693 /// value in the map. 2687 2694 /// 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> 2695 /// \tparam GR The graph type. 2696 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2697 /// \c GR::Edge). 2698 /// 2699 /// \see IterableBoolMap, IterableValueMap 2700 /// \see CrossRefMap 2701 template <typename GR, typename K> 2691 2702 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;2703 : protected ItemSetTraits<GR, K>:: 2704 template Map<_maps_bits::IterableIntMapNode<K> >::Type { 2705 public: 2706 typedef typename ItemSetTraits<GR, K>:: 2707 template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent; 2697 2708 2698 2709 /// The key type 2699 typedef ITEMKey;2710 typedef K Key; 2700 2711 /// The value type 2701 2712 typedef int Value; … … 2705 2716 /// \brief Constructor of the map. 2706 2717 /// 2707 /// Constructor of the map. It set all values to -1.2718 /// Constructor of the map. It sets all values to -1. 2708 2719 explicit IterableIntMap(const Graph& graph) 2709 2720 : Parent(graph) {} … … 2713 2724 /// Constructor of the map with a given value. 2714 2725 explicit IterableIntMap(const Graph& graph, int value) 2715 : Parent(graph, _maps_bits::IterableIntMapNode< ITEM>(value)) {2726 : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) { 2716 2727 if (value >= 0) { 2717 2728 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { … … 2755 2766 public: 2756 2767 2757 /// Indicates that the map i freference map.2768 /// Indicates that the map is reference map. 2758 2769 typedef True ReferenceMapTag; 2759 2770 2760 /// \brief Refer nce to the value of the map.2761 /// 2762 /// This class is similar to the int type. It can2763 /// be converted to int and it has the same operators.2771 /// \brief Reference to the value of the map. 2772 /// 2773 /// This class is similar to the \c int type. It can 2774 /// be converted to \c int and it has the same operators. 2764 2775 class Reference { 2765 2776 friend class IterableIntMap; … … 2882 2893 /// 2883 2894 /// Iterator for the keys with the same value. It works 2884 /// like a graph item iterator in the map, it can be converted2895 /// like a graph item iterator, it can be converted to 2885 2896 /// the item type of the map, incremented with \c ++ operator, and 2886 /// if the iterator leave the last valid itemit will be equal to2897 /// if the iterator leaves the last valid item, it will be equal to 2887 2898 /// \c INVALID. 2888 class ItemIt : public ITEM{2899 class ItemIt : public Key { 2889 2900 public: 2890 typedef ITEMParent;2901 typedef Key Parent; 2891 2902 2892 2903 /// \brief Invalid constructor \& conversion. 2893 2904 /// 2894 /// This constructor initializes the ite mto be invalid.2905 /// This constructor initializes the iterator to be invalid. 2895 2906 /// \sa Invalid for more details. 2896 2907 ItemIt(Invalid) : Parent(INVALID), _map(0) {} … … 2899 2910 /// 2900 2911 /// Creates an iterator with a value. It iterates on the 2901 /// keys which havethe given value.2902 /// \param map The IterableIntMap 2903 /// \param value The value 2912 /// keys mapped to the given value. 2913 /// \param map The IterableIntMap. 2914 /// \param value The value. 2904 2915 ItemIt(const IterableIntMap& map, int value) : _map(&map) { 2905 2916 if (value < 0 || value >= int(_map->_first.size())) { … … 2912 2923 /// \brief Increment operator. 2913 2924 /// 2914 /// Increment Operator.2925 /// Increment operator. 2915 2926 ItemIt& operator++() { 2916 2927 Parent::operator=(_map->IterableIntMap::Parent:: … … 2919 2930 } 2920 2931 2921 2922 2932 private: 2923 2933 const IterableIntMap* _map; … … 2944 2954 2945 2955 private: 2946 std::vector< ITEM> _first;2956 std::vector<Key> _first; 2947 2957 }; 2948 2958 … … 2956 2966 } 2957 2967 2958 ///\ingroup graph_maps2959 ///2960 2968 /// \brief Dynamic iterable map for comparable values. 2961 2969 /// 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 2970 /// This class provides a special graph map type which can store an 2971 /// comparable value for graph items (\c Node, \c Arc or \c Edge). 2972 /// For each value it is possible to iterate on the keys mapped to 2973 /// the value. 2974 /// 2975 /// The map stores for each value a linked list with 2966 2976 /// the items which mapped to the value, and the values are stored 2967 2977 /// in balanced binary tree. The values of the map can be accessed 2968 2978 /// with stl compatible forward iterator. 2969 2979 /// 2970 /// This type is not reference map so it cannot be modified with2980 /// This type is not reference map, so it cannot be modified with 2971 2981 /// the subscription operator. 2972 2982 /// 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> 2983 /// \tparam GR The graph type. 2984 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or 2985 /// \c GR::Edge). 2986 /// \tparam V The value type of the map. It can be any comparable 2987 /// value type. 2988 /// 2989 /// \see IterableBoolMap, IterableIntMap 2990 /// \see CrossRefMap 2991 template <typename GR, typename K, typename V> 2979 2992 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;2993 : protected ItemSetTraits<GR, K>:: 2994 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type { 2995 public: 2996 typedef typename ItemSetTraits<GR, K>:: 2997 template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent; 2985 2998 2986 2999 /// The key type 2987 typedef ITEMKey;3000 typedef K Key; 2988 3001 /// The value type 2989 typedef V ALValue;3002 typedef V Value; 2990 3003 /// The graph type 2991 3004 typedef GR Graph; … … 2993 3006 public: 2994 3007 2995 /// \brief Constructor of the Map with a given value.2996 /// 2997 /// Constructor of the Map with a given value.3008 /// \brief Constructor of the map with a given value. 3009 /// 3010 /// Constructor of the map with a given value. 2998 3011 explicit IterableValueMap(const Graph& graph, 2999 3012 const Value& value = Value()) 3000 : Parent(graph, _maps_bits::IterableValueMapNode< ITEM, VAL>(value)) {3013 : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) { 3001 3014 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { 3002 3015 lace(it); … … 3027 3040 if (it == _first.end()) { 3028 3041 node.prev = node.next = INVALID; 3029 if (node.next != INVALID) {3030 Parent::operator[](node.next).prev = key;3031 }3032 3042 _first.insert(std::make_pair(node.value, key)); 3033 3043 } else { … … 3047 3057 /// This iterator is an stl compatible forward 3048 3058 /// iterator on the values of the map. The values can 3049 /// be accessed in the [beginValue, endValue) range. 3050 /// 3059 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 3051 3060 class ValueIterator 3052 3061 : public std::iterator<std::forward_iterator_tag, Value> { … … 3080 3089 /// Returns an stl compatible iterator to the 3081 3090 /// first value of the map. The values of the 3082 /// map can be accessed in the [beginValue, endValue)3091 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3083 3092 /// range. 3084 3093 ValueIterator beginValue() const { … … 3090 3099 /// Returns an stl compatible iterator after the 3091 3100 /// last value of the map. The values of the 3092 /// map can be accessed in the [beginValue, endValue)3101 /// map can be accessed in the <tt>[beginValue, endValue)</tt> 3093 3102 /// range. 3094 3103 ValueIterator endValue() const { … … 3115 3124 /// 3116 3125 /// Iterator for the keys with the same value. It works 3117 /// like a graph item iterator in the map, it can be converted3126 /// like a graph item iterator, it can be converted to 3118 3127 /// the item type of the map, incremented with \c ++ operator, and 3119 /// if the iterator leave the last valid itemit will be equal to3128 /// if the iterator leaves the last valid item, it will be equal to 3120 3129 /// \c INVALID. 3121 class ItemIt : public ITEM{3130 class ItemIt : public Key { 3122 3131 public: 3123 typedef ITEMParent;3132 typedef Key Parent; 3124 3133 3125 3134 /// \brief Invalid constructor \& conversion. 3126 3135 /// 3127 /// This constructor initializes the ite mto be invalid.3136 /// This constructor initializes the iterator to be invalid. 3128 3137 /// \sa Invalid for more details. 3129 3138 ItemIt(Invalid) : Parent(INVALID), _map(0) {} -
test/maps_test.cc
r693 r694 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/smart_graph.h> 25 26 26 27 #include "test_tools.h" … … 356 357 357 358 typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm; 358 checkConcept<Re adWriteMap<Item, int>, Ibm>();359 checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>(); 359 360 360 361 const int num = 10; … … 437 438 typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim; 438 439 439 checkConcept<Re adWriteMap<Item, int>, Iim>();440 checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>(); 440 441 441 442 const int num = 10; … … 468 469 int n = 0; 469 470 for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { 470 check(map1[static_cast<Item>(it)] == 0, "Wrong Value");471 check(map1[static_cast<Item>(it)] == 0, "Wrong value"); 471 472 ++n; 472 473 } … … 474 475 475 476 for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { 476 check(map1[static_cast<Item>(it)] == 1, "Wrong Value");477 check(map1[static_cast<Item>(it)] == 1, "Wrong value"); 477 478 ++n; 478 479 } … … 525 526 int n = 0; 526 527 for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { 527 check(map1[static_cast<Item>(it)] == 0.0, "Wrong Value");528 check(map1[static_cast<Item>(it)] == 0.0, "Wrong value"); 528 529 ++n; 529 530 } … … 531 532 532 533 for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { 533 check(map1[static_cast<Item>(it)] == 1.0, "Wrong Value");534 check(map1[static_cast<Item>(it)] == 1.0, "Wrong value"); 534 535 ++n; 535 536 }
Note: See TracChangeset
for help on using the changeset viewer.
