#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(Graph& g, MapRegistry& r) : MapBase(g, r) {

	  int max_id = -1;

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

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

	    int id = graph->id(it);

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

	  }								

	}

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

	  capacity = copy.capacity;

	  values = allocator.allocate(capacity);

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

	    int id = graph->id(it);

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

	  }

	}

	virtual ~Map() {

	  destroy();

	  allocator.deallocate(values, capacity);

	}

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

	  int id = graph->id(key);

	  return values[id];

	} 

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

	  int id = graph->id(key);

	  return values[id];

	}

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

	  int id = graph->id(key);

	  return values[id];

	} 

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

	  int id = graph->id(key);

	  values[id] = val;

	}

	void add(const Key& key) {

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

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

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

	}

	private:

	int capacity;

	Value* values;

	Allocator allocator;

      };		

  };

}

#endif