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 <lemon/traits.h>
deba@1752: #include <lemon/invalid.h>
alpar@1677: #include <vector>
alpar@1677: #include <limits>
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<class BaseMap>
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<Key> 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) { sep--; swap(k,sep); } }
alpar@1677:     void setFalse(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<int>::max()) { }
alpar@1677:       FalseIt &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 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 i<M.sep; }
alpar@1677:     };
alpar@1677:   
alpar@1677:     ///\e
alpar@1677:     class RefType
alpar@1677:     {
alpar@1677:       IterableBoolMap &M;
alpar@1677:       Key k;
alpar@1677:     public:
alpar@1677:       RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
alpar@1677:     
alpar@1677:       operator Value() const 
alpar@1677:       {
alpar@1677: 	return M.isTrue(k);
alpar@1677:       }
alpar@1677:       Value operator = (Value v) const { M.set(k,v); return v; }
alpar@1677:     };
alpar@1677:   
alpar@1677:   public:
alpar@1677:     explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
alpar@1677:     {
alpar@1677:       sep=0;
alpar@1677:       for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
alpar@1677: 	  i!=cref.mapSet().end();
alpar@1677: 	  ++i) {
alpar@1677: 	i->second=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<bool> 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 <class Graph>
alpar@1677:   class IterableBoolNodeMap
alpar@1677:   {
deba@1685:     typename Graph::template NodeMap<int> cmap;
alpar@1677:   
alpar@1677:   public:
alpar@1677:   
deba@1685:     typedef IterableBoolMap<typename Graph::template NodeMap<int> > 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<bool> 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 <class Graph>
alpar@1677:   class IterableBoolEdgeMap
alpar@1677:   {
deba@1685:     typename Graph::template EdgeMap<int> cmap;
alpar@1677:   
alpar@1677:   public:
alpar@1677:   
deba@1685:     typedef IterableBoolMap<typename Graph::template EdgeMap<int> > 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 <typename Item>
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 <typename _Graph, typename _Item>
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<const IterableIntMap&>(_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<Parent&>(*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: }