#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