zircon/system/ulib/fbl/include/fbl/algorithm.h

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef FBL_ALGORITHM_H_
#define FBL_ALGORITHM_H_

#include <stdlib.h>

#include <algorithm>
#include <type_traits>

namespace fbl {

using std::min;
using std::max;
using std::clamp;

// is_pow2
//
// Test to see if an unsigned integer type is an exact power of two or
// not.  Note, this needs to use a helper struct because we are not
// allowed to partially specialize functions (because C++).
namespace internal {
template <typename T, typename Enable = void> struct IsPow2Helper;

template <typename T>
struct IsPow2Helper<T, std::enable_if_t<std::is_unsigned_v<T>>> {
    static constexpr bool is_pow2(T val) {
        return (val != 0) && (((val - 1U) & val) == 0);
    }
};
}

// is_pow2<T>(T val)
//
// Tests to see if val (which may be any unsigned integer type) is a power of 2
// or not.  0 is not considered to be a power of 2.
//
template <typename T>
constexpr bool is_pow2(T val) {
    return internal::IsPow2Helper<T>::is_pow2(val);
}

// round_up rounds up val until it is divisible by multiple.
// Zero is divisible by all multiples.
template<class T, class U,
         class L = std::conditional_t<sizeof(T) >= sizeof(U), T, U>,
         class = std::enable_if_t<std::is_unsigned_v<T>>,
         class = std::enable_if_t<std::is_unsigned_v<U>>>
constexpr const L round_up(const T& val_, const U& multiple_) {
    const L val = static_cast<L>(val_);
    const L multiple = static_cast<L>(multiple_);
    return val == 0 ? 0 :
            is_pow2<L>(multiple) ? (val + (multiple - 1)) & ~(multiple - 1) :
                ((val + (multiple - 1)) / multiple) * multiple;
}

// round_down rounds down val until it is divisible by multiple.
// Zero is divisible by all multiples.
template<class T, class U,
         class L = std::conditional_t<sizeof(T) >= sizeof(U), T, U>,
         class = std::enable_if_t<std::is_unsigned_v<T>>,
         class = std::enable_if_t<std::is_unsigned_v<U>>>
constexpr const L round_down(const T& val_, const U& multiple_) {
    const L val = static_cast<L>(val_);
    const L multiple = static_cast<L>(multiple_);
    return val == 0 ? 0 :
            is_pow2<L>(multiple) ? val & ~(multiple - 1) :
                (val / multiple) * multiple;
}

// Returns an iterator to the maximum element in the range [|first|, |last|).
//
// |first| and |last| must be forward iterators.
//
// Similar to: <http://en.cppreference.com/w/cpp/algorithm/max_element>
template<class FwIterator>
FwIterator max_element(FwIterator first, FwIterator last) {
    FwIterator max = first;
    while (first < last) {
        if (*first > *max) {
            max = first;
        }
        first++;
    }
    return max;
}

// Returns an iterator to the maximum element in the range [|first|, |last|).
// using |comp| to compare elements instead of operator>
//
// |first| and |last| must be forward iterators.
//
// Similar to: <http://en.cppreference.com/w/cpp/algorithm/max_element>
template<class FwIterator, class Compare>
FwIterator max_element(FwIterator first, FwIterator last, Compare comp) {
    FwIterator max = first;
    while (first < last) {
        if (comp(*first, *max)) {
            max = first;
        }
        first++;
    }
    return max;
}

// Returns an iterator to the minimum element in the range [|first|, |last|).
//
// |first| and |last| must be forward iterators.
//
// Similar to: <http://en.cppreference.com/w/cpp/algorithm/min_element>
template<class FwIterator>
FwIterator min_element(FwIterator first, FwIterator last) {
    FwIterator min = first;
    while (first < last) {
        if (*first < *min) {
            min = first;
        }
        first++;
    }
    return min;
}

// Returns an iterator to the minimum element in the range [|first|, |last|)
// using |comp| to compare elements instead of operator<
//
// |first| and |last| must be forward iterators.
//
// Similar to: <http://en.cppreference.com/w/cpp/algorithm/min_element>
template<class FwIterator, class Compare>
FwIterator min_element(FwIterator first, FwIterator last, Compare comp) {
    FwIterator min = first;
    while (first < last) {
        if (comp(*first, *min)) {
            min = first;
        }
        first++;
    }
    return min;
}

// Returns a pointer to the first element that is not less than |value|, or
// |last| if no such element is found.
//
// Similar to <http://en.cppreference.com/w/cpp/algorithm/lower_bound>
template<class T, class U>
const T* lower_bound(const T* first, const T* last, const U& value) {
    while (first < last) {
        const T* probe = first + (last - first) / 2;
        if (*probe < value) {
            first = probe + 1;
        } else {
            last = probe;
        }
    }
    return last;
}

// Returns a pointer to the first element that is not less than |value|, or
// |last| if no such element is found.
//
// |comp| is used to compare the elements rather than operator<.
//
// Similar to <http://en.cppreference.com/w/cpp/algorithm/lower_bound>
template<class T, class U, class Compare>
const T* lower_bound(const T* first, const T* last, const U& value, Compare comp) {
    while (first < last) {
        const T* probe = first + (last - first) / 2;
        if (comp(*probe, value)) {
            first = probe + 1;
        } else {
            last = probe;
        }
    }
    return last;
}

template <typename T, size_t N>
constexpr size_t count_of(T const(&)[N]) {
    return N;
}

// 2017-12-10: On ARM/release/GCC, a div(mod)-based implementation runs at 2x
// the speed of subtract-based ones, with no O(n) scaling as input values grow.
// For x86-64/release/GCC, sub-based methods are initially 20-40% faster (depending
// on int type) but scale linearly; they are comparable for values 100000-200000.
//
// gcd (greatest common divisor) returns the largest non-negative integer that cleanly
// divides both inputs. Inputs are unsigned integers. gcd(x,0)=x; gcd(x,1)=1
template <typename T, class = std::enable_if_t<std::is_unsigned_v<T>>>
T gcd(T first, T second) {
    // If function need not support uint8 or uint16, static_casts can be removed
    while (second != 0) {
        first = static_cast<T>(first % second);
        if (first == 0) {
            return second;
        }
        second = static_cast<T>(second % first);
    }

    return first;
}

// lcm (least common multiple) returns the smallest non-negative integer that is
// cleanly divided by both inputs.
// Inputs are unsigned integers. lcm(x,0)=0; lcm(x,1)=x
template <typename T, class = std::enable_if_t<std::is_unsigned_v<T>>>
T lcm(T first, T second) {
    if (first == 0 && second == 0) {
        return 0;
    }

    // If function need not support uint8 or uint16, static_cast can be removed
    return static_cast<T>((first / gcd(first, second)) * second);
}

// Accumulates the elements in the range [|first|, |last|) with |initial_value|.
// Returns the accumulated value.
//
// |first| and |last| must be InputIterators.
//
// Similar to <http://en.cppreference.com/w/cpp/algorithm/accumulate>.
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T initial_value) {
    while(first < last) {
        initial_value += *first;
        first++;
    }
    return initial_value;
}

// Accumulates the elements in the range [|first|, |last|) with |initial_value|
// using |op| instead of operator+.  Returns the accumulated value.
//
// |first| and |last| must be InputIterators.
//
// Similar to <http://en.cppreference.com/w/cpp/algorithm/accumulate>.
template <class InputIterator, class T, class BinaryOp>
T accumulate(InputIterator first, InputIterator last, T initial_value, BinaryOp op) {
    while(first < last) {
        initial_value = op(initial_value, *first);
        first++;
    }
    return initial_value;
}

}  // namespace fbl

#endif  // FBL_ALGORITHM_H_