2309 const InverseMap inverse() const { |
2310 const InverseMap inverse() const { |
2310 return InverseMap(*this); |
2311 return InverseMap(*this); |
2311 } |
2312 } |
2312 }; |
2313 }; |
2313 |
2314 |
|
2315 /// \brief Dynamic iterable bool map. |
|
2316 /// |
|
2317 /// This class provides a special graph map type which can store for |
|
2318 /// each graph item(node, arc, edge, etc.) a bool value. For both |
|
2319 /// the true and the false values it is possible to iterate on the |
|
2320 /// keys. |
|
2321 /// |
|
2322 /// \param GR The graph type. |
|
2323 /// \param ITEM One of the graph's item types, the key of the map. |
|
2324 template <typename GR, typename ITEM> |
|
2325 class IterableBoolMap |
|
2326 : protected ItemSetTraits<GR, ITEM>::template Map<int>::Type { |
|
2327 private: |
|
2328 typedef GR Graph; |
|
2329 |
|
2330 typedef typename ItemSetTraits<Graph, ITEM>::ItemIt KeyIt; |
|
2331 typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent; |
|
2332 |
|
2333 std::vector<ITEM> _array; |
|
2334 int _sep; |
|
2335 |
|
2336 public: |
|
2337 |
|
2338 /// Indicates that the map if reference map. |
|
2339 typedef True ReferenceMapTag; |
|
2340 |
|
2341 /// The key type |
|
2342 typedef ITEM Key; |
|
2343 /// The value type |
|
2344 typedef bool Value; |
|
2345 /// The const reference type. |
|
2346 typedef const Value& ConstReference; |
|
2347 |
|
2348 private: |
|
2349 |
|
2350 int position(const Key& key) const { |
|
2351 return Parent::operator[](key); |
|
2352 } |
|
2353 |
|
2354 public: |
|
2355 |
|
2356 /// \brief Refernce to the value of the map. |
|
2357 /// |
|
2358 /// This class is similar to the bool type. It can be converted to |
|
2359 /// bool and it provides the same operators. |
|
2360 class Reference { |
|
2361 friend class IterableBoolMap; |
|
2362 private: |
|
2363 Reference(IterableBoolMap& map, const Key& key) |
|
2364 : _key(key), _map(map) {} |
|
2365 public: |
|
2366 |
|
2367 Reference& operator=(const Reference& value) { |
|
2368 _map.set(_key, static_cast<bool>(value)); |
|
2369 return *this; |
|
2370 } |
|
2371 |
|
2372 operator bool() const { |
|
2373 return static_cast<const IterableBoolMap&>(_map)[_key]; |
|
2374 } |
|
2375 |
|
2376 Reference& operator=(bool value) { |
|
2377 _map.set(_key, value); |
|
2378 return *this; |
|
2379 } |
|
2380 Reference& operator&=(bool value) { |
|
2381 _map.set(_key, _map[_key] & value); |
|
2382 return *this; |
|
2383 } |
|
2384 Reference& operator|=(bool value) { |
|
2385 _map.set(_key, _map[_key] | value); |
|
2386 return *this; |
|
2387 } |
|
2388 Reference& operator^=(bool value) { |
|
2389 _map.set(_key, _map[_key] ^ value); |
|
2390 return *this; |
|
2391 } |
|
2392 private: |
|
2393 Key _key; |
|
2394 IterableBoolMap& _map; |
|
2395 }; |
|
2396 |
|
2397 /// \brief Constructor of the map with a default value. |
|
2398 /// |
|
2399 /// Constructor of the map with a default value. |
|
2400 explicit IterableBoolMap(const Graph& graph, bool def = false) |
|
2401 : Parent(graph) { |
|
2402 typename Parent::Notifier* nf = Parent::notifier(); |
|
2403 Key it; |
|
2404 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
2405 Parent::set(it, _array.size()); |
|
2406 _array.push_back(it); |
|
2407 } |
|
2408 _sep = (def ? _array.size() : 0); |
|
2409 } |
|
2410 |
|
2411 /// \brief Const subscript operator of the map. |
|
2412 /// |
|
2413 /// Const subscript operator of the map. |
|
2414 bool operator[](const Key& key) const { |
|
2415 return position(key) < _sep; |
|
2416 } |
|
2417 |
|
2418 /// \brief Subscript operator of the map. |
|
2419 /// |
|
2420 /// Subscript operator of the map. |
|
2421 Reference operator[](const Key& key) { |
|
2422 return Reference(*this, key); |
|
2423 } |
|
2424 |
|
2425 /// \brief Set operation of the map. |
|
2426 /// |
|
2427 /// Set operation of the map. |
|
2428 void set(const Key& key, bool value) { |
|
2429 int pos = position(key); |
|
2430 if (value) { |
|
2431 if (pos < _sep) return; |
|
2432 Key tmp = _array[_sep]; |
|
2433 _array[_sep] = key; |
|
2434 Parent::set(key, _sep); |
|
2435 _array[pos] = tmp; |
|
2436 Parent::set(tmp, pos); |
|
2437 ++_sep; |
|
2438 } else { |
|
2439 if (pos >= _sep) return; |
|
2440 --_sep; |
|
2441 Key tmp = _array[_sep]; |
|
2442 _array[_sep] = key; |
|
2443 Parent::set(key, _sep); |
|
2444 _array[pos] = tmp; |
|
2445 Parent::set(tmp, pos); |
|
2446 } |
|
2447 } |
|
2448 |
|
2449 /// \brief Set all items. |
|
2450 /// |
|
2451 /// Set all items in the map. |
|
2452 /// \note Constant time operation. |
|
2453 void setAll(bool value) { |
|
2454 _sep = (value ? _array.size() : 0); |
|
2455 } |
|
2456 |
|
2457 /// \brief Returns the number of the keys mapped to true. |
|
2458 /// |
|
2459 /// Returns the number of the keys mapped to true. |
|
2460 int trueNum() const { |
|
2461 return _sep; |
|
2462 } |
|
2463 |
|
2464 /// \brief Returns the number of the keys mapped to false. |
|
2465 /// |
|
2466 /// Returns the number of the keys mapped to false. |
|
2467 int falseNum() const { |
|
2468 return _array.size() - _sep; |
|
2469 } |
|
2470 |
|
2471 /// \brief Iterator for the keys mapped to true. |
|
2472 /// |
|
2473 /// Iterator for the keys mapped to true. It works |
|
2474 /// like a graph item iterator in the map, it can be converted |
|
2475 /// the key type of the map, incremented with \c ++ operator, and |
|
2476 /// if the iterator leave the last valid key it will be equal to |
|
2477 /// \c INVALID. |
|
2478 class TrueIt : public Key { |
|
2479 public: |
|
2480 typedef Key Parent; |
|
2481 |
|
2482 /// \brief Creates an iterator. |
|
2483 /// |
|
2484 /// Creates an iterator. It iterates on the |
|
2485 /// keys which mapped to true. |
|
2486 /// \param map The IterableIntMap |
|
2487 explicit TrueIt(const IterableBoolMap& map) |
|
2488 : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), |
|
2489 _map(&map) {} |
|
2490 |
|
2491 /// \brief Invalid constructor \& conversion. |
|
2492 /// |
|
2493 /// This constructor initializes the key to be invalid. |
|
2494 /// \sa Invalid for more details. |
|
2495 TrueIt(Invalid) : Parent(INVALID), _map(0) {} |
|
2496 |
|
2497 /// \brief Increment operator. |
|
2498 /// |
|
2499 /// Increment Operator. |
|
2500 TrueIt& operator++() { |
|
2501 int pos = _map->position(*this); |
|
2502 Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID); |
|
2503 return *this; |
|
2504 } |
|
2505 |
|
2506 |
|
2507 private: |
|
2508 const IterableBoolMap* _map; |
|
2509 }; |
|
2510 |
|
2511 /// \brief Iterator for the keys mapped to false. |
|
2512 /// |
|
2513 /// Iterator for the keys mapped to false. It works |
|
2514 /// like a graph item iterator in the map, it can be converted |
|
2515 /// the key type of the map, incremented with \c ++ operator, and |
|
2516 /// if the iterator leave the last valid key it will be equal to |
|
2517 /// \c INVALID. |
|
2518 class FalseIt : public Key { |
|
2519 public: |
|
2520 typedef Key Parent; |
|
2521 |
|
2522 /// \brief Creates an iterator. |
|
2523 /// |
|
2524 /// Creates an iterator. It iterates on the |
|
2525 /// keys which mapped to false. |
|
2526 /// \param map The IterableIntMap |
|
2527 explicit FalseIt(const IterableBoolMap& map) |
|
2528 : Parent(map._sep < int(map._array.size()) ? |
|
2529 map._array.back() : INVALID), _map(&map) {} |
|
2530 |
|
2531 /// \brief Invalid constructor \& conversion. |
|
2532 /// |
|
2533 /// This constructor initializes the key to be invalid. |
|
2534 /// \sa Invalid for more details. |
|
2535 FalseIt(Invalid) : Parent(INVALID), _map(0) {} |
|
2536 |
|
2537 /// \brief Increment operator. |
|
2538 /// |
|
2539 /// Increment Operator. |
|
2540 FalseIt& operator++() { |
|
2541 int pos = _map->position(*this); |
|
2542 Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID); |
|
2543 return *this; |
|
2544 } |
|
2545 |
|
2546 private: |
|
2547 const IterableBoolMap* _map; |
|
2548 }; |
|
2549 |
|
2550 /// \brief Iterator for the keys mapped to a given value. |
|
2551 /// |
|
2552 /// Iterator for the keys mapped to a given value. It works |
|
2553 /// like a graph item iterator in the map, it can be converted |
|
2554 /// the key type of the map, incremented with \c ++ operator, and |
|
2555 /// if the iterator leave the last valid key it will be equal to |
|
2556 /// \c INVALID. |
|
2557 class ItemIt : public Key { |
|
2558 public: |
|
2559 typedef Key Parent; |
|
2560 |
|
2561 /// \brief Creates an iterator. |
|
2562 /// |
|
2563 /// Creates an iterator. It iterates on the |
|
2564 /// keys which mapped to false. |
|
2565 /// \param map The IterableIntMap |
|
2566 /// \param value Which elements should be iterated. |
|
2567 ItemIt(const IterableBoolMap& map, bool value) |
|
2568 : Parent(value ? |
|
2569 (map._sep > 0 ? |
|
2570 map._array[map._sep - 1] : INVALID) : |
|
2571 (map._sep < int(map._array.size()) ? |
|
2572 map._array.back() : INVALID)), _map(&map) {} |
|
2573 |
|
2574 /// \brief Invalid constructor \& conversion. |
|
2575 /// |
|
2576 /// This constructor initializes the key to be invalid. |
|
2577 /// \sa Invalid for more details. |
|
2578 ItemIt(Invalid) : Parent(INVALID), _map(0) {} |
|
2579 |
|
2580 /// \brief Increment operator. |
|
2581 /// |
|
2582 /// Increment Operator. |
|
2583 ItemIt& operator++() { |
|
2584 int pos = _map->position(*this); |
|
2585 int _sep = pos >= _map->_sep ? _map->_sep : 0; |
|
2586 Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID); |
|
2587 return *this; |
|
2588 } |
|
2589 |
|
2590 private: |
|
2591 const IterableBoolMap* _map; |
|
2592 }; |
|
2593 |
|
2594 protected: |
|
2595 |
|
2596 virtual void add(const Key& key) { |
|
2597 Parent::add(key); |
|
2598 Parent::set(key, _array.size()); |
|
2599 _array.push_back(key); |
|
2600 } |
|
2601 |
|
2602 virtual void add(const std::vector<Key>& keys) { |
|
2603 Parent::add(keys); |
|
2604 for (int i = 0; i < int(keys.size()); ++i) { |
|
2605 Parent::set(keys[i], _array.size()); |
|
2606 _array.push_back(keys[i]); |
|
2607 } |
|
2608 } |
|
2609 |
|
2610 virtual void erase(const Key& key) { |
|
2611 int pos = position(key); |
|
2612 if (pos < _sep) { |
|
2613 --_sep; |
|
2614 Parent::set(_array[_sep], pos); |
|
2615 _array[pos] = _array[_sep]; |
|
2616 Parent::set(_array.back(), _sep); |
|
2617 _array[_sep] = _array.back(); |
|
2618 _array.pop_back(); |
|
2619 } else { |
|
2620 Parent::set(_array.back(), pos); |
|
2621 _array[pos] = _array.back(); |
|
2622 _array.pop_back(); |
|
2623 } |
|
2624 Parent::erase(key); |
|
2625 } |
|
2626 |
|
2627 virtual void erase(const std::vector<Key>& keys) { |
|
2628 for (int i = 0; i < int(keys.size()); ++i) { |
|
2629 int pos = position(keys[i]); |
|
2630 if (pos < _sep) { |
|
2631 --_sep; |
|
2632 Parent::set(_array[_sep], pos); |
|
2633 _array[pos] = _array[_sep]; |
|
2634 Parent::set(_array.back(), _sep); |
|
2635 _array[_sep] = _array.back(); |
|
2636 _array.pop_back(); |
|
2637 } else { |
|
2638 Parent::set(_array.back(), pos); |
|
2639 _array[pos] = _array.back(); |
|
2640 _array.pop_back(); |
|
2641 } |
|
2642 } |
|
2643 Parent::erase(keys); |
|
2644 } |
|
2645 |
|
2646 virtual void build() { |
|
2647 Parent::build(); |
|
2648 typename Parent::Notifier* nf = Parent::notifier(); |
|
2649 Key it; |
|
2650 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
2651 Parent::set(it, _array.size()); |
|
2652 _array.push_back(it); |
|
2653 } |
|
2654 _sep = 0; |
|
2655 } |
|
2656 |
|
2657 virtual void clear() { |
|
2658 _array.clear(); |
|
2659 _sep = 0; |
|
2660 Parent::clear(); |
|
2661 } |
|
2662 |
|
2663 }; |
|
2664 |
|
2665 |
|
2666 namespace _maps_bits { |
|
2667 template <typename Item> |
|
2668 struct IterableIntMapNode { |
|
2669 IterableIntMapNode() : value(-1) {} |
|
2670 IterableIntMapNode(int _value) : value(_value) {} |
|
2671 Item prev, next; |
|
2672 int value; |
|
2673 }; |
|
2674 } |
|
2675 |
|
2676 ///\ingroup graph_maps |
|
2677 /// |
|
2678 /// \brief Dynamic iterable integer map. |
|
2679 /// |
|
2680 /// This class provides a special graph map type which can store |
|
2681 /// for each graph item(node, edge, etc.) an integer value. For each |
|
2682 /// non negative value it is possible to iterate on the keys which |
|
2683 /// mapped to the given value. |
|
2684 /// |
|
2685 /// \note The size of the data structure depends on the highest |
|
2686 /// value in the map. |
|
2687 /// |
|
2688 /// \param GR The graph type. |
|
2689 /// \param ITEM One of the graph's item type, the key of the map. |
|
2690 template <typename GR, typename ITEM> |
|
2691 class IterableIntMap |
|
2692 : protected ItemSetTraits<GR, ITEM>:: |
|
2693 template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type { |
|
2694 public: |
|
2695 typedef typename ItemSetTraits<GR, ITEM>:: |
|
2696 template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type Parent; |
|
2697 |
|
2698 /// The key type |
|
2699 typedef ITEM Key; |
|
2700 /// The value type |
|
2701 typedef int Value; |
|
2702 /// The graph type |
|
2703 typedef GR Graph; |
|
2704 |
|
2705 /// \brief Constructor of the map. |
|
2706 /// |
|
2707 /// Constructor of the map. It set all values to -1. |
|
2708 explicit IterableIntMap(const Graph& graph) |
|
2709 : Parent(graph) {} |
|
2710 |
|
2711 /// \brief Constructor of the map with a given value. |
|
2712 /// |
|
2713 /// Constructor of the map with a given value. |
|
2714 explicit IterableIntMap(const Graph& graph, int value) |
|
2715 : Parent(graph, _maps_bits::IterableIntMapNode<ITEM>(value)) { |
|
2716 if (value >= 0) { |
|
2717 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { |
|
2718 lace(it); |
|
2719 } |
|
2720 } |
|
2721 } |
|
2722 |
|
2723 private: |
|
2724 |
|
2725 void unlace(const Key& key) { |
|
2726 typename Parent::Value& node = Parent::operator[](key); |
|
2727 if (node.value < 0) return; |
|
2728 if (node.prev != INVALID) { |
|
2729 Parent::operator[](node.prev).next = node.next; |
|
2730 } else { |
|
2731 _first[node.value] = node.next; |
|
2732 } |
|
2733 if (node.next != INVALID) { |
|
2734 Parent::operator[](node.next).prev = node.prev; |
|
2735 } |
|
2736 while (!_first.empty() && _first.back() == INVALID) { |
|
2737 _first.pop_back(); |
|
2738 } |
|
2739 } |
|
2740 |
|
2741 void lace(const Key& key) { |
|
2742 typename Parent::Value& node = Parent::operator[](key); |
|
2743 if (node.value < 0) return; |
|
2744 if (node.value >= int(_first.size())) { |
|
2745 _first.resize(node.value + 1, INVALID); |
|
2746 } |
|
2747 node.prev = INVALID; |
|
2748 node.next = _first[node.value]; |
|
2749 if (node.next != INVALID) { |
|
2750 Parent::operator[](node.next).prev = key; |
|
2751 } |
|
2752 _first[node.value] = key; |
|
2753 } |
|
2754 |
|
2755 public: |
|
2756 |
|
2757 /// Indicates that the map if reference map. |
|
2758 typedef True ReferenceMapTag; |
|
2759 |
|
2760 /// \brief Refernce to the value of the map. |
|
2761 /// |
|
2762 /// This class is similar to the int type. It can |
|
2763 /// be converted to int and it has the same operators. |
|
2764 class Reference { |
|
2765 friend class IterableIntMap; |
|
2766 private: |
|
2767 Reference(IterableIntMap& map, const Key& key) |
|
2768 : _key(key), _map(map) {} |
|
2769 public: |
|
2770 |
|
2771 Reference& operator=(const Reference& value) { |
|
2772 _map.set(_key, static_cast<const int&>(value)); |
|
2773 return *this; |
|
2774 } |
|
2775 |
|
2776 operator const int&() const { |
|
2777 return static_cast<const IterableIntMap&>(_map)[_key]; |
|
2778 } |
|
2779 |
|
2780 Reference& operator=(int value) { |
|
2781 _map.set(_key, value); |
|
2782 return *this; |
|
2783 } |
|
2784 Reference& operator++() { |
|
2785 _map.set(_key, _map[_key] + 1); |
|
2786 return *this; |
|
2787 } |
|
2788 int operator++(int) { |
|
2789 int value = _map[_key]; |
|
2790 _map.set(_key, value + 1); |
|
2791 return value; |
|
2792 } |
|
2793 Reference& operator--() { |
|
2794 _map.set(_key, _map[_key] - 1); |
|
2795 return *this; |
|
2796 } |
|
2797 int operator--(int) { |
|
2798 int value = _map[_key]; |
|
2799 _map.set(_key, value - 1); |
|
2800 return value; |
|
2801 } |
|
2802 Reference& operator+=(int value) { |
|
2803 _map.set(_key, _map[_key] + value); |
|
2804 return *this; |
|
2805 } |
|
2806 Reference& operator-=(int value) { |
|
2807 _map.set(_key, _map[_key] - value); |
|
2808 return *this; |
|
2809 } |
|
2810 Reference& operator*=(int value) { |
|
2811 _map.set(_key, _map[_key] * value); |
|
2812 return *this; |
|
2813 } |
|
2814 Reference& operator/=(int value) { |
|
2815 _map.set(_key, _map[_key] / value); |
|
2816 return *this; |
|
2817 } |
|
2818 Reference& operator%=(int value) { |
|
2819 _map.set(_key, _map[_key] % value); |
|
2820 return *this; |
|
2821 } |
|
2822 Reference& operator&=(int value) { |
|
2823 _map.set(_key, _map[_key] & value); |
|
2824 return *this; |
|
2825 } |
|
2826 Reference& operator|=(int value) { |
|
2827 _map.set(_key, _map[_key] | value); |
|
2828 return *this; |
|
2829 } |
|
2830 Reference& operator^=(int value) { |
|
2831 _map.set(_key, _map[_key] ^ value); |
|
2832 return *this; |
|
2833 } |
|
2834 Reference& operator<<=(int value) { |
|
2835 _map.set(_key, _map[_key] << value); |
|
2836 return *this; |
|
2837 } |
|
2838 Reference& operator>>=(int value) { |
|
2839 _map.set(_key, _map[_key] >> value); |
|
2840 return *this; |
|
2841 } |
|
2842 |
|
2843 private: |
|
2844 Key _key; |
|
2845 IterableIntMap& _map; |
|
2846 }; |
|
2847 |
|
2848 /// The const reference type. |
|
2849 typedef const Value& ConstReference; |
|
2850 |
|
2851 /// \brief Gives back the maximal value plus one. |
|
2852 /// |
|
2853 /// Gives back the maximal value plus one. |
|
2854 int size() const { |
|
2855 return _first.size(); |
|
2856 } |
|
2857 |
|
2858 /// \brief Set operation of the map. |
|
2859 /// |
|
2860 /// Set operation of the map. |
|
2861 void set(const Key& key, const Value& value) { |
|
2862 unlace(key); |
|
2863 Parent::operator[](key).value = value; |
|
2864 lace(key); |
|
2865 } |
|
2866 |
|
2867 /// \brief Const subscript operator of the map. |
|
2868 /// |
|
2869 /// Const subscript operator of the map. |
|
2870 const Value& operator[](const Key& key) const { |
|
2871 return Parent::operator[](key).value; |
|
2872 } |
|
2873 |
|
2874 /// \brief Subscript operator of the map. |
|
2875 /// |
|
2876 /// Subscript operator of the map. |
|
2877 Reference operator[](const Key& key) { |
|
2878 return Reference(*this, key); |
|
2879 } |
|
2880 |
|
2881 /// \brief Iterator for the keys with the same value. |
|
2882 /// |
|
2883 /// Iterator for the keys with the same value. It works |
|
2884 /// like a graph item iterator in the map, it can be converted |
|
2885 /// the item type of the map, incremented with \c ++ operator, and |
|
2886 /// if the iterator leave the last valid item it will be equal to |
|
2887 /// \c INVALID. |
|
2888 class ItemIt : public ITEM { |
|
2889 public: |
|
2890 typedef ITEM Parent; |
|
2891 |
|
2892 /// \brief Invalid constructor \& conversion. |
|
2893 /// |
|
2894 /// This constructor initializes the item to be invalid. |
|
2895 /// \sa Invalid for more details. |
|
2896 ItemIt(Invalid) : Parent(INVALID), _map(0) {} |
|
2897 |
|
2898 /// \brief Creates an iterator with a value. |
|
2899 /// |
|
2900 /// Creates an iterator with a value. It iterates on the |
|
2901 /// keys which have the given value. |
|
2902 /// \param map The IterableIntMap |
|
2903 /// \param value The value |
|
2904 ItemIt(const IterableIntMap& map, int value) : _map(&map) { |
|
2905 if (value < 0 || value >= int(_map->_first.size())) { |
|
2906 Parent::operator=(INVALID); |
|
2907 } else { |
|
2908 Parent::operator=(_map->_first[value]); |
|
2909 } |
|
2910 } |
|
2911 |
|
2912 /// \brief Increment operator. |
|
2913 /// |
|
2914 /// Increment Operator. |
|
2915 ItemIt& operator++() { |
|
2916 Parent::operator=(_map->IterableIntMap::Parent:: |
|
2917 operator[](static_cast<Parent&>(*this)).next); |
|
2918 return *this; |
|
2919 } |
|
2920 |
|
2921 |
|
2922 private: |
|
2923 const IterableIntMap* _map; |
|
2924 }; |
|
2925 |
|
2926 protected: |
|
2927 |
|
2928 virtual void erase(const Key& key) { |
|
2929 unlace(key); |
|
2930 Parent::erase(key); |
|
2931 } |
|
2932 |
|
2933 virtual void erase(const std::vector<Key>& keys) { |
|
2934 for (int i = 0; i < int(keys.size()); ++i) { |
|
2935 unlace(keys[i]); |
|
2936 } |
|
2937 Parent::erase(keys); |
|
2938 } |
|
2939 |
|
2940 virtual void clear() { |
|
2941 _first.clear(); |
|
2942 Parent::clear(); |
|
2943 } |
|
2944 |
|
2945 private: |
|
2946 std::vector<ITEM> _first; |
|
2947 }; |
|
2948 |
|
2949 namespace _maps_bits { |
|
2950 template <typename Item, typename Value> |
|
2951 struct IterableValueMapNode { |
|
2952 IterableValueMapNode(Value _value = Value()) : value(_value) {} |
|
2953 Item prev, next; |
|
2954 Value value; |
|
2955 }; |
|
2956 } |
|
2957 |
|
2958 ///\ingroup graph_maps |
|
2959 /// |
|
2960 /// \brief Dynamic iterable map for comparable values. |
|
2961 /// |
|
2962 /// This class provides a special graph map type which can store |
|
2963 /// for each graph item(node, edge, etc.) a value. For each |
|
2964 /// value it is possible to iterate on the keys which mapped to the |
|
2965 /// given value. The type stores for each value a linked list with |
|
2966 /// the items which mapped to the value, and the values are stored |
|
2967 /// in balanced binary tree. The values of the map can be accessed |
|
2968 /// with stl compatible forward iterator. |
|
2969 /// |
|
2970 /// This type is not reference map so it cannot be modified with |
|
2971 /// the subscription operator. |
|
2972 /// |
|
2973 /// \see InvertableMap |
|
2974 /// |
|
2975 /// \param GR The graph type. |
|
2976 /// \param ITEM One of the graph's item type, the key of the map. |
|
2977 /// \param VAL Any comparable value type. |
|
2978 template <typename GR, typename ITEM, typename VAL> |
|
2979 class IterableValueMap |
|
2980 : protected ItemSetTraits<GR, ITEM>:: |
|
2981 template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type { |
|
2982 public: |
|
2983 typedef typename ItemSetTraits<GR, ITEM>:: |
|
2984 template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type Parent; |
|
2985 |
|
2986 /// The key type |
|
2987 typedef ITEM Key; |
|
2988 /// The value type |
|
2989 typedef VAL Value; |
|
2990 /// The graph type |
|
2991 typedef GR Graph; |
|
2992 |
|
2993 public: |
|
2994 |
|
2995 /// \brief Constructor of the Map with a given value. |
|
2996 /// |
|
2997 /// Constructor of the Map with a given value. |
|
2998 explicit IterableValueMap(const Graph& graph, |
|
2999 const Value& value = Value()) |
|
3000 : Parent(graph, _maps_bits::IterableValueMapNode<ITEM, VAL>(value)) { |
|
3001 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { |
|
3002 lace(it); |
|
3003 } |
|
3004 } |
|
3005 |
|
3006 protected: |
|
3007 |
|
3008 void unlace(const Key& key) { |
|
3009 typename Parent::Value& node = Parent::operator[](key); |
|
3010 if (node.prev != INVALID) { |
|
3011 Parent::operator[](node.prev).next = node.next; |
|
3012 } else { |
|
3013 if (node.next != INVALID) { |
|
3014 _first[node.value] = node.next; |
|
3015 } else { |
|
3016 _first.erase(node.value); |
|
3017 } |
|
3018 } |
|
3019 if (node.next != INVALID) { |
|
3020 Parent::operator[](node.next).prev = node.prev; |
|
3021 } |
|
3022 } |
|
3023 |
|
3024 void lace(const Key& key) { |
|
3025 typename Parent::Value& node = Parent::operator[](key); |
|
3026 typename std::map<Value, Key>::iterator it = _first.find(node.value); |
|
3027 if (it == _first.end()) { |
|
3028 node.prev = node.next = INVALID; |
|
3029 if (node.next != INVALID) { |
|
3030 Parent::operator[](node.next).prev = key; |
|
3031 } |
|
3032 _first.insert(std::make_pair(node.value, key)); |
|
3033 } else { |
|
3034 node.prev = INVALID; |
|
3035 node.next = it->second; |
|
3036 if (node.next != INVALID) { |
|
3037 Parent::operator[](node.next).prev = key; |
|
3038 } |
|
3039 it->second = key; |
|
3040 } |
|
3041 } |
|
3042 |
|
3043 public: |
|
3044 |
|
3045 /// \brief Forward iterator for values. |
|
3046 /// |
|
3047 /// This iterator is an stl compatible forward |
|
3048 /// iterator on the values of the map. The values can |
|
3049 /// be accessed in the [beginValue, endValue) range. |
|
3050 /// |
|
3051 class ValueIterator |
|
3052 : public std::iterator<std::forward_iterator_tag, Value> { |
|
3053 friend class IterableValueMap; |
|
3054 private: |
|
3055 ValueIterator(typename std::map<Value, Key>::const_iterator _it) |
|
3056 : it(_it) {} |
|
3057 public: |
|
3058 |
|
3059 ValueIterator() {} |
|
3060 |
|
3061 ValueIterator& operator++() { ++it; return *this; } |
|
3062 ValueIterator operator++(int) { |
|
3063 ValueIterator tmp(*this); |
|
3064 operator++(); |
|
3065 return tmp; |
|
3066 } |
|
3067 |
|
3068 const Value& operator*() const { return it->first; } |
|
3069 const Value* operator->() const { return &(it->first); } |
|
3070 |
|
3071 bool operator==(ValueIterator jt) const { return it == jt.it; } |
|
3072 bool operator!=(ValueIterator jt) const { return it != jt.it; } |
|
3073 |
|
3074 private: |
|
3075 typename std::map<Value, Key>::const_iterator it; |
|
3076 }; |
|
3077 |
|
3078 /// \brief Returns an iterator to the first value. |
|
3079 /// |
|
3080 /// Returns an stl compatible iterator to the |
|
3081 /// first value of the map. The values of the |
|
3082 /// map can be accessed in the [beginValue, endValue) |
|
3083 /// range. |
|
3084 ValueIterator beginValue() const { |
|
3085 return ValueIterator(_first.begin()); |
|
3086 } |
|
3087 |
|
3088 /// \brief Returns an iterator after the last value. |
|
3089 /// |
|
3090 /// Returns an stl compatible iterator after the |
|
3091 /// last value of the map. The values of the |
|
3092 /// map can be accessed in the [beginValue, endValue) |
|
3093 /// range. |
|
3094 ValueIterator endValue() const { |
|
3095 return ValueIterator(_first.end()); |
|
3096 } |
|
3097 |
|
3098 /// \brief Set operation of the map. |
|
3099 /// |
|
3100 /// Set operation of the map. |
|
3101 void set(const Key& key, const Value& value) { |
|
3102 unlace(key); |
|
3103 Parent::operator[](key).value = value; |
|
3104 lace(key); |
|
3105 } |
|
3106 |
|
3107 /// \brief Const subscript operator of the map. |
|
3108 /// |
|
3109 /// Const subscript operator of the map. |
|
3110 const Value& operator[](const Key& key) const { |
|
3111 return Parent::operator[](key).value; |
|
3112 } |
|
3113 |
|
3114 /// \brief Iterator for the keys with the same value. |
|
3115 /// |
|
3116 /// Iterator for the keys with the same value. It works |
|
3117 /// like a graph item iterator in the map, it can be converted |
|
3118 /// the item type of the map, incremented with \c ++ operator, and |
|
3119 /// if the iterator leave the last valid item it will be equal to |
|
3120 /// \c INVALID. |
|
3121 class ItemIt : public ITEM { |
|
3122 public: |
|
3123 typedef ITEM Parent; |
|
3124 |
|
3125 /// \brief Invalid constructor \& conversion. |
|
3126 /// |
|
3127 /// This constructor initializes the item to be invalid. |
|
3128 /// \sa Invalid for more details. |
|
3129 ItemIt(Invalid) : Parent(INVALID), _map(0) {} |
|
3130 |
|
3131 /// \brief Creates an iterator with a value. |
|
3132 /// |
|
3133 /// Creates an iterator with a value. It iterates on the |
|
3134 /// keys which have the given value. |
|
3135 /// \param map The IterableValueMap |
|
3136 /// \param value The value |
|
3137 ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { |
|
3138 typename std::map<Value, Key>::const_iterator it = |
|
3139 map._first.find(value); |
|
3140 if (it == map._first.end()) { |
|
3141 Parent::operator=(INVALID); |
|
3142 } else { |
|
3143 Parent::operator=(it->second); |
|
3144 } |
|
3145 } |
|
3146 |
|
3147 /// \brief Increment operator. |
|
3148 /// |
|
3149 /// Increment Operator. |
|
3150 ItemIt& operator++() { |
|
3151 Parent::operator=(_map->IterableValueMap::Parent:: |
|
3152 operator[](static_cast<Parent&>(*this)).next); |
|
3153 return *this; |
|
3154 } |
|
3155 |
|
3156 |
|
3157 private: |
|
3158 const IterableValueMap* _map; |
|
3159 }; |
|
3160 |
|
3161 protected: |
|
3162 |
|
3163 virtual void add(const Key& key) { |
|
3164 Parent::add(key); |
|
3165 unlace(key); |
|
3166 } |
|
3167 |
|
3168 virtual void add(const std::vector<Key>& keys) { |
|
3169 Parent::add(keys); |
|
3170 for (int i = 0; i < int(keys.size()); ++i) { |
|
3171 lace(keys[i]); |
|
3172 } |
|
3173 } |
|
3174 |
|
3175 virtual void erase(const Key& key) { |
|
3176 unlace(key); |
|
3177 Parent::erase(key); |
|
3178 } |
|
3179 |
|
3180 virtual void erase(const std::vector<Key>& keys) { |
|
3181 for (int i = 0; i < int(keys.size()); ++i) { |
|
3182 unlace(keys[i]); |
|
3183 } |
|
3184 Parent::erase(keys); |
|
3185 } |
|
3186 |
|
3187 virtual void build() { |
|
3188 Parent::build(); |
|
3189 for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { |
|
3190 lace(it); |
|
3191 } |
|
3192 } |
|
3193 |
|
3194 virtual void clear() { |
|
3195 _first.clear(); |
|
3196 Parent::clear(); |
|
3197 } |
|
3198 |
|
3199 private: |
|
3200 std::map<Value, Key> _first; |
|
3201 }; |
|
3202 |
2314 /// \brief Map of the source nodes of arcs in a digraph. |
3203 /// \brief Map of the source nodes of arcs in a digraph. |
2315 /// |
3204 /// |
2316 /// SourceMap provides access for the source node of each arc in a digraph, |
3205 /// SourceMap provides access for the source node of each arc in a digraph, |
2317 /// which is returned by the \c source() function of the digraph. |
3206 /// which is returned by the \c source() function of the digraph. |
2318 /// \tparam GR The digraph type. |
3207 /// \tparam GR The digraph type. |