#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