1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/array_map.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,349 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_ARRAY_MAP_H
1.21 +#define LEMON_ARRAY_MAP_H
1.22 +
1.23 +#include <memory>
1.24 +
1.25 +#include <lemon/map_iterator.h>
1.26 +#include <lemon/map_bits.h>
1.27 +
1.28 +///\ingroup graphmaps
1.29 +///\file
1.30 +///\brief Graph maps that construates and destruates
1.31 +///their elements dynamically.
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 +
1.36 + /// \addtogroup graphmaps
1.37 + /// @{
1.38 +
1.39 + /** The ArrayMap template class is graph map structure what
1.40 + * automatically updates the map when a key is added to or erased from
1.41 + * the map. This map factory uses the allocators to implement
1.42 + * the container functionality.
1.43 + *
1.44 + * The template parameter is the MapRegistry that the maps
1.45 + * will belong to and the ValueType.
1.46 + */
1.47 +
1.48 + template <typename MapRegistry, typename Value>
1.49 + class ArrayMap : public MapRegistry::MapBase {
1.50 +
1.51 + template <typename MR, typename V> friend class ArrayMap;
1.52 +
1.53 + public:
1.54 +
1.55 + /// The graph type of the maps.
1.56 + typedef typename MapRegistry::Graph Graph;
1.57 + /// The key type of the maps.
1.58 + typedef typename MapRegistry::KeyType KeyType;
1.59 + /// The iterator to iterate on the keys.
1.60 + typedef typename MapRegistry::KeyIt KeyIt;
1.61 +
1.62 + /// The MapBase of the Map which imlements the core regisitry function.
1.63 + typedef typename MapRegistry::MapBase MapBase;
1.64 +
1.65 +
1.66 + public:
1.67 +
1.68 + /// The value type of the map.
1.69 + typedef Value ValueType;
1.70 + /// The reference type of the map;
1.71 + typedef Value& ReferenceType;
1.72 + /// The pointer type of the map;
1.73 + typedef Value* PointerType;
1.74 +
1.75 + /// The const value type of the map.
1.76 + typedef const Value ConstValueType;
1.77 + /// The const reference type of the map;
1.78 + typedef const Value& ConstReferenceType;
1.79 + /// The pointer type of the map;
1.80 + typedef const Value* ConstPointerType;
1.81 +
1.82 +
1.83 + typedef std::allocator<Value> Allocator;
1.84 +
1.85 +
1.86 + /** Graph and Registry initialized map constructor.
1.87 + */
1.88 + ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.89 + allocate_memory();
1.90 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.91 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.92 + allocator.construct(&(values[id]), Value());
1.93 + }
1.94 + }
1.95 +
1.96 + /** Constructor to use default value to initialize the map.
1.97 + */
1.98 + ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
1.99 + : MapBase(g, r) {
1.100 + allocate_memory();
1.101 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.102 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.103 + allocator.construct(&(values[id]), v);
1.104 + }
1.105 + }
1.106 +
1.107 + /** Constructor to copy a map of the same map type.
1.108 + */
1.109 + ArrayMap(const ArrayMap& copy) : MapBase(copy) {
1.110 + capacity = copy.capacity;
1.111 + if (capacity == 0) return;
1.112 + values = allocator.allocate(capacity);
1.113 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.114 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.115 + allocator.construct(&(values[id]), copy.values[id]);
1.116 + }
1.117 + }
1.118 +
1.119 + /** Constructor to copy a map of an other map type.
1.120 + */
1.121 + template <typename TT>
1.122 + ArrayMap(const ArrayMap<MapRegistry, TT>& copy)
1.123 + : MapBase(copy) {
1.124 + capacity = copy.capacity;
1.125 + if (capacity == 0) return;
1.126 + values = allocator.allocate(capacity);
1.127 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.128 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.129 + allocator.construct(&(values[id]), copy.values[id]);
1.130 + }
1.131 + }
1.132 +
1.133 + /** Assign operator to copy a map of the same map type.
1.134 + */
1.135 + ArrayMap& operator=(const ArrayMap& copy) {
1.136 + if (© == this) return *this;
1.137 +
1.138 + if (MapBase::getGraph() != copy.getGraph()) {
1.139 + if (capacity != 0) {
1.140 + MapBase::destroy();
1.141 + allocator.deallocate(values, capacity);
1.142 + }
1.143 +
1.144 + MapBase::operator=(copy);
1.145 + capacity = copy.capacity;
1.146 + if (capacity == 0) return *this;
1.147 + values = allocator.allocate(capacity);
1.148 + }
1.149 +
1.150 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.151 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.152 + allocator.construct(&(values[id]), copy.values[id]);
1.153 + }
1.154 +
1.155 + return *this;
1.156 + }
1.157 +
1.158 + /** Assign operator to copy a map of an other map type.
1.159 + */
1.160 + template <typename TT>
1.161 + ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
1.162 +
1.163 + if (MapBase::getGraph() != copy.getGraph()) {
1.164 + if (capacity != 0) {
1.165 + MapBase::destroy();
1.166 + allocator.deallocate(values, capacity);
1.167 + }
1.168 +
1.169 + MapBase::operator=(copy);
1.170 +
1.171 + capacity = copy.capacity;
1.172 + if (capacity == 0) return *this;
1.173 + values = allocator.allocate(capacity);
1.174 + }
1.175 +
1.176 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.177 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.178 + allocator.construct(&(values[id]), copy.values[id]);
1.179 + }
1.180 +
1.181 + return *this;
1.182 + }
1.183 +
1.184 + /** The destructor of the map.
1.185 + */
1.186 + virtual ~ArrayMap() {
1.187 + if (capacity != 0) {
1.188 + MapBase::destroy();
1.189 + allocator.deallocate(values, capacity);
1.190 + }
1.191 + }
1.192 +
1.193 +
1.194 + /**
1.195 + * The subscript operator. The map can be subscripted by the
1.196 + * actual keys of the graph.
1.197 + */
1.198 + ReferenceType operator[](const KeyType& key) {
1.199 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.200 + return values[id];
1.201 + }
1.202 +
1.203 + /**
1.204 + * The const subscript operator. The map can be subscripted by the
1.205 + * actual keys of the graph.
1.206 + */
1.207 + ConstReferenceType operator[](const KeyType& key) const {
1.208 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.209 + return values[id];
1.210 + }
1.211 +
1.212 + /** Setter function of the map. Equivalent with map[key] = val.
1.213 + * This is a compatibility feature with the not dereferable maps.
1.214 + */
1.215 + void set(const KeyType& key, const ValueType& val) {
1.216 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.217 + values[id] = val;
1.218 + }
1.219 +
1.220 + /** Add a new key to the map. It called by the map registry.
1.221 + */
1.222 + void add(const KeyType& key) {
1.223 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.224 + if (id >= capacity) {
1.225 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.226 + while (new_capacity <= id) {
1.227 + new_capacity <<= 1;
1.228 + }
1.229 + Value* new_values = allocator.allocate(new_capacity);;
1.230 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.231 + int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.232 + if (id != jd) {
1.233 + allocator.construct(&(new_values[jd]), values[jd]);
1.234 + allocator.destroy(&(values[jd]));
1.235 + }
1.236 + }
1.237 + if (capacity != 0) allocator.deallocate(values, capacity);
1.238 + values = new_values;
1.239 + capacity = new_capacity;
1.240 + }
1.241 + allocator.construct(&(values[id]), Value());
1.242 + }
1.243 +
1.244 + /** Erase a key from the map. It called by the map registry.
1.245 + */
1.246 + void erase(const KeyType& key) {
1.247 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.248 + allocator.destroy(&(values[id]));
1.249 + }
1.250 +
1.251 + /** Clear the data structure.
1.252 + */
1.253 + void clear() {
1.254 + if (capacity != 0) {
1.255 + MapBase::destroy();
1.256 + allocator.deallocate(values, capacity);
1.257 + capacity = 0;
1.258 + }
1.259 + }
1.260 +
1.261 + /// The stl compatible pair iterator of the map.
1.262 + typedef MapIterator<ArrayMap> Iterator;
1.263 + /// The stl compatible const pair iterator of the map.
1.264 + typedef MapConstIterator<ArrayMap> ConstIterator;
1.265 +
1.266 + /** Returns the begin iterator of the map.
1.267 + */
1.268 + Iterator begin() {
1.269 + return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.270 + }
1.271 +
1.272 + /** Returns the end iterator of the map.
1.273 + */
1.274 + Iterator end() {
1.275 + return Iterator(*this, INVALID);
1.276 + }
1.277 +
1.278 + /** Returns the begin ConstIterator of the map.
1.279 + */
1.280 + ConstIterator begin() const {
1.281 + return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.282 + }
1.283 +
1.284 + /** Returns the end const_iterator of the map.
1.285 + */
1.286 + ConstIterator end() const {
1.287 + return ConstIterator(*this, INVALID);
1.288 + }
1.289 +
1.290 + /// The KeySet of the Map.
1.291 + typedef MapConstKeySet<ArrayMap> ConstKeySet;
1.292 +
1.293 + /// KeySet getter function.
1.294 + ConstKeySet keySet() const {
1.295 + return ConstKeySet(*this);
1.296 + }
1.297 +
1.298 + /// The ConstValueSet of the Map.
1.299 + typedef MapConstValueSet<ArrayMap> ConstValueSet;
1.300 +
1.301 + /// ConstValueSet getter function.
1.302 + ConstValueSet valueSet() const {
1.303 + return ConstValueSet(*this);
1.304 + }
1.305 +
1.306 + /// The ValueSet of the Map.
1.307 + typedef MapValueSet<ArrayMap> ValueSet;
1.308 +
1.309 + /// ValueSet getter function.
1.310 + ValueSet valueSet() {
1.311 + return ValueSet(*this);
1.312 + }
1.313 +
1.314 + private:
1.315 +
1.316 + void allocate_memory() {
1.317 + int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
1.318 + if (max_id == -1) {
1.319 + capacity = 0;
1.320 + values = 0;
1.321 + return;
1.322 + }
1.323 + capacity = 1;
1.324 + while (capacity <= max_id) {
1.325 + capacity <<= 1;
1.326 + }
1.327 + values = allocator.allocate(capacity);
1.328 + }
1.329 +
1.330 + int capacity;
1.331 + Value* values;
1.332 + Allocator allocator;
1.333 +
1.334 + public:
1.335 + // STL compatibility typedefs.
1.336 + typedef Iterator iterator;
1.337 + typedef ConstIterator const_iterator;
1.338 + typedef typename Iterator::PairValueType value_type;
1.339 + typedef typename Iterator::KeyType key_type;
1.340 + typedef typename Iterator::ValueType data_type;
1.341 + typedef typename Iterator::PairReferenceType reference;
1.342 + typedef typename Iterator::PairPointerType pointer;
1.343 + typedef typename ConstIterator::PairReferenceType const_reference;
1.344 + typedef typename ConstIterator::PairPointerType const_pointer;
1.345 + typedef int difference_type;
1.346 + };
1.347 +
1.348 +/// @}
1.349 +
1.350 +}
1.351 +
1.352 +#endif //LEMON_ARRAY_MAP_H