Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

array_map.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_ARRAY_MAP_H
00018 #define LEMON_ARRAY_MAP_H
00019 
00020 #include <memory>
00021 
00026 
00027 namespace lemon {
00028 
00029 
00032         
00042   template <typename _Graph, 
00043             typename _Item,
00044             typename _ItemIt,
00045             typename _Value>
00046   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
00047 
00048   public:
00049                 
00051     typedef _Graph Graph;
00053     typedef _Item Key;
00054 
00055     typedef AlterationNotifier<_Item> Registry;
00056 
00057   private:
00059     typedef _ItemIt KeyIt;
00060 
00062     typedef typename Registry::ObserverBase Parent;
00063                 
00064     
00065   public:
00066 
00068     typedef _Value Value;
00070     typedef Value& Reference;
00072     typedef Value* Pointer;
00073 
00075     typedef const Value ConstValue;
00077     typedef const Value& ConstReference;
00079     typedef const Value* ConstPointer;
00080 
00081 
00082   private:
00083     typedef std::allocator<Value> Allocator;
00084 
00085 
00086   public:
00087 
00090     ArrayMap(const Graph& _g) : graph(&_g) {
00091       attach(_g.getNotifier(_Item()));
00092       allocate_memory();
00093       for (KeyIt it(*graph); it != INVALID; ++it) {
00094         int id = graph->id(it);;
00095         allocator.construct(&(values[id]), Value());
00096       }                                                         
00097     }
00098 
00100 
00102 
00103     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
00104       attach(_g.getNotifier(_Item()));
00105       allocate_memory();
00106       for (KeyIt it(*graph); it != INVALID; ++it) {
00107         int id = graph->id(it);;
00108         allocator.construct(&(values[id]), _v);
00109       }                                                         
00110     }
00111 
00114     ArrayMap(const ArrayMap& copy) {
00115       if (copy.attached()) {
00116         attach(*copy.getRegistry());
00117       }
00118       capacity = copy.capacity;
00119       if (capacity == 0) return;
00120       values = allocator.allocate(capacity);
00121       for (KeyIt it(*graph); it != INVALID; ++it) {
00122         int id = graph->id(it);;
00123         allocator.construct(&(values[id]), copy.values[id]);
00124       }
00125     }
00126 
00127     using Parent::attach;
00128     using Parent::detach;
00129     using Parent::attached;
00130 
00133     ArrayMap& operator=(const ArrayMap& copy) {
00134       if (&copy == this) return *this;
00135       
00136       if (graph != copy.graph) {
00137         if (attached()) {
00138           clear();
00139           detach();
00140         }
00141         if (copy.attached()) {
00142           attach(*copy.getRegistry());
00143         }
00144         capacity = copy.capacity;
00145         if (capacity == 0) return *this;
00146         values = allocator.allocate(capacity);      
00147       }
00148 
00149       for (KeyIt it(*graph); it != INVALID; ++it) {
00150         int id = graph->id(it);;
00151         allocator.construct(&(values[id]), copy.values[id]);
00152       }
00153 
00154       return *this;
00155     }
00156 
00159     virtual ~ArrayMap() {      
00160       if (attached()) {
00161         clear();
00162         detach();
00163       }
00164     }
00165         
00166         
00171     Reference operator[](const Key& key) {
00172       int id = graph->id(key);
00173       return values[id];
00174     } 
00175                 
00180     ConstReference operator[](const Key& key) const {
00181       int id = graph->id(key);
00182       return values[id];
00183     }
00184         
00188     void set(const Key& key, const Value& val) {
00189       (*this)[key] = val;
00190     }
00191                 
00194     void add(const Key& key) {
00195       int id = graph->id(key);
00196       if (id >= capacity) {
00197         int new_capacity = (capacity == 0 ? 1 : capacity);
00198         while (new_capacity <= id) {
00199           new_capacity <<= 1;
00200         }
00201         Value* new_values = allocator.allocate(new_capacity);
00202         for (KeyIt it(*graph); it != INVALID; ++it) {
00203           int jd = graph->id(it);;
00204           if (id != jd) {
00205             allocator.construct(&(new_values[jd]), values[jd]);
00206             allocator.destroy(&(values[jd]));
00207           }
00208         }
00209         if (capacity != 0) allocator.deallocate(values, capacity);
00210         values = new_values;
00211         capacity = new_capacity;
00212       }
00213       allocator.construct(&(values[id]), Value());
00214     }
00215                 
00218     void erase(const Key& key) {
00219       int id = graph->id(key);
00220       allocator.destroy(&(values[id]));
00221     }
00222 
00223     void build() {
00224       allocate_memory();
00225       for (KeyIt it(*graph); it != INVALID; ++it) {
00226         int id = graph->id(it);;
00227         allocator.construct(&(values[id]), Value());
00228       }                                                         
00229     }
00230 
00231     void clear() {      
00232       if (capacity != 0) {
00233         for (KeyIt it(*graph); it != INVALID; ++it) {
00234           int id = graph->id(it);;
00235           allocator.destroy(&(values[id]));
00236         }                                                               
00237         allocator.deallocate(values, capacity);
00238         capacity = 0;
00239       }
00240     }
00241 
00242 //     /// The stl compatible pair iterator of the map.
00243 //     typedef MapIterator<ArrayMap> Iterator;
00244 //     /// The stl compatible const pair iterator of the map.
00245 //     typedef MapConstIterator<ArrayMap> ConstIterator;
00246 
00247 //     /** Returns the begin iterator of the map.
00248 //      */
00249 //     Iterator begin() {
00250 //       return Iterator(*this, KeyIt(*MapBase::getGraph()));
00251 //     }
00252 
00253 //     /** Returns the end iterator of the map.
00254 //      */
00255 //     Iterator end() {
00256 //       return Iterator(*this, INVALID);
00257 //     }
00258 
00259 //     /** Returns the begin ConstIterator of the map.
00260 //      */
00261 //     ConstIterator begin() const {
00262 //       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
00263 //     }
00264 
00265 //     /** Returns the end const_iterator of the map.
00266 //      */
00267 //     ConstIterator end() const {
00268 //       return ConstIterator(*this, INVALID);
00269 //     }
00270 
00271 //     /// The KeySet of the Map.
00272 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;
00273 
00274 //     /// KeySet getter function.
00275 //     ConstKeySet keySet() const {
00276 //       return ConstKeySet(*this); 
00277 //     }
00278 
00279 //     /// The ConstValueSet of the Map.
00280 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;
00281 
00282 //     /// ConstValueSet getter function.
00283 //     ConstValueSet valueSet() const {
00284 //       return ConstValueSet(*this);
00285 //     }
00286 
00287 //     /// The ValueSet of the Map.
00288 //     typedef MapValueSet<ArrayMap> ValueSet;
00289 
00290 //     /// ValueSet getter function.
00291 //     ValueSet valueSet() {
00292 //       return ValueSet(*this);
00293 //     }
00294 
00295   private:
00296       
00297     void allocate_memory() {
00298       int max_id = graph->maxId(_Item());
00299       if (max_id == -1) {
00300         capacity = 0;
00301         values = 0;
00302         return;
00303       }
00304       capacity = 1;
00305       while (capacity <= max_id) {
00306         capacity <<= 1;
00307       }
00308       values = allocator.allocate(capacity);    
00309     }      
00310 
00311     const Graph* graph;
00312     int capacity;
00313     Value* values;
00314     Allocator allocator;
00315 
00316   public:
00317 //     // STL  compatibility typedefs.
00318 //     typedef Iterator iterator;
00319 //     typedef ConstIterator const_iterator;
00320 //     typedef typename Iterator::PairValue value_type;
00321 //     typedef typename Iterator::Key key_type;
00322 //     typedef typename Iterator::Value data_type;
00323 //     typedef typename Iterator::PairReference reference;
00324 //     typedef typename Iterator::PairPointer pointer;
00325 //     typedef typename ConstIterator::PairReference const_reference;
00326 //     typedef typename ConstIterator::PairPointer const_pointer;
00327 //     typedef int difference_type;             
00328   };            
00329 
00330   template <typename _Base> 
00331   class ArrayMappableGraphExtender : public _Base {
00332   public:
00333 
00334     typedef ArrayMappableGraphExtender<_Base> Graph;
00335     typedef _Base Parent;
00336 
00337     typedef typename Parent::Node Node;
00338     typedef typename Parent::NodeIt NodeIt;
00339     typedef typename Parent::NodeNotifier NodeObserverRegistry;
00340 
00341     typedef typename Parent::Edge Edge;
00342     typedef typename Parent::EdgeIt EdgeIt;
00343     typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
00344 
00345     
00346 
00347     template <typename _Value>
00348     class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
00349     public:
00350       typedef ArrayMappableGraphExtender<_Base> Graph;
00351 
00352       typedef typename Graph::Node Node;
00353       typedef typename Graph::NodeIt NodeIt;
00354 
00355       typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
00356 
00357       //typedef typename Parent::Graph Graph;
00358       typedef typename Parent::Value Value;
00359 
00360       NodeMap(const Graph& g) 
00361         : Parent(g) {}
00362       NodeMap(const Graph& g, const Value& v) 
00363         : Parent(g, v) {}
00364 
00365     };
00366 
00367     template <typename _Value>
00368     class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
00369     public:
00370       typedef ArrayMappableGraphExtender<_Base> Graph;
00371 
00372       typedef typename Graph::Edge Edge;
00373       typedef typename Graph::EdgeIt EdgeIt;
00374 
00375       typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
00376 
00377       //typedef typename Parent::Graph Graph;
00378       typedef typename Parent::Value Value;
00379 
00380       EdgeMap(const Graph& g) 
00381         : Parent(g) {}
00382       EdgeMap(const Graph& g, const Value& v) 
00383         : Parent(g, v) {}
00384 
00385     };
00386     
00387   };
00388 
00390 
00391 }
00392 
00393 #endif //LEMON_ARRAY_MAP_H

Generated on Sat Mar 19 10:58:39 2005 for LEMON by  doxygen 1.4.1