00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_ARRAY_MAP_H
00020 #define LEMON_ARRAY_MAP_H
00021
00022 #include <memory>
00023 #include <lemon/bits/map_extender.h>
00024 #include <lemon/bits/alteration_notifier.h>
00025 #include <lemon/concept_check.h>
00026 #include <lemon/concept/maps.h>
00027
00032
00033 namespace lemon {
00034
00046
00047 template <typename _Graph,
00048 typename _Item,
00049 typename _Value>
00050 class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
00051
00052 typedef _Item Item;
00053 public:
00055 typedef _Graph Graph;
00057 typedef True ReferenceMapTag;
00058
00060 typedef _Item Key;
00062 typedef _Value Value;
00064 typedef const _Value& ConstReference;
00066 typedef _Value& Reference;
00067
00068 typedef const Value ConstValue;
00069 typedef Value* Pointer;
00070 typedef const Value* ConstPointer;
00071
00072 typedef AlterationNotifier<_Item> Registry;
00073
00075 typedef typename Registry::ObserverBase Parent;
00076
00077
00078
00079 private:
00080 typedef std::allocator<Value> Allocator;
00081
00082
00083 public:
00084
00088 ArrayMap(const Graph& _g) : graph(&_g) {
00089 Item it;
00090 attach(_g.getNotifier(Item()));
00091 allocate_memory();
00092 for (graph->first(it); it != INVALID; graph->next(it)) {
00093 int id = graph->id(it);;
00094 allocator.construct(&(values[id]), Value());
00095 }
00096 }
00097
00101 ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
00102 Item it;
00103 attach(_g.getNotifier(_Item()));
00104 allocate_memory();
00105 for (graph->first(it); it != INVALID; graph->next(it)) {
00106 int id = graph->id(it);;
00107 allocator.construct(&(values[id]), _v);
00108 }
00109 }
00110
00114 ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
00115 if (copy.attached()) {
00116 attach(*copy.getRegistry());
00117 }
00118 capacity = copy.capacity;
00119 if (capacity == 0) return;
00120 values = allocator.allocate(capacity);
00121 Item it;
00122 for (graph->first(it); it != INVALID; graph->next(it)) {
00123 int id = graph->id(it);;
00124 allocator.construct(&(values[id]), copy.values[id]);
00125 }
00126 }
00127
00131 virtual ~ArrayMap() {
00132 if (attached()) {
00133 clear();
00134 detach();
00135 }
00136 }
00137
00138 private:
00139
00140 ArrayMap& operator=(const ArrayMap&);
00141
00142 protected:
00143
00144 using Parent::attach;
00145 using Parent::detach;
00146 using Parent::attached;
00147
00148 const Graph* getGraph() {
00149 return graph;
00150 }
00151
00152
00153 public:
00154
00159 Value& operator[](const Key& key) {
00160 int id = graph->id(key);
00161 return values[id];
00162 }
00163
00168 const Value& operator[](const Key& key) const {
00169 int id = graph->id(key);
00170 return values[id];
00171 }
00172
00177 void set(const Key& key, const Value& val) {
00178 (*this)[key] = val;
00179 }
00180
00181 protected:
00182
00184
00185 virtual void add(const Key& key) {
00186 int id = graph->id(key);
00187 if (id >= capacity) {
00188 int new_capacity = (capacity == 0 ? 1 : capacity);
00189 while (new_capacity <= id) {
00190 new_capacity <<= 1;
00191 }
00192 Value* new_values = allocator.allocate(new_capacity);
00193 Item it;
00194 for (graph->first(it); it != INVALID; graph->next(it)) {
00195 int jd = graph->id(it);;
00196 if (id != jd) {
00197 allocator.construct(&(new_values[jd]), values[jd]);
00198 allocator.destroy(&(values[jd]));
00199 }
00200 }
00201 if (capacity != 0) allocator.deallocate(values, capacity);
00202 values = new_values;
00203 capacity = new_capacity;
00204 }
00205 allocator.construct(&(values[id]), Value());
00206 }
00207
00208 virtual void add(const std::vector<Key>& keys) {
00209 int max_id = -1;
00210 for (int i = 0; i < (int)keys.size(); ++i) {
00211 int id = graph->id(keys[i]);
00212 if (id > max_id) {
00213 max_id = id;
00214 }
00215 }
00216 if (max_id >= capacity) {
00217 int new_capacity = (capacity == 0 ? 1 : capacity);
00218 while (new_capacity <= max_id) {
00219 new_capacity <<= 1;
00220 }
00221 Value* new_values = allocator.allocate(new_capacity);
00222 Item it;
00223 for (graph->first(it); it != INVALID; graph->next(it)) {
00224 int id = graph->id(it);
00225 bool found = false;
00226 for (int i = 0; i < (int)keys.size(); ++i) {
00227 int jd = graph->id(keys[i]);
00228 if (id == jd) {
00229 found = true;
00230 break;
00231 }
00232 }
00233 if (found) continue;
00234 allocator.construct(&(new_values[id]), values[id]);
00235 allocator.destroy(&(values[id]));
00236 }
00237 if (capacity != 0) allocator.deallocate(values, capacity);
00238 values = new_values;
00239 capacity = new_capacity;
00240 }
00241 for (int i = 0; i < (int)keys.size(); ++i) {
00242 int id = graph->id(keys[i]);
00243 allocator.construct(&(values[id]), Value());
00244 }
00245 }
00246
00248
00249 virtual void erase(const Key& key) {
00250 int id = graph->id(key);
00251 allocator.destroy(&(values[id]));
00252 }
00253
00254 virtual void erase(const std::vector<Key>& keys) {
00255 for (int i = 0; i < (int)keys.size(); ++i) {
00256 int id = graph->id(keys[i]);
00257 allocator.destroy(&(values[id]));
00258 }
00259 }
00260
00261 virtual void build() {
00262 allocate_memory();
00263 Item it;
00264 for (graph->first(it); it != INVALID; graph->next(it)) {
00265 int id = graph->id(it);;
00266 allocator.construct(&(values[id]), Value());
00267 }
00268 }
00269
00270 virtual void clear() {
00271 if (capacity != 0) {
00272 Item it;
00273 for (graph->first(it); it != INVALID; graph->next(it)) {
00274 int id = graph->id(it);
00275 allocator.destroy(&(values[id]));
00276 }
00277 allocator.deallocate(values, capacity);
00278 capacity = 0;
00279 }
00280 }
00281
00282 private:
00283
00284 void allocate_memory() {
00285 int max_id = graph->maxId(_Item());
00286 if (max_id == -1) {
00287 capacity = 0;
00288 values = 0;
00289 return;
00290 }
00291 capacity = 1;
00292 while (capacity <= max_id) {
00293 capacity <<= 1;
00294 }
00295 values = allocator.allocate(capacity);
00296 }
00297
00298 const Graph* graph;
00299 int capacity;
00300 Value* values;
00301 Allocator allocator;
00302
00303 };
00304
00305 }
00306
00307 #endif //LEMON_ARRAY_MAP_H