cpp-useful-iterators/include/iterator/detail/recursive_iterator_traits.hpp

#pragma once

#include <iterator>
#include <string>
#include <tuple>
#include <utility>

#include "../iterator_fwd.hpp"

namespace iterator { namespace detail {
  template <typename Iterator, typename RecursiveIterator_NextLayer>
  class flatten_iterator_layer;
  template <typename Iterator, typename RecursiveIterator_NextLayer>
  class recursive_iterator_layer;

  // Helper struct for dealing with merging output from associative and
  // non-associative containers.
  // TODO: This seems unnecessarily verbose t.b.h.
  struct terminal_layer_tag_t;
  struct continue_layer_tag_t;

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

  // Helpers for condensing type deductions
  template <typename IterType>
  using value_iterator = decltype(std::begin(*std::declval<IterType>()));

  template <typename IterType>
  using mapped_iterator =
      decltype(std::begin(std::declval<IterType>()->second));

  // Type trait to identify value_type ~~ std::pair<K const, V>, which is
  // a safe bet towards 'this is an associative container type'
  template <typename T, typename = void>
  struct is_associative : std::false_type {};
  template <typename T>
  struct is_associative<T, std::enable_if_t<std::is_const<
                               typename T::value_type::first_type>::value>>
      : std::true_type {};

  template <typename T>
  using is_associative_t = std::enable_if_t<is_associative<T>::value>;

  // Type deduction guides for constructing recursive iterators.
  enum class typeclass { TERMINAL, CONTAINER, ASSOCIATIVE_CONTAINER };

  template <typename> struct void_t { using type = void; };

  template <typename T, typename = void> struct typeclass_t {
    static constexpr typeclass const value{typeclass::TERMINAL};
  };

  template <typename T> struct is_string_iterator : std::false_type {};
  template <>
  struct is_string_iterator<std::string::iterator> : std::true_type {};
  template <>
  struct is_string_iterator<std::string::const_iterator> : std::true_type {};

  template <typename T>
  struct typeclass_t<
      T, std::enable_if_t<!is_string_iterator<value_iterator<T>>::value>> {
    static constexpr typeclass const value{typeclass::CONTAINER};
  };

  template <typename T>
  struct typeclass_t<
      T, std::enable_if_t<is_string_iterator<value_iterator<T>>::value>> {
    static constexpr typeclass const value{typeclass::TERMINAL};
  };

  template <typename T>
  struct typeclass_t<T, typename void_t<mapped_iterator<T>>::type> {
    static constexpr typeclass const value{typeclass::ASSOCIATIVE_CONTAINER};
  };

  // Accessor templates for invoking std::get
  template <std::size_t I, typename It, typename = void> struct accessor;

  template <typename It> struct accessor<0, end_aware_iterator<It>> {
    using type = end_aware_iterator<It>;
  };

  template <typename It, typename Rec>
  struct accessor<0, recursive_iterator_layer<It, Rec>> {
    using type = end_aware_iterator<It>;
  };

  template <typename It, typename Rec>
  struct accessor<0, flatten_iterator_layer<It, Rec>> {
    using type = end_aware_iterator<It>;
  };

  template <typename It> struct accessor<0, It> {
    using type = typename accessor<0, typename It::super>::type;
  };

  template <std::size_t I, typename It>
  struct accessor<I, It, typename std::enable_if<I != 0>::type> {
    using type = typename accessor<I, typename It::super>::type;
  };

  template <std::size_t I, typename It, typename Rec>
  struct accessor<I, recursive_iterator_layer<It, Rec>,
                  typename std::enable_if<I != 0>::type> {
    using type = typename accessor<I - 1, Rec>::type;
  };

  template <std::size_t I, typename It, typename Rec>
  struct accessor<I, flatten_iterator_layer<It, Rec>,
                  typename std::enable_if<I != 0>::type> {
    using type = typename accessor<I - 1, Rec>::type;
  };

}}