pigweed/pw_containers/inline_deque_test.cc

// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

#include "pw_containers/inline_deque.h"

#include <algorithm>
#include <array>
#include <cstddef>

#include "pw_compilation_testing/negative_compilation.h"
#include "pw_containers/algorithm.h"
#include "pw_containers_private/test_helpers.h"
#include "pw_unit_test/framework.h"

namespace pw::containers {
namespace {

using namespace std::literals::string_view_literals;
using test::CopyOnly;
using test::Counter;
using test::MoveOnly;

TEST(InlineDeque, Construct_Sized) {
  InlineDeque<int, 3> deque;
  EXPECT_TRUE(deque.empty());
  EXPECT_EQ(deque.size(), 0u);
  EXPECT_EQ(deque.max_size(), 3u);
}

TEST(InlineDeque, Construct_GenericSized) {
  InlineDeque<int, 3> sized_deque;
  InlineDeque<int>& deque(sized_deque);
  EXPECT_TRUE(deque.empty());
  EXPECT_EQ(deque.size(), 0u);
  EXPECT_EQ(deque.max_size(), 3u);
}

TEST(InlineDeque, Construct_ConstexprSized) {
  constexpr InlineDeque<int, 3> deque(pw::kConstexpr);
  EXPECT_TRUE(deque.empty());
  EXPECT_EQ(deque.size(), 0u);
  EXPECT_EQ(deque.max_size(), 3u);
}

TEST(InlineDeque, Construct_CopySameCapacity) {
  InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
  const auto& deque_ref = deque;
  InlineDeque<CopyOnly, 4> copied(deque_ref);

  ASSERT_EQ(4u, deque.size());
  EXPECT_EQ(123, deque[3].value);

  ASSERT_EQ(4u, copied.size());
  EXPECT_EQ(123, copied[3].value);
}

TEST(InlineDeque, Construct_MoveSameCapacity) {
  InlineDeque<MoveOnly, 4> deque;
  deque.emplace_back(MoveOnly(1));
  deque.emplace_back(MoveOnly(2));
  deque.emplace_back(MoveOnly(3));
  deque.emplace_back(MoveOnly(4));
  InlineDeque<MoveOnly, 4> moved(std::move(deque));

  // NOLINTNEXTLINE(bugprone-use-after-move)
  EXPECT_EQ(0u, deque.size());

  ASSERT_EQ(4u, moved.size());
  EXPECT_EQ(4, moved[3].value);
}

TEST(InlineDeque, Construct_CopyLargerCapacity) {
  InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
  InlineDeque<CopyOnly, 5> copied(deque);

  ASSERT_EQ(4u, deque.size());
  EXPECT_EQ(123, deque[3].value);

  ASSERT_EQ(4u, copied.size());
  EXPECT_EQ(123, copied[3].value);
}

TEST(InlineDeque, Construct_MoveLargerCapacity) {
  InlineDeque<MoveOnly, 4> deque;
  deque.emplace_back(MoveOnly(1));
  deque.emplace_back(MoveOnly(2));
  deque.emplace_back(MoveOnly(3));
  deque.emplace_back(MoveOnly(4));
  InlineDeque<MoveOnly, 5> moved(std::move(deque));

  // NOLINTNEXTLINE(bugprone-use-after-move)
  EXPECT_EQ(0u, deque.size());

  ASSERT_EQ(4u, moved.size());
  EXPECT_EQ(4, moved[3].value);
}

TEST(InlineDeque, Construct_CopySmallerCapacity) {
  InlineDeque<CopyOnly, 4> deque(3, CopyOnly(123));
  InlineDeque<CopyOnly, 3> copied(deque);

  ASSERT_EQ(3u, deque.size());
  EXPECT_EQ(123, deque[2].value);

  ASSERT_EQ(3u, copied.size());
  EXPECT_EQ(123, copied[2].value);
}

TEST(InlineDeque, Destruct_ZeroLength) {
  Counter::Reset();
  {
    InlineDeque<Counter, 0> deque;
    EXPECT_EQ(deque.size(), 0u);
  }
  EXPECT_EQ(Counter::created, 0);
  EXPECT_EQ(Counter::destroyed, 0);
}

TEST(InlineDeque, Destruct_Empty) {
  Counter::Reset();

  {
    InlineDeque<Counter, 3> deque;
    EXPECT_EQ(deque.size(), 0u);
  }
  EXPECT_EQ(Counter::created, 0);
  EXPECT_EQ(Counter::destroyed, 0);
}

TEST(InlineDeque, Destruct_MultipleEntries) {
  Counter value;
  Counter::Reset();

  {
    InlineDeque<Counter, 128> deque(100, value);
  }

  EXPECT_EQ(Counter::created, 100);
  EXPECT_EQ(Counter::destroyed, 100);
}

TEST(InlineDeque, Assign_InitializerList) {
  InlineDeque<int, 4> deque = {1, 3, 5, 7};

  ASSERT_EQ(4u, deque.size());

  EXPECT_EQ(1, deque[0]);
  EXPECT_EQ(3, deque[1]);
  EXPECT_EQ(5, deque[2]);
  EXPECT_EQ(7, deque[3]);
}

TEST(InlineDeque, Assign_CopySameCapacity) {
  InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
  InlineDeque<CopyOnly, 4> copied = deque;

  ASSERT_EQ(4u, deque.size());
  EXPECT_EQ(123, deque[3].value);

  ASSERT_EQ(4u, copied.size());
  EXPECT_EQ(123, copied[3].value);
}

TEST(InlineDeque, Assign_CopyLargerCapacity) {
  InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
  InlineDeque<CopyOnly, 5> copied = deque;

  ASSERT_EQ(4u, deque.size());
  EXPECT_EQ(123, deque[3].value);

  ASSERT_EQ(4u, copied.size());
  EXPECT_EQ(123, copied[3].value);
}

TEST(InlineDeque, Assign_CopySmallerCapacity) {
  InlineDeque<CopyOnly, 4> deque(3, CopyOnly(123));
  InlineDeque<CopyOnly, 3> copied = deque;

  ASSERT_EQ(3u, deque.size());
  EXPECT_EQ(123, deque[2].value);

  ASSERT_EQ(3u, copied.size());
  EXPECT_EQ(123, copied[2].value);
}

TEST(InlineDeque, Assign_MoveSameCapacity) {
  InlineDeque<MoveOnly, 4> deque;
  deque.emplace_back(MoveOnly(1));
  deque.emplace_back(MoveOnly(2));
  deque.emplace_back(MoveOnly(3));
  deque.emplace_back(MoveOnly(4));
  InlineDeque<MoveOnly, 4> moved = std::move(deque);

  // NOLINTNEXTLINE(bugprone-use-after-move)
  EXPECT_EQ(0u, deque.size());

  ASSERT_EQ(4u, moved.size());
  EXPECT_EQ(4, moved[3].value);
}

TEST(InlineDeque, Assign_MoveLargerCapacity) {
  InlineDeque<MoveOnly, 4> deque;
  deque.emplace_back(MoveOnly(1));
  deque.emplace_back(MoveOnly(2));
  deque.emplace_back(MoveOnly(3));
  deque.emplace_back(MoveOnly(4));
  InlineDeque<MoveOnly, 5> moved = std::move(deque);

  // NOLINTNEXTLINE(bugprone-use-after-move)
  EXPECT_EQ(0u, deque.size());

  ASSERT_EQ(4u, moved.size());
  EXPECT_EQ(4, moved[3].value);
}

TEST(InlineDeque, Assign_MoveSmallerCapacity) {
  InlineDeque<MoveOnly, 4> deque;
  deque.emplace_back(MoveOnly(1));
  deque.emplace_back(MoveOnly(2));
  deque.emplace_back(MoveOnly(3));
  InlineDeque<MoveOnly, 3> moved = std::move(deque);

  // NOLINTNEXTLINE(bugprone-use-after-move)
  EXPECT_EQ(0u, deque.size());

  ASSERT_EQ(3u, moved.size());
  EXPECT_EQ(3, moved[2].value);
}

TEST(InlineDeque, Access_Iterator) {
  InlineDeque<Counter, 2> deque(2);
  for (Counter& item : deque) {
    EXPECT_EQ(item.value, 0);
  }
  for (const Counter& item : deque) {
    EXPECT_EQ(item.value, 0);
  }
}

TEST(InlineDeque, Access_ConstIterator) {
  const InlineDeque<Counter, 2> deque(2);
  for (const Counter& item : deque) {
    EXPECT_EQ(item.value, 0);
  }
}

TEST(InlineDeque, Access_ZeroLength) {
  InlineDeque<Counter, 0> deque;

  EXPECT_EQ(0u, deque.size());
  EXPECT_EQ(0u, deque.max_size());
  EXPECT_TRUE(deque.empty());
  EXPECT_TRUE(deque.full());

  for (Counter& item : deque) {
    (void)item;
    FAIL();
  }
}

TEST(InlineDeque, Access_ContiguousData) {
  // Content = {}, Storage = [x, x]
  InlineDeque<int, 2> deque;

  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_EQ(first.size(), 0u);
    EXPECT_EQ(second.size(), 0u);
  }

  // Content = {1}, Storage = [1, x]
  deque.push_back(1);
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
    EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
  }

  // Content = {1, 2}, Storage = [1, 2]
  deque.push_back(2);
  EXPECT_TRUE(deque.full());
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
    EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
  }

  // Content = {2}, Storage = [x, 2]
  deque.pop_front();
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
    EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
  }

  // Content = {2, 1}, Storage = [1, 2]
  deque.push_back(1);
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
    EXPECT_TRUE(Equal(second, std::array<int, 1>{1}));
  }

  // Content = {1}, Storage = [1, x]
  deque.pop_front();
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
    EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
  }

  // Content = {1, 2}, Storage = [1, 2]
  deque.push_back(2);
  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
    EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
  }
}

TEST(InlineDeque, Access_ConstContiguousData) {
  // Content = {1, 2}, Storage = [1, 2]
  const InlineDeque<int, 2> deque = {1, 2};

  {
    auto [first, second] = deque.contiguous_data();
    EXPECT_EQ(first.size(), 2u);
    EXPECT_EQ(second.size(), 0u);
  }
}

TEST(InlineDeque, Modify_Clear) {
  Counter::Reset();

  InlineDeque<Counter, 100> deque;
  deque.emplace_back();
  deque.emplace_back();
  deque.emplace_back();

  deque.clear();

  EXPECT_EQ(3, Counter::created);
  EXPECT_EQ(3, Counter::destroyed);
}

TEST(InlineDeque, Modify_PushBack_Copy) {
  Counter value(99);
  Counter::Reset();

  {
    InlineDeque<Counter, 10> deque;
    deque.push_back(value);

    ASSERT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 99);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 1);
}

TEST(InlineDeque, Modify_PushBack_Move) {
  Counter::Reset();

  {
    Counter value(99);
    InlineDeque<Counter, 10> deque;
    deque.push_back(std::move(value));

    EXPECT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 99);
    // NOLINTNEXTLINE(bugprone-use-after-move)
    EXPECT_EQ(value.value, 0);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 2);
  EXPECT_EQ(Counter::moved, 1);
}

TEST(InlineDeque, Modify_EmplaceBack) {
  Counter::Reset();

  {
    InlineDeque<Counter, 10> deque;
    deque.emplace_back(314);

    ASSERT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 314);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 1);
}

TEST(InlineDeque, Modify_WrapForwards) {
  Counter::Reset();

  {
    InlineDeque<Counter, 3> deque;
    deque.emplace_back(1);
    deque.emplace_back(2);
    deque.emplace_back(3);

    ASSERT_EQ(deque.size(), 3u);
    EXPECT_EQ(deque[0].value, 1);
    EXPECT_EQ(deque.front().value, 1);
    EXPECT_EQ(deque[1].value, 2);
    EXPECT_EQ(deque[2].value, 3);
    EXPECT_EQ(deque.back().value, 3);

    deque.pop_front();
    deque.emplace_back(4);

    ASSERT_EQ(deque.size(), 3u);
    EXPECT_EQ(deque[0].value, 2);
    EXPECT_EQ(deque.front().value, 2);
    EXPECT_EQ(deque[1].value, 3);
    EXPECT_EQ(deque[2].value, 4);
    EXPECT_EQ(deque.back().value, 4);
  }

  EXPECT_EQ(Counter::created, 4);
  EXPECT_EQ(Counter::destroyed, 4);
}

TEST(InlineDeque, Modify_WrapBackwards) {
  Counter::Reset();

  {
    InlineDeque<Counter, 3> deque;
    deque.emplace_front(1);
    deque.emplace_front(2);
    deque.emplace_front(3);

    ASSERT_EQ(deque.size(), 3u);
    EXPECT_EQ(deque[0].value, 3);
    EXPECT_EQ(deque.front().value, 3);
    EXPECT_EQ(deque[1].value, 2);
    EXPECT_EQ(deque[2].value, 1);
    EXPECT_EQ(deque.back().value, 1);

    deque.pop_back();
    deque.emplace_front(4);

    ASSERT_EQ(deque.size(), 3u);
    EXPECT_EQ(deque[0].value, 4);
    EXPECT_EQ(deque.front().value, 4);
    EXPECT_EQ(deque[1].value, 3);
    EXPECT_EQ(deque[2].value, 2);
    EXPECT_EQ(deque.back().value, 2);
  }

  EXPECT_EQ(Counter::created, 4);
  EXPECT_EQ(Counter::destroyed, 4);
}

TEST(InlineDeque, Modify_PushFront_Copy) {
  Counter value(99);
  Counter::Reset();

  {
    InlineDeque<Counter, 10> deque;
    deque.push_front(value);

    EXPECT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 99);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 1);
}

TEST(InlineDeque, Modify_PushFront_Move) {
  Counter::Reset();

  {
    Counter value(99);
    InlineDeque<Counter, 10> deque;
    deque.push_front(std::move(value));

    EXPECT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 99);
    // NOLINTNEXTLINE(bugprone-use-after-move)
    EXPECT_EQ(value.value, 0);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 2);
  EXPECT_EQ(Counter::moved, 1);
}

TEST(InlineDeque, Modify_EmplaceFront) {
  Counter::Reset();

  {
    InlineDeque<Counter, 10> deque;
    deque.emplace_front(314);

    EXPECT_EQ(deque.size(), 1u);
    EXPECT_EQ(deque.front().value, 314);
  }

  EXPECT_EQ(Counter::created, 1);
  EXPECT_EQ(Counter::destroyed, 1);
}

TEST(InlineDeque, Modify_PopBack) {
  Counter::Reset();

  InlineDeque<Counter, 3> deque;
  deque.emplace_front(1);  // This wraps to the other end.
  deque.emplace_back(2);   // This is the first entry in storage.
  deque.emplace_back(3);
  // Content = {1, 2, 3}, Storage = [2, 3, 1]

  ASSERT_EQ(deque.size(), 3u);
  EXPECT_EQ(deque[0].value, 1);
  EXPECT_EQ(deque[1].value, 2);
  EXPECT_EQ(deque[2].value, 3);

  deque.pop_back();
  // Content = {1, 2}, Storage = [2, x, 1]
  ASSERT_EQ(deque.size(), 2u);
  EXPECT_EQ(deque[0].value, 1);
  EXPECT_EQ(deque[1].value, 2);

  // This wraps around.
  deque.pop_back();
  // Content = {1}, Storage = [x, x, 1]

  ASSERT_EQ(deque.size(), 1u);
  EXPECT_EQ(deque[0].value, 1);

  EXPECT_EQ(Counter::created, 3);
  EXPECT_EQ(Counter::destroyed, 2);
}

TEST(InlineDeque, Modify_PopFront) {
  Counter::Reset();

  InlineDeque<Counter, 3> deque;
  deque.emplace_front(1);  // This wraps to the other end.
  deque.emplace_back(2);   // This is the first entry in storage.
  deque.emplace_back(3);
  // Content = {1, 2, 3}, Storage = [2, 3, 1]

  ASSERT_EQ(deque.size(), 3u);
  EXPECT_EQ(deque[0].value, 1);
  EXPECT_EQ(deque[1].value, 2);
  EXPECT_EQ(deque[2].value, 3);

  // This wraps around
  deque.pop_front();
  // Content = {2, 3}, Storage = [2, 3, x]

  EXPECT_EQ(deque.size(), 2u);
  EXPECT_EQ(deque[0].value, 2);
  EXPECT_EQ(deque[1].value, 3);

  deque.pop_front();
  // Content = {3}, Storage = [x, 3, x]
  ASSERT_EQ(deque.size(), 1u);
  EXPECT_EQ(deque[0].value, 3);

  EXPECT_EQ(Counter::created, 3);
  EXPECT_EQ(Counter::destroyed, 2);
}

TEST(InlineDeque, Modify_Resize_Larger) {
  InlineDeque<CopyOnly, 10> deque(1, CopyOnly(123));
  deque.resize(3, CopyOnly(123));

  EXPECT_EQ(deque.size(), 3u);
  for (auto& i : deque) {
    EXPECT_EQ(i.value, 123);
  }
}

TEST(InlineDeque, Modify_Resize_LargerThanMax) {
  InlineDeque<CopyOnly, 10> deque;
  deque.resize(1000, CopyOnly(123));

  EXPECT_EQ(deque.size(), 10u);
  for (auto& i : deque) {
    EXPECT_EQ(i.value, 123);
  }
}

TEST(InlineDeque, Modify_Resize_Smaller) {
  InlineDeque<CopyOnly, 10> deque(9, CopyOnly(123));
  deque.resize(3, CopyOnly(123));

  EXPECT_EQ(deque.size(), 3u);
  for (auto& i : deque) {
    EXPECT_EQ(i.value, 123);
  }
}

TEST(InlineDeque, Modify_Resize_Zero) {
  InlineDeque<CopyOnly, 10> deque(10, CopyOnly(123));
  deque.resize(0, CopyOnly(123));

  EXPECT_EQ(deque.size(), 0u);
}

TEST(InlineDeque, Generic) {
  InlineDeque<int, 10> deque;
  InlineDeque<int>& generic_deque(deque);
  generic_deque = {1, 2, 3, 4, 5};

  EXPECT_EQ(generic_deque.size(), deque.size());
  EXPECT_EQ(generic_deque.max_size(), deque.max_size());

  unsigned short i = 0;
  for (int value : deque) {
    EXPECT_EQ(value, generic_deque[i]);
    i += 1;
  }

  i = 0;
  for (int value : generic_deque) {
    EXPECT_EQ(deque[i], value);
    i += 1;
  }
}

TEST(InlineDeque, ConstexprMaxSize) {
  InlineDeque<int, 10> deque;
  constexpr size_t kMaxSize = deque.max_size();
  EXPECT_EQ(deque.max_size(), kMaxSize);

  // Ensure the generic sized container does not have a constexpr max_size().
  [[maybe_unused]] InlineDeque<int>& generic_deque(deque);
#if PW_NC_TEST(InlineDeque_GenericMaxSize_NotConstexpr)
  PW_NC_EXPECT_CLANG(
      "kGenericMaxSize.* must be initialized by a constant expression");
  PW_NC_EXPECT_GCC("call to non-'constexpr' function .*InlineDeque.*max_size");
  [[maybe_unused]] constexpr size_t kGenericMaxSize = generic_deque.max_size();
#endif  // PW_NC_TEST
}

TEST(InlineDeque, StdMaxElement) {
  // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
  InlineDeque<int, 4> deque = {1, 2, 3, 4};

  auto max_element_it = std::max_element(deque.begin(), deque.end());
  ASSERT_NE(max_element_it, deque.end());
  EXPECT_EQ(*max_element_it, 4);

  // Content = {2, 3, 4}, Storage = [x, 2, 3, 4]
  deque.pop_front();

  max_element_it = std::max_element(deque.begin(), deque.end());
  ASSERT_NE(max_element_it, deque.end());
  EXPECT_EQ(*max_element_it, 4);

  // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
  deque.push_back(5);
  max_element_it = std::max_element(deque.begin(), deque.end());
  ASSERT_NE(max_element_it, deque.end());
  EXPECT_EQ(*max_element_it, 5);

  // Content = {}, Storage = [x, x, x, x]
  deque.clear();

  max_element_it = std::max_element(deque.begin(), deque.end());
  ASSERT_EQ(max_element_it, deque.end());
}

TEST(InlineDeque, StdMaxElementConst) {
  // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
  InlineDeque<int, 4> deque = {1, 2, 3, 4};

  auto max_element_it = std::max_element(deque.cbegin(), deque.cend());
  ASSERT_NE(max_element_it, deque.cend());
  EXPECT_EQ(*max_element_it, 4);

  // Content = {2, 3, 4}, Storage = [x, 2, 3, 4]
  deque.pop_front();

  max_element_it = std::max_element(deque.cbegin(), deque.cend());
  ASSERT_NE(max_element_it, deque.cend());
  EXPECT_EQ(*max_element_it, 4);

  // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
  deque.push_back(5);
  max_element_it = std::max_element(deque.cbegin(), deque.cend());
  ASSERT_NE(max_element_it, deque.cend());
  EXPECT_EQ(*max_element_it, 5);

  // Content = {}, Storage = [x, x, x, x]
  deque.clear();

  max_element_it = std::max_element(deque.cbegin(), deque.cend());
  ASSERT_EQ(max_element_it, deque.cend());
}

TEST(InlineDeque, OperatorPlus) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < 4; i++) {
    ASSERT_EQ(*(deque.begin() + i), static_cast<int>(i + 1));
    ASSERT_EQ(*(i + deque.begin()), static_cast<int>(i + 1));
  }

  ASSERT_EQ(deque.begin() + deque.size(), deque.end());
}

TEST(InlineDeque, OperatorPlusPlus) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  auto it = deque.begin();

  ASSERT_EQ(*it, 1);
  it++;
  ASSERT_EQ(*it, 2);
  it++;
  ASSERT_EQ(*it, 3);
  it++;
  ASSERT_EQ(*it, 4);
  it++;

  ASSERT_EQ(it, deque.end());
}

TEST(InlineDeque, OperatorPlusEquals) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  auto it = deque.begin();

  ASSERT_EQ(*it, 1);
  it += 1;
  ASSERT_EQ(*it, 2);
  it += 1;
  ASSERT_EQ(*it, 3);
  it += 1;
  ASSERT_EQ(*it, 4);
  it += 1;
  ASSERT_EQ(it, deque.end());

  it = deque.begin();
  ASSERT_EQ(*it, 1);
  it += 2;
  ASSERT_EQ(*it, 3);
  it += 2;
  ASSERT_EQ(it, deque.end());

  it = deque.begin();
  it += deque.size();

  ASSERT_EQ(it, deque.end());
}

TEST(InlineDeque, OpeartorMinus) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 1; i <= 4; i++) {
    ASSERT_EQ(*(deque.end() - i), static_cast<int>(5 - i));
  }

  ASSERT_EQ(deque.end() - deque.size(), deque.begin());
}
TEST(InlineDeque, OperatorMinusMinus) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  auto it = deque.end();

  it--;
  ASSERT_EQ(*it, 4);
  it--;
  ASSERT_EQ(*it, 3);
  it--;
  ASSERT_EQ(*it, 2);
  it--;
  ASSERT_EQ(*it, 1);

  ASSERT_EQ(it, deque.begin());
}

TEST(InlineDeque, OperatorMinusEquals) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  auto it = deque.end();

  it -= 1;
  ASSERT_EQ(*it, 4);
  it -= 1;
  ASSERT_EQ(*it, 3);
  it -= 1;
  ASSERT_EQ(*it, 2);
  it -= 1;
  ASSERT_EQ(*it, 1);

  ASSERT_EQ(it, deque.begin());

  it = deque.end();

  it -= 2;
  ASSERT_EQ(*it, 3);
  it -= 2;
  ASSERT_EQ(*it, 1);

  ASSERT_EQ(it, deque.begin());

  it = deque.end();
  it -= deque.size();

  ASSERT_EQ(it, deque.begin());
}

TEST(InlineDeque, OperatorSquareBracket) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (unsigned short i = 0; i < deque.size(); i++) {
    ASSERT_EQ(deque.begin()[i], static_cast<int>(i + 1));
  }
}

TEST(InlineDeque, OperatorLessThan) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < deque.size(); i++) {
    for (int j = 0; j < i; j++) {
      ASSERT_TRUE((deque.begin() + j) < (deque.begin() + i));
    }

    ASSERT_TRUE((deque.begin() + i) < deque.end());
  }
}

TEST(InlineDeque, OperatorLessThanEqual) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < deque.size(); i++) {
    for (int j = 0; j <= i; j++) {
      ASSERT_TRUE((deque.begin() + j) <= (deque.begin() + i));
    }

    ASSERT_TRUE((deque.begin() + i) <= deque.end());
  }
}

TEST(InlineDeque, OperatorGreater) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < deque.size(); i++) {
    for (int j = i + 1; j < deque.size(); j++) {
      ASSERT_TRUE((deque.begin() + j) > (deque.begin() + i));
    }

    ASSERT_TRUE(deque.end() > (deque.begin() + i));
  }
}

TEST(InlineDeque, OperatorGreaterThanEqual) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < deque.size(); i++) {
    for (int j = i; j < deque.size(); j++) {
      ASSERT_TRUE((deque.begin() + j) >= (deque.begin() + i));
    }

    ASSERT_TRUE(deque.end() >= (deque.begin() + i));
  }
}

TEST(InlineDeque, DereferenceOperator) {
  // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
  InlineDeque<int, 4> deque = {0, 0, 1, 2};
  // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
  deque.pop_front();
  // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
  deque.push_back(3);
  // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
  deque.pop_front();
  // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
  deque.push_back(4);

  for (int i = 0; i < deque.size(); i++) {
    const auto it = deque.begin() + i;
    ASSERT_EQ(*(it.operator->()), static_cast<int>(i + 1));
  }
}

// Test that InlineDeque<T> is trivially destructible when its type is.
static_assert(std::is_trivially_destructible_v<InlineDeque<int, 4>>);

static_assert(std::is_trivially_destructible_v<MoveOnly>);
static_assert(std::is_trivially_destructible_v<InlineDeque<MoveOnly, 1>>);

static_assert(std::is_trivially_destructible_v<CopyOnly>);
static_assert(std::is_trivially_destructible_v<InlineDeque<CopyOnly, 99>>);

static_assert(!std::is_trivially_destructible_v<Counter>);
static_assert(!std::is_trivially_destructible_v<InlineDeque<Counter, 99>>);

// Generic-capacity deques cannot be constructed or destructed.
static_assert(!std::is_constructible_v<InlineDeque<int>>);
static_assert(!std::is_destructible_v<InlineDeque<int>>);

// Tests that InlineDeque<T> does not have any extra padding.
static_assert(sizeof(InlineDeque<uint8_t, 1>) ==
              sizeof(InlineDeque<uint8_t>::size_type) * 4 +
                  std::max(sizeof(InlineDeque<uint8_t>::size_type),
                           sizeof(uint8_t)));
static_assert(sizeof(InlineDeque<uint8_t, 2>) ==
              sizeof(InlineDeque<uint8_t>::size_type) * 4 +
                  2 * sizeof(uint8_t));
static_assert(sizeof(InlineDeque<uint16_t, 1>) ==
              sizeof(InlineDeque<uint16_t>::size_type) * 4 + sizeof(uint16_t));
static_assert(sizeof(InlineDeque<uint32_t, 1>) ==
              sizeof(InlineDeque<uint32_t>::size_type) * 4 + sizeof(uint32_t));
static_assert(sizeof(InlineDeque<uint64_t, 1>) ==
              sizeof(InlineDeque<uint64_t>::size_type) * 4 + sizeof(uint64_t));

// Test that InlineDeque<T> is copy constructible
static_assert(std::is_copy_constructible_v<InlineDeque<int, 4>::iterator>);

// Test that InlineDeque<T> is move constructible
static_assert(std::is_move_constructible_v<InlineDeque<MoveOnly, 4>::iterator>);

// Test that InlineDeque<T> is copy assignable
static_assert(std::is_copy_assignable_v<InlineDeque<int>::iterator>);
static_assert(std::is_copy_assignable_v<InlineDeque<int, 4>::iterator>);

// Test that InlineDeque<T> is move assignable
static_assert(std::is_move_assignable_v<InlineDeque<MoveOnly>>);
static_assert(std::is_move_assignable_v<InlineDeque<MoveOnly, 4>>);

// Test that InlineDeque<T>::iterator can be converted to a const_iterator
static_assert(std::is_convertible<InlineDeque<int>::iterator,
                                  InlineDeque<int>::const_iterator>::value);
static_assert(std::is_convertible<InlineDeque<int, 4>::iterator,
                                  InlineDeque<int, 4>::const_iterator>::value);

// Test that InlineDeque<T>::const_iterator can NOT be converted to a iterator
static_assert(!std::is_convertible<InlineDeque<int>::const_iterator,
                                   InlineDeque<int>::iterator>::value);
static_assert(!std::is_convertible<InlineDeque<int, 4>::const_iterator,
                                   InlineDeque<int, 4>::iterator>::value);

}  // namespace
}  // namespace pw::containers