matrix_maps.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_MATRIX_MAPS_H
00020 #define LEMON_MATRIX_MAPS_H
00021 
00022 
00023 #include <vector>
00024 #include <lemon/utility.h>
00025 #include <lemon/maps.h>
00026 
00027 
00034 namespace lemon {
00035 
00039   template <typename _MatrixMap>
00040   class MatrixRowMap : public MapTraits<_MatrixMap> {
00041   public:
00042     typedef _MatrixMap MatrixMap;
00043     typedef typename MatrixMap::SecondKey Key;
00044     typedef typename MatrixMap::Value Value;
00045 
00046 
00047     MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) 
00048       : matrix(_matrix), row(_row) {}
00049 
00053     typename MapTraits<MatrixMap>::ReturnValue
00054     operator[](Key col) {
00055       return matrix(row, col);
00056     }
00057 
00061     void set(Key col, const Value& val) {
00062       matrix.set(row, col, val);
00063     }
00064       
00068     typename MapTraits<MatrixMap>::ConstReturnValue
00069     operator[](Key col) const {
00070       return matrix(row, col);
00071     }
00072 
00073   private:
00074     MatrixMap& matrix;
00075     typename MatrixMap::FirstKey row;
00076   };
00077 
00081   template <typename _MatrixMap>
00082   class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
00083   public:
00084     typedef _MatrixMap MatrixMap;
00085     typedef typename MatrixMap::SecondKey Key;
00086     typedef typename MatrixMap::Value Value;
00087 
00088 
00089     ConstMatrixRowMap(const MatrixMap& _matrix, 
00090                       typename MatrixMap::FirstKey _row) 
00091       : matrix(_matrix), row(_row) {}
00092 
00096     typename MapTraits<MatrixMap>::ConstReturnValue
00097     operator[](Key col) const {
00098       return matrix(row, col);
00099     }
00100 
00101   private:
00102     const MatrixMap& matrix;
00103     typename MatrixMap::FirstKey row;
00104   };
00105 
00109   template <typename MatrixMap>
00110   MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
00111                                        typename MatrixMap::FirstKey row) {
00112     return MatrixRowMap<MatrixMap>(matrixMap, row);
00113   }
00114 
00115   template <typename MatrixMap>
00116   ConstMatrixRowMap<MatrixMap>
00117   matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {
00118     return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
00119   }
00120 
00124   template <typename _MatrixMap>
00125   class MatrixColMap : public MapTraits<_MatrixMap> {
00126   public:
00127     typedef _MatrixMap MatrixMap;
00128     typedef typename MatrixMap::FirstKey Key;
00129     typedef typename MatrixMap::Value Value;
00130 
00131     MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) 
00132       : matrix(_matrix), col(_col) {}
00133 
00137     typename MapTraits<MatrixMap>::ReturnValue
00138     operator[](Key row) {
00139       return matrix(row, col);
00140     }
00141 
00145     void set(Key row, const Value& val) {
00146       matrix.set(row, col, val);
00147     }
00148       
00152     typename MapTraits<MatrixMap>::ConstReturnValue
00153     operator[](Key row) const {
00154       return matrix(row, col);
00155     }
00156 
00157   private:
00158     MatrixMap& matrix;
00159     typename MatrixMap::SecondKey col;
00160   };
00161 
00165   template <typename _MatrixMap>
00166   class ConstMatrixColMap : public MapTraits<_MatrixMap> {
00167   public:
00168     typedef _MatrixMap MatrixMap;
00169     typedef typename MatrixMap::FirstKey Key;
00170     typedef typename MatrixMap::Value Value;
00171 
00172     ConstMatrixColMap(const MatrixMap& _matrix, 
00173                       typename MatrixMap::SecondKey _col) 
00174       : matrix(_matrix), col(_col) {}
00175 
00179     typename MapTraits<MatrixMap>::ConstReturnValue
00180     operator[](Key row) const {
00181       return matrix(row, col);
00182     }
00183 
00184   private:
00185     const MatrixMap& matrix;
00186     typename MatrixMap::SecondKey col;
00187   };
00188 
00192   template <typename MatrixMap>
00193   MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
00194                                        typename MatrixMap::SecondKey col) {
00195     return MatrixColMap<MatrixMap>(matrixMap, col);
00196   }
00197 
00198   template <typename MatrixMap>
00199   ConstMatrixColMap<MatrixMap> 
00200   matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {
00201     return ConstMatrixColMap<MatrixMap>(matrixMap, col);
00202   }
00203 
00210   template <typename _Graph, typename _Item, typename _Value>
00211   class DynamicMatrixMap 
00212     : protected AlterationNotifier<_Item>::ObserverBase {
00213   public:
00214     typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
00215 
00216     typedef _Graph Graph;
00217     typedef _Item Key;
00218 
00219     typedef _Item FirstKey;
00220     typedef _Item SecondKey;
00221     typedef _Value Value;
00222 
00223     typedef True ReferenceMapTag;
00224 
00225   private:
00226                 
00227     typedef std::vector<Value> Container;
00228 
00229   public:
00230 
00231     typedef typename Container::reference Reference;
00232     typedef typename Container::const_reference ConstReference;
00233 
00237     DynamicMatrixMap(const Graph& _graph) 
00238       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
00239       Parent::attach(graph.getNotifier(Key()));
00240     }
00241 
00246     DynamicMatrixMap(const Graph& _graph, const Value& _val) 
00247       : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
00248       Parent::attach(graph.getNotifier(Key()));
00249     }
00250 
00251     ~DynamicMatrixMap() {
00252       if (Parent::attached()) {
00253         Parent::detach();
00254       }
00255     }
00256 
00261     ConstReference operator()(const Key& first, const Key& second) const {
00262       return values[index(graph.id(first), graph.id(second))];
00263     }
00264     
00269     Reference operator()(const Key& first, const Key& second) {
00270       return values[index(graph.id(first), graph.id(second))];
00271     }
00272 
00276     void set(const Key& first, const Key& second, const Value& val) {
00277       values[index(graph.id(first), graph.id(second))] = val;
00278     }
00279 
00280   protected:
00281 
00282     static int index(int i, int j) {
00283       if (i < j) {
00284         return j * j + i;
00285       } else {
00286         return i * i + i + j;
00287       }
00288     }
00289 
00290     static int size(int s) {
00291       return s * s;
00292     }
00293 
00294     virtual void add(const Key& key) {
00295       if (size(graph.id(key) + 1) >= (int)values.size()) {
00296         values.resize(size(graph.id(key) + 1)); 
00297       }
00298     }
00299 
00300     virtual void erase(const Key&) {}
00301 
00302     virtual void build() {
00303       values.resize(size(graph.maxId(Key()) + 1));
00304     }
00305 
00306     virtual void clear() {
00307       values.clear();
00308     }   
00309     
00310   private:
00311     const Graph& graph;
00312     std::vector<Value> values;
00313   };
00314 
00321   template <typename _Graph, typename _Item, typename _Value>
00322   class DynamicSymMatrixMap 
00323     : protected AlterationNotifier<_Item>::ObserverBase {
00324   public:
00325     typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
00326 
00327     typedef _Graph Graph;
00328     typedef _Item Key;
00329 
00330     typedef _Item FirstKey;
00331     typedef _Item SecondKey;
00332     typedef _Value Value;
00333 
00334     typedef True ReferenceMapTag;
00335 
00336   private:
00337                 
00338     typedef std::vector<Value> Container;
00339 
00340   public:
00341 
00342     typedef typename Container::reference Reference;
00343     typedef typename Container::const_reference ConstReference;
00344 
00348     DynamicSymMatrixMap(const Graph& _graph) 
00349       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
00350       Parent::attach(graph.getNotifier(Key()));
00351     }
00352 
00357     DynamicSymMatrixMap(const Graph& _graph, const Value& _val) 
00358       : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
00359       Parent::attach(graph.getNotifier(Key()));
00360     }
00361 
00362     ~DynamicSymMatrixMap() {
00363       if (Parent::attached()) {
00364         Parent::detach();
00365       }
00366     }
00367 
00373     ConstReference operator()(const Key& first, const Key& second) const {
00374       return values[index(graph.id(first), graph.id(second))];
00375     }
00376     
00382     Reference operator()(const Key& first, const Key& second) {
00383       return values[index(graph.id(first), graph.id(second))];
00384     }
00385 
00389     void set(const Key& first, const Key& second, const Value& val) {
00390       values[index(graph.id(first), graph.id(second))] = val;
00391     }
00392 
00393   protected:
00394 
00395     static int index(int i, int j) {
00396       if (i < j) {
00397         return j * (j + 1) / 2 + i;
00398       } else {
00399         return i * (i + 1) / 2 + j;
00400       }
00401     }
00402 
00403     static int size(int s) {
00404       return s * (s + 1) / 2;
00405     }
00406 
00407     virtual void add(const Key& key) {
00408       if (size(graph.id(key) + 1) >= (int)values.size()) {
00409         values.resize(size(graph.id(key) + 1)); 
00410       }
00411     }
00412 
00413     virtual void erase(const Key&) {}
00414 
00415     virtual void build() {
00416       values.resize(size(graph.maxId(Key()) + 1));
00417     }
00418 
00419     virtual void clear() {
00420       values.clear();
00421     }   
00422     
00423   private:
00424     const Graph& graph;
00425     std::vector<Value> values;
00426   };
00427 
00428 }
00429 
00430 #endif

Generated on Fri Feb 3 18:39:12 2006 for LEMON by  doxygen 1.4.6