OpenMS
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-2023.
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>
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>
68  {
69 public:
70 
72 
73  typedef Value value_type;
75 
77 
78  typedef Size SizeType;
81 
86  matrix_(nullptr), init_size_(0), dimensionsize_(0), min_element_(0, 0)
87  {
88  }
89 
97  DistanceMatrix(SizeType dimensionsize, Value value = Value()) :
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 
139  matrix_(new ValueType*[source.dimensionsize_]),
140  init_size_(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 
175  {
176  for (SizeType i = 1; i < init_size_; i++)
177  {
178  delete[] matrix_[i];
179  }
180  delete[] matrix_;
181  }
182 
190  {
191  return getValue(i, j);
192  }
193 
201  {
202  return getValue(i, j);
203  }
204 
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 
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 
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;
294  }
295  }
296  }
297  }
298 
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_;
358  min_element_ = std::make_pair(0, 0);
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 
419  {
420  return dimensionsize_;
421  }
422 
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:
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:
498  {
499  matrix_ = rhs.matrix_;
500  init_size_ = rhs.init_size_;
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 
A two-dimensional distance matrix, similar to OpenMS::Matrix.
Definition: DistanceMatrix.h:68
SizeType dimensionsize() const
gives the number of rows (i.e. number of columns)
Definition: DistanceMatrix.h:418
Value value_type
Definition: DistanceMatrix.h:73
std::ostream & operator<<(std::ostream &os, const DistanceMatrix< Value > &matrix)
Print the contents to a stream.
Definition: DistanceMatrix.h:515
DistanceMatrix()
default constructor
Definition: DistanceMatrix.h:85
bool operator==(DistanceMatrix< ValueType > const &rhs) const
Equality comparator.
Definition: DistanceMatrix.h:455
void setValue(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:263
void updateMinElement()
keep track of the actual minimum element after altering the matrix
Definition: DistanceMatrix.h:428
std::pair< SizeType, SizeType > getMinElementCoordinates() const
Indexpair of minimal element.
Definition: DistanceMatrix.h:476
const ValueType getValue(SizeType i, SizeType j) const
gets a value at a given position:
Definition: DistanceMatrix.h:212
ValueType getValue(SizeType i, SizeType j)
gets a value at a given position:
Definition: DistanceMatrix.h:237
const ValueType operator()(SizeType i, SizeType j) const
gets a value at a given position (read only):
Definition: DistanceMatrix.h:189
DistanceMatrix(const DistanceMatrix &source)
copy constructor
Definition: DistanceMatrix.h:138
Size SizeType
Definition: DistanceMatrix.h:78
std::pair< SizeType, SizeType > min_element_
index of minimal element(i.e. number in underlying SparseVector)
Definition: DistanceMatrix.h:493
ValueType operator()(SizeType i, SizeType j)
gets a value at a given position (read only):
Definition: DistanceMatrix.h:200
ValueType ** matrix_
sparse element not to be included in base container
Definition: DistanceMatrix.h:487
void setValueQuick(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:309
value_type ValueType
Definition: DistanceMatrix.h:79
~DistanceMatrix()
destructor
Definition: DistanceMatrix.h:174
SizeType init_size_
number of actually stored rows
Definition: DistanceMatrix.h:489
DistanceMatrix(SizeType dimensionsize, Value value=Value())
detailed constructor
Definition: DistanceMatrix.h:97
DistanceMatrix & operator=(const DistanceMatrix &rhs)
assignment operator (unsafe)
Definition: DistanceMatrix.h:497
void clear()
reset all
Definition: DistanceMatrix.h:327
SizeType dimensionsize_
number of accessibly stored rows (i.e. number of columns)
Definition: DistanceMatrix.h:491
void resize(SizeType dimensionsize, Value value=Value())
resizing the container
Definition: DistanceMatrix.h:349
void reduce(SizeType j)
reduces DistanceMatrix by one dimension. first the jth row, then jth column
Definition: DistanceMatrix.h:397
Out of memory exception.
Definition: Exception.h:461
Out of range exception.
Definition: Exception.h:313
unsigned int UInt
Unsigned integer type.
Definition: Types.h:94
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:127
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: openms/include/OpenMS/CONCEPT/Macros.h:120
const double k
Definition: Constants.h:158
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:48
constexpr Int writtenDigits< double >(const double &)
Number of digits commonly used for writing a double (a.k.a. precision).
Definition: Types.h:219