alpar@1677: /* -*- C++ -*- alpar@1677: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1677: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@1677: * alpar@1677: * Permission to use, modify and distribute this software is granted alpar@1677: * provided that this copyright notice appears in all copies. For alpar@1677: * precise terms see the accompanying LICENSE file. alpar@1677: * alpar@1677: * This software is provided "AS IS" with no warranty of any kind, alpar@1677: * express or implied, and with no claim as to its suitability for any alpar@1677: * purpose. alpar@1677: * alpar@1677: */ alpar@1677: deba@2210: #ifndef LEMON_ITERABLE_MAPS_H deba@2210: #define LEMON_ITERABLE_MAPS_H deba@2210: deba@1993: #include deba@1993: #include deba@1931: deba@1990: #include deba@2031: #include deba@1990: alpar@1677: #include deba@1931: #include deba@1931: deba@1931: #include alpar@1677: #include alpar@1677: alpar@1677: ///\ingroup maps alpar@1677: ///\file alpar@1677: ///\brief Maps that makes it possible to iterate through the keys having alpar@1677: ///a certain value alpar@1677: /// alpar@1677: /// alpar@1677: alpar@1677: alpar@1677: namespace lemon { deba@1913: deba@1931: ///\ingroup graph_maps deba@1913: /// deba@1913: /// \brief Dynamic iterable bool map. deba@1913: /// deba@1913: /// This class provides a special graph map type which can store deba@1913: /// for each graph item(node, edge, etc.) a bool value. For both deba@1913: /// the true and the false it is possible to iterate on the keys which deba@1913: /// mapped to the given value. deba@1913: /// deba@1913: /// \param _Graph The graph type. deba@1913: /// \param _Item One of the graph's item type, the key of the map. deba@1913: template deba@1990: class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> { deba@1913: private: deba@1913: typedef _Graph Graph; deba@1913: deba@1931: typedef typename ItemSetTraits::ItemIt KeyIt; deba@1990: typedef DefaultMap<_Graph, _Item, int> Parent; deba@1913: deba@1931: std::vector<_Item> array; deba@1913: int sep; deba@1913: deba@1913: const Graph& graph; alpar@1677: alpar@1677: public: alpar@1805: deba@1913: /// Indicates that the map if reference map. deba@1913: typedef True ReferenceMapTag; alpar@1805: deba@1913: /// The key type deba@1931: typedef _Item Key; deba@1913: /// The value type deba@1913: typedef bool Value; deba@1913: /// The const reference type. deba@1913: typedef const Value& ConstReference; deba@1913: deba@1931: private: deba@1931: deba@1931: int position(const Key& key) const { deba@1931: return Parent::operator[](key); deba@1931: } deba@1931: deba@1931: public: deba@1913: deba@1913: /// \brief Refernce to the value of the map. deba@1913: /// deba@1913: /// This class is near to similar to the bool type. It can deba@1913: /// be converted to bool and it has the same operators. deba@1913: class Reference { deba@1913: friend class IterableBoolMap; deba@1913: private: deba@1913: Reference(IterableBoolMap& map, const Key& key) deba@1913: : _key(key), _map(map) {} alpar@1677: public: deba@1913: deba@1913: Reference& operator=(const Reference& value) { deba@2386: _map.set(_key, static_cast(value)); deba@1913: return *this; deba@1913: } deba@1913: deba@1913: operator bool() const { deba@1913: return static_cast(_map)[_key]; deba@1913: } deba@1913: deba@1913: Reference& operator=(bool value) { deba@1913: _map.set(_key, value); deba@1913: return *this; deba@1913: } deba@1913: Reference& operator&=(bool value) { deba@1913: _map.set(_key, _map[_key] & value); deba@1913: return *this; deba@1913: } deba@1913: Reference& operator|=(bool value) { deba@1913: _map.set(_key, _map[_key] | value); deba@1913: return *this; deba@1913: } deba@1913: Reference& operator^=(bool value) { deba@1913: _map.set(_key, _map[_key] ^ value); deba@1913: return *this; deba@1913: } deba@1913: private: deba@1913: Key _key; deba@1913: IterableBoolMap& _map; alpar@1677: }; deba@1913: deba@1913: /// \brief Constructor of the Map with a default value. deba@1913: /// deba@1913: /// Constructor of the Map with a default value. deba@2112: explicit IterableBoolMap(const Graph& _graph, bool def = false) deba@1913: : Parent(_graph), graph(_graph) { deba@1931: for (KeyIt it(graph); it != INVALID; ++it) { deba@1913: Parent::set(it, array.size()); deba@1913: array.push_back(it); deba@1913: } deba@1913: sep = (def ? array.size() : 0); deba@1913: } deba@1913: deba@1913: /// \brief Const subscript operator of the map. deba@1913: /// deba@1913: /// Const subscript operator of the map. deba@1931: bool operator[](const Key& key) const { deba@1931: return position(key) < sep; deba@1913: } deba@1913: deba@1913: /// \brief Subscript operator of the map. deba@1913: /// deba@1913: /// Subscript operator of the map. deba@1931: Reference operator[](const Key& key) { deba@1931: return Reference(*this, key); deba@1913: } deba@1913: deba@1913: /// \brief Set operation of the map. deba@1913: /// deba@1913: /// Set operation of the map. deba@1931: void set(const Key& key, bool value) { deba@1931: int pos = position(key); deba@1913: if (value) { deba@1913: if (pos < sep) return; deba@1931: Key tmp = array[sep]; deba@1931: array[sep] = key; deba@1931: Parent::set(key, sep); deba@1913: array[pos] = tmp; deba@1913: Parent::set(tmp, pos); deba@1913: ++sep; deba@1913: } else { deba@1913: if (pos >= sep) return; deba@1913: --sep; deba@1931: Key tmp = array[sep]; deba@1931: array[sep] = key; deba@1931: Parent::set(key, sep); deba@1913: array[pos] = tmp; deba@1913: Parent::set(tmp, pos); deba@1913: } deba@1913: } deba@1913: deba@2496: /// \brief Set all items. deba@2496: /// deba@2496: /// Set all items in the map. deba@2496: /// \note Constant time operation. deba@2496: void setAll(bool value) { deba@2496: sep = (value ? array.size() : 0); deba@2496: } deba@2496: deba@1931: /// \brief Returns the number of the keys mapped to true. deba@1913: /// deba@1931: /// Returns the number of the keys mapped to true. deba@1913: int trueNum() const { deba@1913: return sep; deba@1913: } deba@1913: deba@1931: /// \brief Returns the number of the keys mapped to false. deba@1913: /// deba@1931: /// Returns the number of the keys mapped to false. deba@1913: int falseNum() const { deba@1913: return array.size() - sep; deba@1913: } deba@1913: deba@1913: /// \brief Iterator for the keys mapped to true. deba@1913: /// deba@1913: /// Iterator for the keys mapped to true. It works deba@1913: /// like a graph item iterator in the map, it can be converted deba@1931: /// the key type of the map, incremented with \c ++ operator, and deba@1931: /// if the iterator leave the last valid key it will be equal to deba@1913: /// \c INVALID. deba@1931: class TrueIt : public Key { alpar@1677: public: deba@1931: typedef Key Parent; deba@1913: deba@1913: /// \brief Creates an iterator. deba@1913: /// deba@1913: /// Creates an iterator. It iterates on the deba@1913: /// keys which mapped to true. alpar@1953: /// \param _map The IterableIntMap deba@2112: explicit TrueIt(const IterableBoolMap& _map) deba@1913: : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), deba@1913: map(&_map) {} deba@1913: deba@1913: /// \brief Invalid constructor \& conversion. deba@1913: /// deba@1931: /// This constructor initializes the key to be invalid. deba@1913: /// \sa Invalid for more details. deba@1913: TrueIt(Invalid) : Parent(INVALID), map(0) {} deba@1913: deba@1913: /// \brief Increment operator. deba@1913: /// deba@1913: /// Increment Operator. deba@1913: TrueIt& operator++() { deba@1913: int pos = map->position(*this); deba@1913: Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID); deba@1913: return *this; deba@1913: } deba@1913: deba@1913: deba@1913: private: deba@1913: const IterableBoolMap* map; deba@1913: }; deba@1913: deba@1913: /// \brief Iterator for the keys mapped to false. deba@1913: /// deba@1913: /// Iterator for the keys mapped to false. It works deba@1913: /// like a graph item iterator in the map, it can be converted deba@1931: /// the key type of the map, incremented with \c ++ operator, and deba@1931: /// if the iterator leave the last valid key it will be equal to deba@1913: /// \c INVALID. deba@1931: class FalseIt : public Key { deba@1913: public: deba@1931: typedef Key Parent; deba@1913: deba@1913: /// \brief Creates an iterator. deba@1913: /// deba@1913: /// Creates an iterator. It iterates on the deba@1913: /// keys which mapped to false. alpar@1953: /// \param _map The IterableIntMap deba@2112: explicit FalseIt(const IterableBoolMap& _map) deba@2386: : Parent(_map.sep < int(_map.array.size()) ? deba@1931: _map.array.back() : INVALID), map(&_map) {} deba@1913: deba@1913: /// \brief Invalid constructor \& conversion. deba@1913: /// deba@1931: /// This constructor initializes the key to be invalid. deba@1913: /// \sa Invalid for more details. deba@1913: FalseIt(Invalid) : Parent(INVALID), map(0) {} deba@1913: deba@1913: /// \brief Increment operator. deba@1913: /// deba@1913: /// Increment Operator. deba@1913: FalseIt& operator++() { deba@1913: int pos = map->position(*this); deba@1913: Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID); deba@1913: return *this; deba@1913: } deba@1913: deba@1913: private: deba@1913: const IterableBoolMap* map; deba@1913: }; deba@1913: deba@1931: /// \brief Iterator for the keys mapped to a given value. deba@1931: /// deba@1931: /// Iterator for the keys mapped to a given value. It works deba@1931: /// like a graph item iterator in the map, it can be converted deba@1931: /// the key type of the map, incremented with \c ++ operator, and deba@1931: /// if the iterator leave the last valid key it will be equal to deba@1931: /// \c INVALID. deba@1931: class ItemIt : public Key { deba@1931: public: deba@1931: typedef Key Parent; deba@1931: deba@1931: /// \brief Creates an iterator. deba@1931: /// deba@1931: /// Creates an iterator. It iterates on the deba@1931: /// keys which mapped to false. alpar@1953: /// \param _map The IterableIntMap deba@1931: /// \param value Which elements should be iterated. deba@1931: ItemIt(const IterableBoolMap& _map, bool value) deba@1931: : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) : deba@2386: (_map.sep < int(_map.array.size()) ? deba@1931: _map.array.back() : INVALID)), map(&_map) {} deba@1931: deba@1931: /// \brief Invalid constructor \& conversion. deba@1931: /// deba@1931: /// This constructor initializes the key to be invalid. deba@1931: /// \sa Invalid for more details. deba@1931: ItemIt(Invalid) : Parent(INVALID), map(0) {} deba@1931: deba@1931: /// \brief Increment operator. deba@1931: /// deba@1931: /// Increment Operator. deba@1931: ItemIt& operator++() { deba@1931: int pos = map->position(*this); deba@1931: int sep = pos >= map->sep ? map->sep : 0; deba@1931: Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID); deba@1931: return *this; deba@1931: } deba@1931: deba@1931: private: deba@1931: const IterableBoolMap* map; deba@1931: }; deba@1931: deba@1913: protected: deba@1913: deba@1931: virtual void add(const Key& key) { deba@1931: Parent::add(key); deba@1931: Parent::set(key, array.size()); deba@1931: array.push_back(key); deba@1913: } deba@1913: deba@1931: virtual void add(const std::vector& keys) { deba@1931: Parent::add(keys); deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@1931: Parent::set(keys[i], array.size()); deba@1931: array.push_back(keys[i]); deba@1913: } deba@1913: } deba@1913: deba@1931: virtual void erase(const Key& key) { deba@1931: int pos = position(key); deba@1913: if (pos < sep) { deba@1913: --sep; deba@1913: Parent::set(array[sep], pos); deba@1913: array[pos] = array[sep]; deba@1913: Parent::set(array.back(), sep); deba@1913: array[sep] = array.back(); deba@1913: array.pop_back(); deba@1913: } else { deba@1913: Parent::set(array.back(), pos); deba@1913: array[pos] = array.back(); deba@1913: array.pop_back(); deba@1913: } deba@1931: Parent::erase(key); deba@1913: } deba@1913: deba@1931: virtual void erase(const std::vector& keys) { deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@1931: int pos = position(keys[i]); deba@1913: if (pos < sep) { deba@1913: --sep; deba@1913: Parent::set(array[sep], pos); deba@1913: array[pos] = array[sep]; deba@1913: Parent::set(array.back(), sep); deba@1913: array[sep] = array.back(); deba@1913: array.pop_back(); deba@1913: } else { deba@1913: Parent::set(array.back(), pos); deba@1913: array[pos] = array.back(); deba@1913: array.pop_back(); deba@1913: } deba@1913: } deba@1931: Parent::erase(keys); deba@1913: } deba@1913: deba@1913: virtual void build() { deba@1913: Parent::build(); deba@1931: for (KeyIt it(graph); it != INVALID; ++it) { deba@1913: Parent::set(it, array.size()); deba@1913: array.push_back(it); deba@1913: } deba@1913: sep = 0; deba@1913: } deba@1913: deba@1913: virtual void clear() { deba@1913: array.clear(); deba@1913: sep = 0; deba@1913: Parent::clear(); deba@1913: } deba@1913: alpar@1677: }; alpar@1873: deba@1752: deba@1752: namespace _iterable_maps_bits { deba@1752: template deba@1752: struct IterableIntMapNode { deba@1913: IterableIntMapNode() : value(-1) {} deba@1810: IterableIntMapNode(int _value) : value(_value) {} deba@1752: Item prev, next; deba@1752: int value; deba@1752: }; deba@1752: } deba@1752: deba@1931: ///\ingroup graph_maps deba@1752: /// deba@1752: /// \brief Dynamic iterable integer map. deba@1752: /// deba@1810: /// This class provides a special graph map type which can store deba@1810: /// for each graph item(node, edge, etc.) an integer value. For each deba@1810: /// non negative value it is possible to iterate on the keys which deba@1810: /// mapped to the given value. deba@1810: /// deba@1810: /// \param _Graph The graph type. deba@1810: /// \param _Item One of the graph's item type, the key of the map. deba@1752: template deba@1990: class IterableIntMap deba@2031: : protected MapExtender > >{ deba@1752: public: deba@2031: typedef MapExtender > > Parent; deba@1752: deba@1810: /// The key type deba@1752: typedef _Item Key; deba@1810: /// The value type deba@1752: typedef int Value; deba@1810: /// The graph type deba@1752: typedef _Graph Graph; deba@1752: deba@1810: /// \brief Constructor of the Map. deba@1810: /// deba@1810: /// Constructor of the Map. It set all values -1. deba@1810: explicit IterableIntMap(const Graph& graph) deba@1913: : Parent(graph) {} deba@1810: deba@1810: /// \brief Constructor of the Map with a given value. deba@1810: /// deba@1810: /// Constructor of the Map with a given value. deba@1810: explicit IterableIntMap(const Graph& graph, int value) deba@1810: : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) { deba@1810: if (value >= 0) { deba@1810: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@1810: lace(it); deba@1810: } deba@1810: } deba@1810: } deba@1752: deba@1752: private: deba@1752: deba@1752: void unlace(const Key& key) { deba@1752: typename Parent::Value& node = Parent::operator[](key); deba@1752: if (node.value < 0) return; deba@1752: if (node.prev != INVALID) { deba@1752: Parent::operator[](node.prev).next = node.next; deba@1752: } else { deba@1752: first[node.value] = node.next; deba@1752: } deba@1752: if (node.next != INVALID) { deba@1752: Parent::operator[](node.next).prev = node.prev; deba@1752: } deba@1752: while (!first.empty() && first.back() == INVALID) { deba@1752: first.pop_back(); deba@1752: } deba@1752: } deba@1752: deba@1752: void lace(const Key& key) { deba@1752: typename Parent::Value& node = Parent::operator[](key); deba@1752: if (node.value < 0) return; deba@2386: if (node.value >= int(first.size())) { deba@1752: first.resize(node.value + 1, INVALID); deba@1752: } deba@1752: node.prev = INVALID; deba@1752: node.next = first[node.value]; deba@1752: if (node.next != INVALID) { deba@1752: Parent::operator[](node.next).prev = key; deba@1752: } deba@1752: first[node.value] = key; deba@1752: } deba@1752: deba@1752: public: deba@1752: deba@1810: /// Indicates that the map if reference map. deba@1752: typedef True ReferenceMapTag; deba@1752: deba@1810: /// \brief Refernce to the value of the map. deba@1810: /// deba@1810: /// This class is near to similar to the int type. It can deba@1810: /// be converted to int and it has the same operators. deba@1752: class Reference { deba@1752: friend class IterableIntMap; deba@1752: private: deba@1752: Reference(IterableIntMap& map, const Key& key) deba@1752: : _key(key), _map(map) {} deba@1752: public: deba@1752: deba@1752: Reference& operator=(const Reference& value) { deba@2386: _map.set(_key, static_cast(value)); deba@1752: return *this; deba@1752: } deba@1752: deba@1752: operator const int&() const { deba@1752: return static_cast(_map)[_key]; deba@1752: } deba@1752: deba@1752: Reference& operator=(int value) { deba@1752: _map.set(_key, value); deba@1752: return *this; deba@1752: } deba@1759: Reference& operator++() { deba@1759: _map.set(_key, _map[_key] + 1); deba@1759: return *this; deba@1759: } deba@1759: int operator++(int) { deba@1759: int value = _map[_key]; deba@1759: _map.set(_key, value + 1); deba@1759: return value; deba@1759: } deba@1759: Reference& operator--() { deba@1759: _map.set(_key, _map[_key] - 1); deba@1759: return *this; deba@1759: } deba@1759: int operator--(int) { deba@1759: int value = _map[_key]; deba@1759: _map.set(_key, value - 1); deba@1759: return value; deba@1759: } deba@1752: Reference& operator+=(int value) { deba@1752: _map.set(_key, _map[_key] + value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator-=(int value) { deba@1752: _map.set(_key, _map[_key] - value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator*=(int value) { deba@1752: _map.set(_key, _map[_key] * value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator/=(int value) { deba@1752: _map.set(_key, _map[_key] / value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator%=(int value) { deba@1752: _map.set(_key, _map[_key] % value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator&=(int value) { deba@1752: _map.set(_key, _map[_key] & value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator|=(int value) { deba@1752: _map.set(_key, _map[_key] | value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator^=(int value) { deba@1752: _map.set(_key, _map[_key] ^ value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator<<=(int value) { deba@1752: _map.set(_key, _map[_key] << value); deba@1752: return *this; deba@1752: } deba@1752: Reference& operator>>=(int value) { deba@1752: _map.set(_key, _map[_key] >> value); deba@1752: return *this; deba@1752: } deba@1752: deba@1752: private: deba@1752: Key _key; deba@1752: IterableIntMap& _map; deba@1752: }; deba@1810: deba@1810: /// The const reference type. deba@1752: typedef const Value& ConstReference; deba@1752: deba@1810: /// \brief Gives back the maximal value plus one. deba@1810: /// deba@1810: /// Gives back the maximal value plus one. deba@1931: unsigned int size() const { deba@1931: return first.size(); deba@1752: } deba@1752: deba@1810: /// \brief Set operation of the map. deba@1810: /// deba@1810: /// Set operation of the map. deba@1752: void set(const Key& key, const Value& value) { deba@1752: unlace(key); deba@1752: Parent::operator[](key).value = value; deba@1752: lace(key); deba@1752: } deba@1752: deba@1810: /// \brief Const subscript operator of the map. deba@1810: /// deba@1810: /// Const subscript operator of the map. deba@1752: const Value& operator[](const Key& key) const { deba@1752: return Parent::operator[](key).value; deba@1752: } deba@1752: deba@1810: /// \brief Subscript operator of the map. deba@1810: /// deba@1810: /// Subscript operator of the map. deba@1752: Reference operator[](const Key& key) { deba@1752: return Reference(*this, key); deba@1752: } deba@1752: deba@1810: /// \brief Iterator for the keys with the same value. deba@1810: /// deba@1810: /// Iterator for the keys with the same value. It works deba@1810: /// like a graph item iterator in the map, it can be converted deba@1810: /// the item type of the map, incremented with \c ++ operator, and deba@1810: /// if the iterator leave the last valid item it will be equal to deba@1810: /// \c INVALID. deba@1752: class ItemIt : public _Item { deba@1752: public: deba@1752: typedef _Item Parent; deba@1752: deba@1810: /// \brief Invalid constructor \& conversion. deba@1810: /// deba@1810: /// This constructor initializes the item to be invalid. deba@1810: /// \sa Invalid for more details. deba@1752: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@1752: deba@1810: /// \brief Creates an iterator with a value. deba@1810: /// deba@1810: /// Creates an iterator with a value. It iterates on the deba@1810: /// keys which have the given value. deba@1810: /// \param map The IterableIntMap deba@1810: /// \param value The value deba@1752: ItemIt(const IterableIntMap& map, int value) : _map(&map) { deba@2386: if (value < 0 || value >= int(_map->first.size())) { deba@1752: Parent::operator=(INVALID); deba@1752: } else { deba@1752: Parent::operator=(_map->first[value]); deba@1752: } deba@1752: } deba@1752: deba@1810: /// \brief Increment operator. deba@1810: /// deba@1810: /// Increment Operator. deba@1752: ItemIt& operator++() { deba@1752: Parent::operator=(_map->IterableIntMap::Parent:: deba@1752: operator[](static_cast(*this)).next); deba@1752: return *this; deba@1752: } deba@1752: deba@1752: deba@1752: private: deba@1752: const IterableIntMap* _map; deba@1752: }; deba@1752: deba@1752: protected: deba@1752: deba@1752: virtual void erase(const Key& key) { deba@1752: unlace(key); deba@1752: Parent::erase(key); deba@1752: } deba@1752: deba@1913: virtual void erase(const std::vector& keys) { deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@1913: unlace(keys[i]); deba@1913: } deba@1913: Parent::erase(keys); deba@1913: } deba@1913: deba@1752: virtual void clear() { deba@1752: first.clear(); deba@1752: Parent::clear(); deba@1752: } deba@1752: deba@1752: private: deba@1752: std::vector<_Item> first; deba@1752: }; deba@1752: deba@1931: namespace _iterable_maps_bits { deba@1931: template deba@1931: struct IterableValueMapNode { deba@1931: IterableValueMapNode(Value _value = Value()) : value(_value) {} deba@1931: Item prev, next; deba@1931: Value value; deba@1931: }; deba@1931: } deba@1931: deba@1931: ///\ingroup graph_maps deba@1931: /// deba@1931: /// \brief Dynamic iterable map for comparable values. deba@1931: /// deba@1931: /// This class provides a special graph map type which can store deba@1931: /// for each graph item(node, edge, etc.) a value. For each deba@1931: /// value it is possible to iterate on the keys which mapped to the deba@1931: /// given value. The type stores for each value a linked list with deba@1931: /// the items which mapped to the value, and the values are stored deba@1931: /// in balanced binary tree. The values of the map can be accessed deba@1931: /// with stl compatible forward iterator. deba@1931: /// deba@1931: /// This type is not reference map so it cannot be modified with deba@1931: /// the subscription operator. deba@1931: /// deba@1931: /// \see InvertableMap deba@1931: /// deba@1931: /// \param _Graph The graph type. deba@1931: /// \param _Item One of the graph's item type, the key of the map. deba@1931: /// \param _Value Any comparable value type. deba@1931: template deba@1990: class IterableValueMap deba@2031: : protected MapExtender > >{ deba@1931: public: deba@2031: typedef MapExtender > > deba@2031: Parent; deba@1931: deba@1931: /// The key type deba@1931: typedef _Item Key; deba@1931: /// The value type deba@1931: typedef _Value Value; deba@1931: /// The graph type deba@1931: typedef _Graph Graph; deba@1931: deba@1990: public: deba@1990: deba@1931: /// \brief Constructor of the Map with a given value. deba@1931: /// deba@1931: /// Constructor of the Map with a given value. deba@1931: explicit IterableValueMap(const Graph& graph, deba@1931: const Value& value = Value()) deba@1990: : Parent(graph, _iterable_maps_bits:: deba@1990: IterableValueMapNode<_Item, _Value>(value)) { deba@2031: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@1931: lace(it); deba@1931: } deba@1931: } deba@1931: deba@1990: protected: deba@1931: deba@1931: void unlace(const Key& key) { deba@1931: typename Parent::Value& node = Parent::operator[](key); deba@1931: if (node.prev != INVALID) { deba@1931: Parent::operator[](node.prev).next = node.next; deba@1931: } else { deba@1931: if (node.next != INVALID) { deba@1931: first[node.value] = node.next; deba@1931: } else { deba@1931: first.erase(node.value); deba@1931: } deba@1931: } deba@1931: if (node.next != INVALID) { deba@1931: Parent::operator[](node.next).prev = node.prev; deba@1931: } deba@1931: } deba@1931: deba@1931: void lace(const Key& key) { deba@1931: typename Parent::Value& node = Parent::operator[](key); deba@1931: typename std::map::iterator it = first.find(node.value); deba@1931: if (it == first.end()) { deba@1931: node.prev = node.next = INVALID; deba@1931: if (node.next != INVALID) { deba@1931: Parent::operator[](node.next).prev = key; deba@1931: } deba@1931: first.insert(make_pair(node.value, key)); deba@1931: } else { deba@1931: node.prev = INVALID; deba@1931: node.next = it->second; deba@1931: if (node.next != INVALID) { deba@1931: Parent::operator[](node.next).prev = key; deba@1931: } deba@1931: it->second = key; deba@1931: } deba@1931: } deba@1931: deba@1931: public: deba@1931: deba@1931: /// \brief Forward iterator for values. deba@1931: /// deba@1931: /// This iterator is an stl compatible forward deba@1931: /// iterator on the values of the map. The values can deba@1931: /// be accessed in the [beginValue, endValue) range. deba@1931: /// deba@1931: class ValueIterator deba@1931: : public std::iterator { deba@1931: friend class IterableValueMap; deba@1931: private: deba@1931: ValueIterator(typename std::map::const_iterator _it) deba@1931: : it(_it) {} deba@1931: public: deba@1931: deba@1931: ValueIterator() {} deba@1931: deba@1931: ValueIterator& operator++() { ++it; return *this; } deba@1931: ValueIterator operator++(int) { deba@1931: ValueIterator tmp(*this); deba@1931: operator++(); deba@1931: return tmp; deba@1931: } deba@1931: deba@1931: const Value& operator*() const { return it->first; } deba@1931: const Value* operator->() const { return &(it->first); } deba@1931: deba@1931: bool operator==(ValueIterator jt) const { return it == jt.it; } deba@1931: bool operator!=(ValueIterator jt) const { return it != jt.it; } deba@1931: deba@1931: private: deba@1931: typename std::map::const_iterator it; deba@1931: }; deba@1931: deba@1931: /// \brief Returns an iterator to the first value. deba@1931: /// deba@1931: /// Returns an stl compatible iterator to the deba@1931: /// first value of the map. The values of the deba@1931: /// map can be accessed in the [beginValue, endValue) deba@1931: /// range. deba@1931: ValueIterator beginValue() const { deba@1931: return ValueIterator(first.begin()); deba@1931: } deba@1931: deba@1931: /// \brief Returns an iterator after the last value. deba@1931: /// deba@1931: /// Returns an stl compatible iterator after the deba@1931: /// last value of the map. The values of the deba@1931: /// map can be accessed in the [beginValue, endValue) deba@1931: /// range. deba@1931: ValueIterator endValue() const { deba@1931: return ValueIterator(first.end()); deba@1931: } deba@1931: deba@1931: /// \brief Set operation of the map. deba@1931: /// deba@1931: /// Set operation of the map. deba@1931: void set(const Key& key, const Value& value) { deba@1931: unlace(key); deba@1931: Parent::operator[](key).value = value; deba@1931: lace(key); deba@1931: } deba@1931: deba@1931: /// \brief Const subscript operator of the map. deba@1931: /// deba@1931: /// Const subscript operator of the map. deba@1931: const Value& operator[](const Key& key) const { deba@1931: return Parent::operator[](key).value; deba@1931: } deba@1931: deba@1931: /// \brief Iterator for the keys with the same value. deba@1931: /// deba@1931: /// Iterator for the keys with the same value. It works deba@1931: /// like a graph item iterator in the map, it can be converted deba@1931: /// the item type of the map, incremented with \c ++ operator, and deba@1931: /// if the iterator leave the last valid item it will be equal to deba@1931: /// \c INVALID. deba@1931: class ItemIt : public _Item { deba@1931: public: deba@1931: typedef _Item Parent; deba@1931: deba@1931: /// \brief Invalid constructor \& conversion. deba@1931: /// deba@1931: /// This constructor initializes the item to be invalid. deba@1931: /// \sa Invalid for more details. deba@1931: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@1931: deba@1931: /// \brief Creates an iterator with a value. deba@1931: /// deba@1931: /// Creates an iterator with a value. It iterates on the deba@1931: /// keys which have the given value. deba@1931: /// \param map The IterableValueMap deba@1931: /// \param value The value deba@1931: ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { deba@1931: typename std::map::const_iterator it = deba@1931: map.first.find(value); deba@1931: if (it == map.first.end()) { deba@1931: Parent::operator=(INVALID); deba@1931: } else { deba@1931: Parent::operator=(it->second); deba@1931: } deba@1931: } deba@1931: deba@1931: /// \brief Increment operator. deba@1931: /// deba@1931: /// Increment Operator. deba@1931: ItemIt& operator++() { deba@1931: Parent::operator=(_map->IterableValueMap::Parent:: deba@1931: operator[](static_cast(*this)).next); deba@1931: return *this; deba@1931: } deba@1931: deba@1931: deba@1931: private: deba@1931: const IterableValueMap* _map; deba@1931: }; deba@1931: deba@1931: protected: deba@1931: deba@1990: virtual void add(const Key& key) { deba@1990: Parent::add(key); deba@1990: unlace(key); deba@1990: } deba@1990: deba@1990: virtual void add(const std::vector& keys) { deba@1990: Parent::add(keys); deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@1990: lace(keys[i]); deba@1990: } deba@1990: } deba@1990: deba@1931: virtual void erase(const Key& key) { deba@1931: unlace(key); deba@1931: Parent::erase(key); deba@1931: } deba@1931: deba@1931: virtual void erase(const std::vector& keys) { deba@2386: for (int i = 0; i < int(keys.size()); ++i) { deba@1931: unlace(keys[i]); deba@1931: } deba@1931: Parent::erase(keys); deba@1931: } deba@1931: deba@1990: virtual void build() { deba@1990: Parent::build(); deba@2031: for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { deba@1990: lace(it); deba@1990: } deba@1990: } deba@1990: deba@1931: virtual void clear() { deba@1931: first.clear(); deba@1931: Parent::clear(); deba@1931: } deba@1931: deba@1931: private: deba@1931: std::map first; deba@1931: }; deba@1931: alpar@1677: /// @} alpar@1677: } deba@2210: deba@2210: #endif