pw_containers/algorithm_test.cc - pigweed/sandbox - Git at Google

 // 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/constexpr.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, Contains) {
   EXPECT_TRUE(pw::containers::Contains(vector_, 3));
   EXPECT_FALSE(pw::containers::Contains(vector_, 4));
 }

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

 static constexpr std::array<int, 5> kConstExprTestAllOfValues = {5, 6, 7, 8, 9};
 PW_CONSTEXPR_TEST(AlgorithmPolyfill, AllOf, {
   PW_TEST_EXPECT_TRUE(pw::all_of(kConstExprTestAllOfValues.begin(),
                                  kConstExprTestAllOfValues.end(),
                                  [](auto v) { return v > 2; }));
   PW_TEST_EXPECT_TRUE(pw::all_of(kConstExprTestAllOfValues.begin(),
                                  kConstExprTestAllOfValues.end(),
                                  [](auto v) { return v < 10; }));
   PW_TEST_EXPECT_TRUE(!pw::all_of(kConstExprTestAllOfValues.begin(),
                                   kConstExprTestAllOfValues.end(),
                                   [](auto v) { return v > 10; }));
 });

 static constexpr std::array<int, 5> kConstExprTestAnyOfValues = {1, 2, 3, 4, 5};
 PW_CONSTEXPR_TEST(AlgorithmPolyfill, AnyOf, {
   PW_TEST_EXPECT_TRUE(pw::any_of(kConstExprTestAnyOfValues.begin(),
                                  kConstExprTestAnyOfValues.end(),
                                  [](auto v) { return v > 3; }));
   PW_TEST_EXPECT_TRUE(pw::any_of(kConstExprTestAnyOfValues.begin(),
                                  kConstExprTestAnyOfValues.end(),
                                  [](auto v) { return v == 1; }));
   PW_TEST_EXPECT_TRUE(!pw::any_of(kConstExprTestAnyOfValues.begin(),
                                   kConstExprTestAnyOfValues.end(),
                                   [](auto v) { return v > 10; }));
 });

 static constexpr std::array<int, 5> kConstExprTestFindIfValues = {
     1, 2, 3, 4, 5};
 PW_CONSTEXPR_TEST(AlgorithmPolyfill, FindIf, {
   constexpr auto it = pw::find_if(kConstExprTestFindIfValues.begin(),
                                   kConstExprTestFindIfValues.end(),
                                   [](auto v) { return v > 3; });
   PW_TEST_EXPECT_EQ(it, kConstExprTestFindIfValues.begin() + 3);

   constexpr auto it2 = pw::find_if(kConstExprTestFindIfValues.begin(),
                                    kConstExprTestFindIfValues.end(),
                                    [](auto v) { return v == 1; });
   PW_TEST_EXPECT_EQ(it2, kConstExprTestFindIfValues.begin());

   constexpr auto it3 = pw::find_if(kConstExprTestFindIfValues.begin(),
                                    kConstExprTestFindIfValues.end(),
                                    [](auto v) { return v > 10; });
   PW_TEST_EXPECT_EQ(it3, kConstExprTestFindIfValues.end());
 });

 PW_CONSTEXPR_TEST(AlgorithmPolyfill, Fill, {
   std::array<int, 5> values = {1, 2, 3, 4, 5};
   pw::fill(values.begin(), values.end(), 42);
   PW_TEST_EXPECT_TRUE(
       pw::all_of(values.begin(), values.end(), [](int v) { return v == 42; }));

   pw::fill(values.begin(), values.begin(), -1);
   PW_TEST_EXPECT_TRUE(
       pw::all_of(values.begin(), values.end(), [](int v) { return v == 42; }));
 });

 PW_CONSTEXPR_TEST(AlgorithmPolyfill, FillN, {
   std::array<int, 5> values = {1, 2, 3, 4, 5};

   PW_TEST_EXPECT_EQ(pw::fill_n(values.begin(), 3, 42), values.begin() + 3);
   PW_TEST_EXPECT_EQ(values[0], 42);
   PW_TEST_EXPECT_EQ(values[1], 42);
   PW_TEST_EXPECT_EQ(values[2], 42);
   PW_TEST_EXPECT_EQ(values[3], 4);
   PW_TEST_EXPECT_EQ(values[4], 5);

   PW_TEST_EXPECT_EQ(pw::fill_n(values.begin(), 0, -1), values.begin());
   PW_TEST_EXPECT_EQ(values[0], 42);
 });

 PW_CONSTEXPR_TEST(AlgorithmPolyfill, Copy, {
   constexpr std::array<int, 5> source = {1, 2, 3, 4, 5};
   std::array<int, 5> dest = {0, 0, 0, 0, 0};
   auto it = pw::copy(source.begin(), source.end(), dest.begin());
   PW_TEST_EXPECT_EQ(it, dest.end());
   PW_TEST_EXPECT_EQ(source[0], dest[0]);
   PW_TEST_EXPECT_EQ(source[1], dest[1]);
   PW_TEST_EXPECT_EQ(source[2], dest[2]);
   PW_TEST_EXPECT_EQ(source[3], dest[3]);
   PW_TEST_EXPECT_EQ(source[4], dest[4]);

   // Test empty range
   std::array<int, 5> dest2 = {0, 0, 0, 0, 0};
   auto it2 = pw::copy(source.begin(), source.begin(), dest2.begin());
   PW_TEST_EXPECT_EQ(it2, dest2.begin());
   PW_TEST_EXPECT_EQ(dest2[0], 0);
 });

 PW_CONSTEXPR_TEST(AlgorithmPolyfill, CopyIf, {
   constexpr std::array<int, 5> source = {1, 2, 3, 4, 5};
   std::array<int, 5> dest = {0, 0, 0, 0, 0};
   auto it = pw::copy_if(source.begin(), source.end(), dest.begin(), [](int x) {
     return x % 2 == 0;
   });
   PW_TEST_EXPECT_EQ(it, dest.begin() + 2);
   PW_TEST_EXPECT_EQ(dest[0], 2);
   PW_TEST_EXPECT_EQ(dest[1], 4);
   PW_TEST_EXPECT_EQ(dest[2], 0);

   // Test with no elements matching
   std::array<int, 5> dest2 = {0, 0, 0, 0, 0};
   auto it2 =
       pw::copy_if(source.begin(), source.end(), dest2.begin(), [](int x) {
         return x > 10;
       });
   PW_TEST_EXPECT_EQ(it2, dest2.begin());
   PW_TEST_EXPECT_EQ(dest2[0], 0);
 });
	// 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/constexpr.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, Contains) {
	EXPECT_TRUE(pw::containers::Contains(vector_, 3));
	EXPECT_FALSE(pw::containers::Contains(vector_, 4));
	}

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

	static constexpr std::array<int, 5> kConstExprTestAllOfValues = {5, 6, 7, 8, 9};
	PW_CONSTEXPR_TEST(AlgorithmPolyfill, AllOf, {
	PW_TEST_EXPECT_TRUE(pw::all_of(kConstExprTestAllOfValues.begin(),
	kConstExprTestAllOfValues.end(),
	[](auto v) { return v > 2; }));
	PW_TEST_EXPECT_TRUE(pw::all_of(kConstExprTestAllOfValues.begin(),
	kConstExprTestAllOfValues.end(),
	[](auto v) { return v < 10; }));
	PW_TEST_EXPECT_TRUE(!pw::all_of(kConstExprTestAllOfValues.begin(),
	kConstExprTestAllOfValues.end(),
	[](auto v) { return v > 10; }));
	});

	static constexpr std::array<int, 5> kConstExprTestAnyOfValues = {1, 2, 3, 4, 5};
	PW_CONSTEXPR_TEST(AlgorithmPolyfill, AnyOf, {
	PW_TEST_EXPECT_TRUE(pw::any_of(kConstExprTestAnyOfValues.begin(),
	kConstExprTestAnyOfValues.end(),
	[](auto v) { return v > 3; }));
	PW_TEST_EXPECT_TRUE(pw::any_of(kConstExprTestAnyOfValues.begin(),
	kConstExprTestAnyOfValues.end(),
	[](auto v) { return v == 1; }));
	PW_TEST_EXPECT_TRUE(!pw::any_of(kConstExprTestAnyOfValues.begin(),
	kConstExprTestAnyOfValues.end(),
	[](auto v) { return v > 10; }));
	});

	static constexpr std::array<int, 5> kConstExprTestFindIfValues = {
	1, 2, 3, 4, 5};
	PW_CONSTEXPR_TEST(AlgorithmPolyfill, FindIf, {
	constexpr auto it = pw::find_if(kConstExprTestFindIfValues.begin(),
	kConstExprTestFindIfValues.end(),
	[](auto v) { return v > 3; });
	PW_TEST_EXPECT_EQ(it, kConstExprTestFindIfValues.begin() + 3);

	constexpr auto it2 = pw::find_if(kConstExprTestFindIfValues.begin(),
	kConstExprTestFindIfValues.end(),
	[](auto v) { return v == 1; });
	PW_TEST_EXPECT_EQ(it2, kConstExprTestFindIfValues.begin());

	constexpr auto it3 = pw::find_if(kConstExprTestFindIfValues.begin(),
	kConstExprTestFindIfValues.end(),
	[](auto v) { return v > 10; });
	PW_TEST_EXPECT_EQ(it3, kConstExprTestFindIfValues.end());
	});

	PW_CONSTEXPR_TEST(AlgorithmPolyfill, Fill, {
	std::array<int, 5> values = {1, 2, 3, 4, 5};
	pw::fill(values.begin(), values.end(), 42);
	PW_TEST_EXPECT_TRUE(
	pw::all_of(values.begin(), values.end(), [](int v) { return v == 42; }));

	pw::fill(values.begin(), values.begin(), -1);
	PW_TEST_EXPECT_TRUE(
	pw::all_of(values.begin(), values.end(), [](int v) { return v == 42; }));
	});

	PW_CONSTEXPR_TEST(AlgorithmPolyfill, FillN, {
	std::array<int, 5> values = {1, 2, 3, 4, 5};

	PW_TEST_EXPECT_EQ(pw::fill_n(values.begin(), 3, 42), values.begin() + 3);
	PW_TEST_EXPECT_EQ(values[0], 42);
	PW_TEST_EXPECT_EQ(values[1], 42);
	PW_TEST_EXPECT_EQ(values[2], 42);
	PW_TEST_EXPECT_EQ(values[3], 4);
	PW_TEST_EXPECT_EQ(values[4], 5);

	PW_TEST_EXPECT_EQ(pw::fill_n(values.begin(), 0, -1), values.begin());
	PW_TEST_EXPECT_EQ(values[0], 42);
	});

	PW_CONSTEXPR_TEST(AlgorithmPolyfill, Copy, {
	constexpr std::array<int, 5> source = {1, 2, 3, 4, 5};
	std::array<int, 5> dest = {0, 0, 0, 0, 0};
	auto it = pw::copy(source.begin(), source.end(), dest.begin());
	PW_TEST_EXPECT_EQ(it, dest.end());
	PW_TEST_EXPECT_EQ(source[0], dest[0]);
	PW_TEST_EXPECT_EQ(source[1], dest[1]);
	PW_TEST_EXPECT_EQ(source[2], dest[2]);
	PW_TEST_EXPECT_EQ(source[3], dest[3]);
	PW_TEST_EXPECT_EQ(source[4], dest[4]);

	// Test empty range
	std::array<int, 5> dest2 = {0, 0, 0, 0, 0};
	auto it2 = pw::copy(source.begin(), source.begin(), dest2.begin());
	PW_TEST_EXPECT_EQ(it2, dest2.begin());
	PW_TEST_EXPECT_EQ(dest2[0], 0);
	});

	PW_CONSTEXPR_TEST(AlgorithmPolyfill, CopyIf, {
	constexpr std::array<int, 5> source = {1, 2, 3, 4, 5};
	std::array<int, 5> dest = {0, 0, 0, 0, 0};
	auto it = pw::copy_if(source.begin(), source.end(), dest.begin(), [](int x) {
	return x % 2 == 0;
	});
	PW_TEST_EXPECT_EQ(it, dest.begin() + 2);
	PW_TEST_EXPECT_EQ(dest[0], 2);
	PW_TEST_EXPECT_EQ(dest[1], 4);
	PW_TEST_EXPECT_EQ(dest[2], 0);

	// Test with no elements matching
	std::array<int, 5> dest2 = {0, 0, 0, 0, 0};
	auto it2 =
	pw::copy_if(source.begin(), source.end(), dest2.begin(), [](int x) {
	return x > 10;
	});
	PW_TEST_EXPECT_EQ(it2, dest2.begin());
	PW_TEST_EXPECT_EQ(dest2[0], 0);
	});