1
// k9/a4/sparmat.h, templates for sparse matrices
3
#define SPARSEMATRIX_H SPARSEMATRIX_H
5
// selection of implementation
6
#ifdef STL_map // defined in main()
12
/* If at this point the HMap container is chosen, a function for
13
calculating the hash table addresses is needed. As opposed to the
14
hash functions described up to now, not only one value, but two are
15
used for the calculation. Therefore, the function operator of the
16
PairHashFun class takes a pair as argument. The address calculation
17
itself is simple, but sufficient for our purposes. */
21
template<class IndexType> // int, long or unsigned
25
PairHashFun(long prime=65537) // another prime number is possible
26
// e.g. 2111 for smaller Matrizes
30
// Address calculation with two values
31
long operator()(const pair<IndexType, IndexType>& p) const
33
return (p.first + p.second) % tabSize;
36
long tableSize() const
51
template<class ValueType, class IndexType, class ContainerType>
56
typename ContainerType::iterator I;
57
IndexType row, column;
60
typedef pair<IndexType, IndexType> IndexPair;
61
typedef MatrixElement<ValueType, IndexType,
62
ContainerType>& Reference;
64
MatrixElement(ContainerType& Cont, IndexType r, IndexType c)
65
: C(Cont), I(C.find(IndexPair(r,c))),
69
/* The constructor initializes the private variables with all
70
information that is needed. The container itself is located in
71
the sparseMatrix class; here, the reference to it is entered.
72
If the passed indices for row and column belong to an element
73
not yet stored in the container, the iterator has the value
76
ValueType asValue() const
84
operator ValueType () const // type conversion operator
89
/* According to the definition of the sparse matrix, 0 is returned
90
if the element is not present in the container. Otherwise, the
91
result is the second part of the object of type value_type
92
stored in the container. */
94
Reference operator=(const ValueType& x)
96
if(x != ValueType(0)) // not equal 0?
98
/* If the element does not yet exist, it is put, together
99
with the indices, into an object of type value_type and
100
inserted with insert(): */
104
assert(C.size() < C.max_size());
109
ContainerType::value_type(
110
IndexPair(row,column), x))
113
else (*I).second = x;
116
/* insert() returns a pair whose first part is an iterator
117
pointing to the inserted object. The second part is of type
118
bool and indicates whether the insertion took place because
119
no element with this key existed. This is, however, not
120
evaluated here because, due to the precondition (I ==
121
C.end()), the second part must always have the value true.
122
If, instead, the element already exists, the value is
123
entered into the second part of the value_type object. If
124
the value is equal 0, in order to save space the element is
125
deleted if it existed. */
136
/* An assignment operator is required which in turn requires a
137
reference to an object of type MatrixElement. When both the
138
left- and right-hand side are identical, nothing has to happen.
139
Otherwise, as above, it has to be checked whether the value of
140
the right-hand element is 0 or not. The resulting behavior is
141
described together with the above assignment operator, so that
142
here it is simply called: */
144
Reference operator=(const Reference rhs)
146
if(this != &rhs) // not identical?
148
return operator=(rhs.asValue()); // see above
153
}; // class MatrixElement
155
template<class ValueType, class IndexType>
159
typedef pair<IndexType, IndexType> IndexPair;
161
// The switch STL_map controls the compilation:
164
typedef map<IndexPair, ValueType,
165
less<IndexPair> > ContainerType;
167
typedef HMap<IndexPair, ValueType,
168
PairHashFun<IndexType> > ContainerType;
171
typedef MatrixElement<ValueType, IndexType,
172
ContainerType> MatrixElement;
175
typedef IndexType size_type;
177
/* The constructor only initializes the row and column
178
information. The container is created by its standard
179
constructor, where in the case of hash implementation, the size
180
of the container is given by the hash function object of type
181
PairHashFun (see typedef above). */
184
size_type rows, columns;
188
sparseMatrix(size_type r, size_type c)
189
: rows(r), columns(c)
192
size_type Rows() const { return rows;}
193
size_type Columns() const { return columns;}
195
// usual container type definitions
196
typedef typename ContainerType::iterator iterator;
197
typedef typename ContainerType::const_iterator const_iterator;
199
// usual container functions
200
size_type size() const { return C.size();}
201
size_type max_size() const { return C.max_size();}
203
iterator begin() { return C.begin();}
204
iterator end() { return C.end();}
206
const_iterator begin() const { return C.begin();}
207
const_iterator end() const { return C.end();}
215
class Aux // for index operator below
218
Aux(size_type r, size_type maxs, ContainerType& Cont)
219
: Row(r), maxColumns(maxs), C(Cont)
222
/* After checking the number of columns, the index operator of
223
Aux returns a matrix element which is equipped with all
224
necessary information to carry out a successful assignment.
227
MatrixElement operator[](size_type c)
229
assert(c >= 0 && c < maxColumns);
230
return MatrixElement(C, Row, c);
234
size_type Row, maxColumns;
238
/* The index operator of the sparseMatrix class returns the
239
auxiliary object, whose class is defined as nested inside
241
Aux operator[](size_type r)
243
assert(r >= 0 && r < rows);
244
return Aux(r, columns, C);
247
/* Up to this point, from a functionality point of view, the
248
sparseMatrix class is sufficiently equipped. In order, however,
249
to avoid writing such horrible things as `(*I).first.first' for
250
accessing the elements, some auxiliary functions follow which
251
determine the indices and associated values of an iterator in a
252
more readable way. */
254
size_type Index1(iterator& I) const
256
return (*I).first.first;
259
size_type Index2(iterator& I) const
261
return (*I).first.second;
264
ValueType Value(iterator& I) const
268
}; // class sparseMatrix
270
#endif // file sparmat.h
added
removed
src/terralib/kernel/TeSparseMatrix.h
