lemon-0.x: lemon/iterable_maps.h@029cc4f638d1

     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   ///\todo Undocumented.

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

    35   template<class BaseMap>

    36   class IterableBoolMap

    37   {

    38   public:

    40     typedef typename BaseMap::Key Key;

    41     typedef bool Value;

    43     friend class RefType;

    44     friend class FalseIt;

    45     friend class TrueIt;

    47   private:

    48     BaseMap &cref;

    49     std::vector<Key> vals;

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

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

    53     void swap(Key k, int s)

    54     {

    55       int ti=cref[k];

    56       Key tk=vals[s];

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

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

    59     }

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

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

    64   public:

    65     ///\e

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

    67     ///Number of \c true items in the map

    69     ///Returns the number of \c true values in the map.

    70     ///This is a constant time operation.

    71     int countTrue() { return vals.size()-sep; }

    72     ///Number of \c false items in the map

    74     ///Returns the number of \c false values in the map.

    75     ///This is a constant time operation.

    76     int countFalse() { return sep; }

    78     ///\e

    79     class FalseIt

    80     {

    81       const IterableBoolMap &M;

    82       int i;

    83     public:

    84       ///\e

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

    86       ///\e

    87       FalseIt(Invalid)

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

    89       ///\e

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

    91       ///\e

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

    93       ///\e

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

    95       ///\e

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

    97     };

    98     ///\e

    99     class TrueIt

   100     {

   101       const IterableBoolMap &M;

   102       int i;

   103     public:

   104       ///\e

   105       explicit TrueIt(const IterableBoolMap &_M)

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

   107       ///\e

   108       TrueIt(Invalid)

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

   110       ///\e

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

   112       ///\e

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

   114       ///\e

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

   116       ///\e

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

   118     };

   120     ///\e

   121     class RefType

   122     {

   123       IterableBoolMap &M;

   124       Key k;

   125     public:

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

   128       operator Value() const

   129       {

   130 	return M.isTrue(k);

   131       }

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

   133     };

   135   public:

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

   137     {

   138       sep=0;

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

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

   141 	  ++i) {

   142 	i->second=sep;

   143 	vals.push_back(i->first);

   144 	sep++;

   145       }

   146       if(init) sep=0;

   147     }

   148     ///\e

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

   150     ///\e

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

   152   };

   157   /// \addtogroup graph_maps

   158   /// @{

   160   /// Iterable bool NodeMap

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

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

   164   /// given graph \c Graph.

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

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

   167   template <class Graph>

   168   class IterableBoolNodeMap

   169   {

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

   172   public:

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

   175     BimType imap;

   178     typedef typename BimType::RefType RefType;

   179     typedef typename Graph::Node Key;

   180     typedef bool Value;

   182     friend class FalseIt;

   183     friend class TrueIt;

   185     ///\e

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

   188   public:

   189     ///\e

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

   191     ///Number of \c true items in the map

   193     ///Returns the number of \c true values in the map.

   194     ///This is a constant time operation.

   195     int countTrue() { return imap.countTrue(); }

   196     ///Number of \c false items in the map

   198     ///Returns the number of \c false values in the map.

   199     ///This is a constant time operation.

   200     int countFalse() { return imap.countFalse(); }

   201 #ifdef DOXYGEN

   202     ///\e

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

   204     ///\e

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

   206 #else

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

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

   209 #endif

   210     ///Iterator for the "false" nodes

   211     class FalseIt : public BimType::FalseIt

   212     {

   213     public:

   214       ///\e

   215       explicit FalseIt(const IterableBoolNodeMap &m)

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

   217       ///\e

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

   219     };

   220     ///Iterator for the "true" nodes

   221     class TrueIt : public BimType::TrueIt

   222     {

   223     public:

   224       ///\e

   225       explicit TrueIt(const IterableBoolNodeMap &m)

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

   227       ///\e

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

   229     };

   230   };

   232   /// Iterable bool EdgeMap

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

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

   236   /// given graph \c Graph.

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

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

   239   template <class Graph>

   240   class IterableBoolEdgeMap

   241   {

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

   244   public:

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

   247     BimType imap;

   250     typedef typename BimType::RefType RefType;

   251     typedef typename Graph::Edge Key;

   252     typedef bool Value;

   254     friend class FalseIt;

   255     friend class TrueIt;

   257     ///\e

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

   260   public:

   261     ///\e

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

   263     ///Returns the number of \c true values in the map.

   264     ///This is a constant time operation.

   265     int countTrue() { return imap.countTrue(); }

   266     ///Number of \c false items in the map

   268     ///Returns the number of \c false values in the map.

   269     ///This is a constant time operation.

   270     int countFalse() { return imap.countFalse(); }

   271 #ifdef DOXYGEN

   272     ///\e

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

   274     ///\e

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

   276 #else

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

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

   279 #endif

   280     ///Iterator for the "false" edges

   281     class FalseIt : public BimType::FalseIt

   282     {

   283     public:

   284       ///\e

   285       explicit FalseIt(const IterableBoolEdgeMap &m)

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

   287       ///\e

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

   289     };

   290     ///Iterator for the "true" edges

   291     class TrueIt : public BimType::TrueIt

   292     {

   293     public:

   294       ///\e

   295       explicit TrueIt(const IterableBoolEdgeMap &m)

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

   297       ///\e

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

   299     };

   300   };

   303   namespace _iterable_maps_bits {

   304     template <typename Item>

   305     struct IterableIntMapNode {

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

   307       Item prev, next;

   308       int value;

   309     };

   310   }

   312   ///\ingroup maps

   313   ///

   314   /// \brief Dynamic iterable integer map.

   315   ///

   316   /// \todo Document please

   317   template <typename _Graph, typename _Item>

   318   class IterableIntMap : protected ItemSetTraits<_Graph, _Item>

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

   320   public:

   321     typedef typename ItemSetTraits<_Graph, _Item>

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

   323     ::Parent Parent;

   325     typedef _Item Key;

   326     typedef int Value;

   327     typedef _Graph Graph;

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

   331   private:

   333     void unlace(const Key& key) {

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

   335       if (node.value < 0) return;

   336       if (node.prev != INVALID) {

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

   338       } else {

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

   340       }

   341       if (node.next != INVALID) {

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

   343       }

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

   345 	first.pop_back();

   346       }

   347     }

   349     void lace(const Key& key) {

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

   351       if (node.value < 0) return;

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

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

   354       }

   355       node.prev = INVALID;

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

   357       if (node.next != INVALID) {

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

   359       }

   360       first[node.value] = key;

   361     }

   363   public:

   365     typedef True ReferenceMapTag;

   367     class Reference {

   368       friend class IterableIntMap;

   369     private:

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

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

   372     public:

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

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

   376  	return *this;

   377       }

   379       operator const int&() const {

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

   381       }

   383       Reference& operator=(int value) {

   384 	_map.set(_key, value);

   385 	return *this;

   386       }

   387       Reference& operator++() {

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

   389 	return *this;

   390       }

   391       int operator++(int) {

   392 	int value = _map[_key];

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

   394 	return value;

   395       }

   396       Reference& operator--() {

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

   398 	return *this;

   399       }

   400       int operator--(int) {

   401 	int value = _map[_key];

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

   403 	return value;

   404       }

   405       Reference& operator+=(int value) {

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

   407 	return *this;

   408       }

   409       Reference& operator-=(int value) {

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

   411 	return *this;

   412       }

   413       Reference& operator*=(int value) {

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

   415 	return *this;

   416       }

   417       Reference& operator/=(int value) {

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

   419 	return *this;

   420       }

   421       Reference& operator%=(int value) {

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

   423 	return *this;

   424       }

   425       Reference& operator&=(int value) {

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

   427 	return *this;

   428       }

   429       Reference& operator|=(int value) {

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

   431 	return *this;

   432       }

   433       Reference& operator^=(int value) {

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

   435 	return *this;

   436       }

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

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

   439 	return *this;

   440       }

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

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

   443 	return *this;

   444       }

   446     private:

   447       Key _key;

   448       IterableIntMap& _map;

   449     };

   451     typedef const Value& ConstReference;

   453     int size() const {

   454       return (int)first.size();

   455     }

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

   458       unlace(key);

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

   460       lace(key);

   461     }

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

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

   465     }

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

   468       return Reference(*this, key);

   469     }

   471     class ItemIt : public _Item {

   472     public:

   473       typedef _Item Parent;

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

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

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

   479 	  Parent::operator=(INVALID);

   480 	} else {

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

   482 	}

   483       }

   485       ItemIt& operator++() {

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

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

   488 	return *this;

   489       }

   492     private:

   493       const IterableIntMap* _map;

   494     };

   496   protected:

   498     virtual void erase(const Key& key) {

   499       unlace(key);

   500       Parent::erase(key);

   501     }

   503     virtual void clear() {

   504       first.clear();

   505       Parent::clear();

   506     }

   508   private:

   509     std::vector<_Item> first;

   510   };

   512   /// @}

   513 }

author	marci
	Wed, 16 Nov 2005 14:46:22 +0000
changeset 1809	029cc4f638d1
parent 1759	0bb3fb3baffd
child 1810	474d093466a5
permissions	-rw-r--r--