alpar@1677: /* -*- C++ -*-
alpar@1677:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1677:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1677:  *
alpar@1677:  * Permission to use, modify and distribute this software is granted
alpar@1677:  * provided that this copyright notice appears in all copies. For
alpar@1677:  * precise terms see the accompanying LICENSE file.
alpar@1677:  *
alpar@1677:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1677:  * express or implied, and with no claim as to its suitability for any
alpar@1677:  * purpose.
alpar@1677:  *
alpar@1677:  */
alpar@1677: 
deba@1993: #include <lemon/bits/traits.h>
deba@1993: #include <lemon/bits/invalid.h>
deba@1931: 
deba@1990: #include <lemon/bits/default_map.h>
deba@2031: #include <lemon/bits/map_extender.h>
deba@1990: 
alpar@1677: #include <vector>
deba@1931: #include <map>
deba@1931: 
deba@1931: #include <iterator>
alpar@1677: #include <limits>
alpar@1677: 
alpar@1677: ///\ingroup maps
alpar@1677: ///\file
alpar@1677: ///\brief Maps that makes it possible to iterate through the keys having
alpar@1677: ///a certain value
alpar@1677: ///
alpar@1677: ///
alpar@1677: 
alpar@1677: 
alpar@1677: namespace lemon {
deba@1913: 
deba@1931:   ///\ingroup graph_maps
deba@1913:   ///
deba@1913:   /// \brief Dynamic iterable bool map.
deba@1913:   ///
deba@1913:   /// This class provides a special graph map type which can store
deba@1913:   /// for each graph item(node, edge, etc.) a bool value. For both 
deba@1913:   /// the true and the false it is possible to iterate on the keys which
deba@1913:   /// mapped to the given value.
deba@1913:   /// 
deba@1913:   /// \param _Graph The graph type.
deba@1913:   /// \param _Item One of the graph's item type, the key of the map.
deba@1913:   template <typename _Graph, typename _Item>
deba@1990:   class IterableBoolMap : protected DefaultMap<_Graph, _Item, int> {
deba@1913:   private:
deba@1913:     typedef _Graph Graph;
deba@1913:     
deba@1931:     typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
deba@1990:     typedef DefaultMap<_Graph, _Item, int> Parent;
deba@1913:     
deba@1931:     std::vector<_Item> array;
deba@1913:     int sep;
deba@1913: 
deba@1913:     const Graph& graph;
alpar@1677: 
alpar@1677:   public:
alpar@1805: 
deba@1913:     /// Indicates that the map if reference map.
deba@1913:     typedef True ReferenceMapTag;
alpar@1805: 
deba@1913:     /// The key type
deba@1931:     typedef _Item Key;
deba@1913:     /// The value type
deba@1913:     typedef bool Value;
deba@1913:     /// The const reference type.    
deba@1913:     typedef const Value& ConstReference;
deba@1913: 
deba@1931:   private:
deba@1931: 
deba@1931:     int position(const Key& key) const {
deba@1931:       return Parent::operator[](key);
deba@1931:     }
deba@1931: 
deba@1931:   public:
deba@1913: 
deba@1913:     /// \brief Refernce to the value of the map.
deba@1913:     ///
deba@1913:     /// This class is near to similar to the bool type. It can
deba@1913:     /// be converted to bool and it has the same operators.
deba@1913:     class Reference {
deba@1913:       friend class IterableBoolMap;
deba@1913:     private:
deba@1913:       Reference(IterableBoolMap& map, const Key& key) 
deba@1913: 	: _key(key), _map(map) {} 
alpar@1677:     public:
deba@1913: 
deba@1913:       Reference& operator=(const Reference& value) {
deba@1913: 	_map.set(_key, (bool)value);
deba@1913:  	return *this;
deba@1913:       }
deba@1913: 
deba@1913:       operator bool() const { 
deba@1913: 	return static_cast<const IterableBoolMap&>(_map)[_key]; 
deba@1913:       }
deba@1913: 
deba@1913:       Reference& operator=(bool value) { 
deba@1913: 	_map.set(_key, value); 
deba@1913: 	return *this; 
deba@1913:       }
deba@1913:       Reference& operator&=(bool value) {
deba@1913: 	_map.set(_key, _map[_key] & value); 
deba@1913: 	return *this; 	
deba@1913:       }
deba@1913:       Reference& operator|=(bool value) {
deba@1913: 	_map.set(_key, _map[_key] | value); 
deba@1913: 	return *this; 	
deba@1913:       }
deba@1913:       Reference& operator^=(bool value) {
deba@1913: 	_map.set(_key, _map[_key] ^ value); 
deba@1913: 	return *this; 	
deba@1913:       }
deba@1913:     private:
deba@1913:       Key _key;
deba@1913:       IterableBoolMap& _map; 
alpar@1677:     };
deba@1913:     
deba@1913:     /// \brief Constructor of the Map with a default value.
deba@1913:     ///
deba@1913:     /// Constructor of the Map with a default value.
deba@1913:     IterableBoolMap(const Graph& _graph, bool def = false) 
deba@1913:       : Parent(_graph), graph(_graph) {
deba@1931:       for (KeyIt it(graph); it != INVALID; ++it) {
deba@1913:         Parent::set(it, array.size());
deba@1913:         array.push_back(it);
deba@1913:       }
deba@1913:       sep = (def ? array.size() : 0);
deba@1913:     }
deba@1913: 
deba@1913:     /// \brief Const subscript operator of the map.
deba@1913:     ///
deba@1913:     /// Const subscript operator of the map.
deba@1931:     bool operator[](const Key& key) const {
deba@1931:       return position(key) < sep;
deba@1913:     }
deba@1913: 
deba@1913:     /// \brief Subscript operator of the map.
deba@1913:     ///
deba@1913:     /// Subscript operator of the map.
deba@1931:     Reference operator[](const Key& key) {
deba@1931:       return Reference(*this, key);
deba@1913:     }
deba@1913: 
deba@1913:     /// \brief Set operation of the map.
deba@1913:     ///
deba@1913:     /// Set operation of the map.
deba@1931:     void set(const Key& key, bool value) {
deba@1931:       int pos = position(key);
deba@1913:       if (value) {
deba@1913:         if (pos < sep) return;
deba@1931:         Key tmp = array[sep];
deba@1931:         array[sep] = key;
deba@1931:         Parent::set(key, sep);
deba@1913:         array[pos] = tmp;
deba@1913:         Parent::set(tmp, pos); 
deba@1913:         ++sep;
deba@1913:       } else {
deba@1913:         if (pos >= sep) return;
deba@1913:         --sep;
deba@1931:         Key tmp = array[sep];
deba@1931:         array[sep] = key;
deba@1931:         Parent::set(key, sep);
deba@1913:         array[pos] = tmp;
deba@1913:         Parent::set(tmp, pos);
deba@1913:       }
deba@1913:     }
deba@1913: 
deba@1931:     /// \brief Returns the number of the keys mapped to true.
deba@1913:     ///
deba@1931:     /// Returns the number of the keys mapped to true.
deba@1913:     int trueNum() const {
deba@1913:       return sep;
deba@1913:     } 
deba@1913:     
deba@1931:     /// \brief Returns the number of the keys mapped to false.
deba@1913:     ///
deba@1931:     /// Returns the number of the keys mapped to false.
deba@1913:     int falseNum() const {
deba@1913:       return array.size() - sep;
deba@1913:     }
deba@1913: 
deba@1913:     /// \brief Iterator for the keys mapped to true.
deba@1913:     ///
deba@1913:     /// Iterator for the keys mapped to true. It works
deba@1913:     /// like a graph item iterator in the map, it can be converted
deba@1931:     /// the key type of the map, incremented with \c ++ operator, and
deba@1931:     /// if the iterator leave the last valid key it will be equal to 
deba@1913:     /// \c INVALID.
deba@1931:     class TrueIt : public Key {
alpar@1677:     public:
deba@1931:       typedef Key Parent;
deba@1913:       
deba@1913:       /// \brief Creates an iterator.
deba@1913:       ///
deba@1913:       /// Creates an iterator. It iterates on the 
deba@1913:       /// keys which mapped to true.
alpar@1953:       /// \param _map The IterableIntMap
deba@1913:       TrueIt(const IterableBoolMap& _map) 
deba@1913:         : Parent(_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID), 
deba@1913:           map(&_map) {}
deba@1913: 
deba@1913:       /// \brief Invalid constructor \& conversion.
deba@1913:       ///
deba@1931:       /// This constructor initializes the key to be invalid.
deba@1913:       /// \sa Invalid for more details.
deba@1913:       TrueIt(Invalid) : Parent(INVALID), map(0) {}
deba@1913: 
deba@1913:       /// \brief Increment operator.
deba@1913:       ///
deba@1913:       /// Increment Operator.
deba@1913:       TrueIt& operator++() {
deba@1913:         int pos = map->position(*this);
deba@1913:         Parent::operator=(pos > 0 ? map->array[pos - 1] : INVALID);
deba@1913:         return *this;
deba@1913:       }
deba@1913: 
deba@1913:       
deba@1913:     private:
deba@1913:       const IterableBoolMap* map;
deba@1913:     };
deba@1913: 
deba@1913:     /// \brief Iterator for the keys mapped to false.
deba@1913:     ///
deba@1913:     /// Iterator for the keys mapped to false. It works
deba@1913:     /// like a graph item iterator in the map, it can be converted
deba@1931:     /// the key type of the map, incremented with \c ++ operator, and
deba@1931:     /// if the iterator leave the last valid key it will be equal to 
deba@1913:     /// \c INVALID.
deba@1931:     class FalseIt : public Key {
deba@1913:     public:
deba@1931:       typedef Key Parent;
deba@1913:       
deba@1913:       /// \brief Creates an iterator.
deba@1913:       ///
deba@1913:       /// Creates an iterator. It iterates on the 
deba@1913:       /// keys which mapped to false.
alpar@1953:       /// \param _map The IterableIntMap
deba@1913:       FalseIt(const IterableBoolMap& _map) 
deba@1931:         : Parent(_map.sep < (int)_map.array.size() ? 
deba@1931:                  _map.array.back() : INVALID), map(&_map) {}
deba@1913: 
deba@1913:       /// \brief Invalid constructor \& conversion.
deba@1913:       ///
deba@1931:       /// This constructor initializes the key to be invalid.
deba@1913:       /// \sa Invalid for more details.
deba@1913:       FalseIt(Invalid) : Parent(INVALID), map(0) {}
deba@1913: 
deba@1913:       /// \brief Increment operator.
deba@1913:       ///
deba@1913:       /// Increment Operator.
deba@1913:       FalseIt& operator++() {
deba@1913:         int pos = map->position(*this);
deba@1913:         Parent::operator=(pos > map->sep ? map->array[pos - 1] : INVALID);
deba@1913:         return *this;
deba@1913:       }
deba@1913: 
deba@1913:     private:
deba@1913:       const IterableBoolMap* map;
deba@1913:     };
deba@1913: 
deba@1931:     /// \brief Iterator for the keys mapped to a given value.
deba@1931:     ///
deba@1931:     /// Iterator for the keys mapped to a given value. It works
deba@1931:     /// like a graph item iterator in the map, it can be converted
deba@1931:     /// the key type of the map, incremented with \c ++ operator, and
deba@1931:     /// if the iterator leave the last valid key it will be equal to 
deba@1931:     /// \c INVALID.
deba@1931:     class ItemIt : public Key {
deba@1931:     public:
deba@1931:       typedef Key Parent;
deba@1931:       
deba@1931:       /// \brief Creates an iterator.
deba@1931:       ///
deba@1931:       /// Creates an iterator. It iterates on the 
deba@1931:       /// keys which mapped to false.
alpar@1953:       /// \param _map The IterableIntMap
deba@1931:       /// \param value Which elements should be iterated.
deba@1931:       ItemIt(const IterableBoolMap& _map, bool value) 
deba@1931:         : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
deba@1931:                  (_map.sep < (int)_map.array.size() ? 
deba@1931:                   _map.array.back() : INVALID)), map(&_map) {}
deba@1931: 
deba@1931:       /// \brief Invalid constructor \& conversion.
deba@1931:       ///
deba@1931:       /// This constructor initializes the key to be invalid.
deba@1931:       /// \sa Invalid for more details.
deba@1931:       ItemIt(Invalid) : Parent(INVALID), map(0) {}
deba@1931: 
deba@1931:       /// \brief Increment operator.
deba@1931:       ///
deba@1931:       /// Increment Operator.
deba@1931:       ItemIt& operator++() {
deba@1931:         int pos = map->position(*this);
deba@1931:         int sep = pos >= map->sep ? map->sep : 0;
deba@1931:         Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
deba@1931:         return *this;
deba@1931:       }
deba@1931: 
deba@1931:     private:
deba@1931:       const IterableBoolMap* map;
deba@1931:     };
deba@1931: 
deba@1913:   protected:
deba@1913:     
deba@1931:     virtual void add(const Key& key) {
deba@1931:       Parent::add(key);
deba@1931:       Parent::set(key, array.size());
deba@1931:       array.push_back(key);
deba@1913:     }
deba@1913: 
deba@1931:     virtual void add(const std::vector<Key>& keys) {
deba@1931:       Parent::add(keys);
deba@1931:       for (int i = 0; i < (int)keys.size(); ++i) {
deba@1931:         Parent::set(keys[i], array.size());
deba@1931:         array.push_back(keys[i]);
deba@1913:       }
deba@1913:     }
deba@1913: 
deba@1931:     virtual void erase(const Key& key) {
deba@1931:       int pos = position(key); 
deba@1913:       if (pos < sep) {
deba@1913:         --sep;
deba@1913:         Parent::set(array[sep], pos);
deba@1913:         array[pos] = array[sep];
deba@1913:         Parent::set(array.back(), sep);
deba@1913:         array[sep] = array.back();
deba@1913:         array.pop_back();
deba@1913:       } else {
deba@1913:         Parent::set(array.back(), pos);
deba@1913:         array[pos] = array.back();
deba@1913:         array.pop_back();
deba@1913:       }
deba@1931:       Parent::erase(key);
deba@1913:     }
deba@1913: 
deba@1931:     virtual void erase(const std::vector<Key>& keys) {
deba@1931:       for (int i = 0; i < (int)keys.size(); ++i) {
deba@1931:         int pos = position(keys[i]); 
deba@1913:         if (pos < sep) {
deba@1913:           --sep;
deba@1913:           Parent::set(array[sep], pos);
deba@1913:           array[pos] = array[sep];
deba@1913:           Parent::set(array.back(), sep);
deba@1913:           array[sep] = array.back();
deba@1913:           array.pop_back();
deba@1913:         } else {
deba@1913:           Parent::set(array.back(), pos);
deba@1913:           array[pos] = array.back();
deba@1913:           array.pop_back();
deba@1913:         }
deba@1913:       }
deba@1931:       Parent::erase(keys);
deba@1913:     }    
deba@1913: 
deba@1913:     virtual void build() {
deba@1913:       Parent::build();
deba@1931:       for (KeyIt it(graph); it != INVALID; ++it) {
deba@1913:         Parent::set(it, array.size());
deba@1913:         array.push_back(it);
deba@1913:       }
deba@1913:       sep = 0;      
deba@1913:     }
deba@1913: 
deba@1913:     virtual void clear() {
deba@1913:       array.clear();
deba@1913:       sep = 0;
deba@1913:       Parent::clear();
deba@1913:     }
deba@1913:     
alpar@1677:   };
alpar@1873:   
deba@1752: 
deba@1752:   namespace _iterable_maps_bits {
deba@1752:     template <typename Item>
deba@1752:     struct IterableIntMapNode {
deba@1913:       IterableIntMapNode() : value(-1) {}
deba@1810:       IterableIntMapNode(int _value) : value(_value) {}
deba@1752:       Item prev, next;
deba@1752:       int value;
deba@1752:     };
deba@1752:   }
deba@1752: 
deba@1931:   ///\ingroup graph_maps
deba@1752:   ///
deba@1752:   /// \brief Dynamic iterable integer map.
deba@1752:   ///
deba@1810:   /// This class provides a special graph map type which can store
deba@1810:   /// for each graph item(node, edge, etc.) an integer value. For each
deba@1810:   /// non negative value it is possible to iterate on the keys which
deba@1810:   /// mapped to the given value.
deba@1810:   /// 
deba@1810:   /// \param _Graph The graph type.
deba@1810:   /// \param _Item One of the graph's item type, the key of the map.
deba@1752:   template <typename _Graph, typename _Item>
deba@1990:   class IterableIntMap 
deba@2031:     : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
deba@2031:                                        IterableIntMapNode<_Item> > >{
deba@1752:   public:
deba@2031:     typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
deba@2031:                                    IterableIntMapNode<_Item> > > Parent;
deba@1752: 
deba@1810:     /// The key type
deba@1752:     typedef _Item Key;
deba@1810:     /// The value type
deba@1752:     typedef int Value;
deba@1810:     /// The graph type
deba@1752:     typedef _Graph Graph;
deba@1752: 
deba@1810:     /// \brief Constructor of the Map.
deba@1810:     ///
deba@1810:     /// Constructor of the Map. It set all values -1.
deba@1810:     explicit IterableIntMap(const Graph& graph) 
deba@1913:       : Parent(graph) {}
deba@1810: 
deba@1810:     /// \brief Constructor of the Map with a given value.
deba@1810:     ///
deba@1810:     /// Constructor of the Map with a given value.
deba@1810:     explicit IterableIntMap(const Graph& graph, int value) 
deba@1810:       : Parent(graph, _iterable_maps_bits::IterableIntMapNode<_Item>(value)) {
deba@1810:       if (value >= 0) {
deba@1810: 	for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@1810: 	  lace(it);
deba@1810: 	}
deba@1810:       }
deba@1810:     }
deba@1752: 
deba@1752:   private:
deba@1752:     
deba@1752:     void unlace(const Key& key) {
deba@1752:       typename Parent::Value& node = Parent::operator[](key);
deba@1752:       if (node.value < 0) return;
deba@1752:       if (node.prev != INVALID) {
deba@1752: 	Parent::operator[](node.prev).next = node.next;	
deba@1752:       } else {
deba@1752: 	first[node.value] = node.next;
deba@1752:       }
deba@1752:       if (node.next != INVALID) {
deba@1752: 	Parent::operator[](node.next).prev = node.prev;
deba@1752:       }
deba@1752:       while (!first.empty() && first.back() == INVALID) {
deba@1752: 	first.pop_back();
deba@1752:       }
deba@1752:     }
deba@1752: 
deba@1752:     void lace(const Key& key) {
deba@1752:       typename Parent::Value& node = Parent::operator[](key);
deba@1752:       if (node.value < 0) return;
deba@1752:       if (node.value >= (int)first.size()) {
deba@1752: 	first.resize(node.value + 1, INVALID);
deba@1752:       } 
deba@1752:       node.prev = INVALID;
deba@1752:       node.next = first[node.value];
deba@1752:       if (node.next != INVALID) {
deba@1752: 	Parent::operator[](node.next).prev = key;	
deba@1752:       }
deba@1752:       first[node.value] = key;
deba@1752:     }
deba@1752: 
deba@1752:   public:
deba@1752: 
deba@1810:     /// Indicates that the map if reference map.
deba@1752:     typedef True ReferenceMapTag;
deba@1752: 
deba@1810:     /// \brief Refernce to the value of the map.
deba@1810:     ///
deba@1810:     /// This class is near to similar to the int type. It can
deba@1810:     /// be converted to int and it has the same operators.
deba@1752:     class Reference {
deba@1752:       friend class IterableIntMap;
deba@1752:     private:
deba@1752:       Reference(IterableIntMap& map, const Key& key) 
deba@1752: 	: _key(key), _map(map) {} 
deba@1752:     public:
deba@1752: 
deba@1752:       Reference& operator=(const Reference& value) {
deba@1752: 	_map.set(_key, (const int&)value);
deba@1752:  	return *this;
deba@1752:       }
deba@1752: 
deba@1752:       operator const int&() const { 
deba@1752: 	return static_cast<const IterableIntMap&>(_map)[_key]; 
deba@1752:       }
deba@1752: 
deba@1752:       Reference& operator=(int value) { 
deba@1752: 	_map.set(_key, value); 
deba@1752: 	return *this; 
deba@1752:       }
deba@1759:       Reference& operator++() {
deba@1759: 	_map.set(_key, _map[_key] + 1); 
deba@1759: 	return *this; 	
deba@1759:       }
deba@1759:       int operator++(int) {
deba@1759: 	int value = _map[_key];
deba@1759: 	_map.set(_key, value + 1); 
deba@1759: 	return value; 	
deba@1759:       }
deba@1759:       Reference& operator--() {
deba@1759: 	_map.set(_key, _map[_key] - 1); 
deba@1759: 	return *this; 	
deba@1759:       }
deba@1759:       int operator--(int) {
deba@1759: 	int value = _map[_key];
deba@1759: 	_map.set(_key, value - 1); 
deba@1759: 	return value; 	
deba@1759:       }
deba@1752:       Reference& operator+=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] + value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator-=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] - value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator*=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] * value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator/=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] / value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator%=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] % value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator&=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] & value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator|=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] | value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator^=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] ^ value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator<<=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] << value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752:       Reference& operator>>=(int value) { 
deba@1752: 	_map.set(_key, _map[_key] >> value); 
deba@1752: 	return *this;
deba@1752:       }
deba@1752: 
deba@1752:     private:
deba@1752:       Key _key;
deba@1752:       IterableIntMap& _map; 
deba@1752:     };
deba@1810: 
deba@1810:     /// The const reference type.    
deba@1752:     typedef const Value& ConstReference;
deba@1752: 
deba@1810:     /// \brief Gives back the maximal value plus one.
deba@1810:     ///
deba@1810:     /// Gives back the maximal value plus one.
deba@1931:     unsigned int size() const {
deba@1931:       return first.size();
deba@1752:     }
deba@1752:     
deba@1810:     /// \brief Set operation of the map.
deba@1810:     ///
deba@1810:     /// Set operation of the map.
deba@1752:     void set(const Key& key, const Value& value) {
deba@1752:       unlace(key);
deba@1752:       Parent::operator[](key).value = value;
deba@1752:       lace(key);
deba@1752:     }
deba@1752: 
deba@1810:     /// \brief Const subscript operator of the map.
deba@1810:     ///
deba@1810:     /// Const subscript operator of the map.
deba@1752:     const Value& operator[](const Key& key) const {
deba@1752:       return Parent::operator[](key).value;
deba@1752:     }
deba@1752: 
deba@1810:     /// \brief Subscript operator of the map.
deba@1810:     ///
deba@1810:     /// Subscript operator of the map.
deba@1752:     Reference operator[](const Key& key) {
deba@1752:       return Reference(*this, key);
deba@1752:     }
deba@1752: 
deba@1810:     /// \brief Iterator for the keys with the same value.
deba@1810:     ///
deba@1810:     /// Iterator for the keys with the same value. It works
deba@1810:     /// like a graph item iterator in the map, it can be converted
deba@1810:     /// the item type of the map, incremented with \c ++ operator, and
deba@1810:     /// if the iterator leave the last valid item it will be equal to 
deba@1810:     /// \c INVALID.
deba@1752:     class ItemIt : public _Item {
deba@1752:     public:
deba@1752:       typedef _Item Parent;
deba@1752: 
deba@1810:       /// \brief Invalid constructor \& conversion.
deba@1810:       ///
deba@1810:       /// This constructor initializes the item to be invalid.
deba@1810:       /// \sa Invalid for more details.
deba@1752:       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@1752: 
deba@1810:       /// \brief Creates an iterator with a value.
deba@1810:       ///
deba@1810:       /// Creates an iterator with a value. It iterates on the 
deba@1810:       /// keys which have the given value.
deba@1810:       /// \param map The IterableIntMap
deba@1810:       /// \param value The value
deba@1752:       ItemIt(const IterableIntMap& map, int value) : _map(&map) {
deba@1752: 	if (value < 0 || value >= (int)_map->first.size()) {	  
deba@1752: 	  Parent::operator=(INVALID);
deba@1752: 	} else {
deba@1752: 	  Parent::operator=(_map->first[value]);
deba@1752: 	}
deba@1752:       } 
deba@1752: 
deba@1810:       /// \brief Increment operator.
deba@1810:       ///
deba@1810:       /// Increment Operator.
deba@1752:       ItemIt& operator++() {
deba@1752: 	Parent::operator=(_map->IterableIntMap::Parent::
deba@1752: 			  operator[](static_cast<Parent&>(*this)).next);
deba@1752: 	return *this;
deba@1752:       }
deba@1752: 
deba@1752: 
deba@1752:     private:
deba@1752:       const IterableIntMap* _map;
deba@1752:     };
deba@1752: 
deba@1752:   protected:
deba@1752:     
deba@1752:     virtual void erase(const Key& key) {
deba@1752:       unlace(key);
deba@1752:       Parent::erase(key);
deba@1752:     }
deba@1752: 
deba@1913:     virtual void erase(const std::vector<Key>& keys) {
deba@1931:       for (int i = 0; i < (int)keys.size(); ++i) {
deba@1913:         unlace(keys[i]);
deba@1913:       }
deba@1913:       Parent::erase(keys);
deba@1913:     }
deba@1913: 
deba@1752:     virtual void clear() {
deba@1752:       first.clear();
deba@1752:       Parent::clear();
deba@1752:     }
deba@1752: 
deba@1752:   private:
deba@1752:     std::vector<_Item> first;
deba@1752:   };
deba@1752: 
deba@1931:   namespace _iterable_maps_bits {
deba@1931:     template <typename Item, typename Value>
deba@1931:     struct IterableValueMapNode {
deba@1931:       IterableValueMapNode(Value _value = Value()) : value(_value) {}
deba@1931:       Item prev, next;
deba@1931:       Value value;
deba@1931:     };
deba@1931:   }
deba@1931: 
deba@1931:   ///\ingroup graph_maps
deba@1931:   ///
deba@1931:   /// \brief Dynamic iterable map for comparable values.
deba@1931:   ///
deba@1931:   /// This class provides a special graph map type which can store
deba@1931:   /// for each graph item(node, edge, etc.) a value. For each
deba@1931:   /// value it is possible to iterate on the keys which mapped to the 
deba@1931:   /// given value. The type stores for each value a linked list with
deba@1931:   /// the items which mapped to the value, and the values are stored
deba@1931:   /// in balanced binary tree. The values of the map can be accessed
deba@1931:   /// with stl compatible forward iterator.
deba@1931:   ///
deba@1931:   /// This type is not reference map so it cannot be modified with
deba@1931:   /// the subscription operator.
deba@1931:   ///
deba@1931:   /// \see InvertableMap
deba@1931:   /// 
deba@1931:   /// \param _Graph The graph type.
deba@1931:   /// \param _Item One of the graph's item type, the key of the map.
deba@1931:   /// \param _Value Any comparable value type.
deba@1931:   template <typename _Graph, typename _Item, typename _Value>
deba@1990:   class IterableValueMap 
deba@2031:     : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
deba@2031:                                        IterableValueMapNode<_Item, _Value> > >{
deba@1931:   public:
deba@2031:     typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
deba@2031:                                    IterableValueMapNode<_Item, _Value> > >
deba@2031:     Parent;
deba@1931: 
deba@1931:     /// The key type
deba@1931:     typedef _Item Key;
deba@1931:     /// The value type
deba@1931:     typedef _Value Value;
deba@1931:     /// The graph type
deba@1931:     typedef _Graph Graph;
deba@1931: 
deba@1990:   public:
deba@1990: 
deba@1931:     /// \brief Constructor of the Map with a given value.
deba@1931:     ///
deba@1931:     /// Constructor of the Map with a given value.
deba@1931:     explicit IterableValueMap(const Graph& graph, 
deba@1931:                               const Value& value = Value()) 
deba@1990:       : Parent(graph, _iterable_maps_bits::
deba@1990:                IterableValueMapNode<_Item, _Value>(value)) {
deba@2031:       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@1931:         lace(it);
deba@1931:       }
deba@1931:     }
deba@1931: 
deba@1990:   protected:
deba@1931:     
deba@1931:     void unlace(const Key& key) {
deba@1931:       typename Parent::Value& node = Parent::operator[](key);
deba@1931:       if (node.prev != INVALID) {
deba@1931: 	Parent::operator[](node.prev).next = node.next;	
deba@1931:       } else {
deba@1931:         if (node.next != INVALID) {
deba@1931:           first[node.value] = node.next;
deba@1931:         } else {
deba@1931:           first.erase(node.value);
deba@1931:         }
deba@1931:       }
deba@1931:       if (node.next != INVALID) {
deba@1931: 	Parent::operator[](node.next).prev = node.prev;
deba@1931:       }
deba@1931:     }
deba@1931: 
deba@1931:     void lace(const Key& key) {
deba@1931:       typename Parent::Value& node = Parent::operator[](key);
deba@1931:       typename std::map<Value, Key>::iterator it = first.find(node.value);
deba@1931:       if (it == first.end()) {
deba@1931:         node.prev = node.next = INVALID;
deba@1931:         if (node.next != INVALID) {
deba@1931:           Parent::operator[](node.next).prev = key;	
deba@1931:         }
deba@1931:         first.insert(make_pair(node.value, key));
deba@1931:       } else {
deba@1931:         node.prev = INVALID;
deba@1931:         node.next = it->second;
deba@1931:         if (node.next != INVALID) {
deba@1931:           Parent::operator[](node.next).prev = key;	
deba@1931:         }
deba@1931:         it->second = key;
deba@1931:       }
deba@1931:     }
deba@1931: 
deba@1931:   public:
deba@1931: 
deba@1931:     /// \brief Forward iterator for values.
deba@1931:     ///
deba@1931:     /// This iterator is an stl compatible forward
deba@1931:     /// iterator on the values of the map. The values can
deba@1931:     /// be accessed in the [beginValue, endValue) range.
deba@1931:     ///
deba@1931:     class ValueIterator 
deba@1931:       : public std::iterator<std::forward_iterator_tag, Value> {
deba@1931:       friend class IterableValueMap;
deba@1931:     private:
deba@1931:       ValueIterator(typename std::map<Value, Key>::const_iterator _it) 
deba@1931:         : it(_it) {}
deba@1931:     public:
deba@1931:       
deba@1931:       ValueIterator() {}
deba@1931: 
deba@1931:       ValueIterator& operator++() { ++it; return *this; }
deba@1931:       ValueIterator operator++(int) { 
deba@1931:         ValueIterator tmp(*this); 
deba@1931:         operator++();
deba@1931:         return tmp; 
deba@1931:       }
deba@1931: 
deba@1931:       const Value& operator*() const { return it->first; }
deba@1931:       const Value* operator->() const { return &(it->first); }
deba@1931: 
deba@1931:       bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@1931:       bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@1931:       
deba@1931:     private:
deba@1931:       typename std::map<Value, Key>::const_iterator it;
deba@1931:     };
deba@1931: 
deba@1931:     /// \brief Returns an iterator to the first value.
deba@1931:     ///
deba@1931:     /// Returns an stl compatible iterator to the 
deba@1931:     /// first value of the map. The values of the
deba@1931:     /// map can be accessed in the [beginValue, endValue)
deba@1931:     /// range.
deba@1931:     ValueIterator beginValue() const {
deba@1931:       return ValueIterator(first.begin());
deba@1931:     }
deba@1931: 
deba@1931:     /// \brief Returns an iterator after the last value.
deba@1931:     ///
deba@1931:     /// Returns an stl compatible iterator after the 
deba@1931:     /// last value of the map. The values of the
deba@1931:     /// map can be accessed in the [beginValue, endValue)
deba@1931:     /// range.
deba@1931:     ValueIterator endValue() const {
deba@1931:       return ValueIterator(first.end());
deba@1931:     }
deba@1931: 
deba@1931:     /// \brief Set operation of the map.
deba@1931:     ///
deba@1931:     /// Set operation of the map.
deba@1931:     void set(const Key& key, const Value& value) {
deba@1931:       unlace(key);
deba@1931:       Parent::operator[](key).value = value;
deba@1931:       lace(key);
deba@1931:     }
deba@1931: 
deba@1931:     /// \brief Const subscript operator of the map.
deba@1931:     ///
deba@1931:     /// Const subscript operator of the map.
deba@1931:     const Value& operator[](const Key& key) const {
deba@1931:       return Parent::operator[](key).value;
deba@1931:     }
deba@1931: 
deba@1931:     /// \brief Iterator for the keys with the same value.
deba@1931:     ///
deba@1931:     /// Iterator for the keys with the same value. It works
deba@1931:     /// like a graph item iterator in the map, it can be converted
deba@1931:     /// the item type of the map, incremented with \c ++ operator, and
deba@1931:     /// if the iterator leave the last valid item it will be equal to 
deba@1931:     /// \c INVALID.
deba@1931:     class ItemIt : public _Item {
deba@1931:     public:
deba@1931:       typedef _Item Parent;
deba@1931: 
deba@1931:       /// \brief Invalid constructor \& conversion.
deba@1931:       ///
deba@1931:       /// This constructor initializes the item to be invalid.
deba@1931:       /// \sa Invalid for more details.
deba@1931:       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@1931: 
deba@1931:       /// \brief Creates an iterator with a value.
deba@1931:       ///
deba@1931:       /// Creates an iterator with a value. It iterates on the 
deba@1931:       /// keys which have the given value.
deba@1931:       /// \param map The IterableValueMap
deba@1931:       /// \param value The value
deba@1931:       ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
deba@1931:         typename std::map<Value, Key>::const_iterator it = 
deba@1931:           map.first.find(value); 
deba@1931: 	if (it == map.first.end()) {	  
deba@1931: 	  Parent::operator=(INVALID);
deba@1931: 	} else {
deba@1931: 	  Parent::operator=(it->second);
deba@1931: 	}
deba@1931:       } 
deba@1931: 
deba@1931:       /// \brief Increment operator.
deba@1931:       ///
deba@1931:       /// Increment Operator.
deba@1931:       ItemIt& operator++() {
deba@1931: 	Parent::operator=(_map->IterableValueMap::Parent::
deba@1931: 			  operator[](static_cast<Parent&>(*this)).next);
deba@1931: 	return *this;
deba@1931:       }
deba@1931: 
deba@1931: 
deba@1931:     private:
deba@1931:       const IterableValueMap* _map;
deba@1931:     };
deba@1931: 
deba@1931:   protected:
deba@1931:     
deba@1990:     virtual void add(const Key& key) {
deba@1990:       Parent::add(key);
deba@1990:       unlace(key);
deba@1990:     }
deba@1990: 
deba@1990:     virtual void add(const std::vector<Key>& keys) {
deba@1990:       Parent::add(keys);
deba@1990:       for (int i = 0; i < (int)keys.size(); ++i) {
deba@1990:         lace(keys[i]);
deba@1990:       }
deba@1990:     }
deba@1990: 
deba@1931:     virtual void erase(const Key& key) {
deba@1931:       unlace(key);
deba@1931:       Parent::erase(key);
deba@1931:     }
deba@1931: 
deba@1931:     virtual void erase(const std::vector<Key>& keys) {
deba@1931:       for (int i = 0; i < (int)keys.size(); ++i) {
deba@1931:         unlace(keys[i]);
deba@1931:       }
deba@1931:       Parent::erase(keys);
deba@1931:     }
deba@1931: 
deba@1990:     virtual void build() {
deba@1990:       Parent::build();
deba@2031:       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@1990:         lace(it);
deba@1990:       }
deba@1990:     }
deba@1990: 
deba@1931:     virtual void clear() {
deba@1931:       first.clear();
deba@1931:       Parent::clear();
deba@1931:     }
deba@1931: 
deba@1931:   private:
deba@1931:     std::map<Value, Key> first;
deba@1931:   };
deba@1931: 
alpar@1677:   /// @}
alpar@1677: }