// -*- c++ -*-

#ifndef VECTOR_MAP_H

#define VECTOR_MAP_H

#include <vector>

#include <hugo/extended_pair.h>

///\ingroup graphmapfactory

///\file

///\brief Vector based graph maps.

namespace hugo {

  /// \addtogroup graphmapfactory

  /// @{

  /** The VectorMapFactory template class is a factory class

   *  to create maps for the edge and nodes. This map factory

   *  uses the std::vector to implement the container function.

   *

   *  The template parameter is the MapRegistry that the maps

   *  will belong to.

   * 

   * \todo It should use a faster initialization using the maxNodeId() or

   * maxEdgeId() function of the graph istead of iterating through each

   * edge/node.

   */

  template <typename MapRegistry>

  class VectorMapFactory {

  public:

    /// The graph type of the maps. 

    typedef typename MapRegistry::Graph Graph;

    /// The key type of the maps.

    typedef typename MapRegistry::KeyType KeyType;

    /// The iterator to iterate on the keys.

    typedef typename MapRegistry::KeyIt KeyIt;

    /// The MapBase of the Map which imlements the core regisitry function.

    typedef typename MapRegistry::MapBase MapBase;

    /** The template Map type.

     */

    template <typename V> 

    class Map : public MapBase {

      typedef std::vector<V> Container;	

    public:

      /// The value type of the map.

      typedef V ValueType;

      /// The value type of the map.

      typedef V Value;

      /// The reference type of the map;

      typedef typename Container::reference Reference;

      /// The pointer type of the map;

      typedef typename Container::pointer Pointer;

      /// The const value type of the map.

      typedef const Value ConstValue;

      /// The const reference type of the map;

      typedef typename Container::const_reference ConstReference;

      /// The pointer type of the map;

      typedef typename Container::const_pointer ConstPointer;

      /** Default constructor for the map.

       */

      Map() {}

      /** Graph and Registry initialized map constructor.

       */

      Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {

	init();

      }

      /** Constructor to use default value to initialize the map. 

       */

      Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {

	for (KeyIt it(*getGraph()); it != INVALID; ++it) {

          int id = getGraph()->id(it);

	  if (id >= (int)container.size()) {

	    container.resize(id + 1);

	  }

	  set(it, v);

        }

      }

      /** Constructor to copy a map of an other map type.

       */

      template <typename CMap> Map(const CMap& copy) : MapBase(copy) {

	if (getGraph()) {

	  for (KeyIt it(*getGraph()); it != INVALID; ++it) {

	    int id = getGraph()->id(it);

	    if (id >= (int)container.size()) {

	      container.resize(id + 1);

	    }

	    set(it, copy[it]);

	  }

	}

      }

      /** Assign operator to copy a map an other map type.

       */

      template <typename CMap> Map& operator=(const CMap& copy) {

	if (getGraph()) {

	  destroy();

	} 

	this->MapBase::operator=(copy);

	if (getGraph()) {

	  for (KeyIt it(*getGraph()); it != INVALID; ++it) {

	    int id = getGraph()->id(it);

	    if (id >= (int)container.size()) {

	      container.resize(id + 1);

	    }

	    set(it, copy[it]);

	  }

	}

	return *this;

      }

      /** The destructor of the map.

       */

      virtual ~Map() {

      }

      /**

       * The subscript operator. The map can be subscripted by the

       * actual keys of the graph. 

       */

      Reference operator[](const KeyType& key) {

	int id = getGraph()->id(key);

	return container[id];

      } 

      /**

       * The const subscript operator. The map can be subscripted by the

       * actual keys of the graph. 

       */

      ConstReference operator[](const KeyType& key) const {

	int id = getGraph()->id(key);

	return container[id];

      }

      /** Setter function of the map. Equivalent with map[key] = val.

       *  This is a compatibility feature with the not dereferable maps.

       */

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

	int id = getGraph()->id(key);

	container[id] = val;

      }

      /** Add a new key to the map. It called by the map registry.

       */

      void add(const KeyType& key) {

	int id = getGraph()->id(key);

	if (id >= (int)container.size()) {

	  container.resize(id + 1);

	}

      }

      /** Erase a key from the map. It called by the map registry.

       */

      void erase(const KeyType& key) {}

      /** Clear the data structure.

       */

      void clear() { 

	container.clear();

      }

      /** Compatible iterator with the stl maps' iterators.

       *  It iterates on pairs of a key and a value.

       */

      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 KeyType&, const KeyType&, 

			      Map::Reference, Map::Reference> Reference;

	/** Dereference operator for map.

	 */	 

	Reference operator*() {

	  return Reference(it, (*map)[it]);

	}

	class Pointer {

	  friend class iterator;

	private:

	  Reference data;

	  Pointer(const KeyType& key, Map::Reference 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++() { 

	  ++it; 

	  return *this; 

	}

	/** The post increment operator of the map.

	 */

	iterator operator++(int) { 

	  iterator tmp(it); 

	  ++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 KeyType&, const KeyType&, 

	  Map::ConstReference, Map::ConstReference> Reference;

	/** Dereference operator for map.

	 */	 

	Reference operator*() {

	  return Reference(it, (*map)[it]);

	}

	class Pointer {

	  friend class const_iterator;

	private:

	  Reference data;

	  Pointer(const KeyType& key, Map::ConstReference 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++() { 

	  ++it; 

	  return *this; 

	}

	/** The post increment operator of the map.

	 */

	const_iterator operator++(int) { 

	  const_iterator tmp(it); 

	  ++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:

      Container container;

    };

  };

  /// @}

}

#endif