#ifndef ARRAY_MAP_H

#define ARRAY_MAP_H

#include <memory>

#include <iostream>

using namespace std;

namespace hugo {

  template <typename MapRegistry> class ArrayMapFactory {

  public:

    typedef typename MapRegistry::Graph Graph;

    typedef typename MapRegistry::Key Key;

    typedef typename MapRegistry::KeyIt KeyIt;

    typedef typename MapRegistry::MapBase MapBase;

    template <typename V, typename A = std::allocator<V> > class Map : public MapBase {

      public:

      typedef V Value;

      typedef A Allocator;

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

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

	int max_id = -1;

	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

	  int id = 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);

	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

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

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

	}								

      }

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

	int max_id = -1;

	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

	  int id = 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);

	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

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

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

	}								

      }

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

	capacity = copy.capacity;

	if (capacity == 0) return;

	values = allocator.allocate(capacity);

	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

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

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

	}

      }

      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {

	if (getGraph()) {

	  init();

	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

	    set(it, copy[it]);

	  }

	}

      }

      Map& operator=(const Map& copy) {

	if (&copy == this) return;

	if (capacity != 0) {

	  destroy();

	  allocator.deallocate(values, capacity);

	}

	capacity = copy.capacity;

	if (capacity == 0) return;

	values = allocator.allocate(capacity);

	for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

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

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

	}

      }

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

	if (getGraph()) {

	  destroy();

	} 

	this->MapBase::operator=(copy);

	if (getGraph()) {

	  init();

	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

	    set(it, copy[it]);

	  }

	}

      }

      virtual ~Map() {

	if (capacity != 0) {

	  destroy();

	  allocator.deallocate(values, capacity);

	}

      }

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

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

	return values[id];

      } 

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

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

	return values[id];

      }

      const Value& get(const Key& key) const {

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

	return values[id];

      } 

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

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

	values[id] = val;

      }

      void add(const Key& key) {

	int id = 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(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {

	    int jd = 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());

      }

      void erase(const Key& key) {

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

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

      }

      /** 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() {}

	/** Dereference operator for map.

	 */	 

	std::pair<const Key, Value> operator*() {

	  return std::pair<const Key, Value>(it, (*map)[it]);

	}

	/** Arrow operator for map.

	 */	 

	std::pair<const Key, Value>* operator->() {

	  static std::pair<const Key, Value> tmp = operator*();

	  return &tmp;

	}

	/** The pre increment operator of the map.

	 */

	iterator& operator++() { 

	  map->getGraph()->next(it); 

	  return *this; 

	}

	/** The post increment operator of the map.

	 */

	iterator operator++(int) { 

	  iterator tmp(it); 

	  map.getGraph()->next(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(*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 (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) {

	  it = p_it.it;

	}

	/** Dereference operator for map.

	 */	 

	std::pair<const Key, const Value> operator*() const {

	  return std::pair<const Key, const Value>(it, (*map)[it]);

	}

	/** Arrow operator for map.

	 */	 

	std::pair<const Key, const Value>* operator->() const {

	  static std::pair<const Key, const Value> tmp = operator*();

	  return &tmp;

	}

	/** The pre increment operator of the map.

	 */

	const_iterator& operator++() { 

	  map->getGraph()->next(it); 

	  return *this; 

	}

	/** The post increment operator of the map.

	 */

	const_iterator operator++(int) { 

	  const_iterator tmp(it); 

	  map->getGraph()->next(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(*getGraph()));

      }

      /** Returns the end const_iterator of the map.

       */

      const_iterator end() const {

	return const_iterator(*this, INVALID);

      }

      private:

      int capacity;

      Value* values;

      Allocator allocator;

    };		

  };

}

#endif