lemon-0.x: src/lemon/array_map.h@6a6f3ac07b20

     1 /* -*- C++ -*-

     2  * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2004 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 #include <lemon/map_iterator.h>

    24 ///\ingroup graphmaps

    25 ///\file

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

    27 ///their elements dynamically.

    29 namespace lemon {

    32   /// \addtogroup graphmaps

    33   /// @{

    35   /** The ArrayMap template class is graph map structure what

    36    *  automatically updates the map when a key is added to or erased from

    37    *  the map. This map factory uses the allocators to implement

    38    *  the container functionality.

    39    *

    40    *  The template parameter is the MapRegistry that the maps

    41    *  will belong to and the ValueType.

    42    */

    44   template <typename _Graph,

    45 	    typename _Item,

    46 	    typename _ItemIt,

    47 	    typename _IdMap,

    48 	    typename _Value>

    49   class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {

    51   public:

    53     /// The graph type of the maps.

    54     typedef _Graph Graph;

    55     /// The key type of the maps.

    56     typedef _Item KeyType;

    58     typedef AlterationObserverRegistry<_Item> Registry;

    60   private:

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

    62     typedef _ItemIt KeyIt;

    64     typedef _IdMap IdMap;

    66     typedef _Value Value;

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

    69     typedef typename Registry::ObserverBase Parent;

    72   public:

    74     /// The value type of the map.

    75     typedef Value ValueType;

    76     /// The reference type of the map;

    77     typedef Value& ReferenceType;

    78     /// The pointer type of the map;

    79     typedef Value* PointerType;

    81     /// The const value type of the map.

    82     typedef const Value ConstValueType;

    83     /// The const reference type of the map;

    84     typedef const Value& ConstReferenceType;

    85     /// The pointer type of the map;

    86     typedef const Value* ConstPointerType;

    89   private:

    90     typedef std::allocator<Value> Allocator;

    93   public:

    95     /** Graph and Registry initialized map constructor.

    96      */

    97     ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {

    98       attach(_r);

    99       allocate_memory();

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

   101 	int id = IdMap(*graph)[it];

   102 	allocator.construct(&(values[id]), Value());

   103       }

   104     }

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

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

   110     ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {

   111       attach(_r);

   112       allocate_memory();

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

   114 	int id = IdMap(*graph)[it];

   115 	allocator.construct(&(values[id]), _v);

   116       }

   117     }

   119     /** Constructor to copy a map of the same map type.

   120      */

   121     ArrayMap(const ArrayMap& copy) {

   122       if (copy.attached()) {

   123 	attach(*copy.getRegistry());

   124       }

   125       capacity = copy.capacity;

   126       if (capacity == 0) return;

   127       values = allocator.allocate(capacity);

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

   129 	int id = IdMap(*graph)[it];

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

   131       }

   132     }

   134     /** Assign operator to copy a map of the same map type.

   135      */

   136     ArrayMap& operator=(const ArrayMap& copy) {

   137       if (&copy == this) return *this;

   139       if (graph != copy.graph) {

   140 	if (attached()) {

   141 	  clear();

   142 	  detach();

   143 	}

   144 	if (copy.attached()) {

   145 	  attach(*copy.getRegistry());

   146 	}

   147 	capacity = copy.capacity;

   148 	if (capacity == 0) return *this;

   149 	values = allocator.allocate(capacity);

   150       }

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

   153 	int id = IdMap(*graph)[it];

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

   155       }

   157       return *this;

   158     }

   160     /** The destructor of the map.

   161      */

   162     virtual ~ArrayMap() {

   163       if (attached()) {

   164 	clear();

   165 	detach();

   166       }

   167     }

   170     /**

   171      * The subscript operator. The map can be subscripted by the

   172      * actual keys of the graph.

   173      */

   174     ReferenceType operator[](const KeyType& key) {

   175       int id = IdMap(*graph)[key];

   176       return values[id];

   177     }

   179     /**

   180      * The const subscript operator. The map can be subscripted by the

   181      * actual keys of the graph.

   182      */

   183     ConstReferenceType operator[](const KeyType& key) const {

   184       int id = IdMap(*graph)[key];

   185       return values[id];

   186     }

   188     /** Setter function of the map. Equivalent with map[key] = val.

   189      *  This is a compatibility feature with the not dereferable maps.

   190      */

   191     void set(const KeyType& key, const ValueType& val) {

   192       (*this)[key] = val;

   193     }

   195     /** Add a new key to the map. It called by the map registry.

   196      */

   197     void add(const KeyType& key) {

   198       int id = IdMap(*graph)[key];

   199       if (id >= capacity) {

   200 	int new_capacity = (capacity == 0 ? 1 : capacity);

   201 	while (new_capacity <= id) {

   202 	  new_capacity <<= 1;

   203 	}

   204 	Value* new_values = allocator.allocate(new_capacity);

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

   206 	  int jd = IdMap(*graph)[it];

   207 	  if (id != jd) {

   208 	    allocator.construct(&(new_values[jd]), values[jd]);

   209 	    allocator.destroy(&(values[jd]));

   210 	  }

   211 	}

   212 	if (capacity != 0) allocator.deallocate(values, capacity);

   213 	values = new_values;

   214 	capacity = new_capacity;

   215       }

   216       allocator.construct(&(values[id]), Value());

   217     }

   219     /** Erase a key from the map. It called by the map registry.

   220      */

   221     void erase(const KeyType& key) {

   222       int id = IdMap(*graph)[key];

   223       allocator.destroy(&(values[id]));

   224     }

   226     void build() {

   227       allocate_memory();

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

   229 	int id = IdMap(*graph)[it];

   230 	allocator.construct(&(values[id]), Value());

   231       }

   232     }

   234     void clear() {

   235       if (capacity != 0) {

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

   237 	  int id = IdMap(*graph)[it];

   238 	  allocator.destroy(&(values[id]));

   239 	}

   240 	allocator.deallocate(values, capacity);

   241 	capacity = 0;

   242       }

   243     }

   245 //     /// The stl compatible pair iterator of the map.

   246 //     typedef MapIterator<ArrayMap> Iterator;

   247 //     /// The stl compatible const pair iterator of the map.

   248 //     typedef MapConstIterator<ArrayMap> ConstIterator;

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

   251 //      */

   252 //     Iterator begin() {

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

   254 //     }

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

   257 //      */

   258 //     Iterator end() {

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

   260 //     }

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

   263 //      */

   264 //     ConstIterator begin() const {

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

   266 //     }

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

   269 //      */

   270 //     ConstIterator end() const {

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

   272 //     }

   274 //     /// The KeySet of the Map.

   275 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;

   277 //     /// KeySet getter function.

   278 //     ConstKeySet keySet() const {

   279 //       return ConstKeySet(*this);

   280 //     }

   282 //     /// The ConstValueSet of the Map.

   283 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;

   285 //     /// ConstValueSet getter function.

   286 //     ConstValueSet valueSet() const {

   287 //       return ConstValueSet(*this);

   288 //     }

   290 //     /// The ValueSet of the Map.

   291 //     typedef MapValueSet<ArrayMap> ValueSet;

   293 //     /// ValueSet getter function.

   294 //     ValueSet valueSet() {

   295 //       return ValueSet(*this);

   296 //     }

   298   private:

   300     void allocate_memory() {

   301       int max_id = IdMap(*graph).maxId();

   302       if (max_id == -1) {

   303 	capacity = 0;

   304 	values = 0;

   305 	return;

   306       }

   307       capacity = 1;

   308       while (capacity <= max_id) {

   309 	capacity <<= 1;

   310       }

   311       values = allocator.allocate(capacity);

   312     }

   314     const Graph* graph;

   315     int capacity;

   316     Value* values;

   317     Allocator allocator;

   319   public:

   320 //     // STL  compatibility typedefs.

   321 //     typedef Iterator iterator;

   322 //     typedef ConstIterator const_iterator;

   323 //     typedef typename Iterator::PairValueType value_type;

   324 //     typedef typename Iterator::KeyType key_type;

   325 //     typedef typename Iterator::ValueType data_type;

   326 //     typedef typename Iterator::PairReferenceType reference;

   327 //     typedef typename Iterator::PairPointerType pointer;

   328 //     typedef typename ConstIterator::PairReferenceType const_reference;

   329 //     typedef typename ConstIterator::PairPointerType const_pointer;

   330 //     typedef int difference_type;

   331   };

   333   template <typename _Base>

   334   class ArrayMappableGraphExtender : public _Base {

   335   public:

   337     typedef ArrayMappableGraphExtender<_Base> Graph;

   338     typedef _Base Parent;

   340     typedef typename Parent::Node Node;

   341     typedef typename Parent::NodeIt NodeIt;

   342     typedef typename Parent::NodeIdMap NodeIdMap;

   343     typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;

   345     typedef typename Parent::Edge Edge;

   346     typedef typename Parent::EdgeIt EdgeIt;

   347     typedef typename Parent::EdgeIdMap EdgeIdMap;

   348     typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;

   352     template <typename _Value>

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

   354     public:

   355       typedef ArrayMappableGraphExtender<_Base> Graph;

   357       typedef typename Graph::Node Node;

   358       typedef typename Graph::NodeIt NodeIt;

   359       typedef typename Graph::NodeIdMap NodeIdMap;

   361       typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;

   363       typedef typename Parent::Graph Graph;

   364       typedef typename Parent::Value Value;

   366       NodeMap(const Graph& g)

   367 	: Parent(g, g.getNodeObserverRegistry()) {}

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

   369 	: Parent(g, g.getNodeObserverRegistry(), v) {}

   371     };

   373     template <typename _Value>

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

   375     public:

   376       typedef ArrayMappableGraphExtender<_Base> Graph;

   378       typedef typename Graph::Edge Edge;

   379       typedef typename Graph::EdgeIt EdgeIt;

   380       typedef typename Graph::EdgeIdMap EdgeIdMap;

   382       typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;

   384       typedef typename Parent::Graph Graph;

   385       typedef typename Parent::Value Value;

   387       EdgeMap(const Graph& g)

   388 	: Parent(g, g.getEdgeObserverRegistry()) {}

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

   390 	: Parent(g, g.getEdgeObserverRegistry(), v) {}

   392     };

   394   };

   396 /// @}

   398 }

   400 #endif //LEMON_ARRAY_MAP_H

author	alpar
	Tue, 09 Nov 2004 17:48:52 +0000
changeset 973	6a6f3ac07b20
parent 921	818510fa3d99
child 978	175cf8c3a994
permissions	-rw-r--r--