1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/array_map_factory.h Thu Sep 02 10:07:30 2004 +0000
1.3 @@ -0,0 +1,366 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef ARRAY_MAP_FACTORY_H
1.6 +#define ARRAY_MAP_FACTORY_H
1.7 +
1.8 +#include <memory>
1.9 +
1.10 +#include <hugo/extended_pair.h>
1.11 +
1.12 +namespace hugo {
1.13 +
1.14 + template <typename MapRegistry> class ArrayMapFactory {
1.15 +
1.16 + public:
1.17 +
1.18 + typedef typename MapRegistry::Graph Graph;
1.19 + typedef typename MapRegistry::Key Key;
1.20 + typedef typename MapRegistry::KeyIt KeyIt;
1.21 +
1.22 + typedef typename MapRegistry::MapBase MapBase;
1.23 +
1.24 + template <typename V, typename A = std::allocator<V> >
1.25 + class Map : public MapBase {
1.26 +
1.27 + public:
1.28 +
1.29 + typedef V Value;
1.30 + typedef A Allocator;
1.31 +
1.32 +
1.33 + Map() : values(0), capacity(0) {}
1.34 +
1.35 + Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.36 + allocate_memory();
1.37 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.38 + int id = MapBase::getGraph()->id(it);
1.39 + allocator.construct(&(values[id]), Value());
1.40 + }
1.41 + }
1.42 +
1.43 + Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
1.44 + allocate_memory();
1.45 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.46 + int id = MapBase::getGraph()->id(it);
1.47 + allocator.construct(&(values[id]), v);
1.48 + }
1.49 + }
1.50 +
1.51 + Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) {
1.52 + capacity = copy.capacity;
1.53 + if (capacity == 0) return;
1.54 + values = allocator.allocate(capacity);
1.55 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.56 + int id = MapBase::getGraph()->id(it);
1.57 + allocator.construct(&(values[id]), copy.values[id]);
1.58 + }
1.59 + }
1.60 +
1.61 + template <typename CMap> Map(const CMap& copy)
1.62 + : capacity(0), values(0), MapBase(copy) {
1.63 + if (MapBase::getGraph()) {
1.64 + allocate_memory();
1.65 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.66 + set(it, copy[it]);
1.67 + }
1.68 + }
1.69 + }
1.70 +
1.71 + Map& operator=(const Map& copy) {
1.72 + if (© == this) return *this;
1.73 + if (capacity != 0) {
1.74 + MapBase::destroy();
1.75 + allocator.deallocate(values, capacity);
1.76 + }
1.77 + capacity = copy.capacity;
1.78 + if (capacity == 0) return *this;
1.79 + values = allocator.allocate(capacity);
1.80 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.81 + int id = MapBase::getGraph()->id(it);
1.82 + allocator.construct(&(values[id]), copy.values[id]);
1.83 + }
1.84 + return *this;
1.85 + }
1.86 +
1.87 + template <typename CMap> Map& operator=(const CMap& copy) {
1.88 + if (MapBase::getGraph()) {
1.89 + MapBase::destroy();
1.90 + }
1.91 + MapBase::operator=(copy);
1.92 + if (MapBase::getGraph()) {
1.93 + allocate_memory();
1.94 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.95 + set(it, copy[it]);
1.96 + }
1.97 + }
1.98 + return *this;
1.99 + }
1.100 +
1.101 + virtual ~Map() {
1.102 + if (capacity != 0) {
1.103 + MapBase::destroy();
1.104 + allocator.deallocate(values, capacity);
1.105 + }
1.106 + }
1.107 +
1.108 +
1.109 + Value& operator[](const Key& key) {
1.110 + int id = MapBase::getGraph()->id(key);
1.111 + return values[id];
1.112 + }
1.113 +
1.114 + const Value& operator[](const Key& key) const {
1.115 + int id = MapBase::getGraph()->id(key);
1.116 + return values[id];
1.117 + }
1.118 +
1.119 + const Value& get(const Key& key) const {
1.120 + int id = MapBase::getGraph()->id(key);
1.121 + return values[id];
1.122 + }
1.123 +
1.124 + void set(const Key& key, const Value& val) {
1.125 + int id = MapBase::getGraph()->id(key);
1.126 + values[id] = val;
1.127 + }
1.128 +
1.129 + void add(const Key& key) {
1.130 + int id = MapBase::getGraph()->id(key);
1.131 + if (id >= capacity) {
1.132 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.133 + while (new_capacity <= id) {
1.134 + new_capacity <<= 1;
1.135 + }
1.136 + Value* new_values = allocator.allocate(new_capacity);;
1.137 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.138 + int jd = MapBase::getGraph()->id(it);
1.139 + if (id != jd) {
1.140 + allocator.construct(&(new_values[jd]), values[jd]);
1.141 + allocator.destroy(&(values[jd]));
1.142 + }
1.143 + }
1.144 + if (capacity != 0) allocator.deallocate(values, capacity);
1.145 + values = new_values;
1.146 + capacity = new_capacity;
1.147 + }
1.148 + allocator.construct(&(values[id]), Value());
1.149 + }
1.150 +
1.151 + void erase(const Key& key) {
1.152 + int id = MapBase::getGraph()->id(key);
1.153 + allocator.destroy(&(values[id]));
1.154 + }
1.155 +
1.156 + void clear() {
1.157 + if (capacity != 0) {
1.158 + MapBase::destroy();
1.159 + allocator.deallocate(values, capacity);
1.160 + capacity = 0;
1.161 + }
1.162 + }
1.163 +
1.164 + class iterator {
1.165 + friend class Map;
1.166 + friend class const_iterator;
1.167 + private:
1.168 +
1.169 + /** Private constructor to initalize the the iterators returned
1.170 + * by the begin() and end().
1.171 + */
1.172 + iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
1.173 +
1.174 + public:
1.175 +
1.176 + /** Default constructor.
1.177 + */
1.178 + iterator() {}
1.179 +
1.180 + typedef extended_pair<const Key&, const Key&,
1.181 + Value&, Value&> Reference;
1.182 +
1.183 + /** Dereference operator for map.
1.184 + */
1.185 + Reference operator*() {
1.186 + return Reference(it, (*map)[it]);
1.187 + }
1.188 +
1.189 + class Pointer {
1.190 + friend class iterator;
1.191 + private:
1.192 + Reference data;
1.193 + Pointer(const Key& key, Value& val) : data(key, val) {}
1.194 + public:
1.195 + Reference* operator->() {return &data;}
1.196 + };
1.197 +
1.198 + /** Arrow operator for map.
1.199 + */
1.200 + Pointer operator->() {
1.201 + return Pointer(it, ((*map)[it]));
1.202 + }
1.203 +
1.204 + /** The pre increment operator of the map.
1.205 + */
1.206 + iterator& operator++() {
1.207 + ++it;
1.208 + return *this;
1.209 + }
1.210 +
1.211 + /** The post increment operator of the map.
1.212 + */
1.213 + iterator operator++(int) {
1.214 + iterator tmp(it);
1.215 + ++it;
1.216 + return tmp;
1.217 + }
1.218 +
1.219 + /** The equality operator of the map.
1.220 + */
1.221 + bool operator==(const_iterator p_it) {
1.222 + return p_it.it == it;
1.223 + }
1.224 +
1.225 + /** The not-equality operator of the map.
1.226 + */
1.227 + bool operator!=(const_iterator p_it) {
1.228 + return !(*this == p_it);
1.229 + }
1.230 +
1.231 +
1.232 + private:
1.233 + Map* map;
1.234 + KeyIt it;
1.235 + };
1.236 +
1.237 + /** Returns the begin iterator of the map.
1.238 + */
1.239 + iterator begin() {
1.240 + return iterator(*this, KeyIt(*MapBase::getGraph()));
1.241 + }
1.242 +
1.243 + /** Returns the end iterator of the map.
1.244 + */
1.245 + iterator end() {
1.246 + return iterator(*this, INVALID);
1.247 + }
1.248 +
1.249 + class const_iterator {
1.250 + friend class Map;
1.251 + friend class iterator;
1.252 + private:
1.253 +
1.254 + /** Private constructor to initalize the the iterators returned
1.255 + * by the begin() and end().
1.256 + */
1.257 + const_iterator (const Map& pmap, const KeyIt& pit)
1.258 + : map(&pmap), it(pit) {}
1.259 +
1.260 + public:
1.261 +
1.262 + /** Default constructor.
1.263 + */
1.264 + const_iterator() {}
1.265 +
1.266 + /** Constructor to convert iterator to const_iterator.
1.267 + */
1.268 + const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
1.269 +
1.270 + typedef extended_pair<const Key&, const Key&,
1.271 + const Value&, const Value&> Reference;
1.272 +
1.273 + /** Dereference operator for map.
1.274 + */
1.275 + Reference operator*() {
1.276 + return Reference(it, (*map)[it]);
1.277 + }
1.278 +
1.279 +
1.280 + class Pointer {
1.281 + friend class const_iterator;
1.282 + private:
1.283 + Reference data;
1.284 + Pointer(const Key& key, const Value& val) : data(key, val) {}
1.285 + public:
1.286 + Reference* operator->() {return &data;}
1.287 + };
1.288 +
1.289 + /** Arrow operator for map.
1.290 + */
1.291 + Pointer operator->() {
1.292 + return Pointer(it, ((*map)[it]));
1.293 + }
1.294 +
1.295 + /** The pre increment operator of the map.
1.296 + */
1.297 + const_iterator& operator++() {
1.298 + ++it;
1.299 + return *this;
1.300 + }
1.301 +
1.302 + /** The post increment operator of the map.
1.303 + */
1.304 + const_iterator operator++(int) {
1.305 + const_iterator tmp(it);
1.306 + ++it;
1.307 + return tmp;
1.308 + }
1.309 +
1.310 + /** The equality operator of the map.
1.311 + */
1.312 + bool operator==(const_iterator p_it) {
1.313 + return p_it.it == it;
1.314 + }
1.315 +
1.316 + /** The not-equality operator of the map.
1.317 + */
1.318 + bool operator!=(const_iterator p_it) {
1.319 + return !(*this == p_it);
1.320 + }
1.321 +
1.322 +
1.323 + private:
1.324 + const Map* map;
1.325 + KeyIt it;
1.326 + };
1.327 +
1.328 + /** Returns the begin const_iterator of the map.
1.329 + */
1.330 + const_iterator begin() const {
1.331 + return const_iterator(*this, KeyIt(*MapBase::getGraph()));
1.332 + }
1.333 +
1.334 + /** Returns the end const_iterator of the map.
1.335 + */
1.336 + const_iterator end() const {
1.337 + return const_iterator(*this, INVALID);
1.338 + }
1.339 +
1.340 + private:
1.341 +
1.342 + void allocate_memory() {
1.343 + int max_id = -1;
1.344 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.345 + int id = MapBase::getGraph()->id(it);
1.346 + if (id > max_id) {
1.347 + max_id = id;
1.348 + }
1.349 + }
1.350 + if (max_id == -1) {
1.351 + capacity = 0;
1.352 + values = 0;
1.353 + return;
1.354 + }
1.355 + capacity = 1;
1.356 + while (capacity <= max_id) {
1.357 + capacity <<= 1;
1.358 + }
1.359 + values = allocator.allocate(capacity);
1.360 + }
1.361 +
1.362 + int capacity;
1.363 + Value* values;
1.364 + Allocator allocator;
1.365 + };
1.366 + };
1.367 +}
1.368 +
1.369 +#endif