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)};
}