/* -*- C++ -*- * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include #include #include ///\ingroup maps ///\file ///\brief Maps that makes it possible to iterate through the keys having ///a certain value /// /// namespace lemon { ///\todo This is only a static map! ///\todo Undocumented. ///\param BaseMap is an interger map. template class IterableBoolMap { public: typedef typename BaseMap::Key Key; typedef bool Value; friend class RefType; friend class FalseIt; friend class TrueIt; private: BaseMap &cref; std::vector vals; int sep; //map[e] is true <=> cref[e]>=sep bool isTrue(Key k) {return cref[k]>=sep;} void swap(Key k, int s) { int ti=cref[k]; Key tk=vals[s]; cref[k]=s; vals[s]=k; cref[tk]=ti; vals[ti]=tk; } void setTrue(Key k) { if(cref[k]=sep) { swap(k,sep); sep++; } } public: ///\e void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);} ///Number of \c true items in the map ///Returns the number of \c true values in the map. ///This is a constant time operation. int countTrue() { return vals.size()-sep; } ///Number of \c false items in the map ///Returns the number of \c false values in the map. ///This is a constant time operation. int countFalse() { return sep; } ///\e class FalseIt { const IterableBoolMap &M; int i; public: ///\e explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { } ///\e FalseIt(Invalid) : M(*((IterableBoolMap*)(0))), i(std::numeric_limits::max()) { } ///\e FalseIt &operator++() { ++i; return *this;} ///\e operator Key() const { return i=M.sep; } }; ///\e class TrueIt { const IterableBoolMap &M; int i; public: ///\e explicit TrueIt(const IterableBoolMap &_M) : M(_M), i(M.vals.size()-1) { } ///\e TrueIt(Invalid) : M(*((IterableBoolMap*)(0))), i(-1) { } ///\e TrueIt &operator++() { --i; return *this;} ///\e operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; } ///\e bool operator !=(Invalid) const { return i>=M.sep; } ///\e bool operator ==(Invalid) const { return i of the /// given graph \c Graph. /// In addition, this class provides two iterators called \ref TrueIt /// and \ref FalseIt to iterate through the "true" and "false" nodes. template class IterableBoolNodeMap { typename Graph::template NodeMap cmap; public: typedef IterableBoolMap > BimType; BimType imap; typedef typename BimType::RefType RefType; typedef typename Graph::Node Key; typedef bool Value; friend class FalseIt; friend class TrueIt; ///\e IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} public: ///\e void set(Key k, bool v) { imap.set(k,v);} ///Number of \c true items in the map ///Returns the number of \c true values in the map. ///This is a constant time operation. int countTrue() { return imap.countTrue(); } ///Number of \c false items in the map ///Returns the number of \c false values in the map. ///This is a constant time operation. int countFalse() { return imap.countFalse(); } #ifdef DOXYGEN ///\e bool &operator[](Key k) { return imap[k];} ///\e const bool &operator[](Key k) const { return imap[k];} #else Value operator[](Key k) const { return imap[k];} RefType operator[](Key k) { return imap[k];} #endif ///Iterator for the "false" nodes class FalseIt : public BimType::FalseIt { public: ///\e explicit FalseIt(const IterableBoolNodeMap &m) : BimType::FalseIt(m.imap) { } ///\e FalseIt(Invalid i) : BimType::FalseIt(i) { } }; ///Iterator for the "true" nodes class TrueIt : public BimType::TrueIt { public: ///\e explicit TrueIt(const IterableBoolNodeMap &m) : BimType::TrueIt(m.imap) { } ///\e TrueIt(Invalid i) : BimType::TrueIt(i) { } }; }; /// Iterable bool UpperNodeMap /// This map can be used in the same way /// as the standard UpperNodeMap of the /// given graph \c Graph. /// In addition, this class provides two iterators called \ref TrueIt /// and \ref FalseIt to iterate through the "true" and "false" nodes. template class IterableBoolUpperNodeMap { typename Graph::template UpperNodeMap cmap; public: typedef IterableBoolMap > BimType; BimType imap; typedef typename BimType::RefType RefType; typedef typename Graph::Node Key; typedef bool Value; friend class FalseIt; friend class TrueIt; ///\e IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} public: ///\e void set(Key k, bool v) { imap.set(k,v);} ///Number of \c true items in the map ///Returns the number of \c true values in the map. ///This is a constant time operation. int countTrue() { return imap.countTrue(); } ///Number of \c false items in the map ///Returns the number of \c false values in the map. ///This is a constant time operation. int countFalse() { return imap.countFalse(); } #ifdef DOXYGEN ///\e bool &operator[](Key k) { return imap[k];} ///\e const bool &operator[](Key k) const { return imap[k];} #else Value operator[](Key k) const { return imap[k];} RefType operator[](Key k) { return imap[k];} #endif ///Iterator for the "false" nodes class FalseIt : public BimType::FalseIt { public: ///\e explicit FalseIt(const IterableBoolUpperNodeMap &m) : BimType::FalseIt(m.imap) { } ///\e FalseIt(Invalid i) : BimType::FalseIt(i) { } }; ///Iterator for the "true" nodes class TrueIt : public BimType::TrueIt { public: ///\e explicit TrueIt(const IterableBoolUpperNodeMap &m) : BimType::TrueIt(m.imap) { } ///\e TrueIt(Invalid i) : BimType::TrueIt(i) { } }; }; /// Iterable bool LowerNodeMap /// This map can be used in the same way /// as the standard LowerNodeMap of the /// given graph \c Graph. /// In addition, this class provides two iterators called \ref TrueIt /// and \ref FalseIt to iterate through the "true" and "false" nodes. template class IterableBoolLowerNodeMap { typename Graph::template LowerNodeMap cmap; public: typedef IterableBoolMap > BimType; BimType imap; typedef typename BimType::RefType RefType; typedef typename Graph::Node Key; typedef bool Value; friend class FalseIt; friend class TrueIt; ///\e IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} public: ///\e void set(Key k, bool v) { imap.set(k,v);} ///Number of \c true items in the map ///Returns the number of \c true values in the map. ///This is a constant time operation. int countTrue() { return imap.countTrue(); } ///Number of \c false items in the map ///Returns the number of \c false values in the map. ///This is a constant time operation. int countFalse() { return imap.countFalse(); } #ifdef DOXYGEN ///\e bool &operator[](Key k) { return imap[k];} ///\e const bool &operator[](Key k) const { return imap[k];} #else Value operator[](Key k) const { return imap[k];} RefType operator[](Key k) { return imap[k];} #endif ///Iterator for the "false" nodes class FalseIt : public BimType::FalseIt { public: ///\e explicit FalseIt(const IterableBoolLowerNodeMap &m) : BimType::FalseIt(m.imap) { } ///\e FalseIt(Invalid i) : BimType::FalseIt(i) { } }; ///Iterator for the "true" nodes class TrueIt : public BimType::TrueIt { public: ///\e explicit TrueIt(const IterableBoolLowerNodeMap &m) : BimType::TrueIt(m.imap) { } ///\e TrueIt(Invalid i) : BimType::TrueIt(i) { } }; }; /// Iterable bool EdgeMap /// This map can be used in the same way /// as the standard EdgeMap of the /// given graph \c Graph. /// In addition, this class provides two iterators called \ref TrueIt /// and \ref FalseIt to iterate through the "true" and "false" edges. template class IterableBoolEdgeMap { typename Graph::template EdgeMap cmap; public: typedef IterableBoolMap > BimType; BimType imap; typedef typename BimType::RefType RefType; typedef typename Graph::Edge Key; typedef bool Value; friend class FalseIt; friend class TrueIt; ///\e IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} public: ///\e void set(Key k, bool v) { imap.set(k,v);} ///Returns the number of \c true values in the map. ///This is a constant time operation. int countTrue() { return imap.countTrue(); } ///Number of \c false items in the map ///Returns the number of \c false values in the map. ///This is a constant time operation. int countFalse() { return imap.countFalse(); } #ifdef DOXYGEN ///\e bool &operator[](Key k) { return imap[k];} ///\e const bool &operator[](Key k) const { return imap[k];} #else Value operator[](Key k) const { return imap[k];} RefType operator[](Key k) { return imap[k];} #endif ///Iterator for the "false" edges class FalseIt : public BimType::FalseIt { public: ///\e explicit FalseIt(const IterableBoolEdgeMap &m) : BimType::FalseIt(m.imap) { } ///\e FalseIt(Invalid i) : BimType::FalseIt(i) { } }; ///Iterator for the "true" edges class TrueIt : public BimType::TrueIt { public: ///\e explicit TrueIt(const IterableBoolEdgeMap &m) : BimType::TrueIt(m.imap) { } ///\e TrueIt(Invalid i) : BimType::TrueIt(i) { } }; }; namespace _iterable_maps_bits { template struct IterableIntMapNode { IterableIntMapNode() {} IterableIntMapNode(int _value) : value(_value) {} Item prev, next; int value; }; } ///\ingroup maps /// /// \brief Dynamic iterable integer map. /// /// This class provides a special graph map type which can store /// for each graph item(node, edge, etc.) an integer value. For each /// non negative value it is possible to iterate on the keys which /// mapped to the given value. /// /// \param _Graph The graph type. /// \param _Item One of the graph's item type, the key of the map. template class IterableIntMap : protected ItemSetTraits<_Graph, _Item> ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent { public: typedef typename ItemSetTraits<_Graph, _Item> ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> > ::Parent Parent; /// The key type typedef _Item Key; /// The value type typedef int Value; /// The graph type typedef _Graph Graph; /// \brief Constructor of the Map. /// /// Constructor of the Map. It set all values -1. explicit IterableIntMap(const Graph& graph) : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {} /// \brief Constructor of the Map with a given value. /// /// Constructor of the Map with a given value. explicit IterableIntMap(const Graph& graph, int value) : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) { if (value >= 0) { for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { lace(it); } } } private: void unlace(const Key& key) { typename Parent::Value& node = Parent::operator[](key); if (node.value < 0) return; if (node.prev != INVALID) { Parent::operator[](node.prev).next = node.next; } else { first[node.value] = node.next; } if (node.next != INVALID) { Parent::operator[](node.next).prev = node.prev; } while (!first.empty() && first.back() == INVALID) { first.pop_back(); } } void lace(const Key& key) { typename Parent::Value& node = Parent::operator[](key); if (node.value < 0) return; if (node.value >= (int)first.size()) { first.resize(node.value + 1, INVALID); } node.prev = INVALID; node.next = first[node.value]; if (node.next != INVALID) { Parent::operator[](node.next).prev = key; } first[node.value] = key; } public: /// Indicates that the map if reference map. typedef True ReferenceMapTag; /// \brief Refernce to the value of the map. /// /// This class is near to similar to the int type. It can /// be converted to int and it has the same operators. class Reference { friend class IterableIntMap; private: Reference(IterableIntMap& map, const Key& key) : _key(key), _map(map) {} public: Reference& operator=(const Reference& value) { _map.set(_key, (const int&)value); return *this; } operator const int&() const { return static_cast(_map)[_key]; } Reference& operator=(int value) { _map.set(_key, value); return *this; } Reference& operator++() { _map.set(_key, _map[_key] + 1); return *this; } int operator++(int) { int value = _map[_key]; _map.set(_key, value + 1); return value; } Reference& operator--() { _map.set(_key, _map[_key] - 1); return *this; } int operator--(int) { int value = _map[_key]; _map.set(_key, value - 1); return value; } Reference& operator+=(int value) { _map.set(_key, _map[_key] + value); return *this; } Reference& operator-=(int value) { _map.set(_key, _map[_key] - value); return *this; } Reference& operator*=(int value) { _map.set(_key, _map[_key] * value); return *this; } Reference& operator/=(int value) { _map.set(_key, _map[_key] / value); return *this; } Reference& operator%=(int value) { _map.set(_key, _map[_key] % value); return *this; } Reference& operator&=(int value) { _map.set(_key, _map[_key] & value); return *this; } Reference& operator|=(int value) { _map.set(_key, _map[_key] | value); return *this; } Reference& operator^=(int value) { _map.set(_key, _map[_key] ^ value); return *this; } Reference& operator<<=(int value) { _map.set(_key, _map[_key] << value); return *this; } Reference& operator>>=(int value) { _map.set(_key, _map[_key] >> value); return *this; } private: Key _key; IterableIntMap& _map; }; /// The const reference type. typedef const Value& ConstReference; /// \brief Gives back the maximal value plus one. /// /// Gives back the maximal value plus one. int size() const { return (int)first.size(); } /// \brief Set operation of the map. /// /// Set operation of the map. void set(const Key& key, const Value& value) { unlace(key); Parent::operator[](key).value = value; lace(key); } /// \brief Const subscript operator of the map. /// /// Const subscript operator of the map. const Value& operator[](const Key& key) const { return Parent::operator[](key).value; } /// \brief Subscript operator of the map. /// /// Subscript operator of the map. Reference operator[](const Key& key) { return Reference(*this, key); } /// \brief Iterator for the keys with the same value. /// /// Iterator for the keys with the same value. It works /// like a graph item iterator in the map, it can be converted /// the item type of the map, incremented with \c ++ operator, and /// if the iterator leave the last valid item it will be equal to /// \c INVALID. class ItemIt : public _Item { public: typedef _Item Parent; /// \brief Invalid constructor \& conversion. /// /// This constructor initializes the item to be invalid. /// \sa Invalid for more details. ItemIt(Invalid) : Parent(INVALID), _map(0) {} /// \brief Creates an iterator with a value. /// /// Creates an iterator with a value. It iterates on the /// keys which have the given value. /// \param map The IterableIntMap /// \param value The value ItemIt(const IterableIntMap& map, int value) : _map(&map) { if (value < 0 || value >= (int)_map->first.size()) { Parent::operator=(INVALID); } else { Parent::operator=(_map->first[value]); } } /// \brief Increment operator. /// /// Increment Operator. ItemIt& operator++() { Parent::operator=(_map->IterableIntMap::Parent:: operator[](static_cast(*this)).next); return *this; } private: const IterableIntMap* _map; }; protected: virtual void erase(const Key& key) { unlace(key); Parent::erase(key); } virtual void clear() { first.clear(); Parent::clear(); } private: std::vector<_Item> first; }; /// @} }