COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/matrix_maps.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 1999:2ff283124dfc, checked in by Balazs Dezso, 18 years ago

Clarifing alteration observing system
It is directly connected now to a container

File size: 11.8 KB
RevLine 
[1720]1/* -*- C++ -*-
2 *
[1956]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
[1720]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 */
18
19#ifndef LEMON_MATRIX_MAPS_H
20#define LEMON_MATRIX_MAPS_H
21
22
23#include <vector>
[1993]24#include <lemon/bits/utility.h>
[1720]25#include <lemon/maps.h>
26
27
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...
34namespace lemon {
35
36  /// \brief Map for the coloumn view of the matrix
37  ///
38  /// Map for the coloumn view of the matrix.
39  template <typename _MatrixMap>
[1751]40  class MatrixRowMap : public MapTraits<_MatrixMap> {
[1720]41  public:
42    typedef _MatrixMap MatrixMap;
43    typedef typename MatrixMap::SecondKey Key;
44    typedef typename MatrixMap::Value Value;
45
46
[1751]47    MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row)
[1720]48      : matrix(_matrix), row(_row) {}
49
50    /// \brief Subscription operator
51    ///
52    /// Subscription operator.
53    typename MapTraits<MatrixMap>::ReturnValue
54    operator[](Key col) {
[1751]55      return matrix(row, col);
[1720]56    }
57
58    /// \brief Setter function
59    ///
60    /// Setter function.
61    void set(Key col, const Value& val) {
[1751]62      matrix.set(row, col, val);
[1720]63    }
64     
65    /// \brief Subscription operator
66    ///
67    /// Subscription operator.
68    typename MapTraits<MatrixMap>::ConstReturnValue
69    operator[](Key col) const {
[1751]70      return matrix(row, col);
[1720]71    }
72
73  private:
74    MatrixMap& matrix;
[1751]75    typename MatrixMap::FirstKey row;
[1720]76  };
77
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;
[1751]85    typedef typename MatrixMap::SecondKey Key;
[1720]86    typedef typename MatrixMap::Value Value;
87
[1751]88
[1720]89    ConstMatrixRowMap(const MatrixMap& _matrix,
[1751]90                      typename MatrixMap::FirstKey _row)
[1720]91      : matrix(_matrix), row(_row) {}
92
93    /// \brief Subscription operator
94    ///
95    /// Subscription operator.
96    typename MapTraits<MatrixMap>::ConstReturnValue
97    operator[](Key col) const {
[1751]98      return matrix(row, col);
[1720]99    }
100
101  private:
102    const MatrixMap& matrix;
[1751]103    typename MatrixMap::FirstKey row;
[1720]104  };
105
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,
[1751]111                                       typename MatrixMap::FirstKey row) {
[1720]112    return MatrixRowMap<MatrixMap>(matrixMap, row);
113  }
114
115  template <typename MatrixMap>
[1751]116  ConstMatrixRowMap<MatrixMap>
117  matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {
[1720]118    return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
119  }
120
[1751]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;
130
131    MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col)
132      : matrix(_matrix), col(_col) {}
133
134    /// \brief Subscription operator
135    ///
136    /// Subscription operator.
137    typename MapTraits<MatrixMap>::ReturnValue
138    operator[](Key row) {
139      return matrix(row, col);
140    }
141
142    /// \brief Setter function
143    ///
144    /// Setter function.
145    void set(Key row, const Value& val) {
146      matrix.set(row, col, val);
147    }
148     
149    /// \brief Subscription operator
150    ///
151    /// Subscription operator.
152    typename MapTraits<MatrixMap>::ConstReturnValue
153    operator[](Key row) const {
154      return matrix(row, col);
155    }
156
157  private:
158    MatrixMap& matrix;
159    typename MatrixMap::SecondKey col;
160  };
161
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;
171
172    ConstMatrixColMap(const MatrixMap& _matrix,
173                      typename MatrixMap::SecondKey _col)
174      : matrix(_matrix), col(_col) {}
175
176    /// \brief Subscription operator
177    ///
178    /// Subscription operator.
179    typename MapTraits<MatrixMap>::ConstReturnValue
180    operator[](Key row) const {
181      return matrix(row, col);
182    }
183
184  private:
185    const MatrixMap& matrix;
186    typename MatrixMap::SecondKey col;
187  };
188
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  }
197
198  template <typename MatrixMap>
199  ConstMatrixColMap<MatrixMap>
200  matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {
201    return ConstMatrixColMap<MatrixMap>(matrixMap, col);
202  }
203
[1720]204  /// \brief Container for store values for each ordered pair of graph items
205  ///
[1757]206  /// This data structure can strore for each pair of the same item
[1720]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
[1999]212    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
[1720]213  public:
[1999]214    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
215    Parent;
[1720]216
217    typedef _Graph Graph;
218    typedef _Item Key;
219
220    typedef _Item FirstKey;
221    typedef _Item SecondKey;
222    typedef _Value Value;
223
224    typedef True ReferenceMapTag;
225
226  private:
227               
228    typedef std::vector<Value> Container;
229
230  public:
231
232    typedef typename Container::reference Reference;
233    typedef typename Container::const_reference ConstReference;
234
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)
[1999]239      : values(size(_graph.maxId(Key()) + 1)) {
240      Parent::attach(_graph.getNotifier(Key()));
[1720]241    }
242
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)
[1999]248      : values(size(_graph.maxId(Key()) + 1), _val) {
249      Parent::attach(_graph.getNotifier(Key()));
[1720]250    }
251
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 {
[1999]257      return values[index(Parent::getNotifier()->id(first),
258                          Parent::getNotifier()->id(second))];
[1720]259    }
260   
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) {
[1999]266      return values[index(Parent::getNotifier()->id(first),
267                          Parent::getNotifier()->id(second))];
[1720]268    }
269
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) {
[1999]274      values[index(Parent::getNotifier()->id(first),
275                   Parent::getNotifier()->id(second))] = val;
[1720]276    }
277
278  protected:
279
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    }
287
288    static int size(int s) {
289      return s * s;
290    }
291
292    virtual void add(const Key& key) {
[1999]293      if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
294        values.resize(size(Parent::getNotifier()->id(key) + 1));       
[1720]295      }
296    }
297
298    virtual void erase(const Key&) {}
299
300    virtual void build() {
[1999]301      values.resize(size(Parent::getNotifier()->maxId() + 1));
[1720]302    }
303
304    virtual void clear() {
305      values.clear();
306    }   
307   
308  private:
309    std::vector<Value> values;
310  };
311
312  /// \brief Container for store values for each unordered pair of graph items
313  ///
[1757]314  /// This data structure can strore for each pair of the same item
[1720]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
[1999]320    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
[1720]321  public:
[1999]322    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
323    Parent;
[1720]324
325    typedef _Graph Graph;
326    typedef _Item Key;
327
328    typedef _Item FirstKey;
329    typedef _Item SecondKey;
330    typedef _Value Value;
331
332    typedef True ReferenceMapTag;
333
334  private:
335               
336    typedef std::vector<Value> Container;
337
338  public:
339
340    typedef typename Container::reference Reference;
341    typedef typename Container::const_reference ConstReference;
342
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)
[1999]347      : values(size(_graph.maxId(Key()) + 1)) {
348      Parent::attach(_graph.getNotifier(Key()));
[1720]349    }
350
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)
[1999]356      : values(size(_graph.maxId(Key()) + 1), _val) {
357      Parent::attach(_graph.getNotifier(Key()));
[1720]358    }
359
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 {
[1999]366      return values[index(Parent::getNotifier()->id(first),
367                          Parent::getNotifier()->id(second))];
[1720]368    }
369   
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) {
[1999]376      return values[index(Parent::getNotifier()->id(first),
377                          Parent::getNotifier()->id(second))];
[1720]378    }
379
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) {
[1999]384      values[index(Parent::getNotifier()->id(first),
385                   Parent::getNotifier()->id(second))] = val;
[1720]386    }
387
388  protected:
389
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    }
397
398    static int size(int s) {
399      return s * (s + 1) / 2;
400    }
401
402    virtual void add(const Key& key) {
[1999]403      if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
404        values.resize(size(Parent::getNotifier()->id(key) + 1));       
[1720]405      }
406    }
407
408    virtual void erase(const Key&) {}
409
410    virtual void build() {
[1999]411      values.resize(size(Parent::getNotifier()->maxId() + 1));
[1720]412    }
413
414    virtual void clear() {
415      values.clear();
416    }   
417   
418  private:
419    std::vector<Value> values;
420  };
421
422}
423
424#endif
Note: See TracBrowser for help on using the repository browser.