| OpenMS 2.5.0

DistanceMatrix.h
Go to the documentation of this file.
1 // --------------------------------------------------------------------------
2 // OpenMS -- Open-Source Mass Spectrometry
3 // --------------------------------------------------------------------------
4 // Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
5 // ETH Zurich, and Freie Universitaet Berlin 2002-2020.
6 //
7 // This software is released under a three-clause BSD license:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of any author or any participating institution
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 // For a full list of authors, refer to the file AUTHORS.
17 // --------------------------------------------------------------------------
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
22 // INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // --------------------------------------------------------------------------
31 // $Maintainer: Mathias Walzer $
32 // $Authors: $
33 // --------------------------------------------------------------------------
34
35 #pragma once
36
37 #include <OpenMS/CONCEPT/Macros.h>
38 #include <OpenMS/CONCEPT/Types.h>
39 #include <OpenMS/CONCEPT/Exception.h>
40 #include <OpenMS/config.h>
41
42 #include <algorithm>
43 #include <cmath>
44 #include <iomanip>
45 #include <iostream>
46
47 namespace OpenMS
48 {
49
66 template <typename Value>
67 class DistanceMatrix
68 {
69 public:
70
72
73 typedef Value value_type;
75
77
78 typedef Size SizeType;
79 typedef value_type ValueType;
81
85 DistanceMatrix() :
86 matrix_(nullptr), init_size_(0), dimensionsize_(0), min_element_(0, 0)
87 {
88 }
89
97 DistanceMatrix(SizeType dimensionsize, Value value = Value()) :
98 matrix_(new ValueType*[dimensionsize]), init_size_(dimensionsize), dimensionsize_(dimensionsize), min_element_(0, 0)
99 {
100 matrix_[0] = NULL;
101 SizeType i = 1;
102 for (i = 1; i < dimensionsize; ++i)
103 {
104 matrix_[i] = new ValueType[i];
105 if (matrix_[i] == NULL)
106 {
107 SizeType j = i;
108 for (i = 1; i < j; i++)
109 {
110 delete[] matrix_[i];
111 }
112 delete[] matrix_;
113 matrix_ = NULL;
114 dimensionsize_ = 0;
115 init_size_ = 0;
116 throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize - 2) * (dimensionsize - 1)) / 2) * sizeof(ValueType)));
117 }
118 }
119 if (matrix_ != NULL)
120 {
121 for (i = 1; i < dimensionsize; ++i)
122 {
123 for (SizeType j = 0; j < i; ++j)
124 {
125 matrix_[i][j] = value;
126 }
127 }
128 min_element_ = std::make_pair(1, 0);
129 }
130 }
131
138 DistanceMatrix(const DistanceMatrix& source) :
139 matrix_(new ValueType*[source.dimensionsize_]),
140 init_size_(source.dimensionsize_),
141 dimensionsize_(source.dimensionsize_),
142 min_element_(source.min_element_)
143 {
144 matrix_[0] = NULL;
145 SizeType i = 1;
146 for (i = 1; i < dimensionsize_; ++i)
147 {
148 matrix_[i] = new ValueType[i];
149 if (matrix_[i] == NULL)
150 {
151 SizeType j = i;
152 for (i = 1; i < j; i++)
153 {
154 delete[] matrix_[i];
155 }
156 delete[] matrix_;
157 matrix_ = NULL;
158 dimensionsize_ = 0;
159 init_size_ = 0;
160 min_element_ = std::make_pair(0, 0);
161 throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(ValueType)));
162 }
163 }
164 if (matrix_ != NULL)
165 {
166 for (i = 1; i < dimensionsize_; ++i)
167 {
168 std::copy(source.matrix_[i], source.matrix_[i] + i, matrix_[i]);
169 }
170 }
171 }
172
174 ~DistanceMatrix()
175 {
176 for (SizeType i = 1; i < init_size_; i++)
177 {
178 delete[] matrix_[i];
179 }
180 delete[] matrix_;
181 }
182
189 const ValueType operator()(SizeType i, SizeType j) const
190 {
191 return getValue(i, j);
192 }
193
200 ValueType operator()(SizeType i, SizeType j)
201 {
202 return getValue(i, j);
203 }
204
212 const ValueType getValue(SizeType i, SizeType j) const
213 {
214 if (i >= dimensionsize_ || j >= dimensionsize_)
215 {
216 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
217 }
218 // elements on main diagonal are not stored and assumed to be 0
219 if (i == j)
220 {
221 return 0;
222 }
223 if (i < j)
224 {
225 std::swap(i, j);
226 }
227 return (const ValueType)(matrix_[i][j]);
228 }
229
237 ValueType getValue(SizeType i, SizeType j)
238 {
239 if (i >= dimensionsize_ || j >= dimensionsize_)
240 {
241 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
242 }
243 // elements on main diagonal are not stored and assumed to be 0
244 if (i == j)
245 {
246 return 0;
247 }
248 if (i < j)
249 {
250 std::swap(i, j);
251 }
252 return matrix_[i][j];
253 }
254
263 void setValue(SizeType i, SizeType j, ValueType value)
264 {
265 if (i >= dimensionsize_ || j >= dimensionsize_)
266 {
267 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
268 }
269 // elements on main diagonal are not stored and assumed to be 0
270 if (i != j)
271 {
272 if (i < j)
273 {
274 std::swap(i, j);
275 }
276 if (i != min_element_.first && j != min_element_.second)
277 {
278 matrix_[i][j] = value;
279 if (value < matrix_[min_element_.first][min_element_.second]) // keep min_element_ up-to-date
280 {
281 min_element_ = std::make_pair(i, j);
282 }
283 }
284 else
285 {
286 if (value <= matrix_[min_element_.first][min_element_.second])
287 {
288 matrix_[i][j] = value;
289 }
290 else
291 {
292 matrix_[i][j] = value;
293 updateMinElement();
294 }
295 }
296 }
297 }
298
309 void setValueQuick(SizeType i, SizeType j, ValueType value)
310 {
311 if (i >= dimensionsize_ || j >= dimensionsize_)
312 {
313 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
314 }
315 // elements on main diagonal are not stored and assumed to be 0
316 if (i != j)
317 {
318 if (i < j)
319 {
320 std::swap(i, j);
321 }
322 matrix_[i][j] = value;
323 }
324 }
325
327 void clear()
328 {
329 for (SizeType i = 1; i < init_size_; i++)
330 {
331 delete[] matrix_[i];
332 }
333 delete[] matrix_;
334 matrix_ = nullptr;
335 min_element_ = std::make_pair(0, 0);
336 dimensionsize_ = 0;
337 init_size_ = 0;
338 }
339
349 void resize(SizeType dimensionsize, Value value = Value())
350 {
351 for (SizeType j = 1; j < init_size_; j++)
352 {
353 delete[] matrix_[j];
354 }
355 delete[] matrix_;
356 dimensionsize_ = dimensionsize;
357 init_size_ = dimensionsize;
358 min_element_ = std::make_pair(0, 0);
359 matrix_ = new ValueType*[dimensionsize_];
360 for (SizeType j = 1; j < dimensionsize_; ++j)
361 {
362 matrix_[j] = new ValueType[j];
363 if (matrix_[j] == nullptr)
364 {
365 for (SizeType k = 1; k < j; ++k)
366 {
367 delete[] matrix_[k];
368 }
369 delete[] matrix_;
370 matrix_ = nullptr;
371 dimensionsize_ = 0;
372 init_size_ = 0;
373 throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(Value)));
374 }
375 }
376 if (matrix_ != nullptr)
377 {
378 for (SizeType j = 0; j < dimensionsize; ++j)
379 {
380 for (SizeType k = 0; k < j; ++k)
381 {
382 matrix_[j][k] = value;
383 }
384 }
385 min_element_ = std::make_pair(1, 0);
386 }
387 }
388
397 void reduce(SizeType j)
398 {
399 if (j >= dimensionsize_)
400 {
401 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
402 }
403 //delete row j and therefor overwrite with row j+1 and iterate like this to last row
404 SizeType i = j + 1;
405 while (i < dimensionsize_ && matrix_[i] != nullptr)
406 {
407 //left out in the copy is each rows jth element, pointer working here as iterators just fine
408 std::copy(matrix_[i] + j + 1, matrix_[i] + i, std::copy(matrix_[i], matrix_[i] + j, matrix_[i - 1]));
409 ++i;
410 }
411 //last row is freed and the pointer set to NULL (outer array's size is not changed)
412 delete[] matrix_[i - 1];
413 matrix_[i - 1] = nullptr;
414 --dimensionsize_;
415 }
416
418 SizeType dimensionsize() const
419 {
420 return dimensionsize_;
421 }
422
428 void updateMinElement()
429 {
430 min_element_ = std::make_pair(1, 0);
431 //error if dimensionsize_<1, return if dimensionsize_ == 1, else
432 if (dimensionsize_ < 1)
433 {
434 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
435 }
436 if (dimensionsize_ != 1) //else matrix has one element: (1,0)
437 {
438 ValueType* row_min_;
439 for (SizeType r = 2; r < dimensionsize_ && matrix_[r] != nullptr; ++r)
440 {
441 row_min_ = std::min_element(matrix_[r], matrix_[r] + r);
442 if (*row_min_ < matrix_[min_element_.first][min_element_.second])
443 {
444 min_element_ = std::make_pair(r, row_min_ - matrix_[r]);
445 }
446 }
447 }
448 }
449
455 bool operator==(DistanceMatrix<ValueType> const& rhs) const
456 {
457 OPENMS_PRECONDITION(dimensionsize_ == rhs.dimensionsize_, "DistanceMatrices have different sizes.");
458 for (Size i = 1; i < rhs.dimensionsize(); ++i)
459 {
460 for (Size j = 0; j < i; ++j)
461 {
462 if (matrix_[i][j] != rhs.matrix_[i][j])
463 {
464 return false;
465 }
466 }
467 }
468 return true;
469 }
470
476 std::pair<SizeType, SizeType> getMinElementCoordinates() const
477 {
478 if (dimensionsize_ == 0)
479 {
480 throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
481 }
482 return min_element_;
483 }
484
485 protected:
487 ValueType** matrix_;
489 SizeType init_size_; // actual size of outer array
491 SizeType dimensionsize_; //number of virtual elements: ((dimensionsize-1)*(dimensionsize))/2
493 std::pair<SizeType, SizeType> min_element_;
494
495 private:
497 DistanceMatrix& operator=(const DistanceMatrix& rhs)
498 {
499 matrix_ = rhs.matrix_;
500 init_size_ = rhs.init_size_;
501 dimensionsize_ = rhs.dimensionsize_;
502 min_element_ = rhs.min_element_;
503
504 return *this;
505 }
506
507 }; // class DistanceMatrix
508
514 template <typename Value>
515 std::ostream& operator<<(std::ostream& os, const DistanceMatrix<Value>& matrix)
516 {
517 typedef typename DistanceMatrix<Value>::SizeType SizeType;
518
519 std::ios_base::fmtflags flag_backup = os.setf(std::ios::scientific);
520 std::streamsize precision_backup = os.precision();
521 //~ os.precision(15);
522 os.precision(writtenDigits<double>(0.0)); // #include <OpenMS/CONCEPT/Types.h>
523
524 //evtl. color lower triangular matrix o.s.l.t.
525 for (SizeType i = 0; i < matrix.dimensionsize(); ++i)
526 {
527 for (SizeType j = 0; j < matrix.dimensionsize(); ++j)
528 {
529 os << matrix(i, j) << '\t';
530 }
531 os << std::endl;
532 }
533 os.flags(flag_backup);
534 os.precision(precision_backup);
535 return os;
536 }
537
538 } // namespace OpenMS
539
OpenMS::DistanceMatrix::min_element_
std::pair< SizeType, SizeType > min_element_
index of minimal element(i.e. number in underlying SparseVector)
Definition: DistanceMatrix.h:493
OpenMS::DistanceMatrix::DistanceMatrix
DistanceMatrix(SizeType dimensionsize, Value value=Value())
detailed constructor
Definition: DistanceMatrix.h:97
OpenMS::DistanceMatrix::getValue
const ValueType getValue(SizeType i, SizeType j) const
gets a value at a given position:
Definition: DistanceMatrix.h:212
OpenMS::DistanceMatrix::SizeType
Size SizeType
Definition: DistanceMatrix.h:78
OpenMS::DistanceMatrix::matrix_
ValueType ** matrix_
sparse element not to be included in base container
Definition: DistanceMatrix.h:487
OpenMS::DistanceMatrix::setValue
void setValue(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:263
OpenMS::Constants::k
const double k
OpenMS::DistanceMatrix::~DistanceMatrix
~DistanceMatrix()
destructor
Definition: DistanceMatrix.h:174
OpenMS::DistanceMatrix::value_type
Value value_type
Definition: DistanceMatrix.h:73
OpenMS::Exception::OutOfRange
Out of range exception.
Definition: Exception.h:319
Exception.h
OpenMS::DistanceMatrix::operator()
ValueType operator()(SizeType i, SizeType j)
gets a value at a given position (read only):
Definition: DistanceMatrix.h:200
OpenMS::DistanceMatrix::dimensionsize
SizeType dimensionsize() const
gives the number of rows (i.e. number of columns)
Definition: DistanceMatrix.h:418
OpenMS::DistanceMatrix::operator()
const ValueType operator()(SizeType i, SizeType j) const
gets a value at a given position (read only):
Definition: DistanceMatrix.h:189
OpenMS::DistanceMatrix::getValue
ValueType getValue(SizeType i, SizeType j)
gets a value at a given position:
Definition: DistanceMatrix.h:237
Types.h
OpenMS::DistanceMatrix::resize
void resize(SizeType dimensionsize, Value value=Value())
resizing the container
Definition: DistanceMatrix.h:349
OpenMS::DistanceMatrix::init_size_
SizeType init_size_
number of actually stored rows
Definition: DistanceMatrix.h:489
OpenMS::DistanceMatrix
A two-dimensional distance matrix, similar to OpenMS::Matrix.
Definition: DistanceMatrix.h:67
OpenMS::DistanceMatrix::operator==
bool operator==(DistanceMatrix< ValueType > const &rhs) const
Equality comparator.
Definition: DistanceMatrix.h:455
OpenMS::writtenDigits< double >
constexpr Int writtenDigits< double >(const double &)
Number of digits commonly used for writing a double (a.k.a. precision).
Definition: Types.h:219
OPENMS_PRECONDITION
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: openms/include/OpenMS/CONCEPT/Macros.h:136
OpenMS
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:46
OpenMS::DistanceMatrix::reduce
void reduce(SizeType j)
reduces DistanceMatrix by one dimension. first the jth row, then jth column
Definition: DistanceMatrix.h:397
OpenMS::DistanceMatrix::DistanceMatrix
DistanceMatrix(const DistanceMatrix &source)
copy constructor
Definition: DistanceMatrix.h:138
OpenMS::UInt
unsigned int UInt
Unsigned integer type.
Definition: Types.h:94
OpenMS::DistanceMatrix::DistanceMatrix
DistanceMatrix()
default constructor
Definition: DistanceMatrix.h:85
OpenMS::DistanceMatrix::getMinElementCoordinates
std::pair< SizeType, SizeType > getMinElementCoordinates() const
Indexpair of minimal element.
Definition: DistanceMatrix.h:476
Value
OpenMS::DistanceMatrix::dimensionsize_
SizeType dimensionsize_
number of accessibly stored rows (i.e. number of columns)
Definition: DistanceMatrix.h:491
Macros.h
OpenMS::DistanceMatrix::setValueQuick
void setValueQuick(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:309
OpenMS::DistanceMatrix::operator=
DistanceMatrix & operator=(const DistanceMatrix &rhs)
assignment operator (unsafe)
Definition: DistanceMatrix.h:497
OpenMS::DistanceMatrix::ValueType
value_type ValueType
Definition: DistanceMatrix.h:79
OpenMS::DistanceMatrix::updateMinElement
void updateMinElement()
keep track of the actual minimum element after altering the matrix
Definition: DistanceMatrix.h:428
OpenMS::DistanceMatrix::clear
void clear()
reset all
Definition: DistanceMatrix.h:327
OpenMS::Size
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:127
OpenMS::Exception::OutOfMemory
Out of memory exception.
Definition: Exception.h:471