#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 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) {
  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>>
bool
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";

  return true;
}


/////////////////////////////////////////////////////////////////////////////
// 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<typename T>
struct SequenceTraits<std::vector<T>> {
  using Kind  = std::vector<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;
  }
};


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

  return 0;
}


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