vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_MATRIX_MAPS_H
20 #define LEMON_MATRIX_MAPS_H
24 #include <lemon/utility.h>
25 #include <lemon/maps.h>
30 /// \brief Maps indexed with pairs of items.
32 /// \todo This file has the same name as the concept file in concept/,
33 /// and this is not easily detectable in docs...
36 /// \brief Map for the coloumn view of the matrix
38 /// Map for the coloumn view of the matrix.
39 template <typename _MatrixMap>
40 class MatrixRowMap : public MapTraits<_MatrixMap> {
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
52 /// Subscription operator.
53 typename MapTraits<MatrixMap>::ReturnValue
55 return matrix(row, col);
58 /// \brief Setter function
61 void set(Key col, const Value& val) {
62 matrix.set(row, col, val);
65 /// \brief Subscription operator
67 /// Subscription operator.
68 typename MapTraits<MatrixMap>::ConstReturnValue
69 operator[](Key col) const {
70 return matrix(row, col);
75 typename MatrixMap::FirstKey row;
78 /// \brief Map for the row view of the matrix
80 /// Map for the row view of the matrix.
81 template <typename _MatrixMap>
82 class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
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
95 /// Subscription operator.
96 typename MapTraits<MatrixMap>::ConstReturnValue
97 operator[](Key col) const {
98 return matrix(row, col);
102 const MatrixMap& matrix;
103 typename MatrixMap::FirstKey row;
106 /// \brief Gives back a row view of the matrix map
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);
115 template <typename MatrixMap>
116 ConstMatrixRowMap<MatrixMap>
117 matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {
118 return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
121 /// \brief Map for the row view of the matrix
123 /// Map for the row view of the matrix.
124 template <typename _MatrixMap>
125 class MatrixColMap : public MapTraits<_MatrixMap> {
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
136 /// Subscription operator.
137 typename MapTraits<MatrixMap>::ReturnValue
138 operator[](Key row) {
139 return matrix(row, col);
142 /// \brief Setter function
145 void set(Key row, const Value& val) {
146 matrix.set(row, col, val);
149 /// \brief Subscription operator
151 /// Subscription operator.
152 typename MapTraits<MatrixMap>::ConstReturnValue
153 operator[](Key row) const {
154 return matrix(row, col);
159 typename MatrixMap::SecondKey col;
162 /// \brief Map for the col view of the matrix
164 /// Map for the col view of the matrix.
165 template <typename _MatrixMap>
166 class ConstMatrixColMap : public MapTraits<_MatrixMap> {
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
178 /// Subscription operator.
179 typename MapTraits<MatrixMap>::ConstReturnValue
180 operator[](Key row) const {
181 return matrix(row, col);
185 const MatrixMap& matrix;
186 typename MatrixMap::SecondKey col;
189 /// \brief Gives back a col view of the matrix map
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);
198 template <typename MatrixMap>
199 ConstMatrixColMap<MatrixMap>
200 matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {
201 return ConstMatrixColMap<MatrixMap>(matrixMap, col);
204 /// \brief Container for store values for each ordered pair of graph items
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
210 template <typename _Graph, typename _Item, typename _Value>
211 class DynamicMatrixMap
212 : protected AlterationNotifier<_Item>::ObserverBase {
214 typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
216 typedef _Graph Graph;
219 typedef _Item FirstKey;
220 typedef _Item SecondKey;
221 typedef _Value Value;
223 typedef True ReferenceMapTag;
227 typedef std::vector<Value> Container;
231 typedef typename Container::reference Reference;
232 typedef typename Container::const_reference ConstReference;
234 /// \brief Creates an item matrix for the given graph
236 /// Creates an item matrix for the given graph.
237 DynamicMatrixMap(const Graph& _graph)
238 : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
239 Parent::attach(graph.getNotifier(Key()));
242 /// \brief Creates an item matrix for the given graph
244 /// Creates an item matrix for the given graph and assigns for each
245 /// pairs of keys the given parameter.
246 DynamicMatrixMap(const Graph& _graph, const Value& _val)
247 : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
248 Parent::attach(graph.getNotifier(Key()));
251 ~DynamicMatrixMap() {
252 if (Parent::attached()) {
257 /// \brief Gives back the value assigned to the \c first - \c second
260 /// Gives back the value assigned to the \c first - \c second ordered pair.
261 ConstReference operator()(const Key& first, const Key& second) const {
262 return values[index(graph.id(first), graph.id(second))];
265 /// \brief Gives back the value assigned to the \c first - \c second
268 /// Gives back the value assigned to the \c first - \c second ordered pair.
269 Reference operator()(const Key& first, const Key& second) {
270 return values[index(graph.id(first), graph.id(second))];
273 /// \brief Setter function for the matrix map.
275 /// Setter function for the matrix map.
276 void set(const Key& first, const Key& second, const Value& val) {
277 values[index(graph.id(first), graph.id(second))] = val;
282 static int index(int i, int j) {
286 return i * i + i + j;
290 static int size(int s) {
294 virtual void add(const Key& key) {
295 if (size(graph.id(key) + 1) >= (int)values.size()) {
296 values.resize(size(graph.id(key) + 1));
300 virtual void erase(const Key&) {}
302 virtual void build() {
303 values.resize(size(graph.maxId(Key()) + 1));
306 virtual void clear() {
312 std::vector<Value> values;
315 /// \brief Container for store values for each unordered pair of graph items
317 /// This data structure can strore for each pair of the same item
318 /// type a value. It increase the size of the container when the
319 /// associated graph modified, so it updated automaticly whenever
321 template <typename _Graph, typename _Item, typename _Value>
322 class DynamicSymMatrixMap
323 : protected AlterationNotifier<_Item>::ObserverBase {
325 typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
327 typedef _Graph Graph;
330 typedef _Item FirstKey;
331 typedef _Item SecondKey;
332 typedef _Value Value;
334 typedef True ReferenceMapTag;
338 typedef std::vector<Value> Container;
342 typedef typename Container::reference Reference;
343 typedef typename Container::const_reference ConstReference;
345 /// \brief Creates an item matrix for the given graph
347 /// Creates an item matrix for the given graph.
348 DynamicSymMatrixMap(const Graph& _graph)
349 : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
350 Parent::attach(graph.getNotifier(Key()));
353 /// \brief Creates an item matrix for the given graph
355 /// Creates an item matrix for the given graph and assigns for each
356 /// pairs of keys the given parameter.
357 DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
358 : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
359 Parent::attach(graph.getNotifier(Key()));
362 ~DynamicSymMatrixMap() {
363 if (Parent::attached()) {
368 /// \brief Gives back the value assigned to the \c first - \c second
371 /// Gives back the value assigned to the \c first - \c second unordered
373 ConstReference operator()(const Key& first, const Key& second) const {
374 return values[index(graph.id(first), graph.id(second))];
377 /// \brief Gives back the value assigned to the \c first - \c second
380 /// Gives back the value assigned to the \c first - \c second unordered
382 Reference operator()(const Key& first, const Key& second) {
383 return values[index(graph.id(first), graph.id(second))];
386 /// \brief Setter function for the matrix map.
388 /// Setter function for the matrix map.
389 void set(const Key& first, const Key& second, const Value& val) {
390 values[index(graph.id(first), graph.id(second))] = val;
395 static int index(int i, int j) {
397 return j * (j + 1) / 2 + i;
399 return i * (i + 1) / 2 + j;
403 static int size(int s) {
404 return s * (s + 1) / 2;
407 virtual void add(const Key& key) {
408 if (size(graph.id(key) + 1) >= (int)values.size()) {
409 values.resize(size(graph.id(key) + 1));
413 virtual void erase(const Key&) {}
415 virtual void build() {
416 values.resize(size(graph.maxId(Key()) + 1));
419 virtual void clear() {
425 std::vector<Value> values;