1.1 --- a/src/lemon/bits/array_map.h Wed May 11 17:36:25 2005 +0000
1.2 +++ b/src/lemon/bits/array_map.h Sat May 14 17:20:40 2005 +0000
1.3 @@ -1,5 +1,5 @@
1.4 /* -*- C++ -*-
1.5 - * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
1.6 + * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
1.7 *
1.8 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.9 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.10 @@ -31,14 +31,14 @@
1.11 /// \addtogroup graphmaps
1.12 /// @{
1.13
1.14 - /** The ArrayMap template class is graph map structure what
1.15 - * automatically updates the map when a key is added to or erased from
1.16 - * the map. This map factory uses the allocators to implement
1.17 - * the container functionality.
1.18 - *
1.19 - * The template parameter is the AlterationNotifier that the maps
1.20 - * will belong to and the Value.
1.21 - */
1.22 + /// The ArrayMap template class is graph map structure what
1.23 + /// automatically updates the map when a key is added to or erased from
1.24 + /// the map. This map factory uses the allocators to implement
1.25 + /// the container functionality.
1.26 + ///
1.27 + /// The template parameter is the AlterationNotifier that the maps
1.28 + /// will belong to and the Value.
1.29 +
1.30
1.31 template <typename _Graph,
1.32 typename _Item,
1.33 @@ -68,8 +68,8 @@
1.34
1.35 public:
1.36
1.37 - /** Graph and Registry initialized map constructor.
1.38 - */
1.39 + /// Graph and Registry initialized map constructor.
1.40 +
1.41 ArrayMap(const Graph& _g) : graph(&_g) {
1.42 Item it;
1.43 attach(_g.getNotifier(Item()));
1.44 @@ -94,8 +94,8 @@
1.45 }
1.46 }
1.47
1.48 - /** Constructor to copy a map of the same map type.
1.49 - */
1.50 + /// Constructor to copy a map of the same map type.
1.51 +
1.52 ArrayMap(const ArrayMap& copy) : Parent() {
1.53 if (copy.attached()) {
1.54 attach(*copy.getRegistry());
1.55 @@ -114,8 +114,8 @@
1.56 using Parent::detach;
1.57 using Parent::attached;
1.58
1.59 - /** Assign operator to copy a map of the same map type.
1.60 - */
1.61 + /// Assign operator to copy a map of the same map type.
1.62 +
1.63 ArrayMap& operator=(const ArrayMap& copy) {
1.64 if (© == this) return *this;
1.65
1.66 @@ -141,8 +141,8 @@
1.67 return *this;
1.68 }
1.69
1.70 - /** The destructor of the map.
1.71 - */
1.72 + /// The destructor of the map.
1.73 +
1.74 virtual ~ArrayMap() {
1.75 if (attached()) {
1.76 clear();
1.77 @@ -151,33 +151,32 @@
1.78 }
1.79
1.80
1.81 - /**
1.82 - * The subscript operator. The map can be subscripted by the
1.83 - * actual keys of the graph.
1.84 - */
1.85 + ///The subscript operator. The map can be subscripted by the
1.86 + ///actual keys of the graph.
1.87 +
1.88 Value& operator[](const Key& key) {
1.89 int id = graph->id(key);
1.90 return values[id];
1.91 }
1.92
1.93 - /**
1.94 - * The const subscript operator. The map can be subscripted by the
1.95 - * actual keys of the graph.
1.96 - */
1.97 +
1.98 + ///The const subscript operator. The map can be subscripted by the
1.99 + ///actual keys of the graph.
1.100 +
1.101 const Value& operator[](const Key& key) const {
1.102 int id = graph->id(key);
1.103 return values[id];
1.104 }
1.105
1.106 - /** Setter function of the map. Equivalent with map[key] = val.
1.107 - * This is a compatibility feature with the not dereferable maps.
1.108 - */
1.109 + /// Setter function of the map. Equivalent with map[key] = val.
1.110 + /// This is a compatibility feature with the not dereferable maps.
1.111 +
1.112 void set(const Key& key, const Value& val) {
1.113 (*this)[key] = val;
1.114 }
1.115
1.116 - /** Add a new key to the map. It called by the map registry.
1.117 - */
1.118 + /// Add a new key to the map. It called by the map registry.
1.119 +
1.120 void add(const Key& key) {
1.121 int id = graph->id(key);
1.122 if (id >= capacity) {
1.123 @@ -200,14 +199,60 @@
1.124 }
1.125 allocator.construct(&(values[id]), Value());
1.126 }
1.127 +
1.128 + void add(const std::vector<Key>& keys) {
1.129 + int max_id = -1;
1.130 + for (int i = 0; i < (int)keys.size(); ++i) {
1.131 + int id = graph->id(keys[i]);
1.132 + if (id > max_id) {
1.133 + max_id = id;
1.134 + }
1.135 + }
1.136 + if (max_id >= capacity) {
1.137 + int new_capacity = (capacity == 0 ? 1 : capacity);
1.138 + while (new_capacity <= max_id) {
1.139 + new_capacity <<= 1;
1.140 + }
1.141 + Value* new_values = allocator.allocate(new_capacity);
1.142 + Item it;
1.143 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.144 + int id = graph->id(it);
1.145 + bool found = false;
1.146 + for (int i = 0; i < (int)keys.size(); ++i) {
1.147 + int jd = graph->id(keys[i]);
1.148 + if (id == jd) {
1.149 + found = true;
1.150 + break;
1.151 + }
1.152 + }
1.153 + if (found) continue;
1.154 + allocator.construct(&(new_values[id]), values[id]);
1.155 + allocator.destroy(&(values[id]));
1.156 + }
1.157 + if (capacity != 0) allocator.deallocate(values, capacity);
1.158 + values = new_values;
1.159 + capacity = new_capacity;
1.160 + }
1.161 + for (int i = 0; i < (int)keys.size(); ++i) {
1.162 + int id = graph->id(keys[i]);
1.163 + allocator.construct(&(values[id]), Value());
1.164 + }
1.165 + }
1.166
1.167 - /** Erase a key from the map. It called by the map registry.
1.168 - */
1.169 + /// Erase a key from the map. It called by the map registry.
1.170 +
1.171 void erase(const Key& key) {
1.172 int id = graph->id(key);
1.173 allocator.destroy(&(values[id]));
1.174 }
1.175
1.176 + void erase(const std::vector<Key>& keys) {
1.177 + for (int i = 0; i < (int)keys.size(); ++i) {
1.178 + int id = graph->id(keys[i]);
1.179 + allocator.destroy(&(values[id]));
1.180 + }
1.181 + }
1.182 +
1.183 void build() {
1.184 allocate_memory();
1.185 Item it;
1.186 @@ -221,7 +266,7 @@
1.187 if (capacity != 0) {
1.188 Item it;
1.189 for (graph->first(it); it != INVALID; graph->next(it)) {
1.190 - int id = graph->id(it);;
1.191 + int id = graph->id(it);
1.192 allocator.destroy(&(values[id]));
1.193 }
1.194 allocator.deallocate(values, capacity);
1.195 @@ -233,59 +278,6 @@
1.196 return graph;
1.197 }
1.198
1.199 -// /// The stl compatible pair iterator of the map.
1.200 -// typedef MapIterator<ArrayMap> Iterator;
1.201 -// /// The stl compatible const pair iterator of the map.
1.202 -// typedef MapConstIterator<ArrayMap> ConstIterator;
1.203 -
1.204 -// /** Returns the begin iterator of the map.
1.205 -// */
1.206 -// Iterator begin() {
1.207 -// return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.208 -// }
1.209 -
1.210 -// /** Returns the end iterator of the map.
1.211 -// */
1.212 -// Iterator end() {
1.213 -// return Iterator(*this, INVALID);
1.214 -// }
1.215 -
1.216 -// /** Returns the begin ConstIterator of the map.
1.217 -// */
1.218 -// ConstIterator begin() const {
1.219 -// return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.220 -// }
1.221 -
1.222 -// /** Returns the end const_iterator of the map.
1.223 -// */
1.224 -// ConstIterator end() const {
1.225 -// return ConstIterator(*this, INVALID);
1.226 -// }
1.227 -
1.228 -// /// The KeySet of the Map.
1.229 -// typedef MapConstKeySet<ArrayMap> ConstKeySet;
1.230 -
1.231 -// /// KeySet getter function.
1.232 -// ConstKeySet keySet() const {
1.233 -// return ConstKeySet(*this);
1.234 -// }
1.235 -
1.236 -// /// The ConstValueSet of the Map.
1.237 -// typedef MapConstValueSet<ArrayMap> ConstValueSet;
1.238 -
1.239 -// /// ConstValueSet getter function.
1.240 -// ConstValueSet valueSet() const {
1.241 -// return ConstValueSet(*this);
1.242 -// }
1.243 -
1.244 -// /// The ValueSet of the Map.
1.245 -// typedef MapValueSet<ArrayMap> ValueSet;
1.246 -
1.247 -// /// ValueSet getter function.
1.248 -// ValueSet valueSet() {
1.249 -// return ValueSet(*this);
1.250 -// }
1.251 -
1.252 private:
1.253
1.254 void allocate_memory() {