Changes in / [720:6e8c27ee9079:721:99124ea4f048] in lemon-1.2
- Files:
-
- 3 added
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r667 r681 60 60 lemon/bfs.h \ 61 61 lemon/bin_heap.h \ 62 lemon/bucket_heap.h \ 62 63 lemon/cbc.h \ 63 64 lemon/circulation.h \ … … 77 78 lemon/error.h \ 78 79 lemon/euler.h \ 80 lemon/fib_heap.h \ 79 81 lemon/full_graph.h \ 80 82 lemon/glpk.h \ … … 100 102 lemon/path.h \ 101 103 lemon/preflow.h \ 104 lemon/radix_heap.h \ 102 105 lemon/radix_sort.h \ 103 106 lemon/random.h \ -
lemon/bin_heap.h
r584 r683 34 34 ///\brief A Binary Heap implementation. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 38 38 ///A \e heap is a data structure for storing items with specified values 39 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c C ompspecifies the ordering of the priorities.40 ///priority is efficient. \c CMP specifies the ordering of the priorities. 41 41 ///In a heap one can change the priority of an item, add or erase an 42 42 ///item, etc. … … 45 45 ///\tparam IM A read and writable item map with int values, used internally 46 46 ///to handle the cross references. 47 ///\tparam C ompA functor class for the ordering of the priorities.47 ///\tparam CMP A functor class for the ordering of the priorities. 48 48 ///The default is \c std::less<PR>. 49 49 /// 50 50 ///\sa FibHeap 51 51 ///\sa Dijkstra 52 template <typename PR, typename IM, typename C omp= std::less<PR> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 53 class BinHeap { 54 54 … … 63 63 typedef std::pair<Item,Prio> Pair; 64 64 ///\e 65 typedef C ompCompare;65 typedef CMP Compare; 66 66 67 67 /// \brief Type to represent the items states. -
lemon/maps.h
r720 r721 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 -
test/heap_test.cc
r440 r681 32 32 33 33 #include <lemon/bin_heap.h> 34 #include <lemon/fib_heap.h> 35 #include <lemon/radix_heap.h> 36 #include <lemon/bucket_heap.h> 34 37 35 38 #include "test_tools.h" … … 184 187 } 185 188 189 { 190 typedef FibHeap<Prio, ItemIntMap> IntHeap; 191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 192 heapSortTest<IntHeap>(); 193 heapIncreaseTest<IntHeap>(); 194 195 typedef FibHeap<Prio, IntNodeMap > NodeHeap; 196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 197 dijkstraHeapTest<NodeHeap>(digraph, length, source); 198 } 199 200 { 201 typedef RadixHeap<ItemIntMap> IntHeap; 202 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 203 heapSortTest<IntHeap>(); 204 heapIncreaseTest<IntHeap>(); 205 206 typedef RadixHeap<IntNodeMap > NodeHeap; 207 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 208 dijkstraHeapTest<NodeHeap>(digraph, length, source); 209 } 210 211 { 212 typedef BucketHeap<ItemIntMap> IntHeap; 213 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 214 heapSortTest<IntHeap>(); 215 heapIncreaseTest<IntHeap>(); 216 217 typedef BucketHeap<IntNodeMap > NodeHeap; 218 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 219 dijkstraHeapTest<NodeHeap>(digraph, length, source); 220 } 221 222 186 223 return 0; 187 224 } -
test/maps_test.cc
r720 r721 24 24 #include <lemon/maps.h> 25 25 #include <lemon/list_graph.h> 26 #include <lemon/smart_graph.h> 26 27 27 28 #include "test_tools.h" … … 495 496 } 496 497 498 // Iterable bool map 499 { 500 typedef SmartGraph Graph; 501 typedef SmartGraph::Node Item; 502 503 typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm; 504 checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>(); 505 506 const int num = 10; 507 Graph g; 508 std::vector<Item> items; 509 for (int i = 0; i < num; ++i) { 510 items.push_back(g.addNode()); 511 } 512 513 Ibm map1(g, true); 514 int n = 0; 515 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 516 check(map1[static_cast<Item>(it)], "Wrong TrueIt"); 517 ++n; 518 } 519 check(n == num, "Wrong number"); 520 521 n = 0; 522 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 523 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 524 ++n; 525 } 526 check(n == num, "Wrong number"); 527 check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt"); 528 check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false"); 529 530 map1[items[5]] = true; 531 532 n = 0; 533 for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { 534 check(map1[static_cast<Item>(it)], "Wrong ItemIt for true"); 535 ++n; 536 } 537 check(n == num, "Wrong number"); 538 539 map1[items[num / 2]] = false; 540 check(map1[items[num / 2]] == false, "Wrong map value"); 541 542 n = 0; 543 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 544 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 545 ++n; 546 } 547 check(n == num - 1, "Wrong number"); 548 549 n = 0; 550 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 551 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 552 ++n; 553 } 554 check(n == 1, "Wrong number"); 555 556 map1[items[0]] = false; 557 check(map1[items[0]] == false, "Wrong map value"); 558 559 map1[items[num - 1]] = false; 560 check(map1[items[num - 1]] == false, "Wrong map value"); 561 562 n = 0; 563 for (Ibm::TrueIt it(map1); it != INVALID; ++it) { 564 check(map1[static_cast<Item>(it)], "Wrong TrueIt for true"); 565 ++n; 566 } 567 check(n == num - 3, "Wrong number"); 568 check(map1.trueNum() == num - 3, "Wrong number"); 569 570 n = 0; 571 for (Ibm::FalseIt it(map1); it != INVALID; ++it) { 572 check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true"); 573 ++n; 574 } 575 check(n == 3, "Wrong number"); 576 check(map1.falseNum() == 3, "Wrong number"); 577 } 578 579 // Iterable int map 580 { 581 typedef SmartGraph Graph; 582 typedef SmartGraph::Node Item; 583 typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim; 584 585 checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>(); 586 587 const int num = 10; 588 Graph g; 589 std::vector<Item> items; 590 for (int i = 0; i < num; ++i) { 591 items.push_back(g.addNode()); 592 } 593 594 Iim map1(g); 595 check(map1.size() == 0, "Wrong size"); 596 597 for (int i = 0; i < num; ++i) { 598 map1[items[i]] = i; 599 } 600 check(map1.size() == num, "Wrong size"); 601 602 for (int i = 0; i < num; ++i) { 603 Iim::ItemIt it(map1, i); 604 check(static_cast<Item>(it) == items[i], "Wrong value"); 605 ++it; 606 check(static_cast<Item>(it) == INVALID, "Wrong value"); 607 } 608 609 for (int i = 0; i < num; ++i) { 610 map1[items[i]] = i % 2; 611 } 612 check(map1.size() == 2, "Wrong size"); 613 614 int n = 0; 615 for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { 616 check(map1[static_cast<Item>(it)] == 0, "Wrong value"); 617 ++n; 618 } 619 check(n == (num + 1) / 2, "Wrong number"); 620 621 for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { 622 check(map1[static_cast<Item>(it)] == 1, "Wrong value"); 623 ++n; 624 } 625 check(n == num, "Wrong number"); 626 627 } 628 629 // Iterable value map 630 { 631 typedef SmartGraph Graph; 632 typedef SmartGraph::Node Item; 633 typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm; 634 635 checkConcept<ReadWriteMap<Item, double>, Ivm>(); 636 637 const int num = 10; 638 Graph g; 639 std::vector<Item> items; 640 for (int i = 0; i < num; ++i) { 641 items.push_back(g.addNode()); 642 } 643 644 Ivm map1(g, 0.0); 645 check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size"); 646 check(*map1.beginValue() == 0.0, "Wrong value"); 647 648 for (int i = 0; i < num; ++i) { 649 map1.set(items[i], static_cast<double>(i)); 650 } 651 check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size"); 652 653 for (int i = 0; i < num; ++i) { 654 Ivm::ItemIt it(map1, static_cast<double>(i)); 655 check(static_cast<Item>(it) == items[i], "Wrong value"); 656 ++it; 657 check(static_cast<Item>(it) == INVALID, "Wrong value"); 658 } 659 660 for (Ivm::ValueIterator vit = map1.beginValue(); 661 vit != map1.endValue(); ++vit) { 662 check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit, 663 "Wrong ValueIterator"); 664 } 665 666 for (int i = 0; i < num; ++i) { 667 map1.set(items[i], static_cast<double>(i % 2)); 668 } 669 check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size"); 670 671 int n = 0; 672 for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { 673 check(map1[static_cast<Item>(it)] == 0.0, "Wrong value"); 674 ++n; 675 } 676 check(n == (num + 1) / 2, "Wrong number"); 677 678 for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { 679 check(map1[static_cast<Item>(it)] == 1.0, "Wrong value"); 680 ++n; 681 } 682 check(n == num, "Wrong number"); 683 684 } 497 685 return 0; 498 686 }
Note: See TracChangeset
for help on using the changeset viewer.