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 {  
//  template <typename Iterator>
//  using recursive_iterator_base = end_aware_iterator< Iterator >;
  
  template <typename Iterator, typename = void>
  class recursive_iterator_base : public end_aware_iterator<Iterator> {
  private:
    using super = end_aware_iterator<Iterator>;
  public:
    using super::super;
  };

  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 = typename super::value_type::first_type;
    using second_type = typename super::value_type::second_type;
  public:
    using value_type = std::tuple<first_type, second_type>;
    using reference = std::tuple<first_type &, second_type &>;
  public:
    using super::super;
  };

  template <typename Iterator, typename = void>
  class recursive_iterator_terminal : public recursive_iterator_base< Iterator > {
  private:
    using layer = recursive_iterator_base< Iterator >;
  public:
    recursive_iterator_terminal() = default;
    recursive_iterator_terminal(layer v) : layer(v) {}
    
    typename layer::reference operator*() {
      return layer::operator*();
    }
    
    typename layer::pointer operator->() {
      return layer::operator->();
    }
  protected:
    void next() {
      layer::operator++();
    }
    
    void assign(layer eat) {
      static_cast<layer&>(*this) = eat;
    }
    
    bool done() const { return layer::done(); }
  };
  
  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 >;
  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) : layer(v), next_layer() {
      if ( !v.done() ) {
        next_layer::assign({ std::begin(*v), std::end(*v) });
      }
    }
    
    reference operator*() {
      return next_layer::operator*();
    }
    
    pointer operator->() {
      return next_layer::operator->();
    }
    
    bool operator==(recursive_iterator_layer const & other) const {
      return layer::operator==(other) && next_layer::operator==(other);
    }
  protected:
    void next() {
      layer & self = static_cast<layer&>(*this);
      next_layer::next();
      while ( next_layer::done() && !(++self).done() ) {
        next_layer::assign({ std::begin(*self), std::end(*self) });
      }
    }
    
    void assign(layer eat) {
      static_cast<layer&>(*this) = eat;
    }
    
    bool done() const { return layer::done(); }
  };
  
  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;
  public:
    using value_type = decltype(std::tuple_cat(std::make_tuple(std::declval<key_type>()), std::declval<typename next_layer::value_type>()));
    using reference = decltype(std::tuple_cat(std::tie(std::declval<key_type>()), std::declval<typename next_layer::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) : layer(v), next_layer() {
      if ( !v.done() ) {
        next_layer::assign({ std::begin(v->second), std::end(v->second) });
      }
    }
    
    reference operator*() {
      return std::tuple_cat(std::forward_as_tuple(layer::operator*().first), next_layer::operator*());
    }
    
    pointer operator->();
    //    pointer operator->() {
    //      return next_layer::operator->();
    //    }
    
    bool operator==(flatten_iterator_layer const & other) const {
      return layer::operator==(other) && next_layer::operator==(other);
    }
  protected:
    void next() {
      layer & self = static_cast<layer&>(*this);
      next_layer::next();
      while ( next_layer::done() && !(++self).done() ) {
        next_layer::assign({ std::begin(self->second), std::end(self->second) });
      }
    }
    
    void assign(layer eat) {
      static_cast<layer&>(*this) = eat;
    }
    
    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_terminal< Iterator > {
  private:
    using super = recursive_iterator_terminal< Iterator >;
  public:
    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<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:
    using super::super;
  };
  
  template <typename Iterator, typename = void>
  class recursive_iterator_impl : public recursive_iterator_terminal< Iterator > {
  private:
    using super = recursive_iterator_terminal< Iterator >;
  public:
    using super::super;
  };
  
  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:
    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 !(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 !(operator==(other)); }
};
}