lemon-0.x: lemon/bits/default

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_DEFAULT_MAP_H

    20 #define LEMON_DEFAULT_MAP_H

    23 #include <lemon/bits/array_map.h>

    24 #include <lemon/bits/vector_map.h>

    26 ///\ingroup graphmapfactory

    27 ///\file

    28 ///\brief Graph maps that construct and destruct

    29 ///their elements dynamically.

    31 namespace lemon {

    34   template <typename _Graph, typename _Item, typename _Value>

    35   struct DefaultMapSelector {

    36     typedef ArrayMap<_Graph, _Item, _Value> Map;

    37   };

    39   // bool

    40   template <typename _Graph, typename _Item>

    41   struct DefaultMapSelector<_Graph, _Item, bool> {

    42     typedef VectorMap<_Graph, _Item, bool> Map;

    43   };

    45   // char

    46   template <typename _Graph, typename _Item>

    47   struct DefaultMapSelector<_Graph, _Item, char> {

    48     typedef VectorMap<_Graph, _Item, char> Map;

    49   };

    51   template <typename _Graph, typename _Item>

    52   struct DefaultMapSelector<_Graph, _Item, signed char> {

    53     typedef VectorMap<_Graph, _Item, signed char> Map;

    54   };

    56   template <typename _Graph, typename _Item>

    57   struct DefaultMapSelector<_Graph, _Item, unsigned char> {

    58     typedef VectorMap<_Graph, _Item, unsigned char> Map;

    59   };

    62   // int

    63   template <typename _Graph, typename _Item>

    64   struct DefaultMapSelector<_Graph, _Item, signed int> {

    65     typedef VectorMap<_Graph, _Item, signed int> Map;

    66   };

    68   template <typename _Graph, typename _Item>

    69   struct DefaultMapSelector<_Graph, _Item, unsigned int> {

    70     typedef VectorMap<_Graph, _Item, unsigned int> Map;

    71   };

    74   // short

    75   template <typename _Graph, typename _Item>

    76   struct DefaultMapSelector<_Graph, _Item, signed short> {

    77     typedef VectorMap<_Graph, _Item, signed short> Map;

    78   };

    80   template <typename _Graph, typename _Item>

    81   struct DefaultMapSelector<_Graph, _Item, unsigned short> {

    82     typedef VectorMap<_Graph, _Item, unsigned short> Map;

    83   };

    86   // long

    87   template <typename _Graph, typename _Item>

    88   struct DefaultMapSelector<_Graph, _Item, signed long> {

    89     typedef VectorMap<_Graph, _Item, signed long> Map;

    90   };

    92   template <typename _Graph, typename _Item>

    93   struct DefaultMapSelector<_Graph, _Item, unsigned long> {

    94     typedef VectorMap<_Graph, _Item, unsigned long> Map;

    95   };

    97   // \todo handling long long type

   100   // float

   101   template <typename _Graph, typename _Item>

   102   struct DefaultMapSelector<_Graph, _Item, float> {

   103     typedef VectorMap<_Graph, _Item, float> Map;

   104   };

   107   // double

   108   template <typename _Graph, typename _Item>

   109   struct DefaultMapSelector<_Graph, _Item, double> {

   110     typedef VectorMap<_Graph, _Item,  double> Map;

   111   };

   114   // long double

   115   template <typename _Graph, typename _Item>

   116   struct DefaultMapSelector<_Graph, _Item, long double> {

   117     typedef VectorMap<_Graph, _Item, long double> Map;

   118   };

   121   // pointer

   122   template <typename _Graph, typename _Item, typename _Ptr>

   123   struct DefaultMapSelector<_Graph, _Item, _Ptr*> {

   124     typedef VectorMap<_Graph, _Item, _Ptr*> Map;

   125   };

   127   /// \e

   128   template <

   129     typename _Graph,

   130     typename _Item,

   131     typename _Value>

   132   class DefaultMap

   133     : public DefaultMapSelector<_Graph, _Item, _Value>::Map {

   134   public:

   135     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;

   136     typedef DefaultMap<_Graph, _Item, _Value> Map;

   138     typedef typename Parent::Graph Graph;

   139     typedef typename Parent::Value Value;

   141     DefaultMap(const Graph& _g) : Parent(_g) {}

   142     DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}

   144   };

   147   /// \e

   148   template <typename _Base>

   149   class MappableGraphExtender : public _Base {

   150   public:

   152     typedef MappableGraphExtender<_Base> Graph;

   153     typedef _Base Parent;

   155     typedef typename Parent::Node Node;

   156     typedef typename Parent::NodeIt NodeIt;

   158     typedef typename Parent::Edge Edge;

   159     typedef typename Parent::EdgeIt EdgeIt;

   162     template <typename _Value>

   163     class NodeMap

   164       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {

   165     public:

   166       typedef MappableGraphExtender Graph;

   167       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;

   169       NodeMap(const Graph& _g)

   170 	: Parent(_g) {}

   171       NodeMap(const Graph& _g, const _Value& _v)

   172 	: Parent(_g, _v) {}

   174       NodeMap& operator=(const NodeMap& cmap) {

   175 	return operator=<NodeMap>(cmap);

   176       }

   179       /// \brief Template assign operator.

   180       ///

   181       /// The given parameter should be conform to the ReadMap

   182       /// concecpt and could be indiced by the current item set of

   183       /// the NodeMap. In this case the value for each item

   184       /// is assigned by the value of the given ReadMap.

   185       template <typename CMap>

   186       NodeMap& operator=(const CMap& cmap) {

   187 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();

   188 	const typename Parent::Graph* graph = Parent::getGraph();

   189 	Node it;

   190 	for (graph->first(it); it != INVALID; graph->next(it)) {

   191 	  Parent::set(it, cmap[it]);

   192 	}

   193 	return *this;

   194       }

   196     };

   198     template <typename _Value>

   199     class EdgeMap

   200       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {

   201     public:

   202       typedef MappableGraphExtender Graph;

   203       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   205       EdgeMap(const Graph& _g)

   206 	: Parent(_g) {}

   207       EdgeMap(const Graph& _g, const _Value& _v)

   208 	: Parent(_g, _v) {}

   210       EdgeMap& operator=(const EdgeMap& cmap) {

   211 	return operator=<EdgeMap>(cmap);

   212       }

   214       template <typename CMap>

   215       EdgeMap& operator=(const CMap& cmap) {

   216 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   217 	const typename Parent::Graph* graph = Parent::getGraph();

   218 	Edge it;

   219 	for (graph->first(it); it != INVALID; graph->next(it)) {

   220 	  Parent::set(it, cmap[it]);

   221 	}

   222 	return *this;

   223       }

   224     };

   226   };

   228   /// \e

   229   template <typename _Base>

   230   class MappableEdgeSetExtender : public _Base {

   231   public:

   233     typedef MappableEdgeSetExtender<_Base> Graph;

   234     typedef _Base Parent;

   236     typedef typename Parent::Edge Edge;

   237     typedef typename Parent::EdgeIt EdgeIt;

   239     template <typename _Value>

   240     class EdgeMap

   241       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {

   242     public:

   243       typedef MappableEdgeSetExtender Graph;

   244       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   246       EdgeMap(const Graph& _g)

   247 	: Parent(_g) {}

   248       EdgeMap(const Graph& _g, const _Value& _v)

   249 	: Parent(_g, _v) {}

   251       EdgeMap& operator=(const EdgeMap& cmap) {

   252 	return operator=<EdgeMap>(cmap);

   253       }

   255       template <typename CMap>

   256       EdgeMap& operator=(const CMap& cmap) {

   257 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   258 	const typename Parent::Graph* graph = Parent::getGraph();

   259 	Edge it;

   260 	for (graph->first(it); it != INVALID; graph->next(it)) {

   261 	  Parent::set(it, cmap[it]);

   262 	}

   263 	return *this;

   264       }

   265     };

   267   };

   269   /// \e

   270   template <typename _Base>

   271   class MappableUGraphExtender :

   272     public MappableGraphExtender<_Base> {

   273   public:

   275     typedef MappableUGraphExtender Graph;

   276     typedef MappableGraphExtender<_Base> Parent;

   278     typedef typename Parent::UEdge UEdge;

   280     template <typename _Value>

   281     class UEdgeMap

   282       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {

   283     public:

   284       typedef MappableUGraphExtender Graph;

   285       typedef IterableMapExtender<

   286 	DefaultMap<Graph, UEdge, _Value> > Parent;

   288       UEdgeMap(const Graph& _g)

   289 	: Parent(_g) {}

   290       UEdgeMap(const Graph& _g, const _Value& _v)

   291 	: Parent(_g, _v) {}

   293       UEdgeMap& operator=(const UEdgeMap& cmap) {

   294 	return operator=<UEdgeMap>(cmap);

   295       }

   297       template <typename CMap>

   298       UEdgeMap& operator=(const CMap& cmap) {

   299 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

   300 	const typename Parent::Graph* graph = Parent::getGraph();

   301 	UEdge it;

   302 	for (graph->first(it); it != INVALID; graph->next(it)) {

   303 	  Parent::set(it, cmap[it]);

   304 	}

   305 	return *this;

   306       }

   307     };

   310   };

   312   /// \e

   313   template <typename _Base>

   314   class MappableUEdgeSetExtender :

   315     public MappableEdgeSetExtender<_Base> {

   316   public:

   318     typedef MappableUEdgeSetExtender Graph;

   319     typedef MappableEdgeSetExtender<_Base> Parent;

   321     typedef typename Parent::UEdge UEdge;

   323     template <typename _Value>

   324     class UEdgeMap

   325       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {

   326     public:

   327       typedef MappableUEdgeSetExtender Graph;

   328       typedef IterableMapExtender<

   329 	DefaultMap<Graph, UEdge, _Value> > Parent;

   331       UEdgeMap(const Graph& _g)

   332 	: Parent(_g) {}

   333       UEdgeMap(const Graph& _g, const _Value& _v)

   334 	: Parent(_g, _v) {}

   336       UEdgeMap& operator=(const UEdgeMap& cmap) {

   337 	return operator=<UEdgeMap>(cmap);

   338       }

   340       template <typename CMap>

   341       UEdgeMap& operator=(const CMap& cmap) {

   342 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

   343 	const typename Parent::Graph* graph = Parent::getGraph();

   344 	UEdge it;

   345 	for (graph->first(it); it != INVALID; graph->next(it)) {

   346 	  Parent::set(it, cmap[it]);

   347 	}

   348 	return *this;

   349       }

   350     };

   353   };

   356   template <typename _Base>

   357   class MappableBpUGraphExtender : public _Base {

   358   public:

   360     typedef _Base Parent;

   361     typedef MappableBpUGraphExtender Graph;

   363     typedef typename Parent::Node Node;

   364     typedef typename Parent::ANode ANode;

   365     typedef typename Parent::BNode BNode;

   366     typedef typename Parent::Edge Edge;

   367     typedef typename Parent::UEdge UEdge;

   369     template <typename _Value>

   370     class ANodeMap

   371       : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {

   372     public:

   373       typedef MappableBpUGraphExtender Graph;

   374       typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >

   375       Parent;

   377       ANodeMap(const Graph& _g)

   378 	: Parent(_g) {}

   379       ANodeMap(const Graph& _g, const _Value& _v)

   380 	: Parent(_g, _v) {}

   382       ANodeMap& operator=(const ANodeMap& cmap) {

   383 	return operator=<ANodeMap>(cmap);

   384       }

   387       /// \brief Template assign operator.

   388       ///

   389       /// The given parameter should be conform to the ReadMap

   390       /// concept and could be indiced by the current item set of

   391       /// the ANodeMap. In this case the value for each item

   392       /// is assigned by the value of the given ReadMap.

   393       template <typename CMap>

   394       ANodeMap& operator=(const CMap& cmap) {

   395 	checkConcept<concept::ReadMap<ANode, _Value>, CMap>();

   396 	const typename Parent::Graph* graph = Parent::getGraph();

   397 	ANode it;

   398 	for (graph->first(it); it != INVALID; graph->next(it)) {

   399 	  Parent::set(it, cmap[it]);

   400 	}

   401 	return *this;

   402       }

   404     };

   406     template <typename _Value>

   407     class BNodeMap

   408       : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {

   409     public:

   410       typedef MappableBpUGraphExtender Graph;

   411       typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >

   412       Parent;

   414       BNodeMap(const Graph& _g)

   415 	: Parent(_g) {}

   416       BNodeMap(const Graph& _g, const _Value& _v)

   417 	: Parent(_g, _v) {}

   419       BNodeMap& operator=(const BNodeMap& cmap) {

   420 	return operator=<BNodeMap>(cmap);

   421       }

   424       /// \brief Template assign operator.

   425       ///

   426       /// The given parameter should be conform to the ReadMap

   427       /// concept and could be indiced by the current item set of

   428       /// the BNodeMap. In this case the value for each item

   429       /// is assigned by the value of the given ReadMap.

   430       template <typename CMap>

   431       BNodeMap& operator=(const CMap& cmap) {

   432 	checkConcept<concept::ReadMap<BNode, _Value>, CMap>();

   433 	const typename Parent::Graph* graph = Parent::getGraph();

   434 	BNode it;

   435 	for (graph->first(it); it != INVALID; graph->next(it)) {

   436 	  Parent::set(it, cmap[it]);

   437 	}

   438 	return *this;

   439       }

   441     };

   443   protected:

   445     template <typename _Value>

   446     class NodeMapBase : public Parent::NodeNotifier::ObserverBase {

   447     public:

   448       typedef MappableBpUGraphExtender Graph;

   450       typedef Node Key;

   451       typedef _Value Value;

   453       /// The reference type of the map;

   454       typedef typename BNodeMap<_Value>::Reference Reference;

   455       /// The pointer type of the map;

   456       typedef typename BNodeMap<_Value>::Pointer Pointer;

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

   459       typedef const Value ConstValue;

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

   461       typedef typename BNodeMap<_Value>::ConstReference ConstReference;

   462       /// The pointer type of the map;

   463       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;

   465       typedef True ReferenceMapTag;

   467       NodeMapBase(const Graph& _g)

   468 	: graph(&_g), bNodeMap(_g), aNodeMap(_g) {

   469 	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));

   470       }

   471       NodeMapBase(const Graph& _g, const _Value& _v)

   472 	: graph(&_g), bNodeMap(_g, _v),

   473 	  aNodeMap(_g, _v) {

   474 	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));

   475       }

   477       virtual ~NodeMapBase() {

   478 	if (Parent::NodeNotifier::ObserverBase::attached()) {

   479 	  Parent::NodeNotifier::ObserverBase::detach();

   480 	}

   481       }

   483       ConstReference operator[](const Key& node) const {

   484 	if (Parent::aNode(node)) {

   485 	  return aNodeMap[node];

   486 	} else {

   487 	  return bNodeMap[node];

   488 	}

   489       }

   491       Reference operator[](const Key& node) {

   492 	if (Parent::aNode(node)) {

   493 	  return aNodeMap[node];

   494 	} else {

   495 	  return bNodeMap[node];

   496 	}

   497       }

   499       void set(const Key& node, const Value& value) {

   500 	if (Parent::aNode(node)) {

   501 	  aNodeMap.set(node, value);

   502 	} else {

   503 	  bNodeMap.set(node, value);

   504 	}

   505       }

   507     protected:

   509       virtual void add(const Node&) {}

   510       virtual void add(const std::vector<Node>&) {}

   511       virtual void erase(const Node&) {}

   512       virtual void erase(const std::vector<Node>&) {}

   513       virtual void clear() {}

   514       virtual void build() {}

   516       const Graph* getGraph() const { return graph; }

   518     private:

   519       const Graph* graph;

   520       BNodeMap<_Value> bNodeMap;

   521       ANodeMap<_Value> aNodeMap;

   522     };

   524   public:

   526     template <typename _Value>

   527     class NodeMap

   528       : public IterableMapExtender<NodeMapBase<_Value> > {

   529     public:

   530       typedef MappableBpUGraphExtender Graph;

   531       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;

   533       NodeMap(const Graph& _g)

   534 	: Parent(_g) {}

   535       NodeMap(const Graph& _g, const _Value& _v)

   536 	: Parent(_g, _v) {}

   538       NodeMap& operator=(const NodeMap& cmap) {

   539 	return operator=<NodeMap>(cmap);

   540       }

   543       /// \brief Template assign operator.

   544       ///

   545       /// The given parameter should be conform to the ReadMap

   546       /// concept and could be indiced by the current item set of

   547       /// the NodeMap. In this case the value for each item

   548       /// is assigned by the value of the given ReadMap.

   549       template <typename CMap>

   550       NodeMap& operator=(const CMap& cmap) {

   551 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();

   552 	const typename Parent::Graph* graph = Parent::getGraph();

   553 	Node it;

   554 	for (graph->first(it); it != INVALID; graph->next(it)) {

   555 	  Parent::set(it, cmap[it]);

   556 	}

   557 	return *this;

   558       }

   560     };

   564     template <typename _Value>

   565     class EdgeMap

   566       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {

   567     public:

   568       typedef MappableBpUGraphExtender Graph;

   569       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   571       EdgeMap(const Graph& _g)

   572 	: Parent(_g) {}

   573       EdgeMap(const Graph& _g, const _Value& _v)

   574 	: Parent(_g, _v) {}

   576       EdgeMap& operator=(const EdgeMap& cmap) {

   577 	return operator=<EdgeMap>(cmap);

   578       }

   580       template <typename CMap>

   581       EdgeMap& operator=(const CMap& cmap) {

   582 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   583 	const typename Parent::Graph* graph = Parent::getGraph();

   584 	Edge it;

   585 	for (graph->first(it); it != INVALID; graph->next(it)) {

   586 	  Parent::set(it, cmap[it]);

   587 	}

   588 	return *this;

   589       }

   590     };

   592     template <typename _Value>

   593     class UEdgeMap

   594       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {

   595     public:

   596       typedef MappableBpUGraphExtender Graph;

   597       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >

   598       Parent;

   600       UEdgeMap(const Graph& _g)

   601 	: Parent(_g) {}

   602       UEdgeMap(const Graph& _g, const _Value& _v)

   603 	: Parent(_g, _v) {}

   605       UEdgeMap& operator=(const UEdgeMap& cmap) {

   606 	return operator=<UEdgeMap>(cmap);

   607       }

   609       template <typename CMap>

   610       UEdgeMap& operator=(const CMap& cmap) {

   611 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

   612 	const typename Parent::Graph* graph = Parent::getGraph();

   613 	UEdge it;

   614 	for (graph->first(it); it != INVALID; graph->next(it)) {

   615 	  Parent::set(it, cmap[it]);

   616 	}

   617 	return *this;

   618       }

   619     };

   621   };

   623 }

   625 #endif

author	deba
	Mon, 06 Feb 2006 20:32:29 +0000
changeset 1964	df0b07457083
parent 1956	a055123339d5
child 1965	71b3bc042c47
permissions	-rw-r--r--