lemon-0.x: lemon/iterable_maps.h@ea5927cef15c

     1 /* -*- C++ -*-

     2  * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #include <lemon/traits.h>

    18 #include <lemon/invalid.h>

    19 #include <vector>

    20 #include <limits>

    22 ///\ingroup maps

    23 ///\file

    24 ///\brief Maps that makes it possible to iterate through the keys having

    25 ///a certain value

    26 ///

    27 ///

    30 namespace lemon {

    32   ///\todo This is only a static map!

    33   ///\param BaseMap is an interger map.

    34   template<class BaseMap>

    35   class IterableBoolMap

    36   {

    37   public:

    39     typedef typename BaseMap::Key Key;

    40     typedef bool Value;

    42     friend class RefType;

    43     friend class FalseIt;

    44     friend class TrueIt;

    46   private:

    47     BaseMap &cref;

    48     std::vector<Key> vals;

    49     int sep;           //map[e] is true <=> cref[e]>=sep

    51     bool isTrue(Key k) {return cref[k]>=sep;}

    52     void swap(Key k, int s)

    53     {

    54       int ti=cref[k];

    55       Key tk=vals[s];

    56       cref[k]=s; vals[s]=k;

    57       cref[tk]=ti; vals[ti]=tk;

    58     }

    60     void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }

    61     void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }

    63   public:

    64     ///\e

    65     void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}

    67     ///\e

    68     class FalseIt

    69     {

    70       const IterableBoolMap &M;

    71       int i;

    72     public:

    73       explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }

    74       FalseIt(Invalid)

    75 	: M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }

    76       FalseIt &operator++() { ++i; return *this;}

    77       operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }

    78       bool operator !=(Invalid) const { return i<M.sep; }

    79       bool operator ==(Invalid) const { return i>=M.sep; }

    80     };

    81     ///\e

    82     class TrueIt

    83     {

    84       const IterableBoolMap &M;

    85       int i;

    86     public:

    87       explicit TrueIt(const IterableBoolMap &_M)

    88 	: M(_M), i(M.vals.size()-1) { }

    89       TrueIt(Invalid)

    90 	: M(*((IterableBoolMap*)(0))), i(-1) { }

    91       TrueIt &operator++() { --i; return *this;}

    92       operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }

    93       bool operator !=(Invalid) const { return i>=M.sep; }

    94       bool operator ==(Invalid) const { return i<M.sep; }

    95     };

    97     ///\e

    98     class RefType

    99     {

   100       IterableBoolMap &M;

   101       Key k;

   102     public:

   103       RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }

   105       operator Value() const

   106       {

   107 	return M.isTrue(k);

   108       }

   109       Value operator = (Value v) const { M.set(k,v); return v; }

   110     };

   112   public:

   113     explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)

   114     {

   115       sep=0;

   116       for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();

   117 	  i!=cref.mapSet().end();

   118 	  ++i) {

   119 	i->second=sep;

   120 	vals.push_back(i->first);

   121 	sep++;

   122       }

   123       if(init) sep=0;

   124     }

   125     RefType operator[] (Key k) { return RefType(*this,k);}

   126     Value operator[] (Key k) const { return isTrue(k);}

   127   };

   132   /// \addtogroup graph_maps

   133   /// @{

   135   /// Iterable bool NodeMap

   137   /// This map can be used in the same way

   138   /// as the standard NodeMap<bool> of the

   139   /// given graph \c Graph.

   140   /// In addition, this class provides two iterators called \ref TrueIt

   141   /// and \ref FalseIt to iterate through the "true" and "false" nodes.

   142   template <class Graph>

   143   class IterableBoolNodeMap

   144   {

   145     typename Graph::template NodeMap<int> cmap;

   147   public:

   149     typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;

   150     BimType imap;

   153     typedef typename BimType::RefType RefType;

   154     typedef typename Graph::Node Key;

   155     typedef bool Value;

   157     friend class FalseIt;

   158     friend class TrueIt;

   160     ///\e

   161     IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

   163   public:

   164     ///\e

   165     void set(Key k, bool v) { imap.set(k,v);}

   166 #ifdef DOXYGEN

   167     ///\e

   168     bool &operator[](Key k) { return imap[k];}

   169     ///\e

   170     const bool &operator[](Key k) const { return imap[k];}

   171 #else

   172     Value operator[](Key k) const { return imap[k];}

   173     RefType operator[](Key k) { return imap[k];}

   174 #endif

   175     ///Iterator for the "false" nodes

   176     class FalseIt : public BimType::FalseIt

   177     {

   178     public:

   179       explicit FalseIt(const IterableBoolNodeMap &m)

   180 	: BimType::FalseIt(m.imap) { }

   181       FalseIt(Invalid i) : BimType::FalseIt(i) { }

   182     };

   183     ///Iterator for the "true" nodes

   184     class TrueIt : public BimType::TrueIt

   185     {

   186     public:

   187       explicit TrueIt(const IterableBoolNodeMap &m)

   188 	: BimType::TrueIt(m.imap) { }

   189       TrueIt(Invalid i) : BimType::TrueIt(i) { }

   190     };

   191   };

   193   /// Iterable bool EdgeMap

   195   /// This map can be used in the same way

   196   /// as the standard EdgeMap<bool> of the

   197   /// given graph \c Graph.

   198   /// In addition, this class provides two iterators called \ref TrueIt

   199   /// and \ref FalseIt to iterate through the "true" and "false" edges.

   200   template <class Graph>

   201   class IterableBoolEdgeMap

   202   {

   203     typename Graph::template EdgeMap<int> cmap;

   205   public:

   207     typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;

   208     BimType imap;

   211     typedef typename BimType::RefType RefType;

   212     typedef typename Graph::Edge Key;

   213     typedef bool Value;

   215     friend class FalseIt;

   216     friend class TrueIt;

   218     ///\e

   219     IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}

   221   public:

   222     ///\e

   223     void set(Key k, bool v) { imap.set(k,v);}

   224 #ifdef DOXYGEN

   225     ///\e

   226     bool &operator[](Key k) { return imap[k];}

   227     ///\e

   228     const bool &operator[](Key k) const { return imap[k];}

   229 #else

   230     Value operator[](Key k) const { return imap[k];}

   231     RefType operator[](Key k) { return imap[k];}

   232 #endif

   233     ///Iterator for the "false" edges

   234     class FalseIt : public BimType::FalseIt

   235     {

   236     public:

   237       explicit FalseIt(const IterableBoolEdgeMap &m)

   238 	: BimType::FalseIt(m.imap) { }

   239       FalseIt(Invalid i) : BimType::FalseIt(i) { }

   240     };

   241     ///Iterator for the "true" edges

   242     class TrueIt : public BimType::TrueIt

   243     {

   244     public:

   245       explicit TrueIt(const IterableBoolEdgeMap &m)

   246 	: BimType::TrueIt(m.imap) { }

   247       TrueIt(Invalid i) : BimType::TrueIt(i) { }

   248     };

   249   };

   252   namespace _iterable_maps_bits {

   253     template <typename Item>

   254     struct IterableIntMapNode {

   255       IterableIntMapNode() : value(-1) {}

   256       Item prev, next;

   257       int value;

   258     };

   259   }

   261   ///\ingroup maps

   262   ///

   263   /// \brief Dynamic iterable integer map.

   264   ///

   265   /// \todo Document please

   266   template <typename _Graph, typename _Item>

   267   class IterableIntMap : protected ItemSetTraits<_Graph, _Item>

   268   ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {

   269   public:

   270     typedef typename ItemSetTraits<_Graph, _Item>

   271     ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >

   272     ::Parent Parent;

   274     typedef _Item Key;

   275     typedef int Value;

   276     typedef _Graph Graph;

   278     explicit IterableIntMap(const Graph& graph) : Parent(graph) {}

   280   private:

   282     void unlace(const Key& key) {

   283       typename Parent::Value& node = Parent::operator[](key);

   284       if (node.value < 0) return;

   285       if (node.prev != INVALID) {

   286 	Parent::operator[](node.prev).next = node.next;

   287       } else {

   288 	first[node.value] = node.next;

   289       }

   290       if (node.next != INVALID) {

   291 	Parent::operator[](node.next).prev = node.prev;

   292       }

   293       while (!first.empty() && first.back() == INVALID) {

   294 	first.pop_back();

   295       }

   296     }

   298     void lace(const Key& key) {

   299       typename Parent::Value& node = Parent::operator[](key);

   300       if (node.value < 0) return;

   301       if (node.value >= (int)first.size()) {

   302 	first.resize(node.value + 1, INVALID);

   303       }

   304       node.prev = INVALID;

   305       node.next = first[node.value];

   306       if (node.next != INVALID) {

   307 	Parent::operator[](node.next).prev = key;

   308       }

   309       first[node.value] = key;

   310     }

   312   public:

   314     typedef True ReferenceMapTag;

   316     class Reference {

   317       friend class IterableIntMap;

   318     private:

   319       Reference(IterableIntMap& map, const Key& key)

   320 	: _key(key), _map(map) {}

   321     public:

   323       Reference& operator=(const Reference& value) {

   324 	_map.set(_key, (const int&)value);

   325  	return *this;

   326       }

   328       operator const int&() const {

   329 	return static_cast<const IterableIntMap&>(_map)[_key];

   330       }

   332       Reference& operator=(int value) {

   333 	_map.set(_key, value);

   334 	return *this;

   335       }

   336       Reference& operator++() {

   337 	_map.set(_key, _map[_key] + 1);

   338 	return *this;

   339       }

   340       int operator++(int) {

   341 	int value = _map[_key];

   342 	_map.set(_key, value + 1);

   343 	return value;

   344       }

   345       Reference& operator--() {

   346 	_map.set(_key, _map[_key] - 1);

   347 	return *this;

   348       }

   349       int operator--(int) {

   350 	int value = _map[_key];

   351 	_map.set(_key, value - 1);

   352 	return value;

   353       }

   354       Reference& operator+=(int value) {

   355 	_map.set(_key, _map[_key] + value);

   356 	return *this;

   357       }

   358       Reference& operator-=(int value) {

   359 	_map.set(_key, _map[_key] - value);

   360 	return *this;

   361       }

   362       Reference& operator*=(int value) {

   363 	_map.set(_key, _map[_key] * value);

   364 	return *this;

   365       }

   366       Reference& operator/=(int value) {

   367 	_map.set(_key, _map[_key] / value);

   368 	return *this;

   369       }

   370       Reference& operator%=(int value) {

   371 	_map.set(_key, _map[_key] % value);

   372 	return *this;

   373       }

   374       Reference& operator&=(int value) {

   375 	_map.set(_key, _map[_key] & value);

   376 	return *this;

   377       }

   378       Reference& operator|=(int value) {

   379 	_map.set(_key, _map[_key] | value);

   380 	return *this;

   381       }

   382       Reference& operator^=(int value) {

   383 	_map.set(_key, _map[_key] ^ value);

   384 	return *this;

   385       }

   386       Reference& operator<<=(int value) {

   387 	_map.set(_key, _map[_key] << value);

   388 	return *this;

   389       }

   390       Reference& operator>>=(int value) {

   391 	_map.set(_key, _map[_key] >> value);

   392 	return *this;

   393       }

   395     private:

   396       Key _key;

   397       IterableIntMap& _map;

   398     };

   400     typedef const Value& ConstReference;

   402     int size() const {

   403       return (int)first.size();

   404     }

   406     void set(const Key& key, const Value& value) {

   407       unlace(key);

   408       Parent::operator[](key).value = value;

   409       lace(key);

   410     }

   412     const Value& operator[](const Key& key) const {

   413       return Parent::operator[](key).value;

   414     }

   416     Reference operator[](const Key& key) {

   417       return Reference(*this, key);

   418     }

   420     class ItemIt : public _Item {

   421     public:

   422       typedef _Item Parent;

   424       ItemIt(Invalid) : Parent(INVALID), _map(0) {}

   426       ItemIt(const IterableIntMap& map, int value) : _map(&map) {

   427 	if (value < 0 || value >= (int)_map->first.size()) {

   428 	  Parent::operator=(INVALID);

   429 	} else {

   430 	  Parent::operator=(_map->first[value]);

   431 	}

   432       }

   434       ItemIt& operator++() {

   435 	Parent::operator=(_map->IterableIntMap::Parent::

   436 			  operator[](static_cast<Parent&>(*this)).next);

   437 	return *this;

   438       }

   441     private:

   442       const IterableIntMap* _map;

   443     };

   445   protected:

   447     virtual void erase(const Key& key) {

   448       unlace(key);

   449       Parent::erase(key);

   450     }

   452     virtual void clear() {

   453       first.clear();

   454       Parent::clear();

   455     }

   457   private:

   458     std::vector<_Item> first;

   459   };

   461   /// @}

   462 }

author	alpar
	Fri, 04 Nov 2005 16:35:18 +0000
changeset 1773	ea5927cef15c
parent 1752	dce1f28ac595
child 1805	d284f81f02a5
permissions	-rw-r--r--