/Users/deen/code/yugabyte-db/src/yb/util/algorithm_util.h
Line | Count | Source |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #ifndef YB_UTIL_ALGORITHM_UTIL_H |
15 | | #define YB_UTIL_ALGORITHM_UTIL_H |
16 | | |
17 | | #include <algorithm> |
18 | | #include <bitset> |
19 | | #include <type_traits> |
20 | | |
21 | | namespace yb { |
22 | | |
23 | | enum class SortOrder : uint8_t { |
24 | | kAscending = 0, |
25 | | kDescending |
26 | | }; |
27 | | |
28 | | template<typename Iterator, typename Functor> |
29 | | void SortByKey(Iterator begin, |
30 | | Iterator end, |
31 | | const Functor& f, |
32 | 48 | SortOrder sort_order = SortOrder::kAscending) { |
33 | 48 | using Value = typename Iterator::value_type; |
34 | 48 | const bool invert_order = sort_order == SortOrder::kDescending; |
35 | 266 | std::sort(begin, end, [invert_order, &f](const Value& a, const Value& b){ |
36 | 266 | return (f(a) < f(b)) != invert_order; |
37 | 266 | }); |
38 | 48 | } |
39 | | |
40 | | // Returns an iterator pointing to last element that is <= k. |
41 | | // Returns map.end() if there are no such elements. |
42 | | // |
43 | | template <class Map, class Key> |
44 | | typename Map::const_iterator GetLastLessOrEqual(const Map& map, const Key& k) { |
45 | | auto iter = map.upper_bound(k); |
46 | | // iter is the first element > k. |
47 | | if (iter == map.begin()) { |
48 | | // All elements are > k => there are no elements that are <= k. |
49 | | return map.end(); |
50 | | } else { |
51 | | // Element previous to iter is the last element that <= k. |
52 | | iter--; |
53 | | return iter; |
54 | | } |
55 | | } |
56 | | |
57 | | }; // namespace yb |
58 | | |
59 | | #endif // YB_UTIL_ALGORITHM_UTIL_H |