#include "kstd/tests/os_panic.hpp"

#include <kstd/ranges>
#include <kstd/vector>

#include <catch2/catch_test_macros.hpp>

#include <array>
#include <cstddef>
#include <ranges>
#include <utility>

SCENARIO("Vector initialization and construction", "[vector]")
{
  GIVEN("An empty context")
  {
    WHEN("constructing by default")
    {
      kstd::vector<int> v;

      THEN("the vector is empty")
      {
        REQUIRE(v.empty());
      }

      THEN("the size and capacity are zero")
      {
        REQUIRE(v.size() == 0);
        REQUIRE(v.capacity() == 0);
      }
    }

    WHEN("constructing with a specific size")
    {
      kstd::vector<int> v(10);

      THEN("the vector is not empty")
      {
        REQUIRE_FALSE(v.empty());
      }

      THEN("the size is and capacity match the specified value")
      {
        REQUIRE(v.size() == 10);
        REQUIRE(v.capacity() == 10);
      }
    }

    WHEN("constructing from an initializer list")
    {
      kstd::vector<int> v = {1, 2, 3, 4, 5};

      THEN("the vector is not empty")
      {
        REQUIRE_FALSE(v.empty());
      }

      THEN("the size is and capacity match the specified value")
      {
        REQUIRE(v.size() == 5);
        REQUIRE(v.capacity() == 5);
      }

      THEN("the elements are correctly initialized")
      {
        REQUIRE(v[0] == 1);
        REQUIRE(v[1] == 2);
        REQUIRE(v[2] == 3);
        REQUIRE(v[3] == 4);
        REQUIRE(v[4] == 5);
      }
    }
  }

  GIVEN("A non-empty range")
  {
    auto range = std::array<int, 3>{1, 2, 3};

    WHEN("constructing from a random-access iterator range")
    {
      auto v = kstd::vector<int>{std::begin(range), std::end(range)};

      THEN("the vector is not empty")
      {
        REQUIRE_FALSE(v.empty());
      }

      THEN("the size and capacity match the range size")
      {
        REQUIRE(v.size() == std::size(range));
        REQUIRE(v.capacity() == std::size(range));
      }

      THEN("the elements are correctly initialized")
      {
        REQUIRE(v[0] == 1);
        REQUIRE(v[1] == 2);
        REQUIRE(v[2] == 3);
      }
    }

    WHEN("constructing from a range")
    {
      auto v = kstd::vector<int>{kstd::from_range, range};

      THEN("the vector is not empty")
      {
        REQUIRE_FALSE(v.empty());
      }

      THEN("the size and capacity match the range size")
      {
        REQUIRE(v.size() == std::ranges::size(range));
        REQUIRE(v.capacity() == std::ranges::size(range));
      }

      THEN("the elements are correctly initialized")
      {
        REQUIRE(v[0] == 1);
        REQUIRE(v[1] == 2);
        REQUIRE(v[2] == 3);
      }
    }
  }

  GIVEN("A populated vector")
  {
    kstd::vector<int> source = {1, 2, 3, 4, 5};

    WHEN("copy constructing a new vector")
    {
      kstd::vector<int> copy(source);

      THEN("the copy matches the original")
      {
        REQUIRE(copy.size() == source.size());
        REQUIRE(copy.capacity() == source.capacity());
        REQUIRE(copy[0] == 1);
        REQUIRE(copy[1] == 2);
        REQUIRE(copy[2] == 3);
        REQUIRE(copy[3] == 4);
        REQUIRE(copy[4] == 5);
      }

      THEN("the original is left unchanged")
      {
        REQUIRE(source.size() == 5);
        REQUIRE(source.capacity() == 5);
        REQUIRE(source[0] == 1);
        REQUIRE(source[1] == 2);
        REQUIRE(source[2] == 3);
        REQUIRE(source[3] == 4);
        REQUIRE(source[4] == 5);
      }
    }

    WHEN("move constructing a new vector")
    {
      kstd::vector<int> moved(std::move(source));

      THEN("The new vector has the original elements")
      {
        REQUIRE(moved.size() == 5);
        REQUIRE(moved.capacity() == 5);
        REQUIRE(moved[0] == 1);
        REQUIRE(moved[1] == 2);
        REQUIRE(moved[2] == 3);
        REQUIRE(moved[3] == 4);
        REQUIRE(moved[4] == 5);
      }

      THEN("The original vector is left in a valid but unspecified state")
      {
        REQUIRE(source.empty());
        REQUIRE(source.size() == 0);
        REQUIRE(source.capacity() == 0);
      }
    }
  }
}

SCENARIO("Vector element access", "[vector]")
{
  GIVEN("A populated vector")
  {
    kstd::vector<int> v = {10, 20, 30};

    WHEN("accessing elements for reading")
    {
      THEN("operator[] and at() return the correct elements")
      {
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
        REQUIRE(v[2] == 30);

        REQUIRE(v.at(0) == 10);
        REQUIRE(v.at(1) == 20);
        REQUIRE(v.at(2) == 30);
      }

      THEN("front() and back() return the first and last elements")
      {
        REQUIRE(v.front() == 10);
        REQUIRE(v.back() == 30);
      }

      THEN("data() return a pointer to the contiguous storage")
      {
        auto ptr = v.data();
        REQUIRE(ptr);
        REQUIRE(ptr[0] == 10);
        REQUIRE(ptr[1] == 20);
        REQUIRE(ptr[2] == 30);
      }

      THEN("accessing out of bounds elements panics")
      {
        REQUIRE_THROWS_AS(v.at(3), kstd::tests::os_panic);
      }
    }

    WHEN("accessing elements for writing")
    {
      v[0] = 100;
      v.at(1) = 200;
      v.back() = 300;

      THEN("the elements are correctly modified")
      {
        REQUIRE(v[0] == 100);
        REQUIRE(v[1] == 200);
        REQUIRE(v[2] == 300);
      }
    }
  }
}

SCENARIO("Vector iterators", "[vector]")
{
  GIVEN("A populated vector")
  {
    kstd::vector<int> v = {1, 2, 3};

    WHEN("using forward iterators")
    {
      THEN("they navigate the elements in the correct forward order")
      {
        auto it = v.begin();
        REQUIRE(it != v.end());
        REQUIRE(*it == 1);

        ++it;
        REQUIRE(it != v.end());
        REQUIRE(*it == 2);

        ++it;
        REQUIRE(it != v.end());
        REQUIRE(*it == 3);

        ++it;
        REQUIRE(it == v.end());
      }

      THEN("const forward iterators provide correct access")
      {
        auto it = v.cbegin();
        REQUIRE(it != v.cend());
        REQUIRE(*it == 1);

        ++it;
        REQUIRE(it != v.cend());
        REQUIRE(*it == 2);

        ++it;
        REQUIRE(it != v.cend());
        REQUIRE(*it == 3);

        ++it;
        REQUIRE(it == v.cend());
      }
    }

    WHEN("using reverse iterators")
    {
      THEN("they navigate the elements in the correct reverse order")
      {
        auto it = v.rbegin();
        REQUIRE(it != v.rend());
        REQUIRE(*it == 3);

        ++it;
        REQUIRE(it != v.rend());
        REQUIRE(*it == 2);

        ++it;
        REQUIRE(it != v.rend());
        REQUIRE(*it == 1);

        ++it;
        REQUIRE(it == v.rend());
      }

      THEN("const reverse iterators provide correct access")
      {
        auto it = v.crbegin();
        REQUIRE(it != v.crend());
        REQUIRE(*it == 3);

        ++it;
        REQUIRE(it != v.crend());
        REQUIRE(*it == 2);

        ++it;
        REQUIRE(it != v.crend());
        REQUIRE(*it == 1);

        ++it;
        REQUIRE(it == v.crend());
      }
    }
  }

  GIVEN("an empty vector")
  {
    kstd::vector<int> v;

    WHEN("getting iterators")
    {
      THEN("begin() equals end() and cbegin() equals cend()")
      {
        REQUIRE(v.begin() == v.end());
        REQUIRE(v.cbegin() == v.cend());
      }

      THEN("rbegin() equals rend() and crbegin() equals crend()")
      {
        REQUIRE(v.rbegin() == v.rend());
        REQUIRE(v.crbegin() == v.crend());
      }
    }
  }
}

SCENARIO("Vector capacity management", "[vector]")
{
  GIVEN("An empty vector")
  {
    kstd::vector<int> v;

    WHEN("reserving space")
    {
      v.reserve(10);

      THEN("the capacity is at least the reserved amount")
      {
        REQUIRE(v.capacity() >= 10);
      }

      THEN("the size is still zero")
      {
        REQUIRE(v.size() == 0);
      }

      THEN("the vector is still empty")
      {
        REQUIRE(v.empty());
      }
    }
  }

  GIVEN("A populated vector with excess capacity")
  {
    kstd::vector<int> v{1, 2, 3};
    v.reserve(10);

    REQUIRE(v.capacity() == 10);

    WHEN("calling shrink_to_fit")
    {
      v.shrink_to_fit();

      THEN("the capacity is reduced to match the size")
      {
        REQUIRE(v.capacity() == 3);
        REQUIRE(v.size() == 3);
      }

      THEN("the elements remain unchanged")
      {
        REQUIRE(v[0] == 1);
        REQUIRE(v[1] == 2);
        REQUIRE(v[2] == 3);
      }
    }
  }
}

SCENARIO("Vector modifiers", "[vector]")
{
  GIVEN("An empty vector")
  {
    kstd::vector<int> v;

    WHEN("push_back is called with a value")
    {
      v.push_back(10);

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.capacity() >= 1);
        REQUIRE(v.back() == 10);
      }
    }

    WHEN("emplace_back is called with constructor arguments")
    {
      v.emplace_back(20);

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.capacity() >= 1);
        REQUIRE(v.back() == 20);
      }
    }
  }

  GIVEN("A populated vector")
  {
    kstd::vector<int> v = {10, 20, 30};
    auto initial_capacity = v.capacity();

    WHEN("push_back is called")
    {
      v.push_back(40);

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v.capacity() >= initial_capacity);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
        REQUIRE(v[2] == 30);
        REQUIRE(v[3] == 40);
      }
    }

    WHEN("emplace_back is called with constructor arguments")
    {
      v.emplace_back(40);

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v.capacity() >= initial_capacity);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
        REQUIRE(v[2] == 30);
        REQUIRE(v[3] == 40);
      }
    }

    WHEN("pop_back is called")
    {
      v.pop_back();

      THEN("the last element is removed and the size decreases")
      {
        REQUIRE(v.size() == 2);
        REQUIRE(v.capacity() == initial_capacity);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
      }
    }

    WHEN("clear is called")
    {
      v.clear();

      THEN("the vector is empty")
      {
        REQUIRE(v.empty());
        REQUIRE(v.size() == 0);
        REQUIRE(v.capacity() == initial_capacity);
      }
    }
  }
}

SCENARIO("Vector comparison", "[vector]")
{
  GIVEN("Two identical vectors")
  {
    kstd::vector<int> v1 = {1, 2, 3};
    kstd::vector<int> v2 = {1, 2, 3};

    WHEN("comparing for equality")
    {
      THEN("the vectors are equal")
      {
        REQUIRE(v1 == v2);
      }

      THEN("the vectors and not not-equal")
      {
        REQUIRE_FALSE(v1 != v2);
      }
    }

    WHEN("comparing using the spaceship operator")
    {
      THEN("the vectors are equivalent")
      {
        REQUIRE((v1 <=> v2) == 0);
        REQUIRE(v1 <= v2);
        REQUIRE(v1 >= v2);
      }
    }
  }

  GIVEN("Two vectors of different sizes")
  {
    kstd::vector<int> v1 = {1, 2, 3};
    kstd::vector<int> v2 = {1, 2, 3, 4};

    WHEN("comparing for equality")
    {
      THEN("the vectors are not equal")
      {
        REQUIRE_FALSE(v1 == v2);
      }

      THEN("the vectors are not-equal")
      {
        REQUIRE(v1 != v2);
      }
    }

    WHEN("comparing for ordering")
    {
      THEN("the shorter vector evaluates as less than the longer vector")
      {
        REQUIRE(v1 < v2);
        REQUIRE(v2 > v1);
      }
    }
  }

  GIVEN("Two vectors of the same size but different elements")
  {
    kstd::vector<int> v1 = {1, 2, 3};
    kstd::vector<int> v2 = {1, 2, 4};

    WHEN("comparing for ordering")
    {
      THEN("they are ordered lexicographically")
      {
        REQUIRE(v1 < v2);
        REQUIRE(v2 > v1);
      }
    }
  }
}

struct non_default_constructible
{
  int value;
  non_default_constructible() = delete;
  explicit non_default_constructible(int v)
      : value{v}
  {}

  bool operator==(non_default_constructible const & other) const noexcept = default;
};

SCENARIO("Vector with non-default-constructible types", "[vector]")
{
  GIVEN("A type without a default constructor")
  {
    WHEN("constructing an empty vector")
    {
      kstd::vector<non_default_constructible> v;

      THEN("the vector is empty")
      {
        REQUIRE(v.empty());
      }
    }

    WHEN("using emplace_back")
    {
      kstd::vector<non_default_constructible> v;
      v.emplace_back(42);

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.back() == non_default_constructible{42});
      }
    }
  }
}

template<typename T>
struct tracking_allocator
{
  using value_type = T;

  int * allocation_count;

  tracking_allocator(int * counter)
      : allocation_count{counter}
  {}

  template<typename U>
  tracking_allocator(tracking_allocator<U> const & other) noexcept
      : allocation_count{other.allocation_count}
  {}

  T * allocate(std::size_t n)
  {
    if (allocation_count)
    {
      (*allocation_count)++;
    }
    return static_cast<T *>(::operator new(n * sizeof(T)));
  }

  void deallocate(T * p, std::size_t n) noexcept
  {
    ::operator delete(p, n * sizeof(T));
  }

  bool operator==(tracking_allocator const & other)
  {
    return allocation_count == other.allocation_count;
  }
};

SCENARIO("Vector with custom allocator", "[vector]")
{
  GIVEN("a tracking allocator acting as the vector's memory manager")
  {
    auto allocations = 0;
    tracking_allocator<int> allocator{&allocations};

    WHEN("a vector uses this allocator to allocate memory")
    {
      kstd::vector<int, tracking_allocator<int>> v{allocator};
      REQUIRE(allocations == 0);

      v.reserve(10);

      THEN("the allocator was used to allocate memory")
      {
        REQUIRE(allocations > 0);
      }
    }
  }
}

struct move_tracker
{
  int value;
  bool was_copied{};
  bool was_moved{};

  move_tracker() = default;
  explicit move_tracker(int v)
      : value{v}
  {}

  move_tracker(move_tracker const & other)
      : value{other.value}
      , was_copied{true}
      , was_moved{false}
  {}

  move_tracker(move_tracker && other) noexcept
      : value{other.value}
      , was_copied{false}
      , was_moved{true}
  {
    other.value = -1;
  }

  move_tracker & operator=(move_tracker const & other)
  {
    value = other.value;
    was_copied = true;
    was_moved = false;
    return *this;
  }

  move_tracker & operator=(move_tracker && other) noexcept
  {
    value = other.value;
    was_moved = true;
    was_copied = false;
    other.value = -1;
    return *this;
  }
};

SCENARIO("Vector modifier move semantics", "[vector]")
{
  GIVEN("An empty vector and a move tracker element")
  {
    kstd::vector<move_tracker> v;
    move_tracker tracker{42};

    WHEN("push_back is called with the move tracker")
    {
      v.push_back(std::move(tracker));

      THEN("the element is added and the size and capacity increase")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.back().was_moved);
        REQUIRE_FALSE(v.back().was_copied);
        REQUIRE(v.back().value == 42);
      }

      THEN("the original tracker is left in a valid but unspecified state")
      {
        REQUIRE(tracker.value == -1);
      }
    }
  }

  GIVEN("An empty vector")
  {
    kstd::vector<move_tracker> v;

    WHEN("emplace_back is called with constructor arguments")
    {
      v.emplace_back(42);

      THEN("the element is constructed directly, without moves or copies")
      {
        REQUIRE(v.size() == 1);
        REQUIRE_FALSE(v.back().was_moved);
        REQUIRE_FALSE(v.back().was_copied);
        REQUIRE(v.back().value == 42);
      }
    }
  }
}