1// Copyright 2017 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// -----------------------------------------------------------------------------
16// File: algorithm.h
17// -----------------------------------------------------------------------------
18//
19// This header file contains Google extensions to the standard <algorithm> C++
20// header.
21
22#ifndef ABSL_ALGORITHM_ALGORITHM_H_
23#define ABSL_ALGORITHM_ALGORITHM_H_
24
25#include <algorithm>
26#include <iterator>
27#include <type_traits>
28
29namespace absl {
30
31namespace algorithm_internal {
32
33// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
34struct EqualTo {
35 template <typename T, typename U>
36 bool operator()(const T& a, const U& b) const {
37 return a == b;
38 }
39};
40
41template <typename InputIter1, typename InputIter2, typename Pred>
42bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
43 InputIter2 last2, Pred pred, std::input_iterator_tag,
44 std::input_iterator_tag) {
45 while (true) {
46 if (first1 == last1) return first2 == last2;
47 if (first2 == last2) return false;
48 if (!pred(*first1, *first2)) return false;
49 ++first1;
50 ++first2;
51 }
52}
53
54template <typename InputIter1, typename InputIter2, typename Pred>
55bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
56 InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
57 std::random_access_iterator_tag) {
58 return (last1 - first1 == last2 - first2) &&
59 std::equal(first1, last1, first2, std::forward<Pred>(pred));
60}
61
62// When we are using our own internal predicate that just applies operator==, we
63// forward to the non-predicate form of std::equal. This enables an optimization
64// in libstdc++ that can result in std::memcmp being used for integer types.
65template <typename InputIter1, typename InputIter2>
66bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
67 InputIter2 last2, algorithm_internal::EqualTo /* unused */,
68 std::random_access_iterator_tag,
69 std::random_access_iterator_tag) {
70 return (last1 - first1 == last2 - first2) &&
71 std::equal(first1, last1, first2);
72}
73
74template <typename It>
75It RotateImpl(It first, It middle, It last, std::true_type) {
76 return std::rotate(first, middle, last);
77}
78
79template <typename It>
80It RotateImpl(It first, It middle, It last, std::false_type) {
81 std::rotate(first, middle, last);
82 return std::next(first, std::distance(middle, last));
83}
84
85} // namespace algorithm_internal
86
87// Compares the equality of two ranges specified by pairs of iterators, using
88// the given predicate, returning true iff for each corresponding iterator i1
89// and i2 in the first and second range respectively, pred(*i1, *i2) == true
90//
91// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
92// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
93// both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
94// then the predicate is never invoked and the function returns false.
95//
96// This is a C++11-compatible implementation of C++14 `std::equal`. See
97// https://en.cppreference.com/w/cpp/algorithm/equal for more information.
98template <typename InputIter1, typename InputIter2, typename Pred>
99bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
100 InputIter2 last2, Pred&& pred) {
101 return algorithm_internal::EqualImpl(
102 first1, last1, first2, last2, std::forward<Pred>(pred),
103 typename std::iterator_traits<InputIter1>::iterator_category{},
104 typename std::iterator_traits<InputIter2>::iterator_category{});
105}
106
107// Performs comparison of two ranges specified by pairs of iterators using
108// operator==.
109template <typename InputIter1, typename InputIter2>
110bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
111 InputIter2 last2) {
112 return absl::equal(first1, last1, first2, last2,
113 algorithm_internal::EqualTo{});
114}
115
116// Performs a linear search for `value` using the iterator `first` up to
117// but not including `last`, returning true if [`first`, `last`) contains an
118// element equal to `value`.
119//
120// A linear search is of O(n) complexity which is guaranteed to make at most
121// n = (`last` - `first`) comparisons. A linear search over short containers
122// may be faster than a binary search, even when the container is sorted.
123template <typename InputIterator, typename EqualityComparable>
124bool linear_search(InputIterator first, InputIterator last,
125 const EqualityComparable& value) {
126 return std::find(first, last, value) != last;
127}
128
129// Performs a left rotation on a range of elements (`first`, `last`) such that
130// `middle` is now the first element. `rotate()` returns an iterator pointing to
131// the first element before rotation. This function is exactly the same as
132// `std::rotate`, but fixes a bug in gcc
133// <= 4.9 where `std::rotate` returns `void` instead of an iterator.
134//
135// The complexity of this algorithm is the same as that of `std::rotate`, but if
136// `ForwardIterator` is not a random-access iterator, then `absl::rotate`
137// performs an additional pass over the range to construct the return value.
138
139template <typename ForwardIterator>
140ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
141 ForwardIterator last) {
142 return algorithm_internal::RotateImpl(
143 first, middle, last,
144 std::is_same<decltype(std::rotate(first, middle, last)),
145 ForwardIterator>());
146}
147
148} // namespace absl
149
150#endif // ABSL_ALGORITHM_ALGORITHM_H_
151