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
|
/*!
@authors Andrei Novikov (pyclustering@yandex.ru)
@date 2014-2020
@copyright BSD-3-Clause
*/
#pragma once
#include <iterator>
namespace pyclustering {
namespace utils {
namespace algorithm {
/*!
@brief Returns the element at the left side from the right border with the same value as the
last element in the range `[p_begin, p_end)`.
@details The element at the right is considered as target to search. `[p_begin, p_end)` must
be sorted collection. `InputIt` must meet the requirements of `LegacyInputIterator`
and `LegacyRandomAccessIterator`. The complexity of the algorithm is `O(log(n))`. The
algorithm is based on the binary search algorithm.
@param[in] p_begin: iterator pointing to the first element.
@param[in] p_end: iterator pointing to the end of the range.
@param[in] p_comparator: comparison function object which returns `true` if the first argument
is less than the second. The signature of the compare function should be equivalent
to the following: `bool comparator(const Type & p_val1, const Type & p_val2)`.
@return The element at the left side from the right border with the same value as the
last element in the range `[p_begin, p_end)`.
*/
template <class InputIt, class Comparator>
InputIt find_left_element(const InputIt p_begin, const InputIt p_end, Comparator p_comparator) {
if (p_begin == p_end) {
return p_end;
}
InputIt left = p_begin, right = p_end - 1;
InputIt middle = p_begin + (std::distance(left, right) / 2);
auto target = *right;
while (left < right) {
if (p_comparator(*middle, target)) {
left = middle + 1;
}
else {
right = middle;
}
const auto offset = std::distance(left, right) / 2;
middle = left + offset;
}
return left;
}
/*!
@brief Returns the element at the left side from the right border with the same value as the
last element in the range `[p_begin, p_end)`.
@details The element at the right is considered as target to search. `[p_begin, p_end)` must
be sorted collection. `InputIt` must meet the requirements of `LegacyInputIterator`
and `LegacyRandomAccessIterator`. The complexity of the algorithm is `O(log(n))`. The
algorithm is based on the binary search algorithm.
@param[in] p_begin: iterator pointing to the first element.
@param[in] p_end: iterator pointing to the end of the range.
@return The element at the left side from the right border with the same value as the
last element in the range `[p_begin, p_end)`.
@code
#include <iterator>
#include <vector>
#include <iostream>
#include <pyclustering/utils/algorithm.hpp>
using namespace pyclustering::utils::algorithm;
int main() {
std::vector<int> seq = { 1, 2, 2, 3, 3, 3, 6, 6, 6 };
for (auto iter = seq.begin() + 1; iter != seq.end(); iter++) {
auto left = find_left_element(seq.begin(), iter);
std::cout << "Index of the left element: " << std::distance(seq.begin(), left)
<< " for " << *iter << std::endl;
}
return 0;
}
@endcode
*/
template <class InputIt>
InputIt find_left_element(const InputIt p_begin, const InputIt p_end) {
using iter_type = typename std::iterator_traits<InputIt>::value_type;
return find_left_element(p_begin, p_end, [](iter_type & p_val1, iter_type & p_val2) {
return p_val1 < p_val2;
});
}
}
}
}
|
