diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/algorithm')
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/BUILD.bazel | 91 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/CMakeLists.txt | 69 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/algorithm.h | 159 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/algorithm_test.cc | 182 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/container.h | 1764 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/container_test.cc | 1124 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/algorithm/equal_benchmark.cc | 126 |
7 files changed, 0 insertions, 3515 deletions
diff --git a/third_party/abseil_cpp/absl/algorithm/BUILD.bazel b/third_party/abseil_cpp/absl/algorithm/BUILD.bazel deleted file mode 100644 index a3002b7dcd5f..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/BUILD.bazel +++ /dev/null @@ -1,91 +0,0 @@ -# -# 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. -# - -load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test") -load( - "//absl:copts/configure_copts.bzl", - "ABSL_DEFAULT_COPTS", - "ABSL_DEFAULT_LINKOPTS", - "ABSL_TEST_COPTS", -) - -package(default_visibility = ["//visibility:public"]) - -licenses(["notice"]) - -cc_library( - name = "algorithm", - hdrs = ["algorithm.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - "//absl/base:config", - ], -) - -cc_test( - name = "algorithm_test", - size = "small", - srcs = ["algorithm_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":algorithm", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "algorithm_benchmark", - srcs = ["equal_benchmark.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - tags = ["benchmark"], - deps = [ - ":algorithm", - "//absl/base:core_headers", - "@com_github_google_benchmark//:benchmark_main", - ], -) - -cc_library( - name = "container", - hdrs = [ - "container.h", - ], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":algorithm", - "//absl/base:core_headers", - "//absl/meta:type_traits", - ], -) - -cc_test( - name = "container_test", - srcs = ["container_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":container", - "//absl/base", - "//absl/base:core_headers", - "//absl/memory", - "//absl/types:span", - "@com_google_googletest//:gtest_main", - ], -) diff --git a/third_party/abseil_cpp/absl/algorithm/CMakeLists.txt b/third_party/abseil_cpp/absl/algorithm/CMakeLists.txt deleted file mode 100644 index 56cd0fb85b50..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/CMakeLists.txt +++ /dev/null @@ -1,69 +0,0 @@ -# -# 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. -# - -absl_cc_library( - NAME - algorithm - HDRS - "algorithm.h" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::config - PUBLIC -) - -absl_cc_test( - NAME - algorithm_test - SRCS - "algorithm_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::algorithm - gmock_main -) - -absl_cc_library( - NAME - algorithm_container - HDRS - "container.h" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::algorithm - absl::core_headers - absl::meta - PUBLIC -) - -absl_cc_test( - NAME - container_test - SRCS - "container_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::algorithm_container - absl::base - absl::core_headers - absl::memory - absl::span - gmock_main -) diff --git a/third_party/abseil_cpp/absl/algorithm/algorithm.h b/third_party/abseil_cpp/absl/algorithm/algorithm.h deleted file mode 100644 index e9b473387278..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/algorithm.h +++ /dev/null @@ -1,159 +0,0 @@ -// 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. -// -// ----------------------------------------------------------------------------- -// File: algorithm.h -// ----------------------------------------------------------------------------- -// -// This header file contains Google extensions to the standard <algorithm> C++ -// header. - -#ifndef ABSL_ALGORITHM_ALGORITHM_H_ -#define ABSL_ALGORITHM_ALGORITHM_H_ - -#include <algorithm> -#include <iterator> -#include <type_traits> - -#include "absl/base/config.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN - -namespace algorithm_internal { - -// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`. -struct EqualTo { - template <typename T, typename U> - bool operator()(const T& a, const U& b) const { - return a == b; - } -}; - -template <typename InputIter1, typename InputIter2, typename Pred> -bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2, - InputIter2 last2, Pred pred, std::input_iterator_tag, - std::input_iterator_tag) { - while (true) { - if (first1 == last1) return first2 == last2; - if (first2 == last2) return false; - if (!pred(*first1, *first2)) return false; - ++first1; - ++first2; - } -} - -template <typename InputIter1, typename InputIter2, typename Pred> -bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2, - InputIter2 last2, Pred&& pred, std::random_access_iterator_tag, - std::random_access_iterator_tag) { - return (last1 - first1 == last2 - first2) && - std::equal(first1, last1, first2, std::forward<Pred>(pred)); -} - -// When we are using our own internal predicate that just applies operator==, we -// forward to the non-predicate form of std::equal. This enables an optimization -// in libstdc++ that can result in std::memcmp being used for integer types. -template <typename InputIter1, typename InputIter2> -bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2, - InputIter2 last2, algorithm_internal::EqualTo /* unused */, - std::random_access_iterator_tag, - std::random_access_iterator_tag) { - return (last1 - first1 == last2 - first2) && - std::equal(first1, last1, first2); -} - -template <typename It> -It RotateImpl(It first, It middle, It last, std::true_type) { - return std::rotate(first, middle, last); -} - -template <typename It> -It RotateImpl(It first, It middle, It last, std::false_type) { - std::rotate(first, middle, last); - return std::next(first, std::distance(middle, last)); -} - -} // namespace algorithm_internal - -// equal() -// -// Compares the equality of two ranges specified by pairs of iterators, using -// the given predicate, returning true iff for each corresponding iterator i1 -// and i2 in the first and second range respectively, pred(*i1, *i2) == true -// -// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`) -// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are -// both random-access iterators, and `last1` - `first1` != `last2` - `first2`, -// then the predicate is never invoked and the function returns false. -// -// This is a C++11-compatible implementation of C++14 `std::equal`. See -// https://en.cppreference.com/w/cpp/algorithm/equal for more information. -template <typename InputIter1, typename InputIter2, typename Pred> -bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, - InputIter2 last2, Pred&& pred) { - return algorithm_internal::EqualImpl( - first1, last1, first2, last2, std::forward<Pred>(pred), - typename std::iterator_traits<InputIter1>::iterator_category{}, - typename std::iterator_traits<InputIter2>::iterator_category{}); -} - -// Overload of equal() that performs comparison of two ranges specified by pairs -// of iterators using operator==. -template <typename InputIter1, typename InputIter2> -bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, - InputIter2 last2) { - return absl::equal(first1, last1, first2, last2, - algorithm_internal::EqualTo{}); -} - -// linear_search() -// -// Performs a linear search for `value` using the iterator `first` up to -// but not including `last`, returning true if [`first`, `last`) contains an -// element equal to `value`. -// -// A linear search is of O(n) complexity which is guaranteed to make at most -// n = (`last` - `first`) comparisons. A linear search over short containers -// may be faster than a binary search, even when the container is sorted. -template <typename InputIterator, typename EqualityComparable> -bool linear_search(InputIterator first, InputIterator last, - const EqualityComparable& value) { - return std::find(first, last, value) != last; -} - -// rotate() -// -// Performs a left rotation on a range of elements (`first`, `last`) such that -// `middle` is now the first element. `rotate()` returns an iterator pointing to -// the first element before rotation. This function is exactly the same as -// `std::rotate`, but fixes a bug in gcc -// <= 4.9 where `std::rotate` returns `void` instead of an iterator. -// -// The complexity of this algorithm is the same as that of `std::rotate`, but if -// `ForwardIterator` is not a random-access iterator, then `absl::rotate` -// performs an additional pass over the range to construct the return value. -template <typename ForwardIterator> -ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, - ForwardIterator last) { - return algorithm_internal::RotateImpl( - first, middle, last, - std::is_same<decltype(std::rotate(first, middle, last)), - ForwardIterator>()); -} - -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_ALGORITHM_ALGORITHM_H_ diff --git a/third_party/abseil_cpp/absl/algorithm/algorithm_test.cc b/third_party/abseil_cpp/absl/algorithm/algorithm_test.cc deleted file mode 100644 index 81fccb61353e..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/algorithm_test.cc +++ /dev/null @@ -1,182 +0,0 @@ -// 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/algorithm.h" - -#include <algorithm> -#include <list> -#include <vector> - -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -namespace { - -TEST(EqualTest, DefaultComparisonRandomAccess) { - std::vector<int> v1{1, 2, 3}; - std::vector<int> v2 = v1; - std::vector<int> v3 = {1, 2}; - std::vector<int> v4 = {1, 2, 4}; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end())); -} - -TEST(EqualTest, DefaultComparison) { - std::list<int> lst1{1, 2, 3}; - std::list<int> lst2 = lst1; - std::list<int> lst3{1, 2}; - std::list<int> lst4{1, 2, 4}; - - EXPECT_TRUE(absl::equal(lst1.begin(), lst1.end(), lst2.begin(), lst2.end())); - EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst3.begin(), lst3.end())); - EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst4.begin(), lst4.end())); -} - -TEST(EqualTest, EmptyRange) { - std::vector<int> v1{1, 2, 3}; - std::vector<int> empty1; - std::vector<int> empty2; - - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), empty1.begin(), empty1.end())); - EXPECT_FALSE(absl::equal(empty1.begin(), empty1.end(), v1.begin(), v1.end())); - EXPECT_TRUE( - absl::equal(empty1.begin(), empty1.end(), empty2.begin(), empty2.end())); -} - -TEST(EqualTest, MixedIterTypes) { - std::vector<int> v1{1, 2, 3}; - std::list<int> lst1{v1.begin(), v1.end()}; - std::list<int> lst2{1, 2, 4}; - std::list<int> lst3{1, 2}; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), lst1.begin(), lst1.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst2.begin(), lst2.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst3.begin(), lst3.end())); -} - -TEST(EqualTest, MixedValueTypes) { - std::vector<int> v1{1, 2, 3}; - std::vector<char> v2{1, 2, 3}; - std::vector<char> v3{1, 2}; - std::vector<char> v4{1, 2, 4}; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end())); -} - -TEST(EqualTest, WeirdIterators) { - std::vector<bool> v1{true, false}; - std::vector<bool> v2 = v1; - std::vector<bool> v3{true}; - std::vector<bool> v4{true, true, true}; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end())); -} - -TEST(EqualTest, CustomComparison) { - int n[] = {1, 2, 3, 4}; - std::vector<int*> v1{&n[0], &n[1], &n[2]}; - std::vector<int*> v2 = v1; - std::vector<int*> v3{&n[0], &n[1], &n[3]}; - std::vector<int*> v4{&n[0], &n[1]}; - - auto eq = [](int* a, int* b) { return *a == *b; }; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), eq)); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), eq)); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end(), eq)); -} - -TEST(EqualTest, MoveOnlyPredicate) { - std::vector<int> v1{1, 2, 3}; - std::vector<int> v2{4, 5, 6}; - - // move-only equality predicate - struct Eq { - Eq() = default; - Eq(Eq &&) = default; - Eq(const Eq &) = delete; - Eq &operator=(const Eq &) = delete; - bool operator()(const int a, const int b) const { return a == b; } - }; - - EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v1.begin(), v1.end(), Eq())); - EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), Eq())); -} - -struct CountingTrivialPred { - int* count; - bool operator()(int, int) const { - ++*count; - return true; - } -}; - -TEST(EqualTest, RandomAccessComplexity) { - std::vector<int> v1{1, 1, 3}; - std::vector<int> v2 = v1; - std::vector<int> v3{1, 2}; - - do { - int count = 0; - absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), - CountingTrivialPred{&count}); - EXPECT_LE(count, 3); - } while (std::next_permutation(v2.begin(), v2.end())); - - int count = 0; - absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), - CountingTrivialPred{&count}); - EXPECT_EQ(count, 0); -} - -class LinearSearchTest : public testing::Test { - protected: - LinearSearchTest() : container_{1, 2, 3} {} - - static bool Is3(int n) { return n == 3; } - static bool Is4(int n) { return n == 4; } - - std::vector<int> container_; -}; - -TEST_F(LinearSearchTest, linear_search) { - EXPECT_TRUE(absl::linear_search(container_.begin(), container_.end(), 3)); - EXPECT_FALSE(absl::linear_search(container_.begin(), container_.end(), 4)); -} - -TEST_F(LinearSearchTest, linear_searchConst) { - const std::vector<int> *const const_container = &container_; - EXPECT_TRUE( - absl::linear_search(const_container->begin(), const_container->end(), 3)); - EXPECT_FALSE( - absl::linear_search(const_container->begin(), const_container->end(), 4)); -} - -TEST(RotateTest, Rotate) { - std::vector<int> v{0, 1, 2, 3, 4}; - EXPECT_EQ(*absl::rotate(v.begin(), v.begin() + 2, v.end()), 0); - EXPECT_THAT(v, testing::ElementsAreArray({2, 3, 4, 0, 1})); - - std::list<int> l{0, 1, 2, 3, 4}; - EXPECT_EQ(*absl::rotate(l.begin(), std::next(l.begin(), 3), l.end()), 0); - EXPECT_THAT(l, testing::ElementsAreArray({3, 4, 0, 1, 2})); -} - -} // namespace diff --git a/third_party/abseil_cpp/absl/algorithm/container.h b/third_party/abseil_cpp/absl/algorithm/container.h deleted file mode 100644 index 6398438f08ce..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/container.h +++ /dev/null @@ -1,1764 +0,0 @@ -// 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. -// -// ----------------------------------------------------------------------------- -// File: container.h -// ----------------------------------------------------------------------------- -// -// This header file provides Container-based versions of algorithmic functions -// within the C++ standard library. The following standard library sets of -// functions are covered within this file: -// -// * Algorithmic <iterator> functions -// * Algorithmic <numeric> functions -// * <algorithm> functions -// -// The standard library functions operate on iterator ranges; the functions -// within this API operate on containers, though many return iterator ranges. -// -// All functions within this API are named with a `c_` prefix. Calls such as -// `absl::c_xx(container, ...) are equivalent to std:: functions such as -// `std::xx(std::begin(cont), std::end(cont), ...)`. Functions that act on -// iterators but not conceptually on iterator ranges (e.g. `std::iter_swap`) -// have no equivalent here. -// -// For template parameter and variable naming, `C` indicates the container type -// to which the function is applied, `Pred` indicates the predicate object type -// to be used by the function and `T` indicates the applicable element type. - -#ifndef ABSL_ALGORITHM_CONTAINER_H_ -#define ABSL_ALGORITHM_CONTAINER_H_ - -#include <algorithm> -#include <cassert> -#include <iterator> -#include <numeric> -#include <type_traits> -#include <unordered_map> -#include <unordered_set> -#include <utility> -#include <vector> - -#include "absl/algorithm/algorithm.h" -#include "absl/base/macros.h" -#include "absl/meta/type_traits.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace container_algorithm_internal { - -// NOTE: it is important to defer to ADL lookup for building with C++ modules, -// especially for headers like <valarray> which are not visible from this file -// but specialize std::begin and std::end. -using std::begin; -using std::end; - -// The type of the iterator given by begin(c) (possibly std::begin(c)). -// ContainerIter<const vector<T>> gives vector<T>::const_iterator, -// while ContainerIter<vector<T>> gives vector<T>::iterator. -template <typename C> -using ContainerIter = decltype(begin(std::declval<C&>())); - -// An MSVC bug involving template parameter substitution requires us to use -// decltype() here instead of just std::pair. -template <typename C1, typename C2> -using ContainerIterPairType = - decltype(std::make_pair(ContainerIter<C1>(), ContainerIter<C2>())); - -template <typename C> -using ContainerDifferenceType = - decltype(std::distance(std::declval<ContainerIter<C>>(), - std::declval<ContainerIter<C>>())); - -template <typename C> -using ContainerPointerType = - typename std::iterator_traits<ContainerIter<C>>::pointer; - -// container_algorithm_internal::c_begin and -// container_algorithm_internal::c_end are abbreviations for proper ADL -// lookup of std::begin and std::end, i.e. -// using std::begin; -// using std::end; -// std::foo(begin(c), end(c)); -// becomes -// std::foo(container_algorithm_internal::begin(c), -// container_algorithm_internal::end(c)); -// These are meant for internal use only. - -template <typename C> -ContainerIter<C> c_begin(C& c) { return begin(c); } - -template <typename C> -ContainerIter<C> c_end(C& c) { return end(c); } - -template <typename T> -struct IsUnorderedContainer : std::false_type {}; - -template <class Key, class T, class Hash, class KeyEqual, class Allocator> -struct IsUnorderedContainer< - std::unordered_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; - -template <class Key, class Hash, class KeyEqual, class Allocator> -struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>> - : std::true_type {}; - -// container_algorithm_internal::c_size. It is meant for internal use only. - -template <class C> -auto c_size(C& c) -> decltype(c.size()) { - return c.size(); -} - -template <class T, std::size_t N> -constexpr std::size_t c_size(T (&)[N]) { - return N; -} - -} // namespace container_algorithm_internal - -// PUBLIC API - -//------------------------------------------------------------------------------ -// Abseil algorithm.h functions -//------------------------------------------------------------------------------ - -// c_linear_search() -// -// Container-based version of absl::linear_search() for performing a linear -// search within a container. -template <typename C, typename EqualityComparable> -bool c_linear_search(const C& c, EqualityComparable&& value) { - return linear_search(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<EqualityComparable>(value)); -} - -//------------------------------------------------------------------------------ -// <iterator> algorithms -//------------------------------------------------------------------------------ - -// c_distance() -// -// Container-based version of the <iterator> `std::distance()` function to -// return the number of elements within a container. -template <typename C> -container_algorithm_internal::ContainerDifferenceType<const C> c_distance( - const C& c) { - return std::distance(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Non-modifying sequence operations -//------------------------------------------------------------------------------ - -// c_all_of() -// -// Container-based version of the <algorithm> `std::all_of()` function to -// test a condition on all elements within a container. -template <typename C, typename Pred> -bool c_all_of(const C& c, Pred&& pred) { - return std::all_of(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_any_of() -// -// Container-based version of the <algorithm> `std::any_of()` function to -// test if any element in a container fulfills a condition. -template <typename C, typename Pred> -bool c_any_of(const C& c, Pred&& pred) { - return std::any_of(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_none_of() -// -// Container-based version of the <algorithm> `std::none_of()` function to -// test if no elements in a container fulfill a condition. -template <typename C, typename Pred> -bool c_none_of(const C& c, Pred&& pred) { - return std::none_of(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_for_each() -// -// Container-based version of the <algorithm> `std::for_each()` function to -// apply a function to a container's elements. -template <typename C, typename Function> -decay_t<Function> c_for_each(C&& c, Function&& f) { - return std::for_each(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Function>(f)); -} - -// c_find() -// -// Container-based version of the <algorithm> `std::find()` function to find -// the first element containing the passed value within a container value. -template <typename C, typename T> -container_algorithm_internal::ContainerIter<C> c_find(C& c, T&& value) { - return std::find(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<T>(value)); -} - -// c_find_if() -// -// Container-based version of the <algorithm> `std::find_if()` function to find -// the first element in a container matching the given condition. -template <typename C, typename Pred> -container_algorithm_internal::ContainerIter<C> c_find_if(C& c, Pred&& pred) { - return std::find_if(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_find_if_not() -// -// Container-based version of the <algorithm> `std::find_if_not()` function to -// find the first element in a container not matching the given condition. -template <typename C, typename Pred> -container_algorithm_internal::ContainerIter<C> c_find_if_not(C& c, - Pred&& pred) { - return std::find_if_not(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_find_end() -// -// Container-based version of the <algorithm> `std::find_end()` function to -// find the last subsequence within a container. -template <typename Sequence1, typename Sequence2> -container_algorithm_internal::ContainerIter<Sequence1> c_find_end( - Sequence1& sequence, Sequence2& subsequence) { - return std::find_end(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(subsequence), - container_algorithm_internal::c_end(subsequence)); -} - -// Overload of c_find_end() for using a predicate evaluation other than `==` as -// the function's test condition. -template <typename Sequence1, typename Sequence2, typename BinaryPredicate> -container_algorithm_internal::ContainerIter<Sequence1> c_find_end( - Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { - return std::find_end(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(subsequence), - container_algorithm_internal::c_end(subsequence), - std::forward<BinaryPredicate>(pred)); -} - -// c_find_first_of() -// -// Container-based version of the <algorithm> `std::find_first_of()` function to -// find the first element within the container that is also within the options -// container. -template <typename C1, typename C2> -container_algorithm_internal::ContainerIter<C1> c_find_first_of(C1& container, - C2& options) { - return std::find_first_of(container_algorithm_internal::c_begin(container), - container_algorithm_internal::c_end(container), - container_algorithm_internal::c_begin(options), - container_algorithm_internal::c_end(options)); -} - -// Overload of c_find_first_of() for using a predicate evaluation other than -// `==` as the function's test condition. -template <typename C1, typename C2, typename BinaryPredicate> -container_algorithm_internal::ContainerIter<C1> c_find_first_of( - C1& container, C2& options, BinaryPredicate&& pred) { - return std::find_first_of(container_algorithm_internal::c_begin(container), - container_algorithm_internal::c_end(container), - container_algorithm_internal::c_begin(options), - container_algorithm_internal::c_end(options), - std::forward<BinaryPredicate>(pred)); -} - -// c_adjacent_find() -// -// Container-based version of the <algorithm> `std::adjacent_find()` function to -// find equal adjacent elements within a container. -template <typename Sequence> -container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( - Sequence& sequence) { - return std::adjacent_find(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_adjacent_find() for using a predicate evaluation other than -// `==` as the function's test condition. -template <typename Sequence, typename BinaryPredicate> -container_algorithm_internal::ContainerIter<Sequence> c_adjacent_find( - Sequence& sequence, BinaryPredicate&& pred) { - return std::adjacent_find(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<BinaryPredicate>(pred)); -} - -// c_count() -// -// Container-based version of the <algorithm> `std::count()` function to count -// values that match within a container. -template <typename C, typename T> -container_algorithm_internal::ContainerDifferenceType<const C> c_count( - const C& c, T&& value) { - return std::count(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<T>(value)); -} - -// c_count_if() -// -// Container-based version of the <algorithm> `std::count_if()` function to -// count values matching a condition within a container. -template <typename C, typename Pred> -container_algorithm_internal::ContainerDifferenceType<const C> c_count_if( - const C& c, Pred&& pred) { - return std::count_if(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_mismatch() -// -// Container-based version of the <algorithm> `std::mismatch()` function to -// return the first element where two ordered containers differ. Applies `==` to -// the first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). -template <typename C1, typename C2> -container_algorithm_internal::ContainerIterPairType<C1, C2> -c_mismatch(C1& c1, C2& c2) { - auto first1 = container_algorithm_internal::c_begin(c1); - auto last1 = container_algorithm_internal::c_end(c1); - auto first2 = container_algorithm_internal::c_begin(c2); - auto last2 = container_algorithm_internal::c_end(c2); - - for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { - // Negates equality because Cpp17EqualityComparable doesn't require clients - // to overload both `operator==` and `operator!=`. - if (!(*first1 == *first2)) { - break; - } - } - - return std::make_pair(first1, first2); -} - -// Overload of c_mismatch() for using a predicate evaluation other than `==` as -// the function's test condition. Applies `pred`to the first N elements of `c1` -// and `c2`, where N = min(size(c1), size(c2)). -template <typename C1, typename C2, typename BinaryPredicate> -container_algorithm_internal::ContainerIterPairType<C1, C2> -c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) { - auto first1 = container_algorithm_internal::c_begin(c1); - auto last1 = container_algorithm_internal::c_end(c1); - auto first2 = container_algorithm_internal::c_begin(c2); - auto last2 = container_algorithm_internal::c_end(c2); - - for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { - if (!pred(*first1, *first2)) { - break; - } - } - - return std::make_pair(first1, first2); -} - -// c_equal() -// -// Container-based version of the <algorithm> `std::equal()` function to -// test whether two containers are equal. -// -// NOTE: the semantics of c_equal() are slightly different than those of -// equal(): while the latter iterates over the second container only up to the -// size of the first container, c_equal() also checks whether the container -// sizes are equal. This better matches expectations about c_equal() based on -// its signature. -// -// Example: -// vector v1 = <1, 2, 3>; -// vector v2 = <1, 2, 3, 4>; -// equal(std::begin(v1), std::end(v1), std::begin(v2)) returns true -// c_equal(v1, v2) returns false - -template <typename C1, typename C2> -bool c_equal(const C1& c1, const C2& c2) { - return ((container_algorithm_internal::c_size(c1) == - container_algorithm_internal::c_size(c2)) && - std::equal(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2))); -} - -// Overload of c_equal() for using a predicate evaluation other than `==` as -// the function's test condition. -template <typename C1, typename C2, typename BinaryPredicate> -bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) { - return ((container_algorithm_internal::c_size(c1) == - container_algorithm_internal::c_size(c2)) && - std::equal(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - std::forward<BinaryPredicate>(pred))); -} - -// c_is_permutation() -// -// Container-based version of the <algorithm> `std::is_permutation()` function -// to test whether a container is a permutation of another. -template <typename C1, typename C2> -bool c_is_permutation(const C1& c1, const C2& c2) { - using std::begin; - using std::end; - return c1.size() == c2.size() && - std::is_permutation(begin(c1), end(c1), begin(c2)); -} - -// Overload of c_is_permutation() for using a predicate evaluation other than -// `==` as the function's test condition. -template <typename C1, typename C2, typename BinaryPredicate> -bool c_is_permutation(const C1& c1, const C2& c2, BinaryPredicate&& pred) { - using std::begin; - using std::end; - return c1.size() == c2.size() && - std::is_permutation(begin(c1), end(c1), begin(c2), - std::forward<BinaryPredicate>(pred)); -} - -// c_search() -// -// Container-based version of the <algorithm> `std::search()` function to search -// a container for a subsequence. -template <typename Sequence1, typename Sequence2> -container_algorithm_internal::ContainerIter<Sequence1> c_search( - Sequence1& sequence, Sequence2& subsequence) { - return std::search(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(subsequence), - container_algorithm_internal::c_end(subsequence)); -} - -// Overload of c_search() for using a predicate evaluation other than -// `==` as the function's test condition. -template <typename Sequence1, typename Sequence2, typename BinaryPredicate> -container_algorithm_internal::ContainerIter<Sequence1> c_search( - Sequence1& sequence, Sequence2& subsequence, BinaryPredicate&& pred) { - return std::search(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(subsequence), - container_algorithm_internal::c_end(subsequence), - std::forward<BinaryPredicate>(pred)); -} - -// c_search_n() -// -// Container-based version of the <algorithm> `std::search_n()` function to -// search a container for the first sequence of N elements. -template <typename Sequence, typename Size, typename T> -container_algorithm_internal::ContainerIter<Sequence> c_search_n( - Sequence& sequence, Size count, T&& value) { - return std::search_n(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), count, - std::forward<T>(value)); -} - -// Overload of c_search_n() for using a predicate evaluation other than -// `==` as the function's test condition. -template <typename Sequence, typename Size, typename T, - typename BinaryPredicate> -container_algorithm_internal::ContainerIter<Sequence> c_search_n( - Sequence& sequence, Size count, T&& value, BinaryPredicate&& pred) { - return std::search_n(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), count, - std::forward<T>(value), - std::forward<BinaryPredicate>(pred)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Modifying sequence operations -//------------------------------------------------------------------------------ - -// c_copy() -// -// Container-based version of the <algorithm> `std::copy()` function to copy a -// container's elements into an iterator. -template <typename InputSequence, typename OutputIterator> -OutputIterator c_copy(const InputSequence& input, OutputIterator output) { - return std::copy(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), output); -} - -// c_copy_n() -// -// Container-based version of the <algorithm> `std::copy_n()` function to copy a -// container's first N elements into an iterator. -template <typename C, typename Size, typename OutputIterator> -OutputIterator c_copy_n(const C& input, Size n, OutputIterator output) { - return std::copy_n(container_algorithm_internal::c_begin(input), n, output); -} - -// c_copy_if() -// -// Container-based version of the <algorithm> `std::copy_if()` function to copy -// a container's elements satisfying some condition into an iterator. -template <typename InputSequence, typename OutputIterator, typename Pred> -OutputIterator c_copy_if(const InputSequence& input, OutputIterator output, - Pred&& pred) { - return std::copy_if(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), output, - std::forward<Pred>(pred)); -} - -// c_copy_backward() -// -// Container-based version of the <algorithm> `std::copy_backward()` function to -// copy a container's elements in reverse order into an iterator. -template <typename C, typename BidirectionalIterator> -BidirectionalIterator c_copy_backward(const C& src, - BidirectionalIterator dest) { - return std::copy_backward(container_algorithm_internal::c_begin(src), - container_algorithm_internal::c_end(src), dest); -} - -// c_move() -// -// Container-based version of the <algorithm> `std::move()` function to move -// a container's elements into an iterator. -template <typename C, typename OutputIterator> -OutputIterator c_move(C&& src, OutputIterator dest) { - return std::move(container_algorithm_internal::c_begin(src), - container_algorithm_internal::c_end(src), dest); -} - -// c_move_backward() -// -// Container-based version of the <algorithm> `std::move_backward()` function to -// move a container's elements into an iterator in reverse order. -template <typename C, typename BidirectionalIterator> -BidirectionalIterator c_move_backward(C&& src, BidirectionalIterator dest) { - return std::move_backward(container_algorithm_internal::c_begin(src), - container_algorithm_internal::c_end(src), dest); -} - -// c_swap_ranges() -// -// Container-based version of the <algorithm> `std::swap_ranges()` function to -// swap a container's elements with another container's elements. Swaps the -// first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). -template <typename C1, typename C2> -container_algorithm_internal::ContainerIter<C2> c_swap_ranges(C1& c1, C2& c2) { - auto first1 = container_algorithm_internal::c_begin(c1); - auto last1 = container_algorithm_internal::c_end(c1); - auto first2 = container_algorithm_internal::c_begin(c2); - auto last2 = container_algorithm_internal::c_end(c2); - - using std::swap; - for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { - swap(*first1, *first2); - } - return first2; -} - -// c_transform() -// -// Container-based version of the <algorithm> `std::transform()` function to -// transform a container's elements using the unary operation, storing the -// result in an iterator pointing to the last transformed element in the output -// range. -template <typename InputSequence, typename OutputIterator, typename UnaryOp> -OutputIterator c_transform(const InputSequence& input, OutputIterator output, - UnaryOp&& unary_op) { - return std::transform(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), output, - std::forward<UnaryOp>(unary_op)); -} - -// Overload of c_transform() for performing a transformation using a binary -// predicate. Applies `binary_op` to the first N elements of `c1` and `c2`, -// where N = min(size(c1), size(c2)). -template <typename InputSequence1, typename InputSequence2, - typename OutputIterator, typename BinaryOp> -OutputIterator c_transform(const InputSequence1& input1, - const InputSequence2& input2, OutputIterator output, - BinaryOp&& binary_op) { - auto first1 = container_algorithm_internal::c_begin(input1); - auto last1 = container_algorithm_internal::c_end(input1); - auto first2 = container_algorithm_internal::c_begin(input2); - auto last2 = container_algorithm_internal::c_end(input2); - for (; first1 != last1 && first2 != last2; - ++first1, (void)++first2, ++output) { - *output = binary_op(*first1, *first2); - } - - return output; -} - -// c_replace() -// -// Container-based version of the <algorithm> `std::replace()` function to -// replace a container's elements of some value with a new value. The container -// is modified in place. -template <typename Sequence, typename T> -void c_replace(Sequence& sequence, const T& old_value, const T& new_value) { - std::replace(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), old_value, - new_value); -} - -// c_replace_if() -// -// Container-based version of the <algorithm> `std::replace_if()` function to -// replace a container's elements of some value with a new value based on some -// condition. The container is modified in place. -template <typename C, typename Pred, typename T> -void c_replace_if(C& c, Pred&& pred, T&& new_value) { - std::replace_if(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred), std::forward<T>(new_value)); -} - -// c_replace_copy() -// -// Container-based version of the <algorithm> `std::replace_copy()` function to -// replace a container's elements of some value with a new value and return the -// results within an iterator. -template <typename C, typename OutputIterator, typename T> -OutputIterator c_replace_copy(const C& c, OutputIterator result, T&& old_value, - T&& new_value) { - return std::replace_copy(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result, - std::forward<T>(old_value), - std::forward<T>(new_value)); -} - -// c_replace_copy_if() -// -// Container-based version of the <algorithm> `std::replace_copy_if()` function -// to replace a container's elements of some value with a new value based on -// some condition, and return the results within an iterator. -template <typename C, typename OutputIterator, typename Pred, typename T> -OutputIterator c_replace_copy_if(const C& c, OutputIterator result, Pred&& pred, - T&& new_value) { - return std::replace_copy_if(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result, - std::forward<Pred>(pred), - std::forward<T>(new_value)); -} - -// c_fill() -// -// Container-based version of the <algorithm> `std::fill()` function to fill a -// container with some value. -template <typename C, typename T> -void c_fill(C& c, T&& value) { - std::fill(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), std::forward<T>(value)); -} - -// c_fill_n() -// -// Container-based version of the <algorithm> `std::fill_n()` function to fill -// the first N elements in a container with some value. -template <typename C, typename Size, typename T> -void c_fill_n(C& c, Size n, T&& value) { - std::fill_n(container_algorithm_internal::c_begin(c), n, - std::forward<T>(value)); -} - -// c_generate() -// -// Container-based version of the <algorithm> `std::generate()` function to -// assign a container's elements to the values provided by the given generator. -template <typename C, typename Generator> -void c_generate(C& c, Generator&& gen) { - std::generate(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Generator>(gen)); -} - -// c_generate_n() -// -// Container-based version of the <algorithm> `std::generate_n()` function to -// assign a container's first N elements to the values provided by the given -// generator. -template <typename C, typename Size, typename Generator> -container_algorithm_internal::ContainerIter<C> c_generate_n(C& c, Size n, - Generator&& gen) { - return std::generate_n(container_algorithm_internal::c_begin(c), n, - std::forward<Generator>(gen)); -} - -// Note: `c_xx()` <algorithm> container versions for `remove()`, `remove_if()`, -// and `unique()` are omitted, because it's not clear whether or not such -// functions should call erase on their supplied sequences afterwards. Either -// behavior would be surprising for a different set of users. - -// c_remove_copy() -// -// Container-based version of the <algorithm> `std::remove_copy()` function to -// copy a container's elements while removing any elements matching the given -// `value`. -template <typename C, typename OutputIterator, typename T> -OutputIterator c_remove_copy(const C& c, OutputIterator result, T&& value) { - return std::remove_copy(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result, - std::forward<T>(value)); -} - -// c_remove_copy_if() -// -// Container-based version of the <algorithm> `std::remove_copy_if()` function -// to copy a container's elements while removing any elements matching the given -// condition. -template <typename C, typename OutputIterator, typename Pred> -OutputIterator c_remove_copy_if(const C& c, OutputIterator result, - Pred&& pred) { - return std::remove_copy_if(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result, - std::forward<Pred>(pred)); -} - -// c_unique_copy() -// -// Container-based version of the <algorithm> `std::unique_copy()` function to -// copy a container's elements while removing any elements containing duplicate -// values. -template <typename C, typename OutputIterator> -OutputIterator c_unique_copy(const C& c, OutputIterator result) { - return std::unique_copy(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result); -} - -// Overload of c_unique_copy() for using a predicate evaluation other than -// `==` for comparing uniqueness of the element values. -template <typename C, typename OutputIterator, typename BinaryPredicate> -OutputIterator c_unique_copy(const C& c, OutputIterator result, - BinaryPredicate&& pred) { - return std::unique_copy(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), result, - std::forward<BinaryPredicate>(pred)); -} - -// c_reverse() -// -// Container-based version of the <algorithm> `std::reverse()` function to -// reverse a container's elements. -template <typename Sequence> -void c_reverse(Sequence& sequence) { - std::reverse(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// c_reverse_copy() -// -// Container-based version of the <algorithm> `std::reverse()` function to -// reverse a container's elements and write them to an iterator range. -template <typename C, typename OutputIterator> -OutputIterator c_reverse_copy(const C& sequence, OutputIterator result) { - return std::reverse_copy(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - result); -} - -// c_rotate() -// -// Container-based version of the <algorithm> `std::rotate()` function to -// shift a container's elements leftward such that the `middle` element becomes -// the first element in the container. -template <typename C, - typename Iterator = container_algorithm_internal::ContainerIter<C>> -Iterator c_rotate(C& sequence, Iterator middle) { - return absl::rotate(container_algorithm_internal::c_begin(sequence), middle, - container_algorithm_internal::c_end(sequence)); -} - -// c_rotate_copy() -// -// Container-based version of the <algorithm> `std::rotate_copy()` function to -// shift a container's elements leftward such that the `middle` element becomes -// the first element in a new iterator range. -template <typename C, typename OutputIterator> -OutputIterator c_rotate_copy( - const C& sequence, - container_algorithm_internal::ContainerIter<const C> middle, - OutputIterator result) { - return std::rotate_copy(container_algorithm_internal::c_begin(sequence), - middle, container_algorithm_internal::c_end(sequence), - result); -} - -// c_shuffle() -// -// Container-based version of the <algorithm> `std::shuffle()` function to -// randomly shuffle elements within the container using a `gen()` uniform random -// number generator. -template <typename RandomAccessContainer, typename UniformRandomBitGenerator> -void c_shuffle(RandomAccessContainer& c, UniformRandomBitGenerator&& gen) { - std::shuffle(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<UniformRandomBitGenerator>(gen)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Partition functions -//------------------------------------------------------------------------------ - -// c_is_partitioned() -// -// Container-based version of the <algorithm> `std::is_partitioned()` function -// to test whether all elements in the container for which `pred` returns `true` -// precede those for which `pred` is `false`. -template <typename C, typename Pred> -bool c_is_partitioned(const C& c, Pred&& pred) { - return std::is_partitioned(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_partition() -// -// Container-based version of the <algorithm> `std::partition()` function -// to rearrange all elements in a container in such a way that all elements for -// which `pred` returns `true` precede all those for which it returns `false`, -// returning an iterator to the first element of the second group. -template <typename C, typename Pred> -container_algorithm_internal::ContainerIter<C> c_partition(C& c, Pred&& pred) { - return std::partition(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_stable_partition() -// -// Container-based version of the <algorithm> `std::stable_partition()` function -// to rearrange all elements in a container in such a way that all elements for -// which `pred` returns `true` precede all those for which it returns `false`, -// preserving the relative ordering between the two groups. The function returns -// an iterator to the first element of the second group. -template <typename C, typename Pred> -container_algorithm_internal::ContainerIter<C> c_stable_partition(C& c, - Pred&& pred) { - return std::stable_partition(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -// c_partition_copy() -// -// Container-based version of the <algorithm> `std::partition_copy()` function -// to partition a container's elements and return them into two iterators: one -// for which `pred` returns `true`, and one for which `pred` returns `false.` - -template <typename C, typename OutputIterator1, typename OutputIterator2, - typename Pred> -std::pair<OutputIterator1, OutputIterator2> c_partition_copy( - const C& c, OutputIterator1 out_true, OutputIterator2 out_false, - Pred&& pred) { - return std::partition_copy(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), out_true, - out_false, std::forward<Pred>(pred)); -} - -// c_partition_point() -// -// Container-based version of the <algorithm> `std::partition_point()` function -// to return the first element of an already partitioned container for which -// the given `pred` is not `true`. -template <typename C, typename Pred> -container_algorithm_internal::ContainerIter<C> c_partition_point(C& c, - Pred&& pred) { - return std::partition_point(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Pred>(pred)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Sorting functions -//------------------------------------------------------------------------------ - -// c_sort() -// -// Container-based version of the <algorithm> `std::sort()` function -// to sort elements in ascending order of their values. -template <typename C> -void c_sort(C& c) { - std::sort(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_sort() for performing a `comp` comparison other than the -// default `operator<`. -template <typename C, typename Compare> -void c_sort(C& c, Compare&& comp) { - std::sort(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_stable_sort() -// -// Container-based version of the <algorithm> `std::stable_sort()` function -// to sort elements in ascending order of their values, preserving the order -// of equivalents. -template <typename C> -void c_stable_sort(C& c) { - std::stable_sort(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_stable_sort() for performing a `comp` comparison other than the -// default `operator<`. -template <typename C, typename Compare> -void c_stable_sort(C& c, Compare&& comp) { - std::stable_sort(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_is_sorted() -// -// Container-based version of the <algorithm> `std::is_sorted()` function -// to evaluate whether the given container is sorted in ascending order. -template <typename C> -bool c_is_sorted(const C& c) { - return std::is_sorted(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// c_is_sorted() overload for performing a `comp` comparison other than the -// default `operator<`. -template <typename C, typename Compare> -bool c_is_sorted(const C& c, Compare&& comp) { - return std::is_sorted(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_partial_sort() -// -// Container-based version of the <algorithm> `std::partial_sort()` function -// to rearrange elements within a container such that elements before `middle` -// are sorted in ascending order. -template <typename RandomAccessContainer> -void c_partial_sort( - RandomAccessContainer& sequence, - container_algorithm_internal::ContainerIter<RandomAccessContainer> middle) { - std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_partial_sort() for performing a `comp` comparison other than -// the default `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_partial_sort( - RandomAccessContainer& sequence, - container_algorithm_internal::ContainerIter<RandomAccessContainer> middle, - Compare&& comp) { - std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_partial_sort_copy() -// -// Container-based version of the <algorithm> `std::partial_sort_copy()` -// function to sort the elements in the given range `result` within the larger -// `sequence` in ascending order (and using `result` as the output parameter). -// At most min(result.last - result.first, sequence.last - sequence.first) -// elements from the sequence will be stored in the result. -template <typename C, typename RandomAccessContainer> -container_algorithm_internal::ContainerIter<RandomAccessContainer> -c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { - return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(result), - container_algorithm_internal::c_end(result)); -} - -// Overload of c_partial_sort_copy() for performing a `comp` comparison other -// than the default `operator<`. -template <typename C, typename RandomAccessContainer, typename Compare> -container_algorithm_internal::ContainerIter<RandomAccessContainer> -c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, - Compare&& comp) { - return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - container_algorithm_internal::c_begin(result), - container_algorithm_internal::c_end(result), - std::forward<Compare>(comp)); -} - -// c_is_sorted_until() -// -// Container-based version of the <algorithm> `std::is_sorted_until()` function -// to return the first element within a container that is not sorted in -// ascending order as an iterator. -template <typename C> -container_algorithm_internal::ContainerIter<C> c_is_sorted_until(C& c) { - return std::is_sorted_until(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_is_sorted_until() for performing a `comp` comparison other than -// the default `operator<`. -template <typename C, typename Compare> -container_algorithm_internal::ContainerIter<C> c_is_sorted_until( - C& c, Compare&& comp) { - return std::is_sorted_until(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_nth_element() -// -// Container-based version of the <algorithm> `std::nth_element()` function -// to rearrange the elements within a container such that the `nth` element -// would be in that position in an ordered sequence; other elements may be in -// any order, except that all preceding `nth` will be less than that element, -// and all following `nth` will be greater than that element. -template <typename RandomAccessContainer> -void c_nth_element( - RandomAccessContainer& sequence, - container_algorithm_internal::ContainerIter<RandomAccessContainer> nth) { - std::nth_element(container_algorithm_internal::c_begin(sequence), nth, - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_nth_element() for performing a `comp` comparison other than -// the default `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_nth_element( - RandomAccessContainer& sequence, - container_algorithm_internal::ContainerIter<RandomAccessContainer> nth, - Compare&& comp) { - std::nth_element(container_algorithm_internal::c_begin(sequence), nth, - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Binary Search -//------------------------------------------------------------------------------ - -// c_lower_bound() -// -// Container-based version of the <algorithm> `std::lower_bound()` function -// to return an iterator pointing to the first element in a sorted container -// which does not compare less than `value`. -template <typename Sequence, typename T> -container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( - Sequence& sequence, T&& value) { - return std::lower_bound(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value)); -} - -// Overload of c_lower_bound() for performing a `comp` comparison other than -// the default `operator<`. -template <typename Sequence, typename T, typename Compare> -container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( - Sequence& sequence, T&& value, Compare&& comp) { - return std::lower_bound(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); -} - -// c_upper_bound() -// -// Container-based version of the <algorithm> `std::upper_bound()` function -// to return an iterator pointing to the first element in a sorted container -// which is greater than `value`. -template <typename Sequence, typename T> -container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( - Sequence& sequence, T&& value) { - return std::upper_bound(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value)); -} - -// Overload of c_upper_bound() for performing a `comp` comparison other than -// the default `operator<`. -template <typename Sequence, typename T, typename Compare> -container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( - Sequence& sequence, T&& value, Compare&& comp) { - return std::upper_bound(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); -} - -// c_equal_range() -// -// Container-based version of the <algorithm> `std::equal_range()` function -// to return an iterator pair pointing to the first and last elements in a -// sorted container which compare equal to `value`. -template <typename Sequence, typename T> -container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> -c_equal_range(Sequence& sequence, T&& value) { - return std::equal_range(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value)); -} - -// Overload of c_equal_range() for performing a `comp` comparison other than -// the default `operator<`. -template <typename Sequence, typename T, typename Compare> -container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> -c_equal_range(Sequence& sequence, T&& value, Compare&& comp) { - return std::equal_range(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); -} - -// c_binary_search() -// -// Container-based version of the <algorithm> `std::binary_search()` function -// to test if any element in the sorted container contains a value equivalent to -// 'value'. -template <typename Sequence, typename T> -bool c_binary_search(Sequence&& sequence, T&& value) { - return std::binary_search(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value)); -} - -// Overload of c_binary_search() for performing a `comp` comparison other than -// the default `operator<`. -template <typename Sequence, typename T, typename Compare> -bool c_binary_search(Sequence&& sequence, T&& value, Compare&& comp) { - return std::binary_search(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value), - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Merge functions -//------------------------------------------------------------------------------ - -// c_merge() -// -// Container-based version of the <algorithm> `std::merge()` function -// to merge two sorted containers into a single sorted iterator. -template <typename C1, typename C2, typename OutputIterator> -OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result) { - return std::merge(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), result); -} - -// Overload of c_merge() for performing a `comp` comparison other than -// the default `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> -OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result, - Compare&& comp) { - return std::merge(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), result, - std::forward<Compare>(comp)); -} - -// c_inplace_merge() -// -// Container-based version of the <algorithm> `std::inplace_merge()` function -// to merge a supplied iterator `middle` into a container. -template <typename C> -void c_inplace_merge(C& c, - container_algorithm_internal::ContainerIter<C> middle) { - std::inplace_merge(container_algorithm_internal::c_begin(c), middle, - container_algorithm_internal::c_end(c)); -} - -// Overload of c_inplace_merge() for performing a merge using a `comp` other -// than `operator<`. -template <typename C, typename Compare> -void c_inplace_merge(C& c, - container_algorithm_internal::ContainerIter<C> middle, - Compare&& comp) { - std::inplace_merge(container_algorithm_internal::c_begin(c), middle, - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_includes() -// -// Container-based version of the <algorithm> `std::includes()` function -// to test whether a sorted container `c1` entirely contains another sorted -// container `c2`. -template <typename C1, typename C2> -bool c_includes(const C1& c1, const C2& c2) { - return std::includes(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2)); -} - -// Overload of c_includes() for performing a merge using a `comp` other than -// `operator<`. -template <typename C1, typename C2, typename Compare> -bool c_includes(const C1& c1, const C2& c2, Compare&& comp) { - return std::includes(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), - std::forward<Compare>(comp)); -} - -// c_set_union() -// -// Container-based version of the <algorithm> `std::set_union()` function -// to return an iterator containing the union of two containers; duplicate -// values are not copied into the output. -template <typename C1, typename C2, typename OutputIterator, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { - return std::set_union(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output); -} - -// Overload of c_set_union() for performing a merge using a `comp` other than -// `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, - Compare&& comp) { - return std::set_union(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); -} - -// c_set_intersection() -// -// Container-based version of the <algorithm> `std::set_intersection()` function -// to return an iterator containing the intersection of two containers. -template <typename C1, typename C2, typename OutputIterator, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_intersection(const C1& c1, const C2& c2, - OutputIterator output) { - return std::set_intersection(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output); -} - -// Overload of c_set_intersection() for performing a merge using a `comp` other -// than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_intersection(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { - return std::set_intersection(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); -} - -// c_set_difference() -// -// Container-based version of the <algorithm> `std::set_difference()` function -// to return an iterator containing elements present in the first container but -// not in the second. -template <typename C1, typename C2, typename OutputIterator, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_difference(const C1& c1, const C2& c2, - OutputIterator output) { - return std::set_difference(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output); -} - -// Overload of c_set_difference() for performing a merge using a `comp` other -// than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_difference(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { - return std::set_difference(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); -} - -// c_set_symmetric_difference() -// -// Container-based version of the <algorithm> `std::set_symmetric_difference()` -// function to return an iterator containing elements present in either one -// container or the other, but not both. -template <typename C1, typename C2, typename OutputIterator, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, - OutputIterator output) { - return std::set_symmetric_difference( - container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output); -} - -// Overload of c_set_symmetric_difference() for performing a merge using a -// `comp` other than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C1>::value, - void>::type, - typename = typename std::enable_if< - !container_algorithm_internal::IsUnorderedContainer<C2>::value, - void>::type> -OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, - OutputIterator output, - Compare&& comp) { - return std::set_symmetric_difference( - container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Heap functions -//------------------------------------------------------------------------------ - -// c_push_heap() -// -// Container-based version of the <algorithm> `std::push_heap()` function -// to push a value onto a container heap. -template <typename RandomAccessContainer> -void c_push_heap(RandomAccessContainer& sequence) { - std::push_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_push_heap() for performing a push operation on a heap using a -// `comp` other than `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_push_heap(RandomAccessContainer& sequence, Compare&& comp) { - std::push_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_pop_heap() -// -// Container-based version of the <algorithm> `std::pop_heap()` function -// to pop a value from a heap container. -template <typename RandomAccessContainer> -void c_pop_heap(RandomAccessContainer& sequence) { - std::pop_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_pop_heap() for performing a pop operation on a heap using a -// `comp` other than `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_pop_heap(RandomAccessContainer& sequence, Compare&& comp) { - std::pop_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_make_heap() -// -// Container-based version of the <algorithm> `std::make_heap()` function -// to make a container a heap. -template <typename RandomAccessContainer> -void c_make_heap(RandomAccessContainer& sequence) { - std::make_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_make_heap() for performing heap comparisons using a -// `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -void c_make_heap(RandomAccessContainer& sequence, Compare&& comp) { - std::make_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_sort_heap() -// -// Container-based version of the <algorithm> `std::sort_heap()` function -// to sort a heap into ascending order (after which it is no longer a heap). -template <typename RandomAccessContainer> -void c_sort_heap(RandomAccessContainer& sequence) { - std::sort_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_sort_heap() for performing heap comparisons using a -// `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -void c_sort_heap(RandomAccessContainer& sequence, Compare&& comp) { - std::sort_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_is_heap() -// -// Container-based version of the <algorithm> `std::is_heap()` function -// to check whether the given container is a heap. -template <typename RandomAccessContainer> -bool c_is_heap(const RandomAccessContainer& sequence) { - return std::is_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_is_heap() for performing heap comparisons using a -// `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -bool c_is_heap(const RandomAccessContainer& sequence, Compare&& comp) { - return std::is_heap(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_is_heap_until() -// -// Container-based version of the <algorithm> `std::is_heap_until()` function -// to find the first element in a given container which is not in heap order. -template <typename RandomAccessContainer> -container_algorithm_internal::ContainerIter<RandomAccessContainer> -c_is_heap_until(RandomAccessContainer& sequence) { - return std::is_heap_until(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_is_heap_until() for performing heap comparisons using a -// `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -container_algorithm_internal::ContainerIter<RandomAccessContainer> -c_is_heap_until(RandomAccessContainer& sequence, Compare&& comp) { - return std::is_heap_until(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Min/max -//------------------------------------------------------------------------------ - -// c_min_element() -// -// Container-based version of the <algorithm> `std::min_element()` function -// to return an iterator pointing to the element with the smallest value, using -// `operator<` to make the comparisons. -template <typename Sequence> -container_algorithm_internal::ContainerIter<Sequence> c_min_element( - Sequence& sequence) { - return std::min_element(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_min_element() for performing a `comp` comparison other than -// `operator<`. -template <typename Sequence, typename Compare> -container_algorithm_internal::ContainerIter<Sequence> c_min_element( - Sequence& sequence, Compare&& comp) { - return std::min_element(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_max_element() -// -// Container-based version of the <algorithm> `std::max_element()` function -// to return an iterator pointing to the element with the largest value, using -// `operator<` to make the comparisons. -template <typename Sequence> -container_algorithm_internal::ContainerIter<Sequence> c_max_element( - Sequence& sequence) { - return std::max_element(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence)); -} - -// Overload of c_max_element() for performing a `comp` comparison other than -// `operator<`. -template <typename Sequence, typename Compare> -container_algorithm_internal::ContainerIter<Sequence> c_max_element( - Sequence& sequence, Compare&& comp) { - return std::max_element(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); -} - -// c_minmax_element() -// -// Container-based version of the <algorithm> `std::minmax_element()` function -// to return a pair of iterators pointing to the elements containing the -// smallest and largest values, respectively, using `operator<` to make the -// comparisons. -template <typename C> -container_algorithm_internal::ContainerIterPairType<C, C> -c_minmax_element(C& c) { - return std::minmax_element(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_minmax_element() for performing `comp` comparisons other than -// `operator<`. -template <typename C, typename Compare> -container_algorithm_internal::ContainerIterPairType<C, C> -c_minmax_element(C& c, Compare&& comp) { - return std::minmax_element(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <algorithm> Lexicographical Comparisons -//------------------------------------------------------------------------------ - -// c_lexicographical_compare() -// -// Container-based version of the <algorithm> `std::lexicographical_compare()` -// function to lexicographically compare (e.g. sort words alphabetically) two -// container sequences. The comparison is performed using `operator<`. Note -// that capital letters ("A-Z") have ASCII values less than lowercase letters -// ("a-z"). -template <typename Sequence1, typename Sequence2> -bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2) { - return std::lexicographical_compare( - container_algorithm_internal::c_begin(sequence1), - container_algorithm_internal::c_end(sequence1), - container_algorithm_internal::c_begin(sequence2), - container_algorithm_internal::c_end(sequence2)); -} - -// Overload of c_lexicographical_compare() for performing a lexicographical -// comparison using a `comp` operator instead of `operator<`. -template <typename Sequence1, typename Sequence2, typename Compare> -bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2, - Compare&& comp) { - return std::lexicographical_compare( - container_algorithm_internal::c_begin(sequence1), - container_algorithm_internal::c_end(sequence1), - container_algorithm_internal::c_begin(sequence2), - container_algorithm_internal::c_end(sequence2), - std::forward<Compare>(comp)); -} - -// c_next_permutation() -// -// Container-based version of the <algorithm> `std::next_permutation()` function -// to rearrange a container's elements into the next lexicographically greater -// permutation. -template <typename C> -bool c_next_permutation(C& c) { - return std::next_permutation(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_next_permutation() for performing a lexicographical -// comparison using a `comp` operator instead of `operator<`. -template <typename C, typename Compare> -bool c_next_permutation(C& c, Compare&& comp) { - return std::next_permutation(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -// c_prev_permutation() -// -// Container-based version of the <algorithm> `std::prev_permutation()` function -// to rearrange a container's elements into the next lexicographically lesser -// permutation. -template <typename C> -bool c_prev_permutation(C& c) { - return std::prev_permutation(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c)); -} - -// Overload of c_prev_permutation() for performing a lexicographical -// comparison using a `comp` operator instead of `operator<`. -template <typename C, typename Compare> -bool c_prev_permutation(C& c, Compare&& comp) { - return std::prev_permutation(container_algorithm_internal::c_begin(c), - container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); -} - -//------------------------------------------------------------------------------ -// <numeric> algorithms -//------------------------------------------------------------------------------ - -// c_iota() -// -// Container-based version of the <algorithm> `std::iota()` function -// to compute successive values of `value`, as if incremented with `++value` -// after each element is written. and write them to the container. -template <typename Sequence, typename T> -void c_iota(Sequence& sequence, T&& value) { - std::iota(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(value)); -} -// c_accumulate() -// -// Container-based version of the <algorithm> `std::accumulate()` function -// to accumulate the element values of a container to `init` and return that -// accumulation by value. -// -// Note: Due to a language technicality this function has return type -// absl::decay_t<T>. As a user of this function you can casually read -// this as "returns T by value" and assume it does the right thing. -template <typename Sequence, typename T> -decay_t<T> c_accumulate(const Sequence& sequence, T&& init) { - return std::accumulate(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(init)); -} - -// Overload of c_accumulate() for using a binary operations other than -// addition for computing the accumulation. -template <typename Sequence, typename T, typename BinaryOp> -decay_t<T> c_accumulate(const Sequence& sequence, T&& init, - BinaryOp&& binary_op) { - return std::accumulate(container_algorithm_internal::c_begin(sequence), - container_algorithm_internal::c_end(sequence), - std::forward<T>(init), - std::forward<BinaryOp>(binary_op)); -} - -// c_inner_product() -// -// Container-based version of the <algorithm> `std::inner_product()` function -// to compute the cumulative inner product of container element pairs. -// -// Note: Due to a language technicality this function has return type -// absl::decay_t<T>. As a user of this function you can casually read -// this as "returns T by value" and assume it does the right thing. -template <typename Sequence1, typename Sequence2, typename T> -decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2, - T&& sum) { - return std::inner_product(container_algorithm_internal::c_begin(factors1), - container_algorithm_internal::c_end(factors1), - container_algorithm_internal::c_begin(factors2), - std::forward<T>(sum)); -} - -// Overload of c_inner_product() for using binary operations other than -// `operator+` (for computing the accumulation) and `operator*` (for computing -// the product between the two container's element pair). -template <typename Sequence1, typename Sequence2, typename T, - typename BinaryOp1, typename BinaryOp2> -decay_t<T> c_inner_product(const Sequence1& factors1, const Sequence2& factors2, - T&& sum, BinaryOp1&& op1, BinaryOp2&& op2) { - return std::inner_product(container_algorithm_internal::c_begin(factors1), - container_algorithm_internal::c_end(factors1), - container_algorithm_internal::c_begin(factors2), - std::forward<T>(sum), std::forward<BinaryOp1>(op1), - std::forward<BinaryOp2>(op2)); -} - -// c_adjacent_difference() -// -// Container-based version of the <algorithm> `std::adjacent_difference()` -// function to compute the difference between each element and the one preceding -// it and write it to an iterator. -template <typename InputSequence, typename OutputIt> -OutputIt c_adjacent_difference(const InputSequence& input, - OutputIt output_first) { - return std::adjacent_difference(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), - output_first); -} - -// Overload of c_adjacent_difference() for using a binary operation other than -// subtraction to compute the adjacent difference. -template <typename InputSequence, typename OutputIt, typename BinaryOp> -OutputIt c_adjacent_difference(const InputSequence& input, - OutputIt output_first, BinaryOp&& op) { - return std::adjacent_difference(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), - output_first, std::forward<BinaryOp>(op)); -} - -// c_partial_sum() -// -// Container-based version of the <algorithm> `std::partial_sum()` function -// to compute the partial sum of the elements in a sequence and write them -// to an iterator. The partial sum is the sum of all element values so far in -// the sequence. -template <typename InputSequence, typename OutputIt> -OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first) { - return std::partial_sum(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), - output_first); -} - -// Overload of c_partial_sum() for using a binary operation other than addition -// to compute the "partial sum". -template <typename InputSequence, typename OutputIt, typename BinaryOp> -OutputIt c_partial_sum(const InputSequence& input, OutputIt output_first, - BinaryOp&& op) { - return std::partial_sum(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), - output_first, std::forward<BinaryOp>(op)); -} - -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_ALGORITHM_CONTAINER_H_ diff --git a/third_party/abseil_cpp/absl/algorithm/container_test.cc b/third_party/abseil_cpp/absl/algorithm/container_test.cc deleted file mode 100644 index 605afc8040d7..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/container_test.cc +++ /dev/null @@ -1,1124 +0,0 @@ -// 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 <functional> -#include <initializer_list> -#include <iterator> -#include <list> -#include <memory> -#include <ostream> -#include <random> -#include <set> -#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/macros.h" -#include "absl/memory/memory.h" -#include "absl/types/span.h" - -namespace { - -using ::testing::Each; -using ::testing::ElementsAre; -using ::testing::Gt; -using ::testing::IsNull; -using ::testing::Lt; -using ::testing::Pointee; -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_F(NonMutatingTest, Distance) { - EXPECT_EQ(container_.size(), absl::c_distance(container_)); - EXPECT_EQ(sequence_.size(), absl::c_distance(sequence_)); - EXPECT_EQ(vector_.size(), absl::c_distance(vector_)); - EXPECT_EQ(ABSL_ARRAYSIZE(array_), absl::c_distance(array_)); - - // Works with a temporary argument. - EXPECT_EQ(vector_.size(), 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, 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_); -} - -TEST_F(NonMutatingTest, FindFirstOfWithPredicate) { - absl::c_find_first_of(container_, sequence_, BinPredicate); - absl::c_find_first_of(sequence_, container_, 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, 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, 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(absl::make_unique<int>(1)); - src.emplace_back(absl::make_unique<int>(2)); - src.emplace_back(absl::make_unique<int>(3)); - src.emplace_back(absl::make_unique<int>(4)); - src.emplace_back(absl::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(absl::make_unique<int>(1)); - actual.emplace_back(absl::make_unique<int>(2)); - actual.emplace_back(absl::make_unique<int>(3)); - actual.emplace_back(absl::make_unique<int>(4)); - actual.emplace_back(absl::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(absl::make_unique<int>(1)); - src.emplace_back(absl::make_unique<int>(2)); - src.emplace_back(absl::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, 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); - - z.clear(); - y.pop_back(); - end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>()); - EXPECT_EQ(std::vector<int>({1, 5}), z); - *end = 7; - EXPECT_EQ(std::vector<int>({1, 5, 7}), z); - - z.clear(); - std::swap(x, y); - end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>()); - EXPECT_EQ(std::vector<int>({1, 5}), z); - *end = 7; - EXPECT_EQ(std::vector<int>({1, 5, 7}), z); -} - -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)); -} - -// 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, 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, 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, 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, std::random_device()); - EXPECT_THAT(actual, UnorderedElementsAre(1, 2, 3, 4, 5)); -} - -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); -} - -} // namespace diff --git a/third_party/abseil_cpp/absl/algorithm/equal_benchmark.cc b/third_party/abseil_cpp/absl/algorithm/equal_benchmark.cc deleted file mode 100644 index 7bf62c9a7f56..000000000000 --- a/third_party/abseil_cpp/absl/algorithm/equal_benchmark.cc +++ /dev/null @@ -1,126 +0,0 @@ -// 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 <cstdint> -#include <cstring> - -#include "benchmark/benchmark.h" -#include "absl/algorithm/algorithm.h" - -namespace { - -// The range of sequence sizes to benchmark. -constexpr int kMinBenchmarkSize = 1024; -constexpr int kMaxBenchmarkSize = 8 * 1024 * 1024; - -// A user-defined type for use in equality benchmarks. Note that we expect -// std::memcmp to win for this type: libstdc++'s std::equal only defers to -// memcmp for integral types. This is because it is not straightforward to -// guarantee that std::memcmp would produce a result "as-if" compared by -// operator== for other types (example gotchas: NaN floats, structs with -// padding). -struct EightBits { - explicit EightBits(int /* unused */) : data(0) {} - bool operator==(const EightBits& rhs) const { return data == rhs.data; } - uint8_t data; -}; - -template <typename T> -void BM_absl_equal_benchmark(benchmark::State& state) { - std::vector<T> xs(state.range(0), T(0)); - std::vector<T> ys = xs; - while (state.KeepRunning()) { - const bool same = absl::equal(xs.begin(), xs.end(), ys.begin(), ys.end()); - benchmark::DoNotOptimize(same); - } -} - -template <typename T> -void BM_std_equal_benchmark(benchmark::State& state) { - std::vector<T> xs(state.range(0), T(0)); - std::vector<T> ys = xs; - while (state.KeepRunning()) { - const bool same = std::equal(xs.begin(), xs.end(), ys.begin()); - benchmark::DoNotOptimize(same); - } -} - -template <typename T> -void BM_memcmp_benchmark(benchmark::State& state) { - std::vector<T> xs(state.range(0), T(0)); - std::vector<T> ys = xs; - while (state.KeepRunning()) { - const bool same = - std::memcmp(xs.data(), ys.data(), xs.size() * sizeof(T)) == 0; - benchmark::DoNotOptimize(same); - } -} - -// The expectation is that the compiler should be able to elide the equality -// comparison altogether for sufficiently simple types. -template <typename T> -void BM_absl_equal_self_benchmark(benchmark::State& state) { - std::vector<T> xs(state.range(0), T(0)); - while (state.KeepRunning()) { - const bool same = absl::equal(xs.begin(), xs.end(), xs.begin(), xs.end()); - benchmark::DoNotOptimize(same); - } -} - -BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint8_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint8_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint8_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint8_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); - -BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint16_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint16_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint16_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint16_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); - -BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint32_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint32_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint32_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint32_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); - -BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, uint64_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_std_equal_benchmark, uint64_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_memcmp_benchmark, uint64_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, uint64_t) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); - -BENCHMARK_TEMPLATE(BM_absl_equal_benchmark, EightBits) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_std_equal_benchmark, EightBits) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_memcmp_benchmark, EightBits) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); -BENCHMARK_TEMPLATE(BM_absl_equal_self_benchmark, EightBits) - ->Range(kMinBenchmarkSize, kMaxBenchmarkSize); - -} // namespace |