#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