// -*- c++ -*-

 #ifndef ARRAY_MAP_FACTORY_H

 #define ARRAY_MAP_FACTORY_H

 #include <memory>

 #include <hugo/extended_pair.h>

 ///\ingroup graphmapfactory

 ///\file

 ///\brief Graph maps that construates and destruates

 ///their elements dynamically.

 namespace hugo {

 /// \addtogroup graphmapfactory

 /// @{

   /** The ArrayMapFactory template class is a factory class

    *  to create maps for the edge and nodes. This map factory

    *  uses the allocators to implement the container function.

    *

    *  The template parameter is the MapRegistry that the maps

    *  will belong to.

    */

   template <typename MapRegistry> 

   class ArrayMapFactory {

   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;

     /** The template Map type.

      */

     template <typename V, typename A = std::allocator<V> > 

     class Map : public MapBase {

       public:

       /// The value type of the map.

       typedef V ValueType;

       /// The value type of the map.

       typedef V Value;

       /// The reference type of the map;

       typedef Value& Reference;

       /// The pointer type of the map;

       typedef Value* Pointer;

       /// The const value type of the map.

       typedef const Value ConstValue;

       /// The const reference type of the map;

       typedef const Value& ConstReference;

       /// The pointer type of the map;

       typedef const Value* ConstPointer;

       typedef A Allocator;

       /** Default constructor for the map.

        */

       Map() : values(0), capacity(0) {}

       /** Graph and Registry initialized map constructor.

        */

       Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {

 	allocate_memory();

 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	  int id = MapBase::getGraph()->id(it);

 	  allocator.construct(&(values[id]), Value());

 	}								

       }

       /** Constructor to use default value to initialize the map. 

        */

       Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {

 	allocate_memory();

 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	  int id = MapBase::getGraph()->id(it);

 	  allocator.construct(&(values[id]), v);

 	}								

       }

       /** Constructor to copy a map of the same map type.

        */

       Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {

 	capacity = copy.capacity;

 	if (capacity == 0) return;

 	values = allocator.allocate(capacity);

 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	  int id = MapBase::getGraph()->id(it);

 	  allocator.construct(&(values[id]), copy.values[id]);

 	}

       }

       /** Constructor to copy a map of an other map type.

        */

       template <typename CMap> Map(const CMap& copy) 

 	: MapBase(copy), capacity(0), values(0) {

 	if (MapBase::getGraph()) {

 	  allocate_memory();

 	  for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	    set(it, copy[it]);

 	  }

 	}

       }

       /** Assign operator to copy a map of the same map type.

        */

       Map& operator=(const Map& copy) {

 	if (&copy == this) return *this;

 	if (capacity != 0) {

 	  MapBase::destroy();

 	  allocator.deallocate(values, capacity);

 	}

 	capacity = copy.capacity;

 	if (capacity == 0) return *this;

 	values = allocator.allocate(capacity);

 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	  int id = MapBase::getGraph()->id(it);

 	  allocator.construct(&(values[id]), copy.values[id]);

 	}

 	return *this;

       }

       /** Assign operator to copy a map an other map type.

        */

       template <typename CMap> Map& operator=(const CMap& copy) {

 	if (MapBase::getGraph()) {

 	  MapBase::destroy();

 	} 

 	MapBase::operator=(copy);

 	if (MapBase::getGraph()) {

 	  allocate_memory();

 	  for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	    set(it, copy[it]);

 	  }

 	}

 	return *this;

       }

       /** The destructor of the map.

        */

       virtual ~Map() {

 	if (capacity != 0) {

 	  MapBase::destroy();

 	  allocator.deallocate(values, capacity);

 	}

       }

       /**

        * The subscript operator. The map can be subscripted by the

        * actual keys of the graph. 

        */

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

 	int id = MapBase::getGraph()->id(key);

 	return values[id];

       } 

       /**

        * The const subscript operator. The map can be subscripted by the

        * actual keys of the graph. 

        */

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

 	int id = MapBase::getGraph()->id(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 Value& val) {

 	int id = MapBase::getGraph()->id(key);

 	values[id] = val;

       }

       /** Add a new key to the map. It called by the map registry.

        */

       void add(const KeyType& key) {

 	int id = MapBase::getGraph()->id(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 = MapBase::getGraph()->id(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 = MapBase::getGraph()->id(key);

 	allocator.destroy(&(values[id]));

       }

       /** Clear the data structure.

        */

       void clear() {	

 	if (capacity != 0) {

 	  MapBase::destroy();

 	  allocator.deallocate(values, capacity);

 	  capacity = 0;

 	}

       }

       class iterator;

       class const_iterator;

       /** Compatible iterator with the stl maps' iterators.

        *  It iterates on pairs of a key and a value.

        */

       class iterator {

 	friend class Map;

 	friend class const_iterator;

       private:

 	/** Private constructor to initalize the the iterators returned

 	 *  by the begin() and end().

 	 */

 	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}

       public:

 	/** Default constructor. 

 	 */

 	iterator() {}

 	typedef extended_pair<const KeyType&, const KeyType&, 

 			      Value&, Value&> Reference;

 	/** Dereference operator for map.

 	 */	 

 	Reference operator*() {

 	  return Reference(it, (*map)[it]);

 	}

 	class Pointer {

 	  friend class iterator;

 	private:

 	  Reference data;

 	  Pointer(const KeyType& key, Value& val) : data(key, val) {}

 	public:

 	  Reference* operator->() {return &data;}

 	};

 	/** Arrow operator for map.

 	 */	 

 	Pointer operator->() {

 	  return Pointer(it, ((*map)[it])); 

 	}

 	/** The pre increment operator of the map.

 	 */

 	iterator& operator++() { 

 	  ++it; 

 	  return *this; 

 	}

 	/** The post increment operator of the map.

 	 */

 	iterator operator++(int) { 

 	  iterator tmp(it); 

 	  ++it; 

 	  return tmp; 

 	}

 	/** The equality operator of the map.

 	 */

 	bool operator==(const_iterator p_it) {

 	  return p_it.it == it;

 	}

 	/** The not-equality operator of the map.

 	 */

 	bool operator!=(const_iterator p_it) {

 	  return !(*this == p_it);

 	}

       private:

 	Map* map;

 	KeyIt it;

       };

       /** 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);

       }

       class const_iterator {

 	friend class Map;

 	friend class iterator;

       private:

 	/** Private constructor to initalize the the iterators returned

 	 *  by the begin() and end().

 	 */

 	const_iterator (const Map& pmap, const KeyIt& pit) 

 	  : map(&pmap), it(pit) {}

       public:

 	/** Default constructor. 

 	 */

 	const_iterator() {}

 	/** Constructor to convert iterator to const_iterator.

 	 */

 	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}

 	typedef extended_pair<const KeyType&, const KeyType&, 

 	  const Value&, const Value&> Reference;

 	/** Dereference operator for map.

 	 */	 

 	Reference operator*() {

 	  return Reference(it, (*map)[it]);

 	}

 	class Pointer {

 	  friend class const_iterator;

 	private:

 	  Reference data;

 	  Pointer(const KeyType& key, const Value& val) : data(key, val) {}

 	public:

 	  Reference* operator->() {return &data;}

 	};

 	/** Arrow operator for map.

 	 */	 

 	Pointer operator->() {

 	  return Pointer(it, ((*map)[it])); 

 	}

 	/** The pre increment operator of the map.

 	 */

 	const_iterator& operator++() { 

 	  ++it; 

 	  return *this; 

 	}

 	/** The post increment operator of the map.

 	 */

 	const_iterator operator++(int) { 

 	  const_iterator tmp(it); 

 	  ++it; 

 	  return tmp; 

 	}

 	/** The equality operator of the map.

 	 */

 	bool operator==(const_iterator p_it) {

 	  return p_it.it == it;

 	}

 	/** The not-equality operator of the map.

 	 */

 	bool operator!=(const_iterator p_it) {

 	  return !(*this == p_it);

 	}

       private:

 	const Map* map;

 	KeyIt it;

       };

       /** Returns the begin const_iterator of the map.

        */

       const_iterator begin() const {

 	return const_iterator(*this, KeyIt(*MapBase::getGraph()));

       }

       /** Returns the end const_iterator of the map.

        */

       const_iterator end() const {

 	return const_iterator(*this, INVALID);

       }

     private:

       void allocate_memory() {

 	int max_id = -1;

 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {

 	  int id = MapBase::getGraph()->id(it);

 	  if (id > max_id) {

 	    max_id = id;

 	  }			

 	}

 	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;

     };		

   };

 /// @}

 }

 #endif