MatchedIterator.h

Go to the documentation of this file.

// Copyright (c) 2002-present, OpenMS Inc. -- EKU Tuebingen, ETH Zurich, and FU Berlin
// SPDX-License-Identifier: BSD-3-Clause
//
// --------------------------------------------------------------------------
// $Maintainer: Chris Bielow $
// $Authors: Chris Bielow $
// --------------------------------------------------------------------------
//
#pragma once
 
#include <OpenMS/CONCEPT/Macros.h>
#include <OpenMS/DATASTRUCTURES/DefaultParamHandler.h>
#include <OpenMS/MATH/MathFunctions.h>
 
#include <iterator>
#include <type_traits>
 
namespace OpenMS
{
  
  template <typename CONT_T, typename TRAIT, bool CONST_T = true >
  class MatchedIterator
  {
    public:
      // define the 5 types required for an iterator. Deriving from std::iterator is deprecated in C++17.
      using iterator_category = std::forward_iterator_tag;
      using value_type = typename CONT_T::value_type; //< dereferences to an element in the target container
      using difference_type = std::ptrdiff_t;
      using pointer = typename std::conditional<CONST_T, typename CONT_T::value_type const*, typename CONT_T::value_type*>::type;
      using reference = typename std::conditional<CONST_T, typename CONT_T::value_type const&, typename CONT_T::value_type&>::type;
      
      using CONT_IT = typename std::conditional<CONST_T, typename CONT_T::const_iterator, typename CONT_T::iterator>::type; // for dereferencing etc
      using CONST_CONT_IT = typename CONT_T::const_iterator; // for input containers
      
      explicit MatchedIterator(const CONT_T& ref, const CONT_T& target, float tolerance)
        : MatchedIterator(ref.begin(), ref.end(), target.begin(), target.end(), tolerance)
      {
      }
    
      explicit 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)
        : 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)
      {
        if (tgt_begin_ == tgt_end_)
        { // nothing to iterate over in target (if ref_ were empty, isEnd_() is automatically true)
          setToEnd_();
          return;
        }
        advanceTarget_();
      }
 
      explicit MatchedIterator()
        : ref_begin_(), ref_end_(), tgt_begin_(), tgt_end_(), it_ref_(), it_tgt_(), tol_(), is_end_(false)
      {
      }
 
      MatchedIterator(const MatchedIterator& rhs) = default;
      
      MatchedIterator& operator=(const MatchedIterator& rhs) = default;
 
      bool operator==(const MatchedIterator& rhs) const
      {
        if (this == &rhs) return true;
 
        if (isEnd_() || rhs.isEnd_())
        {
          return isEnd_() == rhs.isEnd_();
        }
 
        return (it_ref_ == rhs.it_ref_ &&
                it_tgt_ == rhs.it_tgt_ &&
                ref_begin_ == rhs.ref_begin_ &&
                ref_end_ == rhs.ref_end_ &&
                tgt_begin_ == rhs.tgt_begin_ &&
                tgt_end_ == rhs.tgt_end_);
      }
      bool operator!=(const MatchedIterator& rhs) const
      {
        return !(*this == rhs);
      }
 
      template< bool _CONST = CONST_T >
      typename std::enable_if< _CONST, reference >::type operator*() const
      {
        return *it_tgt_;
      }
      template< bool _CONST = CONST_T >
      typename std::enable_if< !_CONST, reference >::type operator*()
      {
        return *it_tgt_;
      }
 
      template< bool _CONST = CONST_T >
      typename std::enable_if< _CONST, pointer >::type operator->() const
      {
        return &(*it_tgt_);
      }
      template< bool _CONST = CONST_T >
      typename std::enable_if< !_CONST, pointer >::type operator->()
      {
        return &(*it_tgt_);
      }
 
      const value_type& ref() const
      {
        return *it_ref_;
      }
 
      size_t refIdx() const
      {
        return it_ref_ - ref_begin_;
      }
      
      size_t tgtIdx() const
      {
        return it_tgt_ - tgt_begin_;
      }
 
      MatchedIterator& operator++()
      {
        // are we at end already? --> wrong usage
        OPENMS_PRECONDITION(!isEnd_(), "Tried to advance beyond end iterator!");
        ++it_ref_;
        advanceTarget_();
        return *this;
      }
 
      MatchedIterator operator++(int)
      {
        MatchedIterator n(*this);
        ++(*this);
        return n;
      }
      
      static MatchedIterator end()
      {
        return MatchedIterator(true);
      }
 
    protected:
 
      MatchedIterator(bool /*is_end*/)
        : ref_begin_(), ref_end_(), tgt_begin_(), tgt_end_(), it_ref_(), it_tgt_(), tol_(), is_end_(true)
      {
      }
 
      void setToEnd_()
      {
        is_end_ = true;
      }
 
      bool isEnd_() const
      {
        return is_end_;
      }
 
      void advanceTarget_()
      {
        while (it_ref_ != ref_end_)
        { // note: it_tgt_ always points to a valid element (unless the whole container was empty -- see CTor)
 
          double max_dist = TRAIT::allowedTol(tol_, *it_ref_);
 
          // forward iterate over elements in target data until distance gets worse.
          // Equal distances (e.g. equal target values) do not stop the walk; the first (smaller) element is kept.
          // Distances are compared in the TRAIT's own type (auto drops a returned reference), so equal target values always tie.
          CONT_IT best = it_tgt_;
          auto diff = TRAIT::getDiffAbsolute(*it_ref_, *it_tgt_);
          while (++it_tgt_ != tgt_end_)
          {
            const auto d = TRAIT::getDiffAbsolute(*it_ref_, *it_tgt_);
            if (d < diff) // getting better
            {
              diff = d;
              best = it_tgt_;
            }
            else if (d > diff) // getting worse (overshot)
            {
              break;
            }
          }
          it_tgt_ = best; // closest valid entry (never tgt_end_)
 
          if (float(diff) <= max_dist) return; // ok, found match (in float precision, like the tolerance)
 
          // try next ref peak
          ++it_ref_;
        }
        // reached end of ref container
        setToEnd_();
        // i.e. isEnd() is true now
      }
      
      CONST_CONT_IT ref_begin_, ref_end_;
      CONST_CONT_IT tgt_begin_, tgt_end_; 
      CONT_IT it_ref_, it_tgt_;
      float tol_;
      bool is_end_ = false;
  };
  
  struct ValueTrait
  {
    template <typename T>
    static float allowedTol(float tol, const T& /*mz_ref*/)
    {
      return tol;
    }
    template <typename T>
    static T getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
    {
      return fabs(elem_ref - elem_tgt);
    }
  };
 
  struct PpmTrait
  {
    template <typename T>
    static float allowedTol(float tol, const T& elem_ref)
    {
      return Math::ppmToMass(tol, (float)elem_ref.getMZ());
    }
    template <typename T>
    static float getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
    {
      return fabs(elem_ref.getMZ() - elem_tgt.getMZ());
    }
  };
 
  struct DaTrait
  {
    template <typename T>
    static float allowedTol(float tol, const T& /*mz_ref*/)
    {
      return tol;
    }
    template <typename T>
    static float getDiffAbsolute(const T& elem_ref, const T& elem_tgt)
    {
      return fabs(elem_ref.getMZ() - elem_tgt.getMZ());
    }
  };
 
} // namespace OpenMS