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

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

#pragma once

#include <tuple>

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

namespace iterator { namespace detail {
  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) };
}