// 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 <cstddef>

#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/config.h"

#include "absl/base/internal/hardening.h"

#include "absl/base/internal/iterator_traits.h"

#include "absl/base/macros.h"

#include "absl/meta/type_traits.h"

#ifdef __cpp_lib_span

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

#endif

namespace absl {

ABSL_NAMESPACE_BEGIN

template <typename T>

class Span;

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(

    std::declval<ContainerIter<C1>>(), std::declval<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::c_begin(c),

//            container_algorithm_internal::c_end(c));

// These are meant for internal use only.

template <typename C>

constexpr ContainerIter<C> c_begin(C& c) {

  return begin(c);

}

template <typename C>

constexpr ContainerIter<C> c_end(C& c) {

  return end(c);

}

// Helper to check that the `OutputRange` has enough space.

// Only performs the check if the iterators are ForwardIterators or better.

template <typename InputSequence, typename Size, typename OutputRange>

constexpr void AssertCopyNSize(InputSequence& input, Size n,

                               OutputRange& output) {

  using InputIter = ContainerIter<InputSequence>;

  using OutputIter = ContainerIter<OutputRange>;

  if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value) {

    base_internal::HardeningAssertLE(

        n, std::distance(container_algorithm_internal::c_begin(input),

                         container_algorithm_internal::c_end(input)));

  }

  if constexpr (base_internal::IsAtLeastForwardIterator<OutputIter>::value) {

    base_internal::HardeningAssertLE(

        n, std::distance(container_algorithm_internal::c_begin(output),

                         container_algorithm_internal::c_end(output)));

  }

}

template <typename InputSequence, typename OutputRange>

constexpr void AssertCopySize(InputSequence& input, OutputRange& output) {

  using InputIter = ContainerIter<InputSequence>;

  using OutputIter = ContainerIter<OutputRange>;

  if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value &&

                base_internal::IsAtLeastForwardIterator<OutputIter>::value) {

    base_internal::HardeningAssertLE(

        std::distance(container_algorithm_internal::c_begin(input),

                      container_algorithm_internal::c_end(input)),

        std::distance(container_algorithm_internal::c_begin(output),

                      container_algorithm_internal::c_end(output)));

  }

}

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

template <typename T, typename = void>

struct HasBeginEnd : std::false_type {};

template <typename T>

struct HasBeginEnd<T, std::void_t<decltype(container_algorithm_internal::begin(

                                      std::declval<T (*)()>()())),

                                  decltype(container_algorithm_internal::end(

                                      std::declval<T (*)()>()()))>>

    : std::true_type {};

// We don't support multidimensional arrays yet

template <class T>

using IsMultidimensionalArray = std::is_array<std::remove_extent_t<T>>;

template <typename Iter, typename = void>

struct IsIterator : std::false_type {};

template <typename Iter>

struct IsIterator<

    Iter, std::void_t<typename std::iterator_traits<Iter>::iterator_category>>

    : std::true_type {};

template <typename C, typename OutputIterator>

using ResultOfRangeToIteratorTransfer =

    std::enable_if_t<container_algorithm_internal::IsIterator<

                         absl::remove_cvref_t<OutputIterator>>::value &&

                         !container_algorithm_internal::IsMultidimensionalArray<

                             std::remove_reference_t<C>>::value,

                     std::decay_t<OutputIterator>>;

// Similar to std::is_pointer, but for testing if a type is a span.

//

// Note that subclasses of spans do not automatically qualify as spans, as they

// may deviate from the ownership assumption of a span.

template <typename T>

struct IsSpan

    : std::conditional_t<std::is_same_v<T, std::remove_cv_t<T>>,

                         std::false_type, IsSpan<std::remove_cv_t<T>>> {};

template <typename T>

struct IsSpan<absl::Span<T>> : std::true_type {};

#ifdef __cpp_lib_span

template <typename T, size_t Extent>

struct IsSpan<std::span<T, Extent>> : std::true_type {};

#endif

// Indicates whether the given type is safe to pass as a sink to a function such

// as absl::c_fill(). Similar idea as std::ranges::borrowed_range.

//

// We are deliberately conservative here and only support lvalues and spans for

// now, in order to avoid divergence from C++17 or potentially unforeseen

// consequences. If needed in the future, we can probably extend this to all

// types that satisfy std::ranges::borrowed_range.

template <typename C>

using IsPermissibleDestinationRange =

    std::conditional_t<std::is_lvalue_reference_v<C>, std::true_type,

                       IsSpan<C>>;

template <typename C, typename OutputRange>

using ResultOfRangeToRangeTransfer =

    std::enable_if_t<container_algorithm_internal::HasBeginEnd<

                         std::add_lvalue_reference_t<OutputRange>>::value &&

                         !container_algorithm_internal::IsMultidimensionalArray<

                             std::remove_reference_t<OutputRange>>::value &&

                         !container_algorithm_internal::IsMultidimensionalArray<

                             std::remove_reference_t<C>>::value &&

                         container_algorithm_internal::

                             IsPermissibleDestinationRange<OutputRange>::value,

                     void>;

}  // 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.

//

// For a generalization that uses a predicate, see absl::c_any_of().

template <typename C, typename EqualityComparable>

constexpr bool c_linear_search(const C& c, EqualityComparable&& value) {

  return absl::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>

constexpr 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 if all elements within a container satisfy a condition.

template <typename C, typename Pred>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr std::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>

constexpr 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_contains()

//

// Container-based version of the <algorithm> `std::ranges::contains()` C++23

// function to search a container for a value.

template <typename Sequence, typename T>

constexpr bool c_contains(const Sequence& sequence, T&& value) {

  return absl::c_find(sequence, std::forward<T>(value)) !=

         container_algorithm_internal::c_end(sequence);

}

// 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr container_algorithm_internal::ContainerIter<C1> c_find_first_of(

    C1& container, const 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>

constexpr container_algorithm_internal::ContainerIter<C1> c_find_first_of(

    C1& container, const 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr container_algorithm_internal::ContainerIterPairType<C1, C2>

c_mismatch(C1& c1, C2& c2) {

  return std::mismatch(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_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>

constexpr container_algorithm_internal::ContainerIterPairType<C1, C2>

c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) {

  return std::mismatch(container_algorithm_internal::c_begin(c1),

                       container_algorithm_internal::c_end(c1),

                       container_algorithm_internal::c_begin(c2),

                       container_algorithm_internal::c_end(c2), pred);

}

// c_equal()

//

// Container-based version of the <algorithm> `std::equal()` function to

// test whether two containers are equal.

template <typename C1, typename C2>

constexpr bool c_equal(const C1& c1, const C2& c2) {

  return std::equal(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_equal() for using a predicate evaluation other than `==` as

// the function's test condition.

template <typename C1, typename C2, typename BinaryPredicate>

constexpr bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {

  return std::equal(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<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>

constexpr bool c_is_permutation(const C1& c1, const C2& c2) {

  return std::is_permutation(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_is_permutation() for using a predicate evaluation other than

// `==` as the function's test condition.

template <typename C1, typename C2, typename BinaryPredicate>

constexpr bool c_is_permutation(const C1& c1, const C2& c2,

                                BinaryPredicate&& pred) {

  return std::is_permutation(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<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>

constexpr 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>

constexpr 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_contains_subrange()

//

// Container-based version of the <algorithm> `std::ranges::contains_subrange()`

// C++23 function to search a container for a subsequence.

template <typename Sequence1, typename Sequence2>

constexpr bool c_contains_subrange(Sequence1& sequence,

                                   Sequence2& subsequence) {

  return absl::c_search(sequence, subsequence) !=

         container_algorithm_internal::c_end(sequence);

}

// Overload of c_contains_subrange() for using a predicate evaluation other than

// `==` as the function's test condition.

template <typename Sequence1, typename Sequence2, typename BinaryPredicate>

constexpr bool c_contains_subrange(Sequence1& sequence, Sequence2& subsequence,

                                   BinaryPredicate&& pred) {

  return absl::c_search(sequence, subsequence,

                        std::forward<BinaryPredicate>(pred)) !=

         container_algorithm_internal::c_end(sequence);

}

// 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>

constexpr 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>

constexpr 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>

constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer<

    InputSequence, OutputIterator>

c_copy(const InputSequence& input, OutputIterator&& output) {

  return std::copy(container_algorithm_internal::c_begin(input),

                   container_algorithm_internal::c_end(input),

                   std::forward<OutputIterator>(output));

}

// Copies elements from `input` to `output`. `absl::c_copy(input, output)` is

// equivalent to `std::copy(std::begin(input), std::end(input),

// std::begin(output))`.

//

// The `output` container must be large enough to hold all elements of `input`;

// this function does not resize `output`.

// If `std::size(input) > std::size(output)`, behavior is undefined.

// If `std::size(output) > std::size(input)`, only `std::size(input)` elements

// are copied, and `output` is not truncated.

template <typename InputSequence, typename OutputRange>

constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer<

    InputSequence, OutputRange>

c_copy(const InputSequence& input, OutputRange&& output) {

  container_algorithm_internal::AssertCopySize(input, output);

  absl::c_copy(input, container_algorithm_internal::c_begin(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>

constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer<

    C, OutputIterator>

c_copy_n(const C& input, Size n, OutputIterator&& output) {

  return std::copy_n(container_algorithm_internal::c_begin(input), n,

                     std::forward<OutputIterator>(output));

}

// Copies the first `n` elements from `input` to `output`.

// `absl::c_copy_n(input, n, output)` is equivalent to

// `std::copy_n(std::begin(input), n, std::begin(output))`.

//

// The `output` container must be large enough to hold N elements; this function

// does not resize `output`.

//

// If `n > std::size(output)` or `n > std::size(input)`, behavior is

// undefined.

// If `std::size(output) > n`, only `n` elements are copied, and `output` is not

// truncated.

template <typename C, typename Size, typename OutputRange>

constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer<

    C, OutputRange>

c_copy_n(const C& input, Size n, OutputRange&& output) {

  container_algorithm_internal::AssertCopyNSize(input, n, output);

  absl::c_copy_n(input, n, container_algorithm_internal::c_begin(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>

constexpr 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>

constexpr 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>

constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer<

    C, OutputIterator>

c_move(C&& src, OutputIterator&& dest) {

  return std::move(container_algorithm_internal::c_begin(src),

                   container_algorithm_internal::c_end(src),

                   std::forward<OutputIterator>(dest));

}

// Moves elements from `src` to `dest`. `absl::c_move(src, dest)` is

// equivalent to `std::move(std::begin(src), std::end(src), std::begin(dest))`.

//

// The `dest` container must be large enough to hold all elements of `src`;

// this function does not resize `dest`.

template <typename C, typename OutputRange>

constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer<

    C, OutputRange>

c_move(C&& src, OutputRange&& dest) {

  container_algorithm_internal::AssertCopySize(src, dest);

  absl::c_move(std::forward<C>(src),

               container_algorithm_internal::c_begin(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>

constexpr 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>

constexpr 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>

constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer<

    InputSequence, 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),

                        std::forward<OutputIterator>(output),

                        std::forward<UnaryOp>(unary_op));

}

// Performs a transformation using a unary predicate. Stores the result in

// `output`. `absl::c_transform(input, output, unary_op)` is equivalent to

// `std::transform(std::begin(input), std::end(input), std::begin(output),

// unary_op)`.

//

// The `output` container must be large enough to hold all elements of `input`;

// this function does not resize `output`.

template <typename InputSequence, typename OutputRange, typename UnaryOp>

constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer<

    InputSequence, OutputRange>

c_transform(const InputSequence& input, OutputRange&& output,

            UnaryOp&& unary_op) {

  container_algorithm_internal::AssertCopySize(input, output);

  absl::c_transform(

      input,

      container_algorithm_internal::c_begin(std::forward<OutputRange>(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>

constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer<

    InputSequence1, 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);

  std::decay_t<OutputIterator> out = std::forward<OutputIterator>(output);

  for (; first1 != last1 && first2 != last2; ++first1, (void)++first2, ++out) {

    *out = binary_op(*first1, *first2);

  }

  return out;

}

// Performs a transformation using a binary predicate. Stores the result in

// `output`. Applies `binary_op` to the first N elements of `input1` and

// `input2`, where N = min(size(input1), size(input2)).

//

// The `output` container must be large enough to hold all N elements;

// this function does not resize `output`.

template <typename InputSequence1, typename InputSequence2,

          typename OutputRange, typename BinaryOp>

constexpr std::common_type_t<

    container_algorithm_internal::ResultOfRangeToRangeTransfer<InputSequence1,

                                                               OutputRange>,

    container_algorithm_internal::ResultOfRangeToRangeTransfer<InputSequence2,

                                                               OutputRange>>

c_transform(const InputSequence1& input1, const InputSequence2& input2,

            OutputRange&& output, BinaryOp&& binary_op) {

  using InputIter1 =

      container_algorithm_internal::ContainerIter<InputSequence1>;

  using InputIter2 =

      container_algorithm_internal::ContainerIter<InputSequence2>;

  using OutputIter = container_algorithm_internal::ContainerIter<OutputRange>;

  if constexpr (base_internal::IsAtLeastForwardIterator<OutputIter>::value) {

    constexpr bool input1_has_size =

        base_internal::IsAtLeastForwardIterator<InputIter1>::value;

    constexpr bool input2_has_size =

        base_internal::IsAtLeastForwardIterator<InputIter2>::value;

    auto output_size =

        std::distance(container_algorithm_internal::c_begin(output),

                      container_algorithm_internal::c_end(output));

    if constexpr (input1_has_size && input2_has_size) {

      base_internal::HardeningAssertLE(

          (std::min)(std::distance(

                         container_algorithm_internal::c_begin(input1),

                         container_algorithm_internal::c_end(input1)),

                     std::distance(

                         container_algorithm_internal::c_begin(input2),

                         container_algorithm_internal::c_end(input2))),

          output_size);

    } else if constexpr (input1_has_size) {

      base_internal::HardeningAssertLE(

          std::distance(container_algorithm_internal::c_begin(input1),

                        container_algorithm_internal::c_end(input1)),

          output_size);

    } else if constexpr (input2_has_size) {

      base_internal::HardeningAssertLE(

          std::distance(container_algorithm_internal::c_begin(input2),

                        container_algorithm_internal::c_end(input2)),

          output_size);

    }

  }

  absl::c_transform(

      input1, input2,

      container_algorithm_internal::c_begin(std::forward<OutputRange>(output)),

      std::forward<BinaryOp>(binary_op));

}

// 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr OutputIterator c_replace_copy_if(const C& c, OutputIterator result,

                                           Pred&& pred, const 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), 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>

constexpr std::enable_if_t<

    container_algorithm_internal::IsPermissibleDestinationRange<C>::value, void>

c_fill(C&& c, const T& value) {

  std::fill(container_algorithm_internal::c_begin(c),

            container_algorithm_internal::c_end(c), 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>

constexpr std::enable_if_t<

    container_algorithm_internal::IsPermissibleDestinationRange<C>::value, void>

c_fill_n(C&& c, Size n, const T& value) {

  std::fill_n(container_algorithm_internal::c_begin(c), n, 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>

constexpr 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>

constexpr 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>

constexpr OutputIterator c_remove_copy(const C& c, OutputIterator result,

                                       const T& value) {

  return std::remove_copy(container_algorithm_internal::c_begin(c),

                          container_algorithm_internal::c_end(c), result,

                          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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr 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>

constexpr 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>>

constexpr Iterator c_rotate(C& sequence, Iterator middle) {

  return std::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>

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

}

// c_sample()

//

// Container-based version of the <algorithm> `std::sample()` function to

// randomly sample elements from the container without replacement using a

// `gen()` uniform random number generator and write them to an iterator range.

template <typename C, typename OutputIterator, typename Distance,

          typename UniformRandomBitGenerator>

OutputIterator c_sample(const C& c, OutputIterator result, Distance n,

                        UniformRandomBitGenerator&& gen) {

  return std::sample(container_algorithm_internal::c_begin(c),

                     container_algorithm_internal::c_end(c), result, n,

                     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>

constexpr 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>

constexpr 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.`