00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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