"Fossies" - the Fresh Open Source Software Archive 
Member "abseil-cpp-20230802.1/absl/algorithm/algorithm.h" (18 Sep 2023, 6293 Bytes) of package /linux/misc/abseil-cpp-20230802.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "algorithm.h" see the
Fossies "Dox" file reference documentation.
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>
39 bool operator()(const T& a, const U& b) const {
40 return a == b;
41 }
42 };
43
44 template <typename InputIter1, typename InputIter2, typename Pred>
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>
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>
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>
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>
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>
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>
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>
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>
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_