deba@703: // -*- c++ -*-
deba@571: #ifndef VECTOR_MAP_H
deba@571: #define VECTOR_MAP_H
deba@571: 
deba@571: #include <vector>
deba@571: 
deba@702: #include "extended_pair.h"
deba@702: 
alpar@921: namespace lemon {
deba@700: 
deba@700:   /** The VectorMapFactory template class is a factory class
deba@700:    *  to create maps for the edge and nodes. This map factory
deba@700:    *  use the std::vector to implement the container function.
deba@700:    *
deba@700:    *  The template parameter is the MapRegistry that the maps
deba@700:    *  will belong to.
deba@700:    */
deba@571: 	
deba@627:   template <typename MapRegistry>
deba@700:   class VectorMapFactory {
deba@700:   public:
deba@627: 		
deba@700:     /// The graph type of the maps. 
deba@627:     typedef typename MapRegistry::Graph Graph;
deba@700:     /// The key type of the maps.
deba@627:     typedef typename MapRegistry::Key Key;
deba@700:     /// The iterator to iterate on the keys.
deba@627:     typedef typename MapRegistry::KeyIt KeyIt;
deba@627: 
deba@700:     /// The MapBase of the Map which imlements the core regisitry function.
deba@627:     typedef typename MapRegistry::MapBase MapBase;
deba@698: 
deba@627: 		
deba@700:     /** The template Map type.
deba@700:      */
deba@627:     template <typename V> 
deba@700:     class Map : public MapBase {
deba@700:     public:
deba@700: 
deba@700:       /// The value type of the map.
deba@627:       typedef V Value;
deba@700: 
deba@700:       typedef std::vector<Value> Container;	
deba@700: 
deba@700:       /** Default constructor for the map.
deba@700:        */
deba@627:       Map() {}
deba@700: 		
deba@700:       /** Graph and Registry initialized map constructor.
deba@700:        */
deba@700:       Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
deba@627: 	init();
deba@627:       }
deba@700: 
deba@700:       /** Constructor to use default value to initialize the map. 
deba@700:        */
deba@700:       Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
deba@700: 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
deba@703:           int id = getGraph->id(it);
deba@703: 	  if (id >= container.size) {
deba@703: 	    container.resize(id + 1);
deba@703: 	  }
deba@703: 	  set(it, v);
deba@700:         }
deba@700:       }
deba@700: 
deba@700:       /** Constructor to copy a map of an other map type.
deba@700:        */
deba@700:       template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
deba@700: 	if (getGraph()) {
deba@700: 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
deba@703: 	    int id = getGraph->id(it);
deba@703: 	    if (id >= container.size) {
deba@703: 	      container.resize(id + 1);
deba@703: 	    }
deba@700: 	    set(it, copy[it]);
deba@700: 	  }
deba@700: 	}
deba@700:       }
deba@700: 
deba@700:       /** Assign operator to copy a map an other map type.
deba@700:        */
deba@700:       template <typename CMap> Map& operator=(const CMap& copy) {
deba@700: 	if (getGraph()) {
deba@700: 	  destroy();
deba@700: 	} 
deba@700: 	this->MapBase::operator=(copy);
deba@700: 	if (getGraph()) {
deba@700: 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
deba@703: 	    int id = getGraph->id(it);
deba@703: 	    if (id >= container.size) {
deba@703: 	      container.resize(id + 1);
deba@703: 	    }
deba@700: 	    set(it, copy[it]);
deba@700: 	  }
deba@700: 	}
deba@700:       }
deba@700: 
deba@700:       /** The destructor of the map.
deba@700:        */
deba@627:       virtual ~Map() {
deba@627:       }
deba@700: 		
deba@700:       /**
deba@700:        * The subscript operator. The map can be subscripted by the
deba@700:        * actual keys of the graph. 
deba@700:        */
deba@698:       typename Container::reference operator[](const Key& key) {
deba@700: 	int id = getGraph()->id(key);
deba@627: 	return container[id];
deba@627:       } 
deba@571: 		
deba@700:       /**
deba@700:        * The const subscript operator. The map can be subscripted by the
deba@700:        * actual keys of the graph. 
deba@700:        */
deba@698:       typename Container::const_reference operator[](const Key& key) const {
deba@700: 	int id = getGraph()->id(key);
deba@627: 	return container[id];
deba@627:       }
deba@700: 
deba@700:       /** Setter function of the map. Equivalent with map[key] = val.
deba@700:        *  This is a compatibility feature with the not dereferable maps.
deba@700:        */
deba@627:       void set(const Key& key, const Value& val) {
deba@700: 	int id = getGraph()->id(key);
deba@627: 	container[id] = val;
deba@627:       }
deba@627: 		
deba@700:       /** Add a new key to the map. It called by the map registry.
deba@700:        */
deba@627:       void add(const Key& key) {
deba@700: 	int id = getGraph()->id(key);
deba@627: 	if (id >= container.size()) {
deba@627: 	  container.resize(id + 1);
deba@627: 	}
deba@627:       }
deba@627: 		
deba@700:       /** Erease a key from the map. It called by the map registry.
deba@700:        */
deba@627:       void erase(const Key& key) {}
deba@698: 
deba@700:       /** Compatible iterator with the stl maps' iterators.
deba@700:        *  It iterates on pairs of a key and a value.
deba@700:        */
deba@700:       class iterator {
deba@700: 	friend class Map;
deba@700: 	friend class const_iterator;
deba@698:       private:
deba@698: 
deba@700: 	/** Private constructor to initalize the the iterators returned
deba@700: 	 *  by the begin() and end().
deba@700: 	 */
deba@700: 	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
deba@700: 
deba@698:       public:
deba@700: 
deba@700: 	/** Default constructor. 
deba@700: 	 */
deba@698: 	iterator() {}
deba@700: 
deba@703: 	typedef extended_pair<const Key&, const Key&, 
deba@703: 			      Value&, Value&> Reference;
deba@703: 
deba@700: 	/** Dereference operator for map.
deba@700: 	 */	 
deba@703: 	Reference operator*() {
deba@703: 	  return Reference(it, (*map)[it]);
deba@698: 	}
deba@698: 
deba@702: 	class Pointer {
deba@702: 	  friend class iterator;
deba@702: 	private:
deba@703: 	  Reference data;
deba@702: 	  Pointer(const Key& key, Value& val) : data(key, val) {}
deba@702: 	public:
deba@703: 	  Reference* operator->() {return &data;}
deba@702: 	};
deba@702: 
deba@700: 	/** Arrow operator for map.
deba@700: 	 */	 
deba@702: 	Pointer operator->() {
deba@702: 	  return Pointer(it, ((*map)[it])); 
deba@700: 	}
deba@700: 
deba@700: 	/** The pre increment operator of the map.
deba@700: 	 */
deba@700: 	iterator& operator++() { 
deba@700: 	  map->getGraph()->next(it); 
deba@700: 	  return *this; 
deba@700: 	}
deba@700: 
deba@700: 	/** The post increment operator of the map.
deba@700: 	 */
deba@700: 	iterator operator++(int) { 
deba@700: 	  iterator tmp(it); 
deba@700: 	  map.getGraph()->next(it); 
deba@700: 	  return tmp; 
deba@700: 	}
deba@700: 
deba@700: 	/** The equality operator of the map.
deba@700: 	 */
deba@700: 	bool operator==(const_iterator p_it) {
deba@700: 	  return p_it.it == it;
deba@700: 	}
deba@700: 	
deba@700: 	/** The not-equality operator of the map.
deba@700: 	 */
deba@700: 	bool operator!=(const_iterator p_it) {
deba@700: 	  return !(*this == p_it);
deba@700: 	}
deba@702: 
deba@700: 	
deba@698:       private:
deba@700: 	Map* map;
deba@698: 	KeyIt it;
deba@698:       };
deba@698: 
deba@700:       /** Returns the begin iterator of the map.
deba@700:        */
deba@700:       iterator begin() {
deba@700: 	return iterator(*this, KeyIt(*getGraph()));
deba@700:       }
deba@700: 
deba@700:       /** Returns the end iterator of the map.
deba@700:        */
deba@700:       iterator end() {
deba@700: 	return iterator(*this, INVALID);
deba@700:       }
deba@700: 
deba@700:       class const_iterator {
deba@700: 	friend class Map;
deba@700: 	friend class iterator;
deba@627:       private:
deba@700: 
deba@700: 	/** Private constructor to initalize the the iterators returned
deba@700: 	 *  by the begin() and end().
deba@700: 	 */
deba@703: 	const_iterator (const Map& pmap, const KeyIt& pit) 
deba@703: 	  : map(&pmap), it(pit) {}
deba@700: 
deba@700:       public:
deba@700: 
deba@700: 	/** Default constructor. 
deba@700: 	 */
deba@700: 	const_iterator() {}
deba@700: 
deba@700: 	/** Constructor to convert iterator to const_iterator.
deba@700: 	 */
deba@703: 	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
deba@700:       
deba@703: 	typedef extended_pair<const Key&, const Key&, 
deba@703: 	  const Value&, const Value&> Reference;
deba@703: 
deba@700: 	/** Dereference operator for map.
deba@700: 	 */	 
deba@703: 	Reference operator*() {
deba@703: 	  return Reference(it, (*map)[it]);
deba@700: 	}
deba@700: 
deba@703: 
deba@702: 	class Pointer {
deba@702: 	  friend class const_iterator;
deba@702: 	private:
deba@703: 	  Reference data;
deba@702: 	  Pointer(const Key& key, const Value& val) : data(key, val) {}
deba@702: 	public:
deba@703: 	  Reference* operator->() {return &data;}
deba@702: 	};
deba@703: 
deba@700: 	/** Arrow operator for map.
deba@700: 	 */	 
deba@703: 	Pointer operator->() {
deba@703: 	  return Pointer(it, ((*map)[it])); 
deba@700: 	}
deba@700: 
deba@700: 	/** The pre increment operator of the map.
deba@700: 	 */
deba@700: 	const_iterator& operator++() { 
deba@700: 	  map->getGraph()->next(it); 
deba@700: 	  return *this; 
deba@700: 	}
deba@700: 
deba@700: 	/** The post increment operator of the map.
deba@700: 	 */
deba@700: 	const_iterator operator++(int) { 
deba@700: 	  const_iterator tmp(it); 
deba@700: 	  map->getGraph()->next(it); 
deba@700: 	  return tmp; 
deba@700: 	}
deba@700: 
deba@700: 	/** The equality operator of the map.
deba@700: 	 */
deba@700: 	bool operator==(const_iterator p_it) {
deba@700: 	  return p_it.it == it;
deba@700: 	}
deba@700: 	
deba@700: 	/** The not-equality operator of the map.
deba@700: 	 */
deba@700: 	bool operator!=(const_iterator p_it) {
deba@700: 	  return !(*this == p_it);
deba@700: 	}
deba@700: 	
deba@702: 
deba@700:       private:
deba@700: 	const Map* map;
deba@700: 	KeyIt it;
deba@700:       };
deba@700: 
deba@700:       /** Returns the begin const_iterator of the map.
deba@700:        */
deba@700:       const_iterator begin() const {
deba@700: 	return const_iterator(*this, KeyIt(*getGraph()));
deba@700:       }
deba@700: 
deba@700:       /** Returns the end const_iterator of the map.
deba@700:        */
deba@700:       const_iterator end() const {
deba@700: 	return const_iterator(*this, INVALID);
deba@700:       }
deba@700: 
deba@700:       private:
deba@571: 		
deba@627:       Container container;
deba@698: 
deba@627:     };
deba@571: 		
deba@627:   };
deba@700: 
deba@571: }
deba@571: 
deba@571: #endif