MappedContainer.h

Go to the documentation of this file.

#ifndef LARDATAALG_UTILITIES_MAPPEDCONTAINER_H
#define LARDATAALG_UTILITIES_MAPPEDCONTAINER_H

// LArSoft libraries
#include "larcorealg/CoreUtils/ContainerMeta.h" // util::collection_value_access_t
#include "larcorealg/CoreUtils/MetaUtils.h"     // util::with_const_as_t

// C/C++ standard libraries
#include <algorithm> // std::reference_wrapper<>
#include <cstddef>   // std::size_t
#include <iterator>  // std::iterator_category, std::size(), ...
#include <limits>    // std::numeric_limits<>
#include <memory>    // std::unique_ptr<>
#include <stdexcept> // std::out_of_range
#include <string>    // std::to_string()

namespace util {

  namespace details {

    // ---------------------------------------------------------------------------
    template <typename Cont>
    struct ContainerTraits;

    // ---------------------------------------------------------------------------
    template <typename Cont, typename = void>
    class ContainerStorage;

    // ---------------------------------------------------------------------------

  } // namespace details

  // ---------------------------------------------------------------------------
  struct MappedContainerBase {

    template <typename T = std::size_t>
    static constexpr T invalidIndex()
    {
      return std::numeric_limits<T>::max();
    }

  }; // struct MappedContainerBase

  // ---------------------------------------------------------------------------
  template <typename Cont, typename Mapping>
  class MappedContainer : private MappedContainerBase {

    using Storage_t = details::ContainerStorage<Cont>;

    using MappingStorage_t = details::ContainerStorage<Mapping>;

    using Value_t = typename Storage_t::value_type;

    using Size_t = std::size_t; 

    Storage_t fData; 

    MappingStorage_t fMapping; 

    Size_t fSize = 0U; 

    // constantness needs to be removed in order for this object to be copiable
    std::remove_cv_t<Value_t> fDefValue{};

    template <typename Container, typename Reference>
    class IteratorBase;

  public:
    using DataContainer_t = Cont; 
    using Mapping_t = Mapping;    

    using MappedContainer_t = MappedContainer<DataContainer_t, Mapping_t>;

    using DataIndex_t = util::collection_value_t<Mapping_t>;

    using MappingIndex_t = std::size_t;

    // --- BEGIN -- C++ standard container definitions -------------------------
    using value_type = Value_t;

    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    using reference = util::with_const_as_t<typename Storage_t::reference,
                                            util::collection_value_access_t<DataContainer_t>>;
    using const_reference = typename Storage_t::const_reference;

    using iterator = IteratorBase<MappedContainer_t, reference>;
    using const_iterator = IteratorBase<MappedContainer_t const, const_reference>;

    // --- END -- C++ standard container definitions ---------------------------

    static constexpr DataIndex_t InvalidIndex = invalidIndex<DataIndex_t>();

    // --- BEGIN Constructors --------------------------------------------------

    MappedContainer() = default;

    MappedContainer(DataContainer_t const& cont,
                    Mapping_t const& mapping,
                    size_type size,
                    value_type defValue)
      : fData(cont), fMapping(mapping), fSize(size), fDefValue(defValue)
    {}

    MappedContainer(DataContainer_t const& cont, Mapping_t const& mapping, size_type size)
      : MappedContainer(cont, mapping, size, {})
    {}

    MappedContainer(DataContainer_t const& cont, Mapping_t const& mapping)
      : MappedContainer(cont, mapping, minimal_size(cont, mapping))
    {}

    // --- END Constructors ----------------------------------------------------

    // --- BEGIN Container information -----------------------------------------

    size_type size() const { return fSize; }

    size_type minimal_size() const;

    size_type max_size() const { return std::numeric_limits<size_type>::max(); }

    bool empty() const { return size() == 0U; }

    // @{
    reference defaultValue() { return fDefValue; }
    const_reference defaultValue() const { return fDefValue; }
    // @}

    void setDefaultValue(value_type defValue) { fDefValue = defValue; }

    // --- END Container information -------------------------------------------

    // --- BEGIN Random access to elements -------------------------------------

    // @{
    decltype(auto) operator[](MappingIndex_t index) const { return map_element(index); }
    decltype(auto) operator[](MappingIndex_t index) { return map_element(index); }
    // @}

    // @{
    decltype(auto) at(MappingIndex_t index) const;
    decltype(auto) at(MappingIndex_t index);
    // @}

    // @{
    decltype(auto) front() const { return map_element(0U); }
    decltype(auto) front() { return map_element(0U); }
    // @}

    // @{
    decltype(auto) back() const { return map_element(size() - 1); }
    decltype(auto) back() { return map_element(size() - 1); }
    // @}

    // @{
    decltype(auto) map_index(MappingIndex_t index) const;
    decltype(auto) map_index(MappingIndex_t index);
    // @}

    // --- END Random access to elements ---------------------------------------

    // --- BEGIN Iteration -----------------------------------------------------

    const_iterator cbegin() const { return {*this, 0U}; }

    const_iterator begin() const { return cbegin(); }

    iterator begin() { return {*this, 0U}; }

    const_iterator cend() const { return {*this, size()}; }

    const_iterator end() const { return cend(); }

    iterator end() { return {*this, size()}; }

    // --- END Iteration -------------------------------------------------------

  protected:
    static size_type minimal_size(DataContainer_t const& cont, Mapping_t const& mapping);

  private:
    decltype(auto) map_element(MappingIndex_t index);

    decltype(auto) map_element(MappingIndex_t index) const;

  }; // class MappedContainer<>

  //----------------------------------------------------------------------------
  template <typename Cont, typename Mapping>
  auto mapContainer(Cont cont, Mapping mapping)
  {
    return MappedContainer<Cont, Mapping>(cont, mapping);
  }

  //----------------------------------------------------------------------------

} // namespace util

//------------------------------------------------------------------------------
//---  template implementation
//------------------------------------------------------------------------------
namespace util {

  namespace details {

    //--------------------------------------------------------------------------
    template <typename T>
    T& NullRef()
    {
      T* nullTptr = nullptr;
      return *nullTptr;
    }

    //--------------------------------------------------------------------------
    //---  ContainerStorage
    //--------------------------------------------------------------------------
    template <typename Cont>
    struct ContainerStorageBase {

      using Container_t = Cont;
      using Traits_t = details::ContainerTraits<Container_t>;

      using index_type = typename Traits_t::size_type;

      using value_type = typename Traits_t::value_type;
      using size_type = typename Traits_t::size_type;
      using difference_type = typename Traits_t::difference_type;
      using reference = typename Traits_t::reference;
      using const_reference = typename Traits_t::const_reference;

      Container_t fCont;

      ContainerStorageBase() = default;
      explicit ContainerStorageBase(Container_t const& cont) : fCont(cont) {}
      explicit ContainerStorageBase(Container_t&& cont) : fCont(std::move(cont)) {}

      decltype(auto) container() const { return util::collection_from_reference(fCont); }
      decltype(auto) container() { return util::collection_from_reference(fCont); }

      auto size() const
      {
        using std::size;
        return size(container());
      }

      decltype(auto) operator[](index_type index) { return container()[index]; }
      decltype(auto) operator[](index_type index) const { return container()[index]; }

    }; // struct ContainerStorageBase

    //--------------------------------------------------------------------------
    template <typename Cont, typename /* = void */>
    class ContainerStorage : public ContainerStorageBase<Cont> {

      using Base_t = ContainerStorageBase<Cont>;

      // inherit all constructors
      using Base_t::Base_t;

    }; // struct ContainerStorage

    template <typename Cont>
    class ContainerStorage<Cont, std::enable_if_t<util::is_reference_wrapper_v<Cont>>>
      : public ContainerStorageBase<Cont> {
      using Base_t = ContainerStorageBase<Cont>;
      using DataContainer_t = typename Cont::type;

    public:
      // inherit all constructors
      using Base_t::Base_t;

      // sad hack :-(
      // calling the inherited constructor with a `reference_wrapper`
      // (`Base_t::Container_t`) referencing an invalid reference to
      // the wrapped data type (which is `DataContainer_t`).
      ContainerStorage() : Base_t(typename Base_t::Container_t{NullRef<DataContainer_t>()}) {}

    }; // struct ContainerStorage

    //--------------------------------------------------------------------------

  } // namespace details

  //----------------------------------------------------------------------------
  //--- MappedContainer::IteratorBase
  //----------------------------------------------------------------------------
  template <typename Cont, typename Mapping>
  template <typename Container, typename Reference>
  class MappedContainer<Cont, Mapping>::IteratorBase {

    using Container_t = Container;
    using Reference_t = Reference;

    using Iterator_t = IteratorBase<Container_t, Reference_t>;

    Container_t* fCont = nullptr;         
    MappingIndex_t fIndex = InvalidIndex; 

  public:
    // --- BEGIN Traits --------------------------------------------------------

    using value_type = std::remove_cv_t<typename Container_t::value_type>;
    using difference_type = typename Container_t::difference_type;
    using size_type = typename Container_t::size_type;
    using reference = Reference_t;
    using pointer = decltype(&std::declval<reference>());
    using iterator_category = std::input_iterator_tag;

    // --- END Traits ----------------------------------------------------------

    IteratorBase() = default;

    IteratorBase(Container_t& cont, MappingIndex_t index) : fCont(&cont), fIndex(index) {}

    IteratorBase(Iterator_t const&) = default;

    template <typename OC, typename OR>
    IteratorBase(IteratorBase<OC, OR> const& from) : fCont(from.cont), fIndex(from.index)
    {}

    Iterator_t& operator=(Iterator_t const&) = default;

    template <typename OC, typename OR>
    Iterator_t& operator=(IteratorBase<OC, OR> const& from)
    {
      fCont = from.fCont;
      fIndex = from.fIndex;
      return *this;
    }

    // --- BEGIN Dereferencing -------------------------------------------------
    reference operator*() const { return (*fCont)[fIndex]; }

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

    reference operator[](difference_type n) const { return (*fCont)[fIndex + n]; }

    // --- END Dereferencing ---------------------------------------------------

    // --- BEGIN Transformation ------------------------------------------------
    Iterator_t& operator++()
    {
      ++fIndex;
      return *this;
    }

    Iterator_t operator++(int)
    {
      auto it = *this;
      this->operator++();
      return it;
    }

    Iterator_t& operator--()
    {
      --fIndex;
      return *this;
    }

    Iterator_t operator--(int)
    {
      auto it = *this;
      this->operator--();
      return it;
    }

    Iterator_t& operator+=(difference_type n)
    {
      fIndex += n;
      return *this;
    }

    Iterator_t& operator-=(difference_type n)
    {
      fIndex -= n;
      return *this;
    }

    Iterator_t operator+(difference_type n) const
    {
      auto it = *this;
      it += n;
      return it;
    }

    Iterator_t operator-(difference_type n) const
    {
      auto it = *this;
      it -= n;
      return it;
    }

    difference_type operator-(Iterator_t& other) const { return fIndex - other.fIndex; }

    // --- END Transformation --------------------------------------------------

    // --- BEGIN Comparisons ---------------------------------------------------
    template <typename OC, typename OR>
    bool operator==(IteratorBase<OC, OR> const& other) const
    {
      return (fCont == other.fCont) && (fIndex == other.fIndex);
    }

    template <typename OC, typename OR>
    bool operator!=(IteratorBase<OC, OR> const& other) const
    {
      return (fCont != other.fCont) || (fIndex != other.fIndex);
    }

    template <typename OC, typename OR>
    bool operator<=(IteratorBase<OC, OR> const& other) const
    {
      return (fCont == other.fCont) && (fIndex <= other.fIndex);
    }

    template <typename OC, typename OR>
    bool operator<(IteratorBase<OC, OR> const& other) const
    {
      return (fCont == other.fCont) && (fIndex < other.fIndex);
    }

    template <typename OC, typename OR>
    bool operator>=(IteratorBase<OC, OR> const& other) const
    {
      return (fCont == other.fCont) && (fIndex >= other.fIndex);
    }

    template <typename OC, typename OR>
    bool operator>(IteratorBase<OC, OR> const& other) const
    {
      return (fCont == other.fCont) && (fIndex > other.fIndex);
    }

    // --- END Comparisons -----------------------------------------------------

  }; // IteratorBase

  // it hurts the eye
  template <typename Cont, typename Mapping, typename Container, typename Reference>
  typename MappedContainer<Cont, Mapping>::template IteratorBase<Container, Reference> operator+(
    typename MappedContainer<Cont, Mapping>::template IteratorBase<Container,
                                                                   Reference>::difference_type n,
    typename MappedContainer<Cont, Mapping>::template IteratorBase<Container, Reference> const& it)
  {
    return it + n;
  }

} // namespace util

namespace util::details {

  //----------------------------------------------------------------------------
  template <typename Cont>
  struct ContainerTraitsImpl {
    using value_type = typename Cont::value_type;
    using difference_type = typename Cont::difference_type;
    using size_type = typename Cont::size_type;
    using const_reference = typename Cont::const_reference;
    using reference = typename Cont::reference;
    using const_iterator = typename Cont::const_iterator;
    using iterator = typename Cont::iterator;
  }; // ContainerTraitsImpl<>

  template <typename T>
  struct ContainerTraitsImpl<T*> {
    using value_type = T; // should it be devoid of const/mutable?
    using difference_type = std::ptrdiff_t;
    using size_type = std::size_t;
    using const_reference = T const&;
    using reference = T&;
    using const_iterator = T const*;
    using iterator = T*;
  }; // ContainerTraitsImpl<T*>

  // this is not as powerful as it should... hoping users do not nest
  // crazily `unique_ptr`, `reference_wrapper` and such
  template <typename Cont>
  struct ContainerTraits
    : ContainerTraitsImpl<std::remove_reference_t<
        util::collection_from_reference_t<util::strip_referenceness_t<Cont>>>> {};

  //----------------------------------------------------------------------------

} // namespace util::details

//------------------------------------------------------------------------------
//--- util::MappedContainer
//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
auto util::MappedContainer<Cont, Mapping>::minimal_size() const -> size_type
{
  return minimal_size(fData.container(), fMapping.container());
}

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::map_element(MappingIndex_t index) const
{
  auto const dataIndex = map_index(index);
  return (dataIndex == InvalidIndex) ? defaultValue() : fData[dataIndex];
} // util::MappedContainer<>::map_element() const

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::map_element(MappingIndex_t index)
{
  auto const dataIndex = map_index(index);
  return (dataIndex == InvalidIndex) ? defaultValue() : fData[dataIndex];
} // util::MappedContainer<>::map_element()

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::at(MappingIndex_t index) const
{
  if (index >= size()) {
    throw std::out_of_range("MappedContainer::at(" + std::to_string(index) +
                            "): out of range (size: " + std::to_string(size()) + ")");
  }
  return map_element(index);
} // util::MappedContainer<>::at() const

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::at(MappingIndex_t index)
{
  if (index >= size()) {
    throw std::out_of_range("MappedContainer::at(" + std::to_string(index) +
                            "): out of range (size: " + std::to_string(size()) + ")");
  }
  return map_element(index);
} // util::MappedContainer<>::at()

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
auto util::MappedContainer<Cont, Mapping>::minimal_size(DataContainer_t const&,
                                                        Mapping_t const& mapping) -> size_type
{
  /*
   * Obscure compiler errors are expected if the `Mapping_t` type does not
   * support `std::size`. In that case, very simply, `minimal_size()` can't be
   * used and the caller must specify the size of the container.
   */

  using std::size;
  return size(util::collection_from_reference(mapping));
} // util::MappedContainer<>::minimal_size(DataContainer_t, Mapping_t)

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::map_index(MappingIndex_t index) const
{
  return fMapping[index];
}

//------------------------------------------------------------------------------
template <typename Cont, typename Mapping>
decltype(auto) util::MappedContainer<Cont, Mapping>::map_index(MappingIndex_t index)
{
  return fMapping[index];
}

//------------------------------------------------------------------------------

#endif // LARDATAALG_UTILITIES_MAPPEDCONTAINER_H