OpenMS
MatchedIterator.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: Chris Bielow $
32 // $Authors: Chris Bielow $
33 // --------------------------------------------------------------------------
34 //
35 #pragma once
36 
37 #include <OpenMS/CONCEPT/Macros.h>
40 
41 #include <iterator>
42 #include <type_traits>
43 
44 namespace OpenMS
45 {
46 
70  template <typename CONT_T, typename TRAIT, bool CONST_T = true >
72  {
73  public:
74  // define the 5 types required for an iterator. Deriving from std::iterator is deprecated in C++17.
75  using iterator_category = std::forward_iterator_tag;
76  using value_type = typename CONT_T::value_type; //< dereferences to an element in the target container
77  using difference_type = std::ptrdiff_t;
78  using pointer = typename std::conditional<CONST_T, typename CONT_T::value_type const*, typename CONT_T::value_type*>::type;
79  using reference = typename std::conditional<CONST_T, typename CONT_T::value_type const&, typename CONT_T::value_type&>::type;
80 
81  using CONT_IT = typename std::conditional<CONST_T, typename CONT_T::const_iterator, typename CONT_T::iterator>::type; // for dereferencing etc
82  using CONST_CONT_IT = typename CONT_T::const_iterator; // for input containers
83 
93  explicit MatchedIterator(const CONT_T& ref, const CONT_T& target, float tolerance)
94  : MatchedIterator(ref.begin(), ref.end(), target.begin(), target.end(), tolerance)
95  {
96  }
97 
109  explicit MatchedIterator(const CONST_CONT_IT ref_begin, const CONST_CONT_IT ref_end,
110  const CONST_CONT_IT tgt_begin, const CONST_CONT_IT tgt_end,
111  float tolerance)
112  : ref_begin_(ref_begin), ref_end_(ref_end), tgt_begin_(tgt_begin), tgt_end_(tgt_end), it_ref_(ref_begin), it_tgt_(tgt_begin), tol_(tolerance), is_end_(false)
113  {
114  if (tgt_begin_ == tgt_end_)
115  { // nothing to iterate over in target (if ref_ were empty, isEnd_() is automatically true)
116  setToEnd_();
117  return;
118  }
119  advanceTarget_();
120  }
121 
125  explicit MatchedIterator()
126  : ref_begin_(), ref_end_(), tgt_begin_(), tgt_end_(), it_ref_(), it_tgt_(), tol_(), is_end_(false)
127  {
128  }
129 
131  MatchedIterator(const MatchedIterator& rhs) = default;
132 
134  MatchedIterator& operator=(const MatchedIterator& rhs) = default;
135 
136  bool operator==(const MatchedIterator& rhs) const
137  {
138  if (this == &rhs) return true;
139 
140  if (isEnd_() || rhs.isEnd_())
141  {
142  return isEnd_() == rhs.isEnd_();
143  }
144 
145  return (it_ref_ == rhs.it_ref_ &&
146  it_tgt_ == rhs.it_tgt_ &&
147  ref_begin_ == rhs.ref_begin_ &&
148  ref_end_ == rhs.ref_end_ &&
149  tgt_begin_ == rhs.tgt_begin_ &&
150  tgt_end_ == rhs.tgt_end_);
151  }
152  bool operator!=(const MatchedIterator& rhs) const
153  {
154  return !(*this == rhs);
155  }
156 
158  template< bool _CONST = CONST_T >
159  typename std::enable_if< _CONST, reference >::type operator*() const
160  {
161  return *it_tgt_;
162  }
163  template< bool _CONST = CONST_T >
164  typename std::enable_if< !_CONST, reference >::type operator*()
165  {
166  return *it_tgt_;
167  }
168 
170  template< bool _CONST = CONST_T >
171  typename std::enable_if< _CONST, pointer >::type operator->() const
172  {
173  return &(*it_tgt_);
174  }
175  template< bool _CONST = CONST_T >
176  typename std::enable_if< !_CONST, pointer >::type operator->()
177  {
178  return &(*it_tgt_);
179  }
180 
182  const value_type& ref() const
183  {
184  return *it_ref_;
185  }
186 
188  size_t refIdx() const
189  {
190  return it_ref_ - ref_begin_;
191  }
192 
194  size_t tgtIdx() const
195  {
196  return it_tgt_ - tgt_begin_;
197  }
198 
205  {
206  // are we at end already? --> wrong usage
207  OPENMS_PRECONDITION(!isEnd_(), "Tried to advance beyond end iterator!");
208  ++it_ref_;
209  advanceTarget_();
210  return *this;
211  }
212 
215  {
216  MatchedIterator n(*this);
217  ++(*this);
218  return n;
219  }
220 
223  {
224  return MatchedIterator(true);
225  }
226 
227  protected:
228 
231  MatchedIterator(bool /*is_end*/)
232  : ref_begin_(), ref_end_(), tgt_begin_(), tgt_end_(), it_ref_(), it_tgt_(), tol_(), is_end_(true)
233  {
234  }
235 
236  void setToEnd_()
237  {
238  is_end_ = true;
239  }
240 
241  bool isEnd_() const
242  {
243  return is_end_;
244  }
245 
247  {
248  while (it_ref_ != ref_end_)
249  { // note: it_tgt_ always points to a valid element (unless the whole container was empty -- see CTor)
250 
251  double max_dist = TRAIT::allowedTol(tol_, *it_ref_);
252 
253  // forward iterate over elements in target data until distance gets worse
254  float diff = std::numeric_limits<float>::max();
255  do
256  {
257  auto d = TRAIT::getDiffAbsolute(*it_ref_, *it_tgt_);
258  if (diff > d) // getting better
259  {
260  diff = d;
261  }
262  else // getting worse (overshot)
263  {
264  --it_tgt_;
265  break;
266  }
267  ++it_tgt_;
268  } while (it_tgt_ != tgt_end_);
269 
270  if (it_tgt_ == tgt_end_)
271  { // reset to last valid entry
272  --it_tgt_;
273  }
274  if (diff <= max_dist) return; // ok, found match
275 
276  // try next ref peak
277  ++it_ref_;
278  }
279  // reached end of ref container
280  setToEnd_();
281  // i.e. isEnd() is true now
282  }
283 
287  float tol_;
288  bool is_end_ = false;
289  };
290 
292  struct ValueTrait
293  {
294  template <typename T>
295  static float allowedTol(float tol, const T& /*mz_ref*/)
296  {
297  return tol;
298  }
300  template <typename T>
301  static T getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
302  {
303  return fabs(elem_ref - elem_tgt);
304  }
305  };
306 
309  struct PpmTrait
310  {
311  template <typename T>
312  static float allowedTol(float tol, const T& elem_ref)
313  {
314  return Math::ppmToMass(tol, (float)elem_ref.getMZ());
315  }
317  template <typename T>
318  static float getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
319  {
320  return fabs(elem_ref.getMZ() - elem_tgt.getMZ());
321  }
322  };
323 
326  struct DaTrait
327  {
328  template <typename T>
329  static float allowedTol(float tol, const T& /*mz_ref*/)
330  {
331  return tol;
332  }
334  template <typename T>
335  static float getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
336  {
337  return fabs(elem_ref.getMZ() - elem_tgt.getMZ());
338  }
339  };
340 
341 } // namespace OpenMS
For each element in the reference container the closest peak in the target will be searched....
Definition: MatchedIterator.h:72
CONT_IT it_ref_
Definition: MatchedIterator.h:286
bool operator!=(const MatchedIterator &rhs) const
Definition: MatchedIterator.h:152
CONST_CONT_IT ref_end_
Definition: MatchedIterator.h:284
MatchedIterator & operator++()
Advances to the next valid pair.
Definition: MatchedIterator.h:204
MatchedIterator(const MatchedIterator &rhs)=default
Copy CTor (default)
CONST_CONT_IT tgt_end_
Definition: MatchedIterator.h:285
typename std::conditional< CONST_T, typename CONT_T::value_type const &, typename CONT_T::value_type & >::type reference
Definition: MatchedIterator.h:79
CONT_IT it_tgt_
Definition: MatchedIterator.h:286
MatchedIterator(const CONST_CONT_IT ref_begin, const CONST_CONT_IT ref_end, const CONST_CONT_IT tgt_begin, const CONST_CONT_IT tgt_end, float tolerance)
Constructs a MatchedIterator on two containers. The way a match is found, depends on the TRAIT type (...
Definition: MatchedIterator.h:109
MatchedIterator & operator=(const MatchedIterator &rhs)=default
Assignment operator (default)
MatchedIterator(bool)
Definition: MatchedIterator.h:231
size_t refIdx() const
index into reference container
Definition: MatchedIterator.h:188
bool isEnd_() const
Definition: MatchedIterator.h:241
MatchedIterator(const CONT_T &ref, const CONT_T &target, float tolerance)
Constructs a MatchedIterator on two containers. The way a match is found, depends on the TRAIT type (...
Definition: MatchedIterator.h:93
std::forward_iterator_tag iterator_category
Definition: MatchedIterator.h:75
typename CONT_T::const_iterator CONST_CONT_IT
Definition: MatchedIterator.h:82
void advanceTarget_()
Definition: MatchedIterator.h:246
bool operator==(const MatchedIterator &rhs) const
Definition: MatchedIterator.h:136
size_t tgtIdx() const
index into target container
Definition: MatchedIterator.h:194
MatchedIterator operator++(int)
post-increment
Definition: MatchedIterator.h:214
bool is_end_
Definition: MatchedIterator.h:288
typename CONT_T::value_type value_type
Definition: MatchedIterator.h:76
std::enable_if< _CONST, reference >::type operator*() const
dereference current target element
Definition: MatchedIterator.h:159
typename std::conditional< CONST_T, typename CONT_T::value_type const *, typename CONT_T::value_type * >::type pointer
Definition: MatchedIterator.h:78
static MatchedIterator end()
the end iterator
Definition: MatchedIterator.h:222
CONST_CONT_IT tgt_begin_
Definition: MatchedIterator.h:285
const value_type & ref() const
current element in reference container
Definition: MatchedIterator.h:182
std::enable_if< _CONST, pointer >::type operator->() const
pointer to current target element
Definition: MatchedIterator.h:171
std::enable_if< !_CONST, reference >::type operator*()
Definition: MatchedIterator.h:164
std::ptrdiff_t difference_type
Definition: MatchedIterator.h:77
MatchedIterator()
Default CTor; do not use this for anything other than assigning to it;.
Definition: MatchedIterator.h:125
CONST_CONT_IT ref_begin_
Definition: MatchedIterator.h:284
void setToEnd_()
Definition: MatchedIterator.h:236
float tol_
Definition: MatchedIterator.h:287
std::enable_if< !_CONST, pointer >::type operator->()
Definition: MatchedIterator.h:176
typename std::conditional< CONST_T, typename CONT_T::const_iterator, typename CONT_T::iterator >::type CONT_IT
Definition: MatchedIterator.h:81
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: openms/include/OpenMS/CONCEPT/Macros.h:120
T ppmToMass(T ppm, T mz_ref)
Compute the mass diff in [Th], given a ppm value and a reference point.
Definition: MathFunctions.h:335
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:48
Definition: MatchedIterator.h:327
static float getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
for Peak1D & Co
Definition: MatchedIterator.h:335
static float allowedTol(float tol, const T &)
Definition: MatchedIterator.h:329
Definition: MatchedIterator.h:310
static float getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
for Peak1D & Co
Definition: MatchedIterator.h:318
static float allowedTol(float tol, const T &elem_ref)
Definition: MatchedIterator.h:312
Trait for MatchedIterator to find pairs with a certain distance, which is computed directly on the va...
Definition: MatchedIterator.h:293
static T getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
just use fabs on the value directly
Definition: MatchedIterator.h:301
static float allowedTol(float tol, const T &)
Definition: MatchedIterator.h:295