deba@782: // -*- c++ -*-
deba@782: #ifndef ARRAY_MAP_FACTORY_H
deba@782: #define ARRAY_MAP_FACTORY_H
deba@782: 
deba@782: #include <memory>
deba@782: 
deba@782: #include <hugo/extended_pair.h>
deba@782: 
deba@782: namespace hugo {
deba@782: 	
deba@782:   template <typename MapRegistry> class ArrayMapFactory {
deba@782: 		
deba@782:   public:
deba@782: 		
deba@782:     typedef typename MapRegistry::Graph Graph;
deba@782:     typedef typename MapRegistry::Key Key;
deba@782:     typedef typename MapRegistry::KeyIt KeyIt;
deba@782: 
deba@782:     typedef typename MapRegistry::MapBase MapBase;
deba@782: 		
deba@782:     template <typename V, typename A = std::allocator<V> > 
deba@782:     class Map : public MapBase {
deba@782:     
deba@782:       public:
deba@782: 
deba@782:       typedef V Value;
deba@782:       typedef A Allocator;
deba@782: 
deba@782: 	
deba@782:       Map() : values(0), capacity(0) {}
deba@782: 			
deba@782:       Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
deba@782: 	allocate_memory();
deba@782: 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	  int id = MapBase::getGraph()->id(it);
deba@782: 	  allocator.construct(&(values[id]), Value());
deba@782: 	}								
deba@782:       }
deba@782: 
deba@782:       Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
deba@782: 	allocate_memory();
deba@782: 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	  int id = MapBase::getGraph()->id(it);
deba@782: 	  allocator.construct(&(values[id]), v);
deba@782: 	}								
deba@782:       }
deba@782: 
deba@782:       Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
deba@782: 	capacity = copy.capacity;
deba@782: 	if (capacity == 0) return;
deba@782: 	values = allocator.allocate(capacity);
deba@782: 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	  int id = MapBase::getGraph()->id(it);
deba@782: 	  allocator.construct(&(values[id]), copy.values[id]);
deba@782: 	}
deba@782:       }
deba@782: 
deba@782:       template <typename CMap> Map(const CMap& copy) 
deba@782: 	: capacity(0), values(0), MapBase(copy) {
deba@782: 	if (MapBase::getGraph()) {
deba@782: 	  allocate_memory();
deba@782: 	  for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	    set(it, copy[it]);
deba@782: 	  }
deba@782: 	}
deba@782:       }
deba@782: 
deba@782:       Map& operator=(const Map& copy) {
deba@782: 	if (&copy == this) return *this;
deba@782: 	if (capacity != 0) {
deba@782: 	  MapBase::destroy();
deba@782: 	  allocator.deallocate(values, capacity);
deba@782: 	}
deba@782: 	capacity = copy.capacity;
deba@782: 	if (capacity == 0) return *this;
deba@782: 	values = allocator.allocate(capacity);
deba@782: 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	  int id = MapBase::getGraph()->id(it);
deba@782: 	  allocator.construct(&(values[id]), copy.values[id]);
deba@782: 	}
deba@782: 	return *this;
deba@782:       }
deba@782: 
deba@782:       template <typename CMap> Map& operator=(const CMap& copy) {
deba@782: 	if (MapBase::getGraph()) {
deba@782: 	  MapBase::destroy();
deba@782: 	} 
deba@782: 	MapBase::operator=(copy);
deba@782: 	if (MapBase::getGraph()) {
deba@782: 	  allocate_memory();
deba@782: 	  for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	    set(it, copy[it]);
deba@782: 	  }
deba@782: 	}
deba@782: 	return *this;
deba@782:       }
deba@782: 				
deba@782:       virtual ~Map() {
deba@782: 	if (capacity != 0) {
deba@782: 	  MapBase::destroy();
deba@782: 	  allocator.deallocate(values, capacity);
deba@782: 	}
deba@782:       }
deba@782: 	
deba@782: 	
deba@782:       Value& operator[](const Key& key) {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	return values[id];
deba@782:       } 
deba@782: 		
deba@782:       const Value& operator[](const Key& key) const {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	return values[id];
deba@782:       }
deba@782: 	
deba@782:       const Value& get(const Key& key) const {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	return values[id];
deba@782:       } 
deba@782: 		
deba@782:       void set(const Key& key, const Value& val) {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	values[id] = val;
deba@782:       }
deba@782: 		
deba@782:       void add(const Key& key) {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	if (id >= capacity) {
deba@782: 	  int new_capacity = (capacity == 0 ? 1 : capacity);
deba@782: 	  while (new_capacity <= id) {
deba@782: 	    new_capacity <<= 1;
deba@782: 	  }
deba@782: 	  Value* new_values = allocator.allocate(new_capacity);;
deba@782: 	  for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	    int jd = MapBase::getGraph()->id(it);
deba@782: 	    if (id != jd) {
deba@782: 	      allocator.construct(&(new_values[jd]), values[jd]);
deba@782: 	      allocator.destroy(&(values[jd]));
deba@782: 	    }
deba@782: 	  }
deba@782: 	  if (capacity != 0) allocator.deallocate(values, capacity);
deba@782: 	  values = new_values;
deba@782: 	  capacity = new_capacity;
deba@782: 	}
deba@782: 	allocator.construct(&(values[id]), Value());
deba@782:       }
deba@782: 		
deba@782:       void erase(const Key& key) {
deba@782: 	int id = MapBase::getGraph()->id(key);
deba@782: 	allocator.destroy(&(values[id]));
deba@782:       }
deba@782: 
deba@782:       void clear() {	
deba@782: 	if (capacity != 0) {
deba@782: 	  MapBase::destroy();
deba@782: 	  allocator.deallocate(values, capacity);
deba@782: 	  capacity = 0;
deba@782: 	}
deba@782:       }
deba@782: 	
deba@782:       class iterator {
deba@782: 	friend class Map;
deba@782: 	friend class const_iterator;
deba@782:       private:
deba@782: 
deba@782: 	/** Private constructor to initalize the the iterators returned
deba@782: 	 *  by the begin() and end().
deba@782: 	 */
deba@782: 	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
deba@782: 
deba@782:       public:
deba@782: 
deba@782: 	/** Default constructor. 
deba@782: 	 */
deba@782: 	iterator() {}
deba@782: 
deba@782: 	typedef extended_pair<const Key&, const Key&, 
deba@782: 			      Value&, Value&> Reference;
deba@782: 
deba@782: 	/** Dereference operator for map.
deba@782: 	 */	 
deba@782: 	Reference operator*() {
deba@782: 	  return Reference(it, (*map)[it]);
deba@782: 	}
deba@782: 
deba@782: 	class Pointer {
deba@782: 	  friend class iterator;
deba@782: 	private:
deba@782: 	  Reference data;
deba@782: 	  Pointer(const Key& key, Value& val) : data(key, val) {}
deba@782: 	public:
deba@782: 	  Reference* operator->() {return &data;}
deba@782: 	};
deba@782: 
deba@782: 	/** Arrow operator for map.
deba@782: 	 */	 
deba@782: 	Pointer operator->() {
deba@782: 	  return Pointer(it, ((*map)[it])); 
deba@782: 	}
deba@782: 
deba@782: 	/** The pre increment operator of the map.
deba@782: 	 */
deba@782: 	iterator& operator++() { 
deba@782: 	  ++it; 
deba@782: 	  return *this; 
deba@782: 	}
deba@782: 
deba@782: 	/** The post increment operator of the map.
deba@782: 	 */
deba@782: 	iterator operator++(int) { 
deba@782: 	  iterator tmp(it); 
deba@782: 	  ++it; 
deba@782: 	  return tmp; 
deba@782: 	}
deba@782: 
deba@782: 	/** The equality operator of the map.
deba@782: 	 */
deba@782: 	bool operator==(const_iterator p_it) {
deba@782: 	  return p_it.it == it;
deba@782: 	}
deba@782: 	
deba@782: 	/** The not-equality operator of the map.
deba@782: 	 */
deba@782: 	bool operator!=(const_iterator p_it) {
deba@782: 	  return !(*this == p_it);
deba@782: 	}
deba@782: 
deba@782: 	
deba@782:       private:
deba@782: 	Map* map;
deba@782: 	KeyIt it;
deba@782:       };
deba@782: 
deba@782:       /** Returns the begin iterator of the map.
deba@782:        */
deba@782:       iterator begin() {
deba@782: 	return iterator(*this, KeyIt(*MapBase::getGraph()));
deba@782:       }
deba@782: 
deba@782:       /** Returns the end iterator of the map.
deba@782:        */
deba@782:       iterator end() {
deba@782: 	return iterator(*this, INVALID);
deba@782:       }
deba@782: 
deba@782:       class const_iterator {
deba@782: 	friend class Map;
deba@782: 	friend class iterator;
deba@782:       private:
deba@782: 
deba@782: 	/** Private constructor to initalize the the iterators returned
deba@782: 	 *  by the begin() and end().
deba@782: 	 */
deba@782: 	const_iterator (const Map& pmap, const KeyIt& pit) 
deba@782: 	  : map(&pmap), it(pit) {}
deba@782: 
deba@782:       public:
deba@782: 
deba@782: 	/** Default constructor. 
deba@782: 	 */
deba@782: 	const_iterator() {}
deba@782: 
deba@782: 	/** Constructor to convert iterator to const_iterator.
deba@782: 	 */
deba@782: 	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
deba@782:       
deba@782: 	typedef extended_pair<const Key&, const Key&, 
deba@782: 	  const Value&, const Value&> Reference;
deba@782: 
deba@782: 	/** Dereference operator for map.
deba@782: 	 */	 
deba@782: 	Reference operator*() {
deba@782: 	  return Reference(it, (*map)[it]);
deba@782: 	}
deba@782: 
deba@782: 
deba@782: 	class Pointer {
deba@782: 	  friend class const_iterator;
deba@782: 	private:
deba@782: 	  Reference data;
deba@782: 	  Pointer(const Key& key, const Value& val) : data(key, val) {}
deba@782: 	public:
deba@782: 	  Reference* operator->() {return &data;}
deba@782: 	};
deba@782: 
deba@782: 	/** Arrow operator for map.
deba@782: 	 */	 
deba@782: 	Pointer operator->() {
deba@782: 	  return Pointer(it, ((*map)[it])); 
deba@782: 	}
deba@782: 
deba@782: 	/** The pre increment operator of the map.
deba@782: 	 */
deba@782: 	const_iterator& operator++() { 
deba@782: 	  ++it; 
deba@782: 	  return *this; 
deba@782: 	}
deba@782: 
deba@782: 	/** The post increment operator of the map.
deba@782: 	 */
deba@782: 	const_iterator operator++(int) { 
deba@782: 	  const_iterator tmp(it); 
deba@782: 	  ++it; 
deba@782: 	  return tmp; 
deba@782: 	}
deba@782: 
deba@782: 	/** The equality operator of the map.
deba@782: 	 */
deba@782: 	bool operator==(const_iterator p_it) {
deba@782: 	  return p_it.it == it;
deba@782: 	}
deba@782: 	
deba@782: 	/** The not-equality operator of the map.
deba@782: 	 */
deba@782: 	bool operator!=(const_iterator p_it) {
deba@782: 	  return !(*this == p_it);
deba@782: 	}
deba@782: 	
deba@782: 
deba@782:       private:
deba@782: 	const Map* map;
deba@782: 	KeyIt it;
deba@782:       };
deba@782: 
deba@782:       /** Returns the begin const_iterator of the map.
deba@782:        */
deba@782:       const_iterator begin() const {
deba@782: 	return const_iterator(*this, KeyIt(*MapBase::getGraph()));
deba@782:       }
deba@782: 
deba@782:       /** Returns the end const_iterator of the map.
deba@782:        */
deba@782:       const_iterator end() const {
deba@782: 	return const_iterator(*this, INVALID);
deba@782:       }
deba@782: 
deba@782:     private:
deba@782:       
deba@782:       void allocate_memory() {
deba@782: 	int max_id = -1;
deba@782: 	for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
deba@782: 	  int id = MapBase::getGraph()->id(it);
deba@782: 	  if (id > max_id) {
deba@782: 	    max_id = id;
deba@782: 	  }			
deba@782: 	}
deba@782: 	if (max_id == -1) {
deba@782: 	  capacity = 0;
deba@782: 	  values = 0;
deba@782: 	  return;
deba@782: 	}
deba@782: 	capacity = 1;
deba@782: 	while (capacity <= max_id) {
deba@782: 	  capacity <<= 1;
deba@782: 	}
deba@782: 	values = allocator.allocate(capacity);	
deba@782:       }      
deba@782: 
deba@782:       int capacity;
deba@782:       Value* values;
deba@782:       Allocator allocator;
deba@782:     };		
deba@782:   };
deba@782: }
deba@782: 
deba@782: #endif