id_iterators.h

Go to the documentation of this file.

#ifndef LARCOREALG_GEOMETRY_DETAILS_ID_ITERATORS_H
#define LARCOREALG_GEOMETRY_DETAILS_ID_ITERATORS_H

// LArSoft libraries
#include "larcorealg/Geometry/fwd.h"
#include "larcoreobj/SimpleTypesAndConstants/geo_types.h"
#include "larcoreobj/SimpleTypesAndConstants/readout_types.h"

// C/C++ standard libraries
#include <iterator> // std::forward_iterator_tag
#include <string>
#include <utility>

namespace geo::details {

  template <typename ID>
  struct id_sentinel {
    ID id;
  };

  template <typename ID>
  id_sentinel(ID) -> id_sentinel<ID>;

  template <typename ID>
  std::ostream& operator<<(std::ostream& out, id_sentinel<ID> const& sentinel)
  {
    return out << "id_sentinel{ " << sentinel.id << " }";
  }

  template <typename LocalID, typename GEOID, typename IterationPolicy>
  class id_iterator_base;

  template <typename GEOID, typename IterationPolicy>
  class id_iterator_base<CryostatID, GEOID, IterationPolicy> {
  public:
    struct GeometryIDIteratorTag {};
    using GeoID_t = GEOID; 

    using LocalID_t = CryostatID; 
    using iterator = id_iterator_base<LocalID_t, GeoID_t, IterationPolicy>; 

    static_assert(std::is_base_of<LocalID_t, GEOID>{}, "template type GEOID is not a LocalID_t");

    using difference_type = std::ptrdiff_t;
    using value_type = LocalID_t;
    using reference = value_type const&;
    using pointer = value_type const*;
    using iterator_category = std::forward_iterator_tag;

    id_iterator_base() = default;

    id_iterator_base(GeoID_t const& start_from, IterationPolicy policy)
      : id{start_from}, limit{policy.NSiblings(localID())}
    {}

    reference operator*() const { return localID(); }
    pointer operator->() const { return &localID(); }

    iterator& operator++()
    {
      next();
      return *this;
    }

    iterator operator++(int)
    {
      iterator old(*this);
      next();
      return old;
    }

    LocalID_t const& localID() const { return ID(); }

  protected:
    using ID_t = typename LocalID_t::CryostatID_t;

    void next()
    {
      if (at_end()) return;
      if (++local_index() < limit) return;
    }

    GeoID_t const& ID() const { return id; }
    GeoID_t& ID() { return id; }

    bool at_end() const { return local_index() == limit; }

  private:
    GeoID_t id{};                      
    ID_t limit = LocalID_t::InvalidID; 

    LocalID_t& localID() { return ID(); }

    ID_t const& local_index() const { return localID().deepestIndex(); }
    ID_t& local_index() { return localID().deepestIndex(); }
  }; // class id_iterator_base<CryostatID>

  template <typename LocalID, typename GEOID, typename IterationPolicy>
  class id_iterator_base
    : protected id_iterator_base<typename LocalID::ParentID_t, GEOID, IterationPolicy> {
    using upper_iterator = id_iterator_base<typename LocalID::ParentID_t, GEOID, IterationPolicy>;

  public:
    struct GeometryIDIteratorTag {};
    using GeoID_t = typename upper_iterator::GeoID_t;

    using LocalID_t = LocalID; 
    static_assert(std::is_base_of<LocalID_t, GEOID>{}, "template type GEOID is not a LocalID_t");

    using iterator =
      id_iterator_base<LocalID_t, GeoID_t, IterationPolicy>; 

    using difference_type = std::ptrdiff_t;
    using value_type = LocalID_t;
    using reference = value_type const&;
    using pointer = value_type const*;
    using iterator_category = std::forward_iterator_tag;

    id_iterator_base() = default;

    id_iterator_base(GeoID_t const& start_from, IterationPolicy itPolicy)
      : upper_iterator{start_from, itPolicy}, policy{itPolicy}, limit(policy.NSiblings(localID()))
    {}

    reference operator*() const { return localID(); }
    pointer operator->() const { return &localID(); }

    iterator& operator++()
    {
      next();
      return *this;
    }

    iterator operator++(int)
    {
      iterator old(*this);
      next();
      return old;
    }

    LocalID_t const& localID() const { return upper_iterator::ID(); }

  protected:
    void next()
    {
      // if at end (checked in the inherited context), do nothing
      if (upper_iterator::at_end()) return;

      // if after incrementing we haven't reached the limit, we are done
      if (++local_index() < limit) return;

      // we reached the end of the current elements list, we need to escalate:
      // - go to the next parent; if that becomes invalid, too bad, but we go on
      upper_iterator::next();
      // - set the index to the first element of the new parent
      local_index() = 0;
      // - update how many elements there are
      //   (expect 0 if it is now at_end() -- and it does not even matter)
      limit = policy.NSiblings(localID());
    }

  private:
    IterationPolicy policy;

    using ID_t = std::decay_t<
      decltype(std::declval<LocalID_t>().deepestIndex())>; 

    ID_t limit = LocalID_t::InvalidID;

    LocalID_t& localID() { return upper_iterator::ID(); }

    ID_t const& local_index() const { return localID().deepestIndex(); }
    ID_t& local_index() { return localID().deepestIndex(); }
  }; // class id_iterator_base

  template <typename LocalID, typename SiblingPolicy>
  using id_iterator = id_iterator_base<LocalID, LocalID, SiblingPolicy>;

  template <typename LocalID, typename SiblingPolicy>
  auto iterator_for(LocalID const& id, SiblingPolicy const& siblingPolicy)
  {
    return id_iterator<LocalID, SiblingPolicy>(id, siblingPolicy);
  }

  template <typename T, typename = void>
  struct has_geometry_id_iterator_tag : std::false_type {};

  template <typename T>
  struct has_geometry_id_iterator_tag<T, std::void_t<typename T::GeometryIDIteratorTag>>
    : std::true_type {};

  template <typename GEOIT>
  std::enable_if_t<has_geometry_id_iterator_tag<GEOIT>::value, std::ostream&> operator<<(
    std::ostream& out,
    GEOIT const& it)
  {
    return out << "geometry_iterator{ " << *it << " }";
  }

  template <typename ID, typename Policy>
  struct supported {
    static constexpr bool check(unsigned int (Policy::*)(ID const&) const) { return true; }
    static constexpr bool check(...) { return false; }
  };

  template <typename ID, typename IterationPolicy>
  void IncrementID(ID& id, IterationPolicy const& policy)
  {
    static_assert(supported<ID, IterationPolicy>::check(&IterationPolicy::NSiblings));

    if (++id.deepestIndex() < policy.NSiblings(id)) return;
    if constexpr (has_parent<ID>::value) {
      // go to next parent element and reset index
      id.deepestIndex() = 0;
      IncrementID(id.parentID(), policy);
    }
  }

  template <typename GeoID, typename IterationPolicy>
  GeoID GetNextID(GeoID const& id, IterationPolicy const& policy)
  {
    auto nextID(id);
    IncrementID(nextID, policy);
    return nextID;
  }

  // ID iterator/sentinel comparisons
  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator==(id_iterator_base<LocalID, GeoID, IterationPolicy> const& a,
                  id_iterator_base<LocalID, GeoID, IterationPolicy> const& b)
  {
    return a.localID() == b.localID();
  }

  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator!=(id_iterator_base<LocalID, GeoID, IterationPolicy> const& a,
                  id_iterator_base<LocalID, GeoID, IterationPolicy> const& b)
  {
    return !(a == b);
  }

  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator==(id_iterator_base<LocalID, GeoID, IterationPolicy> const& a,
                  id_sentinel<LocalID> const& b)
  {
    return a.localID() == b.id;
  }

  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator!=(id_iterator_base<LocalID, GeoID, IterationPolicy> const& a,
                  id_sentinel<LocalID> const& b)
  {
    return !(a == b);
  }

  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator==(id_sentinel<LocalID> const& a,
                  id_iterator_base<LocalID, GeoID, IterationPolicy> const& b)
  {
    return a.id == b.localID();
  }

  template <typename LocalID, typename GeoID, typename IterationPolicy>
  bool operator!=(id_sentinel<LocalID> const& a,
                  id_iterator_base<LocalID, GeoID, IterationPolicy> const& b)
  {
    return !(a == b);
  }

  template <typename LocalID>
  bool operator==(id_sentinel<LocalID> const& a, id_sentinel<LocalID> const& b)
  {
    return a.id == b.id;
  }

  template <typename LocalID>
  bool operator!=(id_sentinel<LocalID> const& a, id_sentinel<LocalID> const& b)
  {
    return !(a == b);
  }

} // namespace geo::details

#endif // LARCOREALG_GEOMETRY_DETAILS_ID_ITERATORS_H