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-2013.
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>
40 
41 #include <cmath>
42 #include <algorithm>
43 #include <iomanip>
44 #include <iostream>
45 
46 namespace OpenMS
47 {
48 
56  template <typename Value>
58  {
59 public:
60 
62 
63  typedef Value value_type;
65 
67 
68  typedef Size SizeType;
71 
77  {
78  }
79 
86  DistanceMatrix(SizeType dimensionsize, Value value = Value()) :
87  matrix_(new ValueType *[dimensionsize]), init_size_(dimensionsize), dimensionsize_(dimensionsize), min_element_(0, 0)
88  {
89  matrix_[0] = NULL;
90  SizeType i = 1;
91  for (i = 1; i < dimensionsize; ++i)
92  {
93  matrix_[i] = new ValueType[i];
94  if (matrix_[i] == NULL)
95  {
96  SizeType j = i;
97  for (i = 1; i < j; i++)
98  {
99  delete[] matrix_[i];
100  }
101  delete[] matrix_;
102  matrix_ = NULL;
103  dimensionsize_ = 0;
104  init_size_ = 0;
105  throw Exception::OutOfMemory(__FILE__, __LINE__, __PRETTY_FUNCTION__, (UInt)((((dimensionsize - 2) * (dimensionsize - 1)) / 2) * sizeof(ValueType)));
106  }
107  }
108  if (matrix_ != NULL)
109  {
110  for (i = 1; i < dimensionsize; ++i)
111  {
112  for (SizeType j = 0; j < i; ++j)
113  {
114  matrix_[i][j] = value;
115  }
116  }
117  min_element_ = std::make_pair(1, 0);
118  }
119  }
120 
126  DistanceMatrix(const DistanceMatrix & source) :
127  matrix_(new ValueType *[source.dimensionsize_]),
128  init_size_(source.dimensionsize_),
130  min_element_(source.min_element_)
131  {
132  matrix_[0] = NULL;
133  SizeType i = 1;
134  for (i = 1; i < dimensionsize_; ++i)
135  {
136  matrix_[i] = new ValueType[i];
137  if (matrix_[i] == NULL)
138  {
139  SizeType j = i;
140  for (i = 1; i < j; i++)
141  {
142  delete[] matrix_[i];
143  }
144  delete[] matrix_;
145  matrix_ = NULL;
146  dimensionsize_ = 0;
147  init_size_ = 0;
148  min_element_ = std::make_pair(0, 0);
149  throw Exception::OutOfMemory(__FILE__, __LINE__, __PRETTY_FUNCTION__, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(ValueType)));
150  }
151  }
152  if (matrix_ != NULL)
153  {
154  for (i = 1; i < dimensionsize_; ++i)
155  {
156  std::copy(source.matrix_[i], source.matrix_[i] + i, matrix_[i]);
157  }
158  }
159  }
160 
163  {
164  for (SizeType i = 1; i < init_size_; i++)
165  {
166  delete[] matrix_[i];
167  }
168  delete[] matrix_;
169  }
170 
177  {
178  return getValue(i, j);
179  }
180 
187  {
188  return getValue(i, j);
189  }
190 
198  {
199  if (i >= dimensionsize_ || j >= dimensionsize_)
200  {
201  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
202  }
203  // elements on main diagonal are not stored and assumed to be 0
204  if (i == j)
205  {
206  return 0;
207  }
208  if (i < j)
209  {
210  std::swap(i, j);
211  }
212  return (const ValueType)(matrix_[i][j]);
213  }
214 
222  {
223  if (i >= dimensionsize_ || j >= dimensionsize_)
224  {
225  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
226  }
227  // elements on main diagonal are not stored and assumed to be 0
228  if (i == j)
229  {
230  return 0;
231  }
232  if (i < j)
233  {
234  std::swap(i, j);
235  }
236  return matrix_[i][j];
237  }
238 
247  {
248  if (i >= dimensionsize_ || j >= dimensionsize_)
249  {
250  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
251  }
252  // elements on main diagonal are not stored and assumed to be 0
253  if (i != j)
254  {
255  if (i < j)
256  {
257  std::swap(i, j);
258  }
259  if (i != min_element_.first && j != min_element_.second)
260  {
261  matrix_[i][j] = value;
262  if (value < matrix_[min_element_.first][min_element_.second]) // keep min_element_ up-to-date
263  {
264  min_element_ = std::make_pair(i, j);
265  }
266  }
267  else
268  {
269  if (value <= matrix_[min_element_.first][min_element_.second])
270  {
271  matrix_[i][j] = value;
272  }
273  else
274  {
275  matrix_[i][j] = value;
277  }
278  }
279  }
280  }
281 
292  {
293  if (i >= dimensionsize_ || j >= dimensionsize_)
294  {
295  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
296  }
297  // elements on main diagonal are not stored and assumed to be 0
298  if (i != j)
299  {
300  if (i < j)
301  {
302  std::swap(i, j);
303  }
304  matrix_[i][j] = value;
305  }
306  }
307 
309  void clear()
310  {
311  for (SizeType i = 1; i < init_size_; i++)
312  {
313  delete[] matrix_[i];
314  }
315  delete[] matrix_;
316  matrix_ = NULL;
317  min_element_ = std::make_pair(0, 0);
318  dimensionsize_ = 0;
319  init_size_ = 0;
320  }
321 
330  void resize(SizeType dimensionsize, Value value = Value())
331  {
332  for (SizeType j = 1; j < init_size_; j++)
333  {
334  delete matrix_[j];
335  }
336  delete[] matrix_;
338  init_size_ = dimensionsize;
339  min_element_ = std::make_pair(0, 0);
341  for (SizeType j = 1; j < dimensionsize_; ++j)
342  {
343  matrix_[j] = new ValueType[j];
344  if (matrix_[j] == NULL)
345  {
346  for (SizeType k = 1; k < j; ++k)
347  {
348  delete[] matrix_[k];
349  }
350  delete[] matrix_;
351  matrix_ = NULL;
352  dimensionsize_ = 0;
353  init_size_ = 0;
354  throw Exception::OutOfMemory(__FILE__, __LINE__, __PRETTY_FUNCTION__, (UInt)((((dimensionsize_ - 2) * (dimensionsize_ - 1)) / 2) * sizeof(Value)));
355  }
356  }
357  if (matrix_ != NULL)
358  {
359  for (SizeType j = 0; j < dimensionsize; ++j)
360  {
361  for (SizeType k = 0; k < j; ++k)
362  {
363  matrix_[j][k] = value;
364  }
365  }
366  min_element_ = std::make_pair(1, 0);
367  }
368  }
369 
377  void reduce(SizeType j)
378  {
379  if (j >= dimensionsize_)
380  {
381  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
382  }
383  //delete row j and therefor overwrite with row j+1 and iterate like this to last row
384  SizeType i = j + 1;
385  while (i < dimensionsize_ && matrix_[i] != NULL)
386  {
387  //left out in the copy is each rows jth element, pointer working here as iterators just fine
388  std::copy(matrix_[i] + j + 1, matrix_[i] + i, std::copy(matrix_[i], matrix_[i] + j, matrix_[i - 1]));
389  ++i;
390  }
391  //last row is freed and the pointer set to NULL (outer array's size is not changed)
392  delete[] matrix_[i - 1];
393  matrix_[i - 1] = NULL;
394  --dimensionsize_;
395  }
396 
399  {
400  return dimensionsize_;
401  }
402 
408  {
409  min_element_ = std::make_pair(1, 0);
410  //error if dimensionsize_<1, return if dimensionsize_ == 1, else
411  if (dimensionsize_ < 1)
412  {
413  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
414  }
415  if (dimensionsize_ != 1) //else matrix has one element: (1,0)
416  {
417  ValueType * row_min_;
418  for (SizeType r = 2; r < dimensionsize_ && matrix_[r] != NULL; ++r)
419  {
420  row_min_ = std::min_element(matrix_[r], matrix_[r] + r);
421  if (*row_min_ < matrix_[min_element_.first][min_element_.second])
422  {
423  min_element_ = std::make_pair(r, row_min_ - matrix_[r]);
424  }
425  }
426  }
427  }
428 
433  bool operator==(DistanceMatrix<ValueType> const & rhs) const
434  {
435  OPENMS_PRECONDITION(dimensionsize_ == rhs.dimensionsize_, "DistanceMatrices have different sizes.");
436  for (Size i = 1; i < rhs.dimensionsize(); ++i)
437  {
438  for (Size j = 0; j < i; ++j)
439  {
440  if (matrix_[i][j] != rhs.matrix_[i][j])
441  {
442  return false;
443  }
444  }
445  }
446  return true;
447  }
448 
453  std::pair<SizeType, SizeType> getMinElementCoordinates() const
454  {
455  if (dimensionsize_ == 0)
456  {
457  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
458  }
459  return min_element_;
460  }
461 
462 protected:
466  SizeType init_size_; // actual size of outer array
468  SizeType dimensionsize_; //number of virtual elements: ((dimensionsize-1)*(dimensionsize))/2
470  std::pair<SizeType, SizeType> min_element_;
471 
472 private:
475  {
476  matrix_ = rhs.matrix_;
477  init_size_ = rhs.init_size_;
480 
481  return *this;
482  }
483 
484  }; // class DistanceMatrix
485 
490  template <typename Value>
491  std::ostream & operator<<(std::ostream & os, const DistanceMatrix<Value> & matrix)
492  {
493  typedef typename DistanceMatrix<Value>::SizeType SizeType;
494 
495  std::ios_base::fmtflags flag_backup = os.setf(std::ios::scientific);
496  std::streamsize precision_backup = os.precision();
497  //~ os.precision(15);
498  os.precision(writtenDigits<DoubleReal>()); // #include <OpenMS/CONCEPT/Types.h>
499 
500  //evtl. color lower triangular matrix o.s.l.t.
501  for (SizeType i = 0; i < matrix.dimensionsize(); ++i)
502  {
503  for (SizeType j = 0; j < matrix.dimensionsize(); ++j)
504  {
505  os << matrix(i, j) << '\t';
506  }
507  os << std::endl;
508  }
509  os.flags(flag_backup);
510  os.precision(precision_backup);
511  return os;
512  }
513 
514 } // namespace OpenMS
515 
516 #endif // OPENMS_DATASTRUCTURES_DISTANCEMATRIX_H
const double k
SizeType init_size_
number of actually stored rows
Definition: DistanceMatrix.h:466
Value value_type
Definition: DistanceMatrix.h:63
void resize(SizeType dimensionsize, Value value=Value())
resizing the container
Definition: DistanceMatrix.h:330
ValueType ** matrix_
sparse element not to be included in base container
Definition: DistanceMatrix.h:464
const ValueType operator()(SizeType i, SizeType j) const
gets a value at a given position (read only):
Definition: DistanceMatrix.h:176
Out of range exception.
Definition: Exception.h:320
ValueType getValue(SizeType i, SizeType j)
gets a value at a given position:
Definition: DistanceMatrix.h:221
value_type ValueType
Definition: DistanceMatrix.h:69
SizeType dimensionsize_
number of accessably stored rows (i.e. number of columns)
Definition: DistanceMatrix.h:468
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: Macros.h:107
A two-dimensional distance matrix, similar to OpenMS::Matrix.
Definition: DistanceMatrix.h:57
#define NULL
Definition: IsotopeWaveletParallelFor.h:41
bool operator==(DistanceMatrix< ValueType > const &rhs) const
Equality comparator.
Definition: DistanceMatrix.h:433
void clear()
reset all
Definition: DistanceMatrix.h:309
DistanceMatrix(const DistanceMatrix &source)
copy constructor
Definition: DistanceMatrix.h:126
void reduce(SizeType j)
reduces DistanceMatrix by one dimension. first the jth row, then jth column
Definition: DistanceMatrix.h:377
void setValueQuick(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:291
void updateMinElement()
keep track of the actual minimum element after altering the matrix
Definition: DistanceMatrix.h:407
ValueType operator()(SizeType i, SizeType j)
gets a value at a given position (read only):
Definition: DistanceMatrix.h:186
std::pair< SizeType, SizeType > getMinElementCoordinates() const
Indexpair of minimal element.
Definition: DistanceMatrix.h:453
DistanceMatrix & operator=(const DistanceMatrix &rhs)
assignment operator (unsafe)
Definition: DistanceMatrix.h:474
void setValue(SizeType i, SizeType j, ValueType value)
sets a value at a given position:
Definition: DistanceMatrix.h:246
DistanceMatrix(SizeType dimensionsize, Value value=Value())
detailed constructor
Definition: DistanceMatrix.h:86
Out of memory exception.
Definition: Exception.h:472
~DistanceMatrix()
destructor
Definition: DistanceMatrix.h:162
SizeType dimensionsize() const
gives the number of rows (i.e. number of columns)
Definition: DistanceMatrix.h:398
DistanceMatrix()
default constructor
Definition: DistanceMatrix.h:75
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:144
Size SizeType
Definition: DistanceMatrix.h:68
std::pair< SizeType, SizeType > min_element_
index of minimal element(i.e. number in underlying SparseVector)
Definition: DistanceMatrix.h:470
const ValueType getValue(SizeType i, SizeType j) const
gets a value at a given position:
Definition: DistanceMatrix.h:197

OpenMS / TOPP release 1.11.1 Documentation generated on Thu Nov 14 2013 11:19:12 using doxygen 1.8.5