# HG changeset patch
# User deba
# Date 1130945113 0
# Node ID dce1f28ac595b8be375c397cb6d56803fdeb1c32
# Parent  a2a454f1232dc0b9b79ab443b42594a0cbf4b82a
IterableIntMap

todo: documentation need

diff -r a2a454f1232d -r dce1f28ac595 lemon/iterable_maps.h
--- a/lemon/iterable_maps.h	Wed Nov 02 15:24:38 2005 +0000
+++ b/lemon/iterable_maps.h	Wed Nov 02 15:25:13 2005 +0000
@@ -14,6 +14,8 @@
  *
  */
 
+#include <lemon/traits.h>
+#include <lemon/invalid.h>
 #include <vector>
 #include <limits>
 
@@ -246,5 +248,197 @@
     };  
   };
 
+
+  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;
+  };
+
   /// @}
 }