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

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

#pragma once

#include <iterator>
#include <tuple>
#include <utility>

#include "end_aware_iterator.hpp"
#include "iterator_fwd.hpp"

namespace iterator { namespace detail {
  template <typename> struct void_t { using type = void; };

  template <typename IterType>
  using value_iterator = decltype(std::begin(*std::declval<IterType>()));

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

  struct terminal_layer_tag_t;
  struct continue_layer_tag_t;

  /**
   * @class recursive_iterator_base
   * @brief A thin wrapper around end_aware_iterator for the purposes of
   * template metaprogramming.
   */
  template <typename Iterator, typename = void>
  class recursive_iterator_base : public end_aware_iterator<Iterator> {
  public:
    using super = end_aware_iterator<Iterator>;

  protected:
    using recursive_category = terminal_layer_tag_t;

  public:
    using super::super;
    recursive_iterator_base(super const & iter) : super(iter) {}
    recursive_iterator_base(super && iter) : super(std::move(iter)) {}
    recursive_iterator_base() = default;
    operator super() const { return *this; }

  protected:
    typename super::reference get() const { return super::operator*(); }
  };

  /**
   * @class recursive_iterator_base
   * @brief An SFINAE specialization of recursive_iterator_base for associative
   * containers
   *
   * Because it is possible for recursive iterator to step over multiple layers
   * of associative containers, the return type is made into a tuple, so that
   * the caller does not need to write something like
   * `it->second.second.second'. Instead, the return type is a tuple of
   * references, so that the caller can write code like `std::get<3>(*it)'.
   *
   * For example, the ref type for std::map<int, std::map<float, double> >
   * with this would be std::tuple<int const&, float const&, double &>.
   */
  template <typename Iterator>
  class recursive_iterator_base<
      Iterator,
      typename std::enable_if<std::is_const<typename end_aware_iterator<
          Iterator>::value_type::first_type>::value>::type>
      : public end_aware_iterator<Iterator> {
  public:
    using super = end_aware_iterator<Iterator>;
    using first_type = decltype((std::declval<Iterator>()->first));
    using second_type = decltype((std::declval<Iterator>()->second));

  protected:
    using recursive_category = continue_layer_tag_t;

  public:
    using value_type = std::tuple<first_type, second_type>;
    using reference = std::tuple<first_type &, second_type &>;

  public:
    using super::super;
    recursive_iterator_base(super const & iter) : super(iter) {}
    recursive_iterator_base(super && iter) : super(std::move(iter)) {}
    recursive_iterator_base() = default;
    operator super() const { return *this; }

  protected:
    /**
     * An alternative function to operator*(), which allows single layer
     * recursive iterators (on associative containers) to return the
     * underlying value/reference type, and nested containers to propogate
     * a tuple or a pair as necessary.
     */
    reference get() const {
      auto & pair = super::operator*();
      return std::tie(pair.first, pair.second);
    }
  };

  /**
   * @class recursive_iterator_layer
   * @brief A single layer for recursing down a nested collection. Represents
   * non-associative containers.
   *
   * Provides dispatch/overloading for types and functions of recursive_iterator
   * chains to resolve ambiguous typedefs and operators.
   *
   * @see recursive_iterator_impl
   * @see bounded_recursive_iterator_impl
   * @tparam Iterator The underlying iterator type of the layer
   * @tparam RecursiveIterator_NextLayer The next layer, either a
   * recursive_iterator_impl, or a bounded_recursive_iterator_impl
   */
  template <typename Iterator, typename RecursiveIterator_NextLayer>
  class recursive_iterator_layer : public recursive_iterator_base<Iterator>,
                                   public RecursiveIterator_NextLayer {
  public:
    using super = RecursiveIterator_NextLayer;
    using layer = recursive_iterator_base<Iterator>;

  protected:
    using recursive_category = continue_layer_tag_t;

  public:
    using value_type = typename super::value_type;
    using reference = typename super::reference;
    using pointer = typename super::pointer;
    using difference_type = typename super::difference_type;
    using iterator_category = std::forward_iterator_tag;

  public:
    recursive_iterator_layer() = default;
    recursive_iterator_layer(layer v) : recursive_iterator_layer() {
      assign(v);
      update();
    }
    template <typename OIter, typename Rec>
    recursive_iterator_layer(recursive_iterator_layer<OIter, Rec> const & other)
        : layer(static_cast<recursive_iterator_base<OIter> const &>(other)),
          super(static_cast<Rec const &>(other)) {}
    template <typename OIter, typename... Iterators>
    recursive_iterator_layer(in_place_t, OIter && it, Iterators &&... iter)
        : layer(std::forward<OIter>(it)),
          super(in_place, std::forward<Iterators>(iter)...) {
      update();
    }

    reference operator*() const { return super::get(); }

    pointer operator->() const { return super::operator->(); }

    bool operator==(recursive_iterator_layer const & other) const {
      return layer::operator==(other) && super::operator==(other);
    }

  protected:
    reference get() const { return operator*(); }

    /**
     * Advance the iterator step. If the next layer has reached the end, then
     * we advance this iterator until it reaches either its own end, or a
     * non-empty subcollection to start iterating over.
     */
    void next() {
      super::next();
      update();
    }

    /**
     * Update the underlying iterator and propogate updates down the chain so
     * that if there is data available, the iterator is in a dereferencable
     * state.
     */
    void assign(layer v) {
      static_cast<layer &>(*this) = v;
      if (!v.done()) { super::assign(make_end_aware_iterator(*v)); }
    }

    void update() {
      layer & self = static_cast<layer &>(*this);
      while (super::done() && !(++self).done()) {
        super::assign(make_end_aware_iterator(*self));
      }
    }

    bool done() const { return layer::done(); }
  };

  /**
   * @class next_layer_type
   * @breif A template metaprogramming type for unifying associative and
   * non-associative containers.
   */
  template <typename V, typename Tag> struct next_layer_type {
    using type = std::tuple<V>;
  };
  template <typename V> struct next_layer_type<V, continue_layer_tag_t> {
    using type = V;
  };

  /**
   * @class flatten_iterator_layer
   * @brief A single layer for recursing down a nested collection. Represents
   * associative containers.
   *
   * @copydoc recursive_iterator_layer
   */
  template <typename Iterator, typename RecursiveIterator_NextLayer>
  class flatten_iterator_layer : public recursive_iterator_base<Iterator>,
                                 public RecursiveIterator_NextLayer {
  public:
    using super = RecursiveIterator_NextLayer;
    using layer = recursive_iterator_base<Iterator>;
    using key_type =
        typename std::tuple_element<0, typename layer::value_type>::type;

  protected:
    using recursive_category = continue_layer_tag_t;
    using next_value_type =
        typename next_layer_type<typename super::value_type,
                                 typename super::recursive_category>::type;
    using next_reference =
        typename next_layer_type<typename super::reference,
                                 typename super::recursive_category>::type;

  public:
    using value_type =
        decltype(std::tuple_cat(std::make_tuple(std::declval<key_type>()),
                                std::declval<next_value_type>()));
    using reference = decltype(std::tuple_cat(
        std::tie(std::declval<key_type>()), std::declval<next_reference>()));
    using pointer = void;
    using difference_type = typename super::difference_type;
    using iterator_category = std::forward_iterator_tag;

  public:
    flatten_iterator_layer() = default;
    flatten_iterator_layer(layer v) : flatten_iterator_layer() {
      assign(v);
      update();
    }
    template <typename OIter, typename Rec>
    flatten_iterator_layer(flatten_iterator_layer<OIter, Rec> const & other)
        : layer(static_cast<recursive_iterator_base<OIter> const &>(other)),
          super(static_cast<Rec const &>(other)) {}
    template <typename OIter, typename... Iterators>
    flatten_iterator_layer(in_place_t, OIter && it, Iterators &&... iter)
        : layer(std::forward<OIter>(it)),
          super(in_place, std::forward<Iterators>(iter)...) {
      update();
    }

    /**
     * @brief Concatenate the key in this layer, with the dereferenced data from
     * the next.
     *
     * Due to the use of the next_layer_type metaprogramming, a type such as
     * std::map<K, std::vector<std::tuple<T1, T2, T3>>> would return a reference
     * of type std::tuple<K const &, std::tuple<T1, T2, T3>&>, preserving
     * sub-aggregates of pair/tuple type. Similarly, forward_as_tuple means
     * even a key-type of pair/tuple will not be unwrapped.
     */
    reference operator*() const {
      return std::tuple_cat(std::forward_as_tuple(std::get<0>(layer::get())),
                            next_reference(super::get()));
    }

    /**
     * Unimplemented because we return an inline constructed type, and tuple
     * can only be accessed through std::get anyway.
     */
    pointer operator->() const;

    bool operator==(flatten_iterator_layer const & other) const {
      return layer::operator==(other) && super::operator==(other);
    }

  protected:
    reference get() const { return operator*(); }

    /**
     * @copydoc recursive_iterator_layer::next
     */
    void next() {
      super::next();
      update();
    }

    void update() {
      layer & self = static_cast<layer &>(*this);
      while (super::done() && !(++self).done()) {
        super::assign(make_end_aware_iterator(self->second));
      }
    }

    /**
     * @copydoc recursive_iterator_layer::assign
     */
    void assign(layer v) {
      static_cast<layer &>(*this) = v;
      if (!v.done()) { super::assign(make_end_aware_iterator(v->second)); }
    }

    bool done() const { return layer::done(); }
  };
}}

#include "recursive_iterator_meta.hpp"

namespace iterator {
  /**
   * @class recursive_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 Iterator The iterator type of the top-level collection.
   */
  template <typename Iterator>
  class recursive_iterator : public detail::recursive_iterator_impl<Iterator> {
  public:
    using super = detail::recursive_iterator_impl<Iterator>;

  public:
    using super::super;
    recursive_iterator() = default;
    template <typename... Iterators>
    recursive_iterator(in_place_t, Iterators &&... iter)
        : super(in_place, std::forward<Iterators>(iter)...) {}

    recursive_iterator & operator++() {
      (void)super::next();
      return *this;
    }

    recursive_iterator operator++(int) {
      recursive_iterator tmp{*this};
      (void)super::next();
      return tmp;
    }

    bool operator!=(recursive_iterator const & other) {
      return !(super::operator==(other));
    }
  };

  /**
   * @class recursive_iterator_n
   * @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 Iterator, std::size_t N>
  class recursive_iterator_n
      : public detail::bounded_recursive_iterator_impl<Iterator, 1, N> {
  public:
    using super = detail::bounded_recursive_iterator_impl<Iterator, 1, N>;

  public:
    using super::super;
    recursive_iterator_n() = default;
    template <typename... Iterators>
    recursive_iterator_n(in_place_t, Iterators &&... iter)
        : super(in_place, std::forward<Iterators>(iter)...) {}

    recursive_iterator_n & operator++() {
      (void)super::next();
      return *this;
    }

    recursive_iterator_n operator++(int) {
      recursive_iterator_n tmp{*this};
      (void)super::next();
      return tmp;
    }

    bool operator!=(recursive_iterator_n const & other) {
      return !(super::operator==(other));
    }
  };
}

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

template <typename Iter0, typename... Iters>
auto make_recursive_iterator(iterator::end_aware_iterator<Iter0> it,
                             Iters &&... iters)
    -> iterator::recursive_iterator<Iter0> {
  return {iterator::in_place, std::move(it), std::forward<Iters>(iters)...};
}

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

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