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
29 #include "absl/base/config.h"
30
31 namespace absl {
32 ABSL_NAMESPACE_BEGIN
33
34 namespace algorithm_internal {
35
36 // Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
37 struct EqualTo {
38 template <typename T, typename U>
operatorEqualTo39 bool operator()(const T& a, const U& b) const {
40 return a == b;
41 }
42 };
43
44 template <typename InputIter1, typename InputIter2, typename Pred>
EqualImpl(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,Pred pred,std::input_iterator_tag,std::input_iterator_tag)45 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
46 InputIter2 last2, Pred pred, std::input_iterator_tag,
47 std::input_iterator_tag) {
48 while (true) {
49 if (first1 == last1) return first2 == last2;
50 if (first2 == last2) return false;
51 if (!pred(*first1, *first2)) return false;
52 ++first1;
53 ++first2;
54 }
55 }
56
57 template <typename InputIter1, typename InputIter2, typename Pred>
EqualImpl(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,Pred && pred,std::random_access_iterator_tag,std::random_access_iterator_tag)58 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
59 InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
60 std::random_access_iterator_tag) {
61 return (last1 - first1 == last2 - first2) &&
62 std::equal(first1, last1, first2, std::forward<Pred>(pred));
63 }
64
65 // When we are using our own internal predicate that just applies operator==, we
66 // forward to the non-predicate form of std::equal. This enables an optimization
67 // in libstdc++ that can result in std::memcmp being used for integer types.
68 template <typename InputIter1, typename InputIter2>
EqualImpl(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,algorithm_internal::EqualTo,std::random_access_iterator_tag,std::random_access_iterator_tag)69 bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
70 InputIter2 last2, algorithm_internal::EqualTo /* unused */,
71 std::random_access_iterator_tag,
72 std::random_access_iterator_tag) {
73 return (last1 - first1 == last2 - first2) &&
74 std::equal(first1, last1, first2);
75 }
76
77 template <typename It>
RotateImpl(It first,It middle,It last,std::true_type)78 It RotateImpl(It first, It middle, It last, std::true_type) {
79 return std::rotate(first, middle, last);
80 }
81
82 template <typename It>
RotateImpl(It first,It middle,It last,std::false_type)83 It RotateImpl(It first, It middle, It last, std::false_type) {
84 std::rotate(first, middle, last);
85 return std::next(first, std::distance(middle, last));
86 }
87
88 } // namespace algorithm_internal
89
90 // equal()
91 //
92 // Compares the equality of two ranges specified by pairs of iterators, using
93 // the given predicate, returning true iff for each corresponding iterator i1
94 // and i2 in the first and second range respectively, pred(*i1, *i2) == true
95 //
96 // This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
97 // invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
98 // both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
99 // then the predicate is never invoked and the function returns false.
100 //
101 // This is a C++11-compatible implementation of C++14 `std::equal`. See
102 // https://en.cppreference.com/w/cpp/algorithm/equal for more information.
103 template <typename InputIter1, typename InputIter2, typename Pred>
equal(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,Pred && pred)104 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
105 InputIter2 last2, Pred&& pred) {
106 return algorithm_internal::EqualImpl(
107 first1, last1, first2, last2, std::forward<Pred>(pred),
108 typename std::iterator_traits<InputIter1>::iterator_category{},
109 typename std::iterator_traits<InputIter2>::iterator_category{});
110 }
111
112 // Overload of equal() that performs comparison of two ranges specified by pairs
113 // of iterators using operator==.
114 template <typename InputIter1, typename InputIter2>
equal(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2)115 bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
116 InputIter2 last2) {
117 return absl::equal(first1, last1, first2, last2,
118 algorithm_internal::EqualTo{});
119 }
120
121 // linear_search()
122 //
123 // Performs a linear search for `value` using the iterator `first` up to
124 // but not including `last`, returning true if [`first`, `last`) contains an
125 // element equal to `value`.
126 //
127 // A linear search is of O(n) complexity which is guaranteed to make at most
128 // n = (`last` - `first`) comparisons. A linear search over short containers
129 // may be faster than a binary search, even when the container is sorted.
130 template <typename InputIterator, typename EqualityComparable>
linear_search(InputIterator first,InputIterator last,const EqualityComparable & value)131 bool linear_search(InputIterator first, InputIterator last,
132 const EqualityComparable& value) {
133 return std::find(first, last, value) != last;
134 }
135
136 // rotate()
137 //
138 // Performs a left rotation on a range of elements (`first`, `last`) such that
139 // `middle` is now the first element. `rotate()` returns an iterator pointing to
140 // the first element before rotation. This function is exactly the same as
141 // `std::rotate`, but fixes a bug in gcc
142 // <= 4.9 where `std::rotate` returns `void` instead of an iterator.
143 //
144 // The complexity of this algorithm is the same as that of `std::rotate`, but if
145 // `ForwardIterator` is not a random-access iterator, then `absl::rotate`
146 // performs an additional pass over the range to construct the return value.
147 template <typename ForwardIterator>
rotate(ForwardIterator first,ForwardIterator middle,ForwardIterator last)148 ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
149 ForwardIterator last) {
150 return algorithm_internal::RotateImpl(
151 first, middle, last,
152 std::is_same<decltype(std::rotate(first, middle, last)),
153 ForwardIterator>());
154 }
155
156 ABSL_NAMESPACE_END
157 } // namespace absl
158
159 #endif // ABSL_ALGORITHM_ALGORITHM_H_
160