alpar@1677: /* -*- C++ -*- alpar@1677: * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library alpar@1677: * alpar@1677: * Copyright (C) 2005 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@1752: #include deba@1752: #include alpar@1677: #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 { alpar@1677: alpar@1677: ///\todo This is only a static map! alpar@1677: ///\param BaseMap is an interger map. alpar@1677: template alpar@1677: class IterableBoolMap alpar@1677: { alpar@1677: public: alpar@1677: alpar@1677: typedef typename BaseMap::Key Key; alpar@1677: typedef bool Value; alpar@1677: alpar@1677: friend class RefType; alpar@1677: friend class FalseIt; alpar@1677: friend class TrueIt; alpar@1677: alpar@1677: private: alpar@1677: BaseMap &cref; alpar@1677: std::vector vals; alpar@1677: int sep; //map[e] is true <=> cref[e]>=sep alpar@1677: alpar@1677: bool isTrue(Key k) {return cref[k]>=sep;} alpar@1677: void swap(Key k, int s) alpar@1677: { alpar@1677: int ti=cref[k]; alpar@1677: Key tk=vals[s]; alpar@1677: cref[k]=s; vals[s]=k; alpar@1677: cref[tk]=ti; vals[ti]=tk; alpar@1677: } alpar@1677: alpar@1677: void setTrue(Key k) { if(cref[k]=sep) { swap(k,sep); sep++; } } alpar@1677: alpar@1677: public: alpar@1677: ///\e alpar@1677: void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);} alpar@1677: alpar@1677: ///\e alpar@1677: class FalseIt alpar@1677: { alpar@1677: const IterableBoolMap &M; alpar@1677: int i; alpar@1677: public: alpar@1677: explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { } alpar@1677: FalseIt(Invalid) alpar@1677: : M(*((IterableBoolMap*)(0))), i(std::numeric_limits::max()) { } alpar@1677: FalseIt &operator++() { ++i; return *this;} alpar@1677: operator Key() const { return i=M.sep; } alpar@1677: }; alpar@1677: ///\e alpar@1677: class TrueIt alpar@1677: { alpar@1677: const IterableBoolMap &M; alpar@1677: int i; alpar@1677: public: alpar@1677: explicit TrueIt(const IterableBoolMap &_M) alpar@1677: : M(_M), i(M.vals.size()-1) { } alpar@1677: TrueIt(Invalid) alpar@1677: : M(*((IterableBoolMap*)(0))), i(-1) { } alpar@1677: TrueIt &operator++() { --i; return *this;} alpar@1677: operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; } alpar@1677: bool operator !=(Invalid) const { return i>=M.sep; } alpar@1677: bool operator ==(Invalid) const { return isecond=sep; alpar@1677: vals.push_back(i->first); alpar@1677: sep++; alpar@1677: } alpar@1677: if(init) sep=0; alpar@1677: } alpar@1677: RefType operator[] (Key k) { return RefType(*this,k);} alpar@1677: Value operator[] (Key k) const { return isTrue(k);} alpar@1677: }; alpar@1677: alpar@1677: alpar@1677: alpar@1677: alpar@1677: /// \addtogroup graph_maps alpar@1677: /// @{ alpar@1677: alpar@1677: /// Iterable bool NodeMap alpar@1677: alpar@1677: /// This map can be used in the same way alpar@1677: /// as the standard NodeMap of the alpar@1677: /// given graph \c Graph. alpar@1677: /// In addition, this class provides two iterators called \ref TrueIt alpar@1677: /// and \ref FalseIt to iterate through the "true" and "false" nodes. alpar@1677: template alpar@1677: class IterableBoolNodeMap alpar@1677: { deba@1685: typename Graph::template NodeMap cmap; alpar@1677: alpar@1677: public: alpar@1677: deba@1685: typedef IterableBoolMap > BimType; alpar@1677: BimType imap; alpar@1677: alpar@1677: alpar@1677: typedef typename BimType::RefType RefType; alpar@1677: typedef typename Graph::Node Key; alpar@1677: typedef bool Value; alpar@1677: alpar@1677: friend class FalseIt; alpar@1677: friend class TrueIt; alpar@1677: alpar@1677: ///\e alpar@1677: IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} alpar@1677: alpar@1677: public: alpar@1677: ///\e alpar@1677: void set(Key k, bool v) { imap.set(k,v);} alpar@1677: #ifdef DOXYGEN alpar@1677: ///\e alpar@1677: bool &operator[](Key k) { return imap[k];} alpar@1677: ///\e alpar@1677: const bool &operator[](Key k) const { return imap[k];} alpar@1677: #else alpar@1677: Value operator[](Key k) const { return imap[k];} alpar@1677: RefType operator[](Key k) { return imap[k];} alpar@1677: #endif alpar@1677: ///Iterator for the "false" nodes alpar@1677: class FalseIt : public BimType::FalseIt alpar@1677: { alpar@1677: public: alpar@1677: explicit FalseIt(const IterableBoolNodeMap &m) alpar@1677: : BimType::FalseIt(m.imap) { } alpar@1677: FalseIt(Invalid i) : BimType::FalseIt(i) { } alpar@1677: }; alpar@1677: ///Iterator for the "true" nodes alpar@1677: class TrueIt : public BimType::TrueIt alpar@1677: { alpar@1677: public: alpar@1677: explicit TrueIt(const IterableBoolNodeMap &m) alpar@1677: : BimType::TrueIt(m.imap) { } alpar@1677: TrueIt(Invalid i) : BimType::TrueIt(i) { } alpar@1677: }; alpar@1677: }; alpar@1677: alpar@1677: /// Iterable bool EdgeMap alpar@1677: alpar@1677: /// This map can be used in the same way alpar@1677: /// as the standard EdgeMap of the alpar@1677: /// given graph \c Graph. alpar@1677: /// In addition, this class provides two iterators called \ref TrueIt alpar@1677: /// and \ref FalseIt to iterate through the "true" and "false" edges. alpar@1677: template alpar@1677: class IterableBoolEdgeMap alpar@1677: { deba@1685: typename Graph::template EdgeMap cmap; alpar@1677: alpar@1677: public: alpar@1677: deba@1685: typedef IterableBoolMap > BimType; alpar@1677: BimType imap; alpar@1677: alpar@1677: alpar@1677: typedef typename BimType::RefType RefType; alpar@1677: typedef typename Graph::Edge Key; alpar@1677: typedef bool Value; alpar@1677: alpar@1677: friend class FalseIt; alpar@1677: friend class TrueIt; alpar@1677: alpar@1677: ///\e alpar@1677: IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {} alpar@1677: alpar@1677: public: alpar@1677: ///\e alpar@1677: void set(Key k, bool v) { imap.set(k,v);} alpar@1677: #ifdef DOXYGEN alpar@1677: ///\e alpar@1677: bool &operator[](Key k) { return imap[k];} alpar@1677: ///\e alpar@1677: const bool &operator[](Key k) const { return imap[k];} alpar@1677: #else alpar@1677: Value operator[](Key k) const { return imap[k];} alpar@1677: RefType operator[](Key k) { return imap[k];} alpar@1677: #endif alpar@1677: ///Iterator for the "false" edges alpar@1677: class FalseIt : public BimType::FalseIt alpar@1677: { alpar@1677: public: alpar@1677: explicit FalseIt(const IterableBoolEdgeMap &m) alpar@1677: : BimType::FalseIt(m.imap) { } alpar@1677: FalseIt(Invalid i) : BimType::FalseIt(i) { } alpar@1677: }; alpar@1677: ///Iterator for the "true" edges alpar@1677: class TrueIt : public BimType::TrueIt alpar@1677: { alpar@1677: public: alpar@1677: explicit TrueIt(const IterableBoolEdgeMap &m) alpar@1677: : BimType::TrueIt(m.imap) { } alpar@1677: TrueIt(Invalid i) : BimType::TrueIt(i) { } alpar@1677: }; alpar@1677: }; alpar@1677: deba@1752: deba@1752: namespace _iterable_maps_bits { deba@1752: template deba@1752: struct IterableIntMapNode { deba@1752: IterableIntMapNode() : value(-1) {} deba@1752: Item prev, next; deba@1752: int value; deba@1752: }; deba@1752: } deba@1752: deba@1752: ///\ingroup maps deba@1752: /// deba@1752: /// \brief Dynamic iterable integer map. deba@1752: /// deba@1752: /// \todo Document please deba@1752: template deba@1752: class IterableIntMap : protected ItemSetTraits<_Graph, _Item> deba@1752: ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent { deba@1752: public: deba@1752: typedef typename ItemSetTraits<_Graph, _Item> deba@1752: ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> > deba@1752: ::Parent Parent; deba@1752: deba@1752: typedef _Item Key; deba@1752: typedef int Value; deba@1752: typedef _Graph Graph; deba@1752: deba@1752: IterableIntMap(const Graph& graph) : Parent(graph) {} 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@1752: 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@1752: typedef True ReferenceMapTag; deba@1752: 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@1752: _map.set(_key, (const int&)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@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@1752: deba@1752: typedef const Value& ConstReference; deba@1752: deba@1752: int size() const { deba@1752: return (int)first.size(); deba@1752: } deba@1752: 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@1752: const Value& operator[](const Key& key) const { deba@1752: return Parent::operator[](key).value; deba@1752: } deba@1752: deba@1752: Reference operator[](const Key& key) { deba@1752: return Reference(*this, key); deba@1752: } deba@1752: deba@1752: class ItemIt : public _Item { deba@1752: public: deba@1752: typedef _Item Parent; deba@1752: deba@1752: ItemIt(Invalid) : Parent(INVALID), _map(0) {} deba@1752: deba@1752: ItemIt(const IterableIntMap& map, int value) : _map(&map) { deba@1752: 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@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@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: alpar@1677: /// @} alpar@1677: }