1.1 --- a/lemon/iterable_maps.h	Wed Nov 02 15:24:38 2005 +0000
     1.2 +++ b/lemon/iterable_maps.h	Wed Nov 02 15:25:13 2005 +0000
     1.3 @@ -14,6 +14,8 @@
     1.4   *
     1.5   */
     1.6  
     1.7 +#include <lemon/traits.h>
     1.8 +#include <lemon/invalid.h>
     1.9  #include <vector>
    1.10  #include <limits>
    1.11  
    1.12 @@ -246,5 +248,197 @@
    1.13      };  
    1.14    };
    1.15  
    1.16 +
    1.17 +  namespace _iterable_maps_bits {
    1.18 +    template <typename Item>
    1.19 +    struct IterableIntMapNode {
    1.20 +      IterableIntMapNode() : value(-1) {}
    1.21 +      Item prev, next;
    1.22 +      int value;
    1.23 +    };
    1.24 +  }
    1.25 +
    1.26 +  ///\ingroup maps
    1.27 +  ///
    1.28 +  /// \brief Dynamic iterable integer map.
    1.29 +  ///
    1.30 +  /// \todo Document please
    1.31 +  template <typename _Graph, typename _Item>
    1.32 +  class IterableIntMap : protected ItemSetTraits<_Graph, _Item> 
    1.33 +  ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >::Parent {
    1.34 +  public:
    1.35 +    typedef typename ItemSetTraits<_Graph, _Item> 
    1.36 +    ::template Map<_iterable_maps_bits::IterableIntMapNode<_Item> >
    1.37 +    ::Parent Parent;
    1.38 +
    1.39 +    typedef _Item Key;
    1.40 +    typedef int Value;
    1.41 +    typedef _Graph Graph;
    1.42 +
    1.43 +    IterableIntMap(const Graph& graph) : Parent(graph) {}
    1.44 +
    1.45 +  private:
    1.46 +    
    1.47 +    void unlace(const Key& key) {
    1.48 +      typename Parent::Value& node = Parent::operator[](key);
    1.49 +      if (node.value < 0) return;
    1.50 +      if (node.prev != INVALID) {
    1.51 +	Parent::operator[](node.prev).next = node.next;	
    1.52 +      } else {
    1.53 +	first[node.value] = node.next;
    1.54 +      }
    1.55 +      if (node.next != INVALID) {
    1.56 +	Parent::operator[](node.next).prev = node.prev;
    1.57 +      }
    1.58 +      while (!first.empty() && first.back() == INVALID) {
    1.59 +	first.pop_back();
    1.60 +      }
    1.61 +    }
    1.62 +
    1.63 +    void lace(const Key& key) {
    1.64 +      typename Parent::Value& node = Parent::operator[](key);
    1.65 +      if (node.value < 0) return;
    1.66 +      if (node.value >= (int)first.size()) {
    1.67 +	first.resize(node.value + 1, INVALID);
    1.68 +      } 
    1.69 +      node.prev = INVALID;
    1.70 +      node.next = first[node.value];
    1.71 +      if (node.next != INVALID) {
    1.72 +	Parent::operator[](node.next).prev = key;	
    1.73 +      }
    1.74 +      first[node.value] = key;
    1.75 +    }
    1.76 +
    1.77 +  public:
    1.78 +
    1.79 +    typedef True ReferenceMapTag;
    1.80 +
    1.81 +    class Reference {
    1.82 +      friend class IterableIntMap;
    1.83 +    private:
    1.84 +      Reference(IterableIntMap& map, const Key& key) 
    1.85 +	: _key(key), _map(map) {} 
    1.86 +    public:
    1.87 +
    1.88 +      Reference& operator=(const Reference& value) {
    1.89 +	_map.set(_key, (const int&)value);
    1.90 + 	return *this;
    1.91 +      }
    1.92 +
    1.93 +      operator const int&() const { 
    1.94 +	return static_cast<const IterableIntMap&>(_map)[_key]; 
    1.95 +      }
    1.96 +
    1.97 +      Reference& operator=(int value) { 
    1.98 +	_map.set(_key, value); 
    1.99 +	return *this; 
   1.100 +      }
   1.101 +      Reference& operator+=(int value) { 
   1.102 +	_map.set(_key, _map[_key] + value); 
   1.103 +	return *this;
   1.104 +      }
   1.105 +      Reference& operator-=(int value) { 
   1.106 +	_map.set(_key, _map[_key] - value); 
   1.107 +	return *this;
   1.108 +      }
   1.109 +      Reference& operator*=(int value) { 
   1.110 +	_map.set(_key, _map[_key] * value); 
   1.111 +	return *this;
   1.112 +      }
   1.113 +      Reference& operator/=(int value) { 
   1.114 +	_map.set(_key, _map[_key] / value); 
   1.115 +	return *this;
   1.116 +      }
   1.117 +      Reference& operator%=(int value) { 
   1.118 +	_map.set(_key, _map[_key] % value); 
   1.119 +	return *this;
   1.120 +      }
   1.121 +      Reference& operator&=(int value) { 
   1.122 +	_map.set(_key, _map[_key] & value); 
   1.123 +	return *this;
   1.124 +      }
   1.125 +      Reference& operator|=(int value) { 
   1.126 +	_map.set(_key, _map[_key] | value); 
   1.127 +	return *this;
   1.128 +      }
   1.129 +      Reference& operator^=(int value) { 
   1.130 +	_map.set(_key, _map[_key] ^ value); 
   1.131 +	return *this;
   1.132 +      }
   1.133 +      Reference& operator<<=(int value) { 
   1.134 +	_map.set(_key, _map[_key] << value); 
   1.135 +	return *this;
   1.136 +      }
   1.137 +      Reference& operator>>=(int value) { 
   1.138 +	_map.set(_key, _map[_key] >> value); 
   1.139 +	return *this;
   1.140 +      }
   1.141 +
   1.142 +    private:
   1.143 +      Key _key;
   1.144 +      IterableIntMap& _map; 
   1.145 +    };
   1.146 +    
   1.147 +    typedef const Value& ConstReference;
   1.148 +
   1.149 +    int size() const {
   1.150 +      return (int)first.size();
   1.151 +    }
   1.152 +    
   1.153 +    void set(const Key& key, const Value& value) {
   1.154 +      unlace(key);
   1.155 +      Parent::operator[](key).value = value;
   1.156 +      lace(key);
   1.157 +    }
   1.158 +
   1.159 +    const Value& operator[](const Key& key) const {
   1.160 +      return Parent::operator[](key).value;
   1.161 +    }
   1.162 +
   1.163 +    Reference operator[](const Key& key) {
   1.164 +      return Reference(*this, key);
   1.165 +    }
   1.166 +
   1.167 +    class ItemIt : public _Item {
   1.168 +    public:
   1.169 +      typedef _Item Parent;
   1.170 +
   1.171 +      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
   1.172 +
   1.173 +      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
   1.174 +	if (value < 0 || value >= (int)_map->first.size()) {	  
   1.175 +	  Parent::operator=(INVALID);
   1.176 +	} else {
   1.177 +	  Parent::operator=(_map->first[value]);
   1.178 +	}
   1.179 +      } 
   1.180 +
   1.181 +      ItemIt& operator++() {
   1.182 +	Parent::operator=(_map->IterableIntMap::Parent::
   1.183 +			  operator[](static_cast<Parent&>(*this)).next);
   1.184 +	return *this;
   1.185 +      }
   1.186 +
   1.187 +
   1.188 +    private:
   1.189 +      const IterableIntMap* _map;
   1.190 +    };
   1.191 +
   1.192 +  protected:
   1.193 +    
   1.194 +    virtual void erase(const Key& key) {
   1.195 +      unlace(key);
   1.196 +      Parent::erase(key);
   1.197 +    }
   1.198 +
   1.199 +    virtual void clear() {
   1.200 +      first.clear();
   1.201 +      Parent::clear();
   1.202 +    }
   1.203 +
   1.204 +  private:
   1.205 +    std::vector<_Item> first;
   1.206 +  };
   1.207 +
   1.208    /// @}
   1.209  }