#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