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


// We can define a concept in order to ensure that all SequenceTraits
// have an appropriate interface, if we so desire.
template<typename T>
concept SequenceAccess =
// We can express the existence of published types that are required.
  requires{
    typename T::Position;
    typename T::Value;
    typename T::Kind;
} &&
// We can also express the constraints on the methods that must be available.
  requires(T t, typename T::Position position, typename T::Value value, const typename T::Kind sequence) {
   { T::getFirst(sequence) }          -> std::same_as<std::optional<typename T::Position>>;
   { T::getNext(sequence, position) } -> std::same_as<std::optional<typename T::Position>>;
   { T::getValue(position) }          -> std::same_as<typename T::Value>;
};


/////////////////////////////////////////////////////////////////////////////
// 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.
/////////////////////////////////////////////////////////////////////////////


// Constraining the function using the concept was actually just a matter of
// replacing the `typename` keyword
template<typename SequenceKind, SequenceAccess Traits = SequenceTraits<SequenceKind>>
bool
isIncreasing(const SequenceKind& sequence) {
  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, SequenceAccess Traits = SequenceTraits<SequenceKind>>
void
printSequence(const SequenceKind& sequence) {
  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
/////////////////////////////////////////////////////////////////////////////


// NOTE: We can write this in a few ways. If we write it as
//
//  template<typename T>
//  struct SequenceTraits<std::vector<T>>
//
//  Then the specialization will work only for vectors. by writing it in the form
//  below, it instead works for any templated containers like `vector` or `list`
//  adhering to the sequence APIs used by the STL (push_back, etc).
//

template<template <class...> class C, typename T>
struct SequenceTraits<C<T>> {
  using Kind  = C<T>;
  using Value = T;
  using Position = typename Kind::const_iterator;

  static std::optional<Position>
  getFirst(const Kind& sequence) {
    if (!sequence.empty()) {
      return sequence.begin();
    } else {
      return {};
    }
  }

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


// // You can try this alternative implementation that does not expose the needed types.
// template<template <class...> class C, typename T>
// struct SequenceTraits<C<T>> {
//   using Value = T;
//   using Position = typename C<T>::const_iterator;
// 
//   static std::optional<Position>
//   getFirst(const C<T>& sequence) {
//     if (!sequence.empty()) {
//       return sequence.begin();
//     } else {
//       return {};
//     }
//   }
// 
//   static std::optional<Position>
//   getNext(const C<T>& sequence, Position position) {
//     auto next = ++position;
//     if (next != sequence.end()) {
//       return next;
//     } else {
//       return {};
//     }
//   }
//   
//   static Value
//   getValue(Position position) {
//     return *position;
//   }
// };


struct Hailstone {
  int start = 10;
};


template<>
struct SequenceTraits<Hailstone> {
  using Kind  = Hailstone;
  using Value = int;
  using Position = Value;

  static std::optional<Position>
  getFirst(const Kind& sequence) {
    return sequence.start;
  }

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


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

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

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

    auto next = Original::getNext(sequence, position.second);
    if (!next) {
      return {};
    } else {
      return std::pair{position.first - 1, *next};
    }
  }
  
  static Value
  getValue(Position position) {
    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;
}


// TODO:
// Discuss in class about safety objectives.
// Discuss CRTP, concepts,