//===-- rosa/support/iterator/split_tuple_iterator.hpp ----------*- C++ -*-===/
//
//                                 The RoSA Framework
//
//===----------------------------------------------------------------------===/
///
/// \file rosa/support/iterator/split_tuple_iterator.hpp
///
/// \authors David Juhasz (david.juhasz@tuwien.ac.at)
///
/// \date 2019
///
/// \brief Facilities to split iterators of \c std::tuple into iterators of
/// their elements.
///
//===----------------------------------------------------------------------===/

#ifndef ROSA_SUPPORT_ITERATOR_SPLIT_TUPLE_ITERATOR_HPP
#define ROSA_SUPPORT_ITERATOR_SPLIT_TUPLE_ITERATOR_HPP

#include "rosa/support/debug.hpp"
#include "rosa/support/sequence.hpp"

#include <memory>
#include <tuple>
#include <type_traits>
#include <queue>

namespace rosa {
namespace iterator {

/// Anonymous namespace providing implementation for splitting tuple iterators;
/// consider it private.
namespace {

/// Iterator of values provided by a buffer based on an index
///
/// \tparam TB buffer providing values to iterate
/// \tparam I index of the values to iterator from \p TB
///
/// \note \p TB is expected to implemnet an interface matching that of \c
/// TupleIteratorBuffer.
template <typename TB, size_t I>
class SplittedElementIterator {
public:
  /// Type alias for the values the iterator iterates.
  using T = typename TB::template element_type<I>;

  /// \defgroup SplittedElementIteratorTypedefs Typedefs of 
  /// \c SplittedElementIterator
  ///
  /// Standard `typedef`s for iterators.
  ///
  ///@{
  typedef std::input_iterator_tag
      iterator_category;               ///< Category of the iterator.
  typedef T value_type;                ///< Type of values iterated over.
  typedef std::size_t difference_type; ///< Type to identify distance.
  typedef T *pointer;                  ///< Pointer to the type iterated over.
  typedef T &reference;                ///< Reference to the type iterated ver.
  ///@}

  /// Creates a new instance.
  ///
  /// \param Buffer buffer providing values for \p this object
  ///
  /// \note \p Buffer is captured as a \c std::shared_ptr because it is shared
  /// among iterators for its element positions.
  SplittedElementIterator(std::shared_ptr<TB> Buffer)
      : Buffer(Buffer), Value() {
    // \c Value is initialized empty so the first incrementation here will read
    // the first value.
    ++(*this);
  }

  /// Creates an empty new instance.
  SplittedElementIterator(void) noexcept : Buffer(), Value() {}

  /// Pre-increment operator.
  ///
  /// The implementation reads the next value from \c Buffer. If no more values
  /// can be provided by \c Buffer, \p this object becomes empty and the
  /// operator has no further effect.
  ///
  /// \return \p this object after incrementing it.
  SplittedElementIterator &operator++() {
    if (Buffer->template hasMore<I>()) {
      Value = Buffer->template next<I>();
    } else {
      // Reached end of range, remove reference of \c Buffer.
      Buffer.reset();
    }
    return *this;
  }

  /// Post-increment operator.
  ///
  /// The implementation uses the pre-increment operator and returns a copy of
  /// the original state of \p this object.
  ///
  /// \return \p this object before incrementing it.
  SplittedElementIterator operator++(int) {
    SplittedElementIterator<TB, I> Tmp(*this);
    ++(*this);
    return Tmp;
  }

  /// Returns a constant reference to the current value.
  ///
  /// \note Should not dereference the iterator when it is empty.
  ///
  /// \return constant reference to the current value.
  const T &operator*(void)const noexcept { return Value; }

  /// Returns a constant pointer to the current value.
  ///
  /// \note Should not dereference the iterator when it is empty.
  ///
  /// \return constant pointer to the current value.
  const T *operator->(void)const noexcept { return &Value; }

  /// Tells if \p this object is equal to another one.
  ///
  /// Two \c SplittedElementIterator instances are equal if and only if they are
  /// the same or both are empty.
  ///
  /// \param RHS other object to compare to
  ///
  /// \return whether \p this object is equal with \p RHS
  bool operator==(const SplittedElementIterator &RHS) const noexcept {
    return ((this == &RHS) || (!Buffer && !RHS.Buffer));
  }

  /// Tells if \p this object is not equal to another one.
  ///
  /// \see SplittedElementIterator::operator==
  ///
  /// \param RHS other object to compare to
  ///
  /// \return whether \p this object is not equal with \p RHS.
  bool operator!=(const SplittedElementIterator &RHS) const noexcept {
    return !((*this) == RHS);
  }

private:
  std::shared_ptr<TB> Buffer; ///< Buffer providing values for \p this object
  T Value;                    ///< The current value of the iterator
};

///\defgroup TupleBufferContainer Type converter turning a \c std::tuple of
///types into a \c std::tuple of container of those types.
///
/// The new type is used for buffering elements of tuples separately.
///
///@{

/// Template declaration.
///
/// \tparam T type to convert
///
/// \note The template is defined only when \p T is a \c std::tuple.
///
/// Usage for a type \c Tuple as:\code
/// typename TupleBufferContainer<Tuple>::Type
/// \endcode
template <typename T> struct TupleBufferContainer;

/// Template definition for \c std::tuple.
template <typename... Ts> struct TupleBufferContainer<std::tuple<Ts...>> {
  /// The converted type.
  using Type = std::tuple<std::queue<Ts>...>;
};

///@}

/// Convenience template type alias for easy use of \c TupleBufferContainer.
///
/// Converts a \c std::tuple of types into a \c std::tuple of container of those
/// types.
///
/// \tparam Tuple type to convert
template <typename Tuple>
using tuple_buffer_container_t = typename TupleBufferContainer<Tuple>::Type;

/// Buffer for element values for iterator of \c std::tuple.
///
/// The class can be instantiated with a range of iterator of \c std::tuple and
/// provides an interface for accessing elements of the iterated tuples one by
/// one.
///
/// \note The class is utilized by \c SplittedElementIterator.
///
/// \tparam TupleIterator the iterator type that provides values of \c
/// std::tuple
///
/// \todo Consider thread safety of the class.
template <typename TupleIterator>
class TupleIteratorBuffer {
public:
  /// Type alias for the value type of \p TupleIterator.
  /// \note The type is expected to be \c std::tuple.
  using iterator_value_type = typename TupleIterator::value_type;

  /// The number of elements of \c iterator_value_type.
  static constexpr size_t iterator_value_size =
      std::tuple_size_v<iterator_value_type>;

  /// Template type alias to get element types of \c iterator_value_type by
  /// index.
  /// \tparam I the index of the element
  template <size_t I>
  using element_type =
      typename std::tuple_element<I, iterator_value_type>::type;

  /// Type alias for index sequence for accessing elements of \c
  /// iterator_value_type.
  using element_idx_seq_t = seq_t<iterator_value_size>;

  /// Creates a new instance.
  ///
  /// \param Begin the beginning of the iterator range to buffer
  /// \param End the end of the iterator range to buffer
  TupleIteratorBuffer(TupleIterator &&Begin, const TupleIterator &End) noexcept
      : Iterator(Begin), End(End), Buffer() {}

  /// Tells whether there is any more value in the handled range for index \p I.
  ///
  /// \tparam I the index of the element to check
  ///
  /// \return whether there is more value for index \p I
  template <size_t I> bool hasMore(void) const noexcept {
    const auto &ElementBuffer = std::get<I>(Buffer);
    // There is more value if some has already been buffered or the end of the
    // handled range is not reached yet.
    return !ElementBuffer.empty() || Iterator != End;
  }

  /// Gives the next value from the handled range for index \p I.
  ///
  /// \note The function should not be called if there is no more value for
  /// index \p I (i.e., \c hasMore<I>() returns \c false). If it is called in
  /// that situation, it returns the default value of \c element_type<I>.
  ///
  /// \tparam I the index of the element to fetch next value for
  ///
  /// \return the next value for index \p I
  template <size_t I> element_type<I> next(void) noexcept {
    auto &ElementBuffer = std::get<I>(Buffer);
    if (ElementBuffer.empty()) {
      // This position needs a new value from Iterator if there is more.
      if (Iterator != End) {
        // Push next value for all elements.
        push(*Iterator++, element_idx_seq_t());
      } else {
        // No more values; called when hasMore<I>() is false.
        // Return default value.
        return element_type<I>();
      }
    }
    // Buffer is not empty here, return the next value.
    ASSERT(!ElementBuffer.empty() && "Unexpected condition");
    // Get the next value and also pop it from the buffer.
    const element_type<I> Elem = ElementBuffer.front();
    ElementBuffer.pop();
    return Elem;
  }

private:
  /// Buffers next tuple value elementwise into element containers.
  ///
  /// \tparam S0 indices for accessing elements of \c std::tuple
  ///
  /// \param Tuple the values to buffer
  ///
  /// \note The second parameter provides indices as template parameter \p S0
  /// and its actual value is ignored.
  template <size_t... S0>
  void push(const iterator_value_type &Tuple, Seq<S0...>) noexcept {
    (std::get<S0>(Buffer).push(std::get<S0>(Tuple)), ...);
  }

  TupleIterator Iterator;  ///< Current input iterator
  const TupleIterator End; ///< End of iterator range to handle
  tuple_buffer_container_t<iterator_value_type>
      Buffer; ///< Container for elementwise buffering
};

/// Template type alias for iterator of an element based on buffered iterator of
/// \c std::tuple.
///
/// The alias utilizes \c SplittedElementIterator for iterating over the values
/// provided by \p TB.
///
/// \tparam TB buffer providing values to iterate
/// \tparam I index of the values to iterator from \p TB
template <typename TB, size_t I>
using element_iterator_t = SplittedElementIterator<TB, I>;

/// Template type alias for iterator-range of an element based on buffered
/// iterator of \c std::tuple.
///
/// \tparam TB buffer providing values to iterate
/// \tparam I index of the values to iterator from \p TB
template <typename TB, size_t I>
using element_iterator_range_t =
    std::pair<element_iterator_t<TB, I>, element_iterator_t<TB, I>>;

///\defgroup ElementIteratorRanges Type converter turning a buffer of \c
/// std::tuple into a \c std::tuple of corresponding \c
/// element_iterator_range_t.
///
///@{

/// Template declaration.
///
/// \tparam TB buffer providing values
/// \tparam S type providing indices for accessing elements of \c std::tuple
///
/// \note \p TB is expected to implement an interface matching that of \c
/// TupleIteratorBuffer.
///
/// \note The template is defined only when \p S is a \c rosa::Seq.
///
/// Usage for a proper buffer type \c TB:\code
/// typename ElementIteratorRanges<TB, typename TB::element_idx_seq_t>::Type
/// \endcode
template <typename TB, typename S> struct ElementIteratorRanges;

/// Template definition.
template <typename TB, size_t... S0>
struct ElementIteratorRanges<TB, Seq<S0...>> {
  /// The converted type.
  using Type = std::tuple<element_iterator_range_t<TB, S0>...>;
};

///@}

/// Convenience template type alias for easy use of \c ElementIteratorRanges.
///
/// Converts a buffer of \c std::tuple into a \c std::tuple of corresponding \c
/// element_iterator_range_t.
///
/// \tparam TB buffer providing values
///
/// \note \p TB is expected to implement an interface matching that of \c
/// TupleIteratorBuffer.
template <typename TB>
using element_iterator_ranges_t =
    typename ElementIteratorRanges<TB, typename TB::element_idx_seq_t>::Type;

/// Template type alias for turning an iterator of \c std::tuple into
/// corresponding \c element_iterator_ranges_t.
///
/// The alias utilizes \c TupleIteratorBuffer for buffering the values provided
/// by \p TupleIterator. The elementwise iterators are \c
/// SplittedElementIterator.
///
/// \tparam TupleIterator iterator of \c std::tuple
template <typename TupleIterator>
using splitted_tuple_iterator_ranges_t =
    element_iterator_ranges_t<TupleIteratorBuffer<TupleIterator>>;

/// Creates elementwise iterator ranges for an iterator range of \c std::tuple.
///
/// \note Implementation for \c rosa::iterator::splitTupleIterator.
///
/// \tparam TupleIterator iterator of \c std::tuple
/// \tparam S0 indices for accessing elements of \c std::tuple
///
/// \param Begin the beginning of the iterator range to handle
/// \param End the end of the iterator range to handle
///
/// \note The last parameter provides indices as template parameter \p S0 and
/// its actual value is ignored.
///
/// \return \c std::tuple of elementwise iterator ranges corresponding to \p
/// Begin and \p End
template <typename TupleIterator, size_t... S0>
splitted_tuple_iterator_ranges_t<TupleIterator>
splitTupleIteratorImpl(TupleIterator &&Begin, const TupleIterator &End,
                       Seq<S0...>) noexcept {
  using TB = TupleIteratorBuffer<TupleIterator>;
  // Create a buffer in shared pointer. The buffer will be destructed once
  // all corresponding element iterators (created below) have reached the end of
  // the handled range or have been destructed.
  auto Buffer = std::make_shared<TB>(std::move(Begin), End);
  return {std::make_pair(element_iterator_t<TB, S0>(Buffer),
                         element_iterator_t<TB, S0>())...};
}

} // End namespace

/// Gives the beginning of a range created by \c splitTupleIterator().
///
/// \see rosa::iterator::splitTupleIterator()
///
/// \note The signature of the template function uses implementation details.
///
/// \tparam TB buffer providing values to iterate
/// \tparam I index of the values to iterator from \p TB
///
/// \param Range range to get the beginning of
///
/// \return beginning of \p Range
template <typename TB, size_t I>
element_iterator_t<TB, I> &begin(element_iterator_range_t<TB, I> &Range) {
  return Range.first;
}

/// Gives the end of a range created by \c splitTupleIterator().
///
/// \see rosa::iterator::splitTupleIterator()
///
/// \note The signature of the template function uses implementation details.
///
/// \tparam TB buffer providing values to iterate
/// \tparam I index of the values to iterator from \p TB
///
/// \param Range range to get the end of
///
/// \return end of \p Range
template <typename TB, size_t I>
element_iterator_t<TB, I> &end(element_iterator_range_t<TB, I> &Range) {
  return Range.second;
}

/// Creates elementwise iterator ranges for an iterator range of \c std::tuple.
///
/// \note The implementation utilizes \c splitTupleIteratorImpl.
///
/// Obtain element iterator ranges for an iterator range \c Begin and \c End of
/// iterator type \c TupleIterator of \c std::tuple<T1, T2, T3> as \code
/// auto [T1Range, T2Range, T3Range] = splitTupleIterator(std::move(Begin), End);
/// auto [T1Begin, T1End] = T1Range;
/// auto [T2Begin, T2End] = T2Range;
/// auto [T3Begin, T3End] = T3Range;
/// \endcode
/// One range can also be dissected by dedicated functions like \code
/// auto T1Begin = begin(T1Range);
/// auto T1End = end(T1Range);
/// \endcode
///
/// The function returns a tuple of ranges (i.e., \c std::pair of iterators),
/// which can be assigned to variables using structured binding. The ranges can
/// be dissected into begin and end iterators by separate structured bindings.
///
/// The function moves its first argument (i.e., \p Begin cannot be used
/// directly after splitting it). If the first argument is a variable, it needs
/// to be moved explicitly by \c std::move() as in the example.
///
/// \tparam TupleIterator iterator of \c std::tuple
///
/// \param Begin the beginning of the iterator range to handle
/// \param End the end of the iterator range to handle
///
/// \return \c std::tuple of elementwise iterator ranges corresponding to \p
/// Begin and \p End
template <typename TupleIterator>
splitted_tuple_iterator_ranges_t<TupleIterator>
splitTupleIterator(TupleIterator &&Begin, const TupleIterator &End) noexcept {
  return splitTupleIteratorImpl(
      std::move(Begin), End,
      seq_t<std::tuple_size_v<typename TupleIterator::value_type>>());
}

} // End namespace iterator
} // End namespace rosa

#endif // ROSA_SUPPORT_ITERATOR_SPLIT_TUPLE_ITERATOR_HPP