1 /* 2 * Copyright (c) 2022 Huawei Device Co., Ltd. 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 * http://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 #ifndef API_BASE_UTIL_ALGORITHM_H 17 #define API_BASE_UTIL_ALGORITHM_H 18 19 #include <cstddef> 20 21 #include <base/namespace.h> 22 23 BASE_BEGIN_NAMESPACE() 24 template<class T = void> 25 struct Less { operatorLess26 constexpr bool operator()(const T& lhs, const T& rhs) const noexcept 27 { 28 return lhs < rhs; 29 } 30 }; 31 32 template<> 33 struct Less<void> { 34 template<typename T1, typename T2> 35 constexpr bool operator()(const T1& lhs, const T2& rhs) const noexcept 36 { 37 return lhs < rhs; 38 } 39 }; 40 41 template<typename It, typename Comparison> 42 void InsertionSort(It first, const It last, Comparison&& func) 43 { 44 const auto len = last - first; 45 for (ptrdiff_t i = 1; i < len; ++i) { 46 auto x = BASE_NS::move(*(first + i)); 47 auto j = i; 48 while (j > 0 && func(x, *(first + (j - 1)))) { 49 *(first + j) = BASE_NS::move(*(first + (j - 1))); 50 j = j - 1; 51 } 52 *(first + j) = BASE_NS::move(x); 53 } 54 } 55 56 template<typename It> 57 inline void InsertionSort(It first, const It last) 58 { 59 InsertionSort(first, last, BASE_NS::Less<decltype(*first)> {}); 60 } 61 62 template<typename Iter, typename T, typename Comparison> 63 constexpr Iter LinearLowerBound(Iter first, Iter last, const T& value, Comparison&& pred) noexcept 64 { 65 while ((first != last)) { 66 if (!pred(*first, value)) { 67 return first; 68 } 69 ++first; 70 } 71 return first; 72 } 73 74 template<typename Iter, typename T, typename Comparison, std::ptrdiff_t limit = 10> 75 constexpr Iter LowerBound(Iter first, Iter last, const T& value, Comparison&& pred) noexcept 76 { 77 auto size = (last - first); 78 79 while (size > 0) { 80 if (size < limit) { 81 return LinearLowerBound(first, last, value, BASE_NS::forward<Comparison>(pred)); 82 } 83 84 const auto midIndex = size / 2; 85 const auto mid = first + midIndex; 86 if (pred(*mid, value)) { 87 first = mid + 1; 88 size -= midIndex + 1; 89 } else { 90 size = midIndex; 91 } 92 } 93 return first; 94 } 95 96 template<typename Iter, typename T, std::ptrdiff_t limit = 10> 97 constexpr Iter LowerBound(Iter first, Iter last, const T& value) noexcept 98 { 99 return LowerBound<Iter, T, BASE_NS::Less<>, limit>(first, last, value, BASE_NS::Less<> {}); 100 } 101 102 BASE_END_NAMESPACE() 103 #endif // API_BASE_UTIL_ALGORITHM_H