cpp-useful-iterators/include/iterator/recursive_iterator.hpp

//
//  recursive_iterator.hpp
//  iterator
//
//  Created by Sam Jaffe on 2/17/17.
//

#pragma once

#include "iterator_fwd.hpp"

#include <string>
#include <tuple>
#include <utility>

#include "detail/recursive_traits.h"
#include "end_aware_iterator.hpp"
#include "facade.h"

namespace iterator::recursive {
template <size_t N, size_t I> struct bounded {
  template <typename It>
  static constexpr recursion_type const value =
      I == N ? recursion_type::END : typeclass_t<It>::value;
  using next = std::conditional_t<I == N, void, bounded<N, I + 1>>;
  static constexpr size_t size = N;
};

struct unbounded {
  template <typename It>
  static constexpr recursion_type const value = typeclass_t<It>::value;
  using next = unbounded;
  static constexpr size_t size = std::numeric_limits<size_t>::max();
};

template <typename It, typename Bnd = unbounded,
          recursion_type = Bnd::template value<It>>
struct tuple;

template <typename It, typename Bnd>
struct tuple<It, Bnd, recursion_type::END> {
  using iter = std::tuple<end_aware_iterator<It>>;
  decltype(auto) get(It iter) const {
    if constexpr (is_associative<It>{}) {
      return std::tie(iter->first, iter->second);
    } else {
      return std::tie(*iter);
    }
  }
};

template <typename... Ts>
using tuple_cat_t = decltype(std::tuple_cat(std::declval<Ts>()...));

template <typename It, typename Bnd>
struct tuple<It, Bnd, recursion_type::THRU> {
  using next = decltype(std::begin(*std::declval<It>()));
  using iter = tuple_cat_t<std::tuple<end_aware_iterator<It>>,
                           typename tuple<next, typename Bnd::next>::iter>;
  auto get(It) const { return std::make_tuple(); }
};

template <typename It, typename Bnd>
struct tuple<It, Bnd, recursion_type::ASSOC> {
  using next = decltype(std::begin(std::declval<It>()->second));
  using iter = tuple_cat_t<std::tuple<end_aware_iterator<It>>,
                           typename tuple<next, typename Bnd::next>::iter>;
  auto get(It iter) const { return std::tie(iter->first); };
};

/**
 * @brief An iterator type for nested collections, allowing you to treat it as
 * a single-layer collection.
 *
 * In order to provide a simple interface, if an associative container is used
 * in the chain, the type returned by operator*() is a tuple. If multiple
 * associative containers are nested, then the tuple will be of the form
 * std::tuple<key1, key2, ..., keyN, value>. To avoid copies, and allow
 * editting of underlying values, the tuple contains references.
 *
 * @tparam It The iterator type of the top-level collection.
 * @tparam Bnd The bounding type, representing how many layers this iterator
 * is willing to delve in the parent object.
 */
template <typename It, typename Bnd>
class rimpl : public facade<rimpl<It, Bnd>> {
private:
  typename tuple<It, Bnd>::iter impl_;

public:
  static constexpr size_t size =
      std::min(std::tuple_size_v<typename tuple<It, Bnd>::iter>, Bnd::size);

  rimpl() = default;
  rimpl(end_aware_iterator<It> iter) { assign<0>(iter); }
  template <typename Ot>
  rimpl(end_aware_iterator<Ot> other) : rimpl(end_aware_iterator<It>(other)) {}
  template <typename Ot>
  rimpl(rimpl<Ot, Bnd> other) : rimpl(end_aware_iterator<Ot>(other)) {}

  template <typename T> operator end_aware_iterator<T>() const {
    return std::get<end_aware_iterator<T>>(impl_);
  }

  decltype(auto) dereference() const {
    // Special Case Handling for circumstances where at least everything up to
    // the deepest nested container is non-associative. In this case, we don't
    // want to transmute our single element/association into a tuple, since
    // there's no benefit from that.
    if constexpr (std::tuple_size_v<decltype(this->build_tuple())> == 1) {
      return *std::get<size - 1>(impl_);
    } else {
      return build_tuple();
    }
  }

  template <size_t I = size - 1> bool increment() {
    auto & iter = std::get<I>(impl_);
    if (iter.at_end()) { return false; } // Make sure we don't go OOB
    ++iter;
    if constexpr (I > 0) {
      while (iter.at_end() && increment<I - 1>()) {
        assign<I>(*std::get<I - 1>(impl_));
      }
    }
    return !iter.at_end();
  }

  bool at_end() const { return std::get<0>(impl_).at_end(); }
  bool equal_to(rimpl const & other) const { return impl_ == other.impl_; }

  // Used by std::get, don't use elsewhere...
  auto const & impl() const { return impl_; }

private:
  template <size_t I = 0> decltype(auto) build_tuple() const {
    // In the case of a bounded recursive iterator, I need to ensure that the
    // effectively terminal iterator is treated as such even if there is still
    // iteration to be had.
    auto it = std::get<I>(impl_);
    if constexpr (I == size - 1) {
      return tuple<decltype(it), unbounded, recursion_type::END>{}.get(it);
    } else {
      // Implemented as a recursive function instead of a parameter-pack
      // because OSX has a compiler bug regarding certain forms of parameter
      // packs...
      return std::tuple_cat(tuple<decltype(it)>{}.get(it),
                            build_tuple<I + 1>());
    }
  }

  template <size_t I, typename C> void assign(end_aware_iterator<C> it) {
    std::get<I>(impl_) = it;
    if constexpr (I < size - 1) {
      if (!it.at_end()) { assign<I + 1>(*it); }
    }
  }

  template <size_t I, typename C> void assign(C && collection) {
    assign<I>(make_end_aware_iterator(std::forward<C>(collection)));
  }

  template <size_t I, typename K, typename V>
  void assign(std::pair<K const, V> const & pair) {
    assign<I>(pair.second);
  }
  template <size_t I, typename K, typename V>
  void assign(std::pair<K const, V> & pair) {
    assign<I>(pair.second);
  }
};
}

MAKE_ITERATOR_FACADE_TYPEDEFS_T(::iterator::recursive::rimpl);

namespace std {
template <std::size_t I, typename It>
auto get(::iterator::recursive_iterator<It> const & iter) {
  return ::std::get<I>(iter.impl());
}

template <std::size_t I, typename It, std::size_t N>
auto get(::iterator::recursive_iterator_n<It, N> const & iter) {
  static_assert(I < N, "Cannot get past bounding level");
  return ::std::get<I>(iter.impl());
}
}

template <typename C>
auto make_recursive_iterator(C & collect)
    -> iterator::recursive_iterator<decltype(std::begin(collect))> {
  return iterator::recursive_iterator<decltype(std::begin(collect))>{
      make_end_aware_iterator(collect)};
}

template <typename C>
auto make_recursive_iterator(C const & collect)
    -> iterator::recursive_iterator<decltype(std::begin(collect))> {
  return iterator::recursive_iterator<decltype(std::begin(collect))>{
      make_end_aware_iterator(collect)};
}

template <std::size_t Max, typename C>
auto make_recursive_iterator(C & collect)
    -> iterator::recursive_iterator_n<decltype(std::begin(collect)), Max> {
  return iterator::recursive_iterator_n<decltype(std::begin(collect)), Max>{
      make_end_aware_iterator(collect)};
}

template <std::size_t Max, typename C>
auto make_recursive_iterator(C const & collect)
    -> iterator::recursive_iterator_n<decltype(std::begin(collect)), Max> {
  return iterator::recursive_iterator_n<decltype(std::begin(collect)), Max>{
      make_end_aware_iterator(collect)};
}