// -*- c++ -*-
#ifndef ARRAY_MAP_H
#define ARRAY_MAP_H

#include <memory>

#include "extended_pair.h"

namespace lemon {
	
  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(const Graph& g, MapRegistry& r) : MapBase(g, r) {
	allocate_memory();
	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	  int id = getGraph()->id(it);
	  allocator.construct(&(values[id]), Value());
	}								
      }

      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
	allocate_memory();
	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	  int id = getGraph()->id(it);
	  allocator.construct(&(values[id]), v);
	}								
      }

      Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
	capacity = copy.capacity;
	if (capacity == 0) return;
	values = allocator.allocate(capacity);
	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	  int id = getGraph()->id(it);
	  allocator.construct(&(values[id]), copy.values[id]);
	}
      }

      template <typename CMap> Map(const CMap& copy) 
	: capacity(0), values(0), MapBase(copy) {
	if (getGraph()) {
	  allocate_memory();
	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	    set(it, copy[it]);
	  }
	}
      }

      Map& operator=(const Map& copy) {
	if (&copy == this) return;
	if (capacity != 0) {
	  destroy();
	  allocator.deallocate(values, capacity);
	}
	capacity = copy.capacity;
	if (capacity == 0) return;
	values = allocator.allocate(capacity);
	for (KeyIt it(getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	  int id = getGraph()->id(it);
	  allocator.construct(&(values[id]), copy.values[id]);
	}
      }

      template <typename CMap> Map& operator=(const CMap& copy) {
	if (getGraph()) {
	  destroy();
	} 
	this->MapBase::operator=(copy);
	if (getGraph()) {
	  allocate_memory();
	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	    set(it, copy[it]);
	  }
	}
      }
				
      virtual ~Map() {
	if (capacity != 0) {
	  destroy();
	  allocator.deallocate(values, capacity);
	}
      }
	
	
      Value& operator[](const Key& key) {
	int id = getGraph()->id(key);
	return values[id];
      } 
		
      const Value& operator[](const Key& key) const {
	int id = getGraph()->id(key);
	return values[id];
      }
	
      const Value& get(const Key& key) const {
	int id = getGraph()->id(key);
	return values[id];
      } 
		
      void set(const Key& key, const Value& val) {
	int id = getGraph()->id(key);
	values[id] = val;
      }
		
      void add(const Key& key) {
	int id = getGraph()->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(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	    int jd = getGraph()->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 = getGraph()->id(key);
	allocator.destroy(&(values[id]));
      }
	
      class iterator {
	friend class Map;
	friend class const_iterator;
      private:

	/** Private constructor to initalize the the iterators returned
	 *  by the begin() and end().
	 */
	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}

      public:

	/** Default constructor. 
	 */
	iterator() {}

	typedef extended_pair<const Key&, const Key&, 
			      Value&, Value&> Reference;

	/** Dereference operator for map.
	 */	 
	Reference operator*() {
	  return Reference(it, (*map)[it]);
	}

	class Pointer {
	  friend class iterator;
	private:
	  Reference data;
	  Pointer(const Key& key, Value& val) : data(key, val) {}
	public:
	  Reference* operator->() {return &data;}
	};

	/** Arrow operator for map.
	 */	 
	Pointer operator->() {
	  return Pointer(it, ((*map)[it])); 
	}

	/** The pre increment operator of the map.
	 */
	iterator& operator++() { 
	  map->getGraph()->next(it); 
	  return *this; 
	}

	/** The post increment operator of the map.
	 */
	iterator operator++(int) { 
	  iterator tmp(it); 
	  map.getGraph()->next(it); 
	  return tmp; 
	}

	/** The equality operator of the map.
	 */
	bool operator==(const_iterator p_it) {
	  return p_it.it == it;
	}
	
	/** The not-equality operator of the map.
	 */
	bool operator!=(const_iterator p_it) {
	  return !(*this == p_it);
	}

	
      private:
	Map* map;
	KeyIt it;
      };

      /** Returns the begin iterator of the map.
       */
      iterator begin() {
	return iterator(*this, KeyIt(*getGraph()));
      }

      /** Returns the end iterator of the map.
       */
      iterator end() {
	return iterator(*this, INVALID);
      }

      class const_iterator {
	friend class Map;
	friend class iterator;
      private:

	/** Private constructor to initalize the the iterators returned
	 *  by the begin() and end().
	 */
	const_iterator (const Map& pmap, const KeyIt& pit) 
	  : map(&pmap), it(pit) {}

      public:

	/** Default constructor. 
	 */
	const_iterator() {}

	/** Constructor to convert iterator to const_iterator.
	 */
	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
      
	typedef extended_pair<const Key&, const Key&, 
	  const Value&, const Value&> Reference;

	/** Dereference operator for map.
	 */	 
	Reference operator*() {
	  return Reference(it, (*map)[it]);
	}


	class Pointer {
	  friend class const_iterator;
	private:
	  Reference data;
	  Pointer(const Key& key, const Value& val) : data(key, val) {}
	public:
	  Reference* operator->() {return &data;}
	};

	/** Arrow operator for map.
	 */	 
	Pointer operator->() {
	  return Pointer(it, ((*map)[it])); 
	}

	/** The pre increment operator of the map.
	 */
	const_iterator& operator++() { 
	  map->getGraph()->next(it); 
	  return *this; 
	}

	/** The post increment operator of the map.
	 */
	const_iterator operator++(int) { 
	  const_iterator tmp(it); 
	  map->getGraph()->next(it); 
	  return tmp; 
	}

	/** The equality operator of the map.
	 */
	bool operator==(const_iterator p_it) {
	  return p_it.it == it;
	}
	
	/** The not-equality operator of the map.
	 */
	bool operator!=(const_iterator p_it) {
	  return !(*this == p_it);
	}
	

      private:
	const Map* map;
	KeyIt it;
      };

      /** Returns the begin const_iterator of the map.
       */
      const_iterator begin() const {
	return const_iterator(*this, KeyIt(*getGraph()));
      }

      /** Returns the end const_iterator of the map.
       */
      const_iterator end() const {
	return const_iterator(*this, INVALID);
      }

    private:
      
      void allocate_memory() {
	int max_id = -1;
	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
	  int id = getGraph()->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);	
      }      
      int capacity;
      Value* values;
      Allocator allocator;
    };		
  };
}

#endif