lemon/bits/array_map.h
author deba
Fri, 04 Nov 2005 19:19:52 +0000
changeset 1778 4ba7965386fb
parent 1703 eb90e3d6bddc
child 1810 474d093466a5
permissions -rw-r--r--
Some just writeable bool maps.
     1 /* -*- C++ -*-
     2  * lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, 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 #include <lemon/bits/map_iterator.h>
    22 #include <lemon/concept_check.h>
    23 #include <lemon/concept/maps.h>
    24 
    25 /// \ingroup graphmapfactory
    26 /// \file
    27 /// \brief Graph maps that construct and destruct
    28 /// their elements dynamically.
    29 
    30 namespace lemon {
    31 
    32   /// \ingroup graphmapfactory
    33   ///
    34   /// \brief Graph map based on the array storage.
    35   ///
    36   /// The ArrayMap template class is graph map structure what
    37   /// automatically updates the map when a key is added to or erased from
    38   /// the map. This map uses the allocators to implement 
    39   /// the container functionality.
    40   ///
    41   /// The template parameter is the AlterationNotifier that the maps
    42   /// will belong to and the Value.
    43 
    44   template <typename _Graph, 
    45 	    typename _Item,
    46 	    typename _Value>
    47   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
    48 
    49     typedef _Item Item;
    50   public:
    51     /// The graph type of the maps. 
    52     typedef _Graph Graph;
    53     /// The reference map tag.
    54     typedef True ReferenceMapTag;
    55 
    56     /// The key type of the maps.
    57     typedef _Item Key;
    58     /// The value type of the map.
    59     typedef _Value Value;
    60     /// The const reference type of the map.
    61     typedef const _Value& ConstReference;
    62     /// The reference type of the map.
    63     typedef _Value& Reference;
    64 
    65     typedef const Value ConstValue;
    66     typedef Value* Pointer;
    67     typedef const Value* ConstPointer;
    68 
    69     typedef AlterationNotifier<_Item> Registry;
    70 
    71     /// The MapBase of the Map which imlements the core regisitry function.
    72     typedef typename Registry::ObserverBase Parent;
    73 		
    74 
    75 
    76   private:
    77     typedef std::allocator<Value> Allocator;
    78 
    79 
    80   public:
    81 
    82     /// \brief Graph initialized map constructor.
    83     ///
    84     /// Graph initialized map constructor.
    85     ArrayMap(const Graph& _g) : graph(&_g) {
    86       Item it;
    87       attach(_g.getNotifier(Item()));
    88       allocate_memory();
    89       for (graph->first(it); it != INVALID; graph->next(it)) {
    90 	int id = graph->id(it);;
    91 	allocator.construct(&(values[id]), Value());
    92       }								
    93     }
    94 
    95     /// \brief Constructor to use default value to initialize the map. 
    96     ///
    97     /// It constructs a map and initialize all of the the map. 
    98     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
    99       Item it;
   100       attach(_g.getNotifier(_Item()));
   101       allocate_memory();
   102       for (graph->first(it); it != INVALID; graph->next(it)) {
   103 	int id = graph->id(it);;
   104 	allocator.construct(&(values[id]), _v);
   105       }								
   106     }
   107 
   108     /// \brief Constructor to copy a map of the same map type.
   109     ///
   110     /// Constructor to copy a map of the same map type.     
   111     ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
   112       if (copy.attached()) {
   113 	attach(*copy.getRegistry());
   114       }
   115       capacity = copy.capacity;
   116       if (capacity == 0) return;
   117       values = allocator.allocate(capacity);
   118       Item it;
   119       for (graph->first(it); it != INVALID; graph->next(it)) {
   120 	int id = graph->id(it);;
   121 	allocator.construct(&(values[id]), copy.values[id]);
   122       }
   123     }
   124 
   125     /// \brief The destructor of the map.
   126     ///     
   127     /// The destructor of the map.
   128     virtual ~ArrayMap() {      
   129       if (attached()) {
   130 	clear();
   131 	detach();
   132       }
   133     }
   134 		
   135   private:
   136 
   137     ArrayMap& operator=(const ArrayMap&);
   138 
   139   protected:
   140 
   141     using Parent::attach;
   142     using Parent::detach;
   143     using Parent::attached;
   144 
   145     const Graph* getGraph() {
   146       return graph;
   147     }
   148 
   149 
   150   public:
   151 
   152     /// \brief The subscript operator. 
   153     ///
   154     /// The subscript operator. The map can be subscripted by the
   155     /// actual keys of the graph. 
   156     Value& operator[](const Key& key) {
   157       int id = graph->id(key);
   158       return values[id];
   159     } 
   160 		
   161     /// \brief The const subscript operator.
   162     ///
   163     /// The const subscript operator. The map can be subscripted by the
   164     /// actual keys of the graph. 
   165     const Value& operator[](const Key& key) const {
   166       int id = graph->id(key);
   167       return values[id];
   168     }
   169 
   170     /// \brief Setter function of the map.
   171     ///	
   172     /// Setter function of the map. Equivalent with map[key] = val.
   173     /// This is a compatibility feature with the not dereferable maps.
   174     void set(const Key& key, const Value& val) {
   175       (*this)[key] = val;
   176     }
   177 
   178   protected:
   179 
   180     /// Add a new key to the map. It called by the map registry.
   181          
   182     virtual void add(const Key& key) {
   183       int id = graph->id(key);
   184       if (id >= capacity) {
   185 	int new_capacity = (capacity == 0 ? 1 : capacity);
   186 	while (new_capacity <= id) {
   187 	  new_capacity <<= 1;
   188 	}
   189 	Value* new_values = allocator.allocate(new_capacity);
   190 	Item it;
   191 	for (graph->first(it); it != INVALID; graph->next(it)) {
   192 	  int jd = graph->id(it);;
   193 	  if (id != jd) {
   194 	    allocator.construct(&(new_values[jd]), values[jd]);
   195 	    allocator.destroy(&(values[jd]));
   196 	  }
   197 	}
   198 	if (capacity != 0) allocator.deallocate(values, capacity);
   199 	values = new_values;
   200 	capacity = new_capacity;
   201       }
   202       allocator.construct(&(values[id]), Value());
   203     }
   204 
   205     virtual void add(const std::vector<Key>& keys) {
   206       int max_id = -1;
   207       for (int i = 0; i < (int)keys.size(); ++i) {
   208 	int id = graph->id(keys[i]);
   209 	if (id > max_id) {
   210 	  max_id = id;
   211 	}
   212       }
   213       if (max_id >= capacity) {
   214 	int new_capacity = (capacity == 0 ? 1 : capacity);
   215 	while (new_capacity <= max_id) {
   216 	  new_capacity <<= 1;
   217 	}
   218 	Value* new_values = allocator.allocate(new_capacity);
   219 	Item it;
   220 	for (graph->first(it); it != INVALID; graph->next(it)) {
   221 	  int id = graph->id(it);
   222 	  bool found = false;
   223 	  for (int i = 0; i < (int)keys.size(); ++i) {
   224 	    int jd = graph->id(keys[i]);
   225 	    if (id == jd) {
   226 	      found = true;
   227 	      break;
   228 	    }
   229 	  }
   230 	  if (found) continue;
   231 	  allocator.construct(&(new_values[id]), values[id]);
   232 	  allocator.destroy(&(values[id]));
   233 	}
   234 	if (capacity != 0) allocator.deallocate(values, capacity);
   235 	values = new_values;
   236 	capacity = new_capacity;
   237       }
   238       for (int i = 0; i < (int)keys.size(); ++i) {
   239 	int id = graph->id(keys[i]);
   240 	allocator.construct(&(values[id]), Value());
   241       }
   242     }
   243 		
   244     /// Erase a key from the map. It called by the map registry.
   245      
   246     virtual void erase(const Key& key) {
   247       int id = graph->id(key);
   248       allocator.destroy(&(values[id]));
   249     }
   250 
   251     virtual void erase(const std::vector<Key>& keys) {
   252       for (int i = 0; i < (int)keys.size(); ++i) {
   253 	int id = graph->id(keys[i]);
   254 	allocator.destroy(&(values[id]));
   255       }
   256     }
   257 
   258     virtual void build() {
   259       allocate_memory();
   260       Item it;
   261       for (graph->first(it); it != INVALID; graph->next(it)) {
   262 	int id = graph->id(it);;
   263 	allocator.construct(&(values[id]), Value());
   264       }								
   265     }
   266 
   267     virtual void clear() {	
   268       if (capacity != 0) {
   269 	Item it;
   270 	for (graph->first(it); it != INVALID; graph->next(it)) {
   271 	  int id = graph->id(it);
   272 	  allocator.destroy(&(values[id]));
   273 	}								
   274 	allocator.deallocate(values, capacity);
   275 	capacity = 0;
   276       }
   277     }
   278 
   279   private:
   280       
   281     void allocate_memory() {
   282       int max_id = graph->maxId(_Item());
   283       if (max_id == -1) {
   284 	capacity = 0;
   285 	values = 0;
   286 	return;
   287       }
   288       capacity = 1;
   289       while (capacity <= max_id) {
   290 	capacity <<= 1;
   291       }
   292       values = allocator.allocate(capacity);	
   293     }      
   294 
   295     const Graph* graph;
   296     int capacity;
   297     Value* values;
   298     Allocator allocator;
   299 
   300   };		
   301 
   302 }
   303 
   304 #endif //LEMON_ARRAY_MAP_H