blob: d8c8d87cae0992ca612ea0b6da7acaa047cc97a9 [file] [log] [blame]
// 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_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