#include <iostream>
#include <list>
#include <optional>
#include <string>
#include <vector>


template <typename SequenceKind>
struct SequenceTraits {
  // By ensuring that this is nonsense for GridKind, we know that this
  // version of the template can never apply, and a specialization
  // must be used.
  using Unresolved = typename SequenceKind::UnspecializedTraitError;
  // must publish
  //   types
  //     the kind itself for convenience
  //     position type
  //     value type
  //   behaviors
  //     get first
  //     get next
  //     get value from position
};


// NOTE: We *could* use inheritance and override checking to ensure that
// appropriate methods and types are exposed. This essentially uses CRTP
// to hoist appropriate information from the derived implementations of
// the trait, but it is a bit of an awkward use of inheritance.
// 
// Notice that as written below, it uses the CRTP to ensure compile time
// resolution of the underlying types. This is also a bit awkward. Ideally,
// the compile time polymorphism features of a language would allow us to
// express a required interface without needing to resort to inheritance.
//
// There is a substantial amount of boilerplate using this approach to
// ensure API consistency. Demonstrating this approach is not the same as
// advocating for it.
// 
template <typename TraitName,
          typename SequenceKind, typename ValueKind, typename PositionKind>
struct SequenceTraitConstraints {
public:
  using Kind = SequenceKind;
  using Value = ValueKind;
  using Position = PositionKind;
  
  std::optional<Position>
  getFirst(const Kind& sequence) {
    return getTraits().getFirstImpl(sequence);
  }

  std::optional<Position>
  getNext(const Kind& sequence, Position position) {
    return getTraits().getNextImpl(sequence, position);
  }
  
  Value
  getValue(Position position) {
    return getTraits().getValueImpl(position);
  }

private:
  TraitName&
  getTraits() {
    return *static_cast<TraitName*>(this);
  }
  
  virtual std::optional<Position> getFirstImpl(const Kind& sequence) = 0;
  virtual std::optional<Position> getNextImpl(const Kind& sequence, Position position) = 0;
  virtual Value getValueImpl(Position position) = 0;
};


/////////////////////////////////////////////////////////////////////////////
// We can define behaviors that are independent of the specific structures
// in question but that make use of information about them. This is done in
// part through specialization of the trait information for the types of interest.
/////////////////////////////////////////////////////////////////////////////


template<typename SequenceKind, typename Traits = SequenceTraits<SequenceKind>>
bool
isIncreasing(const SequenceKind& sequence) {
  Traits traits;
  using Position = typename Traits::Position;

  std::optional<Position> previous = std::nullopt;
  std::optional<Position> next     = traits.getFirst(sequence);

  while (next) {
    if (previous && traits.getValue(*next) <= traits.getValue(*previous)) {
      return false;
    }

    previous = next;
    next = traits.getNext(sequence, *next);
  }

  return true;
}


template<typename SequenceKind, typename Traits = SequenceTraits<SequenceKind>>
void
printSequence(const SequenceKind& sequence) {
  Traits traits;
  using Position = typename Traits::Position;

  std::optional<Position> next = traits.getFirst(sequence);

  while (next) {
    std::cout << traits.getValue(*next) << " ";
    next = traits.getNext(sequence, *next);
  }
  std::cout << "\n";
}


/////////////////////////////////////////////////////////////////////////////
// In order to make these work, we need to define the types that we care about
// along with extra trait information to glue the trait driven code to the type
/////////////////////////////////////////////////////////////////////////////



template<template <class...> class C, typename T>
struct SequenceTraits<C<T>> final
   : public SequenceTraitConstraints<SequenceTraits<C<T>>, C<T>, T, typename C<T>::const_iterator>  {

  // Redefining these type aliases is required due to some of the
  // rules on how names are inherited from templated base classes.
  // This comes from something known as "two-phase lookup" in C++.
  using Position = typename SequenceTraits<C<T>>::Position;
  using Value = typename SequenceTraits<C<T>>::Value;
  using Kind = typename SequenceTraits<C<T>>::Kind;
     
  std::optional<Position>
  getFirstImpl(const Kind& sequence) override {
    if (!sequence.empty()) {
      return sequence.begin();
    } else {
      return {};
    }
  }

  std::optional<Position>
  getNextImpl(const Kind& sequence, Position position) override {
    auto next = ++position;
    if (next != sequence.end()) {
      return next;
    } else {
      return {};
    }
  }
  
  Value
  getValueImpl(Position position) override {
    return *position;
  }
};


struct Hailstone {
  int start = 10;
};


template<>
struct SequenceTraits<Hailstone> final
    : public SequenceTraitConstraints<SequenceTraits<Hailstone>, Hailstone, int, int> {

  using Position = typename SequenceTraits<Hailstone>::Position;
  using Value = typename SequenceTraits<Hailstone>::Value;
  using Kind = typename SequenceTraits<Hailstone>::Kind;
     
  std::optional<Position>
  getFirstImpl(const Kind& sequence) override {
    return sequence.start;
  }

  std::optional<Position>
  getNextImpl(const Kind& sequence, Position position) override {
    if (position == 1) {
      return {};
    } else if (position % 2 == 0) {
      return position / 2;
    } else {
      return 3 * position + 1;
    }
  }
  
  Value
  getValueImpl(Position position) override {
    return position;
  }
};


struct BoundedHailstone final
    : public SequenceTraitConstraints<BoundedHailstone,
                                      Hailstone,
                                      int,
                                      std::pair<int, typename SequenceTraits<Hailstone>::Position>> {
  using Original = SequenceTraits<Hailstone>;
  using Position = typename BoundedHailstone::Position;
  using Value = typename BoundedHailstone::Value;
  using Kind = typename BoundedHailstone::Kind;
 
  constexpr static  int BOUND = 10;

  std::optional<Position>
  getFirstImpl(const Kind& sequence) override {
    Original traits;
    return std::pair{BOUND, *traits.getFirst(sequence)};
  }

  std::optional<Position>
  getNextImpl(const Kind& sequence, Position position) override {
    if (position.first == 0) {
      return {};
    }

    Original traits;
    auto next = traits.getNext(sequence, position.second);
    if (!next) {
      return {};
    } else {
      return std::pair{position.first - 1, *next};
    }
  }
  
  Value
  getValueImpl(Position position) override {
    return position.second;
  }
};


/////////////////////////////////////////////////////////////////////////////
// Once we have done so, *using* the APIs actually becomes clear, maintainable,
// and very expressive. There is definitely a trade off, though. This accumulates
// one form of complexity in order to reduce another.
/////////////////////////////////////////////////////////////////////////////


int
main() {
  using namespace std::string_literals;
  std::vector fibs = { 0, 1, 1, 2, 3, 5, 8, 13 };
  std::cout << "vector<int> fibonacci " << isIncreasing(fibs) << "\n";

  std::vector odds = { 1, 3, 5, 7, 9, 11, 13 };
  std::cout << "vector<int> odds      " << isIncreasing(odds) << "\n";

  std::vector<int> empty = { };
  std::cout << "vector<int> empty     " << isIncreasing(empty) << "\n";

  std::vector justOne = { "hello"s };
  std::cout << "vector<string> empty  " << isIncreasing(justOne) << "\n";

  Hailstone hail7{7};
  std::cout << "Hailstones 7 " << isIncreasing(hail7) << "\n";
  
  printSequence(fibs);
  printSequence(hail7);
  printSequence<Hailstone,BoundedHailstone>(hail7);
  
  
  std::list listodds = { 1, 3, 5, 7, 9, 11, 13 };
  std::cout << "list<int> odds      " << isIncreasing(listodds) << "\n";
  printSequence(listodds);

  return 0;
}