1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/array_map.h Sun Jan 20 20:43:48 2008 +0100
1.3 @@ -0,0 +1,346 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BITS_ARRAY_MAP_H
1.23 +#define LEMON_BITS_ARRAY_MAP_H
1.24 +
1.25 +#include <memory>
1.26 +
1.27 +#include <lemon/bits/traits.h>
1.28 +#include <lemon/bits/alteration_notifier.h>
1.29 +#include <lemon/concept_check.h>
1.30 +#include <lemon/concepts/maps.h>
1.31 +
1.32 +/// \ingroup graphbits
1.33 +/// \file
1.34 +/// \brief Graph map based on the array storage.
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 + /// \ingroup graphbits
1.39 + ///
1.40 + /// \brief Graph map based on the array storage.
1.41 + ///
1.42 + /// The ArrayMap template class is graph map structure what
1.43 + /// automatically updates the map when a key is added to or erased from
1.44 + /// the map. This map uses the allocators to implement
1.45 + /// the container functionality.
1.46 + ///
1.47 + /// The template parameters are the Graph the current Item type and
1.48 + /// the Value type of the map.
1.49 + template <typename _Graph, typename _Item, typename _Value>
1.50 + class ArrayMap
1.51 + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
1.52 + public:
1.53 + /// The graph type of the maps.
1.54 + typedef _Graph Graph;
1.55 + /// The item type of the map.
1.56 + typedef _Item Item;
1.57 + /// The reference map tag.
1.58 + typedef True ReferenceMapTag;
1.59 +
1.60 + /// The key type of the maps.
1.61 + typedef _Item Key;
1.62 + /// The value type of the map.
1.63 + typedef _Value Value;
1.64 +
1.65 + /// The const reference type of the map.
1.66 + typedef const _Value& ConstReference;
1.67 + /// The reference type of the map.
1.68 + typedef _Value& Reference;
1.69 +
1.70 + /// The notifier type.
1.71 + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
1.72 +
1.73 + /// The MapBase of the Map which imlements the core regisitry function.
1.74 + typedef typename Notifier::ObserverBase Parent;
1.75 +
1.76 + private:
1.77 + typedef std::allocator<Value> Allocator;
1.78 +
1.79 + public:
1.80 +
1.81 + /// \brief Graph initialized map constructor.
1.82 + ///
1.83 + /// Graph initialized map constructor.
1.84 + explicit ArrayMap(const Graph& graph) {
1.85 + Parent::attach(graph.notifier(Item()));
1.86 + allocate_memory();
1.87 + Notifier* nf = Parent::notifier();
1.88 + Item it;
1.89 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.90 + int id = nf->id(it);;
1.91 + allocator.construct(&(values[id]), Value());
1.92 + }
1.93 + }
1.94 +
1.95 + /// \brief Constructor to use default value to initialize the map.
1.96 + ///
1.97 + /// It constructs a map and initialize all of the the map.
1.98 + ArrayMap(const Graph& graph, const Value& value) {
1.99 + Parent::attach(graph.notifier(Item()));
1.100 + allocate_memory();
1.101 + Notifier* nf = Parent::notifier();
1.102 + Item it;
1.103 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.104 + int id = nf->id(it);;
1.105 + allocator.construct(&(values[id]), value);
1.106 + }
1.107 + }
1.108 +
1.109 + /// \brief Constructor to copy a map of the same map type.
1.110 + ///
1.111 + /// Constructor to copy a map of the same map type.
1.112 + ArrayMap(const ArrayMap& copy) : Parent() {
1.113 + if (copy.attached()) {
1.114 + attach(*copy.notifier());
1.115 + }
1.116 + capacity = copy.capacity;
1.117 + if (capacity == 0) return;
1.118 + values = allocator.allocate(capacity);
1.119 + Notifier* nf = Parent::notifier();
1.120 + Item it;
1.121 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.122 + int id = nf->id(it);;
1.123 + allocator.construct(&(values[id]), copy.values[id]);
1.124 + }
1.125 + }
1.126 +
1.127 + /// \brief Assign operator.
1.128 + ///
1.129 + /// This operator assigns for each item in the map the
1.130 + /// value mapped to the same item in the copied map.
1.131 + /// The parameter map should be indiced with the same
1.132 + /// itemset because this assign operator does not change
1.133 + /// the container of the map.
1.134 + ArrayMap& operator=(const ArrayMap& cmap) {
1.135 + return operator=<ArrayMap>(cmap);
1.136 + }
1.137 +
1.138 +
1.139 + /// \brief Template assign operator.
1.140 + ///
1.141 + /// The given parameter should be conform to the ReadMap
1.142 + /// concecpt and could be indiced by the current item set of
1.143 + /// the NodeMap. In this case the value for each item
1.144 + /// is assigned by the value of the given ReadMap.
1.145 + template <typename CMap>
1.146 + ArrayMap& operator=(const CMap& cmap) {
1.147 + checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
1.148 + const typename Parent::Notifier* nf = Parent::notifier();
1.149 + Item it;
1.150 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.151 + set(it, cmap[it]);
1.152 + }
1.153 + return *this;
1.154 + }
1.155 +
1.156 + /// \brief The destructor of the map.
1.157 + ///
1.158 + /// The destructor of the map.
1.159 + virtual ~ArrayMap() {
1.160 + if (attached()) {
1.161 + clear();
1.162 + detach();
1.163 + }
1.164 + }
1.165 +
1.166 + protected:
1.167 +
1.168 + using Parent::attach;
1.169 + using Parent::detach;
1.170 + using Parent::attached;
1.171 +
1.172 + public:
1.173 +
1.174 + /// \brief The subscript operator.
1.175 + ///
1.176 + /// The subscript operator. The map can be subscripted by the
1.177 + /// actual keys of the graph.
1.178 + Value& operator[](const Key& key) {
1.179 + int id = Parent::notifier()->id(key);
1.180 + return values[id];
1.181 + }
1.182 +
1.183 + /// \brief The const subscript operator.
1.184 + ///
1.185 + /// The const subscript operator. The map can be subscripted by the
1.186 + /// actual keys of the graph.
1.187 + const Value& operator[](const Key& key) const {
1.188 + int id = Parent::notifier()->id(key);
1.189 + return values[id];
1.190 + }
1.191 +
1.192 + /// \brief Setter function of the map.
1.193 + ///
1.194 + /// Setter function of the map. Equivalent with map[key] = val.
1.195 + /// This is a compatibility feature with the not dereferable maps.
1.196 + void set(const Key& key, const Value& val) {
1.197 + (*this)[key] = val;
1.198 + }
1.199 +
1.200 + protected:
1.201 +
1.202 + /// \brief Adds a new key to the map.
1.203 + ///
1.204 + /// It adds a new key to the map. It called by the observer notifier
1.205 + /// and it overrides the add() member function of the observer base.
1.206 + virtual void add(const Key& key) {
1.207 + Notifier* nf = Parent::notifier();
1.208 + int id = nf->id(key);
1.209 + if (id >= capacity) {
1.210 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.211 + while (new_capacity <= id) {
1.212 + new_capacity <<= 1;
1.213 + }
1.214 + Value* new_values = allocator.allocate(new_capacity);
1.215 + Item it;
1.216 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.217 + int jd = nf->id(it);;
1.218 + if (id != jd) {
1.219 + allocator.construct(&(new_values[jd]), values[jd]);
1.220 + allocator.destroy(&(values[jd]));
1.221 + }
1.222 + }
1.223 + if (capacity != 0) allocator.deallocate(values, capacity);
1.224 + values = new_values;
1.225 + capacity = new_capacity;
1.226 + }
1.227 + allocator.construct(&(values[id]), Value());
1.228 + }
1.229 +
1.230 + /// \brief Adds more new keys to the map.
1.231 + ///
1.232 + /// It adds more new keys to the map. It called by the observer notifier
1.233 + /// and it overrides the add() member function of the observer base.
1.234 + virtual void add(const std::vector<Key>& keys) {
1.235 + Notifier* nf = Parent::notifier();
1.236 + int max_id = -1;
1.237 + for (int i = 0; i < int(keys.size()); ++i) {
1.238 + int id = nf->id(keys[i]);
1.239 + if (id > max_id) {
1.240 + max_id = id;
1.241 + }
1.242 + }
1.243 + if (max_id >= capacity) {
1.244 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.245 + while (new_capacity <= max_id) {
1.246 + new_capacity <<= 1;
1.247 + }
1.248 + Value* new_values = allocator.allocate(new_capacity);
1.249 + Item it;
1.250 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.251 + int id = nf->id(it);
1.252 + bool found = false;
1.253 + for (int i = 0; i < int(keys.size()); ++i) {
1.254 + int jd = nf->id(keys[i]);
1.255 + if (id == jd) {
1.256 + found = true;
1.257 + break;
1.258 + }
1.259 + }
1.260 + if (found) continue;
1.261 + allocator.construct(&(new_values[id]), values[id]);
1.262 + allocator.destroy(&(values[id]));
1.263 + }
1.264 + if (capacity != 0) allocator.deallocate(values, capacity);
1.265 + values = new_values;
1.266 + capacity = new_capacity;
1.267 + }
1.268 + for (int i = 0; i < int(keys.size()); ++i) {
1.269 + int id = nf->id(keys[i]);
1.270 + allocator.construct(&(values[id]), Value());
1.271 + }
1.272 + }
1.273 +
1.274 + /// \brief Erase a key from the map.
1.275 + ///
1.276 + /// Erase a key from the map. It called by the observer notifier
1.277 + /// and it overrides the erase() member function of the observer base.
1.278 + virtual void erase(const Key& key) {
1.279 + int id = Parent::notifier()->id(key);
1.280 + allocator.destroy(&(values[id]));
1.281 + }
1.282 +
1.283 + /// \brief Erase more keys from the map.
1.284 + ///
1.285 + /// Erase more keys from the map. It called by the observer notifier
1.286 + /// and it overrides the erase() member function of the observer base.
1.287 + virtual void erase(const std::vector<Key>& keys) {
1.288 + for (int i = 0; i < int(keys.size()); ++i) {
1.289 + int id = Parent::notifier()->id(keys[i]);
1.290 + allocator.destroy(&(values[id]));
1.291 + }
1.292 + }
1.293 +
1.294 + /// \brief Buildes the map.
1.295 + ///
1.296 + /// It buildes the map. It called by the observer notifier
1.297 + /// and it overrides the build() member function of the observer base.
1.298 + virtual void build() {
1.299 + Notifier* nf = Parent::notifier();
1.300 + allocate_memory();
1.301 + Item it;
1.302 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.303 + int id = nf->id(it);;
1.304 + allocator.construct(&(values[id]), Value());
1.305 + }
1.306 + }
1.307 +
1.308 + /// \brief Clear the map.
1.309 + ///
1.310 + /// It erase all items from the map. It called by the observer notifier
1.311 + /// and it overrides the clear() member function of the observer base.
1.312 + virtual void clear() {
1.313 + Notifier* nf = Parent::notifier();
1.314 + if (capacity != 0) {
1.315 + Item it;
1.316 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.317 + int id = nf->id(it);
1.318 + allocator.destroy(&(values[id]));
1.319 + }
1.320 + allocator.deallocate(values, capacity);
1.321 + capacity = 0;
1.322 + }
1.323 + }
1.324 +
1.325 + private:
1.326 +
1.327 + void allocate_memory() {
1.328 + int max_id = Parent::notifier()->maxId();
1.329 + if (max_id == -1) {
1.330 + capacity = 0;
1.331 + values = 0;
1.332 + return;
1.333 + }
1.334 + capacity = 1;
1.335 + while (capacity <= max_id) {
1.336 + capacity <<= 1;
1.337 + }
1.338 + values = allocator.allocate(capacity);
1.339 + }
1.340 +
1.341 + int capacity;
1.342 + Value* values;
1.343 + Allocator allocator;
1.344 +
1.345 + };
1.346 +
1.347 +}
1.348 +
1.349 +#endif