1
// -*- mode: C++; tab-width: 2; -*-
4
// --------------------------------------------------------------------------
5
// OpenMS Mass Spectrometry Framework
6
// --------------------------------------------------------------------------
7
// Copyright (C) 2003-2011 -- Oliver Kohlbacher, Knut Reinert
9
// This library is free software; you can redistribute it and/or
10
// modify it under the terms of the GNU Lesser General Public
11
// License as published by the Free Software Foundation; either
12
// version 2.1 of the License, or (at your option) any later version.
14
// This library is distributed in the hope that it will be useful,
15
// but WITHOUT ANY WARRANTY; without even the implied warranty of
16
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17
// Lesser General Public License for more details.
19
// You should have received a copy of the GNU Lesser General Public
20
// License along with this library; if not, write to the Free Software
21
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23
// --------------------------------------------------------------------------
24
// $Maintainer: Mathias Walzer $
26
// --------------------------------------------------------------------------
28
#ifndef OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
29
#define OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
31
#include <OpenMS/CONCEPT/Macros.h>
32
#include <OpenMS/CONCEPT/Types.h>
43
@brief A two-dimensional distance matrix, similar to OpenMS::Matrix
45
similar to OpenMS::Matrix, but contains only elements above the main diagonal, hence translating access with operator(,) for elements of above the main diagonal to corresponing elements below the main diagonal and returning 0 for requested elements in the main diagonal, since selfdistance is assumed to be 0. Keeps track of the minimal element in the Matrix with OpenMS::DistanceMatrix::min_element_ if only for setting a value OpenMS::DistanceMatrix::setValue is used. Other OpenMS::DistanceMatrix altering methods may require a maual update by call of OpenMS::DistanceMatrix::updateMinElement, see the respective methods documentation.
47
@ingroup Datastructures
49
template <typename Value>
55
///@name STL compliance type definitions
57
typedef Value value_type;
60
///@name OpenMS compliance type definitions
62
typedef Size SizeType;
63
typedef value_type ValueType;
66
/** @brief default constructor
69
DistanceMatrix () : matrix_(0), init_size_(0), dimensionsize_(0), min_element_(0,0)
73
/** @brief detailed constructor
75
@param dimensionsize the number of rows (and therewith cols)
76
@param value DistanceMatrix will be filled with this element (main diagonal will still "hold" only zeros)
77
@throw Exception::OutOfMemory if requested dimensionsize is to big to fit into memory
79
DistanceMatrix (SizeType dimensionsize, Value value = Value())
80
: matrix_(new ValueType*[dimensionsize]), init_size_(dimensionsize), dimensionsize_(dimensionsize), min_element_(0,0)
84
for (i = 1; i < dimensionsize; ++i)
86
matrix_[i] = new ValueType[i];
90
for (i = 1; i < j; i++)
98
throw Exception::OutOfMemory(__FILE__,__LINE__,__PRETTY_FUNCTION__,(UInt)((((dimensionsize-2)*(dimensionsize-1))/2)*sizeof(ValueType)));
103
for(i = 1; i < dimensionsize; ++i)
105
for(SizeType j = 0; j< i; ++j)
110
min_element_ = std::make_pair(1,0);
114
/** @brief copy constructor
116
@param source this DistanceMatrix will be copied
117
@throw Exception::OutOfMemory if requested dimensionsize is to big to fit into memory
119
DistanceMatrix (const DistanceMatrix& source)
120
: matrix_(new ValueType*[source.dimensionsize_]),
121
init_size_(source.dimensionsize_),
122
dimensionsize_(source.dimensionsize_),
123
min_element_(source.min_element_)
127
for (i = 1; i < dimensionsize_; ++i)
129
matrix_[i] = new ValueType[i];
130
if (matrix_[i]==NULL)
133
for (i = 1; i < j; i++)
141
min_element_ = std::make_pair(0,0);
142
throw Exception::OutOfMemory(__FILE__,__LINE__,__PRETTY_FUNCTION__,(UInt)((((dimensionsize_-2)*(dimensionsize_-1))/2)*sizeof(ValueType)));
147
for(i = 1; i < dimensionsize_; ++i)
149
std::copy(source.matrix_[i],source.matrix_[i]+i,matrix_[i]);
157
for (SizeType i = 1; i < init_size_; i++)
164
/** @brief gets a value at a given position (read only):
166
@param i the i-th row
167
@param j the j-th col
169
const ValueType operator() (SizeType i, SizeType j) const
171
return getValue(i,j);
174
/** @brief gets a value at a given position (read only):
176
@param i the i-th row
177
@param j the j-th col
179
ValueType operator() (SizeType i, SizeType j)
181
return getValue(i,j);
184
/** @brief gets a value at a given position:
186
@param i the i-th row
187
@param j the j-th col
188
@throw Exception::OutOfRange if given coordinates are out of range
190
const ValueType getValue(SizeType i, SizeType j) const
192
if(i>=dimensionsize_ || j >= dimensionsize_)
194
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
196
// elements on main diagonal are not stored and assumed to be 0
205
return (const ValueType)(matrix_[i][j]);
208
/** @brief gets a value at a given position:
210
@param i the i-th row
211
@param j the j-th col
212
@throw Exception::OutOfRange if given coordinates are out of range
214
ValueType getValue(SizeType i, SizeType j)
216
if(i>=dimensionsize_ || j >= dimensionsize_)
218
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
220
// elements on main diagonal are not stored and assumed to be 0
229
return matrix_[i][j];
232
/** @brief sets a value at a given position:
234
@param i the i-th row
235
@param j the j-th col
236
@param value the set-value
237
@throw Exception::OutOfRange if given coordinates are out of range
239
void setValue(SizeType i, SizeType j, ValueType value)
241
if(i>=dimensionsize_ || j >= dimensionsize_)
243
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
245
// elements on main diagonal are not stored and assumed to be 0
252
if(i!=min_element_.first && j!=min_element_.second)
254
matrix_[i][j] = value;
255
if(value < matrix_[min_element_.first][min_element_.second]) // keep min_element_ up-to-date
257
min_element_ = std::make_pair(i,j);
262
if(value <= matrix_[min_element_.first][min_element_.second])
264
matrix_[i][j] = value;
268
matrix_[i][j] = value;
275
/** @brief sets a value at a given position:
277
@param i the i-th row
278
@param j the j-th col
279
@param value the set-value
280
@throw Exception::OutOfRange if given coordinates are out of range
282
possible invalidation of min_element_ - make sure to update before further usage of matrix
284
void setValueQuick(SizeType i, SizeType j, ValueType value)
286
if(i>=dimensionsize_ || j >= dimensionsize_)
288
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
290
// elements on main diagonal are not stored and assumed to be 0
297
matrix_[i][j] = value;
304
for (SizeType i = 1; i < init_size_; i++)
310
min_element_ = std::make_pair(0,0);
315
/** @brief resizing the container
317
@param dimensionsize the desired number of rows (and therewith cols)
318
@param value which the matrix will be filled with
319
@throw Exception::OutOfMemory thrown if size of DistanceMatrix requested does not fit into memory
321
invalidates all content
323
void resize(SizeType dimensionsize, Value value = Value())
325
for (SizeType j = 1; j < init_size_; j++)
330
dimensionsize_ = dimensionsize;
331
init_size_ = dimensionsize;
332
min_element_ = std::make_pair(0,0);
333
matrix_ = new ValueType*[dimensionsize_];
334
for (SizeType j = 1; j < dimensionsize_; ++j)
336
matrix_[j] = new ValueType[j];
337
if (matrix_[j]==NULL)
339
for (SizeType k = 1; k < j; ++k)
347
throw Exception::OutOfMemory(__FILE__,__LINE__,__PRETTY_FUNCTION__,(UInt)((((dimensionsize_-2)*(dimensionsize_-1))/2)*sizeof(Value)));
352
for(SizeType j = 0; j < dimensionsize; ++j)
354
for(SizeType k = 0; k< j; ++k)
359
min_element_ = std::make_pair(1,0);
363
/** @brief reduces DistanceMatrix by one dimension. first the jth row, then jth column
365
@param j the jth row (and therewith also jth col) to be removed
366
@throw Exception::OutOfRange if @p j is grater than the greatest row number
368
may invalidates min_element_, make sure to update min_element_ if neccessary before used
370
void reduce(SizeType j)
372
if(j >= dimensionsize_)
374
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
376
//delete row j and therefor overwrite with row j+1 and iterate like this to last row
378
while(i < dimensionsize_ && matrix_[i] != NULL)
380
//left out in the copy is each rows jth element, pointer working here as iterators just fine
381
std::copy(matrix_[i]+j+1,matrix_[i]+i,std::copy(matrix_[i],matrix_[i]+j,matrix_[i-1]));
384
//last row is freed and the pointer set to NULL (outer array's size is not changed)
385
delete[] matrix_[i-1];
390
/// gives the number of rows (i.e. number of columns)
391
SizeType dimensionsize() const
393
return dimensionsize_;
396
/** @brief keep track of the actual minimum element after altering the matrix
398
@throw Exception::OutOfRange thrown if there is no element to access
400
void updateMinElement()
402
min_element_ = std::make_pair(1,0);
403
//error if dimensionsize_<1, return if dimensionsize_ == 1, else
404
if(dimensionsize_ < 1)
406
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
408
if(dimensionsize_!=1) //else matrix has one element: (1,0)
411
for(SizeType r = 2; r < dimensionsize_ && matrix_[r]!=NULL; ++r)
413
row_min_ = std::min_element(matrix_[r],matrix_[r]+r);
414
if(*row_min_ < matrix_[min_element_.first][min_element_.second])
416
min_element_ = std::make_pair(r,row_min_ - matrix_[r]);
424
/**@brief Equality comparator.
426
@throw Exception::Precondition thrown if given DistanceMatrix is not compatible in size
428
bool operator== ( DistanceMatrix<ValueType> const & rhs ) const
430
OPENMS_PRECONDITION(dimensionsize_ == rhs.dimensionsize_,"DistanceMatrices have different sizes.");
431
for (Size i = 1; i < rhs.dimensionsize(); ++i)
433
for (Size j = 0; j < i; ++j)
435
if(matrix_[i][j]!=rhs.matrix_[i][j])
445
/** @brief Indexpair of minimal element
447
@throw Exception::OutOfRange thrown if there is no element to access
449
std::pair<SizeType,SizeType> getMinElementCoordinates() const
451
if ( dimensionsize_ == 0 )
453
throw Exception::OutOfRange(__FILE__,__LINE__,__PRETTY_FUNCTION__);
459
/// sparse element not to be included in base container
461
/// number of actually stored rows
462
SizeType init_size_; // actual size of outer array
463
/// number of accessably stored rows (i.e. number of columns)
464
SizeType dimensionsize_; //number of virtual elements: ((dimensionsize-1)*(dimensionsize))/2
465
/// index of minimal element(i.e. number in underlying SparseVector)
466
std::pair<SizeType,SizeType> min_element_;
469
/// assignment operator (unsafe)
470
DistanceMatrix& operator= (const DistanceMatrix& rhs)
472
matrix_= rhs.matrix_;
473
init_size_= rhs.init_size_;
474
dimensionsize_ = rhs.dimensionsize_;
475
min_element_ = rhs.min_element_;
481
}; // class DistanceMatrix
483
/**@brief Print the contents to a stream.
485
@relatesalso DistanceMatrix
487
template <typename Value>
488
std::ostream& operator<< (std::ostream& os, const DistanceMatrix<Value>& matrix)
490
typedef typename DistanceMatrix<Value>::SizeType SizeType;
492
std::ios_base::fmtflags flag_backup = os.setf(std::ios::scientific);
493
std::streamsize precision_backup = os.precision();
494
//~ os.precision(15);
495
os.precision(writtenDigits<DoubleReal>()); // #include <OpenMS/CONCEPT/Types.h>
497
//evtl. color lower triangular matrix o.s.l.t.
498
for ( SizeType i = 0; i < matrix.dimensionsize(); ++i ) {
499
for ( SizeType j = 0; j < matrix.dimensionsize(); ++j ) {
500
os << matrix(i,j) << '\t';
504
os.flags(flag_backup);
505
os.precision(precision_backup);
510
} // namespace OpenMS
512
#endif // OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
added
removed
include/OpenMS/DATASTRUCTURES/DistanceMatrix.h
