libc/src/__support/CPP/algorithm.h

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Implementation of algorithms analogous to <algorithm>.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H
#define LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H

#include "src/__support/macros/attributes.h" // LIBC_INLINE
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {
namespace cpp {

template <class T = void> struct plus {};
template <class T = void> struct multiplies {};
template <class T = void> struct bit_and {};
template <class T = void> struct bit_or {};
template <class T = void> struct bit_xor {};

template <class T> LIBC_INLINE constexpr const T &max(const T &a, const T &b) {
  return (a < b) ? b : a;
}

template <class T> LIBC_INLINE constexpr const T &min(const T &a, const T &b) {
  return (a < b) ? a : b;
}

template <class T>
LIBC_INLINE constexpr const T &clamp(const T &v, const T &lo, const T &hi) {
  return (v < lo) ? lo : (hi < v) ? hi : v;
}

template <class T, class Compare>
LIBC_INLINE constexpr const T &clamp(const T &v, const T &lo, const T &hi,
                                     Compare comp) {
  return comp(v, lo) ? lo : comp(hi, v) ? hi : v;
}

template <class T> LIBC_INLINE constexpr T abs(T a) { return a < 0 ? -a : a; }

template <class InputIt, class UnaryPred>
LIBC_INLINE constexpr InputIt find_if_not(InputIt first, InputIt last,
                                          UnaryPred q) {
  for (; first != last; ++first)
    if (!q(*first))
      return first;

  return last;
}

template <class InputIt, class UnaryPred>
LIBC_INLINE constexpr bool all_of(InputIt first, InputIt last, UnaryPred p) {
  return find_if_not(first, last, p) == last;
}

template <typename It, typename T, typename Comp>
LIBC_INLINE constexpr It lower_bound(It first, It last, const T &value,
                                     Comp comp) {
  auto count = last - first;

  while (count > 0) {
    It it = first;
    auto step = count / 2;
    it += step;

    if (comp(*it, value)) {
      first = ++it;
      count -= step + 1;
    } else {
      count = step;
    }
  }
  return first;
}

} // namespace cpp
} // namespace LIBC_NAMESPACE_DECL

#endif // LLVM_LIBC_SRC___SUPPORT_CPP_ALGORITHM_H