// Copyright 2017 The Abseil 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 "absl/algorithm/container.h"

#include <algorithm>
#include <array>
#include <cstddef>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <list>
#include <memory>
#include <ostream>
#include <random>
#include <set>
#include <type_traits>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/base/casts.h"
#include "absl/base/config.h"
#include "absl/base/macros.h"
#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
#include "absl/random/random.h"
#include "absl/types/span.h"

#ifdef __cpp_lib_span
#include <span>  // NOLINT(build/c++20)
#endif

namespace {

using ::testing::Each;
using ::testing::ElementsAre;
using ::testing::Gt;
using ::testing::IsNull;
using ::testing::IsSubsetOf;
using ::testing::Lt;
using ::testing::Pointee;
using ::testing::SizeIs;
using ::testing::Truly;
using ::testing::UnorderedElementsAre;

// 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::unordered_set<int> container_ = {1, 2, 3};
  std::list<int> sequence_ = {1, 2, 3};
  std::vector<int> vector_ = {1, 2, 3};
  int array_[3] = {1, 2, 3};
};

struct AccumulateCalls {
  void operator()(int value) { calls.push_back(value); }
  std::vector<int> 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; }
bool IsOdd(int x) { return x % 2 != 0; }

TEST(Span, IsSpan) {
  static_assert(
      absl::container_algorithm_internal::IsSpan<absl::Span<int>>::value);
  static_assert(
      absl::container_algorithm_internal::IsSpan<const absl::Span<int>>::value);
  static_assert(absl::container_algorithm_internal::IsSpan<
                volatile absl::Span<int>>::value);
  static_assert(absl::container_algorithm_internal::IsSpan<
                const volatile absl::Span<int>>::value);

  static_assert(
      !absl::container_algorithm_internal::IsSpan<absl::Span<int>&>::value);
  static_assert(
      !absl::container_algorithm_internal::IsSpan<absl::Span<int>&&>::value);

#ifdef __cpp_lib_span
  static_assert(
      absl::container_algorithm_internal::IsSpan<std::span<int>>::value);
  static_assert(
      !absl::container_algorithm_internal::IsSpan<std::span<int>&>::value);
  static_assert(
      !absl::container_algorithm_internal::IsSpan<std::span<int>&&>::value);
#endif
}

TEST_F(NonMutatingTest, Distance) {
  EXPECT_EQ(container_.size(),
            static_cast<size_t>(absl::c_distance(container_)));
  EXPECT_EQ(sequence_.size(), static_cast<size_t>(absl::c_distance(sequence_)));
  EXPECT_EQ(vector_.size(), static_cast<size_t>(absl::c_distance(vector_)));
  EXPECT_EQ(std::size(array_), static_cast<size_t>(absl::c_distance(array_)));

  // Works with a temporary argument.
  EXPECT_EQ(vector_.size(),
            static_cast<size_t>(absl::c_distance(std::vector<int>(vector_))));
}

TEST_F(NonMutatingTest, Distance_OverloadedBeginEnd) {
  // Works with classes which have custom ADL-selected overloads of std::begin
  // and std::end.
  std::initializer_list<int> a = {1, 2, 3};
  std::valarray<int> b = {1, 2, 3};
  EXPECT_EQ(3, absl::c_distance(a));
  EXPECT_EQ(3, absl::c_distance(b));

  // It is assumed that other c_* functions use the same mechanism for
  // ADL-selecting begin/end overloads.
}

TEST_F(NonMutatingTest, ForEach) {
  AccumulateCalls c = absl::c_for_each(container_, AccumulateCalls());
  // Don't rely on the unordered_set's order.
  std::sort(c.calls.begin(), c.calls.end());
  EXPECT_EQ(vector_, c.calls);

  // Works with temporary container, too.
  AccumulateCalls c2 =
      absl::c_for_each(std::unordered_set<int>(container_), AccumulateCalls());
  std::sort(c2.calls.begin(), c2.calls.end());
  EXPECT_EQ(vector_, c2.calls);
}

TEST_F(NonMutatingTest, FindReturnsCorrectType) {
  auto it = absl::c_find(container_, 3);
  EXPECT_EQ(3, *it);
  absl::c_find(absl::implicit_cast<const std::list<int>&>(sequence_), 3);
}

TEST_F(NonMutatingTest, Contains) {
  EXPECT_TRUE(absl::c_contains(container_, 3));
  EXPECT_FALSE(absl::c_contains(container_, 4));
}

TEST_F(NonMutatingTest, FindIf) { absl::c_find_if(container_, Predicate); }

TEST_F(NonMutatingTest, FindIfNot) {
  absl::c_find_if_not(container_, Predicate);
}

TEST_F(NonMutatingTest, FindEnd) {
  absl::c_find_end(sequence_, vector_);
  absl::c_find_end(vector_, sequence_);
}

TEST_F(NonMutatingTest, FindEndWithPredicate) {
  absl::c_find_end(sequence_, vector_, BinPredicate);
  absl::c_find_end(vector_, sequence_, BinPredicate);
}

TEST_F(NonMutatingTest, FindFirstOf) {
  absl::c_find_first_of(container_, sequence_);
  absl::c_find_first_of(sequence_, container_);
  absl::c_find_first_of(sequence_, std::array<int, 2>{1, 2});
}

TEST_F(NonMutatingTest, FindFirstOfWithPredicate) {
  absl::c_find_first_of(container_, sequence_, BinPredicate);
  absl::c_find_first_of(sequence_, container_, BinPredicate);
  absl::c_find_first_of(sequence_, std::array<int, 2>{1, 2}, BinPredicate);
}

TEST_F(NonMutatingTest, AdjacentFind) { absl::c_adjacent_find(sequence_); }

TEST_F(NonMutatingTest, AdjacentFindWithPredicate) {
  absl::c_adjacent_find(sequence_, BinPredicate);
}

TEST_F(NonMutatingTest, Count) { EXPECT_EQ(1, absl::c_count(container_, 3)); }

TEST_F(NonMutatingTest, CountIf) {
  EXPECT_EQ(2, absl::c_count_if(container_, Predicate));
  const std::unordered_set<int>& const_container = container_;
  EXPECT_EQ(2, absl::c_count_if(const_container, Predicate));
}

TEST_F(NonMutatingTest, Mismatch) {
  // Testing necessary as absl::c_mismatch executes logic.
  {
    auto result = absl::c_mismatch(vector_, sequence_);
    EXPECT_EQ(result.first, vector_.end());
    EXPECT_EQ(result.second, sequence_.end());
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_);
    EXPECT_EQ(result.first, sequence_.end());
    EXPECT_EQ(result.second, vector_.end());
  }

  sequence_.back() = 5;
  {
    auto result = absl::c_mismatch(vector_, sequence_);
    EXPECT_EQ(result.first, std::prev(vector_.end()));
    EXPECT_EQ(result.second, std::prev(sequence_.end()));
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_);
    EXPECT_EQ(result.first, std::prev(sequence_.end()));
    EXPECT_EQ(result.second, std::prev(vector_.end()));
  }

  sequence_.pop_back();
  {
    auto result = absl::c_mismatch(vector_, sequence_);
    EXPECT_EQ(result.first, std::prev(vector_.end()));
    EXPECT_EQ(result.second, sequence_.end());
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_);
    EXPECT_EQ(result.first, sequence_.end());
    EXPECT_EQ(result.second, std::prev(vector_.end()));
  }
  {
    struct NoNotEquals {
      constexpr bool operator==(NoNotEquals) const { return true; }
      constexpr bool operator!=(NoNotEquals) const = delete;
    };
    std::vector<NoNotEquals> first;
    std::list<NoNotEquals> second;

    // Check this still compiles.
    absl::c_mismatch(first, second);
  }
}

TEST_F(NonMutatingTest, MismatchWithPredicate) {
  // Testing necessary as absl::c_mismatch executes logic.
  {
    auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
    EXPECT_EQ(result.first, vector_.begin());
    EXPECT_EQ(result.second, sequence_.begin());
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
    EXPECT_EQ(result.first, sequence_.begin());
    EXPECT_EQ(result.second, vector_.begin());
  }

  sequence_.front() = 0;
  {
    auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
    EXPECT_EQ(result.first, vector_.begin());
    EXPECT_EQ(result.second, sequence_.begin());
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
    EXPECT_EQ(result.first, std::next(sequence_.begin()));
    EXPECT_EQ(result.second, std::next(vector_.begin()));
  }

  sequence_.clear();
  {
    auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
    EXPECT_EQ(result.first, vector_.begin());
    EXPECT_EQ(result.second, sequence_.end());
  }
  {
    auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
    EXPECT_EQ(result.first, sequence_.end());
    EXPECT_EQ(result.second, vector_.begin());
  }
}

TEST_F(NonMutatingTest, Equal) {
  EXPECT_TRUE(absl::c_equal(vector_, sequence_));
  EXPECT_TRUE(absl::c_equal(sequence_, vector_));
  EXPECT_TRUE(absl::c_equal(sequence_, array_));
  EXPECT_TRUE(absl::c_equal(array_, vector_));

  // Test that behavior appropriately differs from that of equal().
  std::vector<int> vector_plus = {1, 2, 3};
  vector_plus.push_back(4);
  EXPECT_FALSE(absl::c_equal(vector_plus, sequence_));
  EXPECT_FALSE(absl::c_equal(sequence_, vector_plus));
  EXPECT_FALSE(absl::c_equal(array_, vector_plus));
}

TEST_F(NonMutatingTest, EqualWithPredicate) {
  EXPECT_TRUE(absl::c_equal(vector_, sequence_, Equals));
  EXPECT_TRUE(absl::c_equal(sequence_, vector_, Equals));
  EXPECT_TRUE(absl::c_equal(array_, sequence_, Equals));
  EXPECT_TRUE(absl::c_equal(vector_, array_, Equals));

  // Test that behavior appropriately differs from that of equal().
  std::vector<int> vector_plus = {1, 2, 3};
  vector_plus.push_back(4);
  EXPECT_FALSE(absl::c_equal(vector_plus, sequence_, Equals));
  EXPECT_FALSE(absl::c_equal(sequence_, vector_plus, Equals));
  EXPECT_FALSE(absl::c_equal(vector_plus, array_, Equals));
}

TEST_F(NonMutatingTest, IsPermutation) {
  auto vector_permut_ = vector_;
  std::next_permutation(vector_permut_.begin(), vector_permut_.end());
  EXPECT_TRUE(absl::c_is_permutation(vector_permut_, sequence_));
  EXPECT_TRUE(absl::c_is_permutation(sequence_, vector_permut_));

  // Test that behavior appropriately differs from that of is_permutation().
  std::vector<int> vector_plus = {1, 2, 3};
  vector_plus.push_back(4);
  EXPECT_FALSE(absl::c_is_permutation(vector_plus, sequence_));
  EXPECT_FALSE(absl::c_is_permutation(sequence_, vector_plus));
}

TEST_F(NonMutatingTest, IsPermutationWithPredicate) {
  auto vector_permut_ = vector_;
  std::next_permutation(vector_permut_.begin(), vector_permut_.end());
  EXPECT_TRUE(absl::c_is_permutation(vector_permut_, sequence_, Equals));
  EXPECT_TRUE(absl::c_is_permutation(sequence_, vector_permut_, Equals));

  // Test that behavior appropriately differs from that of is_permutation().
  std::vector<int> vector_plus = {1, 2, 3};
  vector_plus.push_back(4);
  EXPECT_FALSE(absl::c_is_permutation(vector_plus, sequence_, Equals));
  EXPECT_FALSE(absl::c_is_permutation(sequence_, vector_plus, Equals));
}

TEST_F(NonMutatingTest, Search) {
  absl::c_search(sequence_, vector_);
  absl::c_search(vector_, sequence_);
  absl::c_search(array_, sequence_);
}

TEST_F(NonMutatingTest, SearchWithPredicate) {
  absl::c_search(sequence_, vector_, BinPredicate);
  absl::c_search(vector_, sequence_, BinPredicate);
}

TEST_F(NonMutatingTest, ContainsSubrange) {
  EXPECT_TRUE(absl::c_contains_subrange(sequence_, vector_));
  EXPECT_TRUE(absl::c_contains_subrange(vector_, sequence_));
  EXPECT_TRUE(absl::c_contains_subrange(array_, sequence_));
}

TEST_F(NonMutatingTest, ContainsSubrangeWithPredicate) {
  EXPECT_TRUE(absl::c_contains_subrange(sequence_, vector_, Equals));
  EXPECT_TRUE(absl::c_contains_subrange(vector_, sequence_, Equals));
}

TEST_F(NonMutatingTest, SearchN) { absl::c_search_n(sequence_, 3, 1); }

TEST_F(NonMutatingTest, SearchNWithPredicate) {
  absl::c_search_n(sequence_, 3, 1, BinPredicate);
}

TEST_F(NonMutatingTest, LowerBound) {
  std::list<int>::iterator i = absl::c_lower_bound(sequence_, 3);
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(2, std::distance(sequence_.begin(), i));
  EXPECT_EQ(3, *i);
}

TEST_F(NonMutatingTest, LowerBoundWithPredicate) {
  std::vector<int> v(vector_);
  std::sort(v.begin(), v.end(), std::greater<int>());
  std::vector<int>::iterator i = absl::c_lower_bound(v, 3, std::greater<int>());
  EXPECT_TRUE(i == v.begin());
  EXPECT_EQ(3, *i);
}

TEST_F(NonMutatingTest, UpperBound) {
  std::list<int>::iterator i = absl::c_upper_bound(sequence_, 1);
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(1, std::distance(sequence_.begin(), i));
  EXPECT_EQ(2, *i);
}

TEST_F(NonMutatingTest, UpperBoundWithPredicate) {
  std::vector<int> v(vector_);
  std::sort(v.begin(), v.end(), std::greater<int>());
  std::vector<int>::iterator i = absl::c_upper_bound(v, 1, std::greater<int>());
  EXPECT_EQ(3, i - v.begin());
  EXPECT_TRUE(i == v.end());
}

TEST_F(NonMutatingTest, EqualRange) {
  std::pair<std::list<int>::iterator, std::list<int>::iterator> p =
      absl::c_equal_range(sequence_, 2);
  EXPECT_EQ(1, std::distance(sequence_.begin(), p.first));
  EXPECT_EQ(2, std::distance(sequence_.begin(), p.second));
}

TEST_F(NonMutatingTest, EqualRangeArray) {
  auto p = absl::c_equal_range(array_, 2);
  EXPECT_EQ(1, std::distance(std::begin(array_), p.first));
  EXPECT_EQ(2, std::distance(std::begin(array_), p.second));
}

TEST_F(NonMutatingTest, EqualRangeWithPredicate) {
  std::vector<int> v(vector_);
  std::sort(v.begin(), v.end(), std::greater<int>());
  std::pair<std::vector<int>::iterator, std::vector<int>::iterator> p =
      absl::c_equal_range(v, 2, std::greater<int>());
  EXPECT_EQ(1, std::distance(v.begin(), p.first));
  EXPECT_EQ(2, std::distance(v.begin(), p.second));
}

TEST_F(NonMutatingTest, BinarySearch) {
  EXPECT_TRUE(absl::c_binary_search(vector_, 2));
  EXPECT_TRUE(absl::c_binary_search(std::vector<int>(vector_), 2));
}

TEST_F(NonMutatingTest, BinarySearchWithPredicate) {
  std::vector<int> v(vector_);
  std::sort(v.begin(), v.end(), std::greater<int>());
  EXPECT_TRUE(absl::c_binary_search(v, 2, std::greater<int>()));
  EXPECT_TRUE(
      absl::c_binary_search(std::vector<int>(v), 2, std::greater<int>()));
}

TEST_F(NonMutatingTest, MinElement) {
  std::list<int>::iterator i = absl::c_min_element(sequence_);
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(*i, 1);
}

TEST_F(NonMutatingTest, MinElementWithPredicate) {
  std::list<int>::iterator i =
      absl::c_min_element(sequence_, std::greater<int>());
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(*i, 3);
}

TEST_F(NonMutatingTest, MaxElement) {
  std::list<int>::iterator i = absl::c_max_element(sequence_);
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(*i, 3);
}

TEST_F(NonMutatingTest, MaxElementWithPredicate) {
  std::list<int>::iterator i =
      absl::c_max_element(sequence_, std::greater<int>());
  ASSERT_TRUE(i != sequence_.end());
  EXPECT_EQ(*i, 1);
}

TEST_F(NonMutatingTest, LexicographicalCompare) {
  EXPECT_FALSE(absl::c_lexicographical_compare(sequence_, sequence_));

  std::vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(4);

  EXPECT_TRUE(absl::c_lexicographical_compare(sequence_, v));
  EXPECT_TRUE(absl::c_lexicographical_compare(std::list<int>(sequence_), v));
}

TEST_F(NonMutatingTest, LexicographicalCopmareWithPredicate) {
  EXPECT_FALSE(absl::c_lexicographical_compare(sequence_, sequence_,
                                               std::greater<int>()));

  std::vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(4);

  EXPECT_TRUE(
      absl::c_lexicographical_compare(v, sequence_, std::greater<int>()));
  EXPECT_TRUE(absl::c_lexicographical_compare(
      std::vector<int>(v), std::list<int>(sequence_), std::greater<int>()));
}

TEST_F(NonMutatingTest, Includes) {
  std::set<int> s(vector_.begin(), vector_.end());
  s.insert(4);
  EXPECT_TRUE(absl::c_includes(s, vector_));
}

TEST_F(NonMutatingTest, IncludesWithPredicate) {
  std::vector<int> v = {3, 2, 1};
  std::set<int, std::greater<int>> s(v.begin(), v.end());
  s.insert(4);
  EXPECT_TRUE(absl::c_includes(s, v, std::greater<int>()));
}

class NumericMutatingTest : public testing::Test {
 protected:
  std::list<int> list_ = {1, 2, 3};
  std::vector<int> output_;
};

TEST_F(NumericMutatingTest, Iota) {
  absl::c_iota(list_, 5);
  std::list<int> expected{5, 6, 7};
  EXPECT_EQ(list_, expected);
}

TEST_F(NonMutatingTest, Accumulate) {
  EXPECT_EQ(absl::c_accumulate(sequence_, 4), 1 + 2 + 3 + 4);
}

TEST_F(NonMutatingTest, AccumulateWithBinaryOp) {
  EXPECT_EQ(absl::c_accumulate(sequence_, 4, std::multiplies<int>()),
            1 * 2 * 3 * 4);
}

TEST_F(NonMutatingTest, AccumulateLvalueInit) {
  int lvalue = 4;
  EXPECT_EQ(absl::c_accumulate(sequence_, lvalue), 1 + 2 + 3 + 4);
}

TEST_F(NonMutatingTest, AccumulateWithBinaryOpLvalueInit) {
  int lvalue = 4;
  EXPECT_EQ(absl::c_accumulate(sequence_, lvalue, std::multiplies<int>()),
            1 * 2 * 3 * 4);
}

TEST_F(NonMutatingTest, InnerProduct) {
  EXPECT_EQ(absl::c_inner_product(sequence_, vector_, 1000),
            1000 + 1 * 1 + 2 * 2 + 3 * 3);
}

TEST_F(NonMutatingTest, InnerProductWithBinaryOps) {
  EXPECT_EQ(absl::c_inner_product(sequence_, vector_, 10,
                                  std::multiplies<int>(), std::plus<int>()),
            10 * (1 + 1) * (2 + 2) * (3 + 3));
}

TEST_F(NonMutatingTest, InnerProductLvalueInit) {
  int lvalue = 1000;
  EXPECT_EQ(absl::c_inner_product(sequence_, vector_, lvalue),
            1000 + 1 * 1 + 2 * 2 + 3 * 3);
}

TEST_F(NonMutatingTest, InnerProductWithBinaryOpsLvalueInit) {
  int lvalue = 10;
  EXPECT_EQ(absl::c_inner_product(sequence_, vector_, lvalue,
                                  std::multiplies<int>(), std::plus<int>()),
            10 * (1 + 1) * (2 + 2) * (3 + 3));
}

TEST_F(NumericMutatingTest, AdjacentDifference) {
  auto last = absl::c_adjacent_difference(list_, std::back_inserter(output_));
  *last = 1000;
  std::vector<int> expected{1, 2 - 1, 3 - 2, 1000};
  EXPECT_EQ(output_, expected);
}

TEST_F(NumericMutatingTest, AdjacentDifferenceWithBinaryOp) {
  auto last = absl::c_adjacent_difference(list_, std::back_inserter(output_),
                                          std::multiplies<int>());
  *last = 1000;
  std::vector<int> expected{1, 2 * 1, 3 * 2, 1000};
  EXPECT_EQ(output_, expected);
}

TEST_F(NumericMutatingTest, PartialSum) {
  auto last = absl::c_partial_sum(list_, std::back_inserter(output_));
  *last = 1000;
  std::vector<int> expected{1, 1 + 2, 1 + 2 + 3, 1000};
  EXPECT_EQ(output_, expected);
}

TEST_F(NumericMutatingTest, PartialSumWithBinaryOp) {
  auto last = absl::c_partial_sum(list_, std::back_inserter(output_),
                                  std::multiplies<int>());
  *last = 1000;
  std::vector<int> expected{1, 1 * 2, 1 * 2 * 3, 1000};
  EXPECT_EQ(output_, expected);
}

TEST_F(NonMutatingTest, LinearSearch) {
  EXPECT_TRUE(absl::c_linear_search(container_, 3));
  EXPECT_FALSE(absl::c_linear_search(container_, 4));
}

TEST_F(NonMutatingTest, AllOf) {
  const std::vector<int>& v = vector_;
  EXPECT_FALSE(absl::c_all_of(v, [](int x) { return x > 1; }));
  EXPECT_TRUE(absl::c_all_of(v, [](int x) { return x > 0; }));
}

TEST_F(NonMutatingTest, AnyOf) {
  const std::vector<int>& v = vector_;
  EXPECT_TRUE(absl::c_any_of(v, [](int x) { return x > 2; }));
  EXPECT_FALSE(absl::c_any_of(v, [](int x) { return x > 5; }));
}

TEST_F(NonMutatingTest, NoneOf) {
  const std::vector<int>& v = vector_;
  EXPECT_FALSE(absl::c_none_of(v, [](int x) { return x > 2; }));
  EXPECT_TRUE(absl::c_none_of(v, [](int x) { return x > 5; }));
}

TEST_F(NonMutatingTest, MinMaxElementLess) {
  std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator>
      p = absl::c_minmax_element(vector_, std::less<int>());
  EXPECT_TRUE(p.first == vector_.begin());
  EXPECT_TRUE(p.second == vector_.begin() + 2);
}

TEST_F(NonMutatingTest, MinMaxElementGreater) {
  std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator>
      p = absl::c_minmax_element(vector_, std::greater<int>());
  EXPECT_TRUE(p.first == vector_.begin() + 2);
  EXPECT_TRUE(p.second == vector_.begin());
}

TEST_F(NonMutatingTest, MinMaxElementNoPredicate) {
  std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator>
      p = absl::c_minmax_element(vector_);
  EXPECT_TRUE(p.first == vector_.begin());
  EXPECT_TRUE(p.second == vector_.begin() + 2);
}

class SortingTest : public testing::Test {
 protected:
  std::list<int> sorted_ = {1, 2, 3, 4};
  std::list<int> unsorted_ = {2, 4, 1, 3};
  std::list<int> reversed_ = {4, 3, 2, 1};
};

TEST_F(SortingTest, IsSorted) {
  EXPECT_TRUE(absl::c_is_sorted(sorted_));
  EXPECT_FALSE(absl::c_is_sorted(unsorted_));
  EXPECT_FALSE(absl::c_is_sorted(reversed_));
}

TEST_F(SortingTest, IsSortedWithPredicate) {
  EXPECT_FALSE(absl::c_is_sorted(sorted_, std::greater<int>()));
  EXPECT_FALSE(absl::c_is_sorted(unsorted_, std::greater<int>()));
  EXPECT_TRUE(absl::c_is_sorted(reversed_, std::greater<int>()));
}

TEST_F(SortingTest, IsSortedUntil) {
  EXPECT_EQ(1, *absl::c_is_sorted_until(unsorted_));
  EXPECT_EQ(4, *absl::c_is_sorted_until(unsorted_, std::greater<int>()));
}

TEST_F(SortingTest, NthElement) {
  std::vector<int> unsorted = {2, 4, 1, 3};
  absl::c_nth_element(unsorted, unsorted.begin() + 2);
  EXPECT_THAT(unsorted, ElementsAre(Lt(3), Lt(3), 3, Gt(3)));
  absl::c_nth_element(unsorted, unsorted.begin() + 2, std::greater<int>());
  EXPECT_THAT(unsorted, ElementsAre(Gt(2), Gt(2), 2, Lt(2)));
}

TEST(MutatingTest, IsPartitioned) {
  EXPECT_TRUE(
      absl::c_is_partitioned(std::vector<int>{1, 3, 5, 2, 4, 6}, IsOdd));
  EXPECT_FALSE(
      absl::c_is_partitioned(std::vector<int>{1, 2, 3, 4, 5, 6}, IsOdd));
  EXPECT_FALSE(
      absl::c_is_partitioned(std::vector<int>{2, 4, 6, 1, 3, 5}, IsOdd));
}

TEST(MutatingTest, Partition) {
  std::vector<int> actual = {1, 2, 3, 4, 5};
  absl::c_partition(actual, IsOdd);
  EXPECT_THAT(actual, Truly([](const std::vector<int>& c) {
                return absl::c_is_partitioned(c, IsOdd);
              }));
}

TEST(MutatingTest, StablePartition) {
  std::vector<int> actual = {1, 2, 3, 4, 5};
  absl::c_stable_partition(actual, IsOdd);
  EXPECT_THAT(actual, ElementsAre(1, 3, 5, 2, 4));
}

TEST(MutatingTest, PartitionCopy) {
  const std::vector<int> initial = {1, 2, 3, 4, 5};
  std::vector<int> odds, evens;
  auto ends = absl::c_partition_copy(initial, back_inserter(odds),
                                     back_inserter(evens), IsOdd);
  *ends.first = 7;
  *ends.second = 6;
  EXPECT_THAT(odds, ElementsAre(1, 3, 5, 7));
  EXPECT_THAT(evens, ElementsAre(2, 4, 6));
}

TEST(MutatingTest, PartitionPoint) {
  const std::vector<int> initial = {1, 3, 5, 2, 4};
  auto middle = absl::c_partition_point(initial, IsOdd);
  EXPECT_EQ(2, *middle);
}

TEST(MutatingTest, CopyMiddle) {
  const std::vector<int> initial = {4, -1, -2, -3, 5};
  const std::list<int> input = {1, 2, 3};
  const std::vector<int> expected = {4, 1, 2, 3, 5};

  std::list<int> test_list(initial.begin(), initial.end());
  absl::c_copy(input, ++test_list.begin());
  EXPECT_EQ(std::list<int>(expected.begin(), expected.end()), test_list);

  std::vector<int> test_vector = initial;
  absl::c_copy(input, test_vector.begin() + 1);
  EXPECT_EQ(expected, test_vector);
}

TEST(MutatingTest, CopyFrontInserter) {
  const std::list<int> initial = {4, 5};
  const std::list<int> input = {1, 2, 3};
  const std::list<int> expected = {3, 2, 1, 4, 5};

  std::list<int> test_list = initial;
  absl::c_copy(input, std::front_inserter(test_list));
  EXPECT_EQ(expected, test_list);
}

TEST(MutatingTest, CopyBackInserter) {
  const std::vector<int> initial = {4, 5};
  const std::list<int> input = {1, 2, 3};
  const std::vector<int> expected = {4, 5, 1, 2, 3};

  std::list<int> test_list(initial.begin(), initial.end());
  absl::c_copy(input, std::back_inserter(test_list));
  EXPECT_EQ(std::list<int>(expected.begin(), expected.end()), test_list);

  std::vector<int> test_vector = initial;
  absl::c_copy(input, std::back_inserter(test_vector));
  EXPECT_EQ(expected, test_vector);
}

TEST(MutatingTest, CopyN) {
  const std::vector<int> initial = {1, 2, 3, 4, 5};
  const std::vector<int> expected = {1, 2};
  std::vector<int> actual;
  absl::c_copy_n(initial, 2, back_inserter(actual));
  EXPECT_EQ(expected, actual);
}

TEST(MutatingTest, CopyNWithNegativeN) {
#ifdef _LIBCPP_VERSION
  GTEST_SKIP() << "libc++ does not handle negative counts correctly";
#else
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0};
  absl::c_copy_n(input, -1, actual.begin());
  EXPECT_THAT(actual, ElementsAre(0, 0, 0));
#endif
}

TEST(MutatingTest, CopyToContainer) {
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0, 4, 5};
  absl::c_copy(input, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyToSpanRvalue) {
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0, 4, 5};
  absl::c_copy(input, absl::MakeSpan(actual));
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyNToContainer) {
  const std::vector<int> input = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}

TEST(MutatingTest, CopyNToSpanRvalue) {
  const std::vector<int> input = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, absl::MakeSpan(actual));
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}

TEST(MutatingTest, CopyNToContainerWithZeroN) {
  const std::vector<int> input = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 0, actual);
  EXPECT_THAT(actual, ElementsAre(0, 0, 0, 0, 0));
}

TEST(MutatingTest, CopyNToContainerWithNegativeN) {
#ifdef _LIBCPP_VERSION
  GTEST_SKIP() << "libc++ does not handle negative counts correctly";
#else
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0};
  absl::c_copy_n(input, -1, actual);
  EXPECT_THAT(actual, ElementsAre(0, 0, 0));
#endif
}

TEST(MutatingTest, CopyToDifferentContainerType) {
  const std::list<int> input = {1, 2, 3};
  std::array<int, 5> actual = {0, 0, 0, 4, 5};
  absl::c_copy(input, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyNToDifferentContainerType) {
  const std::list<int> input = {1, 2, 3, 4, 5};
  std::array<int, 5> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}

TEST(MutatingTest, CopyToCArray) {
  const std::vector<int> input = {1, 2, 3};
  int actual[5] = {0, 0, 0, 4, 5};
  absl::c_copy(input, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyNToCArray) {
  const std::vector<int> input = {1, 2, 3, 4, 5};
  int actual[5] = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}

TEST(MutatingTest, CopyFromCArray) {
  const int input[5] = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy(input, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyNFromCArray) {
  const int input[5] = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}

TEST(MutatingTest, CopyContainerWithNoSizeMethod) {
  const std::forward_list<int> input = {1, 2, 3};
  std::forward_list<int> actual = {0, 0, 0, 4, 5};
  absl::c_copy(input, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, CopyNContainerWithNoSizeMethod) {
  const std::forward_list<int> input = {1, 2, 3, 4, 5};
  std::forward_list<int> actual = {0, 0, 0, 0, 0};
  absl::c_copy_n(input, 2, actual);
  EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0));
}


bool IsHardened() {
  bool hardened = false;
  ABSL_HARDENING_ASSERT([&hardened]() {
    hardened = true;
    return true;
  }());
  return hardened;
}

TEST(MutatingTest, CopyToCArrayInvalidSize) {
  const std::vector<int> input = {1, 2, 3};
  int actual[2] = {0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy(input, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToCArrayInvalidSize) {
  const std::vector<int> input = {1, 2, 3};
  int actual[2] = {0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 3, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToCArrayNGreaterThanInput) {
  const std::vector<int> input = {1, 2, 3};
  int actual[4] = {0, 0, 0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 4, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyToContainerInvalidSize) {
  const std::list<int> input = {1, 2, 3, 4, 5};
  std::list<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy(input, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToContainerNGreaterThanInput) {
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 4, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToContainerNGreaterThanOutput) {
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 3, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyToForwardListInvalidSize) {
  const std::forward_list<int> input = {1, 2, 3, 4, 5};
  std::forward_list<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy(input, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToForwardListNGreaterThanInput) {
  const std::forward_list<int> input = {1, 2, 3};
  std::forward_list<int> actual = {0, 0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 4, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyNToForwardListNGreaterThanOutput) {
  const std::forward_list<int> input = {1, 2, 3};
  std::forward_list<int> actual = {0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_copy_n(input, 3, actual), "");
  }
#endif
}

TEST(MutatingTest, CopyIf) {
  const std::list<int> input = {1, 2, 3};
  std::vector<int> output;
  absl::c_copy_if(input, std::back_inserter(output),
                  [](int i) { return i != 2; });
  EXPECT_THAT(output, ElementsAre(1, 3));
}

TEST(MutatingTest, CopyBackward) {
  std::vector<int> actual = {1, 2, 3, 4, 5};
  std::vector<int> expected = {1, 2, 1, 2, 3};
  absl::c_copy_backward(absl::MakeSpan(actual.data(), 3), actual.end());
  EXPECT_EQ(expected, actual);
}

TEST(MutatingTest, Move) {
  std::vector<std::unique_ptr<int>> src;
  src.emplace_back(std::make_unique<int>(1));
  src.emplace_back(std::make_unique<int>(2));
  src.emplace_back(std::make_unique<int>(3));
  src.emplace_back(std::make_unique<int>(4));
  src.emplace_back(std::make_unique<int>(5));

  std::vector<std::unique_ptr<int>> dest = {};
  absl::c_move(src, std::back_inserter(dest));
  EXPECT_THAT(src, Each(IsNull()));
  EXPECT_THAT(dest, ElementsAre(Pointee(1), Pointee(2), Pointee(3), Pointee(4),
                                Pointee(5)));
}

TEST(MutatingTest, MoveBackward) {
  std::vector<std::unique_ptr<int>> actual;
  actual.emplace_back(std::make_unique<int>(1));
  actual.emplace_back(std::make_unique<int>(2));
  actual.emplace_back(std::make_unique<int>(3));
  actual.emplace_back(std::make_unique<int>(4));
  actual.emplace_back(std::make_unique<int>(5));
  auto subrange = absl::MakeSpan(actual.data(), 3);
  absl::c_move_backward(subrange, actual.end());
  EXPECT_THAT(actual, ElementsAre(IsNull(), IsNull(), Pointee(1), Pointee(2),
                                  Pointee(3)));
}

TEST(MutatingTest, MoveWithRvalue) {
  auto MakeRValueSrc = [] {
    std::vector<std::unique_ptr<int>> src;
    src.emplace_back(std::make_unique<int>(1));
    src.emplace_back(std::make_unique<int>(2));
    src.emplace_back(std::make_unique<int>(3));
    return src;
  };

  std::vector<std::unique_ptr<int>> dest = MakeRValueSrc();
  absl::c_move(MakeRValueSrc(), std::back_inserter(dest));
  EXPECT_THAT(dest, ElementsAre(Pointee(1), Pointee(2), Pointee(3), Pointee(1),
                                Pointee(2), Pointee(3)));
}

TEST(MutatingTest, MoveToContainer) {
  std::vector<std::unique_ptr<int>> input;
  input.push_back(std::make_unique<int>(1));
  input.push_back(std::make_unique<int>(2));
  input.push_back(std::make_unique<int>(3));

  std::vector<std::unique_ptr<int>> actual(5);
  absl::c_move(input, actual);

  EXPECT_EQ(input[0], nullptr);
  EXPECT_EQ(input[1], nullptr);
  EXPECT_EQ(input[2], nullptr);

  ASSERT_NE(actual[0], nullptr);
  EXPECT_EQ(*actual[0], 1);
  ASSERT_NE(actual[1], nullptr);
  EXPECT_EQ(*actual[1], 2);
  ASSERT_NE(actual[2], nullptr);
  EXPECT_EQ(*actual[2], 3);
  EXPECT_EQ(actual[3], nullptr);
}

TEST(MutatingTest, MoveToSpanRvalue) {
  std::vector<std::unique_ptr<int>> input;
  input.push_back(std::make_unique<int>(1));
  input.push_back(std::make_unique<int>(2));
  input.push_back(std::make_unique<int>(3));

  std::vector<std::unique_ptr<int>> actual(5);
  absl::c_move(input, absl::MakeSpan(actual));

  EXPECT_EQ(input[0], nullptr);
  EXPECT_EQ(input[1], nullptr);
  EXPECT_EQ(input[2], nullptr);

  ASSERT_NE(actual[0], nullptr);
  EXPECT_EQ(*actual[0], 1);
  ASSERT_NE(actual[1], nullptr);
  EXPECT_EQ(*actual[1], 2);
  ASSERT_NE(actual[2], nullptr);
  EXPECT_EQ(*actual[2], 3);
  EXPECT_EQ(actual[3], nullptr);
}

TEST(MutatingTest, MoveToDifferentContainerType) {
  std::list<std::unique_ptr<int>> input;
  input.push_back(std::make_unique<int>(1));
  input.push_back(std::make_unique<int>(2));

  std::array<std::unique_ptr<int>, 3> actual;
  absl::c_move(input, actual);

  EXPECT_EQ(input.front(), nullptr);
  ASSERT_NE(actual[0], nullptr);
  EXPECT_EQ(*actual[0], 1);
}

TEST(MutatingTest, MoveToCArray) {
  std::vector<std::unique_ptr<int>> input;
  input.push_back(std::make_unique<int>(1));
  input.push_back(std::make_unique<int>(2));

  std::unique_ptr<int> actual[3];
  absl::c_move(input, actual);

  EXPECT_EQ(input.front(), nullptr);
  ASSERT_NE(actual[0], nullptr);
  EXPECT_EQ(*actual[0], 1);
}

TEST(MutatingTest, MoveFromCArray) {
  std::unique_ptr<int> input[2];
  input[0] = std::make_unique<int>(1);
  input[1] = std::make_unique<int>(2);

  std::vector<std::unique_ptr<int>> actual(3);
  absl::c_move(input, actual);

  EXPECT_EQ(input[0], nullptr);
  ASSERT_NE(actual[0], nullptr);
  EXPECT_EQ(*actual[0], 1);
}


TEST(MutatingTest, MoveToCArrayInvalidSize) {
  std::vector<int> input = {1, 2, 3};
  int actual[2] = {0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_move(input, actual), "");
  }
#endif
}

TEST(MutatingTest, MoveToContainerInvalidSize) {
  std::list<int> input = {1, 2, 3, 4, 5};
  std::list<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_move(input, actual), "");
  }
#endif
}

TEST(MutatingTest, MoveToForwardListInvalidSize) {
  std::forward_list<int> input = {1, 2, 3, 4, 5};
  std::forward_list<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_move(input, actual), "");
  }
#endif
}

TEST(MutatingTest, SwapRanges) {
  std::vector<int> odds = {2, 4, 6};
  std::vector<int> evens = {1, 3, 5};
  absl::c_swap_ranges(odds, evens);
  EXPECT_THAT(odds, ElementsAre(1, 3, 5));
  EXPECT_THAT(evens, ElementsAre(2, 4, 6));

  odds.pop_back();
  absl::c_swap_ranges(odds, evens);
  EXPECT_THAT(odds, ElementsAre(2, 4));
  EXPECT_THAT(evens, ElementsAre(1, 3, 6));

  absl::c_swap_ranges(evens, odds);
  EXPECT_THAT(odds, ElementsAre(1, 3));
  EXPECT_THAT(evens, ElementsAre(2, 4, 6));
}

TEST_F(NonMutatingTest, Transform) {
  std::vector<int> x{0, 2, 4}, y, z;
  auto end = absl::c_transform(x, back_inserter(y), std::negate<int>());
  EXPECT_EQ(std::vector<int>({0, -2, -4}), y);
  *end = 7;
  EXPECT_EQ(std::vector<int>({0, -2, -4, 7}), y);

  y = {1, 3, 0};
  end = absl::c_transform(x, y, back_inserter(z), std::plus<int>());
  EXPECT_EQ(std::vector<int>({1, 5, 4}), z);
  *end = 7;
  EXPECT_EQ(std::vector<int>({1, 5, 4, 7}), z);

  std::vector<int> x2{1, 2, 3};
  std::vector<int> y2{10, 20, 30};
  std::vector<int> z2(3);
  auto out_it = z2.begin();
  absl::c_transform(x2, y2, out_it, std::plus<int>());
  // The caller's iterator should not be modified.
  EXPECT_EQ(out_it, z2.begin());
  EXPECT_EQ(z2, std::vector<int>({11, 22, 33}));
}

TEST(MutatingTest, TransformToContainer) {
  const std::vector<int> input = {1, 2, 3};
  std::vector<int> actual = {0, 0, 0, 4, 5};
  absl::c_transform(input, actual, [](int x) { return x * 2; });
  EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5));
}

TEST(MutatingTest, BinaryTransformToContainer) {
  {
    const std::vector<int> input1 = {1, 2, 3};
    const std::vector<int> input2 = {10, 20, 30};
    std::vector<int> actual = {0, 0, 0, 4, 5};
    absl::c_transform(input1, input2, actual, std::plus<int>());
    EXPECT_THAT(actual, ElementsAre(11, 22, 33, 4, 5));
  }
  {
    const std::vector<int> input1 = {1, 2, 3, 4};
    const std::vector<int> input2 = {10, 20};
    std::vector<int> actual = {0, 0, 0, 4, 5};
    absl::c_transform(input1, input2, actual, std::plus<int>());
    EXPECT_THAT(actual, ElementsAre(11, 22, 0, 4, 5));
  }
  {
    const std::vector<int> input1 = {1, 2};
    const std::vector<int> input2 = {10, 20, 30, 40};
    std::vector<int> actual = {0, 0, 0, 4, 5};
    absl::c_transform(input1, input2, actual, std::plus<int>());
    EXPECT_THAT(actual, ElementsAre(11, 22, 0, 4, 5));
  }
}

TEST(MutatingTest, TransformToDifferentContainerType) {
  const std::list<int> input = {1, 2, 3};
  std::array<int, 5> actual = {0, 0, 0, 4, 5};
  absl::c_transform(input, actual, [](int x) { return x * 2; });
  EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5));
}

TEST(MutatingTest, TransformToCArray) {
  const std::vector<int> input = {1, 2, 3};
  int actual[5] = {0, 0, 0, 4, 5};
  absl::c_transform(input, actual, [](int x) { return x * 2; });
  EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5));
}

TEST(MutatingTest, TransformFromCArray) {
  const int input[5] = {1, 2, 3, 4, 5};
  std::vector<int> actual = {0, 0, 0, 0, 0};
  absl::c_transform(input, actual, [](int x) { return x * 2; });
  EXPECT_THAT(actual, ElementsAre(2, 4, 6, 8, 10));
}

TEST(MutatingTest, TransformToCArrayInvalidSize) {
  const std::vector<int> input = {1, 2, 3};
  int actual[2] = {0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input, actual, [](int x) { return x * 2; }),
                 "");
  }
#endif
}

TEST(MutatingTest, BinaryTransformToCArrayInvalidSize) {
  const std::vector<int> input1 = {1, 2, 3};
  const std::vector<int> input2 = {10, 20, 30};
  int actual[2] = {0, 0};
  (void)actual;
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()),
                 "");
  }
#endif
}

TEST(MutatingTest, TransformToContainerInvalidSize) {
  const std::list<int> input = {1, 2, 3, 4, 5};
  std::list<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input, actual, [](int x) { return x * 2; }),
                 "");
  }
#endif
}

TEST(MutatingTest, BinaryTransformToContainerInvalidSize) {
  const std::vector<int> input1 = {1, 2, 3, 4, 5};
  const std::vector<int> input2 = {10, 20, 30, 40, 50};
  std::vector<int> actual = {0, 0, 0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()),
                 "");
  }
#endif
}

TEST(MutatingTest, BinaryTransformInput2InvalidSize) {
  const std::vector<int> input1 = {1, 2, 3};
  const std::vector<int> input2 = {10, 20};
  std::vector<int> actual = {0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()),
                 "");
  }
#endif
}

TEST(MutatingTest, BinaryTransformInput1InvalidSize) {
  const std::vector<int> input1 = {1, 2};
  const std::vector<int> input2 = {10, 20, 30};
  std::vector<int> actual = {0};
#if GTEST_HAS_DEATH_TEST
  if (IsHardened()) {
    EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()),
                 "");
  }
#endif
}

TEST(MutatingTest, Replace) {
  const std::vector<int> initial = {1, 2, 3, 1, 4, 5};
  const std::vector<int> expected = {4, 2, 3, 4, 4, 5};

  std::vector<int> test_vector = initial;
  absl::c_replace(test_vector, 1, 4);
  EXPECT_EQ(expected, test_vector);

  std::list<int> test_list(initial.begin(), initial.end());
  absl::c_replace(test_list, 1, 4);
  EXPECT_EQ(std::list<int>(expected.begin(), expected.end()), test_list);
}

TEST(MutatingTest, ReplaceIf) {
  std::vector<int> actual = {1, 2, 3, 4, 5};
  const std::vector<int> expected = {0, 2, 0, 4, 0};

  absl::c_replace_if(actual, IsOdd, 0);
  EXPECT_EQ(expected, actual);
}

TEST(MutatingTest, ReplaceCopy) {
  const std::vector<int> initial = {1, 2, 3, 1, 4, 5};
  const std::vector<int> expected = {4, 2, 3, 4, 4, 5};

  std::vector<int> actual;
  absl::c_replace_copy(initial, back_inserter(actual), 1, 4);
  EXPECT_EQ(expected, actual);
}

TEST(MutatingTest, Sort) {
  std::vector<int> test_vector = {2, 3, 1, 4};
  absl::c_sort(test_vector);
  EXPECT_THAT(test_vector, ElementsAre(1, 2, 3, 4));
}

TEST(MutatingTest, SortWithPredicate) {
  std::vector<int> test_vector = {2, 3, 1, 4};
  absl::c_sort(test_vector, std::greater<int>());
  EXPECT_THAT(test_vector, ElementsAre(4, 3, 2, 1));
}

TEST(MutatingTest, SortTemporarySpan) {
  std::vector<int> test_vector = {2, 3, 1, 4};
  absl::c_sort(absl::MakeSpan(test_vector));
  EXPECT_THAT(test_vector, ElementsAre(1, 2, 3, 4));
}

TEST(MutatingTest, SortTemporarySpanWithPredicate) {
  std::vector<int> test_vector = {2, 3, 1, 4};
  absl::c_sort(absl::MakeSpan(test_vector), std::greater<int>());
  EXPECT_THAT(test_vector, ElementsAre(4, 3, 2, 1));
}

// For absl::c_stable_sort tests. Needs an operator< that does not cover all
// fields so that the test can check the sort preserves order of equal elements.
struct Element {
  int key;
  int value;
  friend bool operator<(const Element& e1, const Element& e2) {
    return e1.key < e2.key;
  }
  // Make gmock print useful diagnostics.
  friend std::ostream& operator<<(std::ostream& o, const Element& e) {
    return o << "{" << e.key << ", " << e.value << "}";
  }
};

MATCHER_P2(IsElement, key, value, "") {
  return arg.key == key && arg.value == value;
}

TEST(MutatingTest, StableSort) {
  std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}};
  absl::c_stable_sort(test_vector);
  EXPECT_THAT(test_vector,
              ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1),
                          IsElement(2, 0), IsElement(2, 2)));
}

TEST(MutatingTest, StableSortWithPredicate) {
  std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}};
  absl::c_stable_sort(test_vector, [](const Element& e1, const Element& e2) {
    return e2 < e1;
  });
  EXPECT_THAT(test_vector,
              ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2),
                          IsElement(1, 1), IsElement(1, 0)));
}

TEST(MutatingTest, StableSortTemporarySpan) {
  std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}};
  absl::c_stable_sort(absl::MakeSpan(test_vector));
  EXPECT_THAT(test_vector,
              ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1),
                          IsElement(2, 0), IsElement(2, 2)));
}

TEST(MutatingTest, StableSortTemporarySpanWithPredicate) {
  std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}};
  absl::c_stable_sort(
      absl::MakeSpan(test_vector),
      [](const Element& e1, const Element& e2) { return e2 < e1; });
  EXPECT_THAT(test_vector,
              ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2),
                          IsElement(1, 1), IsElement(1, 0)));
}

TEST(MutatingTest, ReplaceCopyIf) {
  const std::vector<int> initial = {1, 2, 3, 4, 5};
  const std::vector<int> expected = {0, 2, 0, 4, 0};

  std::vector<int> actual;
  absl::c_replace_copy_if(initial, back_inserter(actual), IsOdd, 0);
  EXPECT_EQ(expected, actual);
}

TEST(MutatingTest, Fill) {
  std::vector<int> actual(5);
  absl::c_fill(actual, 1);
  EXPECT_THAT(actual, ElementsAre(1, 1, 1, 1, 1));
}

TEST(MutatingTest, FillWithRvalue) {
  std::vector<int> actual(5);
  absl::c_fill(absl::MakeSpan(actual), 1);
  EXPECT_THAT(actual, ElementsAre(1, 1, 1, 1, 1));
}

TEST(MutatingTest, FillN) {
  std::vector<int> actual(5, 0);
  absl::c_fill_n(actual, 2, 1);
  EXPECT_THAT(actual, ElementsAre(1, 1, 0, 0, 0));
}

TEST(MutatingTest, FillNWithRvalue) {
  std::vector<int> actual(5, 0);
  absl::c_fill_n(absl::MakeSpan(actual), 2, 1);
  EXPECT_THAT(actual, ElementsAre(1, 1, 0, 0, 0));
}

TEST(MutatingTest, Generate) {
  std::vector<int> actual(5);
  int x = 0;
  absl::c_generate(actual, [&x]() { return ++x; });
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, GenerateN) {
  std::vector<int> actual(5, 0);
  int x = 0;
  absl::c_generate_n(actual, 3, [&x]() { return ++x; });
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 0, 0));
}

TEST(MutatingTest, RemoveCopy) {
  std::vector<int> actual;
  absl::c_remove_copy(std::vector<int>{1, 2, 3}, back_inserter(actual), 2);
  EXPECT_THAT(actual, ElementsAre(1, 3));
}

TEST(MutatingTest, RemoveCopyIf) {
  std::vector<int> actual;
  absl::c_remove_copy_if(std::vector<int>{1, 2, 3}, back_inserter(actual),
                         IsOdd);
  EXPECT_THAT(actual, ElementsAre(2));
}

TEST(MutatingTest, UniqueCopy) {
  std::vector<int> actual;
  absl::c_unique_copy(std::vector<int>{1, 2, 2, 2, 3, 3, 2},
                      back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 2));
}

TEST(MutatingTest, UniqueCopyWithPredicate) {
  std::vector<int> actual;
  absl::c_unique_copy(std::vector<int>{1, 2, 3, -1, -2, -3, 1},
                      back_inserter(actual),
                      [](int x, int y) { return (x < 0) == (y < 0); });
  EXPECT_THAT(actual, ElementsAre(1, -1, 1));
}

TEST(MutatingTest, Reverse) {
  std::vector<int> test_vector = {1, 2, 3, 4};
  absl::c_reverse(test_vector);
  EXPECT_THAT(test_vector, ElementsAre(4, 3, 2, 1));

  std::list<int> test_list = {1, 2, 3, 4};
  absl::c_reverse(test_list);
  EXPECT_THAT(test_list, ElementsAre(4, 3, 2, 1));
}

TEST(MutatingTest, ReverseCopy) {
  std::vector<int> actual;
  absl::c_reverse_copy(std::vector<int>{1, 2, 3, 4}, back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(4, 3, 2, 1));
}

TEST(MutatingTest, Rotate) {
  std::vector<int> actual = {1, 2, 3, 4};
  auto it = absl::c_rotate(actual, actual.begin() + 2);
  EXPECT_THAT(actual, testing::ElementsAreArray({3, 4, 1, 2}));
  EXPECT_EQ(*it, 1);
}

TEST(MutatingTest, RotateCopy) {
  std::vector<int> initial = {1, 2, 3, 4};
  std::vector<int> actual;
  auto end =
      absl::c_rotate_copy(initial, initial.begin() + 2, back_inserter(actual));
  *end = 5;
  EXPECT_THAT(actual, ElementsAre(3, 4, 1, 2, 5));
}

TEST(MutatingTest, Shuffle) {
  std::vector<int> actual = {1, 2, 3, 4, 5};
  absl::c_shuffle(actual, absl::InsecureBitGen());
  EXPECT_THAT(actual, UnorderedElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, Sample) {
  std::vector<int> actual;
  absl::c_sample(std::vector<int>{1, 2, 3, 4, 5}, std::back_inserter(actual), 3,
                 absl::InsecureBitGen());
  EXPECT_THAT(actual, IsSubsetOf({1, 2, 3, 4, 5}));
  EXPECT_THAT(actual, SizeIs(3));
}

TEST(MutatingTest, PartialSort) {
  std::vector<int> sequence{5, 3, 42, 0};
  absl::c_partial_sort(sequence, sequence.begin() + 2);
  EXPECT_THAT(absl::MakeSpan(sequence.data(), 2), ElementsAre(0, 3));
  absl::c_partial_sort(sequence, sequence.begin() + 2, std::greater<int>());
  EXPECT_THAT(absl::MakeSpan(sequence.data(), 2), ElementsAre(42, 5));
}

TEST(MutatingTest, PartialSortCopy) {
  const std::vector<int> initial = {5, 3, 42, 0};
  std::vector<int> actual(2);
  absl::c_partial_sort_copy(initial, actual);
  EXPECT_THAT(actual, ElementsAre(0, 3));
  absl::c_partial_sort_copy(initial, actual, std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(42, 5));
}

TEST(MutatingTest, Merge) {
  std::vector<int> actual;
  absl::c_merge(std::vector<int>{1, 3, 5}, std::vector<int>{2, 4},
                back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, MergeWithComparator) {
  std::vector<int> actual;
  absl::c_merge(std::vector<int>{5, 3, 1}, std::vector<int>{4, 2},
                back_inserter(actual), std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(5, 4, 3, 2, 1));
}

TEST(MutatingTest, InplaceMerge) {
  std::vector<int> actual = {1, 3, 5, 2, 4};
  absl::c_inplace_merge(actual, actual.begin() + 3);
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 4, 5));
}

TEST(MutatingTest, InplaceMergeWithComparator) {
  std::vector<int> actual = {5, 3, 1, 4, 2};
  absl::c_inplace_merge(actual, actual.begin() + 3, std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(5, 4, 3, 2, 1));
}

class SetOperationsTest : public testing::Test {
 protected:
  std::vector<int> a_ = {1, 2, 3};
  std::vector<int> b_ = {1, 3, 5};

  std::vector<int> a_reversed_ = {3, 2, 1};
  std::vector<int> b_reversed_ = {5, 3, 1};
};

TEST_F(SetOperationsTest, SetUnion) {
  std::vector<int> actual;
  absl::c_set_union(a_, b_, back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(1, 2, 3, 5));
}

TEST_F(SetOperationsTest, SetUnionWithComparator) {
  std::vector<int> actual;
  absl::c_set_union(a_reversed_, b_reversed_, back_inserter(actual),
                    std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(5, 3, 2, 1));
}

TEST_F(SetOperationsTest, SetIntersection) {
  std::vector<int> actual;
  absl::c_set_intersection(a_, b_, back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(1, 3));
}

TEST_F(SetOperationsTest, SetIntersectionWithComparator) {
  std::vector<int> actual;
  absl::c_set_intersection(a_reversed_, b_reversed_, back_inserter(actual),
                           std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(3, 1));
}

TEST_F(SetOperationsTest, SetDifference) {
  std::vector<int> actual;
  absl::c_set_difference(a_, b_, back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(2));
}

TEST_F(SetOperationsTest, SetDifferenceWithComparator) {
  std::vector<int> actual;
  absl::c_set_difference(a_reversed_, b_reversed_, back_inserter(actual),
                         std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(2));
}

TEST_F(SetOperationsTest, SetSymmetricDifference) {
  std::vector<int> actual;
  absl::c_set_symmetric_difference(a_, b_, back_inserter(actual));
  EXPECT_THAT(actual, ElementsAre(2, 5));
}

TEST_F(SetOperationsTest, SetSymmetricDifferenceWithComparator) {
  std::vector<int> actual;
  absl::c_set_symmetric_difference(a_reversed_, b_reversed_,
                                   back_inserter(actual), std::greater<int>());
  EXPECT_THAT(actual, ElementsAre(5, 2));
}

TEST(HeapOperationsTest, WithoutComparator) {
  std::vector<int> heap = {1, 2, 3};
  EXPECT_FALSE(absl::c_is_heap(heap));
  absl::c_make_heap(heap);
  EXPECT_TRUE(absl::c_is_heap(heap));
  heap.push_back(4);
  EXPECT_EQ(3, absl::c_is_heap_until(heap) - heap.begin());
  absl::c_push_heap(heap);
  EXPECT_EQ(4, heap[0]);
  absl::c_pop_heap(heap);
  EXPECT_EQ(4, heap[3]);
  absl::c_make_heap(heap);
  absl::c_sort_heap(heap);
  EXPECT_THAT(heap, ElementsAre(1, 2, 3, 4));
  EXPECT_FALSE(absl::c_is_heap(heap));
}

TEST(HeapOperationsTest, WithComparator) {
  using greater = std::greater<int>;
  std::vector<int> heap = {3, 2, 1};
  EXPECT_FALSE(absl::c_is_heap(heap, greater()));
  absl::c_make_heap(heap, greater());
  EXPECT_TRUE(absl::c_is_heap(heap, greater()));
  heap.push_back(0);
  EXPECT_EQ(3, absl::c_is_heap_until(heap, greater()) - heap.begin());
  absl::c_push_heap(heap, greater());
  EXPECT_EQ(0, heap[0]);
  absl::c_pop_heap(heap, greater());
  EXPECT_EQ(0, heap[3]);
  absl::c_make_heap(heap, greater());
  absl::c_sort_heap(heap, greater());
  EXPECT_THAT(heap, ElementsAre(3, 2, 1, 0));
  EXPECT_FALSE(absl::c_is_heap(heap, greater()));
}

TEST(MutatingTest, PermutationOperations) {
  std::vector<int> initial = {1, 2, 3, 4};
  std::vector<int> permuted = initial;

  absl::c_next_permutation(permuted);
  EXPECT_TRUE(absl::c_is_permutation(initial, permuted));
  EXPECT_TRUE(absl::c_is_permutation(initial, permuted, std::equal_to<int>()));

  std::vector<int> permuted2 = initial;
  absl::c_prev_permutation(permuted2, std::greater<int>());
  EXPECT_EQ(permuted, permuted2);

  absl::c_prev_permutation(permuted);
  EXPECT_EQ(initial, permuted);
}

#if defined(ABSL_INTERNAL_CPLUSPLUS_LANG) && \
    ABSL_INTERNAL_CPLUSPLUS_LANG >= 201703L

TEST(ConstexprTest, Distance) {
  // Works at compile time with constexpr containers.
  static_assert(absl::c_distance(std::array<int, 3>()) == 3);
}

TEST(ConstexprTest, MinElement) {
  constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(*absl::c_min_element(kArray) == 1);
}

TEST(ConstexprTest, MinElementWithPredicate) {
  constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(*absl::c_min_element(kArray, std::greater<int>()) == 3);
}

TEST(ConstexprTest, MaxElement) {
  constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(*absl::c_max_element(kArray) == 3);
}

TEST(ConstexprTest, MaxElementWithPredicate) {
  constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(*absl::c_max_element(kArray, std::greater<int>()) == 1);
}

TEST(ConstexprTest, MinMaxElement) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  constexpr auto kMinMaxPair = absl::c_minmax_element(kArray);
  static_assert(*kMinMaxPair.first == 1);
  static_assert(*kMinMaxPair.second == 3);
}

TEST(ConstexprTest, MinMaxElementWithPredicate) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  constexpr auto kMinMaxPair =
      absl::c_minmax_element(kArray, std::greater<int>());
  static_assert(*kMinMaxPair.first == 3);
  static_assert(*kMinMaxPair.second == 1);
}
#endif  // defined(ABSL_INTERNAL_CPLUSPLUS_LANG) &&
        //  ABSL_INTERNAL_CPLUSPLUS_LANG >= 201703L

#if defined(ABSL_INTERNAL_CPLUSPLUS_LANG) && \
    ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L

TEST(ConstexprTest, LinearSearch) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_linear_search(kArray, 3));
  static_assert(!absl::c_linear_search(kArray, 4));
}

TEST(ConstexprTest, AllOf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(!absl::c_all_of(kArray, [](int x) { return x > 1; }));
  static_assert(absl::c_all_of(kArray, [](int x) { return x > 0; }));
}

TEST(ConstexprTest, AnyOf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_any_of(kArray, [](int x) { return x > 2; }));
  static_assert(!absl::c_any_of(kArray, [](int x) { return x > 5; }));
}

TEST(ConstexprTest, NoneOf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(!absl::c_none_of(kArray, [](int x) { return x > 2; }));
  static_assert(absl::c_none_of(kArray, [](int x) { return x > 5; }));
}

TEST(ConstexprTest, ForEach) {
  static constexpr std::array<int, 3> kArray = [] {
    std::array<int, 3> array = {1, 2, 3};
    absl::c_for_each(array, [](int& x) { x += 1; });
    return array;
  }();
  static_assert(kArray == std::array{2, 3, 4});
}

TEST(ConstexprTest, Find) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_find(kArray, 1) == kArray.begin());
  static_assert(absl::c_find(kArray, 4) == kArray.end());
}

TEST(ConstexprTest, Contains) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_contains(kArray, 1));
  static_assert(!absl::c_contains(kArray, 4));
}

TEST(ConstexprTest, FindIf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_find_if(kArray, [](int x) { return x > 2; }) ==
                kArray.begin() + 2);
  static_assert(absl::c_find_if(kArray, [](int x) { return x > 5; }) ==
                kArray.end());
}

TEST(ConstexprTest, FindIfNot) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_find_if_not(kArray, [](int x) { return x > 1; }) ==
                kArray.begin());
  static_assert(absl::c_find_if_not(kArray, [](int x) { return x > 0; }) ==
                kArray.end());
}

TEST(ConstexprTest, FindEnd) {
  static constexpr std::array<int, 5> kHaystack = {1, 2, 3, 2, 3};
  static constexpr std::array<int, 2> kNeedle = {2, 3};
  static_assert(absl::c_find_end(kHaystack, kNeedle) == kHaystack.begin() + 3);
}

TEST(ConstexprTest, FindFirstOf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_find_first_of(kArray, kArray) == kArray.begin());
}

TEST(ConstexprTest, AdjacentFind) {
  static constexpr std::array<int, 4> kArray = {1, 2, 2, 3};
  static_assert(absl::c_adjacent_find(kArray) == kArray.begin() + 1);
}

TEST(ConstexprTest, AdjacentFindWithPredicate) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_adjacent_find(kArray, std::less<int>()) ==
                kArray.begin());
}

TEST(ConstexprTest, Count) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_count(kArray, 1) == 1);
  static_assert(absl::c_count(kArray, 2) == 1);
  static_assert(absl::c_count(kArray, 3) == 1);
  static_assert(absl::c_count(kArray, 4) == 0);
}

TEST(ConstexprTest, CountIf) {
  static constexpr std::array<int, 3> kArray = {1, 2, 3};
  static_assert(absl::c_count_if(kArray, [](int x) { return x > 0; }) == 3);
  static_assert(absl::c_count_if(kArray, [](int x) { return x > 1; }) == 2);
}

TEST(ConstexprTest, Mismatch) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_mismatch(kArray1, kArray2) ==
                std::pair{kArray1.end(), kArray2.end()});
  static_assert(absl::c_mismatch(kArray1, kArray3) ==
                std::pair{kArray1.begin(), kArray3.begin()});
}

TEST(ConstexprTest, MismatchWithPredicate) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_mismatch(kArray1, kArray2, std::not_equal_to<int>()) ==
                std::pair{kArray1.begin(), kArray2.begin()});
  static_assert(absl::c_mismatch(kArray1, kArray3, std::not_equal_to<int>()) ==
                std::pair{kArray1.end(), kArray3.end()});
}

TEST(ConstexprTest, Equal) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_equal(kArray1, kArray2));
  static_assert(!absl::c_equal(kArray1, kArray3));
}

TEST(ConstexprTest, EqualWithPredicate) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(!absl::c_equal(kArray1, kArray2, std::not_equal_to<int>()));
  static_assert(absl::c_equal(kArray1, kArray3, std::not_equal_to<int>()));
}

TEST(ConstexprTest, IsPermutation) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {3, 2, 1};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_is_permutation(kArray1, kArray2));
  static_assert(!absl::c_is_permutation(kArray1, kArray3));
}

TEST(ConstexprTest, IsPermutationWithPredicate) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {3, 2, 1};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_is_permutation(kArray1, kArray2, std::equal_to<int>()));
  static_assert(
      !absl::c_is_permutation(kArray1, kArray3, std::equal_to<int>()));
}

TEST(ConstexprTest, Search) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_search(kArray1, kArray2) == kArray1.begin());
  static_assert(absl::c_search(kArray1, kArray3) == kArray1.end());
}

TEST(ConstexprTest, SearchWithPredicate) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_search(kArray1, kArray2, std::not_equal_to<int>()) ==
                kArray1.end());
  static_assert(absl::c_search(kArray1, kArray3, std::not_equal_to<int>()) ==
                kArray1.begin());
}

TEST(ConstexprTest, ContainsSubrange) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(absl::c_contains_subrange(kArray1, kArray2));
  static_assert(!absl::c_contains_subrange(kArray1, kArray3));
}

TEST(ConstexprTest, ContainsSubrangeWithPredicate) {
  static constexpr std::array<int, 3> kArray1 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray2 = {1, 2, 3};
  static constexpr std::array<int, 3> kArray3 = {2, 3, 4};
  static_assert(
      !absl::c_contains_subrange(kArray1, kArray2, std::not_equal_to<>()));
  static_assert(
      absl::c_contains_subrange(kArray1, kArray3, std::not_equal_to<>()));
}

TEST(ConstexprTest, SearchN) {
  static constexpr std::array<int, 4> kArray = {1, 2, 2, 3};
  static_assert(absl::c_search_n(kArray, 1, 1) == kArray.begin());
  static_assert(absl::c_search_n(kArray, 2, 2) == kArray.begin() + 1);
  static_assert(absl::c_search_n(kArray, 1, 4) == kArray.end());
}

TEST(ConstexprTest, SearchNWithPredicate) {
  static constexpr std::array<int, 4> kArray = {1, 2, 2, 3};
  static_assert(absl::c_search_n(kArray, 1, 1, std::not_equal_to<int>()) ==
                kArray.begin() + 1);
  static_assert(absl::c_search_n(kArray, 2, 2, std::not_equal_to<int>()) ==
                kArray.end());
  static_assert(absl::c_search_n(kArray, 1, 4, std::not_equal_to<int>()) ==
                kArray.begin());
}

TEST(ConstexprTest, Copy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayCopy = [] {
    std::array<int, 3> array;
    absl::c_copy(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayCopy == kArray);
}

TEST(ConstexprTest, CopyN) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayCopy = [] {
    std::array<int, 2> array;
    absl::c_copy_n(kArray, 2, array.begin());
    return array;
  }();
  static_assert(kArrayCopy == std::array{1, 2});
}

TEST(ConstexprTest, CopyIf) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr auto kArrayCopy = [] {
    std::array<int, 3> array;
    absl::c_copy_if(kArray, array.begin(), [](int x) { return x > 1; });
    return array;
  }();
  static_assert(kArrayCopy == std::array{2, 3, 4});
}

TEST(ConstexprTest, CopyBackward) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayCopy = [] {
    std::array<int, 3> array;
    absl::c_copy_backward(kArray, array.end());
    return array;
  }();
  static_assert(kArrayCopy == kArray);
}

TEST(ConstexprTest, Move) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayMove = [] {
    std::array<int, 3> array;
    absl::c_move(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayMove == kArray);
}

TEST(ConstexprTest, MoveBackward) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayMove = [] {
    std::array<int, 3> array;
    absl::c_move_backward(kArray, array.end());
    return array;
  }();
  static_assert(kArrayMove == kArray);
}

TEST(ConstexprTest, SwapRanges) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {4, 5, 6};

  static constexpr auto kSwapped = [] {
    std::array arr1 = kArray1;
    std::array arr2 = kArray2;
    absl::c_swap_ranges(arr1, arr2);
    return std::make_pair(arr1, arr2);
  }();

  static_assert(kSwapped.first == kArray2);
  static_assert(kSwapped.second == kArray1);
}

TEST(ConstexprTest, Transform) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayTransform = [] {
    std::array<int, 3> array;
    absl::c_transform(kArray, array.begin(), [](int x) { return x + 1; });
    return array;
  }();
  static_assert(kArrayTransform == std::array{2, 3, 4});
}

TEST(ConstexprTest, Replace) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReplace = [] {
    std::array array = kArray;
    absl::c_replace(array, 1, 4);
    return array;
  }();
  static_assert(kArrayReplace == std::array{4, 2, 3});
}

TEST(ConstexprTest, ReplaceIf) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReplaceIf = [] {
    std::array array = kArray;
    absl::c_replace_if(array, [](int x) { return x == 1; }, 4);
    return array;
  }();
  static_assert(kArrayReplaceIf == std::array{4, 2, 3});
}

TEST(ConstexprTest, ReplaceCopy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReplaceCopy = [] {
    std::array<int, 3> array;
    absl::c_replace_copy(kArray, array.begin(), 1, 4);
    return array;
  }();
  static_assert(kArrayReplaceCopy == std::array{4, 2, 3});
}

TEST(ConstexprTest, ReplaceCopyIf) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReplaceCopyIf = [] {
    std::array<int, 3> array;
    absl::c_replace_copy_if(
        kArray, array.begin(), [](int x) { return x == 1; }, 4);
    return array;
  }();
  static_assert(kArrayReplaceCopyIf == std::array{4, 2, 3});
}

TEST(ConstexprTest, Fill) {
  static constexpr auto kArrayFill = [] {
    std::array<int, 3> array;
    absl::c_fill(array, 4);
    return array;
  }();
  static_assert(kArrayFill == std::array{4, 4, 4});
}

TEST(ConstexprTest, FillN) {
  static constexpr auto kArrayFillN = [] {
    std::array array = {0, 0, 0};
    absl::c_fill_n(array, 2, 4);
    return array;
  }();
  static_assert(kArrayFillN == std::array{4, 4, 0});
}

TEST(ConstexprTest, Generate) {
  static constexpr auto kArrayGenerate = [] {
    std::array<int, 3> array;
    absl::c_generate(array, []() { return 4; });
    return array;
  }();
  static_assert(kArrayGenerate == std::array{4, 4, 4});
}

TEST(ConstexprTest, GenerateN) {
  static constexpr auto kArrayGenerateN = [] {
    std::array array = {0, 0, 0};
    absl::c_generate_n(array, 2, []() { return 4; });
    return array;
  }();
  static_assert(kArrayGenerateN == std::array{4, 4, 0});
}

TEST(ConstexprTest, RemoveCopy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayRemoveCopy = [] {
    std::array<int, 2> array;
    absl::c_remove_copy(kArray, array.begin(), 1);
    return array;
  }();
  static_assert(kArrayRemoveCopy == std::array{2, 3});
}

TEST(ConstexprTest, RemoveCopyIf) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayRemoveCopyIf = [] {
    std::array<int, 2> array;
    absl::c_remove_copy_if(kArray, array.begin(), [](int x) { return x == 1; });
    return array;
  }();
  static_assert(kArrayRemoveCopyIf == std::array{2, 3});
}

TEST(ConstexprTest, UniqueCopy) {
  static constexpr std::array kArray = {1, 2, 2, 3};
  static constexpr auto kArrayUniqueCopy = [] {
    std::array<int, 3> array;
    absl::c_unique_copy(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayUniqueCopy == std::array{1, 2, 3});
}

TEST(ConstexprTest, UniqueCopyWithPredicate) {
  static constexpr std::array kArray = {1, 2, 2, 3};
  static constexpr auto kArrayUniqueCopy = [] {
    std::array<int, 3> array;
    absl::c_unique_copy(kArray, array.begin(), std::equal_to<>());
    return array;
  }();
  static_assert(kArrayUniqueCopy == std::array{1, 2, 3});
}

TEST(ConstexprTest, Reverse) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReverse = [] {
    std::array array = kArray;
    absl::c_reverse(array);
    return array;
  }();
  static_assert(kArrayReverse == std::array{3, 2, 1});
}

TEST(ConstexprTest, ReverseCopy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayReverseCopy = [] {
    std::array<int, 3> array;
    absl::c_reverse_copy(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayReverseCopy == std::array{3, 2, 1});
}

TEST(ConstexprTest, Rotate) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayRotate = [] {
    std::array array = kArray;
    absl::c_rotate(array, array.begin() + 1);
    return array;
  }();
  static_assert(kArrayRotate == std::array{2, 3, 1});
}

TEST(ConstexprTest, RotateCopy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayRotateCopy = [] {
    std::array<int, 3> array;
    absl::c_rotate_copy(kArray, kArray.begin() + 1, array.begin());
    return array;
  }();
  static_assert(kArrayRotateCopy == std::array{2, 3, 1});
}

TEST(ConstexprTest, IsPartitioned) {
  static constexpr std::array kArray = {1, 2, 3};
  static_assert(!absl::c_is_partitioned(kArray, [](int x) { return x > 1; }));

  static constexpr std::array kPartitionedArray = {2, 3, 1};
  static_assert(
      absl::c_is_partitioned(kPartitionedArray, [](int x) { return x > 1; }));
}

TEST(ConstexprTest, Partition) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayPartition = [] {
    std::array array = kArray;
    absl::c_partition(array, [](int x) { return x > 1; });
    return array;
  }();
  static_assert(
      absl::c_is_partitioned(kArrayPartition, [](int x) { return x > 1; }));
}

TEST(ConstexprTest, PartitionCopy) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kPartitioned = [] {
    std::array<int, 2> true_part;
    std::array<int, 1> false_part;
    absl::c_partition_copy(kArray, true_part.begin(), false_part.begin(),
                           [](int x) { return x > 1; });
    return std::make_pair(true_part, false_part);
  }();
  static_assert(kPartitioned.first == std::array{2, 3});
  static_assert(kPartitioned.second == std::array{1});
}

TEST(ConstexprTest, PartitionPoint) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kPartitionPoint =
      absl::c_partition_point(kArray, [](int x) { return x > 1; });
  static_assert(kPartitionPoint == kArray.end());
}

TEST(ConstexprTest, Sort) {
  static constexpr std::array kArray = {2, 1, 3};
  static constexpr auto kArraySort = [] {
    std::array array = kArray;
    absl::c_sort(array);
    return array;
  }();
  static_assert(kArraySort == std::array{1, 2, 3});
}

TEST(ConstexprTest, SortWithPredicate) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArraySort = [] {
    std::array array = kArray;
    absl::c_sort(array, std::greater<>());
    return array;
  }();
  static_assert(kArraySort == std::array{3, 2, 1});
}

TEST(ConstexprTest, IsSorted) {
  static constexpr std::array kSortedArray = {1, 2, 3};
  static_assert(absl::c_is_sorted(kSortedArray));
  static constexpr std::array kUnsortedArray = {1, 3, 2};
  static_assert(!absl::c_is_sorted(kUnsortedArray));
}

TEST(ConstexprTest, IsSortedWithPredicate) {
  static constexpr std::array kSortedArray = {3, 2, 1};
  static_assert(absl::c_is_sorted(kSortedArray, std::greater<>()));
  static constexpr std::array kUnsortedArray = {1, 3, 2};
  static_assert(!absl::c_is_sorted(kUnsortedArray, std::greater<>()));
}

TEST(ConstexprTest, PartialSort) {
  static constexpr std::array kArray = {3, 1, 4, 2};
  static constexpr auto kArrayPartialSort = [] {
    std::array array = kArray;
    absl::c_partial_sort(array, array.begin() + 2);
    return array;
  }();
  static_assert(kArrayPartialSort[0] == 1);
  static_assert(kArrayPartialSort[1] == 2);
}

TEST(ConstexprTest, PartialSortWithPredicate) {
  static constexpr std::array kArray = {3, 1, 4, 2};
  static constexpr auto kArrayPartialSort = [] {
    std::array array = kArray;
    absl::c_partial_sort(array, array.begin() + 2, std::greater<>());
    return array;
  }();
  static_assert(kArrayPartialSort[0] == 4);
  static_assert(kArrayPartialSort[1] == 3);
}

TEST(ConstexprTest, PartialSortCopy) {
  static constexpr std::array kArray = {3, 1, 4, 2};
  static constexpr auto kArrayPartialSort = [] {
    std::array<int, 4> array;
    absl::c_partial_sort_copy(kArray, array);
    return array;
  }();
  static_assert(kArrayPartialSort[0] == 1);
  static_assert(kArrayPartialSort[1] == 2);
}

TEST(ConstexprTest, PartialSortCopyWithPredicate) {
  static constexpr std::array kArray = {3, 1, 4, 2};
  static constexpr auto kArrayPartialSort = [] {
    std::array<int, 4> array;
    absl::c_partial_sort_copy(kArray, array, std::greater<>());
    return array;
  }();
  static_assert(kArrayPartialSort[0] == 4);
  static_assert(kArrayPartialSort[1] == 3);
}

TEST(ConstexprTest, IsSortedUntil) {
  static constexpr std::array kSortedArray = {1, 2, 3};
  static_assert(absl::c_is_sorted_until(kSortedArray) == kSortedArray.end());
  static constexpr std::array kUnsortedArray = {1, 3, 2};
  static_assert(absl::c_is_sorted_until(kUnsortedArray) ==
                kUnsortedArray.begin() + 2);
}

TEST(ConstexprTest, IsSortedUntilWithPredicate) {
  static constexpr std::array kSortedArray = {3, 2, 1};
  static_assert(absl::c_is_sorted_until(kSortedArray, std::greater<>()) ==
                kSortedArray.end());
  static constexpr std::array kUnsortedArray = {1, 3, 2};
  static_assert(absl::c_is_sorted_until(kUnsortedArray, std::greater<>()) ==
                kUnsortedArray.begin() + 1);
}

TEST(ConstexprTest, NthElement) {
  static constexpr std::array kArray = {2, 1, 3, 4};
  static constexpr auto kArrayNthElement = [] {
    std::array array = kArray;
    absl::c_nth_element(array, array.begin() + 2);
    return array;
  }();
  static_assert(kArrayNthElement[2] == 3);
  static_assert(kArrayNthElement[0] <= kArrayNthElement[2]);
  static_assert(kArrayNthElement[1] <= kArrayNthElement[2]);
  static_assert(kArrayNthElement[3] >= kArrayNthElement[2]);
}

TEST(ConstexprTest, NthElementWithPredicate) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr auto kArrayNthElement = [] {
    std::array array = kArray;
    absl::c_nth_element(array, array.begin() + 2, std::greater<>());
    return array;
  }();
  static_assert(kArrayNthElement[2] == 2);
  static_assert(std::greater<>()(kArrayNthElement[0], kArrayNthElement[2]) ||
                kArrayNthElement[0] == kArrayNthElement[2]);
  static_assert(std::greater<>()(kArrayNthElement[1], kArrayNthElement[2]) ||
                kArrayNthElement[1] == kArrayNthElement[2]);
  static_assert(std::greater<>()(kArrayNthElement[2], kArrayNthElement[3]) ||
                kArrayNthElement[2] == kArrayNthElement[3]);
}

TEST(ConstexprTest, LowerBound) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr auto kLowerBound = absl::c_lower_bound(kArray, 2);
  static_assert(kLowerBound == kArray.begin() + 1);
}

TEST(ConstexprTest, LowerBoundWithPredicate) {
  static constexpr std::array kArray = {4, 3, 2, 1};
  static constexpr auto kLowerBound =
      absl::c_lower_bound(kArray, 2, std::greater<>());
  static_assert(kLowerBound == kArray.begin() + 2);
}

TEST(ConstexprTest, UpperBound) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr auto kUpperBound = absl::c_upper_bound(kArray, 2);
  static_assert(kUpperBound == kArray.begin() + 2);
}

TEST(ConstexprTest, UpperBoundWithPredicate) {
  static constexpr std::array kArray = {4, 3, 2, 1};
  static constexpr auto kUpperBound =
      absl::c_upper_bound(kArray, 2, std::greater<>());
  static_assert(kUpperBound == kArray.begin() + 3);
}

TEST(ConstexprTest, EqualRange) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr auto kEqualRange = absl::c_equal_range(kArray, 2);
  static_assert(kEqualRange.first == kArray.begin() + 1);
  static_assert(kEqualRange.second == kArray.begin() + 2);
}

TEST(ConstexprTest, EqualRangeWithPredicate) {
  static constexpr std::array kArray = {4, 3, 2, 1};
  static constexpr auto kEqualRange =
      absl::c_equal_range(kArray, 2, std::greater<>());
  static_assert(kEqualRange.first == kArray.begin() + 2);
  static_assert(kEqualRange.second == kArray.begin() + 3);
}

TEST(ConstexprTest, BinarySearch) {
  static constexpr std::array kArray = {1, 2, 3, 4};
  static constexpr bool kBinarySearch = absl::c_binary_search(kArray, 2);
  static_assert(kBinarySearch);
}

TEST(ConstexprTest, BinarySearchWithPredicate) {
  static constexpr std::array kArray = {4, 3, 2, 1};
  static constexpr bool kBinarySearch =
      absl::c_binary_search(kArray, 2, std::greater<>());
  static_assert(kBinarySearch);
}

TEST(ConstexprTest, Merge) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {4, 5, 6};
  static constexpr auto kArrayMerge = [] {
    std::array<int, 6> array;
    absl::c_merge(kArray1, kArray2, array.begin());
    return array;
  }();
  static_assert(kArrayMerge == std::array{1, 2, 3, 4, 5, 6});
}

TEST(ConstexprTest, MergeWithPredicate) {
  static constexpr std::array kArray1 = {3, 2, 1};
  static constexpr std::array kArray2 = {6, 5, 4};
  static constexpr auto kArrayMerge = [] {
    std::array<int, 6> array;
    absl::c_merge(kArray1, kArray2, array.begin(), std::greater<>());
    return array;
  }();
  static_assert(kArrayMerge == std::array{6, 5, 4, 3, 2, 1});
}

TEST(ConstexprTest, Includes) {
  static constexpr std::array kArray1 = {1, 2, 3, 4, 5, 6};
  static constexpr std::array kArray2 = {2, 3, 5};
  static constexpr bool kIncludes = absl::c_includes(kArray1, kArray2);
  static_assert(kIncludes);
}

TEST(ConstexprTest, IncludesWithPredicate) {
  static constexpr std::array kArray1 = {6, 5, 4, 3, 2, 1};
  static constexpr std::array kArray2 = {5, 3, 2};
  static constexpr bool kIncludes =
      absl::c_includes(kArray1, kArray2, std::greater<>());
  static_assert(kIncludes);
}

TEST(ConstexprTest, SetUnion) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 3, 4};
  static constexpr auto kArraySetUnion = [] {
    std::array<int, 4> array;
    absl::c_set_union(kArray1, kArray2, array.begin());
    return array;
  }();
  static_assert(kArraySetUnion == std::array{1, 2, 3, 4});
}

TEST(ConstexprTest, SetUnionWithPredicate) {
  static constexpr std::array kArray1 = {3, 2, 1};
  static constexpr std::array kArray2 = {4, 3, 1};
  static constexpr auto kArraySetUnion = [] {
    std::array<int, 4> array;
    absl::c_set_union(kArray1, kArray2, array.begin(), std::greater<>());
    return array;
  }();
  static_assert(kArraySetUnion == std::array{4, 3, 2, 1});
}

TEST(ConstexprTest, SetIntersection) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 3, 4};
  static constexpr auto kArraySetIntersection = [] {
    std::array<int, 2> array;
    absl::c_set_intersection(kArray1, kArray2, array.begin());
    return array;
  }();
  static_assert(kArraySetIntersection == std::array{1, 3});
}

TEST(ConstexprTest, SetIntersectionWithPredicate) {
  static constexpr std::array kArray1 = {3, 2, 1};
  static constexpr std::array kArray2 = {4, 3, 1};
  static constexpr auto kArraySetIntersection = [] {
    std::array<int, 2> array;
    absl::c_set_intersection(kArray1, kArray2, array.begin(), std::greater<>());
    return array;
  }();
  static_assert(kArraySetIntersection == std::array{3, 1});
}

TEST(ConstexprTest, SetDifference) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 3, 4};
  static constexpr auto kArraySetDifference = [] {
    std::array<int, 1> array;
    absl::c_set_difference(kArray1, kArray2, array.begin());
    return array;
  }();
  static_assert(kArraySetDifference == std::array{2});
}

TEST(ConstexprTest, SetDifferenceWithPredicate) {
  static constexpr std::array kArray1 = {3, 2, 1};
  static constexpr std::array kArray2 = {4, 3, 1};
  static constexpr auto kArraySetDifference = [] {
    std::array<int, 1> array;
    absl::c_set_difference(kArray1, kArray2, array.begin(), std::greater<>());
    return array;
  }();
  static_assert(kArraySetDifference == std::array{2});
}

TEST(ConstexprTest, SetSymmetricDifference) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 3, 4};
  static constexpr auto kArraySetSymmetricDifference = [] {
    std::array<int, 2> array;
    absl::c_set_symmetric_difference(kArray1, kArray2, array.begin());
    return array;
  }();
  static_assert(kArraySetSymmetricDifference == std::array{2, 4});
}

TEST(ConstexprTest, SetSymmetricDifferenceWithPredicate) {
  static constexpr std::array kArray1 = {3, 2, 1};
  static constexpr std::array kArray2 = {4, 3, 1};
  static constexpr auto kArraySetSymmetricDifference = [] {
    std::array<int, 2> array;
    absl::c_set_symmetric_difference(kArray1, kArray2, array.begin(),
                                     std::greater<>());
    return array;
  }();
  static_assert(kArraySetSymmetricDifference == std::array{4, 2});
}

TEST(ConstexprTest, PushHeap) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3, 4};
    absl::c_push_heap(array);
    return array;
  }();
  static_assert(kArray[0] == 4);
}

TEST(ConstexprTest, PushHeapWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {4, 3, 2, 1};
    absl::c_push_heap(array, std::greater<>());
    return array;
  }();
  static_assert(kArray[0] == 1);
}

TEST(ConstexprTest, PopHeap) {
  static constexpr auto kArray = [] {
    std::array array = {4, 3, 2, 1};
    absl::c_pop_heap(array);
    return array;
  }();
  static_assert(kArray[3] == 4);
}

TEST(ConstexprTest, PopHeapWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3, 4};
    absl::c_pop_heap(array, std::greater<>());
    return array;
  }();
  static_assert(kArray[3] == 1);
}

TEST(ConstexprTest, MakeHeap) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3, 4};
    absl::c_make_heap(array);
    return array;
  }();
  static_assert(absl::c_is_heap(kArray));
}

TEST(ConstexprTest, MakeHeapWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {4, 3, 2, 1};
    absl::c_make_heap(array, std::greater<>());
    return array;
  }();
  static_assert(absl::c_is_heap(kArray, std::greater<>()));
}

TEST(ConstexprTest, SortHeap) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3, 4};
    absl::c_make_heap(array);
    absl::c_sort_heap(array);
    return array;
  }();
  static_assert(kArray == std::array{1, 2, 3, 4});
}

TEST(ConstexprTest, SortHeapWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {4, 3, 2, 1};
    absl::c_make_heap(array, std::greater<>());
    absl::c_sort_heap(array, std::greater<>());
    return array;
  }();
  static_assert(kArray == std::array{4, 3, 2, 1});
}

TEST(ConstexprTest, IsHeap) {
  static constexpr std::array kHeap = {4, 2, 3, 1};
  static_assert(absl::c_is_heap(kHeap));
  static constexpr std::array kNotHeap = {1, 2, 3, 4};
  static_assert(!absl::c_is_heap(kNotHeap));
}

TEST(ConstexprTest, IsHeapWithPredicate) {
  static constexpr std::array kHeap = {1, 2, 3, 4};
  static_assert(absl::c_is_heap(kHeap, std::greater<>()));
  static constexpr std::array kNotHeap = {4, 3, 2, 1};
  static_assert(!absl::c_is_heap(kNotHeap, std::greater<>()));
}

TEST(ConstexprTest, IsHeapUntil) {
  static constexpr std::array kHeap = {4, 2, 3, 1};
  static_assert(absl::c_is_heap_until(kHeap) == kHeap.end());
  static constexpr std::array kNotHeap = {4, 2, 3, 5};
  static_assert(absl::c_is_heap_until(kNotHeap) == kNotHeap.begin() + 3);
}

TEST(ConstexprTest, IsHeapUntilWithPredicate) {
  static constexpr std::array kHeap = {1, 2, 3, 4};
  static_assert(absl::c_is_heap_until(kHeap, std::greater<>()) == kHeap.end());
  static constexpr std::array kNotHeap = {1, 2, 3, 0};
  static_assert(absl::c_is_heap_until(kNotHeap, std::greater<>()) ==
                kNotHeap.begin() + 3);
}

TEST(ConstexprTest, LexicographicalCompare) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 2, 4};
  static constexpr std::array kArray3 = {1, 2, 3};
  static_assert(absl::c_lexicographical_compare(kArray1, kArray2));
  static_assert(!absl::c_lexicographical_compare(kArray2, kArray1));
  static_assert(!absl::c_lexicographical_compare(kArray1, kArray3));
}

TEST(ConstexprTest, LexicographicalCompareWithPredicate) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {1, 2, 4};
  static constexpr std::array kArray3 = {1, 2, 3};
  static_assert(
      !absl::c_lexicographical_compare(kArray1, kArray2, std::greater<>()));
  static_assert(
      absl::c_lexicographical_compare(kArray2, kArray1, std::greater<>()));
  static_assert(
      !absl::c_lexicographical_compare(kArray1, kArray3, std::greater<>()));
}

TEST(ConstexprTest, NextPermutation) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3};
    absl::c_next_permutation(array);
    return array;
  }();
  static_assert(kArray == std::array{1, 3, 2});
}

TEST(ConstexprTest, NextPermutationWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {3, 2, 1};
    absl::c_next_permutation(array, std::greater<>());
    return array;
  }();
  static_assert(kArray == std::array{3, 1, 2});
}

TEST(ConstexprTest, PrevPermutation) {
  static constexpr auto kArray = [] {
    std::array array = {1, 3, 2};
    absl::c_prev_permutation(array);
    return array;
  }();
  static_assert(kArray == std::array{1, 2, 3});
}

TEST(ConstexprTest, PrevPermutationWithPredicate) {
  static constexpr auto kArray = [] {
    std::array array = {1, 2, 3};
    absl::c_prev_permutation(array, std::greater<>());
    return array;
  }();
  static_assert(kArray == std::array{1, 3, 2});
}

TEST(ConstexprTest, Iota) {
  static constexpr auto kArray = [] {
    std::array<int, 3> array;
    absl::c_iota(array, 1);
    return array;
  }();
  static_assert(kArray == std::array{1, 2, 3});
}

TEST(ConstexprTest, Accumulate) {
  static constexpr std::array kArray = {1, 2, 3};
  static_assert(absl::c_accumulate(kArray, 0) == 6);
}

TEST(ConstexprTest, AccumulateWithPredicate) {
  static constexpr std::array kArray = {1, 2, 3};
  static_assert(absl::c_accumulate(kArray, 1, std::multiplies<>()) == 6);
}

TEST(ConstexprTest, InnerProduct) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {4, 5, 6};
  static_assert(absl::c_inner_product(kArray1, kArray2, 0) == 32);
}

TEST(ConstexprTest, InnerProductWithPredicate) {
  static constexpr std::array kArray1 = {1, 2, 3};
  static constexpr std::array kArray2 = {4, 5, 6};
  static_assert(absl::c_inner_product(kArray1, kArray2, 1, std::multiplies<>(),
                                      std::plus<>()) == 315);
}

TEST(ConstexprTest, AdjacentDifference) {
  static constexpr std::array kArray = {1, 2, 4};
  static constexpr auto kArrayAdjacentDifference = [] {
    std::array<int, 3> array;
    absl::c_adjacent_difference(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayAdjacentDifference == std::array{1, 1, 2});
}

TEST(ConstexprTest, AdjacentDifferenceWithPredicate) {
  static constexpr std::array kArray = {1, 2, 4};
  static constexpr auto kArrayAdjacentDifference = [] {
    std::array<int, 3> array;
    absl::c_adjacent_difference(kArray, array.begin(), std::multiplies<>());
    return array;
  }();
  static_assert(kArrayAdjacentDifference == std::array{1, 2, 8});
}

TEST(ConstexprTest, PartialSum) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayPartialSum = [] {
    std::array<int, 3> array;
    absl::c_partial_sum(kArray, array.begin());
    return array;
  }();
  static_assert(kArrayPartialSum == std::array{1, 3, 6});
}

TEST(ConstexprTest, PartialSumWithPredicate) {
  static constexpr std::array kArray = {1, 2, 3};
  static constexpr auto kArrayPartialSum = [] {
    std::array<int, 3> array;
    absl::c_partial_sum(kArray, array.begin(), std::multiplies<>());
    return array;
  }();
  static_assert(kArrayPartialSum == std::array{1, 2, 6});
}

#endif  // defined(ABSL_INTERNAL_CPLUSPLUS_LANG) &&
        //  ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L

// A type that acts as both a container and an iterator.
struct AmbiguousType {
  // Container requirements
  int* begin() { return nullptr; }
  int* end() { return nullptr; }

  // Iterator requirements
  using iterator_category = std::input_iterator_tag;
  using value_type = int;
  using difference_type = std::ptrdiff_t;
  using pointer = int*;
  using reference = int&;

  int& operator*() {
    static int x;
    return x;
  }
  AmbiguousType& operator++() { return *this; }
  AmbiguousType operator++(int) { return *this; }
  friend bool operator==(const AmbiguousType&, const AmbiguousType&) {
    return true;
  }
  friend bool operator!=(const AmbiguousType&, const AmbiguousType&) {
    return false;
  }
};

template <typename Container, typename Output, typename = void>
struct CanCopy : std::false_type {};
template <typename Container, typename Output>
struct CanCopy<Container, Output,
               std::void_t<decltype(absl::c_copy(std::declval<Container>(),
                                                 std::declval<Output>()))>>
    : std::true_type {};

template <typename Container, typename Output, typename = void>
struct CanCopyN : std::false_type {};
template <typename Container, typename Output>
struct CanCopyN<Container, Output,
                std::void_t<decltype(absl::c_copy_n(
                    std::declval<Container>(), std::declval<ptrdiff_t>(),
                    std::declval<Output>()))>> : std::true_type {};

template <typename Container, typename Output, typename = void>
struct CanMove : std::false_type {};
template <typename Container, typename Output>
struct CanMove<Container, Output,
               std::void_t<decltype(absl::c_move(std::declval<Container>(),
                                                 std::declval<Output>()))>>
    : std::true_type {};

template <typename Container, typename Output, typename UnaryOp,
          typename = void>
struct CanTransformUnary : std::false_type {};
template <typename Container, typename Output, typename UnaryOp>
struct CanTransformUnary<Container, Output, UnaryOp,
                         absl::void_t<decltype(absl::c_transform(
                             std::declval<Container>(), std::declval<Output>(),
                             std::declval<UnaryOp>()))>> : std::true_type {};

template <typename Container1, typename Container2, typename Output,
          typename BinaryOp, typename = void>
struct CanTransformBinary : std::false_type {};
template <typename Container1, typename Container2, typename Output,
          typename BinaryOp>
struct CanTransformBinary<
    Container1, Container2, Output, BinaryOp,
    absl::void_t<decltype(absl::c_transform(
        std::declval<Container1>(), std::declval<Container2>(),
        std::declval<Output>(), std::declval<BinaryOp>()))>> : std::true_type {
};

TEST(CanCopyTest, CopyToMultiDimArray) {
  static_assert(CanCopy<std::vector<int>, int (&)[10]>::value);
  static_assert(!CanCopy<std::vector<int>, int (&)[2][2]>::value);
  static_assert(CanCopyN<std::vector<int>, int (&)[10]>::value);
  static_assert(!CanCopyN<std::vector<int>, int (&)[2][2]>::value);

  static_assert(CanCopy<int[10], int (&)[10]>::value);
  static_assert(!CanCopy<int[10], int (&)[2][2]>::value);
  static_assert(CanCopyN<int[10], int (&)[10]>::value);
  static_assert(!CanCopyN<int[10], int (&)[2][2]>::value);
  static_assert(!CanCopy<int[2][2], int (&)[4]>::value);
  static_assert(!CanCopy<int[2][2], int (&)[2][2]>::value);
  static_assert(!CanCopyN<int[2][2], int (&)[4]>::value);
  static_assert(!CanCopyN<int[2][2], int (&)[2][2]>::value);
}

TEST(CanCopyTest, BlockNonWritableIterators) {
  using Vec = std::vector<int>;

  static_assert(CanCopy<Vec, Vec::iterator>::value);
  static_assert(CanCopy<Vec, std::back_insert_iterator<Vec>>::value);
}

TEST(CanCopyTest, AmbiguousTypeFailsToCompile) {
  using Vec = std::vector<int>;
  // Because AmbiguousType is both an iterator and a container,
  // the compiler should fail to resolve the c_copy overload.
  static_assert(!CanCopy<Vec, AmbiguousType&>::value,
                "Ambiguous types should not compile!");
  static_assert(!CanCopyN<Vec, AmbiguousType&>::value,
                "Ambiguous types should not compile!");
}

TEST(CanCopyTest, CopyToRValue) {
  using Vec = std::vector<int>;
  using Span = absl::Span<int>;
  static_assert(CanCopy<Vec, Span>::value,
                "Should be able to copy to rvalue Span");
  static_assert(!CanCopy<Vec, Vec>::value,
                "Should not be able to copy to rvalue vector");
  static_assert(CanCopyN<Vec, Span>::value,
                "Should be able to copy_n to rvalue Span");
  static_assert(!CanCopyN<Vec, Vec>::value,
                "Should not be able to copy_n to rvalue vector");
}

TEST(CanMoveTest, MoveToMultiDimArray) {
  static_assert(CanMove<std::vector<int>, int (&)[10]>::value);
  static_assert(!CanMove<std::vector<int>, int (&)[2][2]>::value);

  static_assert(CanMove<int[10], int (&)[10]>::value);
  static_assert(!CanMove<int[10], int (&)[2][2]>::value);
  static_assert(!CanMove<int[2][2], int (&)[4]>::value);
  static_assert(!CanMove<int[2][2], int (&)[2][2]>::value);
}

TEST(CanMoveTest, AmbiguousTypeFailsToCompile) {
  using Vec = std::vector<int>;
  // Because AmbiguousType is both an iterator and a container,
  // the compiler should fail to resolve the c_move overload.
  static_assert(!CanMove<Vec, AmbiguousType&>::value,
                "Ambiguous types should not compile!");
}

TEST(CanMoveTest, MoveToRValue) {
  using Vec = std::vector<std::unique_ptr<int>>;
  using Span = absl::Span<std::unique_ptr<int>>;
  static_assert(CanMove<Vec, Span>::value,
                "Should be able to move to rvalue Span");
  static_assert(!CanMove<Vec, Vec>::value,
                "Should not be able to move to rvalue vector");
}

TEST(CanTransformTest, TransformToMultiDimArray) {
  using Negate = std::negate<int>;
  using Plus = std::plus<int>;

  static_assert(
      CanTransformUnary<std::vector<int>, int (&)[10], Negate>::value);
  static_assert(
      !CanTransformUnary<std::vector<int>, int (&)[2][2], Negate>::value);

  static_assert(CanTransformUnary<int[10], int (&)[10], Negate>::value);
  static_assert(!CanTransformUnary<int[10], int (&)[2][2], Negate>::value);
  static_assert(!CanTransformUnary<int[2][2], int (&)[4], Negate>::value);
  static_assert(!CanTransformUnary<int[2][2], int (&)[2][2], Negate>::value);

  static_assert(CanTransformBinary<std::vector<int>, std::vector<int>,
                                   int (&)[10], Plus>::value);
  static_assert(!CanTransformBinary<std::vector<int>, std::vector<int>,
                                    int (&)[2][2], Plus>::value);

  static_assert(CanTransformBinary<int[10], int[10], int (&)[10], Plus>::value);
  static_assert(
      !CanTransformBinary<int[10], int[10], int (&)[2][2], Plus>::value);
  static_assert(
      !CanTransformBinary<int[2][2], int[4], int (&)[4], Plus>::value);
  static_assert(
      !CanTransformBinary<int[2][2], int[2][2], int (&)[2][2], Plus>::value);
}

TEST(CanTransformTest, AmbiguousTypeFailsToCompile) {
  using Vec = std::vector<int>;
  using Negate = std::negate<int>;
  using Plus = std::plus<int>;

  // Because AmbiguousType is both an iterator and a container,
  // the compiler should fail to resolve the c_transform overload.
  static_assert(!CanTransformUnary<Vec, AmbiguousType&, Negate>::value,
                "Ambiguous types should not compile!");
  static_assert(!CanTransformBinary<Vec, Vec, AmbiguousType&, Plus>::value,
                "Ambiguous types should not compile!");
}

template <typename C, typename T, typename = void>
struct CanFill : std::false_type {};

template <typename C, typename T>
struct CanFill<C, T,
               std::void_t<decltype(absl::c_fill(std::declval<C (*)()>()(),
                                                 std::declval<T (*)()>()()))>>
    : std::true_type {};

TEST(CanFillTest, NonSpans) {
  using T = int;

  struct AbslSpanSubclass : absl::Span<T> {};
  static_assert(!CanFill<std::vector<T>, T>::value,
                "non-spans must not be allowed");
  static_assert(!CanFill<AbslSpanSubclass, T>::value,
                "subclasses must not be allowed");

#ifdef __cpp_lib_span
  struct StdSpanSubclass : std::span<T> {};
  static_assert(!CanFill<StdSpanSubclass, T>::value,
                "std::span must not be allowed");
#endif
}
}  // namespace