Home  · Classes  · Annotated Classes  · Modules  · Members  · Namespaces  · Related Pages
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-2017.
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 #ifndef OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
36 #define OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
37 
38 #include <OpenMS/CONCEPT/Macros.h>
39 #include <OpenMS/CONCEPT/Types.h>
41 #include <OpenMS/config.h>
42 
43 #include <algorithm>
44 #include <cmath>
45 #include <iomanip>
46 #include <iostream>
47 
48 namespace OpenMS
49 {
50 
67  template <typename Value>
69  {
70 public:
71 
73 
74  typedef Value value_type;
76 
78 
79  typedef Size SizeType;
80  typedef value_type ValueType;
82 
88  {
89  }
90 
98  DistanceMatrix(SizeType dimensionsize, Value value = Value()) :
99  matrix_(new ValueType*[dimensionsize]), init_size_(dimensionsize), dimensionsize_(dimensionsize), min_element_(0, 0)
100  {
101  matrix_[0] = NULL;
102  SizeType i = 1;
103  for (i = 1; i < dimensionsize; ++i)
104  {
105  matrix_[i] = new ValueType[i];
106  if (matrix_[i] == NULL)
107  {
108  SizeType j = i;
109  for (i = 1; i < j; i++)
110  {
111  delete[] matrix_[i];
112  }
113  delete[] matrix_;
114  matrix_ = NULL;
115  dimensionsize_ = 0;
116  init_size_ = 0;
117  throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize - 2) * (dimensionsize - 1)) / 2) * sizeof(ValueType)));
118  }
119  }
120  if (matrix_ != NULL)
121  {
122  for (i = 1; i < dimensionsize; ++i)
123  {
124  for (SizeType j = 0; j < i; ++j)
125  {
126  matrix_[i][j] = value;
127  }
128  }
129  min_element_ = std::make_pair(1, 0);
130  }
131  }
132 
140  matrix_(new ValueType*[source.dimensionsize_]),
141  init_size_(source.dimensionsize_),
143  min_element_(source.min_element_)
144  {
145  matrix_[0] = NULL;
146  SizeType i = 1;
147  for (i = 1; i < dimensionsize_; ++i)
148  {
149  matrix_[i] = new ValueType[i];
150  if (matrix_[i] == NULL)
151  {
152  SizeType j = i;
153  for (i = 1; i < j; i++)
154  {
155  delete[] matrix_[i];
156  }
157  delete[] matrix_;
158  matrix_ = NULL;
159  dimensionsize_ = 0;
160  init_size_ = 0;
161  min_element_ = std::make_pair(0, 0);
162  throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(ValueType)));
163  }
164  }
165  if (matrix_ != NULL)
166  {
167  for (i = 1; i < dimensionsize_; ++i)
168  {
169  std::copy(source.matrix_[i], source.matrix_[i] + i, matrix_[i]);
170  }
171  }
172  }
173 
176  {
177  for (SizeType i = 1; i < init_size_; i++)
178  {
179  delete[] matrix_[i];
180  }
181  delete[] matrix_;
182  }
183 
190  const ValueType operator()(SizeType i, SizeType j) const
191  {
192  return getValue(i, j);
193  }
194 
201  ValueType operator()(SizeType i, SizeType j)
202  {
203  return getValue(i, j);
204  }
205 
213  const ValueType getValue(SizeType i, SizeType j) const
214  {
215  if (i >= dimensionsize_ || j >= dimensionsize_)
216  {
217  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
218  }
219  // elements on main diagonal are not stored and assumed to be 0
220  if (i == j)
221  {
222  return 0;
223  }
224  if (i < j)
225  {
226  std::swap(i, j);
227  }
228  return (const ValueType)(matrix_[i][j]);
229  }
230 
238  ValueType getValue(SizeType i, SizeType j)
239  {
240  if (i >= dimensionsize_ || j >= dimensionsize_)
241  {
242  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
243  }
244  // elements on main diagonal are not stored and assumed to be 0
245  if (i == j)
246  {
247  return 0;
248  }
249  if (i < j)
250  {
251  std::swap(i, j);
252  }
253  return matrix_[i][j];
254  }
255 
264  void setValue(SizeType i, SizeType j, ValueType value)
265  {
266  if (i >= dimensionsize_ || j >= dimensionsize_)
267  {
268  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
269  }
270  // elements on main diagonal are not stored and assumed to be 0
271  if (i != j)
272  {
273  if (i < j)
274  {
275  std::swap(i, j);
276  }
277  if (i != min_element_.first && j != min_element_.second)
278  {
279  matrix_[i][j] = value;
280  if (value < matrix_[min_element_.first][min_element_.second]) // keep min_element_ up-to-date
281  {
282  min_element_ = std::make_pair(i, j);
283  }
284  }
285  else
286  {
287  if (value <= matrix_[min_element_.first][min_element_.second])
288  {
289  matrix_[i][j] = value;
290  }
291  else
292  {
293  matrix_[i][j] = value;
295  }
296  }
297  }
298  }
299 
310  void setValueQuick(SizeType i, SizeType j, ValueType value)
311  {
312  if (i >= dimensionsize_ || j >= dimensionsize_)
313  {
314  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
315  }
316  // elements on main diagonal are not stored and assumed to be 0
317  if (i != j)
318  {
319  if (i < j)
320  {
321  std::swap(i, j);
322  }
323  matrix_[i][j] = value;
324  }
325  }
326 
328  void clear()
329  {
330  for (SizeType i = 1; i < init_size_; i++)
331  {
332  delete[] matrix_[i];
333  }
334  delete[] matrix_;
335  matrix_ = NULL;
336  min_element_ = std::make_pair(0, 0);
337  dimensionsize_ = 0;
338  init_size_ = 0;
339  }
340 
350  void resize(SizeType dimensionsize, Value value = Value())
351  {
352  for (SizeType j = 1; j < init_size_; j++)
353  {
354  delete[] matrix_[j];
355  }
356  delete[] matrix_;
358  init_size_ = dimensionsize;
359  min_element_ = std::make_pair(0, 0);
360  matrix_ = new ValueType*[dimensionsize_];
361  for (SizeType j = 1; j < dimensionsize_; ++j)
362  {
363  matrix_[j] = new ValueType[j];
364  if (matrix_[j] == NULL)
365  {
366  for (SizeType k = 1; k < j; ++k)
367  {
368  delete[] matrix_[k];
369  }
370  delete[] matrix_;
371  matrix_ = NULL;
372  dimensionsize_ = 0;
373  init_size_ = 0;
374  throw Exception::OutOfMemory(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(Value)));
375  }
376  }
377  if (matrix_ != NULL)
378  {
379  for (SizeType j = 0; j < dimensionsize; ++j)
380  {
381  for (SizeType k = 0; k < j; ++k)
382  {
383  matrix_[j][k] = value;
384  }
385  }
386  min_element_ = std::make_pair(1, 0);
387  }
388  }
389 
398  void reduce(SizeType j)
399  {
400  if (j >= dimensionsize_)
401  {
402  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
403  }
404  //delete row j and therefor overwrite with row j+1 and iterate like this to last row
405  SizeType i = j + 1;
406  while (i < dimensionsize_ && matrix_[i] != NULL)
407  {
408  //left out in the copy is each rows jth element, pointer working here as iterators just fine
409  std::copy(matrix_[i] + j + 1, matrix_[i] + i, std::copy(matrix_[i], matrix_[i] + j, matrix_[i - 1]));
410  ++i;
411  }
412  //last row is freed and the pointer set to NULL (outer array's size is not changed)
413  delete[] matrix_[i - 1];
414  matrix_[i - 1] = NULL;
415  --dimensionsize_;
416  }
417 
419  SizeType dimensionsize() const
420  {
421  return dimensionsize_;
422  }
423 
430  {
431  min_element_ = std::make_pair(1, 0);
432  //error if dimensionsize_<1, return if dimensionsize_ == 1, else
433  if (dimensionsize_ < 1)
434  {
435  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
436  }
437  if (dimensionsize_ != 1) //else matrix has one element: (1,0)
438  {
439  ValueType* row_min_;
440  for (SizeType r = 2; r < dimensionsize_ && matrix_[r] != NULL; ++r)
441  {
442  row_min_ = std::min_element(matrix_[r], matrix_[r] + r);
443  if (*row_min_ < matrix_[min_element_.first][min_element_.second])
444  {
445  min_element_ = std::make_pair(r, row_min_ - matrix_[r]);
446  }
447  }
448  }
449  }
450 
456  bool operator==(DistanceMatrix<ValueType> const& rhs) const
457  {
458  OPENMS_PRECONDITION(dimensionsize_ == rhs.dimensionsize_, "DistanceMatrices have different sizes.");
459  for (Size i = 1; i < rhs.dimensionsize(); ++i)
460  {
461  for (Size j = 0; j < i; ++j)
462  {
463  if (matrix_[i][j] != rhs.matrix_[i][j])
464  {
465  return false;
466  }
467  }
468  }
469  return true;
470  }
471 
477  std::pair<SizeType, SizeType> getMinElementCoordinates() const
478  {
479  if (dimensionsize_ == 0)
480  {
481  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
482  }
483  return min_element_;
484  }
485 
486 protected:
488  ValueType** matrix_;
490  SizeType init_size_; // actual size of outer array
492  SizeType dimensionsize_; //number of virtual elements: ((dimensionsize-1)*(dimensionsize))/2
494  std::pair<SizeType, SizeType> min_element_;
495 
496 private:
499  {
500  matrix_ = rhs.matrix_;
501  init_size_ = rhs.init_size_;
502  dimensionsize_ = rhs.dimensionsize_;
503  min_element_ = rhs.min_element_;
504 
505  return *this;
506  }
507 
508  }; // class DistanceMatrix
509 
515  template <typename Value>
516  std::ostream& operator<<(std::ostream& os, const DistanceMatrix<Value>& matrix)
517  {
518  typedef typename DistanceMatrix<Value>::SizeType SizeType;
519 
520  std::ios_base::fmtflags flag_backup = os.setf(std::ios::scientific);
521  std::streamsize precision_backup = os.precision();
522  //~ os.precision(15);
523  os.precision(writtenDigits<double>(0.0)); // #include <OpenMS/CONCEPT/Types.h>
524 
525  //evtl. color lower triangular matrix o.s.l.t.
526  for (SizeType i = 0; i < matrix.dimensionsize(); ++i)
527  {
528  for (SizeType j = 0; j < matrix.dimensionsize(); ++j)
529  {
530  os << matrix(i, j) << '\t';
531  }
532  os << std::endl;
533  }
534  os.flags(flag_backup);
535  os.precision(precision_backup);
536  return os;
537  }
538 
539 } // namespace OpenMS
540 
541 #endif // OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
const double k
SizeType init_size_
number of actually stored rows
Definition: DistanceMatrix.h:490
bool operator==(DistanceMatrix< ValueType > const &rhs) const
Equality comparator.
Definition: DistanceMatrix.h:456
const ValueType getValue(SizeType i, SizeType j) const
gets a value at a given position:
Definition: DistanceMatrix.h:213
Value value_type
Definition: DistanceMatrix.h:74
void resize(SizeType dimensionsize, Value value=Value())
resizing the container
Definition: DistanceMatrix.h:350
ValueType ** matrix_
sparse element not to be included in base container
Definition: DistanceMatrix.h:488
Out of range exception.
Definition: Exception.h:320
ValueType getValue(SizeType i, SizeType j)
gets a value at a given position:
Definition: DistanceMatrix.h:238
value_type ValueType
Definition: DistanceMatrix.h:80
SizeType dimensionsize_
number of accessibly stored rows (i.e. number of columns)
Definition: DistanceMatrix.h:492
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: openms/include/OpenMS/CONCEPT/Macros.h:107
A two-dimensional distance matrix, similar to OpenMS::Matrix.
Definition: DistanceMatrix.h:68
unsigned int UInt
Unsigned integer type.
Definition: Types.h:95
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:47
void clear()
reset all
Definition: DistanceMatrix.h:328
const ValueType operator()(SizeType i, SizeType j) const
gets a value at a given position (read only):
Definition: DistanceMatrix.h:190
DistanceMatrix(const DistanceMatrix &source)
copy constructor
Definition: DistanceMatrix.h:139
void reduce(SizeType j)
reduces DistanceMatrix by one dimension. first the jth row, then jth column
Definition: DistanceMatrix.h:398
void setValueQuick(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:310
void updateMinElement()
keep track of the actual minimum element after altering the matrix
Definition: DistanceMatrix.h:429
ValueType operator()(SizeType i, SizeType j)
gets a value at a given position (read only):
Definition: DistanceMatrix.h:201
DistanceMatrix & operator=(const DistanceMatrix &rhs)
assignment operator (unsafe)
Definition: DistanceMatrix.h:498
void setValue(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:264
DistanceMatrix(SizeType dimensionsize, Value value=Value())
detailed constructor
Definition: DistanceMatrix.h:98
Out of memory exception.
Definition: Exception.h:472
~DistanceMatrix()
destructor
Definition: DistanceMatrix.h:175
std::pair< SizeType, SizeType > getMinElementCoordinates() const
Indexpair of minimal element.
Definition: DistanceMatrix.h:477
DistanceMatrix()
default constructor
Definition: DistanceMatrix.h:86
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:128
SizeType dimensionsize() const
gives the number of rows (i.e. number of columns)
Definition: DistanceMatrix.h:419
Size SizeType
Definition: DistanceMatrix.h:79
Int writtenDigits< double >(const double &)
Number of digits commonly used for writing a double (a.k.a. precision).
Definition: Types.h:220
std::pair< SizeType, SizeType > min_element_
index of minimal element(i.e. number in underlying SparseVector)
Definition: DistanceMatrix.h:494

OpenMS / TOPP release 2.3.0 Documentation generated on Tue Jan 9 2018 18:21:59 using doxygen 1.8.13