1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/iterable_maps.h Mon Sep 12 05:31:55 2005 +0000
1.3 @@ -0,0 +1,250 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/iterable_maps.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#include <vector>
1.21 +#include <limits>
1.22 +
1.23 +///\ingroup maps
1.24 +///\file
1.25 +///\brief Maps that makes it possible to iterate through the keys having
1.26 +///a certain value
1.27 +///
1.28 +///
1.29 +
1.30 +
1.31 +namespace lemon {
1.32 +
1.33 + ///\todo This is only a static map!
1.34 + ///\param BaseMap is an interger map.
1.35 + template<class BaseMap>
1.36 + class IterableBoolMap
1.37 + {
1.38 + public:
1.39 +
1.40 + typedef typename BaseMap::Key Key;
1.41 + typedef bool Value;
1.42 +
1.43 + friend class RefType;
1.44 + friend class FalseIt;
1.45 + friend class TrueIt;
1.46 +
1.47 + private:
1.48 + BaseMap &cref;
1.49 + std::vector<Key> vals;
1.50 + int sep; //map[e] is true <=> cref[e]>=sep
1.51 +
1.52 + bool isTrue(Key k) {return cref[k]>=sep;}
1.53 + void swap(Key k, int s)
1.54 + {
1.55 + int ti=cref[k];
1.56 + Key tk=vals[s];
1.57 + cref[k]=s; vals[s]=k;
1.58 + cref[tk]=ti; vals[ti]=tk;
1.59 + }
1.60 +
1.61 + void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
1.62 + void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
1.63 +
1.64 + public:
1.65 + ///\e
1.66 + void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
1.67 +
1.68 + ///\e
1.69 + class FalseIt
1.70 + {
1.71 + const IterableBoolMap &M;
1.72 + int i;
1.73 + public:
1.74 + explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
1.75 + FalseIt(Invalid)
1.76 + : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
1.77 + FalseIt &operator++() { ++i; return *this;}
1.78 + operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
1.79 + bool operator !=(Invalid) const { return i<M.sep; }
1.80 + bool operator ==(Invalid) const { return i>=M.sep; }
1.81 + };
1.82 + ///\e
1.83 + class TrueIt
1.84 + {
1.85 + const IterableBoolMap &M;
1.86 + int i;
1.87 + public:
1.88 + explicit TrueIt(const IterableBoolMap &_M)
1.89 + : M(_M), i(M.vals.size()-1) { }
1.90 + TrueIt(Invalid)
1.91 + : M(*((IterableBoolMap*)(0))), i(-1) { }
1.92 + TrueIt &operator++() { --i; return *this;}
1.93 + operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
1.94 + bool operator !=(Invalid) const { return i>=M.sep; }
1.95 + bool operator ==(Invalid) const { return i<M.sep; }
1.96 + };
1.97 +
1.98 + ///\e
1.99 + class RefType
1.100 + {
1.101 + IterableBoolMap &M;
1.102 + Key k;
1.103 + public:
1.104 + RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
1.105 +
1.106 + operator Value() const
1.107 + {
1.108 + return M.isTrue(k);
1.109 + }
1.110 + Value operator = (Value v) const { M.set(k,v); return v; }
1.111 + };
1.112 +
1.113 + public:
1.114 + explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
1.115 + {
1.116 + sep=0;
1.117 + for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin();
1.118 + i!=cref.mapSet().end();
1.119 + ++i) {
1.120 + i->second=sep;
1.121 + vals.push_back(i->first);
1.122 + sep++;
1.123 + }
1.124 + if(init) sep=0;
1.125 + }
1.126 + RefType operator[] (Key k) { return RefType(*this,k);}
1.127 + Value operator[] (Key k) const { return isTrue(k);}
1.128 + };
1.129 +
1.130 +
1.131 +
1.132 +
1.133 + /// \addtogroup graph_maps
1.134 + /// @{
1.135 +
1.136 + /// Iterable bool NodeMap
1.137 +
1.138 + /// This map can be used in the same way
1.139 + /// as the standard NodeMap<bool> of the
1.140 + /// given graph \c Graph.
1.141 + /// In addition, this class provides two iterators called \ref TrueIt
1.142 + /// and \ref FalseIt to iterate through the "true" and "false" nodes.
1.143 + template <class Graph>
1.144 + class IterableBoolNodeMap
1.145 + {
1.146 + typename Graph::NodeMap<int> cmap;
1.147 +
1.148 + public:
1.149 +
1.150 + typedef IterableBoolMap<typename Graph::NodeMap<int> > BimType;
1.151 + BimType imap;
1.152 +
1.153 +
1.154 + typedef typename BimType::RefType RefType;
1.155 + typedef typename Graph::Node Key;
1.156 + typedef bool Value;
1.157 +
1.158 + friend class FalseIt;
1.159 + friend class TrueIt;
1.160 +
1.161 + ///\e
1.162 + IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
1.163 +
1.164 + public:
1.165 + ///\e
1.166 + void set(Key k, bool v) { imap.set(k,v);}
1.167 +#ifdef DOXYGEN
1.168 + ///\e
1.169 + bool &operator[](Key k) { return imap[k];}
1.170 + ///\e
1.171 + const bool &operator[](Key k) const { return imap[k];}
1.172 +#else
1.173 + Value operator[](Key k) const { return imap[k];}
1.174 + RefType operator[](Key k) { return imap[k];}
1.175 +#endif
1.176 + ///Iterator for the "false" nodes
1.177 + class FalseIt : public BimType::FalseIt
1.178 + {
1.179 + public:
1.180 + explicit FalseIt(const IterableBoolNodeMap &m)
1.181 + : BimType::FalseIt(m.imap) { }
1.182 + FalseIt(Invalid i) : BimType::FalseIt(i) { }
1.183 + };
1.184 + ///Iterator for the "true" nodes
1.185 + class TrueIt : public BimType::TrueIt
1.186 + {
1.187 + public:
1.188 + explicit TrueIt(const IterableBoolNodeMap &m)
1.189 + : BimType::TrueIt(m.imap) { }
1.190 + TrueIt(Invalid i) : BimType::TrueIt(i) { }
1.191 + };
1.192 + };
1.193 +
1.194 + /// Iterable bool EdgeMap
1.195 +
1.196 + /// This map can be used in the same way
1.197 + /// as the standard EdgeMap<bool> of the
1.198 + /// given graph \c Graph.
1.199 + /// In addition, this class provides two iterators called \ref TrueIt
1.200 + /// and \ref FalseIt to iterate through the "true" and "false" edges.
1.201 + template <class Graph>
1.202 + class IterableBoolEdgeMap
1.203 + {
1.204 + typename Graph::EdgeMap<int> cmap;
1.205 +
1.206 + public:
1.207 +
1.208 + typedef IterableBoolMap<typename Graph::EdgeMap<int> > BimType;
1.209 + BimType imap;
1.210 +
1.211 +
1.212 + typedef typename BimType::RefType RefType;
1.213 + typedef typename Graph::Edge Key;
1.214 + typedef bool Value;
1.215 +
1.216 + friend class FalseIt;
1.217 + friend class TrueIt;
1.218 +
1.219 + ///\e
1.220 + IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
1.221 +
1.222 + public:
1.223 + ///\e
1.224 + void set(Key k, bool v) { imap.set(k,v);}
1.225 +#ifdef DOXYGEN
1.226 + ///\e
1.227 + bool &operator[](Key k) { return imap[k];}
1.228 + ///\e
1.229 + const bool &operator[](Key k) const { return imap[k];}
1.230 +#else
1.231 + Value operator[](Key k) const { return imap[k];}
1.232 + RefType operator[](Key k) { return imap[k];}
1.233 +#endif
1.234 + ///Iterator for the "false" edges
1.235 + class FalseIt : public BimType::FalseIt
1.236 + {
1.237 + public:
1.238 + explicit FalseIt(const IterableBoolEdgeMap &m)
1.239 + : BimType::FalseIt(m.imap) { }
1.240 + FalseIt(Invalid i) : BimType::FalseIt(i) { }
1.241 + };
1.242 + ///Iterator for the "true" edges
1.243 + class TrueIt : public BimType::TrueIt
1.244 + {
1.245 + public:
1.246 + explicit TrueIt(const IterableBoolEdgeMap &m)
1.247 + : BimType::TrueIt(m.imap) { }
1.248 + TrueIt(Invalid i) : BimType::TrueIt(i) { }
1.249 + };
1.250 + };
1.251 +
1.252 + /// @}
1.253 +}