1.1 --- a/src/hugo/array_map.h Wed Sep 29 14:12:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,349 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/hugo/array_map.h - Part of HUGOlib, 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 HUGO_ARRAY_MAP_H
1.21 -#define HUGO_ARRAY_MAP_H
1.22 -
1.23 -#include <memory>
1.24 -
1.25 -#include <hugo/map_iterator.h>
1.26 -#include <hugo/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 hugo {
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 //HUGO_ARRAY_MAP_H