/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "nsTArray.h"
#include "gtest/gtest.h"
#include "mozilla/ArrayUtils.h"
#include "mozilla/RefPtr.h"
#include "nsTHashMap.h"

using namespace mozilla;

namespace TestTArray {

struct Copyable {
  Copyable() : mDestructionCounter(nullptr) {}

  ~Copyable() {
    if (mDestructionCounter) {
      (*mDestructionCounter)++;
    }
  }

  Copyable(const Copyable&) = default;
  Copyable& operator=(const Copyable&) = default;

  uint32_t* mDestructionCounter;
};

struct Movable {
  Movable() : mDestructionCounter(nullptr) {}

  ~Movable() {
    if (mDestructionCounter) {
      (*mDestructionCounter)++;
    }
  }

  Movable(Movable&& aOther) : mDestructionCounter(aOther.mDestructionCounter) {
    aOther.mDestructionCounter = nullptr;
  }

  uint32_t* mDestructionCounter;
};

}  // namespace TestTArray

template <>
struct nsTArray_RelocationStrategy<TestTArray::Copyable> {
  using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Copyable>;
};

template <>
struct nsTArray_RelocationStrategy<TestTArray::Movable> {
  using Type = nsTArray_RelocateUsingMoveConstructor<TestTArray::Movable>;
};

namespace TestTArray {

constexpr int dummyArrayData[] = {4, 1, 2, 8};

static const nsTArray<int>& DummyArray() {
  static nsTArray<int> sArray;
  if (sArray.IsEmpty()) {
    sArray.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
  }
  return sArray;
}

// This returns an invalid nsTArray with a huge length in order to test that
// fallible operations actually fail.
#ifdef DEBUG
static const nsTArray<int>& FakeHugeArray() {
  static nsTArray<int> sArray;
  if (sArray.IsEmpty()) {
    sArray.AppendElement();
    ((nsTArrayHeader*)sArray.DebugGetHeader())->mLength = UINT32_MAX;
  }
  return sArray;
}
#endif

TEST(TArray, int_AppendElements_PlainArray)
{
  nsTArray<int> array;

  int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);

  ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData));
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
}

TEST(TArray, int_AppendElements_PlainArray_Fallible)
{
  nsTArray<int> array;

  int* ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData),
                                  fallible);
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);

  ptr = array.AppendElements(dummyArrayData, ArrayLength(dummyArrayData),
                             fallible);
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
}

TEST(TArray, int_AppendElements_TArray_Copy)
{
  nsTArray<int> array;

  const nsTArray<int> temp(DummyArray().Clone());
  int* ptr = array.AppendElements(temp);
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_FALSE(temp.IsEmpty());

  ptr = array.AppendElements(temp);
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_FALSE(temp.IsEmpty());
}

TEST(TArray, int_AppendElements_TArray_Copy_Fallible)
{
  nsTArray<int> array;

  const nsTArray<int> temp(DummyArray().Clone());
  int* ptr = array.AppendElements(temp, fallible);
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_FALSE(temp.IsEmpty());

  ptr = array.AppendElements(temp, fallible);
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_FALSE(temp.IsEmpty());
}

TEST(TArray, int_AppendElements_TArray_Rvalue)
{
  nsTArray<int> array;

  nsTArray<int> temp(DummyArray().Clone());
  int* ptr = array.AppendElements(std::move(temp));
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_TRUE(temp.IsEmpty());

  temp = DummyArray().Clone();
  ptr = array.AppendElements(std::move(temp));
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_TRUE(temp.IsEmpty());
}

TEST(TArray, int_AppendElements_TArray_Rvalue_Fallible)
{
  nsTArray<int> array;

  nsTArray<int> temp(DummyArray().Clone());
  int* ptr = array.AppendElements(std::move(temp), fallible);
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_TRUE(temp.IsEmpty());

  temp = DummyArray().Clone();
  ptr = array.AppendElements(std::move(temp), fallible);
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_TRUE(temp.IsEmpty());
}

TEST(TArray, int_AppendElements_FallibleArray_Rvalue)
{
  nsTArray<int> array;

  FallibleTArray<int> temp;
  ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
  int* ptr = array.AppendElements(std::move(temp));
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_TRUE(temp.IsEmpty());

  ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
  ptr = array.AppendElements(std::move(temp));
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_TRUE(temp.IsEmpty());
}

TEST(TArray, int_AppendElements_FallibleArray_Rvalue_Fallible)
{
  nsTArray<int> array;

  FallibleTArray<int> temp;
  ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
  int* ptr = array.AppendElements(std::move(temp), fallible);
  ASSERT_EQ(&array[0], ptr);
  ASSERT_EQ(DummyArray(), array);
  ASSERT_TRUE(temp.IsEmpty());

  ASSERT_TRUE(temp.AppendElements(DummyArray(), fallible));
  ptr = array.AppendElements(std::move(temp), fallible);
  ASSERT_EQ(&array[DummyArray().Length()], ptr);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
  ASSERT_TRUE(temp.IsEmpty());
}

TEST(TArray, AppendElementsSpan)
{
  nsTArray<int> array;

  nsTArray<int> temp(DummyArray().Clone());
  Span<int> span = temp;
  array.AppendElements(span);
  ASSERT_EQ(DummyArray(), array);

  Span<const int> constSpan = temp;
  array.AppendElements(constSpan);
  nsTArray<int> expected;
  expected.AppendElements(DummyArray());
  expected.AppendElements(DummyArray());
  ASSERT_EQ(expected, array);
}

TEST(TArray, int_AppendElement_NoElementArg)
{
  nsTArray<int> array;
  array.AppendElement();

  ASSERT_EQ(1u, array.Length());
}

TEST(TArray, int_AppendElement_NoElementArg_Fallible)
{
  nsTArray<int> array;
  ASSERT_NE(nullptr, array.AppendElement(fallible));

  ASSERT_EQ(1u, array.Length());
}

TEST(TArray, int_AppendElement_NoElementArg_Address)
{
  nsTArray<int> array;
  *array.AppendElement() = 42;

  ASSERT_EQ(1u, array.Length());
  ASSERT_EQ(42, array[0]);
}

TEST(TArray, int_AppendElement_NoElementArg_Fallible_Address)
{
  nsTArray<int> array;
  *array.AppendElement(fallible) = 42;

  ASSERT_EQ(1u, array.Length());
  ASSERT_EQ(42, array[0]);
}

TEST(TArray, int_AppendElement_ElementArg)
{
  nsTArray<int> array;
  array.AppendElement(42);

  ASSERT_EQ(1u, array.Length());
  ASSERT_EQ(42, array[0]);
}

TEST(TArray, int_AppendElement_ElementArg_Fallible)
{
  nsTArray<int> array;
  ASSERT_NE(nullptr, array.AppendElement(42, fallible));

  ASSERT_EQ(1u, array.Length());
  ASSERT_EQ(42, array[0]);
}

constexpr size_t dummyMovableArrayLength = 4;
uint32_t dummyMovableArrayDestructorCounter;

static nsTArray<Movable> DummyMovableArray() {
  nsTArray<Movable> res;
  res.SetLength(dummyMovableArrayLength);
  for (size_t i = 0; i < dummyMovableArrayLength; ++i) {
    res[i].mDestructionCounter = &dummyMovableArrayDestructorCounter;
  }
  return res;
}

TEST(TArray, Movable_AppendElements_TArray_Rvalue)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;

    nsTArray<Movable> temp(DummyMovableArray());
    Movable* ptr = array.AppendElements(std::move(temp));
    ASSERT_EQ(&array[0], ptr);
    ASSERT_TRUE(temp.IsEmpty());

    temp = DummyMovableArray();
    ptr = array.AppendElements(std::move(temp));
    ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
    ASSERT_TRUE(temp.IsEmpty());
  }
  ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElements_TArray_Rvalue_Fallible)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;

    nsTArray<Movable> temp(DummyMovableArray());
    Movable* ptr = array.AppendElements(std::move(temp), fallible);
    ASSERT_EQ(&array[0], ptr);
    ASSERT_TRUE(temp.IsEmpty());

    temp = DummyMovableArray();
    ptr = array.AppendElements(std::move(temp), fallible);
    ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
    ASSERT_TRUE(temp.IsEmpty());
  }
  ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;

    FallibleTArray<Movable> temp(DummyMovableArray());
    Movable* ptr = array.AppendElements(std::move(temp));
    ASSERT_EQ(&array[0], ptr);
    ASSERT_TRUE(temp.IsEmpty());

    temp = DummyMovableArray();
    ptr = array.AppendElements(std::move(temp));
    ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
    ASSERT_TRUE(temp.IsEmpty());
  }
  ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElements_FallibleArray_Rvalue_Fallible)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;

    FallibleTArray<Movable> temp(DummyMovableArray());
    Movable* ptr = array.AppendElements(std::move(temp), fallible);
    ASSERT_EQ(&array[0], ptr);
    ASSERT_TRUE(temp.IsEmpty());

    temp = DummyMovableArray();
    ptr = array.AppendElements(std::move(temp), fallible);
    ASSERT_EQ(&array[dummyMovableArrayLength], ptr);
    ASSERT_TRUE(temp.IsEmpty());
  }
  ASSERT_EQ(2 * dummyMovableArrayLength, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElement_NoElementArg)
{
  nsTArray<Movable> array;
  array.AppendElement();

  ASSERT_EQ(1u, array.Length());
}

TEST(TArray, Movable_AppendElement_NoElementArg_Fallible)
{
  nsTArray<Movable> array;
  ASSERT_NE(nullptr, array.AppendElement(fallible));

  ASSERT_EQ(1u, array.Length());
}

TEST(TArray, Movable_AppendElement_NoElementArg_Address)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;
    array.AppendElement()->mDestructionCounter =
        &dummyMovableArrayDestructorCounter;

    ASSERT_EQ(1u, array.Length());
  }
  ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElement_NoElementArg_Fallible_Address)
{
  dummyMovableArrayDestructorCounter = 0;
  {
    nsTArray<Movable> array;
    array.AppendElement(fallible)->mDestructionCounter =
        &dummyMovableArrayDestructorCounter;

    ASSERT_EQ(1u, array.Length());
    ASSERT_EQ(&dummyMovableArrayDestructorCounter,
              array[0].mDestructionCounter);
  }
  ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElement_ElementArg)
{
  dummyMovableArrayDestructorCounter = 0;
  Movable movable;
  movable.mDestructionCounter = &dummyMovableArrayDestructorCounter;
  {
    nsTArray<Movable> array;
    array.AppendElement(std::move(movable));

    ASSERT_EQ(1u, array.Length());
    ASSERT_EQ(&dummyMovableArrayDestructorCounter,
              array[0].mDestructionCounter);
  }
  ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
}

TEST(TArray, Movable_AppendElement_ElementArg_Fallible)
{
  dummyMovableArrayDestructorCounter = 0;
  Movable movable;
  movable.mDestructionCounter = &dummyMovableArrayDestructorCounter;
  {
    nsTArray<Movable> array;
    ASSERT_NE(nullptr, array.AppendElement(std::move(movable), fallible));

    ASSERT_EQ(1u, array.Length());
    ASSERT_EQ(&dummyMovableArrayDestructorCounter,
              array[0].mDestructionCounter);
  }
  ASSERT_EQ(1u, dummyMovableArrayDestructorCounter);
}

TEST(TArray, int_Assign)
{
  nsTArray<int> array;
  array.Assign(DummyArray());
  ASSERT_EQ(DummyArray(), array);

  ASSERT_TRUE(array.Assign(DummyArray(), fallible));
  ASSERT_EQ(DummyArray(), array);

#ifdef DEBUG
  ASSERT_FALSE(array.Assign(FakeHugeArray(), fallible));
#endif

  nsTArray<int> array2;
  array2.Assign(std::move(array));
  ASSERT_TRUE(array.IsEmpty());
  ASSERT_EQ(DummyArray(), array2);
}

TEST(TArray, int_Assign_FromEmpty_ToNonEmpty)
{
  nsTArray<int> array;
  array.AppendElement(42);

  const nsTArray<int> empty;
  array.Assign(empty);

  ASSERT_TRUE(array.IsEmpty());
}

TEST(TArray, int_Assign_FromEmpty_ToNonEmpty_Fallible)
{
  nsTArray<int> array;
  array.AppendElement(42);

  const nsTArray<int> empty;
  ASSERT_TRUE(array.Assign(empty, fallible));

  ASSERT_TRUE(array.IsEmpty());
}

TEST(TArray, int_AssignmentOperatorSelfAssignment)
{
  CopyableTArray<int> array;
  array = DummyArray();

  array = *&array;
  ASSERT_EQ(DummyArray(), array);

#if defined(__clang__)
#  pragma clang diagnostic push
#  pragma clang diagnostic ignored "-Wself-move"
#endif
  array = std::move(array);  // self-move
  ASSERT_EQ(DummyArray(), array);
#if defined(__clang__)
#  pragma clang diagnostic pop
#endif
}

TEST(TArray, Movable_CopyOverlappingForwards)
{
  const size_t rangeLength = 8;
  const size_t initialLength = 2 * rangeLength;
  uint32_t destructionCounters[initialLength];
  nsTArray<Movable> array;
  array.AppendElements(initialLength);

  for (uint32_t i = 0; i < initialLength; ++i) {
    destructionCounters[i] = 0;
  }
  for (uint32_t i = 0; i < initialLength; ++i) {
    array[i].mDestructionCounter = &destructionCounters[i];
  }

  const size_t removedLength = rangeLength / 2;
  array.RemoveElementsAt(0, removedLength);

  for (uint32_t i = 0; i < removedLength; ++i) {
    ASSERT_EQ(destructionCounters[i], 1u);
  }
  for (uint32_t i = removedLength; i < initialLength; ++i) {
    ASSERT_EQ(destructionCounters[i], 0u);
  }
}

// The code to copy overlapping regions had a bug in that it wouldn't correctly
// destroy all over the source elements being copied.
TEST(TArray, Copyable_CopyOverlappingBackwards)
{
  const size_t rangeLength = 8;
  const size_t initialLength = 2 * rangeLength;
  uint32_t destructionCounters[initialLength];
  nsTArray<Copyable> array;
  array.SetCapacity(3 * rangeLength);
  array.AppendElements(initialLength);
  // To tickle the bug, we need to copy a source region:
  //
  //   ..XXXXX..
  //
  // such that it overlaps the destination region:
  //
  //   ....XXXXX
  //
  // so we are forced to copy back-to-front to ensure correct behavior.
  // The easiest way to do that is to call InsertElementsAt, which will force
  // the desired kind of shift.
  for (uint32_t i = 0; i < initialLength; ++i) {
    destructionCounters[i] = 0;
  }
  for (uint32_t i = 0; i < initialLength; ++i) {
    array[i].mDestructionCounter = &destructionCounters[i];
  }

  array.InsertElementsAt(0, rangeLength);

  for (uint32_t i = 0; i < initialLength; ++i) {
    ASSERT_EQ(destructionCounters[i], 1u);
  }
}

namespace {

class E {
 public:
  E() : mA(-1), mB(-2) { constructCount++; }
  E(int a, int b) : mA(a), mB(b) { constructCount++; }
  E(E&& aRhs) : mA(aRhs.mA), mB(aRhs.mB) {
    aRhs.mA = 0;
    aRhs.mB = 0;
    moveCount++;
  }

  E& operator=(E&& aRhs) {
    mA = aRhs.mA;
    aRhs.mA = 0;
    mB = aRhs.mB;
    aRhs.mB = 0;
    moveCount++;
    return *this;
  }

  int a() const { return mA; }
  int b() const { return mB; }

  E(const E&) = delete;
  E& operator=(const E&) = delete;

  static size_t constructCount;
  static size_t moveCount;

 private:
  int mA;
  int mB;
};

size_t E::constructCount = 0;
size_t E::moveCount = 0;

}  // namespace

TEST(TArray, Emplace)
{
  nsTArray<E> array;
  array.SetCapacity(20);

  ASSERT_EQ(array.Length(), 0u);

  for (int i = 0; i < 10; i++) {
    E s(i, i * i);
    array.AppendElement(std::move(s));
  }

  ASSERT_EQ(array.Length(), 10u);
  ASSERT_EQ(E::constructCount, 10u);
  ASSERT_EQ(E::moveCount, 10u);

  for (int i = 10; i < 20; i++) {
    array.EmplaceBack(i, i * i);
  }

  ASSERT_EQ(array.Length(), 20u);
  ASSERT_EQ(E::constructCount, 20u);
  ASSERT_EQ(E::moveCount, 10u);

  for (int i = 0; i < 20; i++) {
    ASSERT_EQ(array[i].a(), i);
    ASSERT_EQ(array[i].b(), i * i);
  }

  array.EmplaceBack();

  ASSERT_EQ(array.Length(), 21u);
  ASSERT_EQ(E::constructCount, 21u);
  ASSERT_EQ(E::moveCount, 10u);

  ASSERT_EQ(array[20].a(), -1);
  ASSERT_EQ(array[20].b(), -2);
}

TEST(TArray, UnorderedRemoveElements)
{
  // When removing an element from the end of the array, it can be removed in
  // place, by destroying it and decrementing the length.
  //
  // [ 1, 2, 3 ] => [ 1, 2 ]
  //         ^
  {
    nsTArray<int> array{1, 2, 3};
    array.UnorderedRemoveElementAt(2);

    nsTArray<int> goal{1, 2};
    ASSERT_EQ(array, goal);
  }

  // When removing any other single element, it is removed by swapping it with
  // the last element, and then decrementing the length as before.
  //
  // [ 1, 2, 3, 4, 5, 6 ]  => [ 1, 6, 3, 4, 5 ]
  //      ^
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6};
    array.UnorderedRemoveElementAt(1);

    nsTArray<int> goal{1, 6, 3, 4, 5};
    ASSERT_EQ(array, goal);
  }

  // This method also supports efficiently removing a range of elements. If they
  // are at the end, then they can all be removed like in the one element case.
  //
  // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 2 ]
  //         ^--------^
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6};
    array.UnorderedRemoveElementsAt(2, 4);

    nsTArray<int> goal{1, 2};
    ASSERT_EQ(array, goal);
  }

  // If more elements are removed than exist after the removed section, the
  // remaining elements will be shifted down like in a normal removal.
  //
  // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 2, 7, 8 ]
  //         ^--------^
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8};
    array.UnorderedRemoveElementsAt(2, 4);

    nsTArray<int> goal{1, 2, 7, 8};
    ASSERT_EQ(array, goal);
  }

  // And if fewer elements are removed than exist after the removed section,
  // elements will be moved from the end of the array to fill the vacated space.
  //
  // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 7, 8, 4, 5, 6 ]
  //      ^--^
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6, 7, 8};
    array.UnorderedRemoveElementsAt(1, 2);

    nsTArray<int> goal{1, 7, 8, 4, 5, 6};
    ASSERT_EQ(array, goal);
  }

  // We should do the right thing if we drain the entire array.
  {
    nsTArray<int> array{1, 2, 3, 4, 5};
    array.UnorderedRemoveElementsAt(0, 5);

    nsTArray<int> goal{};
    ASSERT_EQ(array, goal);
  }

  {
    nsTArray<int> array{1};
    array.UnorderedRemoveElementAt(0);

    nsTArray<int> goal{};
    ASSERT_EQ(array, goal);
  }

  // We should do the right thing if we remove the same number of elements that
  // we have remaining.
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6};
    array.UnorderedRemoveElementsAt(2, 2);

    nsTArray<int> goal{1, 2, 5, 6};
    ASSERT_EQ(array, goal);
  }

  {
    nsTArray<int> array{1, 2, 3};
    array.UnorderedRemoveElementAt(1);

    nsTArray<int> goal{1, 3};
    ASSERT_EQ(array, goal);
  }

  // We should be able to remove elements from the front without issue.
  {
    nsTArray<int> array{1, 2, 3, 4, 5, 6};
    array.UnorderedRemoveElementsAt(0, 2);

    nsTArray<int> goal{5, 6, 3, 4};
    ASSERT_EQ(array, goal);
  }

  {
    nsTArray<int> array{1, 2, 3, 4};
    array.UnorderedRemoveElementAt(0);

    nsTArray<int> goal{4, 2, 3};
    ASSERT_EQ(array, goal);
  }
}

TEST(TArray, RemoveFromEnd)
{
  {
    nsTArray<int> array{1, 2, 3, 4};
    ASSERT_EQ(array.PopLastElement(), 4);
    array.RemoveLastElement();
    ASSERT_EQ(array.PopLastElement(), 2);
    array.RemoveLastElement();
    ASSERT_TRUE(array.IsEmpty());
  }
}

TEST(TArray, ConvertIteratorToConstIterator)
{
  nsTArray<int> array{1, 2, 3, 4};

  nsTArray<int>::const_iterator it = array.begin();
  ASSERT_EQ(array.cbegin(), it);
}

TEST(TArray, RemoveElementAt_ByIterator)
{
  nsTArray<int> array{1, 2, 3, 4};
  const auto it = std::find(array.begin(), array.end(), 3);
  const auto itAfter = array.RemoveElementAt(it);

  // Based on the implementation of the iterator, we could compare it and
  // itAfter, but we should not rely on such implementation details.

  ASSERT_EQ(2, std::distance(array.cbegin(), itAfter));
  const nsTArray<int> expected{1, 2, 4};
  ASSERT_EQ(expected, array);
}

TEST(TArray, RemoveElementsRange_ByIterator)
{
  nsTArray<int> array{1, 2, 3, 4};
  const auto it = std::find(array.begin(), array.end(), 3);
  const auto itAfter = array.RemoveElementsRange(it, array.end());

  // Based on the implementation of the iterator, we could compare it and
  // itAfter, but we should not rely on such implementation details.

  ASSERT_EQ(2, std::distance(array.cbegin(), itAfter));
  const nsTArray<int> expected{1, 2};
  ASSERT_EQ(expected, array);
}

TEST(TArray, RemoveLastElements_None)
{
  const nsTArray<int> original{1, 2, 3, 4};
  nsTArray<int> array = original.Clone();
  array.RemoveLastElements(0);

  ASSERT_EQ(original, array);
}

TEST(TArray, RemoveLastElements_Empty_None)
{
  nsTArray<int> array;
  array.RemoveLastElements(0);

  ASSERT_EQ(0u, array.Length());
}

TEST(TArray, RemoveLastElements_All)
{
  nsTArray<int> array{1, 2, 3, 4};
  array.RemoveLastElements(4);

  ASSERT_EQ(0u, array.Length());
}

TEST(TArray, RemoveLastElements_One)
{
  nsTArray<int> array{1, 2, 3, 4};
  array.RemoveLastElements(1);

  ASSERT_EQ((nsTArray<int>{1, 2, 3}), array);
}

static_assert(std::is_copy_assignable<decltype(MakeBackInserter(
                  std::declval<nsTArray<int>&>()))>::value,
              "output iteraror must be copy-assignable");
static_assert(std::is_copy_constructible<decltype(MakeBackInserter(
                  std::declval<nsTArray<int>&>()))>::value,
              "output iterator must be copy-constructible");

TEST(TArray, MakeBackInserter)
{
  const std::vector<int> src{1, 2, 3, 4};
  nsTArray<int> dst;

  std::copy(src.begin(), src.end(), MakeBackInserter(dst));

  const nsTArray<int> expected{1, 2, 3, 4};
  ASSERT_EQ(expected, dst);
}

TEST(TArray, MakeBackInserter_Move)
{
  uint32_t destructionCounter = 0;

  {
    std::vector<Movable> src(1);
    src[0].mDestructionCounter = &destructionCounter;

    nsTArray<Movable> dst;

    std::copy(std::make_move_iterator(src.begin()),
              std::make_move_iterator(src.end()), MakeBackInserter(dst));

    ASSERT_EQ(1u, dst.Length());
    ASSERT_EQ(0u, destructionCounter);
  }

  ASSERT_EQ(1u, destructionCounter);
}

TEST(TArray, ConvertToSpan)
{
  nsTArray<int> arr = {1, 2, 3, 4, 5};

  // from const
  {
    const auto& constArrRef = arr;

    auto span = Span{constArrRef};
    static_assert(std::is_same_v<decltype(span), Span<const int>>);
  }

  // from non-const
  {
    auto span = Span{arr};
    static_assert(std::is_same_v<decltype(span), Span<int>>);
  }
}

// This should compile:
struct RefCounted;

class Foo {
  ~Foo();  // Intentionally out of line

  nsTArray<RefPtr<RefCounted>> mArray;

  const RefCounted* GetFirst() const { return mArray.SafeElementAt(0); }
};

TEST(TArray, StableSort)
{
  const nsTArray<std::pair<int, int>> expected = {
      std::pair(1, 9), std::pair(1, 8), std::pair(1, 7), std::pair(2, 0),
      std::pair(3, 0)};
  nsTArray<std::pair<int, int>> array = {std::pair(1, 9), std::pair(2, 0),
                                         std::pair(1, 8), std::pair(3, 0),
                                         std::pair(1, 7)};

  array.StableSort([](std::pair<int, int> left, std::pair<int, int> right) {
    return left.first - right.first;
  });

  EXPECT_EQ(expected, array);
}

TEST(TArray, ToArray)
{
  const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  nsTArray<int> keys = ToArray(src);
  keys.Sort();

  EXPECT_EQ((nsTArray<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
}

// Test this to make sure this properly uses ADL.
TEST(TArray, ToArray_HashMap)
{
  nsTHashMap<uint32_t, uint64_t> src;

  for (uint32_t i = 0; i < 10; ++i) {
    src.InsertOrUpdate(i, i);
  }

  nsTArray<uint32_t> keys = ToArray(src.Keys());
  keys.Sort();

  EXPECT_EQ((nsTArray<uint32_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
}

TEST(TArray, ToTArray)
{
  const auto src = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  auto keys = ToTArray<AutoTArray<uint64_t, 10>>(src);
  keys.Sort();

  static_assert(std::is_same_v<decltype(keys), AutoTArray<uint64_t, 10>>);

  EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
}

TEST(TArray, RemoveElementsBy)
{
  // Removing elements returns the correct number of removed elements.
  {
    nsTArray<int> array{8, 1, 1, 3, 3, 5, 2, 3};
    auto removed = array.RemoveElementsBy([](int i) { return i == 3; });
    EXPECT_EQ(removed, 3u);

    nsTArray<int> goal{8, 1, 1, 5, 2};
    EXPECT_EQ(array, goal);
  }

  // The check is called in order.
  {
    int index = 0;
    nsTArray<int> array{0, 1, 2, 3, 4, 5};
    auto removed = array.RemoveElementsBy([&](int i) {
      EXPECT_EQ(index, i);
      index++;
      return i == 3;
    });
    EXPECT_EQ(removed, 1u);

    nsTArray<int> goal{0, 1, 2, 4, 5};
    EXPECT_EQ(array, goal);
  }

  // Removing nothing works
  {
    nsTArray<int> array{0, 1, 2, 3, 4};
    auto removed = array.RemoveElementsBy([](int) { return false; });
    EXPECT_EQ(removed, 0u);

    nsTArray<int> goal{0, 1, 2, 3, 4};
    EXPECT_EQ(array, goal);
  }

  // Removing everything works
  {
    nsTArray<int> array{0, 1, 2, 3, 4};
    auto removed = array.RemoveElementsBy([](int) { return true; });
    EXPECT_EQ(removed, 5u);

    nsTArray<int> goal{};
    EXPECT_EQ(array, goal);
  }
}

}  // namespace TestTArray