pw_containers/algorithm_test.cc

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