lemon-0.x: src/lemon/array_map.h@81b4731f8a6b

     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  */

    17 #ifndef LEMON_ARRAY_MAP_H

    18 #define LEMON_ARRAY_MAP_H

    20 #include <memory>

    22 ///\ingroup graphmaps

    23 ///\file

    24 ///\brief Graph maps that construates and destruates

    25 ///their elements dynamically.

    27 namespace lemon {

    30   /// \addtogroup graphmaps

    31   /// @{

    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    */

    42   template <typename _Graph,

    43 	    typename _Item,

    44 	    typename _ItemIt,

    45 	    typename _Value>

    46   class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {

    48   public:

    50     /// The graph type of the maps.

    51     typedef _Graph Graph;

    52     /// The key type of the maps.

    53     typedef _Item Key;

    55     typedef AlterationNotifier<_Item> Registry;

    57   private:

    58     /// The iterator to iterate on the keys.

    59     typedef _ItemIt KeyIt;

    61     /// The MapBase of the Map which imlements the core regisitry function.

    62     typedef typename Registry::ObserverBase Parent;

    65   public:

    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;

    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;

    82   private:

    83     typedef std::allocator<Value> Allocator;

    86   public:

    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     }

    99     /// Constructor to use default value to initialize the map.

   101     /// It constrates a map and initialize all of the the map.

   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     }

   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     }

   127     using Parent::attach;

   128     using Parent::detach;

   129     using Parent::attached;

   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;

   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       }

   149       for (KeyIt it(*graph); it != INVALID; ++it) {

   150 	int id = graph->id(it);;

   151 	allocator.construct(&(values[id]), copy.values[id]);

   152       }

   154       return *this;

   155     }

   157     /** The destructor of the map.

   158      */

   159     virtual ~ArrayMap() {

   160       if (attached()) {

   161 	clear();

   162 	detach();

   163       }

   164     }

   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     }

   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     }

   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     }

   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     }

   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     }

   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     }

   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     }

   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;

   247 //     /** Returns the begin iterator of the map.

   248 //      */

   249 //     Iterator begin() {

   250 //       return Iterator(*this, KeyIt(*MapBase::getGraph()));

   251 //     }

   253 //     /** Returns the end iterator of the map.

   254 //      */

   255 //     Iterator end() {

   256 //       return Iterator(*this, INVALID);

   257 //     }

   259 //     /** Returns the begin ConstIterator of the map.

   260 //      */

   261 //     ConstIterator begin() const {

   262 //       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));

   263 //     }

   265 //     /** Returns the end const_iterator of the map.

   266 //      */

   267 //     ConstIterator end() const {

   268 //       return ConstIterator(*this, INVALID);

   269 //     }

   271 //     /// The KeySet of the Map.

   272 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;

   274 //     /// KeySet getter function.

   275 //     ConstKeySet keySet() const {

   276 //       return ConstKeySet(*this);

   277 //     }

   279 //     /// The ConstValueSet of the Map.

   280 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;

   282 //     /// ConstValueSet getter function.

   283 //     ConstValueSet valueSet() const {

   284 //       return ConstValueSet(*this);

   285 //     }

   287 //     /// The ValueSet of the Map.

   288 //     typedef MapValueSet<ArrayMap> ValueSet;

   290 //     /// ValueSet getter function.

   291 //     ValueSet valueSet() {

   292 //       return ValueSet(*this);

   293 //     }

   295   private:

   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     }

   311     const Graph* graph;

   312     int capacity;

   313     Value* values;

   314     Allocator allocator;

   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   };

   330   template <typename _Base>

   331   class ArrayMappableGraphExtender : public _Base {

   332   public:

   334     typedef ArrayMappableGraphExtender<_Base> Graph;

   335     typedef _Base Parent;

   337     typedef typename Parent::Node Node;

   338     typedef typename Parent::NodeIt NodeIt;

   339     typedef typename Parent::NodeNotifier NodeObserverRegistry;

   341     typedef typename Parent::Edge Edge;

   342     typedef typename Parent::EdgeIt EdgeIt;

   343     typedef typename Parent::EdgeNotifier EdgeObserverRegistry;

   347     template <typename _Value>

   348     class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {

   349     public:

   350       typedef ArrayMappableGraphExtender<_Base> Graph;

   352       typedef typename Graph::Node Node;

   353       typedef typename Graph::NodeIt NodeIt;

   355       typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;

   357       //typedef typename Parent::Graph Graph;

   358       typedef typename Parent::Value Value;

   360       NodeMap(const Graph& g)

   361 	: Parent(g) {}

   362       NodeMap(const Graph& g, const Value& v)

   363 	: Parent(g, v) {}

   365     };

   367     template <typename _Value>

   368     class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {

   369     public:

   370       typedef ArrayMappableGraphExtender<_Base> Graph;

   372       typedef typename Graph::Edge Edge;

   373       typedef typename Graph::EdgeIt EdgeIt;

   375       typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;

   377       //typedef typename Parent::Graph Graph;

   378       typedef typename Parent::Value Value;

   380       EdgeMap(const Graph& g)

   381 	: Parent(g) {}

   382       EdgeMap(const Graph& g, const Value& v)

   383 	: Parent(g, v) {}

   385     };

   387   };

   389 /// @}

   391 }

   393 #endif //LEMON_ARRAY_MAP_H

author	alpar
	Wed, 16 Mar 2005 07:50:20 +0000
changeset 1215	81b4731f8a6b
parent 1039	bd01c5a3f989
child 1267	a93f94dbe3d3
permissions	-rw-r--r--