lemon-0.x: lemon/iterable_maps.h@1d384b30157f

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

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

     3  *

     4  * Copyright (C) 2006 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::MapIt i(cref);i!=INVALID; ++i) {

   140 	i.set(sep);

   141 	vals.push_back(i);

   142 	sep++;

   143       }

   144       if(init) sep=0;

   145     }

   146     ///\e

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

   148     ///\e

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

   150   };

   155   /// \addtogroup graph_maps

   156   /// @{

   158   /// Iterable bool NodeMap

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

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

   162   /// given graph \c Graph.

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

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

   165   template <class Graph>

   166   class IterableBoolNodeMap

   167   {

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

   170   public:

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

   173     BimType imap;

   176     typedef typename BimType::RefType RefType;

   177     typedef typename Graph::Node Key;

   178     typedef bool Value;

   180     friend class FalseIt;

   181     friend class TrueIt;

   183     ///\e

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

   186   public:

   187     ///\e

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

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

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

   192     ///This is a constant time operation.

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

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

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

   197     ///This is a constant time operation.

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

   199 #ifdef DOXYGEN

   200     ///\e

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

   202     ///\e

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

   204 #else

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

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

   207 #endif

   208     ///Iterator for the "false" nodes

   209     class FalseIt : public BimType::FalseIt

   210     {

   211     public:

   212       ///\e

   213       explicit FalseIt(const IterableBoolNodeMap &m)

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

   215       ///\e

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

   217     };

   218     ///Iterator for the "true" nodes

   219     class TrueIt : public BimType::TrueIt

   220     {

   221     public:

   222       ///\e

   223       explicit TrueIt(const IterableBoolNodeMap &m)

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

   225       ///\e

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

   227     };

   228   };

   230   /// Iterable bool UpperNodeMap

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

   233   /// as the standard UpperNodeMap<bool> of the

   234   /// given graph \c Graph.

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

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

   237   template <class Graph>

   238   class IterableBoolUpperNodeMap

   239   {

   240     typename Graph::template UpperNodeMap<int> cmap;

   242   public:

   244     typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;

   245     BimType imap;

   248     typedef typename BimType::RefType RefType;

   249     typedef typename Graph::Node Key;

   250     typedef bool Value;

   252     friend class FalseIt;

   253     friend class TrueIt;

   255     ///\e

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

   258   public:

   259     ///\e

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

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

   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" nodes

   281     class FalseIt : public BimType::FalseIt

   282     {

   283     public:

   284       ///\e

   285       explicit FalseIt(const IterableBoolUpperNodeMap &m)

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

   287       ///\e

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

   289     };

   290     ///Iterator for the "true" nodes

   291     class TrueIt : public BimType::TrueIt

   292     {

   293     public:

   294       ///\e

   295       explicit TrueIt(const IterableBoolUpperNodeMap &m)

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

   297       ///\e

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

   299     };

   300   };

   302   /// Iterable bool LowerNodeMap

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

   305   /// as the standard LowerNodeMap<bool> of the

   306   /// given graph \c Graph.

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

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

   309   template <class Graph>

   310   class IterableBoolLowerNodeMap

   311   {

   312     typename Graph::template LowerNodeMap<int> cmap;

   314   public:

   316     typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;

   317     BimType imap;

   320     typedef typename BimType::RefType RefType;

   321     typedef typename Graph::Node Key;

   322     typedef bool Value;

   324     friend class FalseIt;

   325     friend class TrueIt;

   327     ///\e

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

   330   public:

   331     ///\e

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

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

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

   336     ///This is a constant time operation.

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

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

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

   341     ///This is a constant time operation.

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

   343 #ifdef DOXYGEN

   344     ///\e

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

   346     ///\e

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

   348 #else

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

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

   351 #endif

   352     ///Iterator for the "false" nodes

   353     class FalseIt : public BimType::FalseIt

   354     {

   355     public:

   356       ///\e

   357       explicit FalseIt(const IterableBoolLowerNodeMap &m)

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

   359       ///\e

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

   361     };

   362     ///Iterator for the "true" nodes

   363     class TrueIt : public BimType::TrueIt

   364     {

   365     public:

   366       ///\e

   367       explicit TrueIt(const IterableBoolLowerNodeMap &m)

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

   369       ///\e

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

   371     };

   372   };

   374   /// Iterable bool EdgeMap

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

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

   378   /// given graph \c Graph.

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

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

   381   template <class Graph>

   382   class IterableBoolEdgeMap

   383   {

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

   386   public:

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

   389     BimType imap;

   392     typedef typename BimType::RefType RefType;

   393     typedef typename Graph::Edge Key;

   394     typedef bool Value;

   396     friend class FalseIt;

   397     friend class TrueIt;

   399     ///\e

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

   402   public:

   403     ///\e

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

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

   406     ///This is a constant time operation.

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

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

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

   411     ///This is a constant time operation.

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

   413 #ifdef DOXYGEN

   414     ///\e

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

   416     ///\e

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

   418 #else

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

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

   421 #endif

   422     ///Iterator for the "false" edges

   423     class FalseIt : public BimType::FalseIt

   424     {

   425     public:

   426       ///\e

   427       explicit FalseIt(const IterableBoolEdgeMap &m)

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

   429       ///\e

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

   431     };

   432     ///Iterator for the "true" edges

   433     class TrueIt : public BimType::TrueIt

   434     {

   435     public:

   436       ///\e

   437       explicit TrueIt(const IterableBoolEdgeMap &m)

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

   439       ///\e

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

   441     };

   442   };

   445   namespace _iterable_maps_bits {

   446     template <typename Item>

   447     struct IterableIntMapNode {

   448       IterableIntMapNode() {}

   449       IterableIntMapNode(int _value) : value(_value) {}

   450       Item prev, next;

   451       int value;

   452     };

   453   }

   455   ///\ingroup maps

   456   ///

   457   /// \brief Dynamic iterable integer map.

   458   ///

   459   /// This class provides a special graph map type which can store

   460   /// for each graph item(node, edge, etc.) an integer value. For each

   461   /// non negative value it is possible to iterate on the keys which

   462   /// mapped to the given value.

   463   ///

   464   /// \param _Graph The graph type.

   465   /// \param _Item One of the graph's item type, the key of the map.

   466   template <typename _Graph, typename _Item>

   467   class IterableIntMap : protected ItemSetTraits<_Graph, _Item>

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

   469   public:

   470     typedef typename ItemSetTraits<_Graph, _Item>

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

   472     ::Parent Parent;

   474     /// The key type

   475     typedef _Item Key;

   476     /// The value type

   477     typedef int Value;

   478     /// The graph type

   479     typedef _Graph Graph;

   481     /// \brief Constructor of the Map.

   482     ///

   483     /// Constructor of the Map. It set all values -1.

   484     explicit IterableIntMap(const Graph& graph)

   485       : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}

   487     /// \brief Constructor of the Map with a given value.

   488     ///

   489     /// Constructor of the Map with a given value.

   490     explicit IterableIntMap(const Graph& graph, int value)

   491       : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {

   492       if (value >= 0) {

   493 	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {

   494 	  lace(it);

   495 	}

   496       }

   497     }

   499   private:

   501     void unlace(const Key& key) {

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

   503       if (node.value < 0) return;

   504       if (node.prev != INVALID) {

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

   506       } else {

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

   508       }

   509       if (node.next != INVALID) {

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

   511       }

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

   513 	first.pop_back();

   514       }

   515     }

   517     void lace(const Key& key) {

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

   519       if (node.value < 0) return;

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

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

   522       }

   523       node.prev = INVALID;

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

   525       if (node.next != INVALID) {

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

   527       }

   528       first[node.value] = key;

   529     }

   531   public:

   533     /// Indicates that the map if reference map.

   534     typedef True ReferenceMapTag;

   536     /// \brief Refernce to the value of the map.

   537     ///

   538     /// This class is near to similar to the int type. It can

   539     /// be converted to int and it has the same operators.

   540     class Reference {

   541       friend class IterableIntMap;

   542     private:

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

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

   545     public:

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

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

   549  	return *this;

   550       }

   552       operator const int&() const {

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

   554       }

   556       Reference& operator=(int value) {

   557 	_map.set(_key, value);

   558 	return *this;

   559       }

   560       Reference& operator++() {

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

   562 	return *this;

   563       }

   564       int operator++(int) {

   565 	int value = _map[_key];

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

   567 	return value;

   568       }

   569       Reference& operator--() {

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

   571 	return *this;

   572       }

   573       int operator--(int) {

   574 	int value = _map[_key];

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

   576 	return value;

   577       }

   578       Reference& operator+=(int value) {

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

   580 	return *this;

   581       }

   582       Reference& operator-=(int value) {

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

   584 	return *this;

   585       }

   586       Reference& operator*=(int value) {

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

   588 	return *this;

   589       }

   590       Reference& operator/=(int value) {

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

   592 	return *this;

   593       }

   594       Reference& operator%=(int value) {

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

   596 	return *this;

   597       }

   598       Reference& operator&=(int value) {

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

   600 	return *this;

   601       }

   602       Reference& operator|=(int value) {

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

   604 	return *this;

   605       }

   606       Reference& operator^=(int value) {

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

   608 	return *this;

   609       }

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

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

   612 	return *this;

   613       }

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

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

   616 	return *this;

   617       }

   619     private:

   620       Key _key;

   621       IterableIntMap& _map;

   622     };

   624     /// The const reference type.

   625     typedef const Value& ConstReference;

   627     /// \brief Gives back the maximal value plus one.

   628     ///

   629     /// Gives back the maximal value plus one.

   630     int size() const {

   631       return (int)first.size();

   632     }

   634     /// \brief Set operation of the map.

   635     ///

   636     /// Set operation of the map.

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

   638       unlace(key);

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

   640       lace(key);

   641     }

   643     /// \brief Const subscript operator of the map.

   644     ///

   645     /// Const subscript operator of the map.

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

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

   648     }

   650     /// \brief Subscript operator of the map.

   651     ///

   652     /// Subscript operator of the map.

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

   654       return Reference(*this, key);

   655     }

   657     /// \brief Iterator for the keys with the same value.

   658     ///

   659     /// Iterator for the keys with the same value. It works

   660     /// like a graph item iterator in the map, it can be converted

   661     /// the item type of the map, incremented with \c ++ operator, and

   662     /// if the iterator leave the last valid item it will be equal to

   663     /// \c INVALID.

   664     class ItemIt : public _Item {

   665     public:

   666       typedef _Item Parent;

   668       /// \brief Invalid constructor \& conversion.

   669       ///

   670       /// This constructor initializes the item to be invalid.

   671       /// \sa Invalid for more details.

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

   674       /// \brief Creates an iterator with a value.

   675       ///

   676       /// Creates an iterator with a value. It iterates on the

   677       /// keys which have the given value.

   678       /// \param map The IterableIntMap

   679       /// \param value The value

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

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

   682 	  Parent::operator=(INVALID);

   683 	} else {

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

   685 	}

   686       }

   688       /// \brief Increment operator.

   689       ///

   690       /// Increment Operator.

   691       ItemIt& operator++() {

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

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

   694 	return *this;

   695       }

   698     private:

   699       const IterableIntMap* _map;

   700     };

   702   protected:

   704     virtual void erase(const Key& key) {

   705       unlace(key);

   706       Parent::erase(key);

   707     }

   709     virtual void clear() {

   710       first.clear();

   711       Parent::clear();

   712     }

   714   private:

   715     std::vector<_Item> first;

   716   };

   718   /// @}

   719 }

author	hegyi
	Thu, 12 Jan 2006 14:36:08 +0000
changeset 1892	1d384b30157f
parent 1873	d73c7f115f53
child 1913	49fe71fce7fb
permissions	-rw-r--r--