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