src/lemon/array_map.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1039 bd01c5a3f989
child 1267 a93f94dbe3d3
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
     1 /* -*- C++ -*-
     2  * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_ARRAY_MAP_H
    18 #define LEMON_ARRAY_MAP_H
    19 
    20 #include <memory>
    21 
    22 ///\ingroup graphmaps
    23 ///\file
    24 ///\brief Graph maps that construates and destruates
    25 ///their elements dynamically.
    26 
    27 namespace lemon {
    28 
    29 
    30   /// \addtogroup graphmaps
    31   /// @{
    32 	
    33   /** The ArrayMap template class is graph map structure what
    34    *  automatically updates the map when a key is added to or erased from
    35    *  the map. This map factory uses the allocators to implement 
    36    *  the container functionality.
    37    *
    38    *  The template parameter is the MapRegistry that the maps
    39    *  will belong to and the Value.
    40    */
    41 
    42   template <typename _Graph, 
    43 	    typename _Item,
    44 	    typename _ItemIt,
    45 	    typename _Value>
    46   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
    47 
    48   public:
    49 		
    50     /// The graph type of the maps. 
    51     typedef _Graph Graph;
    52     /// The key type of the maps.
    53     typedef _Item Key;
    54 
    55     typedef AlterationNotifier<_Item> Registry;
    56 
    57   private:
    58     /// The iterator to iterate on the keys.
    59     typedef _ItemIt KeyIt;
    60 
    61     /// The MapBase of the Map which imlements the core regisitry function.
    62     typedef typename Registry::ObserverBase Parent;
    63 		
    64     
    65   public:
    66 
    67     /// The value type of the map.
    68     typedef _Value Value;
    69     /// The reference type of the map;
    70     typedef Value& Reference;
    71     /// The pointer type of the map;
    72     typedef Value* Pointer;
    73 
    74     /// The const value type of the map.
    75     typedef const Value ConstValue;
    76     /// The const reference type of the map;
    77     typedef const Value& ConstReference;
    78     /// The pointer type of the map;
    79     typedef const Value* ConstPointer;
    80 
    81 
    82   private:
    83     typedef std::allocator<Value> Allocator;
    84 
    85 
    86   public:
    87 
    88     /** Graph and Registry initialized map constructor.
    89      */
    90     ArrayMap(const Graph& _g) : graph(&_g) {
    91       attach(_g.getNotifier(_Item()));
    92       allocate_memory();
    93       for (KeyIt it(*graph); it != INVALID; ++it) {
    94 	int id = graph->id(it);;
    95 	allocator.construct(&(values[id]), Value());
    96       }								
    97     }
    98 
    99     /// Constructor to use default value to initialize the map. 
   100 
   101     /// It constrates a map and initialize all of the the map. 
   102 
   103     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
   104       attach(_g.getNotifier(_Item()));
   105       allocate_memory();
   106       for (KeyIt it(*graph); it != INVALID; ++it) {
   107 	int id = graph->id(it);;
   108 	allocator.construct(&(values[id]), _v);
   109       }								
   110     }
   111 
   112     /** Constructor to copy a map of the same map type.
   113      */
   114     ArrayMap(const ArrayMap& copy) {
   115       if (copy.attached()) {
   116 	attach(*copy.getRegistry());
   117       }
   118       capacity = copy.capacity;
   119       if (capacity == 0) return;
   120       values = allocator.allocate(capacity);
   121       for (KeyIt it(*graph); it != INVALID; ++it) {
   122 	int id = graph->id(it);;
   123 	allocator.construct(&(values[id]), copy.values[id]);
   124       }
   125     }
   126 
   127     using Parent::attach;
   128     using Parent::detach;
   129     using Parent::attached;
   130 
   131     /** Assign operator to copy a map of the same map type.
   132      */
   133     ArrayMap& operator=(const ArrayMap& copy) {
   134       if (&copy == this) return *this;
   135       
   136       if (graph != copy.graph) {
   137 	if (attached()) {
   138 	  clear();
   139 	  detach();
   140 	}
   141 	if (copy.attached()) {
   142 	  attach(*copy.getRegistry());
   143 	}
   144 	capacity = copy.capacity;
   145 	if (capacity == 0) return *this;
   146 	values = allocator.allocate(capacity);      
   147       }
   148 
   149       for (KeyIt it(*graph); it != INVALID; ++it) {
   150 	int id = graph->id(it);;
   151 	allocator.construct(&(values[id]), copy.values[id]);
   152       }
   153 
   154       return *this;
   155     }
   156 
   157     /** The destructor of the map.
   158      */
   159     virtual ~ArrayMap() {      
   160       if (attached()) {
   161 	clear();
   162 	detach();
   163       }
   164     }
   165 	
   166 	
   167     /**
   168      * The subscript operator. The map can be subscripted by the
   169      * actual keys of the graph. 
   170      */
   171     Reference operator[](const Key& key) {
   172       int id = graph->id(key);
   173       return values[id];
   174     } 
   175 		
   176     /**
   177      * The const subscript operator. The map can be subscripted by the
   178      * actual keys of the graph. 
   179      */
   180     ConstReference operator[](const Key& key) const {
   181       int id = graph->id(key);
   182       return values[id];
   183     }
   184 	
   185     /** Setter function of the map. Equivalent with map[key] = val.
   186      *  This is a compatibility feature with the not dereferable maps.
   187      */
   188     void set(const Key& key, const Value& val) {
   189       (*this)[key] = val;
   190     }
   191 		
   192     /** Add a new key to the map. It called by the map registry.
   193      */
   194     void add(const Key& key) {
   195       int id = graph->id(key);
   196       if (id >= capacity) {
   197 	int new_capacity = (capacity == 0 ? 1 : capacity);
   198 	while (new_capacity <= id) {
   199 	  new_capacity <<= 1;
   200 	}
   201 	Value* new_values = allocator.allocate(new_capacity);
   202 	for (KeyIt it(*graph); it != INVALID; ++it) {
   203 	  int jd = graph->id(it);;
   204 	  if (id != jd) {
   205 	    allocator.construct(&(new_values[jd]), values[jd]);
   206 	    allocator.destroy(&(values[jd]));
   207 	  }
   208 	}
   209 	if (capacity != 0) allocator.deallocate(values, capacity);
   210 	values = new_values;
   211 	capacity = new_capacity;
   212       }
   213       allocator.construct(&(values[id]), Value());
   214     }
   215 		
   216     /** Erase a key from the map. It called by the map registry.
   217      */
   218     void erase(const Key& key) {
   219       int id = graph->id(key);
   220       allocator.destroy(&(values[id]));
   221     }
   222 
   223     void build() {
   224       allocate_memory();
   225       for (KeyIt it(*graph); it != INVALID; ++it) {
   226 	int id = graph->id(it);;
   227 	allocator.construct(&(values[id]), Value());
   228       }								
   229     }
   230 
   231     void clear() {	
   232       if (capacity != 0) {
   233 	for (KeyIt it(*graph); it != INVALID; ++it) {
   234 	  int id = graph->id(it);;
   235 	  allocator.destroy(&(values[id]));
   236 	}								
   237 	allocator.deallocate(values, capacity);
   238 	capacity = 0;
   239       }
   240     }
   241 
   242 //     /// The stl compatible pair iterator of the map.
   243 //     typedef MapIterator<ArrayMap> Iterator;
   244 //     /// The stl compatible const pair iterator of the map.
   245 //     typedef MapConstIterator<ArrayMap> ConstIterator;
   246 
   247 //     /** Returns the begin iterator of the map.
   248 //      */
   249 //     Iterator begin() {
   250 //       return Iterator(*this, KeyIt(*MapBase::getGraph()));
   251 //     }
   252 
   253 //     /** Returns the end iterator of the map.
   254 //      */
   255 //     Iterator end() {
   256 //       return Iterator(*this, INVALID);
   257 //     }
   258 
   259 //     /** Returns the begin ConstIterator of the map.
   260 //      */
   261 //     ConstIterator begin() const {
   262 //       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
   263 //     }
   264 
   265 //     /** Returns the end const_iterator of the map.
   266 //      */
   267 //     ConstIterator end() const {
   268 //       return ConstIterator(*this, INVALID);
   269 //     }
   270 
   271 //     /// The KeySet of the Map.
   272 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;
   273 
   274 //     /// KeySet getter function.
   275 //     ConstKeySet keySet() const {
   276 //       return ConstKeySet(*this); 
   277 //     }
   278 
   279 //     /// The ConstValueSet of the Map.
   280 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;
   281 
   282 //     /// ConstValueSet getter function.
   283 //     ConstValueSet valueSet() const {
   284 //       return ConstValueSet(*this);
   285 //     }
   286 
   287 //     /// The ValueSet of the Map.
   288 //     typedef MapValueSet<ArrayMap> ValueSet;
   289 
   290 //     /// ValueSet getter function.
   291 //     ValueSet valueSet() {
   292 //       return ValueSet(*this);
   293 //     }
   294 
   295   private:
   296       
   297     void allocate_memory() {
   298       int max_id = graph->maxId(_Item());
   299       if (max_id == -1) {
   300 	capacity = 0;
   301 	values = 0;
   302 	return;
   303       }
   304       capacity = 1;
   305       while (capacity <= max_id) {
   306 	capacity <<= 1;
   307       }
   308       values = allocator.allocate(capacity);	
   309     }      
   310 
   311     const Graph* graph;
   312     int capacity;
   313     Value* values;
   314     Allocator allocator;
   315 
   316   public:
   317 //     // STL  compatibility typedefs.
   318 //     typedef Iterator iterator;
   319 //     typedef ConstIterator const_iterator;
   320 //     typedef typename Iterator::PairValue value_type;
   321 //     typedef typename Iterator::Key key_type;
   322 //     typedef typename Iterator::Value data_type;
   323 //     typedef typename Iterator::PairReference reference;
   324 //     typedef typename Iterator::PairPointer pointer;
   325 //     typedef typename ConstIterator::PairReference const_reference;
   326 //     typedef typename ConstIterator::PairPointer const_pointer;
   327 //     typedef int difference_type;		
   328   };		
   329 
   330   template <typename _Base> 
   331   class ArrayMappableGraphExtender : public _Base {
   332   public:
   333 
   334     typedef ArrayMappableGraphExtender<_Base> Graph;
   335     typedef _Base Parent;
   336 
   337     typedef typename Parent::Node Node;
   338     typedef typename Parent::NodeIt NodeIt;
   339     typedef typename Parent::NodeNotifier NodeObserverRegistry;
   340 
   341     typedef typename Parent::Edge Edge;
   342     typedef typename Parent::EdgeIt EdgeIt;
   343     typedef typename Parent::EdgeNotifier EdgeObserverRegistry;
   344 
   345     
   346 
   347     template <typename _Value>
   348     class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
   349     public:
   350       typedef ArrayMappableGraphExtender<_Base> Graph;
   351 
   352       typedef typename Graph::Node Node;
   353       typedef typename Graph::NodeIt NodeIt;
   354 
   355       typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
   356 
   357       //typedef typename Parent::Graph Graph;
   358       typedef typename Parent::Value Value;
   359 
   360       NodeMap(const Graph& g) 
   361 	: Parent(g) {}
   362       NodeMap(const Graph& g, const Value& v) 
   363 	: Parent(g, v) {}
   364 
   365     };
   366 
   367     template <typename _Value>
   368     class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
   369     public:
   370       typedef ArrayMappableGraphExtender<_Base> Graph;
   371 
   372       typedef typename Graph::Edge Edge;
   373       typedef typename Graph::EdgeIt EdgeIt;
   374 
   375       typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
   376 
   377       //typedef typename Parent::Graph Graph;
   378       typedef typename Parent::Value Value;
   379 
   380       EdgeMap(const Graph& g) 
   381 	: Parent(g) {}
   382       EdgeMap(const Graph& g, const Value& v) 
   383 	: Parent(g, v) {}
   384 
   385     };
   386     
   387   };
   388 
   389 /// @}
   390 
   391 }
   392 
   393 #endif //LEMON_ARRAY_MAP_H