lemon-0.x: lemon/iterable_maps.h@66c89fe52d4e

     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 <vector>

    18 #include <limits>

    20 ///\ingroup maps

    21 ///\file

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

    23 ///a certain value

    24 ///

    25 ///

    28 namespace lemon {

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

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

    32   template<class BaseMap>

    33   class IterableBoolMap

    34   {

    35   public:

    37     typedef typename BaseMap::Key Key;

    38     typedef bool Value;

    40     friend class RefType;

    41     friend class FalseIt;

    42     friend class TrueIt;

    44   private:

    45     BaseMap &cref;

    46     std::vector<Key> vals;

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

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

    50     void swap(Key k, int s)

    51     {

    52       int ti=cref[k];

    53       Key tk=vals[s];

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

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

    56     }

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

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

    61   public:

    62     ///\e

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

    65     ///\e

    66     class FalseIt

    67     {

    68       const IterableBoolMap &M;

    69       int i;

    70     public:

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

    72       FalseIt(Invalid)

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

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

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

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

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

    78     };

    79     ///\e

    80     class TrueIt

    81     {

    82       const IterableBoolMap &M;

    83       int i;

    84     public:

    85       explicit TrueIt(const IterableBoolMap &_M)

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

    87       TrueIt(Invalid)

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

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

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

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

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

    93     };

    95     ///\e

    96     class RefType

    97     {

    98       IterableBoolMap &M;

    99       Key k;

   100     public:

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

   103       operator Value() const

   104       {

   105 	return M.isTrue(k);

   106       }

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

   108     };

   110   public:

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

   112     {

   113       sep=0;

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

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

   116 	  ++i) {

   117 	i->second=sep;

   118 	vals.push_back(i->first);

   119 	sep++;

   120       }

   121       if(init) sep=0;

   122     }

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

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

   125   };

   130   /// \addtogroup graph_maps

   131   /// @{

   133   /// Iterable bool NodeMap

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

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

   137   /// given graph \c Graph.

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

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

   140   template <class Graph>

   141   class IterableBoolNodeMap

   142   {

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

   145   public:

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

   148     BimType imap;

   151     typedef typename BimType::RefType RefType;

   152     typedef typename Graph::Node Key;

   153     typedef bool Value;

   155     friend class FalseIt;

   156     friend class TrueIt;

   158     ///\e

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

   161   public:

   162     ///\e

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

   164 #ifdef DOXYGEN

   165     ///\e

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

   167     ///\e

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

   169 #else

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

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

   172 #endif

   173     ///Iterator for the "false" nodes

   174     class FalseIt : public BimType::FalseIt

   175     {

   176     public:

   177       explicit FalseIt(const IterableBoolNodeMap &m)

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

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

   180     };

   181     ///Iterator for the "true" nodes

   182     class TrueIt : public BimType::TrueIt

   183     {

   184     public:

   185       explicit TrueIt(const IterableBoolNodeMap &m)

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

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

   188     };

   189   };

   191   /// Iterable bool EdgeMap

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

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

   195   /// given graph \c Graph.

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

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

   198   template <class Graph>

   199   class IterableBoolEdgeMap

   200   {

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

   203   public:

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

   206     BimType imap;

   209     typedef typename BimType::RefType RefType;

   210     typedef typename Graph::Edge Key;

   211     typedef bool Value;

   213     friend class FalseIt;

   214     friend class TrueIt;

   216     ///\e

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

   219   public:

   220     ///\e

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

   222 #ifdef DOXYGEN

   223     ///\e

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

   225     ///\e

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

   227 #else

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

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

   230 #endif

   231     ///Iterator for the "false" edges

   232     class FalseIt : public BimType::FalseIt

   233     {

   234     public:

   235       explicit FalseIt(const IterableBoolEdgeMap &m)

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

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

   238     };

   239     ///Iterator for the "true" edges

   240     class TrueIt : public BimType::TrueIt

   241     {

   242     public:

   243       explicit TrueIt(const IterableBoolEdgeMap &m)

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

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

   246     };

   247   };

   249   /// @}

   250 }

author	hegyi
	Thu, 06 Oct 2005 12:32:06 +0000
changeset 1714	66c89fe52d4e
parent 1677	a9f923a4d998
child 1752	dce1f28ac595
permissions	-rw-r--r--