#include <lemon/traits.h>

 #include <lemon/invalid.h>

   namespace _iterable_maps_bits {

     template <typename Item>

     struct IterableIntMapNode {

       IterableIntMapNode() : value(-1) {}

       Item prev, next;

       int value;

     };

   }

   ///\ingroup maps

   ///

   /// \brief Dynamic iterable integer map.

   ///

   /// \todo Document please

   template <typename _Graph, typename _Item>

   class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 

   ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {

   public:

     typedef typename ItemSetTraits<_Graph, _Item> 

     ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >

     ::Parent Parent;

     typedef _Item Key;

     typedef int Value;

     typedef _Graph Graph;

     IterableIntMap(const Graph& graph) : Parent(graph) {}

   private:

     void unlace(const Key& key) {

       typename Parent::Value& node = Parent::operator[](key);

       if (node.value < 0) return;

       if (node.prev != INVALID) {

 	Parent::operator[](node.prev).next = node.next;	

       } else {

 	first[node.value] = node.next;

       }

       if (node.next != INVALID) {

 	Parent::operator[](node.next).prev = node.prev;

       }

       while (!first.empty() && first.back() == INVALID) {

 	first.pop_back();

       }

     }

     void lace(const Key& key) {

       typename Parent::Value& node = Parent::operator[](key);

       if (node.value < 0) return;

       if (node.value >= (int)first.size()) {

 	first.resize(node.value + 1, INVALID);

       } 

       node.prev = INVALID;

       node.next = first[node.value];

       if (node.next != INVALID) {

 	Parent::operator[](node.next).prev = key;	

       }

       first[node.value] = key;

     }

   public:

     typedef True ReferenceMapTag;

     class Reference {

       friend class IterableIntMap;

     private:

       Reference(IterableIntMap& map, const Key& key) 

 	: _key(key), _map(map) {} 

     public:

       Reference& operator=(const Reference& value) {

 	_map.set(_key, (const int&)value);

  	return *this;

       }

       operator const int&() const { 

 	return static_cast<const IterableIntMap&>(_map)[_key]; 

       }

       Reference& operator=(int value) { 

 	_map.set(_key, value); 

 	return *this; 

       }

       Reference& operator+=(int value) { 

 	_map.set(_key, _map[_key] + value); 

 	return *this;

       }

       Reference& operator-=(int value) { 

 	_map.set(_key, _map[_key] - value); 

 	return *this;

       }

       Reference& operator*=(int value) { 

 	_map.set(_key, _map[_key] * value); 

 	return *this;

       }

       Reference& operator/=(int value) { 

 	_map.set(_key, _map[_key] / value); 

 	return *this;

       }

       Reference& operator%=(int value) { 

 	_map.set(_key, _map[_key] % value); 

 	return *this;

       }

       Reference& operator&=(int value) { 

 	_map.set(_key, _map[_key] & value); 

 	return *this;

       }

       Reference& operator|=(int value) { 

 	_map.set(_key, _map[_key] | value); 

 	return *this;

       }

       Reference& operator^=(int value) { 

 	_map.set(_key, _map[_key] ^ value); 

 	return *this;

       }

       Reference& operator<<=(int value) { 

 	_map.set(_key, _map[_key] << value); 

 	return *this;

       }

       Reference& operator>>=(int value) { 

 	_map.set(_key, _map[_key] >> value); 

 	return *this;

       }

     private:

       Key _key;

       IterableIntMap& _map; 

     };

     typedef const Value& ConstReference;

     int size() const {

       return (int)first.size();

     }

     void set(const Key& key, const Value& value) {

       unlace(key);

       Parent::operator[](key).value = value;

       lace(key);

     }

     const Value& operator[](const Key& key) const {

       return Parent::operator[](key).value;

     }

     Reference operator[](const Key& key) {

       return Reference(*this, key);

     }

     class ItemIt : public _Item {

     public:

       typedef _Item Parent;

       ItemIt(Invalid) : Parent(INVALID), _map(0) {}

       ItemIt(const IterableIntMap& map, int value) : _map(&map) {

 	if (value < 0 || value >= (int)_map->first.size()) {	  

 	  Parent::operator=(INVALID);

 	} else {

 	  Parent::operator=(_map->first[value]);

 	}

       } 

       ItemIt& operator++() {

 	Parent::operator=(_map->IterableIntMap::Parent::

 			  operator[](static_cast<Parent&>(*this)).next);

 	return *this;

       }

     private:

       const IterableIntMap* _map;

     };

   protected:

     virtual void erase(const Key& key) {

       unlace(key);

       Parent::erase(key);

     }

     virtual void clear() {

       first.clear();

       Parent::clear();

     }

   private:

     std::vector<_Item> first;

   };