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 <iterator>
#include <string>
#include <tuple>
#include <utility>

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

namespace iterator::recursive {
  // Helpers for condensing type deductions
  template <typename IterType>
  using value = decltype(std::begin(*std::declval<IterType>()));

  template <typename IterType>
  using mapped = decltype(std::begin(std::declval<IterType>()->second));

  // Type trait to identify value_type ~~ std::pair<K const, V>, which is
  // a safe bet towards 'this is an associative container type'
  template <typename T, typename = void>
  struct is_associative : std::false_type {};
  template <typename T>
  struct is_associative<T, std::enable_if_t<std::is_const<
                               typename T::value_type::first_type>::value>>
      : std::true_type {};

  // Type deduction guides for constructing recursive iterators.
  enum class typeclass { TERMINAL, CONTAINER, ASSOCIATIVE_CONTAINER };

  template <typename T, typename = void> struct typeclass_t {
    static constexpr typeclass const value{typeclass::TERMINAL};
  };

  template <typename T> struct is_string_iterator : std::false_type {};
  template <>
  struct is_string_iterator<std::string::iterator> : std::true_type {};
  template <>
  struct is_string_iterator<std::string::const_iterator> : std::true_type {};

  template <typename T>
  struct typeclass_t<T,
                     std::enable_if_t<!is_string_iterator<value<T>>::value>> {
    static constexpr typeclass const value{typeclass::CONTAINER};
  };

  template <typename T>
  struct typeclass_t<T, std::enable_if_t<is_string_iterator<value<T>>::value>> {
    static constexpr typeclass const value{typeclass::TERMINAL};
  };

  template <typename T> struct typeclass_t<T, detail::void_t<mapped<T>>> {
    static constexpr typeclass const value{typeclass::ASSOCIATIVE_CONTAINER};
  };
}

namespace iterator::recursive {
  template <size_t N, size_t I = 1> struct bounded {
    template <typename It>
    static constexpr typeclass const value =
        I == N ? typeclass::TERMINAL : 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 typeclass 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,
            typeclass = Bnd::template value<It>>
  struct tuple;

  template <typename It, typename Bnd>
  struct tuple<It, Bnd, typeclass::TERMINAL> {
    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, typeclass::CONTAINER> {
    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, typeclass::ASSOCIATIVE_CONTAINER> {
    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); };
  };

  template <typename It, typename Bnd = unbounded>
  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, typeclass::TERMINAL>{}.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 iterator {
  /**
   * @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.
   */
  template <typename It> using recursive_iterator = recursive::rimpl<It>;

  /**
   * @copydoc recursive_iterator
   * This object has bounded recursive depth, so that it can be used to get
   * sub-collections, which may be used in other functions.
   *
   * For Example:
   * @code
   * using map_type = std::map<std::string, std::map<std::string,
   * std::vector<Data> > >;
   * ...
   * recursive_iterator_n<map_type::iterator, 2> iter{ ... };
   * std::vector<Data> & data = std::get<2>(*iter);
   * reload_data_from_file( std::get<1>(*iter), data );
   * @endcode
   *
   * @tparam N The maximum depth to recurse into the object
   */
  template <typename It, std::size_t N>
  using recursive_iterator_n = recursive::rimpl<It, recursive::bounded<N>>;
}

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