array_map.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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

Generated on Fri Feb 3 18:35:35 2006 for LEMON by  doxygen 1.4.6