1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// Implementation of algorithms analogous to <algorithm>.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H
15#define LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H
16
17#include "src/__support/macros/attributes.h" // LIBC_INLINE
18#include "src/__support/macros/config.h"
19
20namespace LIBC_NAMESPACE_DECL {
21namespace cpp {
22
23template <class T = void> struct plus {};
24template <class T = void> struct multiplies {};
25template <class T = void> struct bit_and {};
26template <class T = void> struct bit_or {};
27template <class T = void> struct bit_xor {};
28
29template <class T> LIBC_INLINE constexpr const T &max(const T &a, const T &b) {
30 return (a < b) ? b : a;
31}
32
33template <class T> LIBC_INLINE constexpr const T &min(const T &a, const T &b) {
34 return (a < b) ? a : b;
35}
36
37template <class T>
38LIBC_INLINE constexpr const T &clamp(const T &v, const T &lo, const T &hi) {
39 return (v < lo) ? lo : (hi < v) ? hi : v;
40}
41
42template <class T, class Compare>
43LIBC_INLINE constexpr const T &clamp(const T &v, const T &lo, const T &hi,
44 Compare comp) {
45 return comp(v, lo) ? lo : comp(hi, v) ? hi : v;
46}
47
48template <class T> LIBC_INLINE constexpr T abs(T a) { return a < 0 ? -a : a; }
49
50template <class InputIt, class UnaryPred>
51LIBC_INLINE constexpr InputIt find_if_not(InputIt first, InputIt last,
52 UnaryPred q) {
53 for (; first != last; ++first)
54 if (!q(*first))
55 return first;
56
57 return last;
58}
59
60template <class InputIt, class UnaryPred>
61LIBC_INLINE constexpr bool all_of(InputIt first, InputIt last, UnaryPred p) {
62 return find_if_not(first, last, p) == last;
63}
64
65template <typename It, typename T, typename Comp>
66LIBC_INLINE constexpr It lower_bound(It first, It last, const T &value,
67 Comp comp) {
68 auto count = last - first;
69
70 while (count > 0) {
71 It it = first;
72 auto step = count / 2;
73 it += step;
74
75 if (comp(*it, value)) {
76 first = ++it;
77 count -= step + 1;
78 } else {
79 count = step;
80 }
81 }
82 return first;
83}
84
85} // namespace cpp
86} // namespace LIBC_NAMESPACE_DECL
87
88#endif // LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H
89