cpp-useful-iterators/recursive_iterator.hpp

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

#pragma once

#include "iterator_fwd.hpp"

namespace iterator {
  namespace detail {
    struct terminal_layer_tag_t;
    struct continue_layer_tag_t;
    
    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;
    protected:
      typename super::reference get() { return super::operator*(); }
    };
    
    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;
    protected:
      reference get() {
        auto & pair = super::operator*();
        return std::tie(pair.first, pair.second);
      }
    };
    
    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);
      }
      
      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*(); }

      void next() {
        layer & self = static_cast<layer&>(*this);
        next_layer::next();
        while ( next_layer::done() && !(++self).done() ) {
          next_layer::assign(make_end_aware_iterator(*self));
        }
      }
      
      void assign(layer v) {
        static_cast<layer&>(*this) = v;
        if (!v.done()) {
          next_layer::assign(make_end_aware_iterator(*v));
        }
      }
      
      bool done() const { return layer::done(); }
    };
    
    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; };
    
    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);
      }
      
      reference operator*() {
        return std::tuple_cat(std::forward_as_tuple(std::get<0>(layer::get())),
                              next_reference(next_layer::get()));
      }
      
      pointer operator->();
      
      bool operator==(flatten_iterator_layer const & other) const {
        return layer::operator==(other) && next_layer::operator==(other);
      }
    protected:
      reference get() { return operator*(); }

      void next() {
        layer & self = static_cast<layer&>(*this);
        next_layer::next();
        while ( next_layer::done() && !(++self).done() ) {
          next_layer::assign(make_end_aware_iterator(self->second));
        }
      }
      
      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(); }
    };
    
    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;
    protected:
      void next() { super::operator++(); }
      void assign(super eat) { static_cast<super&>(*this) = eat; }
    };
    
    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:
      auto operator*() -> decltype(*(next_layer&)(*this)) { return next_layer::operator*(); }
      using super::super;
    };
    
    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;
    protected:
      void next() { super::operator++(); }
      void assign(super eat) { static_cast<super&>(*this) = eat; }
    };
    
    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:
      auto operator*() -> decltype(*(next_layer&)(*this)) { return next_layer::operator*(); }
      using super::super;
    };
    
    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;
    };
    
    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;
    };
  }
  
  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 & 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)); }
  };
  
  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 & 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) };
}