| OpenMS 2.5.0

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-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: Chris Bielow $
32 // $Authors: Chris Bielow $
33 // --------------------------------------------------------------------------
34 //
35 #pragma once
36
37 #include <OpenMS/CONCEPT/Macros.h>
38 #include <OpenMS/DATASTRUCTURES/DefaultParamHandler.h>
39 #include <OpenMS/MATH/MISC/MathFunctions.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 >
71 class MatchedIterator
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
204 MatchedIterator& operator++()
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
214 MatchedIterator operator++(int)
215 {
216 MatchedIterator n(*this);
217 ++(*this);
218 return n;
219 }
220
222 static MatchedIterator end()
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
246 void advanceTarget_()
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
284 CONST_CONT_IT ref_begin_, ref_end_;
285 CONST_CONT_IT tgt_begin_, tgt_end_;
286 CONT_IT it_ref_, it_tgt_;
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
OpenMS::MatchedIterator::setToEnd_
void setToEnd_()
Definition: MatchedIterator.h:236
OpenMS::MatchedIterator::refIdx
size_t refIdx() const
index into reference container
Definition: MatchedIterator.h:188
OpenMS::MatchedIterator::operator->
std::enable_if< _CONST, pointer >::type operator->() const
pointer to current target element
Definition: MatchedIterator.h:171
OpenMS::MatchedIterator::MatchedIterator
MatchedIterator()
Default CTor; do not use this for anything other than assigning to it;.
Definition: MatchedIterator.h:125
OpenMS::MatchedIterator::operator->
std::enable_if< !_CONST, pointer >::type operator->()
Definition: MatchedIterator.h:176
MathFunctions.h
OpenMS::MatchedIterator::tol_
float tol_
Definition: MatchedIterator.h:287
OpenMS::ValueTrait::allowedTol
static float allowedTol(float tol, const T &)
Definition: MatchedIterator.h:295
OpenMS::MatchedIterator::CONT_IT
typename std::conditional< CONST_T, typename CONT_T::const_iterator, typename CONT_T::iterator >::type CONT_IT
Definition: MatchedIterator.h:81
OpenMS::MatchedIterator::operator==
bool operator==(const MatchedIterator &rhs) const
Definition: MatchedIterator.h:136
OpenMS::PpmTrait::allowedTol
static float allowedTol(float tol, const T &elem_ref)
Definition: MatchedIterator.h:312
OpenMS::DaTrait::allowedTol
static float allowedTol(float tol, const T &)
Definition: MatchedIterator.h:329
OpenMS::MatchedIterator::operator!=
bool operator!=(const MatchedIterator &rhs) const
Definition: MatchedIterator.h:152
OpenMS::MatchedIterator::MatchedIterator
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
OpenMS::MatchedIterator
For each element in the reference container the closest peak in the target will be searched...
Definition: MatchedIterator.h:71
OpenMS::MatchedIterator::MatchedIterator
MatchedIterator(bool)
Definition: MatchedIterator.h:231
OpenMS::MatchedIterator::it_ref_
CONT_IT it_ref_
Definition: MatchedIterator.h:286
OpenMS::MatchedIterator::CONST_CONT_IT
typename CONT_T::const_iterator CONST_CONT_IT
Definition: MatchedIterator.h:82
OpenMS::MatchedIterator::operator*
std::enable_if< !_CONST, reference >::type operator*()
Definition: MatchedIterator.h:164
OpenMS::MatchedIterator::difference_type
std::ptrdiff_t difference_type
Definition: MatchedIterator.h:77
OPENMS_PRECONDITION
#define OPENMS_PRECONDITION(condition, message)
Precondition macro.
Definition: openms/include/OpenMS/CONCEPT/Macros.h:136
OpenMS::MatchedIterator::is_end_
bool is_end_
Definition: MatchedIterator.h:288
OpenMS::MatchedIterator::tgt_begin_
CONST_CONT_IT tgt_begin_
Definition: MatchedIterator.h:285
OpenMS::Math::ppmToMass
T ppmToMass(T ppm, T mz_ref)
Compute the mass diff in [Th], given a ppm value and a reference point.
Definition: MathFunctions.h:263
OpenMS::MatchedIterator::tgt_end_
CONST_CONT_IT tgt_end_
Definition: MatchedIterator.h:285
OpenMS
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:46
OpenMS::MatchedIterator::ref_begin_
CONST_CONT_IT ref_begin_
Definition: MatchedIterator.h:284
OpenMS::MatchedIterator::isEnd_
bool isEnd_() const
Definition: MatchedIterator.h:241
OpenMS::MatchedIterator::value_type
typename CONT_T::value_type value_type
Definition: MatchedIterator.h:76
OpenMS::PpmTrait
Definition: MatchedIterator.h:309
DefaultParamHandler.h
OpenMS::MatchedIterator::pointer
typename std::conditional< CONST_T, typename CONT_T::value_type const *, typename CONT_T::value_type * >::type pointer
Definition: MatchedIterator.h:78
OpenMS::MatchedIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: MatchedIterator.h:75
OpenMS::MatchedIterator::operator*
std::enable_if< _CONST, reference >::type operator*() const
dereference current target element
Definition: MatchedIterator.h:159
OpenMS::PpmTrait::getDiffAbsolute
static float getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
for Peak1D & Co
Definition: MatchedIterator.h:318
OpenMS::MatchedIterator::tgtIdx
size_t tgtIdx() const
index into target container
Definition: MatchedIterator.h:194
OpenMS::MatchedIterator::MatchedIterator
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
OpenMS::MatchedIterator::ref
const value_type & ref() const
current element in reference container
Definition: MatchedIterator.h:182
OpenMS::ValueTrait
Trait for MatchedIterator to find pairs with a certain distance, which is computed directly on the va...
Definition: MatchedIterator.h:292
Macros.h
OpenMS::ValueTrait::getDiffAbsolute
static T getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
just use fabs on the value directly
Definition: MatchedIterator.h:301
OpenMS::MatchedIterator::operator=
MatchedIterator & operator=(const MatchedIterator &rhs)=default
Assignment operator (default)
OpenMS::MatchedIterator::end
static MatchedIterator end()
the end iterator
Definition: MatchedIterator.h:222
OpenMS::DaTrait
Definition: MatchedIterator.h:326
OpenMS::DaTrait::getDiffAbsolute
static float getDiffAbsolute(const T &elem_ref, const T &elem_tgt)
for Peak1D & Co
Definition: MatchedIterator.h:335
OpenMS::MatchedIterator::operator++
MatchedIterator operator++(int)
post-increment
Definition: MatchedIterator.h:214
OpenMS::MatchedIterator::ref_end_
CONST_CONT_IT ref_end_
Definition: MatchedIterator.h:284
OpenMS::MatchedIterator::operator++
MatchedIterator & operator++()
Advances to the next valid pair.
Definition: MatchedIterator.h:204
OpenMS::MatchedIterator::advanceTarget_
void advanceTarget_()
Definition: MatchedIterator.h:246
OpenMS::MatchedIterator::it_tgt_
CONT_IT it_tgt_
Definition: MatchedIterator.h:286
OpenMS::MatchedIterator::reference
typename std::conditional< CONST_T, typename CONT_T::value_type const &, typename CONT_T::value_type & >::type reference
Definition: MatchedIterator.h:79