lemon-0.x: lemon/matrix_maps.h@224cd6aacfc1

     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_MATRIX_MAPS_H

    20 #define LEMON_MATRIX_MAPS_H

    23 #include <vector>

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

    25 #include <lemon/maps.h>

    28 /// \file

    29 /// \ingroup maps

    30 /// \brief Maps indexed with pairs of items.

    31 ///

    32 /// \todo This file has the same name as the concept file in concept/,

    33 ///  and this is not easily detectable in docs...

    34 namespace lemon {

    36   /// \brief Map for the coloumn view of the matrix

    37   ///

    38   /// Map for the coloumn view of the matrix.

    39   template <typename _MatrixMap>

    40   class MatrixRowMap : public MapTraits<_MatrixMap> {

    41   public:

    42     typedef _MatrixMap MatrixMap;

    43     typedef typename MatrixMap::SecondKey Key;

    44     typedef typename MatrixMap::Value Value;

    47     MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row)

    48       : matrix(_matrix), row(_row) {}

    50     /// \brief Subscription operator

    51     ///

    52     /// Subscription operator.

    53     typename MapTraits<MatrixMap>::ReturnValue

    54     operator[](Key col) {

    55       return matrix(row, col);

    56     }

    58     /// \brief Setter function

    59     ///

    60     /// Setter function.

    61     void set(Key col, const Value& val) {

    62       matrix.set(row, col, val);

    63     }

    65     /// \brief Subscription operator

    66     ///

    67     /// Subscription operator.

    68     typename MapTraits<MatrixMap>::ConstReturnValue

    69     operator[](Key col) const {

    70       return matrix(row, col);

    71     }

    73   private:

    74     MatrixMap& matrix;

    75     typename MatrixMap::FirstKey row;

    76   };

    78   /// \brief Map for the row view of the matrix

    79   ///

    80   /// Map for the row view of the matrix.

    81   template <typename _MatrixMap>

    82   class ConstMatrixRowMap : public MapTraits<_MatrixMap> {

    83   public:

    84     typedef _MatrixMap MatrixMap;

    85     typedef typename MatrixMap::SecondKey Key;

    86     typedef typename MatrixMap::Value Value;

    89     ConstMatrixRowMap(const MatrixMap& _matrix,

    90 		      typename MatrixMap::FirstKey _row)

    91       : matrix(_matrix), row(_row) {}

    93     /// \brief Subscription operator

    94     ///

    95     /// Subscription operator.

    96     typename MapTraits<MatrixMap>::ConstReturnValue

    97     operator[](Key col) const {

    98       return matrix(row, col);

    99     }

   101   private:

   102     const MatrixMap& matrix;

   103     typename MatrixMap::FirstKey row;

   104   };

   106   /// \brief Gives back a row view of the matrix map

   107   ///

   108   /// Gives back a row view of the matrix map.

   109   template <typename MatrixMap>

   110   MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,

   111 				       typename MatrixMap::FirstKey row) {

   112     return MatrixRowMap<MatrixMap>(matrixMap, row);

   113   }

   115   template <typename MatrixMap>

   116   ConstMatrixRowMap<MatrixMap>

   117   matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {

   118     return ConstMatrixRowMap<MatrixMap>(matrixMap, row);

   119   }

   121   /// \brief Map for the row view of the matrix

   122   ///

   123   /// Map for the row view of the matrix.

   124   template <typename _MatrixMap>

   125   class MatrixColMap : public MapTraits<_MatrixMap> {

   126   public:

   127     typedef _MatrixMap MatrixMap;

   128     typedef typename MatrixMap::FirstKey Key;

   129     typedef typename MatrixMap::Value Value;

   131     MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col)

   132       : matrix(_matrix), col(_col) {}

   134     /// \brief Subscription operator

   135     ///

   136     /// Subscription operator.

   137     typename MapTraits<MatrixMap>::ReturnValue

   138     operator[](Key row) {

   139       return matrix(row, col);

   140     }

   142     /// \brief Setter function

   143     ///

   144     /// Setter function.

   145     void set(Key row, const Value& val) {

   146       matrix.set(row, col, val);

   147     }

   149     /// \brief Subscription operator

   150     ///

   151     /// Subscription operator.

   152     typename MapTraits<MatrixMap>::ConstReturnValue

   153     operator[](Key row) const {

   154       return matrix(row, col);

   155     }

   157   private:

   158     MatrixMap& matrix;

   159     typename MatrixMap::SecondKey col;

   160   };

   162   /// \brief Map for the col view of the matrix

   163   ///

   164   /// Map for the col view of the matrix.

   165   template <typename _MatrixMap>

   166   class ConstMatrixColMap : public MapTraits<_MatrixMap> {

   167   public:

   168     typedef _MatrixMap MatrixMap;

   169     typedef typename MatrixMap::FirstKey Key;

   170     typedef typename MatrixMap::Value Value;

   172     ConstMatrixColMap(const MatrixMap& _matrix,

   173 		      typename MatrixMap::SecondKey _col)

   174       : matrix(_matrix), col(_col) {}

   176     /// \brief Subscription operator

   177     ///

   178     /// Subscription operator.

   179     typename MapTraits<MatrixMap>::ConstReturnValue

   180     operator[](Key row) const {

   181       return matrix(row, col);

   182     }

   184   private:

   185     const MatrixMap& matrix;

   186     typename MatrixMap::SecondKey col;

   187   };

   189   /// \brief Gives back a col view of the matrix map

   190   ///

   191   /// Gives back a col view of the matrix map.

   192   template <typename MatrixMap>

   193   MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,

   194 				       typename MatrixMap::SecondKey col) {

   195     return MatrixColMap<MatrixMap>(matrixMap, col);

   196   }

   198   template <typename MatrixMap>

   199   ConstMatrixColMap<MatrixMap>

   200   matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {

   201     return ConstMatrixColMap<MatrixMap>(matrixMap, col);

   202   }

   204   /// \brief Container for store values for each ordered pair of graph items

   205   ///

   206   /// This data structure can strore for each pair of the same item

   207   /// type a value. It increase the size of the container when the

   208   /// associated graph modified, so it updated automaticly whenever

   209   /// it is needed.

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

   211   class DynamicMatrixMap

   212     : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

   213   public:

   214     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase

   215     Parent;

   217     typedef _Graph Graph;

   218     typedef _Item Key;

   220     typedef _Item FirstKey;

   221     typedef _Item SecondKey;

   222     typedef _Value Value;

   224     typedef True ReferenceMapTag;

   226   private:

   228     typedef std::vector<Value> Container;

   230   public:

   232     typedef typename Container::reference Reference;

   233     typedef typename Container::const_reference ConstReference;

   235     /// \brief Creates an item matrix for the given graph

   236     ///

   237     /// Creates an item matrix for the given graph.

   238     DynamicMatrixMap(const Graph& _graph)

   239       : values(size(_graph.maxId(Key()) + 1)) {

   240       Parent::attach(_graph.getNotifier(Key()));

   241     }

   243     /// \brief Creates an item matrix for the given graph

   244     ///

   245     /// Creates an item matrix for the given graph and assigns for each

   246     /// pairs of keys the given parameter.

   247     DynamicMatrixMap(const Graph& _graph, const Value& _val)

   248       : values(size(_graph.maxId(Key()) + 1), _val) {

   249       Parent::attach(_graph.getNotifier(Key()));

   250     }

   252     /// \brief Gives back the value assigned to the \c first - \c second

   253     /// ordered pair.

   254     ///

   255     /// Gives back the value assigned to the \c first - \c second ordered pair.

   256     ConstReference operator()(const Key& first, const Key& second) const {

   257       return values[index(Parent::getNotifier()->id(first),

   258                           Parent::getNotifier()->id(second))];

   259     }

   261     /// \brief Gives back the value assigned to the \c first - \c second

   262     /// ordered pair.

   263     ///

   264     /// Gives back the value assigned to the \c first - \c second ordered pair.

   265     Reference operator()(const Key& first, const Key& second) {

   266       return values[index(Parent::getNotifier()->id(first),

   267                           Parent::getNotifier()->id(second))];

   268     }

   270     /// \brief Setter function for the matrix map.

   271     ///

   272     /// Setter function for the matrix map.

   273     void set(const Key& first, const Key& second, const Value& val) {

   274       values[index(Parent::getNotifier()->id(first),

   275                    Parent::getNotifier()->id(second))] = val;

   276     }

   278   protected:

   280     static int index(int i, int j) {

   281       if (i < j) {

   282 	return j * j + i;

   283       } else {

   284 	return i * i + i + j;

   285       }

   286     }

   288     static int size(int s) {

   289       return s * s;

   290     }

   292     virtual void add(const Key& key) {

   293       if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {

   294 	values.resize(size(Parent::getNotifier()->id(key) + 1));

   295       }

   296     }

   298     virtual void erase(const Key&) {}

   300     virtual void build() {

   301       values.resize(size(Parent::getNotifier()->maxId() + 1));

   302     }

   304     virtual void clear() {

   305       values.clear();

   306     }

   308   private:

   309     std::vector<Value> values;

   310   };

   312   /// \brief Container for store values for each unordered pair of graph items

   313   ///

   314   /// This data structure can strore for each pair of the same item

   315   /// type a value. It increase the size of the container when the

   316   /// associated graph modified, so it updated automaticly whenever

   317   /// it is needed.

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

   319   class DynamicSymMatrixMap

   320     : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

   321   public:

   322     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase

   323     Parent;

   325     typedef _Graph Graph;

   326     typedef _Item Key;

   328     typedef _Item FirstKey;

   329     typedef _Item SecondKey;

   330     typedef _Value Value;

   332     typedef True ReferenceMapTag;

   334   private:

   336     typedef std::vector<Value> Container;

   338   public:

   340     typedef typename Container::reference Reference;

   341     typedef typename Container::const_reference ConstReference;

   343     /// \brief Creates an item matrix for the given graph

   344     ///

   345     /// Creates an item matrix for the given graph.

   346     DynamicSymMatrixMap(const Graph& _graph)

   347       : values(size(_graph.maxId(Key()) + 1)) {

   348       Parent::attach(_graph.getNotifier(Key()));

   349     }

   351     /// \brief Creates an item matrix for the given graph

   352     ///

   353     /// Creates an item matrix for the given graph and assigns for each

   354     /// pairs of keys the given parameter.

   355     DynamicSymMatrixMap(const Graph& _graph, const Value& _val)

   356       : values(size(_graph.maxId(Key()) + 1), _val) {

   357       Parent::attach(_graph.getNotifier(Key()));

   358     }

   360     /// \brief Gives back the value assigned to the \c first - \c second

   361     /// unordered pair.

   362     ///

   363     /// Gives back the value assigned to the \c first - \c second unordered

   364     /// pair.

   365     ConstReference operator()(const Key& first, const Key& second) const {

   366       return values[index(Parent::getNotifier()->id(first),

   367                           Parent::getNotifier()->id(second))];

   368     }

   370     /// \brief Gives back the value assigned to the \c first - \c second

   371     /// unordered pair.

   372     ///

   373     /// Gives back the value assigned to the \c first - \c second unordered

   374     /// pair.

   375     Reference operator()(const Key& first, const Key& second) {

   376       return values[index(Parent::getNotifier()->id(first),

   377                           Parent::getNotifier()->id(second))];

   378     }

   380     /// \brief Setter function for the matrix map.

   381     ///

   382     /// Setter function for the matrix map.

   383     void set(const Key& first, const Key& second, const Value& val) {

   384       values[index(Parent::getNotifier()->id(first),

   385                    Parent::getNotifier()->id(second))] = val;

   386     }

   388   protected:

   390     static int index(int i, int j) {

   391       if (i < j) {

   392 	return j * (j + 1) / 2 + i;

   393       } else {

   394 	return i * (i + 1) / 2 + j;

   395       }

   396     }

   398     static int size(int s) {

   399       return s * (s + 1) / 2;

   400     }

   402     virtual void add(const Key& key) {

   403       if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {

   404 	values.resize(size(Parent::getNotifier()->id(key) + 1));

   405       }

   406     }

   408     virtual void erase(const Key&) {}

   410     virtual void build() {

   411       values.resize(size(Parent::getNotifier()->maxId() + 1));

   412     }

   414     virtual void clear() {

   415       values.clear();

   416     }

   418   private:

   419     std::vector<Value> values;

   420   };

   422 }

   424 #endif

author	ladanyi
	Thu, 23 Mar 2006 19:57:14 +0000
changeset 2012	224cd6aacfc1
parent 1993	2115143eceea
child 2039	dacc4ce9474d
permissions	-rw-r--r--