#include "kstd/tests/os_panic.hpp"

#include <kstd/ranges>
#include <kstd/tests/test_types.hpp>
#include <kstd/vector>

#include <catch2/catch_test_macros.hpp>

#include <array>
#include <iterator>
#include <ranges>
#include <utility>

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

      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")
    {
      auto v = kstd::vector<int>(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")
    {
      auto v = kstd::vector<int>{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")
  {
    auto source = kstd::vector<int>{1, 2, 3, 4, 5};

    WHEN("copy constructing a new vector")
    {
      auto copy = kstd::vector<int>(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")
    {
      auto moved = kstd::vector<int>(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")
  {
    auto v = kstd::vector<int>{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")
  {
    auto v = kstd::vector<int>{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")
  {
    auto v = kstd::vector<int>{};

    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")
  {
    auto v = kstd::vector<int>{};

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

    WHEN("reserving space less than or equal to current capacity")
    {
      v.reserve(10);
      auto const current_capacity = v.capacity();
      v.reserve(5);

      THEN("the capacity remains unchanged")
      {
        REQUIRE(v.capacity() == current_capacity);
      }
    }

    WHEN("reserving space greater than max_size")
    {
      THEN("a panic is triggered")
      {
        REQUIRE_THROWS_AS(v.reserve(v.max_size() + 1), kstd::tests::os_panic);
      }
    }
  }

  GIVEN("A populated vector with excess capacity")
  {
    auto v = kstd::vector<int>{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")
  {
    auto v = kstd::vector<int>{};

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

    WHEN("elements are added while capacity is sufficient")
    {
      v.reserve(10);
      auto const capacity = v.capacity();

      v.push_back(10);
      v.emplace_back(20);

      THEN("the elements are added without reallocation")
      {
        REQUIRE(v.size() == 2);
        REQUIRE(v.capacity() == capacity);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
      }
    }

    WHEN("inserting an element")
    {
      auto it = v.insert(v.cbegin(), 42);

      THEN("the size and capacity increase and the element is inserted")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.capacity() >= 1);
        REQUIRE(v[0] == 42);
        REQUIRE(it == v.begin());
      }
    }

    WHEN("inserting an lvalue element")
    {
      auto const value = 42;
      auto it = v.insert(v.cbegin(), value);

      THEN("the size and capacity increase and the element is inserted")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.capacity() >= 1);
        REQUIRE(v[0] == 42);
        REQUIRE(it == v.begin());
      }
    }
  }

  GIVEN("A populated vector")
  {
    auto v = kstd::vector<int>{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("push_back is called with a reference to an internal element")
    {
      v.shrink_to_fit();
      auto const original_value = v[0];

      v.push_back(v[0]);

      THEN("reallocation handles the internal reference safely without dangling")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == original_value);
        REQUIRE(v.back() == original_value);
      }
    }

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

    WHEN("inserting at the beginning")
    {
      auto it = v.insert(v.cbegin(), 5);

      THEN("the element is inserted at the front")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 5);
        REQUIRE(v[1] == 10);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin());
      }
    }

    WHEN("inserting in the middle")
    {
      auto it = v.insert(v.cbegin() + 1, 15);

      THEN("the element is inserted in the middle")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 15);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("inserting at the end")
    {
      auto it = v.insert(v.cend(), 40);

      THEN("the element is inserted at the back")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
        REQUIRE(v[2] == 30);
        REQUIRE(v[3] == 40);
        REQUIRE(it == v.begin() + 3);
      }
    }

    WHEN("inserting an lvalue at the end")
    {
      auto const value = 40;
      auto it = v.insert(v.cend(), value);

      THEN("the element is inserted at the back")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 20);
        REQUIRE(v[2] == 30);
        REQUIRE(v[3] == 40);
        REQUIRE(it == v.begin() + 3);
      }
    }

    WHEN("inserting when capacity is sufficient")
    {
      v.reserve(10);
      auto const capacity = v.capacity();

      auto it = v.insert(v.cbegin() + 1, 15);

      THEN("the element is added without reallocation")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v.capacity() == capacity);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 15);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("inserting a reference to an existing element with reallocation")
    {
      v.shrink_to_fit();
      REQUIRE(v.capacity() == v.size());
      auto it = v.insert(v.cbegin() + 1, v[2]);

      THEN("the element is correctly copied and inserted")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 30);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("inserting a reference to an existing element without reallocation")
    {
      v.reserve(10);
      REQUIRE(v.capacity() > v.size());
      auto it = v.insert(v.cbegin() + 1, v[2]);

      THEN("the element is correctly copied and inserted")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 30);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("inserting an rvalue reference to an existing element with reallocation")
    {
      v.shrink_to_fit();
      REQUIRE(v.capacity() == v.size());
      auto it = v.insert(v.cbegin() + 1, std::move(v[2]));

      THEN("the element is correctly moved and inserted")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 30);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("inserting an rvalue reference to an existing element without reallocation")
    {
      v.reserve(10);
      REQUIRE(v.capacity() > v.size());
      auto it = v.insert(v.cbegin() + 1, std::move(v[2]));

      THEN("the element is correctly moved and inserted")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 30);
        REQUIRE(v[2] == 20);
        REQUIRE(v[3] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("erasing the first element")
    {
      auto it = v.erase(v.cbegin());

      THEN("the first element is removed and the size decreases")
      {
        REQUIRE(v.size() == 2);
        REQUIRE(v[0] == 20);
        REQUIRE(v[1] == 30);
        REQUIRE(it == v.begin());
      }
    }

    WHEN("erasing a middle element")
    {
      auto it = v.erase(v.cbegin() + 1);

      THEN("the middle element is removed and the size decreases")
      {
        REQUIRE(v.size() == 2);
        REQUIRE(v[0] == 10);
        REQUIRE(v[1] == 30);
        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("erasing the last element")
    {
      auto it = v.erase(v.cend() - 1);

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

    WHEN("erasing the end() iterator")
    {
      THEN("a panic is triggered")
      {
        REQUIRE_THROWS_AS(v.erase(v.end()), kstd::tests::os_panic);
      }
    }
  }
}

SCENARIO("Vector comparison", "[vector]")
{
  GIVEN("Two identical vectors")
  {
    auto v1 = kstd::vector<int>{1, 2, 3};
    auto v2 = kstd::vector<int>{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")
  {
    auto v1 = kstd::vector<int>{1, 2, 3};
    auto v2 = kstd::vector<int>{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")
  {
    auto v1 = kstd::vector<int>{1, 2, 3};
    auto v2 = kstd::vector<int>{1, 2, 4};

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

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

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

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

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

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

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

      v.reserve(10);

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

SCENARIO("Vector modifier move semantics", "[vector]")
{
  GIVEN("An empty vector and a move tracker element")
  {
    auto v = kstd::vector<kstd::tests::move_tracker>{};
    auto tracker = kstd::tests::move_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")
  {
    auto v = kstd::vector<kstd::tests::move_tracker>{};

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

  GIVEN("A populated vector of move trackers")
  {
    auto v = kstd::vector<kstd::tests::move_tracker>{};
    v.reserve(10);
    v.emplace_back(10);
    v.emplace_back(20);
    v.emplace_back(30);

    WHEN("inserting an element in the middle with sufficient capacity")
    {
      auto const tracker = kstd::tests::move_tracker{15};
      v.insert(v.cbegin() + 1, tracker);

      THEN("the shifted elements are move-assigned and the new element is copy-assigned")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0].value == 10);
        REQUIRE_FALSE(v[0].was_moved);
        REQUIRE(v[1].value == 15);
        REQUIRE(v[1].was_copied);
        REQUIRE_FALSE(v[1].was_moved);
        REQUIRE(v[2].value == 20);
        REQUIRE(v[2].was_moved);
        REQUIRE(v[3].value == 30);
        REQUIRE(v[3].was_moved);
      }
    }

    WHEN("inserting an rvalue element in the middle with sufficient capacity")
    {
      auto tracker = kstd::tests::move_tracker{15};
      v.insert(v.cbegin() + 1, std::move(tracker));

      THEN("the shifted elements are move-assigned and the new element is move-assigned")
      {
        REQUIRE(v.size() == 4);
        REQUIRE(v[0].value == 10);
        REQUIRE_FALSE(v[0].was_moved);
        REQUIRE(v[1].value == 15);
        REQUIRE_FALSE(v[1].was_copied);
        REQUIRE(v[1].was_moved);
        REQUIRE(v[2].value == 20);
        REQUIRE(v[2].was_moved);
        REQUIRE(v[3].value == 30);
        REQUIRE(v[3].was_moved);
      }
    }

    WHEN("erasing an element in the middle")
    {
      for (auto & elem : v)
      {
        elem.was_copied = false;
        elem.was_moved = false;
      }

      auto it = v.erase(v.cbegin() + 1);

      THEN("the subsequent elements are move-assigned leftwards")
      {
        REQUIRE(v.size() == 2);

        REQUIRE(v[0].value == 10);
        REQUIRE_FALSE(v[0].was_moved);
        REQUIRE_FALSE(v[0].was_copied);

        REQUIRE(v[1].value == 30);
        REQUIRE(v[1].was_moved);
        REQUIRE_FALSE(v[1].was_copied);

        REQUIRE(it == v.begin() + 1);
      }
    }

    WHEN("erasing the last element")
    {
      for (auto & elem : v)
      {
        elem.was_copied = false;
        elem.was_moved = false;
      }

      auto it = v.erase(v.cend() - 1);

      THEN("no elements are moved, just the last element destroyed")
      {
        REQUIRE(v.size() == 2);

        REQUIRE(v[0].value == 10);
        REQUIRE_FALSE(v[0].was_moved);
        REQUIRE_FALSE(v[0].was_copied);

        REQUIRE(v[1].value == 20);
        REQUIRE_FALSE(v[1].was_moved);
        REQUIRE_FALSE(v[1].was_copied);

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

SCENARIO("Vector advanced construction", "[vector]")
{
  GIVEN("A count and a default value")
  {
    WHEN("constructing with count and default argument")
    {
      auto const count = 5uz;
      auto const value = 42;
      auto v = kstd::vector<int>(count, value);

      THEN("the vector is initialized with count copies of value")
      {
        REQUIRE(v.size() == 5);
        REQUIRE(v.capacity() == 5);
        REQUIRE(v.front() == 42);
        REQUIRE(v.back() == 42);
      }
    }
  }

  GIVEN("A pure input iterator range")
  {
    WHEN("constructing from input iterators")
    {
      auto const arr = std::array<int, 3>{1, 2, 3};
      auto const first = kstd::tests::test_input_iterator{arr.data()};
      auto const last = kstd::tests::test_input_iterator{arr.data() + arr.size()};

      auto v = kstd::vector<int>(first, last);

      THEN("the vector is generated dynamically and initialized correctly")
      {
        REQUIRE(v.size() == 3);
        REQUIRE(v[0] == 1);
        REQUIRE(v[2] == 3);
      }
    }
  }

  GIVEN("A tracking allocator and a source vector")
  {
    auto allocs = 0;
    auto allocator = kstd::tests::tracking_allocator<int>{&allocs};
    auto source = kstd::vector<int, kstd::tests::tracking_allocator<int>>{allocator};
    source.push_back(1);
    source.push_back(2);
    source.push_back(3);

    allocs = 0;

    WHEN("copy constructing with an allocator")
    {
      auto copy = kstd::vector<int, kstd::tests::tracking_allocator<int>>(source, allocator);

      THEN("the copy succeeds and the allocator is used")
      {
        REQUIRE(copy.size() == 3);
        REQUIRE(allocs > 0);
        REQUIRE(copy[0] == 1);
        REQUIRE(copy[2] == 3);
      }
    }

    WHEN("move constructing with an identically comparing allocator")
    {
      auto moved = kstd::vector<int, kstd::tests::tracking_allocator<int>>(std::move(source), allocator);

      THEN("the move succeeds and no new allocations are made (memory is stolen)")
      {
        REQUIRE(moved.size() == 3);
        REQUIRE(allocs == 0);
        REQUIRE(moved[0] == 1);
        REQUIRE(moved[2] == 3);
      }
    }

    WHEN("move constructing with a non-equal allocator")
    {
      auto allocs2 = 0;
      auto allocator2 = kstd::tests::tracking_allocator<int>{&allocs2};

      auto moved = kstd::vector<int, kstd::tests::tracking_allocator<int>>(std::move(source), allocator2);

      THEN("the move allocates new memory and moves elements")
      {
        REQUIRE(allocs2 > 0);
        REQUIRE(moved.size() == 3);
        REQUIRE(source.empty());
      }
    }
  }
}

SCENARIO("Vector assignment operators", "[vector]")
{
  GIVEN("A source vector and an empty target vector")
  {
    auto source = kstd::vector<int>{1, 2, 3};
    auto target = kstd::vector<int>{};

    WHEN("copy assigning")
    {
      target = source;

      THEN("the target matches the source")
      {
        REQUIRE(target.size() == 3);
        REQUIRE(target[0] == 1);
        REQUIRE(target[2] == 3);
        REQUIRE(source.size() == 3);
      }
    }

    WHEN("move assigning")
    {
      target = std::move(source);

      THEN("the target assumes the source's data")
      {
        REQUIRE(target.size() == 3);
        REQUIRE(target[0] == 1);
        REQUIRE(target[2] == 3);
        REQUIRE(source.empty());
      }
    }
  }

  GIVEN("Vectors with propagating copy allocator")
  {
    auto allocs1 = 0;
    auto allocs2 = 0;
    auto alloc1 = kstd::tests::propagating_allocator<int>{&allocs1};
    auto alloc2 = kstd::tests::propagating_allocator<int>{&allocs2};

    auto v1 = kstd::vector<int, kstd::tests::propagating_allocator<int>>{alloc1};
    v1.push_back(1);
    v1.push_back(2);
    auto v2 = kstd::vector<int, kstd::tests::propagating_allocator<int>>{alloc2};

    WHEN("copy assigning")
    {
      v2 = v1;
      THEN("the allocator propagates")
      {
        REQUIRE(v2.get_allocator() == v1.get_allocator());
      }
    }
  }

  GIVEN("Vectors for copy assignment overlap")
  {
    auto v1 = kstd::vector<int>{1, 2, 3};
    auto v2 = kstd::vector<int>{4, 5};
    v2.reserve(10);

    WHEN("copy assigning a larger vector to a smaller one with enough capacity")
    {
      v2 = v1;
      THEN("elements are copied and size is updated")
      {
        REQUIRE(v2.size() == 3);
        REQUIRE(v2.capacity() >= 10);
        REQUIRE(v2[2] == 3);
      }
    }

    auto v3 = kstd::vector<int>{1, 2, 3, 4};
    v3.reserve(10);
    WHEN("copy assigning a smaller vector to a larger one")
    {
      v3 = v1;
      THEN("excess elements are destroyed")
      {
        REQUIRE(v3.size() == 3);
        REQUIRE(v3[0] == 1);
      }
    }
  }

  GIVEN("Vectors with the same tracking allocator")
  {
    auto allocs = 0;
    auto alloc = kstd::tests::tracking_allocator<int>{&allocs};
    auto v1 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc};
    v1.push_back(1);
    auto v2 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc};

    WHEN("move assigning")
    {
      v2 = std::move(v1);
      THEN("memory is stolen without allocation")
      {
        REQUIRE(v2.size() == 1);
        REQUIRE(allocs == 1);
      }
    }
  }

  GIVEN("Vectors with different non-propagating tracking allocators")
  {
    auto allocs1 = 0;
    auto allocs2 = 0;
    auto alloc1 = kstd::tests::tracking_allocator<int>{&allocs1};
    auto alloc2 = kstd::tests::tracking_allocator<int>{&allocs2};

    auto v1 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc1};
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);

    auto v2 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc2};
    v2.push_back(4);
    v2.push_back(5);

    WHEN("move assigning a larger vector to a smaller one without enough capacity")
    {
      v2.shrink_to_fit();
      v2 = std::move(v1);
      THEN("memory is reallocated and elements are moved")
      {
        REQUIRE(v2.size() == 3);
        REQUIRE(allocs2 > 2);
      }
    }

    auto v3 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc2};
    v3.reserve(10);
    v3.push_back(4);
    v3.push_back(5);
    WHEN("move assigning a larger vector to a smaller one with enough capacity")
    {
      v3 = std::move(v1);
      THEN("elements are move-assigned over overlap and move-constructed over remainder")
      {
        REQUIRE(v3.size() == 3);
      }
    }

    auto v4 = kstd::vector<int, kstd::tests::tracking_allocator<int>>{alloc2};
    v4.reserve(10);
    v4.push_back(4);
    v4.push_back(5);
    v4.push_back(6);
    v4.push_back(7);
    WHEN("move assigning a smaller vector to a larger one with enough capacity")
    {
      v4 = std::move(v1);
      THEN("overlap is moved and excess is destroyed")
      {
        REQUIRE(v4.size() == 3);
      }
    }
  }
}

SCENARIO("Vector self-assignment operators", "[vector]")
{
  GIVEN("A populated vector")
  {
    auto v = kstd::vector<int>{1, 2, 3};
    auto const initial_capacity = v.capacity();
    auto const * initial_data = v.data();

    WHEN("copy assigning to itself")
    {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wself-assign-overloaded"
      v = v;
#pragma GCC diagnostic pop

      THEN("the vector remains unchanged")
      {
        REQUIRE(v.size() == 3);
        REQUIRE(v.capacity() == initial_capacity);
        REQUIRE(v.data() == initial_data);
        REQUIRE(v[0] == 1);
        REQUIRE(v[2] == 3);
      }
    }

    WHEN("move assigning to itself")
    {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wself-move"
      v = std::move(v);
#pragma GCC diagnostic pop

      THEN("the vector remains unchanged")
      {
        REQUIRE(v.size() == 3);
        REQUIRE(v.capacity() == initial_capacity);
        REQUIRE(v.data() == initial_data);
        REQUIRE(v[0] == 1);
        REQUIRE(v[2] == 3);
      }
    }
  }
}

SCENARIO("Vector const accessors and copy insertion", "[vector]")
{
  GIVEN("A const populated vector")
  {
    auto const v = kstd::vector<int>{10, 20, 30};

    WHEN("calling const accessors")
    {
      THEN("elements are read correctly as const references")
      {
        REQUIRE(v.front() == 10);
        REQUIRE(v.back() == 30);
        REQUIRE(v[1] == 20);
        REQUIRE(v.at(1) == 20);
      }
    }
  }

  GIVEN("An empty vector and a const lvalue tracker")
  {
    auto v = kstd::vector<kstd::tests::move_tracker>{};
    auto const tracker = kstd::tests::move_tracker{42};

    WHEN("push_back is called with the const lvalue")
    {
      v.push_back(tracker);

      THEN("the element is gracefully copy-constructed")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.back().value == 42);
        REQUIRE(v.back().was_copied);
        REQUIRE_FALSE(v.back().was_moved);
      }
    }

    WHEN("push_back is called with a const lvalue when capacity is sufficient")
    {
      v.reserve(10);
      auto const current_capacity = v.capacity();
      v.push_back(tracker);

      THEN("the element is copy-constructed without reallocation")
      {
        REQUIRE(v.size() == 1);
        REQUIRE(v.capacity() == current_capacity);
        REQUIRE(v.back().value == 42);
        REQUIRE(v.back().was_copied);
        REQUIRE_FALSE(v.back().was_moved);
      }
    }
  }
}