blob: d3aa07a1c5682e698d0942e98d0b0e67910b21f7 [file] [log] [blame]
// Copyright 2022 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.
//
// These tests were forked from
// https://cs.opensource.google/abseil/abseil-cpp/+/main:absl/algorithm/algorithm_test.cc;drc=38b704384cd2f17590b3922b97744be0b43622c9
// However they were modified to work with containers available in Pigweed
// without dynamic allocations, i.e. no std::vector, std::map, std::list, etc.
#include "pw_containers/algorithm.h"
#include <algorithm>
#include <iterator>
#include "pw_containers/flat_map.h"
#include "pw_containers/intrusive_list.h"
#include "pw_containers/vector.h"
#include "pw_span/span.h"
#include "pw_unit_test/framework.h"
namespace {
class TestItem : public pw::IntrusiveList<TestItem>::Item {
public:
TestItem() : number_(0) {}
TestItem(int number) : number_(number) {}
// Add equality comparison to ensure comparisons are done by identity rather
// than equality for the remove function.
bool operator==(const TestItem& other) const {
return number_ == other.number_;
}
private:
int number_;
};
// Most of these tests just check that the code compiles, not that it
// does the right thing. That's fine since the functions just forward
// to the STL implementation.
class NonMutatingTest : public testing::Test {
protected:
std::array<int, 3> span_array_ = {1, 2, 3};
pw::span<int> span_{NonMutatingTest::span_array_};
pw::Vector<int, 3> vector_ = {1, 2, 3};
int array_[3] = {1, 2, 3};
};
struct AccumulateCalls {
void operator()(int value) { calls.push_back(value); }
pw::Vector<int, 10> calls;
};
bool Predicate(int value) { return value < 3; }
bool BinPredicate(int v1, int v2) { return v1 < v2; }
bool Equals(int v1, int v2) { return v1 == v2; }
} // namespace
TEST_F(NonMutatingTest, AllOf) {
const pw::Vector<int>& v = vector_;
EXPECT_FALSE(pw::containers::AllOf(v, [](int x) { return x > 1; }));
EXPECT_TRUE(pw::containers::AllOf(v, [](int x) { return x > 0; }));
}
TEST_F(NonMutatingTest, AnyOf) {
const pw::Vector<int>& v = vector_;
EXPECT_TRUE(pw::containers::AnyOf(v, [](int x) { return x > 2; }));
EXPECT_FALSE(pw::containers::AnyOf(v, [](int x) { return x > 5; }));
}
TEST_F(NonMutatingTest, NoneOf) {
const pw::Vector<int>& v = vector_;
EXPECT_FALSE(pw::containers::NoneOf(v, [](int x) { return x > 2; }));
EXPECT_TRUE(pw::containers::NoneOf(v, [](int x) { return x > 5; }));
}
TEST_F(NonMutatingTest, ForEach) {
AccumulateCalls c = pw::containers::ForEach(span_, AccumulateCalls());
std::sort(c.calls.begin(), c.calls.end());
EXPECT_EQ(vector_, c.calls);
}
TEST_F(NonMutatingTest, FindReturnsCorrectType) {
auto it = pw::containers::Find(span_, 3);
EXPECT_EQ(3, *it);
pw::containers::Find(vector_, 3);
}
TEST_F(NonMutatingTest, FindIf) { pw::containers::FindIf(span_, Predicate); }
TEST_F(NonMutatingTest, FindIfNot) {
pw::containers::FindIfNot(span_, Predicate);
}
TEST_F(NonMutatingTest, FindEnd) {
pw::containers::FindEnd(array_, vector_);
pw::containers::FindEnd(vector_, array_);
}
TEST_F(NonMutatingTest, FindEndWithPredicate) {
pw::containers::FindEnd(array_, vector_, BinPredicate);
pw::containers::FindEnd(vector_, array_, BinPredicate);
}
TEST_F(NonMutatingTest, FindFirstOf) {
pw::containers::FindFirstOf(span_, array_);
pw::containers::FindFirstOf(array_, span_);
}
TEST_F(NonMutatingTest, FindFirstOfWithPredicate) {
pw::containers::FindFirstOf(span_, array_, BinPredicate);
pw::containers::FindFirstOf(array_, span_, BinPredicate);
}
TEST_F(NonMutatingTest, AdjacentFind) { pw::containers::AdjacentFind(array_); }
TEST_F(NonMutatingTest, AdjacentFindWithPredicate) {
pw::containers::AdjacentFind(array_, BinPredicate);
}
TEST_F(NonMutatingTest, Count) {
EXPECT_EQ(1, pw::containers::Count(span_, 3));
}
TEST_F(NonMutatingTest, CountIf) {
EXPECT_EQ(2, pw::containers::CountIf(span_, Predicate));
}
TEST_F(NonMutatingTest, Mismatch) {
// Testing necessary as pw::containers::Mismatch executes logic.
{
auto result = pw::containers::Mismatch(span_, vector_);
EXPECT_EQ(result.first, span_.end());
EXPECT_EQ(result.second, vector_.end());
}
{
auto result = pw::containers::Mismatch(vector_, span_);
EXPECT_EQ(result.first, vector_.end());
EXPECT_EQ(result.second, span_.end());
}
vector_.back() = 5;
{
auto result = pw::containers::Mismatch(span_, vector_);
EXPECT_EQ(result.first, std::prev(span_.end()));
EXPECT_EQ(result.second, std::prev(vector_.end()));
}
{
auto result = pw::containers::Mismatch(vector_, span_);
EXPECT_EQ(result.first, std::prev(vector_.end()));
EXPECT_EQ(result.second, std::prev(span_.end()));
}
vector_.pop_back();
{
auto result = pw::containers::Mismatch(span_, vector_);
EXPECT_EQ(result.first, std::prev(span_.end()));
EXPECT_EQ(result.second, vector_.end());
}
{
auto result = pw::containers::Mismatch(vector_, span_);
EXPECT_EQ(result.first, vector_.end());
EXPECT_EQ(result.second, std::prev(span_.end()));
}
{
struct NoNotEquals {
constexpr bool operator==(NoNotEquals) const { return true; }
constexpr bool operator!=(NoNotEquals) const = delete;
};
pw::Vector<NoNotEquals, 1> first;
std::array<NoNotEquals, 1> second;
// Check this still compiles.
pw::containers::Mismatch(first, second);
}
}
TEST_F(NonMutatingTest, MismatchWithPredicate) {
// Testing necessary as pw::containers::Mismatch executes logic.
{
auto result = pw::containers::Mismatch(span_, vector_, BinPredicate);
EXPECT_EQ(result.first, span_.begin());
EXPECT_EQ(result.second, vector_.begin());
}
{
auto result = pw::containers::Mismatch(vector_, span_, BinPredicate);
EXPECT_EQ(result.first, vector_.begin());
EXPECT_EQ(result.second, span_.begin());
}
vector_.front() = 0;
{
auto result = pw::containers::Mismatch(span_, vector_, BinPredicate);
EXPECT_EQ(result.first, span_.begin());
EXPECT_EQ(result.second, vector_.begin());
}
{
auto result = pw::containers::Mismatch(vector_, span_, BinPredicate);
EXPECT_EQ(result.first, std::next(vector_.begin()));
EXPECT_EQ(result.second, std::next(span_.begin()));
}
vector_.clear();
{
auto result = pw::containers::Mismatch(span_, vector_, BinPredicate);
EXPECT_EQ(result.first, span_.begin());
EXPECT_EQ(result.second, vector_.end());
}
{
auto result = pw::containers::Mismatch(vector_, span_, BinPredicate);
EXPECT_EQ(result.first, vector_.end());
EXPECT_EQ(result.second, span_.begin());
}
}
TEST_F(NonMutatingTest, Equal) {
EXPECT_TRUE(pw::containers::Equal(vector_, span_));
EXPECT_TRUE(pw::containers::Equal(span_, vector_));
EXPECT_TRUE(pw::containers::Equal(span_, array_));
EXPECT_TRUE(pw::containers::Equal(array_, vector_));
pw::containers::FlatMap<char, int, 3> map1({{{'A', 1}, {'B', 2}, {'C', 3}}});
pw::containers::FlatMap<char, int, 3> map2({{{'B', 2}, {'A', 1}, {'C', 3}}});
pw::containers::FlatMap<char, int, 3> map3({{{'A', 1}, {'B', 2}, {'C', 4}}});
pw::containers::FlatMap<char, int, 3> map4({{{'A', 1}, {'B', 2}, {'D', 3}}});
EXPECT_TRUE(pw::containers::Equal(map1, map2));
EXPECT_FALSE(pw::containers::Equal(map1, map3));
EXPECT_FALSE(pw::containers::Equal(map1, map4));
// Test that behavior appropriately differs from that of equal().
pw::Vector<int, 4> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(pw::containers::Equal(vector_plus, span_));
EXPECT_FALSE(pw::containers::Equal(span_, vector_plus));
EXPECT_FALSE(pw::containers::Equal(array_, vector_plus));
}
TEST_F(NonMutatingTest, EqualWithPredicate) {
EXPECT_TRUE(pw::containers::Equal(vector_, span_, Equals));
EXPECT_TRUE(pw::containers::Equal(span_, vector_, Equals));
EXPECT_TRUE(pw::containers::Equal(array_, span_, Equals));
EXPECT_TRUE(pw::containers::Equal(vector_, array_, Equals));
// Test that behavior appropriately differs from that of equal().
pw::Vector<int, 4> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(pw::containers::Equal(vector_plus, span_, Equals));
EXPECT_FALSE(pw::containers::Equal(span_, vector_plus, Equals));
EXPECT_FALSE(pw::containers::Equal(vector_plus, array_, Equals));
}
TEST_F(NonMutatingTest, IsPermutation) {
auto vector_permut_ = vector_;
std::next_permutation(vector_permut_.begin(), vector_permut_.end());
EXPECT_TRUE(pw::containers::IsPermutation(vector_permut_, span_));
EXPECT_TRUE(pw::containers::IsPermutation(span_, vector_permut_));
// Test that behavior appropriately differs from that of is_permutation().
pw::Vector<int, 4> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(pw::containers::IsPermutation(vector_plus, span_));
EXPECT_FALSE(pw::containers::IsPermutation(span_, vector_plus));
}
TEST_F(NonMutatingTest, IsPermutationWithPredicate) {
auto vector_permut_ = vector_;
std::next_permutation(vector_permut_.begin(), vector_permut_.end());
EXPECT_TRUE(pw::containers::IsPermutation(vector_permut_, span_, Equals));
EXPECT_TRUE(pw::containers::IsPermutation(span_, vector_permut_, Equals));
// Test that behavior appropriately differs from that of is_permutation().
pw::Vector<int, 4> vector_plus = {1, 2, 3};
vector_plus.push_back(4);
EXPECT_FALSE(pw::containers::IsPermutation(vector_plus, span_, Equals));
EXPECT_FALSE(pw::containers::IsPermutation(span_, vector_plus, Equals));
}
TEST_F(NonMutatingTest, Search) {
pw::containers::Search(span_, vector_);
pw::containers::Search(vector_, span_);
pw::containers::Search(array_, span_);
}
TEST_F(NonMutatingTest, SearchWithPredicate) {
pw::containers::Search(span_, vector_, BinPredicate);
pw::containers::Search(vector_, span_, BinPredicate);
}
TEST_F(NonMutatingTest, SearchN) { pw::containers::SearchN(span_, 3, 1); }
TEST_F(NonMutatingTest, SearchNWithPredicate) {
pw::containers::SearchN(span_, 3, 1, BinPredicate);
}