Port iterable maps from SVN 3509 (#73)
authorBalazs Dezso <deba@inf.elte.hu>
Sat, 27 Jun 2009 13:07:26 +0200 (2009-06-27)
changeset 6937bda7860e0a8
parent 683 9f529abcaebf
child 694 71939d63ae77
Port iterable maps from SVN 3509 (#73)
lemon/maps.h
test/maps_test.cc
     1.1 --- a/lemon/maps.h	Thu Jun 11 23:13:24 2009 +0200
     1.2 +++ b/lemon/maps.h	Sat Jun 27 13:07:26 2009 +0200
     1.3 @@ -24,6 +24,7 @@
     1.4  #include <vector>
     1.5  
     1.6  #include <lemon/core.h>
     1.7 +#include <lemon/smart_graph.h>
     1.8  
     1.9  ///\file
    1.10  ///\ingroup maps
    1.11 @@ -1818,7 +1819,7 @@
    1.12    /// \brief Provides an immutable and unique id for each item in a graph.
    1.13    ///
    1.14    /// IdMap provides a unique and immutable id for each item of the
    1.15 -  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
    1.16 +  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    1.17    ///  - \b unique: different items get different ids,
    1.18    ///  - \b immutable: the id of an item does not change (even if you
    1.19    ///    delete other nodes).
    1.20 @@ -2004,7 +2005,7 @@
    1.21        if (it != _inv_map.end() && it->second == key) {
    1.22          _inv_map.erase(it);
    1.23        }
    1.24 -      _inv_map.insert(make_pair(val, key));
    1.25 +      _inv_map.insert(std::make_pair(val, key));
    1.26        Map::set(key, val);
    1.27      }
    1.28  
    1.29 @@ -2254,7 +2255,7 @@
    1.30      }
    1.31  
    1.32      /// \brief Gives back the item belonging to a \e RangeId
    1.33 -    /// 
    1.34 +    ///
    1.35      /// Gives back the item belonging to a \e RangeId.
    1.36      Item operator()(int id) const {
    1.37        return _inv_map[id];
    1.38 @@ -2311,6 +2312,894 @@
    1.39      }
    1.40    };
    1.41  
    1.42 +  /// \brief Dynamic iterable bool map.
    1.43 +  ///
    1.44 +  /// This class provides a special graph map type which can store for
    1.45 +  /// each graph item(node, arc, edge, etc.) a bool value. For both
    1.46 +  /// the true and the false values it is possible to iterate on the
    1.47 +  /// keys.
    1.48 +  ///
    1.49 +  /// \param GR The graph type.
    1.50 +  /// \param ITEM One of the graph's item types, the key of the map.
    1.51 +  template <typename GR, typename ITEM>
    1.52 +  class IterableBoolMap
    1.53 +    : protected ItemSetTraits<GR, ITEM>::template Map<int>::Type {
    1.54 +  private:
    1.55 +    typedef GR Graph;
    1.56 +
    1.57 +    typedef typename ItemSetTraits<Graph, ITEM>::ItemIt KeyIt;
    1.58 +    typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent;
    1.59 +
    1.60 +    std::vector<ITEM> _array;
    1.61 +    int _sep;
    1.62 +
    1.63 +  public:
    1.64 +
    1.65 +    /// Indicates that the map if reference map.
    1.66 +    typedef True ReferenceMapTag;
    1.67 +
    1.68 +    /// The key type
    1.69 +    typedef ITEM Key;
    1.70 +    /// The value type
    1.71 +    typedef bool Value;
    1.72 +    /// The const reference type.
    1.73 +    typedef const Value& ConstReference;
    1.74 +
    1.75 +  private:
    1.76 +
    1.77 +    int position(const Key& key) const {
    1.78 +      return Parent::operator[](key);
    1.79 +    }
    1.80 +
    1.81 +  public:
    1.82 +
    1.83 +    /// \brief Refernce to the value of the map.
    1.84 +    ///
    1.85 +    /// This class is similar to the bool type. It can be converted to
    1.86 +    /// bool and it provides the same operators.
    1.87 +    class Reference {
    1.88 +      friend class IterableBoolMap;
    1.89 +    private:
    1.90 +      Reference(IterableBoolMap& map, const Key& key)
    1.91 +        : _key(key), _map(map) {}
    1.92 +    public:
    1.93 +
    1.94 +      Reference& operator=(const Reference& value) {
    1.95 +        _map.set(_key, static_cast<bool>(value));
    1.96 +         return *this;
    1.97 +      }
    1.98 +
    1.99 +      operator bool() const {
   1.100 +        return static_cast<const IterableBoolMap&>(_map)[_key];
   1.101 +      }
   1.102 +
   1.103 +      Reference& operator=(bool value) {
   1.104 +        _map.set(_key, value);
   1.105 +        return *this;
   1.106 +      }
   1.107 +      Reference& operator&=(bool value) {
   1.108 +        _map.set(_key, _map[_key] & value);
   1.109 +        return *this;
   1.110 +      }
   1.111 +      Reference& operator|=(bool value) {
   1.112 +        _map.set(_key, _map[_key] | value);
   1.113 +        return *this;
   1.114 +      }
   1.115 +      Reference& operator^=(bool value) {
   1.116 +        _map.set(_key, _map[_key] ^ value);
   1.117 +        return *this;
   1.118 +      }
   1.119 +    private:
   1.120 +      Key _key;
   1.121 +      IterableBoolMap& _map;
   1.122 +    };
   1.123 +
   1.124 +    /// \brief Constructor of the map with a default value.
   1.125 +    ///
   1.126 +    /// Constructor of the map with a default value.
   1.127 +    explicit IterableBoolMap(const Graph& graph, bool def = false)
   1.128 +      : Parent(graph) {
   1.129 +      typename Parent::Notifier* nf = Parent::notifier();
   1.130 +      Key it;
   1.131 +      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.132 +        Parent::set(it, _array.size());
   1.133 +        _array.push_back(it);
   1.134 +      }
   1.135 +      _sep = (def ? _array.size() : 0);
   1.136 +    }
   1.137 +
   1.138 +    /// \brief Const subscript operator of the map.
   1.139 +    ///
   1.140 +    /// Const subscript operator of the map.
   1.141 +    bool operator[](const Key& key) const {
   1.142 +      return position(key) < _sep;
   1.143 +    }
   1.144 +
   1.145 +    /// \brief Subscript operator of the map.
   1.146 +    ///
   1.147 +    /// Subscript operator of the map.
   1.148 +    Reference operator[](const Key& key) {
   1.149 +      return Reference(*this, key);
   1.150 +    }
   1.151 +
   1.152 +    /// \brief Set operation of the map.
   1.153 +    ///
   1.154 +    /// Set operation of the map.
   1.155 +    void set(const Key& key, bool value) {
   1.156 +      int pos = position(key);
   1.157 +      if (value) {
   1.158 +        if (pos < _sep) return;
   1.159 +        Key tmp = _array[_sep];
   1.160 +        _array[_sep] = key;
   1.161 +        Parent::set(key, _sep);
   1.162 +        _array[pos] = tmp;
   1.163 +        Parent::set(tmp, pos);
   1.164 +        ++_sep;
   1.165 +      } else {
   1.166 +        if (pos >= _sep) return;
   1.167 +        --_sep;
   1.168 +        Key tmp = _array[_sep];
   1.169 +        _array[_sep] = key;
   1.170 +        Parent::set(key, _sep);
   1.171 +        _array[pos] = tmp;
   1.172 +        Parent::set(tmp, pos);
   1.173 +      }
   1.174 +    }
   1.175 +
   1.176 +    /// \brief Set all items.
   1.177 +    ///
   1.178 +    /// Set all items in the map.
   1.179 +    /// \note Constant time operation.
   1.180 +    void setAll(bool value) {
   1.181 +      _sep = (value ? _array.size() : 0);
   1.182 +    }
   1.183 +
   1.184 +    /// \brief Returns the number of the keys mapped to true.
   1.185 +    ///
   1.186 +    /// Returns the number of the keys mapped to true.
   1.187 +    int trueNum() const {
   1.188 +      return _sep;
   1.189 +    }
   1.190 +
   1.191 +    /// \brief Returns the number of the keys mapped to false.
   1.192 +    ///
   1.193 +    /// Returns the number of the keys mapped to false.
   1.194 +    int falseNum() const {
   1.195 +      return _array.size() - _sep;
   1.196 +    }
   1.197 +
   1.198 +    /// \brief Iterator for the keys mapped to true.
   1.199 +    ///
   1.200 +    /// Iterator for the keys mapped to true. It works
   1.201 +    /// like a graph item iterator in the map, it can be converted
   1.202 +    /// the key type of the map, incremented with \c ++ operator, and
   1.203 +    /// if the iterator leave the last valid key it will be equal to
   1.204 +    /// \c INVALID.
   1.205 +    class TrueIt : public Key {
   1.206 +    public:
   1.207 +      typedef Key Parent;
   1.208 +
   1.209 +      /// \brief Creates an iterator.
   1.210 +      ///
   1.211 +      /// Creates an iterator. It iterates on the
   1.212 +      /// keys which mapped to true.
   1.213 +      /// \param map The IterableIntMap
   1.214 +      explicit TrueIt(const IterableBoolMap& map)
   1.215 +        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
   1.216 +          _map(&map) {}
   1.217 +
   1.218 +      /// \brief Invalid constructor \& conversion.
   1.219 +      ///
   1.220 +      /// This constructor initializes the key to be invalid.
   1.221 +      /// \sa Invalid for more details.
   1.222 +      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
   1.223 +
   1.224 +      /// \brief Increment operator.
   1.225 +      ///
   1.226 +      /// Increment Operator.
   1.227 +      TrueIt& operator++() {
   1.228 +        int pos = _map->position(*this);
   1.229 +        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
   1.230 +        return *this;
   1.231 +      }
   1.232 +
   1.233 +
   1.234 +    private:
   1.235 +      const IterableBoolMap* _map;
   1.236 +    };
   1.237 +
   1.238 +    /// \brief Iterator for the keys mapped to false.
   1.239 +    ///
   1.240 +    /// Iterator for the keys mapped to false. It works
   1.241 +    /// like a graph item iterator in the map, it can be converted
   1.242 +    /// the key type of the map, incremented with \c ++ operator, and
   1.243 +    /// if the iterator leave the last valid key it will be equal to
   1.244 +    /// \c INVALID.
   1.245 +    class FalseIt : public Key {
   1.246 +    public:
   1.247 +      typedef Key Parent;
   1.248 +
   1.249 +      /// \brief Creates an iterator.
   1.250 +      ///
   1.251 +      /// Creates an iterator. It iterates on the
   1.252 +      /// keys which mapped to false.
   1.253 +      /// \param map The IterableIntMap
   1.254 +      explicit FalseIt(const IterableBoolMap& map)
   1.255 +        : Parent(map._sep < int(map._array.size()) ?
   1.256 +                 map._array.back() : INVALID), _map(&map) {}
   1.257 +
   1.258 +      /// \brief Invalid constructor \& conversion.
   1.259 +      ///
   1.260 +      /// This constructor initializes the key to be invalid.
   1.261 +      /// \sa Invalid for more details.
   1.262 +      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
   1.263 +
   1.264 +      /// \brief Increment operator.
   1.265 +      ///
   1.266 +      /// Increment Operator.
   1.267 +      FalseIt& operator++() {
   1.268 +        int pos = _map->position(*this);
   1.269 +        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
   1.270 +        return *this;
   1.271 +      }
   1.272 +
   1.273 +    private:
   1.274 +      const IterableBoolMap* _map;
   1.275 +    };
   1.276 +
   1.277 +    /// \brief Iterator for the keys mapped to a given value.
   1.278 +    ///
   1.279 +    /// Iterator for the keys mapped to a given value. It works
   1.280 +    /// like a graph item iterator in the map, it can be converted
   1.281 +    /// the key type of the map, incremented with \c ++ operator, and
   1.282 +    /// if the iterator leave the last valid key it will be equal to
   1.283 +    /// \c INVALID.
   1.284 +    class ItemIt : public Key {
   1.285 +    public:
   1.286 +      typedef Key Parent;
   1.287 +
   1.288 +      /// \brief Creates an iterator.
   1.289 +      ///
   1.290 +      /// Creates an iterator. It iterates on the
   1.291 +      /// keys which mapped to false.
   1.292 +      /// \param map The IterableIntMap
   1.293 +      /// \param value Which elements should be iterated.
   1.294 +      ItemIt(const IterableBoolMap& map, bool value)
   1.295 +        : Parent(value ? 
   1.296 +                 (map._sep > 0 ?
   1.297 +                  map._array[map._sep - 1] : INVALID) :
   1.298 +                 (map._sep < int(map._array.size()) ?
   1.299 +                  map._array.back() : INVALID)), _map(&map) {}
   1.300 +
   1.301 +      /// \brief Invalid constructor \& conversion.
   1.302 +      ///
   1.303 +      /// This constructor initializes the key to be invalid.
   1.304 +      /// \sa Invalid for more details.
   1.305 +      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   1.306 +
   1.307 +      /// \brief Increment operator.
   1.308 +      ///
   1.309 +      /// Increment Operator.
   1.310 +      ItemIt& operator++() {
   1.311 +        int pos = _map->position(*this);
   1.312 +        int _sep = pos >= _map->_sep ? _map->_sep : 0;
   1.313 +        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
   1.314 +        return *this;
   1.315 +      }
   1.316 +
   1.317 +    private:
   1.318 +      const IterableBoolMap* _map;
   1.319 +    };
   1.320 +
   1.321 +  protected:
   1.322 +
   1.323 +    virtual void add(const Key& key) {
   1.324 +      Parent::add(key);
   1.325 +      Parent::set(key, _array.size());
   1.326 +      _array.push_back(key);
   1.327 +    }
   1.328 +
   1.329 +    virtual void add(const std::vector<Key>& keys) {
   1.330 +      Parent::add(keys);
   1.331 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.332 +        Parent::set(keys[i], _array.size());
   1.333 +        _array.push_back(keys[i]);
   1.334 +      }
   1.335 +    }
   1.336 +
   1.337 +    virtual void erase(const Key& key) {
   1.338 +      int pos = position(key);
   1.339 +      if (pos < _sep) {
   1.340 +        --_sep;
   1.341 +        Parent::set(_array[_sep], pos);
   1.342 +        _array[pos] = _array[_sep];
   1.343 +        Parent::set(_array.back(), _sep);
   1.344 +        _array[_sep] = _array.back();
   1.345 +        _array.pop_back();
   1.346 +      } else {
   1.347 +        Parent::set(_array.back(), pos);
   1.348 +        _array[pos] = _array.back();
   1.349 +        _array.pop_back();
   1.350 +      }
   1.351 +      Parent::erase(key);
   1.352 +    }
   1.353 +
   1.354 +    virtual void erase(const std::vector<Key>& keys) {
   1.355 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.356 +        int pos = position(keys[i]);
   1.357 +        if (pos < _sep) {
   1.358 +          --_sep;
   1.359 +          Parent::set(_array[_sep], pos);
   1.360 +          _array[pos] = _array[_sep];
   1.361 +          Parent::set(_array.back(), _sep);
   1.362 +          _array[_sep] = _array.back();
   1.363 +          _array.pop_back();
   1.364 +        } else {
   1.365 +          Parent::set(_array.back(), pos);
   1.366 +          _array[pos] = _array.back();
   1.367 +          _array.pop_back();
   1.368 +        }
   1.369 +      }
   1.370 +      Parent::erase(keys);
   1.371 +    }
   1.372 +
   1.373 +    virtual void build() {
   1.374 +      Parent::build();
   1.375 +      typename Parent::Notifier* nf = Parent::notifier();
   1.376 +      Key it;
   1.377 +      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.378 +        Parent::set(it, _array.size());
   1.379 +        _array.push_back(it);
   1.380 +      }
   1.381 +      _sep = 0;
   1.382 +    }
   1.383 +
   1.384 +    virtual void clear() {
   1.385 +      _array.clear();
   1.386 +      _sep = 0;
   1.387 +      Parent::clear();
   1.388 +    }
   1.389 +
   1.390 +  };
   1.391 +
   1.392 +
   1.393 +  namespace _maps_bits {
   1.394 +    template <typename Item>
   1.395 +    struct IterableIntMapNode {
   1.396 +      IterableIntMapNode() : value(-1) {}
   1.397 +      IterableIntMapNode(int _value) : value(_value) {}
   1.398 +      Item prev, next;
   1.399 +      int value;
   1.400 +    };
   1.401 +  }
   1.402 +
   1.403 +  ///\ingroup graph_maps
   1.404 +  ///
   1.405 +  /// \brief Dynamic iterable integer map.
   1.406 +  ///
   1.407 +  /// This class provides a special graph map type which can store
   1.408 +  /// for each graph item(node, edge, etc.) an integer value. For each
   1.409 +  /// non negative value it is possible to iterate on the keys which
   1.410 +  /// mapped to the given value.
   1.411 +  ///
   1.412 +  /// \note The size of the data structure depends on the highest
   1.413 +  /// value in the map.
   1.414 +  ///
   1.415 +  /// \param GR The graph type.
   1.416 +  /// \param ITEM One of the graph's item type, the key of the map.
   1.417 +  template <typename GR, typename ITEM>
   1.418 +  class IterableIntMap
   1.419 +    : protected ItemSetTraits<GR, ITEM>::
   1.420 +        template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type {
   1.421 +  public:
   1.422 +    typedef typename ItemSetTraits<GR, ITEM>::
   1.423 +      template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type Parent;
   1.424 +
   1.425 +    /// The key type
   1.426 +    typedef ITEM Key;
   1.427 +    /// The value type
   1.428 +    typedef int Value;
   1.429 +    /// The graph type
   1.430 +    typedef GR Graph;
   1.431 +
   1.432 +    /// \brief Constructor of the map.
   1.433 +    ///
   1.434 +    /// Constructor of the map. It set all values to -1.
   1.435 +    explicit IterableIntMap(const Graph& graph)
   1.436 +      : Parent(graph) {}
   1.437 +
   1.438 +    /// \brief Constructor of the map with a given value.
   1.439 +    ///
   1.440 +    /// Constructor of the map with a given value.
   1.441 +    explicit IterableIntMap(const Graph& graph, int value)
   1.442 +      : Parent(graph, _maps_bits::IterableIntMapNode<ITEM>(value)) {
   1.443 +      if (value >= 0) {
   1.444 +        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   1.445 +          lace(it);
   1.446 +        }
   1.447 +      }
   1.448 +    }
   1.449 +
   1.450 +  private:
   1.451 +
   1.452 +    void unlace(const Key& key) {
   1.453 +      typename Parent::Value& node = Parent::operator[](key);
   1.454 +      if (node.value < 0) return;
   1.455 +      if (node.prev != INVALID) {
   1.456 +        Parent::operator[](node.prev).next = node.next;
   1.457 +      } else {
   1.458 +        _first[node.value] = node.next;
   1.459 +      }
   1.460 +      if (node.next != INVALID) {
   1.461 +        Parent::operator[](node.next).prev = node.prev;
   1.462 +      }
   1.463 +      while (!_first.empty() && _first.back() == INVALID) {
   1.464 +        _first.pop_back();
   1.465 +      }
   1.466 +    }
   1.467 +
   1.468 +    void lace(const Key& key) {
   1.469 +      typename Parent::Value& node = Parent::operator[](key);
   1.470 +      if (node.value < 0) return;
   1.471 +      if (node.value >= int(_first.size())) {
   1.472 +        _first.resize(node.value + 1, INVALID);
   1.473 +      }
   1.474 +      node.prev = INVALID;
   1.475 +      node.next = _first[node.value];
   1.476 +      if (node.next != INVALID) {
   1.477 +        Parent::operator[](node.next).prev = key;
   1.478 +      }
   1.479 +      _first[node.value] = key;
   1.480 +    }
   1.481 +
   1.482 +  public:
   1.483 +
   1.484 +    /// Indicates that the map if reference map.
   1.485 +    typedef True ReferenceMapTag;
   1.486 +
   1.487 +    /// \brief Refernce to the value of the map.
   1.488 +    ///
   1.489 +    /// This class is similar to the int type. It can
   1.490 +    /// be converted to int and it has the same operators.
   1.491 +    class Reference {
   1.492 +      friend class IterableIntMap;
   1.493 +    private:
   1.494 +      Reference(IterableIntMap& map, const Key& key)
   1.495 +        : _key(key), _map(map) {}
   1.496 +    public:
   1.497 +
   1.498 +      Reference& operator=(const Reference& value) {
   1.499 +        _map.set(_key, static_cast<const int&>(value));
   1.500 +         return *this;
   1.501 +      }
   1.502 +
   1.503 +      operator const int&() const {
   1.504 +        return static_cast<const IterableIntMap&>(_map)[_key];
   1.505 +      }
   1.506 +
   1.507 +      Reference& operator=(int value) {
   1.508 +        _map.set(_key, value);
   1.509 +        return *this;
   1.510 +      }
   1.511 +      Reference& operator++() {
   1.512 +        _map.set(_key, _map[_key] + 1);
   1.513 +        return *this;
   1.514 +      }
   1.515 +      int operator++(int) {
   1.516 +        int value = _map[_key];
   1.517 +        _map.set(_key, value + 1);
   1.518 +        return value;
   1.519 +      }
   1.520 +      Reference& operator--() {
   1.521 +        _map.set(_key, _map[_key] - 1);
   1.522 +        return *this;
   1.523 +      }
   1.524 +      int operator--(int) {
   1.525 +        int value = _map[_key];
   1.526 +        _map.set(_key, value - 1);
   1.527 +        return value;
   1.528 +      }
   1.529 +      Reference& operator+=(int value) {
   1.530 +        _map.set(_key, _map[_key] + value);
   1.531 +        return *this;
   1.532 +      }
   1.533 +      Reference& operator-=(int value) {
   1.534 +        _map.set(_key, _map[_key] - value);
   1.535 +        return *this;
   1.536 +      }
   1.537 +      Reference& operator*=(int value) {
   1.538 +        _map.set(_key, _map[_key] * value);
   1.539 +        return *this;
   1.540 +      }
   1.541 +      Reference& operator/=(int value) {
   1.542 +        _map.set(_key, _map[_key] / value);
   1.543 +        return *this;
   1.544 +      }
   1.545 +      Reference& operator%=(int value) {
   1.546 +        _map.set(_key, _map[_key] % value);
   1.547 +        return *this;
   1.548 +      }
   1.549 +      Reference& operator&=(int value) {
   1.550 +        _map.set(_key, _map[_key] & value);
   1.551 +        return *this;
   1.552 +      }
   1.553 +      Reference& operator|=(int value) {
   1.554 +        _map.set(_key, _map[_key] | value);
   1.555 +        return *this;
   1.556 +      }
   1.557 +      Reference& operator^=(int value) {
   1.558 +        _map.set(_key, _map[_key] ^ value);
   1.559 +        return *this;
   1.560 +      }
   1.561 +      Reference& operator<<=(int value) {
   1.562 +        _map.set(_key, _map[_key] << value);
   1.563 +        return *this;
   1.564 +      }
   1.565 +      Reference& operator>>=(int value) {
   1.566 +        _map.set(_key, _map[_key] >> value);
   1.567 +        return *this;
   1.568 +      }
   1.569 +
   1.570 +    private:
   1.571 +      Key _key;
   1.572 +      IterableIntMap& _map;
   1.573 +    };
   1.574 +
   1.575 +    /// The const reference type.
   1.576 +    typedef const Value& ConstReference;
   1.577 +
   1.578 +    /// \brief Gives back the maximal value plus one.
   1.579 +    ///
   1.580 +    /// Gives back the maximal value plus one.
   1.581 +    int size() const {
   1.582 +      return _first.size();
   1.583 +    }
   1.584 +
   1.585 +    /// \brief Set operation of the map.
   1.586 +    ///
   1.587 +    /// Set operation of the map.
   1.588 +    void set(const Key& key, const Value& value) {
   1.589 +      unlace(key);
   1.590 +      Parent::operator[](key).value = value;
   1.591 +      lace(key);
   1.592 +    }
   1.593 +
   1.594 +    /// \brief Const subscript operator of the map.
   1.595 +    ///
   1.596 +    /// Const subscript operator of the map.
   1.597 +    const Value& operator[](const Key& key) const {
   1.598 +      return Parent::operator[](key).value;
   1.599 +    }
   1.600 +
   1.601 +    /// \brief Subscript operator of the map.
   1.602 +    ///
   1.603 +    /// Subscript operator of the map.
   1.604 +    Reference operator[](const Key& key) {
   1.605 +      return Reference(*this, key);
   1.606 +    }
   1.607 +
   1.608 +    /// \brief Iterator for the keys with the same value.
   1.609 +    ///
   1.610 +    /// Iterator for the keys with the same value. It works
   1.611 +    /// like a graph item iterator in the map, it can be converted
   1.612 +    /// the item type of the map, incremented with \c ++ operator, and
   1.613 +    /// if the iterator leave the last valid item it will be equal to
   1.614 +    /// \c INVALID.
   1.615 +    class ItemIt : public ITEM {
   1.616 +    public:
   1.617 +      typedef ITEM Parent;
   1.618 +
   1.619 +      /// \brief Invalid constructor \& conversion.
   1.620 +      ///
   1.621 +      /// This constructor initializes the item to be invalid.
   1.622 +      /// \sa Invalid for more details.
   1.623 +      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   1.624 +
   1.625 +      /// \brief Creates an iterator with a value.
   1.626 +      ///
   1.627 +      /// Creates an iterator with a value. It iterates on the
   1.628 +      /// keys which have the given value.
   1.629 +      /// \param map The IterableIntMap
   1.630 +      /// \param value The value
   1.631 +      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
   1.632 +        if (value < 0 || value >= int(_map->_first.size())) {
   1.633 +          Parent::operator=(INVALID);
   1.634 +        } else {
   1.635 +          Parent::operator=(_map->_first[value]);
   1.636 +        }
   1.637 +      }
   1.638 +
   1.639 +      /// \brief Increment operator.
   1.640 +      ///
   1.641 +      /// Increment Operator.
   1.642 +      ItemIt& operator++() {
   1.643 +        Parent::operator=(_map->IterableIntMap::Parent::
   1.644 +                          operator[](static_cast<Parent&>(*this)).next);
   1.645 +        return *this;
   1.646 +      }
   1.647 +
   1.648 +
   1.649 +    private:
   1.650 +      const IterableIntMap* _map;
   1.651 +    };
   1.652 +
   1.653 +  protected:
   1.654 +
   1.655 +    virtual void erase(const Key& key) {
   1.656 +      unlace(key);
   1.657 +      Parent::erase(key);
   1.658 +    }
   1.659 +
   1.660 +    virtual void erase(const std::vector<Key>& keys) {
   1.661 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.662 +        unlace(keys[i]);
   1.663 +      }
   1.664 +      Parent::erase(keys);
   1.665 +    }
   1.666 +
   1.667 +    virtual void clear() {
   1.668 +      _first.clear();
   1.669 +      Parent::clear();
   1.670 +    }
   1.671 +
   1.672 +  private:
   1.673 +    std::vector<ITEM> _first;
   1.674 +  };
   1.675 +
   1.676 +  namespace _maps_bits {
   1.677 +    template <typename Item, typename Value>
   1.678 +    struct IterableValueMapNode {
   1.679 +      IterableValueMapNode(Value _value = Value()) : value(_value) {}
   1.680 +      Item prev, next;
   1.681 +      Value value;
   1.682 +    };
   1.683 +  }
   1.684 +
   1.685 +  ///\ingroup graph_maps
   1.686 +  ///
   1.687 +  /// \brief Dynamic iterable map for comparable values.
   1.688 +  ///
   1.689 +  /// This class provides a special graph map type which can store
   1.690 +  /// for each graph item(node, edge, etc.) a value. For each
   1.691 +  /// value it is possible to iterate on the keys which mapped to the
   1.692 +  /// given value. The type stores for each value a linked list with
   1.693 +  /// the items which mapped to the value, and the values are stored
   1.694 +  /// in balanced binary tree. The values of the map can be accessed
   1.695 +  /// with stl compatible forward iterator.
   1.696 +  ///
   1.697 +  /// This type is not reference map so it cannot be modified with
   1.698 +  /// the subscription operator.
   1.699 +  ///
   1.700 +  /// \see InvertableMap
   1.701 +  ///
   1.702 +  /// \param GR The graph type.
   1.703 +  /// \param ITEM One of the graph's item type, the key of the map.
   1.704 +  /// \param VAL Any comparable value type.
   1.705 +  template <typename GR, typename ITEM, typename VAL>
   1.706 +  class IterableValueMap
   1.707 +    : protected ItemSetTraits<GR, ITEM>::
   1.708 +        template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type {
   1.709 +  public:
   1.710 +    typedef typename ItemSetTraits<GR, ITEM>::
   1.711 +      template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type Parent;
   1.712 +
   1.713 +    /// The key type
   1.714 +    typedef ITEM Key;
   1.715 +    /// The value type
   1.716 +    typedef VAL Value;
   1.717 +    /// The graph type
   1.718 +    typedef GR Graph;
   1.719 +
   1.720 +  public:
   1.721 +
   1.722 +    /// \brief Constructor of the Map with a given value.
   1.723 +    ///
   1.724 +    /// Constructor of the Map with a given value.
   1.725 +    explicit IterableValueMap(const Graph& graph,
   1.726 +                              const Value& value = Value())
   1.727 +      : Parent(graph, _maps_bits::IterableValueMapNode<ITEM, VAL>(value)) {
   1.728 +      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   1.729 +        lace(it);
   1.730 +      }
   1.731 +    }
   1.732 +
   1.733 +  protected:
   1.734 +
   1.735 +    void unlace(const Key& key) {
   1.736 +      typename Parent::Value& node = Parent::operator[](key);
   1.737 +      if (node.prev != INVALID) {
   1.738 +        Parent::operator[](node.prev).next = node.next;
   1.739 +      } else {
   1.740 +        if (node.next != INVALID) {
   1.741 +          _first[node.value] = node.next;
   1.742 +        } else {
   1.743 +          _first.erase(node.value);
   1.744 +        }
   1.745 +      }
   1.746 +      if (node.next != INVALID) {
   1.747 +        Parent::operator[](node.next).prev = node.prev;
   1.748 +      }
   1.749 +    }
   1.750 +
   1.751 +    void lace(const Key& key) {
   1.752 +      typename Parent::Value& node = Parent::operator[](key);
   1.753 +      typename std::map<Value, Key>::iterator it = _first.find(node.value);
   1.754 +      if (it == _first.end()) {
   1.755 +        node.prev = node.next = INVALID;
   1.756 +        if (node.next != INVALID) {
   1.757 +          Parent::operator[](node.next).prev = key;
   1.758 +        }
   1.759 +        _first.insert(std::make_pair(node.value, key));
   1.760 +      } else {
   1.761 +        node.prev = INVALID;
   1.762 +        node.next = it->second;
   1.763 +        if (node.next != INVALID) {
   1.764 +          Parent::operator[](node.next).prev = key;
   1.765 +        }
   1.766 +        it->second = key;
   1.767 +      }
   1.768 +    }
   1.769 +
   1.770 +  public:
   1.771 +
   1.772 +    /// \brief Forward iterator for values.
   1.773 +    ///
   1.774 +    /// This iterator is an stl compatible forward
   1.775 +    /// iterator on the values of the map. The values can
   1.776 +    /// be accessed in the [beginValue, endValue) range.
   1.777 +    ///
   1.778 +    class ValueIterator
   1.779 +      : public std::iterator<std::forward_iterator_tag, Value> {
   1.780 +      friend class IterableValueMap;
   1.781 +    private:
   1.782 +      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
   1.783 +        : it(_it) {}
   1.784 +    public:
   1.785 +
   1.786 +      ValueIterator() {}
   1.787 +
   1.788 +      ValueIterator& operator++() { ++it; return *this; }
   1.789 +      ValueIterator operator++(int) {
   1.790 +        ValueIterator tmp(*this);
   1.791 +        operator++();
   1.792 +        return tmp;
   1.793 +      }
   1.794 +
   1.795 +      const Value& operator*() const { return it->first; }
   1.796 +      const Value* operator->() const { return &(it->first); }
   1.797 +
   1.798 +      bool operator==(ValueIterator jt) const { return it == jt.it; }
   1.799 +      bool operator!=(ValueIterator jt) const { return it != jt.it; }
   1.800 +
   1.801 +    private:
   1.802 +      typename std::map<Value, Key>::const_iterator it;
   1.803 +    };
   1.804 +
   1.805 +    /// \brief Returns an iterator to the first value.
   1.806 +    ///
   1.807 +    /// Returns an stl compatible iterator to the
   1.808 +    /// first value of the map. The values of the
   1.809 +    /// map can be accessed in the [beginValue, endValue)
   1.810 +    /// range.
   1.811 +    ValueIterator beginValue() const {
   1.812 +      return ValueIterator(_first.begin());
   1.813 +    }
   1.814 +
   1.815 +    /// \brief Returns an iterator after the last value.
   1.816 +    ///
   1.817 +    /// Returns an stl compatible iterator after the
   1.818 +    /// last value of the map. The values of the
   1.819 +    /// map can be accessed in the [beginValue, endValue)
   1.820 +    /// range.
   1.821 +    ValueIterator endValue() const {
   1.822 +      return ValueIterator(_first.end());
   1.823 +    }
   1.824 +
   1.825 +    /// \brief Set operation of the map.
   1.826 +    ///
   1.827 +    /// Set operation of the map.
   1.828 +    void set(const Key& key, const Value& value) {
   1.829 +      unlace(key);
   1.830 +      Parent::operator[](key).value = value;
   1.831 +      lace(key);
   1.832 +    }
   1.833 +
   1.834 +    /// \brief Const subscript operator of the map.
   1.835 +    ///
   1.836 +    /// Const subscript operator of the map.
   1.837 +    const Value& operator[](const Key& key) const {
   1.838 +      return Parent::operator[](key).value;
   1.839 +    }
   1.840 +
   1.841 +    /// \brief Iterator for the keys with the same value.
   1.842 +    ///
   1.843 +    /// Iterator for the keys with the same value. It works
   1.844 +    /// like a graph item iterator in the map, it can be converted
   1.845 +    /// the item type of the map, incremented with \c ++ operator, and
   1.846 +    /// if the iterator leave the last valid item it will be equal to
   1.847 +    /// \c INVALID.
   1.848 +    class ItemIt : public ITEM {
   1.849 +    public:
   1.850 +      typedef ITEM Parent;
   1.851 +
   1.852 +      /// \brief Invalid constructor \& conversion.
   1.853 +      ///
   1.854 +      /// This constructor initializes the item to be invalid.
   1.855 +      /// \sa Invalid for more details.
   1.856 +      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   1.857 +
   1.858 +      /// \brief Creates an iterator with a value.
   1.859 +      ///
   1.860 +      /// Creates an iterator with a value. It iterates on the
   1.861 +      /// keys which have the given value.
   1.862 +      /// \param map The IterableValueMap
   1.863 +      /// \param value The value
   1.864 +      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
   1.865 +        typename std::map<Value, Key>::const_iterator it =
   1.866 +          map._first.find(value);
   1.867 +        if (it == map._first.end()) {
   1.868 +          Parent::operator=(INVALID);
   1.869 +        } else {
   1.870 +          Parent::operator=(it->second);
   1.871 +        }
   1.872 +      }
   1.873 +
   1.874 +      /// \brief Increment operator.
   1.875 +      ///
   1.876 +      /// Increment Operator.
   1.877 +      ItemIt& operator++() {
   1.878 +        Parent::operator=(_map->IterableValueMap::Parent::
   1.879 +                          operator[](static_cast<Parent&>(*this)).next);
   1.880 +        return *this;
   1.881 +      }
   1.882 +
   1.883 +
   1.884 +    private:
   1.885 +      const IterableValueMap* _map;
   1.886 +    };
   1.887 +
   1.888 +  protected:
   1.889 +
   1.890 +    virtual void add(const Key& key) {
   1.891 +      Parent::add(key);
   1.892 +      unlace(key);
   1.893 +    }
   1.894 +
   1.895 +    virtual void add(const std::vector<Key>& keys) {
   1.896 +      Parent::add(keys);
   1.897 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.898 +        lace(keys[i]);
   1.899 +      }
   1.900 +    }
   1.901 +
   1.902 +    virtual void erase(const Key& key) {
   1.903 +      unlace(key);
   1.904 +      Parent::erase(key);
   1.905 +    }
   1.906 +
   1.907 +    virtual void erase(const std::vector<Key>& keys) {
   1.908 +      for (int i = 0; i < int(keys.size()); ++i) {
   1.909 +        unlace(keys[i]);
   1.910 +      }
   1.911 +      Parent::erase(keys);
   1.912 +    }
   1.913 +
   1.914 +    virtual void build() {
   1.915 +      Parent::build();
   1.916 +      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
   1.917 +        lace(it);
   1.918 +      }
   1.919 +    }
   1.920 +
   1.921 +    virtual void clear() {
   1.922 +      _first.clear();
   1.923 +      Parent::clear();
   1.924 +    }
   1.925 +
   1.926 +  private:
   1.927 +    std::map<Value, Key> _first;
   1.928 +  };
   1.929 +
   1.930    /// \brief Map of the source nodes of arcs in a digraph.
   1.931    ///
   1.932    /// SourceMap provides access for the source node of each arc in a digraph,
   1.933 @@ -2480,7 +3369,7 @@
   1.934    /// in constant time. On the other hand, the values are updated automatically
   1.935    /// whenever the digraph changes.
   1.936    ///
   1.937 -  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
   1.938 +  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
   1.939    /// may provide alternative ways to modify the digraph.
   1.940    /// The correct behavior of InDegMap is not guarantied if these additional
   1.941    /// features are used. For example the functions
   1.942 @@ -2496,7 +3385,7 @@
   1.943        ::ItemNotifier::ObserverBase {
   1.944  
   1.945    public:
   1.946 -    
   1.947 +
   1.948      /// The graph type of InDegMap
   1.949      typedef GR Graph;
   1.950      typedef GR Digraph;
   1.951 @@ -2610,7 +3499,7 @@
   1.952    /// in constant time. On the other hand, the values are updated automatically
   1.953    /// whenever the digraph changes.
   1.954    ///
   1.955 -  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
   1.956 +  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
   1.957    /// may provide alternative ways to modify the digraph.
   1.958    /// The correct behavior of OutDegMap is not guarantied if these additional
   1.959    /// features are used. For example the functions
     2.1 --- a/test/maps_test.cc	Thu Jun 11 23:13:24 2009 +0200
     2.2 +++ b/test/maps_test.cc	Sat Jun 27 13:07:26 2009 +0200
     2.3 @@ -349,5 +349,192 @@
     2.4        check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
     2.5    }
     2.6  
     2.7 +  // Iterable bool map
     2.8 +  {
     2.9 +    typedef SmartGraph Graph;
    2.10 +    typedef SmartGraph::Node Item;
    2.11 +
    2.12 +    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
    2.13 +    checkConcept<ReadWriteMap<Item, int>, Ibm>();
    2.14 +
    2.15 +    const int num = 10;
    2.16 +    Graph g;
    2.17 +    std::vector<Item> items;
    2.18 +    for (int i = 0; i < num; ++i) {
    2.19 +      items.push_back(g.addNode());
    2.20 +    }
    2.21 +
    2.22 +    Ibm map1(g, true);
    2.23 +    int n = 0;
    2.24 +    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    2.25 +      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
    2.26 +      ++n;
    2.27 +    }
    2.28 +    check(n == num, "Wrong number");
    2.29 +
    2.30 +    n = 0;
    2.31 +    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    2.32 +        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    2.33 +        ++n;
    2.34 +    }
    2.35 +    check(n == num, "Wrong number");
    2.36 +    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
    2.37 +    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
    2.38 +
    2.39 +    map1[items[5]] = true;
    2.40 +
    2.41 +    n = 0;
    2.42 +    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    2.43 +        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    2.44 +        ++n;
    2.45 +    }
    2.46 +    check(n == num, "Wrong number");
    2.47 +
    2.48 +    map1[items[num / 2]] = false;
    2.49 +    check(map1[items[num / 2]] == false, "Wrong map value");
    2.50 +
    2.51 +    n = 0;
    2.52 +    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    2.53 +        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    2.54 +        ++n;
    2.55 +    }
    2.56 +    check(n == num - 1, "Wrong number");
    2.57 +
    2.58 +    n = 0;
    2.59 +    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    2.60 +        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    2.61 +        ++n;
    2.62 +    }
    2.63 +    check(n == 1, "Wrong number");
    2.64 +
    2.65 +    map1[items[0]] = false;
    2.66 +    check(map1[items[0]] == false, "Wrong map value");
    2.67 +
    2.68 +    map1[items[num - 1]] = false;
    2.69 +    check(map1[items[num - 1]] == false, "Wrong map value");
    2.70 +
    2.71 +    n = 0;
    2.72 +    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    2.73 +        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    2.74 +        ++n;
    2.75 +    }
    2.76 +    check(n == num - 3, "Wrong number");
    2.77 +    check(map1.trueNum() == num - 3, "Wrong number");
    2.78 +
    2.79 +    n = 0;
    2.80 +    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    2.81 +        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    2.82 +        ++n;
    2.83 +    }
    2.84 +    check(n == 3, "Wrong number");
    2.85 +    check(map1.falseNum() == 3, "Wrong number");
    2.86 +  }
    2.87 +
    2.88 +  // Iterable int map
    2.89 +  {
    2.90 +    typedef SmartGraph Graph;
    2.91 +    typedef SmartGraph::Node Item;
    2.92 +    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
    2.93 +
    2.94 +    checkConcept<ReadWriteMap<Item, int>, Iim>();
    2.95 +
    2.96 +    const int num = 10;
    2.97 +    Graph g;
    2.98 +    std::vector<Item> items;
    2.99 +    for (int i = 0; i < num; ++i) {
   2.100 +      items.push_back(g.addNode());
   2.101 +    }
   2.102 +
   2.103 +    Iim map1(g);
   2.104 +    check(map1.size() == 0, "Wrong size");
   2.105 +
   2.106 +    for (int i = 0; i < num; ++i) {
   2.107 +      map1[items[i]] = i;
   2.108 +    }
   2.109 +    check(map1.size() == num, "Wrong size");
   2.110 +
   2.111 +    for (int i = 0; i < num; ++i) {
   2.112 +      Iim::ItemIt it(map1, i);
   2.113 +      check(static_cast<Item>(it) == items[i], "Wrong value");
   2.114 +      ++it;
   2.115 +      check(static_cast<Item>(it) == INVALID, "Wrong value");
   2.116 +    }
   2.117 +
   2.118 +    for (int i = 0; i < num; ++i) {
   2.119 +      map1[items[i]] = i % 2;
   2.120 +    }
   2.121 +    check(map1.size() == 2, "Wrong size");
   2.122 +
   2.123 +    int n = 0;
   2.124 +    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
   2.125 +      check(map1[static_cast<Item>(it)] == 0, "Wrong Value");
   2.126 +      ++n;
   2.127 +    }
   2.128 +    check(n == (num + 1) / 2, "Wrong number");
   2.129 +
   2.130 +    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
   2.131 +      check(map1[static_cast<Item>(it)] == 1, "Wrong Value");
   2.132 +      ++n;
   2.133 +    }
   2.134 +    check(n == num, "Wrong number");
   2.135 +
   2.136 +  }
   2.137 +
   2.138 +  // Iterable value map
   2.139 +  {
   2.140 +    typedef SmartGraph Graph;
   2.141 +    typedef SmartGraph::Node Item;
   2.142 +    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
   2.143 +
   2.144 +    checkConcept<ReadWriteMap<Item, double>, Ivm>();
   2.145 +
   2.146 +    const int num = 10;
   2.147 +    Graph g;
   2.148 +    std::vector<Item> items;
   2.149 +    for (int i = 0; i < num; ++i) {
   2.150 +      items.push_back(g.addNode());
   2.151 +    }
   2.152 +
   2.153 +    Ivm map1(g, 0.0);
   2.154 +    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
   2.155 +    check(*map1.beginValue() == 0.0, "Wrong value");
   2.156 +
   2.157 +    for (int i = 0; i < num; ++i) {
   2.158 +      map1.set(items[i], static_cast<double>(i));
   2.159 +    }
   2.160 +    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
   2.161 +
   2.162 +    for (int i = 0; i < num; ++i) {
   2.163 +      Ivm::ItemIt it(map1, static_cast<double>(i));
   2.164 +      check(static_cast<Item>(it) == items[i], "Wrong value");
   2.165 +      ++it;
   2.166 +      check(static_cast<Item>(it) == INVALID, "Wrong value");
   2.167 +    }
   2.168 +
   2.169 +    for (Ivm::ValueIterator vit = map1.beginValue();
   2.170 +         vit != map1.endValue(); ++vit) {
   2.171 +      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
   2.172 +            "Wrong ValueIterator");
   2.173 +    }
   2.174 +
   2.175 +    for (int i = 0; i < num; ++i) {
   2.176 +      map1.set(items[i], static_cast<double>(i % 2));
   2.177 +    }
   2.178 +    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
   2.179 +
   2.180 +    int n = 0;
   2.181 +    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
   2.182 +      check(map1[static_cast<Item>(it)] == 0.0, "Wrong Value");
   2.183 +      ++n;
   2.184 +    }
   2.185 +    check(n == (num + 1) / 2, "Wrong number");
   2.186 +
   2.187 +    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
   2.188 +      check(map1[static_cast<Item>(it)] == 1.0, "Wrong Value");
   2.189 +      ++n;
   2.190 +    }
   2.191 +    check(n == num, "Wrong number");
   2.192 +
   2.193 +  }
   2.194    return 0;
   2.195  }