diff -r 2d6c8075d9d0 -r 818510fa3d99 src/lemon/array_map.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/array_map.h	Wed Sep 29 15:30:04 2004 +0000
@@ -0,0 +1,349 @@
+/* -*- C++ -*-
+ * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_ARRAY_MAP_H
+#define LEMON_ARRAY_MAP_H
+
+#include <memory>
+
+#include <lemon/map_iterator.h>
+#include <lemon/map_bits.h>
+
+///\ingroup graphmaps
+///\file
+///\brief Graph maps that construates and destruates
+///their elements dynamically.
+
+namespace lemon {
+
+
+  /// \addtogroup graphmaps
+  /// @{
+	
+  /** The ArrayMap template class is graph map structure what
+   *  automatically updates the map when a key is added to or erased from
+   *  the map. This map factory uses the allocators to implement 
+   *  the container functionality.
+   *
+   *  The template parameter is the MapRegistry that the maps
+   *  will belong to and the ValueType.
+   */
+
+  template <typename MapRegistry, typename Value> 
+  class ArrayMap : public MapRegistry::MapBase {
+
+    template <typename MR, typename V> friend class ArrayMap;
+		
+  public:
+		
+    /// The graph type of the maps. 
+    typedef typename MapRegistry::Graph Graph;
+    /// The key type of the maps.
+    typedef typename MapRegistry::KeyType KeyType;
+    /// The iterator to iterate on the keys.
+    typedef typename MapRegistry::KeyIt KeyIt;
+
+    /// The MapBase of the Map which imlements the core regisitry function.
+    typedef typename MapRegistry::MapBase MapBase;
+		
+    
+  public:
+
+    /// The value type of the map.
+    typedef Value ValueType;
+    /// The reference type of the map;
+    typedef Value& ReferenceType;
+    /// The pointer type of the map;
+    typedef Value* PointerType;
+
+    /// The const value type of the map.
+    typedef const Value ConstValueType;
+    /// The const reference type of the map;
+    typedef const Value& ConstReferenceType;
+    /// The pointer type of the map;
+    typedef const Value* ConstPointerType;
+
+
+    typedef std::allocator<Value> Allocator;
+
+	
+    /** Graph and Registry initialized map constructor.
+     */
+    ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
+      allocate_memory();
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), Value());
+      }								
+    }
+
+    /** Constructor to use default value to initialize the map. 
+     */
+    ArrayMap(const Graph& g, MapRegistry& r, const Value& v) 
+      : MapBase(g, r) {
+      allocate_memory();
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), v);
+      }								
+    }
+
+    /** Constructor to copy a map of the same map type.
+     */
+    ArrayMap(const ArrayMap& copy) : MapBase(copy) {
+      capacity = copy.capacity;
+      if (capacity == 0) return;
+      values = allocator.allocate(capacity);
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), copy.values[id]);
+      }
+    }
+
+    /** Constructor to copy a map of an other map type.
+     */
+    template <typename TT>
+    ArrayMap(const ArrayMap<MapRegistry, TT>& copy) 
+      : MapBase(copy) {
+      capacity = copy.capacity;
+      if (capacity == 0) return;
+      values = allocator.allocate(capacity);
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), copy.values[id]);
+      }
+    }
+
+    /** Assign operator to copy a map of the same map type.
+     */
+    ArrayMap& operator=(const ArrayMap& copy) {
+      if (&copy == this) return *this;
+      
+      if (MapBase::getGraph() != copy.getGraph()) {
+	if (capacity != 0) {
+	  MapBase::destroy();
+	  allocator.deallocate(values, capacity);
+	}
+
+	MapBase::operator=(copy);
+	capacity = copy.capacity;
+	if (capacity == 0) return *this;
+	values = allocator.allocate(capacity);      
+      }
+
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), copy.values[id]);
+      }
+
+      return *this;
+    }
+
+    /** Assign operator to copy a map of an other map type.
+     */
+    template <typename TT>
+    ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
+
+      if (MapBase::getGraph() != copy.getGraph()) {
+	if (capacity != 0) {
+	  MapBase::destroy();
+	  allocator.deallocate(values, capacity);
+	}
+
+	MapBase::operator=(copy);
+
+	capacity = copy.capacity;
+	if (capacity == 0) return *this;
+	values = allocator.allocate(capacity);
+      }
+
+      for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	allocator.construct(&(values[id]), copy.values[id]);
+      }
+
+      return *this;
+    }
+				
+    /** The destructor of the map.
+     */
+    virtual ~ArrayMap() {
+      if (capacity != 0) {
+	MapBase::destroy();
+	allocator.deallocate(values, capacity);
+      }
+    }
+	
+	
+    /**
+     * The subscript operator. The map can be subscripted by the
+     * actual keys of the graph. 
+     */
+    ReferenceType operator[](const KeyType& key) {
+      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      return values[id];
+    } 
+		
+    /**
+     * The const subscript operator. The map can be subscripted by the
+     * actual keys of the graph. 
+     */
+    ConstReferenceType operator[](const KeyType& key) const {
+      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      return values[id];
+    }
+	
+    /** Setter function of the map. Equivalent with map[key] = val.
+     *  This is a compatibility feature with the not dereferable maps.
+     */
+    void set(const KeyType& key, const ValueType& val) {
+      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      values[id] = val;
+    }
+		
+    /** Add a new key to the map. It called by the map registry.
+     */
+    void add(const KeyType& key) {
+      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      if (id >= capacity) {
+	int new_capacity = (capacity == 0 ? 1 : capacity);
+	while (new_capacity <= id) {
+	  new_capacity <<= 1;
+	}
+	Value* new_values = allocator.allocate(new_capacity);;
+	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
+	  int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
+	  if (id != jd) {
+	    allocator.construct(&(new_values[jd]), values[jd]);
+	    allocator.destroy(&(values[jd]));
+	  }
+	}
+	if (capacity != 0) allocator.deallocate(values, capacity);
+	values = new_values;
+	capacity = new_capacity;
+      }
+      allocator.construct(&(values[id]), Value());
+    }
+		
+    /** Erase a key from the map. It called by the map registry.
+     */
+    void erase(const KeyType& key) {
+      int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
+      allocator.destroy(&(values[id]));
+    }
+
+    /** Clear the data structure.
+     */
+    void clear() {	
+      if (capacity != 0) {
+	MapBase::destroy();
+	allocator.deallocate(values, capacity);
+	capacity = 0;
+      }
+    }
+
+    /// The stl compatible pair iterator of the map.
+    typedef MapIterator<ArrayMap> Iterator;
+    /// The stl compatible const pair iterator of the map.
+    typedef MapConstIterator<ArrayMap> ConstIterator;
+
+    /** Returns the begin iterator of the map.
+     */
+    Iterator begin() {
+      return Iterator(*this, KeyIt(*MapBase::getGraph()));
+    }
+
+    /** Returns the end iterator of the map.
+     */
+    Iterator end() {
+      return Iterator(*this, INVALID);
+    }
+
+    /** Returns the begin ConstIterator of the map.
+     */
+    ConstIterator begin() const {
+      return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
+    }
+
+    /** Returns the end const_iterator of the map.
+     */
+    ConstIterator end() const {
+      return ConstIterator(*this, INVALID);
+    }
+
+    /// The KeySet of the Map.
+    typedef MapConstKeySet<ArrayMap> ConstKeySet;
+
+    /// KeySet getter function.
+    ConstKeySet keySet() const {
+      return ConstKeySet(*this); 
+    }
+
+    /// The ConstValueSet of the Map.
+    typedef MapConstValueSet<ArrayMap> ConstValueSet;
+
+    /// ConstValueSet getter function.
+    ConstValueSet valueSet() const {
+      return ConstValueSet(*this);
+    }
+
+    /// The ValueSet of the Map.
+    typedef MapValueSet<ArrayMap> ValueSet;
+
+    /// ValueSet getter function.
+    ValueSet valueSet() {
+      return ValueSet(*this);
+    }
+
+  private:
+      
+    void allocate_memory() {
+      int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
+      if (max_id == -1) {
+	capacity = 0;
+	values = 0;
+	return;
+      }
+      capacity = 1;
+      while (capacity <= max_id) {
+	capacity <<= 1;
+      }
+      values = allocator.allocate(capacity);	
+    }      
+
+    int capacity;
+    Value* values;
+    Allocator allocator;
+
+  public:
+    // STL  compatibility typedefs.
+    typedef Iterator iterator;
+    typedef ConstIterator const_iterator;
+    typedef typename Iterator::PairValueType value_type;
+    typedef typename Iterator::KeyType key_type;
+    typedef typename Iterator::ValueType data_type;
+    typedef typename Iterator::PairReferenceType reference;
+    typedef typename Iterator::PairPointerType pointer;
+    typedef typename ConstIterator::PairReferenceType const_reference;
+    typedef typename ConstIterator::PairPointerType const_pointer;
+    typedef int difference_type;		
+  };		
+
+/// @}
+
+}
+
+#endif //LEMON_ARRAY_MAP_H