2336 const InverseMap inverse() const { |
2335 const InverseMap inverse() const { |
2337 return InverseMap(*this); |
2336 return InverseMap(*this); |
2338 } |
2337 } |
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 /// \brief Map of the source nodes of arcs in a digraph. |
3237 /// \brief Map of the source nodes of arcs in a digraph. |
2342 /// |
3238 /// |
2343 /// SourceMap provides access for the source node of each arc in a digraph, |
3239 /// SourceMap provides access for the source node of each arc in a digraph, |
2344 /// which is returned by the \c source() function of the digraph. |
3240 /// which is returned by the \c source() function of the digraph. |
2345 /// \tparam GR The digraph type. |
3241 /// \tparam GR The digraph type. |