1.1 --- a/demo/graph_orientation.cc Fri Jan 27 08:17:25 2006 +0000
1.2 +++ b/demo/graph_orientation.cc Fri Jan 27 08:18:47 2006 +0000
1.3 @@ -70,7 +70,7 @@
1.4 ListGraph::NodeMap<int> def(g); //deficiency of the nodes
1.5 def = subMap(f,InDegMap<ListGraph>(g));
1.6
1.7 - IterableBoolNodeMap<ListGraph> active(g,false);
1.8 + IterableBoolMap<ListGraph, Node> active(g,false);
1.9 for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
1.10
1.11 ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be
1.12 @@ -79,7 +79,7 @@
1.13 int nodeNum=countNodes(g);
1.14
1.15 Node act;
1.16 - while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
1.17 + while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
1.18 std::cout << "Process node " << label[act]
1.19 << " (def=" << def[act]
1.20 << " lev=" << level[act] << "): ";
2.1 --- a/lemon/iterable_maps.h Fri Jan 27 08:17:25 2006 +0000
2.2 +++ b/lemon/iterable_maps.h Fri Jan 27 08:18:47 2006 +0000
2.3 @@ -28,424 +28,311 @@
2.4
2.5
2.6 namespace lemon {
2.7 -
2.8 - ///\todo This is only a static map!
2.9 - ///\todo Undocumented.
2.10 - ///\param BaseMap is an interger map.
2.11 - template<class BaseMap>
2.12 - class IterableBoolMap
2.13 - {
2.14 - public:
2.15 -
2.16 - typedef typename BaseMap::Key Key;
2.17 - typedef bool Value;
2.18 -
2.19 - friend class RefType;
2.20 - friend class FalseIt;
2.21 - friend class TrueIt;
2.22 +
2.23 + ///\ingroup maps
2.24 + ///
2.25 + /// \brief Dynamic iterable bool map.
2.26 + ///
2.27 + /// This class provides a special graph map type which can store
2.28 + /// for each graph item(node, edge, etc.) a bool value. For both
2.29 + /// the true and the false it is possible to iterate on the keys which
2.30 + /// mapped to the given value.
2.31 + ///
2.32 + /// \param _Graph The graph type.
2.33 + /// \param _Item One of the graph's item type, the key of the map.
2.34 + template <typename _Graph, typename _Item>
2.35 + class IterableBoolMap
2.36 + : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
2.37 + private:
2.38 + typedef _Graph Graph;
2.39 + typedef _Item Item;
2.40 +
2.41 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
2.42 + typedef typename ItemSetTraits<Graph, Item>
2.43 + ::template Map<int>::Parent Parent;
2.44 +
2.45 + std::vector<Item> array;
2.46 + int sep;
2.47 +
2.48 + const Graph& graph;
2.49
2.50 private:
2.51 - BaseMap &cref;
2.52 - std::vector<Key> vals;
2.53 - int sep; //map[e] is true <=> cref[e]>=sep
2.54 -
2.55 - bool isTrue(Key k) {return cref[k]>=sep;}
2.56 - void swap(Key k, int s)
2.57 - {
2.58 - int ti=cref[k];
2.59 - Key tk=vals[s];
2.60 - cref[k]=s; vals[s]=k;
2.61 - cref[tk]=ti; vals[ti]=tk;
2.62 - }
2.63
2.64 - void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } }
2.65 - void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } }
2.66 -
2.67 - public:
2.68 - ///\e
2.69 - void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);}
2.70 - ///Number of \c true items in the map
2.71 -
2.72 - ///Returns the number of \c true values in the map.
2.73 - ///This is a constant time operation.
2.74 - int countTrue() { return vals.size()-sep; }
2.75 - ///Number of \c false items in the map
2.76 -
2.77 - ///Returns the number of \c false values in the map.
2.78 - ///This is a constant time operation.
2.79 - int countFalse() { return sep; }
2.80 -
2.81 - ///\e
2.82 - class FalseIt
2.83 - {
2.84 - const IterableBoolMap &M;
2.85 - int i;
2.86 - public:
2.87 - ///\e
2.88 - explicit FalseIt(const IterableBoolMap &_M) : M(_M), i(0) { }
2.89 - ///\e
2.90 - FalseIt(Invalid)
2.91 - : M(*((IterableBoolMap*)(0))), i(std::numeric_limits<int>::max()) { }
2.92 - ///\e
2.93 - FalseIt &operator++() { ++i; return *this;}
2.94 - ///\e
2.95 - operator Key() const { return i<M.sep ? M.vals[i] : INVALID; }
2.96 - ///\e
2.97 - bool operator !=(Invalid) const { return i<M.sep; }
2.98 - ///\e
2.99 - bool operator ==(Invalid) const { return i>=M.sep; }
2.100 - };
2.101 - ///\e
2.102 - class TrueIt
2.103 - {
2.104 - const IterableBoolMap &M;
2.105 - int i;
2.106 - public:
2.107 - ///\e
2.108 - explicit TrueIt(const IterableBoolMap &_M)
2.109 - : M(_M), i(M.vals.size()-1) { }
2.110 - ///\e
2.111 - TrueIt(Invalid)
2.112 - : M(*((IterableBoolMap*)(0))), i(-1) { }
2.113 - ///\e
2.114 - TrueIt &operator++() { --i; return *this;}
2.115 - ///\e
2.116 - operator Key() const { return i>=M.sep ? M.vals[i] : INVALID; }
2.117 - ///\e
2.118 - bool operator !=(Invalid) const { return i>=M.sep; }
2.119 - ///\e
2.120 - bool operator ==(Invalid) const { return i<M.sep; }
2.121 - };
2.122 -
2.123 - ///\e
2.124 - class RefType
2.125 - {
2.126 - IterableBoolMap &M;
2.127 - Key k;
2.128 - public:
2.129 - RefType(IterableBoolMap &_M,Key _k) : M(_M), k(_k) { }
2.130 -
2.131 - operator Value() const
2.132 - {
2.133 - return M.isTrue(k);
2.134 - }
2.135 - Value operator = (Value v) const { M.set(k,v); return v; }
2.136 - };
2.137 -
2.138 - public:
2.139 - explicit IterableBoolMap(BaseMap &_m,bool init=false) : cref(_m)
2.140 - {
2.141 - sep=0;
2.142 - for(typename BaseMap::MapIt i(cref);i!=INVALID; ++i) {
2.143 - i.set(sep);
2.144 - vals.push_back(i);
2.145 - sep++;
2.146 - }
2.147 - if(init) sep=0;
2.148 + int position(const Item& item) const {
2.149 + return Parent::operator[](item);
2.150 }
2.151 - ///\e
2.152 - RefType operator[] (Key k) { return RefType(*this,k);}
2.153 - ///\e
2.154 - Value operator[] (Key k) const { return isTrue(k);}
2.155 - };
2.156 -
2.157 -
2.158 -
2.159 -
2.160 - /// \addtogroup graph_maps
2.161 - /// @{
2.162 -
2.163 - /// Iterable bool NodeMap
2.164 -
2.165 - /// This map can be used in the same way
2.166 - /// as the standard NodeMap<bool> of the
2.167 - /// given graph \c Graph.
2.168 - /// In addition, this class provides two iterators called \ref TrueIt
2.169 - /// and \ref FalseIt to iterate through the "true" and "false" nodes.
2.170 - template <class Graph>
2.171 - class IterableBoolNodeMap
2.172 - {
2.173 - typename Graph::template NodeMap<int> cmap;
2.174 -
2.175 - public:
2.176 -
2.177 - typedef IterableBoolMap<typename Graph::template NodeMap<int> > BimType;
2.178 - BimType imap;
2.179 -
2.180 -
2.181 - typedef typename BimType::RefType RefType;
2.182 - typedef typename Graph::Node Key;
2.183 - typedef bool Value;
2.184 -
2.185 - friend class FalseIt;
2.186 - friend class TrueIt;
2.187 -
2.188 - ///\e
2.189 - IterableBoolNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
2.190
2.191 public:
2.192 - ///\e
2.193 - void set(Key k, bool v) { imap.set(k,v);}
2.194 - ///Number of \c true items in the map
2.195
2.196 - ///Returns the number of \c true values in the map.
2.197 - ///This is a constant time operation.
2.198 - int countTrue() { return imap.countTrue(); }
2.199 - ///Number of \c false items in the map
2.200 + /// Indicates that the map if reference map.
2.201 + typedef True ReferenceMapTag;
2.202
2.203 - ///Returns the number of \c false values in the map.
2.204 - ///This is a constant time operation.
2.205 - int countFalse() { return imap.countFalse(); }
2.206 -#ifdef DOXYGEN
2.207 - ///\e
2.208 - bool &operator[](Key k) { return imap[k];}
2.209 - ///\e
2.210 - const bool &operator[](Key k) const { return imap[k];}
2.211 -#else
2.212 - Value operator[](Key k) const { return imap[k];}
2.213 - RefType operator[](Key k) { return imap[k];}
2.214 -#endif
2.215 - ///Iterator for the "false" nodes
2.216 - class FalseIt : public BimType::FalseIt
2.217 - {
2.218 + /// The key type
2.219 + typedef Item Key;
2.220 + /// The value type
2.221 + typedef bool Value;
2.222 + /// The const reference type.
2.223 + typedef const Value& ConstReference;
2.224 +
2.225 +
2.226 + /// \brief Refernce to the value of the map.
2.227 + ///
2.228 + /// This class is near to similar to the bool type. It can
2.229 + /// be converted to bool and it has the same operators.
2.230 + class Reference {
2.231 + friend class IterableBoolMap;
2.232 + private:
2.233 + Reference(IterableBoolMap& map, const Key& key)
2.234 + : _key(key), _map(map) {}
2.235 public:
2.236 - ///\e
2.237 - explicit FalseIt(const IterableBoolNodeMap &m)
2.238 - : BimType::FalseIt(m.imap) { }
2.239 - ///\e
2.240 - FalseIt(Invalid i) : BimType::FalseIt(i) { }
2.241 +
2.242 + Reference& operator=(const Reference& value) {
2.243 + _map.set(_key, (bool)value);
2.244 + return *this;
2.245 + }
2.246 +
2.247 + operator bool() const {
2.248 + return static_cast<const IterableBoolMap&>(_map)[_key];
2.249 + }
2.250 +
2.251 + Reference& operator=(bool value) {
2.252 + _map.set(_key, value);
2.253 + return *this;
2.254 + }
2.255 + Reference& operator&=(bool value) {
2.256 + _map.set(_key, _map[_key] & value);
2.257 + return *this;
2.258 + }
2.259 + Reference& operator|=(bool value) {
2.260 + _map.set(_key, _map[_key] | value);
2.261 + return *this;
2.262 + }
2.263 + Reference& operator^=(bool value) {
2.264 + _map.set(_key, _map[_key] ^ value);
2.265 + return *this;
2.266 + }
2.267 + private:
2.268 + Key _key;
2.269 + IterableBoolMap& _map;
2.270 };
2.271 - ///Iterator for the "true" nodes
2.272 - class TrueIt : public BimType::TrueIt
2.273 - {
2.274 +
2.275 + /// \brief Constructor of the Map with a default value.
2.276 + ///
2.277 + /// Constructor of the Map with a default value.
2.278 + IterableBoolMap(const Graph& _graph, bool def = false)
2.279 + : Parent(_graph), graph(_graph) {
2.280 + for (ItemIt it(graph); it != INVALID; ++it) {
2.281 + Parent::set(it, array.size());
2.282 + array.push_back(it);
2.283 + }
2.284 + sep = (def ? array.size() : 0);
2.285 + }
2.286 +
2.287 + /// \brief Const subscript operator of the map.
2.288 + ///
2.289 + /// Const subscript operator of the map.
2.290 + bool operator[](const Item& item) const {
2.291 + return position(item) < sep;
2.292 + }
2.293 +
2.294 + /// \brief Subscript operator of the map.
2.295 + ///
2.296 + /// Subscript operator of the map.
2.297 + Reference operator[](const Item& item) {
2.298 + return Reference(*this, item);
2.299 + }
2.300 +
2.301 + /// \brief Set operation of the map.
2.302 + ///
2.303 + /// Set operation of the map.
2.304 + void set(const Item& item, bool value) {
2.305 + int pos = position(item);
2.306 + if (value) {
2.307 + if (pos < sep) return;
2.308 + Item tmp = array[sep];
2.309 + array[sep] = item;
2.310 + Parent::set(item, sep);
2.311 + array[pos] = tmp;
2.312 + Parent::set(tmp, pos);
2.313 + ++sep;
2.314 + } else {
2.315 + if (pos >= sep) return;
2.316 + --sep;
2.317 + Item tmp = array[sep];
2.318 + array[sep] = item;
2.319 + Parent::set(item, sep);
2.320 + array[pos] = tmp;
2.321 + Parent::set(tmp, pos);
2.322 + }
2.323 + }
2.324 +
2.325 + /// \brief Returns the number of the items mapped to true.
2.326 + ///
2.327 + /// Returns the number of the items mapped to true.
2.328 + int trueNum() const {
2.329 + return sep;
2.330 + }
2.331 +
2.332 + /// \brief Returns the number of the items mapped to false.
2.333 + ///
2.334 + /// Returns the number of the items mapped to false.
2.335 + int falseNum() const {
2.336 + return array.size() - sep;
2.337 + }
2.338 +
2.339 + /// \brief Iterator for the keys mapped to true.
2.340 + ///
2.341 + /// Iterator for the keys mapped to true. It works
2.342 + /// like a graph item iterator in the map, it can be converted
2.343 + /// the item type of the map, incremented with \c ++ operator, and
2.344 + /// if the iterator leave the last valid item it will be equal to
2.345 + /// \c INVALID.
2.346 + class TrueIt : public Item {
2.347 public:
2.348 - ///\e
2.349 - explicit TrueIt(const IterableBoolNodeMap &m)
2.350 - : BimType::TrueIt(m.imap) { }
2.351 - ///\e
2.352 - TrueIt(Invalid i) : BimType::TrueIt(i) { }
2.353 - };
2.354 + typedef Item Parent;
2.355 +
2.356 + /// \brief Creates an iterator.
2.357 + ///
2.358 + /// Creates an iterator. It iterates on the
2.359 + /// keys which mapped to true.
2.360 + /// \param map The IterableIntMap
2.361 + TrueIt(const IterableBoolMap& _map)
2.362 + : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID),
2.363 + map(&_map) {}
2.364 +
2.365 + /// \brief Invalid constructor \& conversion.
2.366 + ///
2.367 + /// This constructor initializes the item to be invalid.
2.368 + /// \sa Invalid for more details.
2.369 + TrueIt(Invalid) : Parent(INVALID), map(0) {}
2.370 +
2.371 + /// \brief Increment operator.
2.372 + ///
2.373 + /// Increment Operator.
2.374 + TrueIt& operator++() {
2.375 + int pos = map->position(*this);
2.376 + Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
2.377 + return *this;
2.378 + }
2.379 +
2.380 +
2.381 + private:
2.382 + const IterableBoolMap* map;
2.383 + };
2.384 +
2.385 + /// \brief Iterator for the keys mapped to false.
2.386 + ///
2.387 + /// Iterator for the keys mapped to false. It works
2.388 + /// like a graph item iterator in the map, it can be converted
2.389 + /// the item type of the map, incremented with \c ++ operator, and
2.390 + /// if the iterator leave the last valid item it will be equal to
2.391 + /// \c INVALID.
2.392 + class FalseIt : public Item {
2.393 + public:
2.394 + typedef Item Parent;
2.395 +
2.396 + /// \brief Creates an iterator.
2.397 + ///
2.398 + /// Creates an iterator. It iterates on the
2.399 + /// keys which mapped to false.
2.400 + /// \param map The IterableIntMap
2.401 + FalseIt(const IterableBoolMap& _map)
2.402 + : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),
2.403 + map(&_map) {}
2.404 +
2.405 + /// \brief Invalid constructor \& conversion.
2.406 + ///
2.407 + /// This constructor initializes the item to be invalid.
2.408 + /// \sa Invalid for more details.
2.409 + FalseIt(Invalid) : Parent(INVALID), map(0) {}
2.410 +
2.411 + /// \brief Increment operator.
2.412 + ///
2.413 + /// Increment Operator.
2.414 + FalseIt& operator++() {
2.415 + int pos = map->position(*this);
2.416 + Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
2.417 + return *this;
2.418 + }
2.419 +
2.420 + private:
2.421 + const IterableBoolMap* map;
2.422 + };
2.423 +
2.424 + protected:
2.425 +
2.426 + virtual void add(const Item& item) {
2.427 + Parent::add(item);
2.428 + Parent::set(item, array.size());
2.429 + array.push_back(item);
2.430 + }
2.431 +
2.432 + virtual void add(const std::vector<Item>& items) {
2.433 + Parent::add(items);
2.434 + for (int i = 0; i < (int)items.size(); ++i) {
2.435 + Parent::set(items[i], array.size());
2.436 + array.push_back(items[i]);
2.437 + }
2.438 + }
2.439 +
2.440 + virtual void erase(const Item& item) {
2.441 + int pos = position(item);
2.442 + if (pos < sep) {
2.443 + --sep;
2.444 + Parent::set(array[sep], pos);
2.445 + array[pos] = array[sep];
2.446 + Parent::set(array.back(), sep);
2.447 + array[sep] = array.back();
2.448 + array.pop_back();
2.449 + } else {
2.450 + Parent::set(array.back(), pos);
2.451 + array[pos] = array.back();
2.452 + array.pop_back();
2.453 + }
2.454 + Parent::erase(item);
2.455 + }
2.456 +
2.457 + virtual void erase(const std::vector<Item>& items) {
2.458 + for (int i = 0; i < (int)items.size(); ++i) {
2.459 + int pos = position(items[i]);
2.460 + if (pos < sep) {
2.461 + --sep;
2.462 + Parent::set(array[sep], pos);
2.463 + array[pos] = array[sep];
2.464 + Parent::set(array.back(), sep);
2.465 + array[sep] = array.back();
2.466 + array.pop_back();
2.467 + } else {
2.468 + Parent::set(array.back(), pos);
2.469 + array[pos] = array.back();
2.470 + array.pop_back();
2.471 + }
2.472 + }
2.473 + Parent::erase(items);
2.474 + }
2.475 +
2.476 + virtual void build() {
2.477 + Parent::build();
2.478 + for (ItemIt it(graph); it != INVALID; ++it) {
2.479 + Parent::set(it, array.size());
2.480 + array.push_back(it);
2.481 + }
2.482 + sep = 0;
2.483 + }
2.484 +
2.485 + virtual void clear() {
2.486 + array.clear();
2.487 + sep = 0;
2.488 + Parent::clear();
2.489 + }
2.490 +
2.491 };
2.492 -
2.493 - /// Iterable bool UpperNodeMap
2.494 -
2.495 - /// This map can be used in the same way
2.496 - /// as the standard UpperNodeMap<bool> of the
2.497 - /// given graph \c Graph.
2.498 - /// In addition, this class provides two iterators called \ref TrueIt
2.499 - /// and \ref FalseIt to iterate through the "true" and "false" nodes.
2.500 - template <class Graph>
2.501 - class IterableBoolUpperNodeMap
2.502 - {
2.503 - typename Graph::template UpperNodeMap<int> cmap;
2.504
2.505 - public:
2.506 -
2.507 - typedef IterableBoolMap<typename Graph::template UpperNodeMap<int> > BimType;
2.508 - BimType imap;
2.509 -
2.510 -
2.511 - typedef typename BimType::RefType RefType;
2.512 - typedef typename Graph::Node Key;
2.513 - typedef bool Value;
2.514 -
2.515 - friend class FalseIt;
2.516 - friend class TrueIt;
2.517 -
2.518 - ///\e
2.519 - IterableBoolUpperNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
2.520 -
2.521 - public:
2.522 - ///\e
2.523 - void set(Key k, bool v) { imap.set(k,v);}
2.524 - ///Number of \c true items in the map
2.525 -
2.526 - ///Returns the number of \c true values in the map.
2.527 - ///This is a constant time operation.
2.528 - int countTrue() { return imap.countTrue(); }
2.529 - ///Number of \c false items in the map
2.530 -
2.531 - ///Returns the number of \c false values in the map.
2.532 - ///This is a constant time operation.
2.533 - int countFalse() { return imap.countFalse(); }
2.534 -#ifdef DOXYGEN
2.535 - ///\e
2.536 - bool &operator[](Key k) { return imap[k];}
2.537 - ///\e
2.538 - const bool &operator[](Key k) const { return imap[k];}
2.539 -#else
2.540 - Value operator[](Key k) const { return imap[k];}
2.541 - RefType operator[](Key k) { return imap[k];}
2.542 -#endif
2.543 - ///Iterator for the "false" nodes
2.544 - class FalseIt : public BimType::FalseIt
2.545 - {
2.546 - public:
2.547 - ///\e
2.548 - explicit FalseIt(const IterableBoolUpperNodeMap &m)
2.549 - : BimType::FalseIt(m.imap) { }
2.550 - ///\e
2.551 - FalseIt(Invalid i) : BimType::FalseIt(i) { }
2.552 - };
2.553 - ///Iterator for the "true" nodes
2.554 - class TrueIt : public BimType::TrueIt
2.555 - {
2.556 - public:
2.557 - ///\e
2.558 - explicit TrueIt(const IterableBoolUpperNodeMap &m)
2.559 - : BimType::TrueIt(m.imap) { }
2.560 - ///\e
2.561 - TrueIt(Invalid i) : BimType::TrueIt(i) { }
2.562 - };
2.563 - };
2.564 -
2.565 - /// Iterable bool LowerNodeMap
2.566 -
2.567 - /// This map can be used in the same way
2.568 - /// as the standard LowerNodeMap<bool> of the
2.569 - /// given graph \c Graph.
2.570 - /// In addition, this class provides two iterators called \ref TrueIt
2.571 - /// and \ref FalseIt to iterate through the "true" and "false" nodes.
2.572 - template <class Graph>
2.573 - class IterableBoolLowerNodeMap
2.574 - {
2.575 - typename Graph::template LowerNodeMap<int> cmap;
2.576 -
2.577 - public:
2.578 -
2.579 - typedef IterableBoolMap<typename Graph::template LowerNodeMap<int> > BimType;
2.580 - BimType imap;
2.581 -
2.582 -
2.583 - typedef typename BimType::RefType RefType;
2.584 - typedef typename Graph::Node Key;
2.585 - typedef bool Value;
2.586 -
2.587 - friend class FalseIt;
2.588 - friend class TrueIt;
2.589 -
2.590 - ///\e
2.591 - IterableBoolLowerNodeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
2.592 -
2.593 - public:
2.594 - ///\e
2.595 - void set(Key k, bool v) { imap.set(k,v);}
2.596 - ///Number of \c true items in the map
2.597 -
2.598 - ///Returns the number of \c true values in the map.
2.599 - ///This is a constant time operation.
2.600 - int countTrue() { return imap.countTrue(); }
2.601 - ///Number of \c false items in the map
2.602 -
2.603 - ///Returns the number of \c false values in the map.
2.604 - ///This is a constant time operation.
2.605 - int countFalse() { return imap.countFalse(); }
2.606 -#ifdef DOXYGEN
2.607 - ///\e
2.608 - bool &operator[](Key k) { return imap[k];}
2.609 - ///\e
2.610 - const bool &operator[](Key k) const { return imap[k];}
2.611 -#else
2.612 - Value operator[](Key k) const { return imap[k];}
2.613 - RefType operator[](Key k) { return imap[k];}
2.614 -#endif
2.615 - ///Iterator for the "false" nodes
2.616 - class FalseIt : public BimType::FalseIt
2.617 - {
2.618 - public:
2.619 - ///\e
2.620 - explicit FalseIt(const IterableBoolLowerNodeMap &m)
2.621 - : BimType::FalseIt(m.imap) { }
2.622 - ///\e
2.623 - FalseIt(Invalid i) : BimType::FalseIt(i) { }
2.624 - };
2.625 - ///Iterator for the "true" nodes
2.626 - class TrueIt : public BimType::TrueIt
2.627 - {
2.628 - public:
2.629 - ///\e
2.630 - explicit TrueIt(const IterableBoolLowerNodeMap &m)
2.631 - : BimType::TrueIt(m.imap) { }
2.632 - ///\e
2.633 - TrueIt(Invalid i) : BimType::TrueIt(i) { }
2.634 - };
2.635 - };
2.636 -
2.637 - /// Iterable bool EdgeMap
2.638 -
2.639 - /// This map can be used in the same way
2.640 - /// as the standard EdgeMap<bool> of the
2.641 - /// given graph \c Graph.
2.642 - /// In addition, this class provides two iterators called \ref TrueIt
2.643 - /// and \ref FalseIt to iterate through the "true" and "false" edges.
2.644 - template <class Graph>
2.645 - class IterableBoolEdgeMap
2.646 - {
2.647 - typename Graph::template EdgeMap<int> cmap;
2.648 -
2.649 - public:
2.650 -
2.651 - typedef IterableBoolMap<typename Graph::template EdgeMap<int> > BimType;
2.652 - BimType imap;
2.653 -
2.654 -
2.655 - typedef typename BimType::RefType RefType;
2.656 - typedef typename Graph::Edge Key;
2.657 - typedef bool Value;
2.658 -
2.659 - friend class FalseIt;
2.660 - friend class TrueIt;
2.661 -
2.662 - ///\e
2.663 - IterableBoolEdgeMap(const Graph &g,bool b=false) : cmap(g), imap(cmap,b) {}
2.664 -
2.665 - public:
2.666 - ///\e
2.667 - void set(Key k, bool v) { imap.set(k,v);}
2.668 - ///Returns the number of \c true values in the map.
2.669 - ///This is a constant time operation.
2.670 - int countTrue() { return imap.countTrue(); }
2.671 - ///Number of \c false items in the map
2.672 -
2.673 - ///Returns the number of \c false values in the map.
2.674 - ///This is a constant time operation.
2.675 - int countFalse() { return imap.countFalse(); }
2.676 -#ifdef DOXYGEN
2.677 - ///\e
2.678 - bool &operator[](Key k) { return imap[k];}
2.679 - ///\e
2.680 - const bool &operator[](Key k) const { return imap[k];}
2.681 -#else
2.682 - Value operator[](Key k) const { return imap[k];}
2.683 - RefType operator[](Key k) { return imap[k];}
2.684 -#endif
2.685 - ///Iterator for the "false" edges
2.686 - class FalseIt : public BimType::FalseIt
2.687 - {
2.688 - public:
2.689 - ///\e
2.690 - explicit FalseIt(const IterableBoolEdgeMap &m)
2.691 - : BimType::FalseIt(m.imap) { }
2.692 - ///\e
2.693 - FalseIt(Invalid i) : BimType::FalseIt(i) { }
2.694 - };
2.695 - ///Iterator for the "true" edges
2.696 - class TrueIt : public BimType::TrueIt
2.697 - {
2.698 - public:
2.699 - ///\e
2.700 - explicit TrueIt(const IterableBoolEdgeMap &m)
2.701 - : BimType::TrueIt(m.imap) { }
2.702 - ///\e
2.703 - TrueIt(Invalid i) : BimType::TrueIt(i) { }
2.704 - };
2.705 - };
2.706 -
2.707
2.708 namespace _iterable_maps_bits {
2.709 template <typename Item>
2.710 struct IterableIntMapNode {
2.711 - IterableIntMapNode() {}
2.712 + IterableIntMapNode() : value(-1) {}
2.713 IterableIntMapNode(int _value) : value(_value) {}
2.714 Item prev, next;
2.715 int value;
2.716 @@ -482,7 +369,7 @@
2.717 ///
2.718 /// Constructor of the Map. It set all values -1.
2.719 explicit IterableIntMap(const Graph& graph)
2.720 - : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(-1)) {}
2.721 + : Parent(graph) {}
2.722
2.723 /// \brief Constructor of the Map with a given value.
2.724 ///
2.725 @@ -706,6 +593,13 @@
2.726 Parent::erase(key);
2.727 }
2.728
2.729 + virtual void erase(const std::vector<Key>& keys) {
2.730 + for (int i = 0; i < keys.size(); ++i) {
2.731 + unlace(keys[i]);
2.732 + }
2.733 + Parent::erase(keys);
2.734 + }
2.735 +
2.736 virtual void clear() {
2.737 first.clear();
2.738 Parent::clear();