1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
// 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 Y_ABSL_ALGORITHM_ALGORITHM_H_
#define Y_ABSL_ALGORITHM_ALGORITHM_H_
#include <algorithm>
#include <iterator>
#include <type_traits>
#include "y_absl/base/config.h"
namespace y_absl {
Y_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 y_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 `y_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>());
}
Y_ABSL_NAMESPACE_END
} // namespace y_absl
#endif // Y_ABSL_ALGORITHM_ALGORITHM_H_
|
