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>
  class recursive_iterator_terminal : public recursive_iterator_base< Iterator > {
  private:
    using layer = recursive_iterator_base< Iterator >;
  public:
    using value_type = typename layer::value_type;
    using reference = typename layer::reference;
    using pointer = typename layer::pointer;
    using difference_type = typename layer::difference_type;
    using iterator_category = typename layer::iterator_category;
  public:
    recursive_iterator_terminal() = default;
    recursive_iterator_terminal(layer v) : layer(v) {}
    
    reference operator*() {
      return layer::operator*();
    }
    
    pointer operator->() {
      return layer::operator->();
    }
    
    bool operator==(recursive_iterator_terminal const & other) const {
      return layer::operator==(other);
    }
  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, 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>
class recursive_iterator : detail::recursive_iterator_impl< Iterator > {
private:
  using super = detail::recursive_iterator_impl< Iterator >;
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 = typename super::iterator_category;
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;
  }
  
  using super::operator*;
  using super::operator->;
  using super::operator==;
  bool operator!=(recursive_iterator const & other) { return !(operator==(other)); }
};

template <typename Iterator, std::size_t N>
class recursive_iterator_n : detail::bounded_recursive_iterator_impl< Iterator, 1, N > {
private:
  using super = detail::bounded_recursive_iterator_impl< Iterator, 1, N >;
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 = typename super::iterator_category;
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;
  }
  
  using super::operator*;
  using super::operator->;
  using super::operator==;
  bool operator!=(recursive_iterator_n const & other) { return !(operator==(other)); }
};
}