#ifndef ARRAY_MAP_H

 #define ARRAY_MAP_H

 #include <memory>

 #include "map_base.h"

 #include <iostream>

 using namespace std;

 namespace hugo {

 	template <typename G, typename K, typename KIt>

 	class ArrayMapFactory {

 	public:

 		typedef G Graph;

 		typedef K Key;

 		typedef KIt KeyIt;

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

 		class Map : public MapBase<G, K, KIt> {

 		public:

 			typedef V Value;

 			typedef typename _Alloc_traits<V, A>::_Alloc_type _Alloc_type;

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

 			Map(Graph& g, MapRegistry<G, K, KIt>& r) 

 				: MapBase<G, K, KIt>(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;

 				}

 				int capacity = 1;

 				while (capacity <= max_id) {

 					capacity <<= 1;

 				}

 				Value* values = reinterpret_cast<Value*>(new char[capacity*sizeof(Value)]);

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

 					int id = graph->id(it);

 					new(&(values[id])) Value();

 				}								

 				cerr << capacity << endl;	

 			}

 			virtual ~Map() {

 				destroy();

 				delete[] reinterpret_cast<char*>(values);

 				values = 0;

 				capacity = 0;

 			}

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

 				int id = graph->id(key);

 				return values[id];

 			} 

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

 				int id = graph->id(key);

 				return values[id];

 			}

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

 				int id = graph->id(key);

 				return values[id];

 			} 

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

 				int id = graph->id(key);

 				values[id] = val;

 			}

 			void add(const K& key) {

 				cerr << capacity << endl;

 				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 = reinterpret_cast<Value*>(new char[new_capacity*sizeof(Value)]);;

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

 						int jd = graph->id(it);

 						if (id != jd) {

 							new(&(new_values[jd])) Value(values[jd]);

 						}

 					}

 					if (capacity != 0) delete[] reinterpret_cast<char *>(values);

 					values = new_values;

 					capacity = new_capacity;

 				}

 				cerr << id << ' ' << capacity << endl;

 				new(&(values[id])) Value();

 			}

 			void erase(const K& key) {

 				int id = graph->id(key);

 				values[id].~Value();

 			}

 		private:

 			int capacity;

 			Value* values;

 		};

 	};

 }

 #endif