cpp-useful-iterators/recursive_iterator.hpp

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

#pragma once

#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
     * @breif 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> {
    private:
      using super = end_aware_iterator<Iterator>;
    protected:
      using recursive_category = terminal_layer_tag_t;
    public:
      using super::super;
      recursive_iterator_base() = default;
      operator super() const { return *this; }
    protected:
      typename super::reference get() { 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> {
    private:
      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() = 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() {
        auto & pair = super::operator*();
        return std::tie(pair.first, pair.second);
      }
    };
    
    /**
     * @class recursive_iterator_layer
     * @breif 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
     * @param Iterator The underlying iterator type of the layer
     * @param 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 {
    private:
      using next_layer = RecursiveIterator_NextLayer;
      using layer = recursive_iterator_base< Iterator >;
    protected:
      using recursive_category = continue_layer_tag_t;
    public:
      using value_type = typename next_layer::value_type;
      using reference = typename next_layer::reference;
      using pointer = typename next_layer::pointer;
      using difference_type = typename next_layer::difference_type;
      using iterator_category = typename next_layer::iterator_category;
    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)), next_layer(static_cast<Rec const&>(other)) {}
      template <typename OIter, typename... Iterators>
      recursive_iterator_layer(in_place_t, OIter it, Iterators && ...iter)
      : layer(it), next_layer(in_place, iter...) {
        update();
      }

      reference operator*() {
        return next_layer::get();
      }
      
      pointer operator->() {
        return next_layer::operator->();
      }
      
      bool operator==(recursive_iterator_layer const & other) const {
        return layer::operator==(other) && next_layer::operator==(other);
      }
    protected:
      reference get() { 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() {
        next_layer::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()) {
          next_layer::assign(make_end_aware_iterator(*v));
        }
      }
      
      void update() {
        layer & self = static_cast<layer&>(*this);
        while ( next_layer::done() && !(++self).done() ) {
          next_layer::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
     * @breif 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 :
    recursive_iterator_base< Iterator >,
    RecursiveIterator_NextLayer {
    private:
      using next_layer = 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 next_layer::value_type, typename next_layer::recursive_category>::type;
      using next_reference = typename next_layer_type<typename next_layer::reference, typename next_layer::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 next_layer::difference_type;
      using iterator_category = typename next_layer::iterator_category;
    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)), next_layer(static_cast<Rec const&>(other)) {}
      template <typename OIter, typename... Iterators>
      flatten_iterator_layer(in_place_t, OIter it, Iterators && ...iter)
      : layer(it), next_layer(in_place, iter...) {
        update();
      }
      
      /**
       * @breif 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*() {
        return std::tuple_cat(std::forward_as_tuple(std::get<0>(layer::get())),
                              next_reference(next_layer::get()));
      }
      
      /**
       * Unimplemented because we return an inline constructed type, and tuple
       * can only be accessed through std::get anyway.
       */
      pointer operator->();
      
      bool operator==(flatten_iterator_layer const & other) const {
        return layer::operator==(other) && next_layer::operator==(other);
      }
    protected:
      reference get() { return operator*(); }

      /**
       * @copydoc recursive_iterator_layer::next
       */
      void next() {
        next_layer::next();
        update();
      }
      
      void update() {
        layer & self = static_cast<layer&>(*this);
        while ( next_layer::done() && !(++self).done() ) {
          next_layer::assign(make_end_aware_iterator(self->second));
        }
      }
      
      /**
       * @copydoc recursive_iterator_layer::assign
       */
      void assign(layer v) {
        static_cast<layer&>(*this) = v;
        if ( !v.done() ) {
          next_layer::assign(make_end_aware_iterator(v->second));
        }
      }
      
      bool done() const { return layer::done(); }
    };
    
    /**
     * @class bounded_recursive_iterator_impl
     * @brief The default (terminal) implementation of a recursive iterator up to Max levels deep.
     *
     * @see recursive_iterator_base
     * @param Iterator The iterator type being processed, such as std::vector<int>::iterator
     * @param N The current layer of depth, starts at 1.
     * @param Max The maximum recursive depth to dive down, in case you need to process some sub-collection in a specific manner.
     */
    template <typename Iterator, std::size_t N, std::size_t Max, typename = void>
    class bounded_recursive_iterator_impl :
    public recursive_iterator_base< Iterator > {
    private:
      using super = recursive_iterator_base< Iterator >;
    public:
      using super::super;
      bounded_recursive_iterator_impl() = default;
      template <typename OIter>
      bounded_recursive_iterator_impl(in_place_t, OIter iter) : super(iter) {}
    protected:
      void next() { super::operator++(); }
      void assign(super eat) { static_cast<super&>(*this) = eat; }
    };
    
    /**
     * @class bounded_recursive_iterator_impl
     * 
     * An SFINAE specialization of bounded_recursive_iterator_impl for 
     * non-associative container types.
     * @see recursive_iterator_layer
     */
    template <typename Iterator, std::size_t N, std::size_t Max>
    class bounded_recursive_iterator_impl< Iterator, N, Max, typename std::enable_if<N < Max, typename void_t<value_iterator<Iterator>>::type>::type > :
    public recursive_iterator_layer< Iterator , bounded_recursive_iterator_impl< value_iterator<Iterator>, N+1, Max > > {
    private:
      using next_layer = bounded_recursive_iterator_impl< value_iterator<Iterator>, N+1, Max >;
      using super = recursive_iterator_layer< Iterator, next_layer >;
    public:
      /**
       * A special override of operator* that allows collections like
       * std::vector<std::vector<std::map<K, V>>> still use the value/reference
       * type of the map. Works only for nested collections with one associative
       * container at the bottom/Max level.
       */
      auto operator*() -> decltype(*(next_layer&)(*this)) { return next_layer::operator*(); }
      using super::super;
      bounded_recursive_iterator_impl() = default;
      template <typename... Iterators>
      bounded_recursive_iterator_impl(in_place_t, Iterators && ...iter) : super(in_place, iter...) {}
    };
    
    /**
     * @class recursive_iterator_impl
     * @brief The default (terminal) implementation of an unbounded recursive iterator.
     *
     * @see recursive_iterator_base
     * @param Iterator The iterator type being processed, such as std::vector<int>::iterator
     */
    template <typename Iterator, typename = void>
    class recursive_iterator_impl : public recursive_iterator_base< Iterator > {
    private:
      using super = recursive_iterator_base< Iterator >;
    public:
      using super::super;
      recursive_iterator_impl() = default;
      template <typename OIter>
      recursive_iterator_impl(in_place_t, OIter iter) : super(iter) {}
    protected:
      void next() { super::operator++(); }
      void assign(super eat) { static_cast<super&>(*this) = eat; }
    };
    
    /**
     * @class recursive_iterator_impl
     *
     * An SFINAE specialization of bounded_recursive_iterator_impl for
     * non-associative container types.
     * @see recursive_iterator_layer
     */
    template <typename Iterator>
    class recursive_iterator_impl< Iterator, typename void_t<value_iterator<Iterator>>::type > :
    public recursive_iterator_layer< Iterator, recursive_iterator_impl< value_iterator<Iterator> > > {
    private:
      using next_layer = recursive_iterator_impl< value_iterator<Iterator> >;
      using super = recursive_iterator_layer< Iterator, next_layer >;
    public:
      /**
       * A special override of operator* that allows collections like
       * std::vector<std::vector<std::map<K, V>>> still use the value/reference
       * type of the map. Works only for nested collections with one associative
       * container at the bottom level.
       */
      auto operator*() -> decltype(*(next_layer&)(*this)) { return next_layer::operator*(); }
      using super::super;
      recursive_iterator_impl() = default;
      template <typename... Iterators>
      recursive_iterator_impl(in_place_t, Iterators && ...iter) : super(in_place, iter...) {}
    };
    
    /**
     * @class bounded_recursive_iterator_impl
     *
     * An SFINAE specialization of bounded_recursive_iterator_impl for
     * associative container types.
     * @see flatten_iterator_layer
     */
    template <typename Iterator, std::size_t N, std::size_t Max>
    class bounded_recursive_iterator_impl< Iterator, N, Max, typename std::enable_if<N < Max, typename void_t<mapped_iterator<Iterator>>::type>::type > :
    public flatten_iterator_layer< Iterator , bounded_recursive_iterator_impl< mapped_iterator<Iterator>, N+1, Max > > {
    private:
      using next_layer = bounded_recursive_iterator_impl< mapped_iterator<Iterator>, N+1, Max >;
      using super = flatten_iterator_layer< Iterator, next_layer >;
    public:
      using super::super;
      bounded_recursive_iterator_impl() = default;
      template <typename... Iterators>
      bounded_recursive_iterator_impl(in_place_t, Iterators && ...iter) : super(in_place, iter...) {}
    };
    
    /**
     * @class recursive_iterator_impl
     *
     * An SFINAE specialization of bounded_recursive_iterator_impl for
     * associative container types.
     * @see flatten_iterator_layer
     */
    template <typename Iterator>
    class recursive_iterator_impl< Iterator, typename void_t<mapped_iterator<Iterator>>::type > :
    public flatten_iterator_layer< Iterator, recursive_iterator_impl< mapped_iterator<Iterator> > > {
    private:
      using next_layer = recursive_iterator_impl< mapped_iterator<Iterator> >;
      using super = flatten_iterator_layer< Iterator, next_layer >;
    public:
      using super::super;
      recursive_iterator_impl() = default;
      template <typename... Iterators>
      recursive_iterator_impl(in_place_t, Iterators && ...iter) : super(in_place, iter...) {}
    };
  }
  
  /**
   * @class recursive_iterator
   * @breif 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.
   *
   * @param Iterator The iterator type of the top-level collection.
   */
  template <typename Iterator>
  class recursive_iterator : public detail::recursive_iterator_impl< Iterator > {
  private:
    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, 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
   *
   * @param 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 > {
  private:
    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, 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)); }
  };
}

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