cpp-useful-iterators/flatten_iterator.hpp

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

#pragma once

#include "iterator_fwd.hpp"

#include <tuple>

namespace iterator {
namespace detail {  
  template <typename Iterator>
  using flatten_iterator_base = end_aware_iterator< Iterator >;
  
  template <typename Iterator>
  class flatten_iterator_terminal : flatten_iterator_base< Iterator > {
  private:
    using layer = flatten_iterator_base< Iterator >;
    using first_type = typename layer::value_type::first_type;
    using second_type = typename layer::value_type::second_type;
  public:
    using value_type = std::tuple<first_type, second_type>;
    using reference = std::tuple<first_type &, second_type &>;
//    using pointer = typename layer::pointer;
    using difference_type = typename layer::difference_type;
    using iterator_category = typename layer::iterator_category;
  public:
    flatten_iterator_terminal() = default;
    flatten_iterator_terminal(layer v) : layer(v) {}
    
    reference operator*() {
      return layer::operator*();
    }
    
//    pointer operator->() {
//      return layer::operator->();
//    }
    
    bool operator==(flatten_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 flatten_iterator_layer :
  flatten_iterator_base< Iterator >,
  RecursiveIterator_NextLayer {
  private:
    using next_layer = RecursiveIterator_NextLayer;
    using layer = flatten_iterator_base< Iterator >;
    
    using key_type = typename layer::value_type::first_type;
    using cat_value_type = typename next_layer::value_type;
    using cat_reference = typename next_layer::reference;
  public:
    using value_type = decltype(std::tuple_cat(std::make_tuple(std::declval<key_type>()), std::declval<cat_value_type>()));
    using reference = decltype(std::tuple_cat(std::tie(std::declval<key_type>()), std::declval<cat_reference>()));
//    using pointer = typename next_layer::pointer;
    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::tie(layer::operator*().first), next_layer::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_flatten_iterator_impl :
  public flatten_iterator_terminal< Iterator > {
  private:
    using super = flatten_iterator_terminal< Iterator >;
  public:
    using super::super;
  };
  
  template <typename Iterator, std::size_t N, std::size_t Max>
  class bounded_flatten_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_flatten_iterator_impl< mapped_iterator<Iterator>, N+1, Max > > {
  private:
    using next_layer = bounded_flatten_iterator_impl< mapped_iterator<Iterator>, N+1, Max >;
    using super = flatten_iterator_layer< Iterator, next_layer >;
  public:
    using super::super;
  };
  
  template <typename Iterator, typename = void>
  class flatten_iterator_impl : public flatten_iterator_terminal< Iterator > {
  private:
    using super = flatten_iterator_terminal< Iterator >;
  public:
    using super::super;
  };
  
  template <typename Iterator>
  class flatten_iterator_impl< Iterator, typename void_t<mapped_iterator<Iterator>>::type > :
  public flatten_iterator_layer< Iterator, flatten_iterator_impl< mapped_iterator<Iterator> > > {
  private:
    using next_layer = flatten_iterator_impl< mapped_iterator<Iterator> >;
    using super = flatten_iterator_layer< Iterator, next_layer >;
  public:
    using super::super;
  };
}

template <typename Iterator>
class flatten_iterator : detail::flatten_iterator_impl< Iterator > {
private:
  using super = detail::flatten_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;
  
  flatten_iterator & operator++() {
    (void) super::next();
    return *this;
  }
  
  flatten_iterator operator++(int) {
    flatten_iterator tmp{*this};
    (void) super::next();
    return tmp;
  }
  
  using super::operator*;
//  using super::operator->;
  using super::operator==;
  bool operator!=(flatten_iterator const & other) { return !(operator==(other)); }
};

template <typename Iterator, std::size_t N>
class flatten_iterator_n : detail::bounded_flatten_iterator_impl< Iterator, 1, N > {
private:
  using super = detail::bounded_flatten_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;
  
  flatten_iterator_n & operator++() {
    (void) super::next();
    return *this;
  }
  
  flatten_iterator_n operator++(int) {
    flatten_iterator_n tmp{*this};
    (void) super::next();
    return tmp;
  }
  
  using super::operator*;
//  using super::operator->;
  using super::operator==;
  bool operator!=(flatten_iterator_n const & other) { return !(operator==(other)); }
};
}