sorted_utils.hpp

Go to the documentation of this file.

#ifndef SORTED_UTILS_H
#define SORTED_UTILS_H
 
#include <vector>
#include <concepts>
#include <optional>
#include <functional>
#include <tuple>
 
namespace hsc_snippets {
    template<std::totally_ordered T>
    int numOfGreaterElements(const std::vector<T> &v, T value)
    // v should be non-descreasing
    {
        auto it = std::lower_bound(v.cbegin(), v.cend(), value,
                                   [](const T &value, const T &element) { return value <= element; });
        if (it == v.cend()) {
            return 0;
        }
        return v.cend() - it;
    }
 
    template<std::integral T>
    // vec must be in ascending order. [start, end)
    bool containsInRange(const std::vector<T> &vec, T start, T end) {
        if (vec.empty() || start >= end) {
            return false;
        }
 
        // Lower bound of the range
        auto lower = std::lower_bound(vec.begin(), vec.end(), start);
 
        // Check if the lower bound is not beyond the vector and less than 'end'
        if (lower != vec.end() && *lower < end) {
            return true;
        }
 
        return false;
    }
 
    template<typename T, std::integral I = int>
    std::optional<I> deferred_binary_search(I low,
                                            I high,
                                            const T &value,
                                            auto &&func) {
        while (low <= high) {
            I mid = low + (high - low) / 2;
            T res = func(mid);
            if (res == value) {
                return mid;
            } else if (res < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
 
        return std::nullopt;
    }
 
 
    template<typename T, std::integral I = int>
    I deferred_upper_bound(I low, I high, const T &value, auto &&func, auto &&comp) {
        I it;
        I count = high - low + 1;
        I step;
 
        while (count > 0) {
            it = low;
            step = count / 2;
            it += step;
 
            if (comp(value, func(it))) {
                count = step;
            } else {
                low = ++it;
                count -= step + 1;
            }
        }
 
        return low;
    }
 
    template<typename T, std::integral I = int>
    I deferred_upper_bound(I low, I high, const T &value, auto &&func) {
        return deferred_upper_bound(low, high, value, func, std::less<T>());
    }
 
    template<typename T, std::integral I = int>
    I deferred_lower_bound(I low, I high, const T &value, auto &&func, auto &&comp) {
        I it;
        I count = high - low + 1;
        I step;
 
        while (count > 0) {
            it = low;
            step = count / 2;
            it += step;
 
            if (comp(func(it), value)) {
                low = ++it;
                count -= step + 1;
            } else {
                count = step;
            }
        }
 
        return low; // Returns the first index where the value is not less than the target value
    }
 
    template<typename T, std::integral I = int>
    I deferred_lower_bound(I low, I high, const T &value, auto &&func) {
        return deferred_lower_bound(low, high, value, func, std::less<T>());
    }
 
 
    template<std::integral T>
    void sortThree(T &a, T &b, T &c) {
        if (a > b) {
            std::swap(a, b);
        }
        if (b > c) {
            std::swap(b, c);
        }
        if (a > b) {
            std::swap(a, b);
        }
    }
 
    static std::tuple<std::function<int(int)>, int> create_compression_mapper(const std::vector<int> &nums) {
        std::vector<int> compressed = nums;
        std::sort(compressed.begin(), compressed.end());
        compressed.erase(std::unique(compressed.begin(), compressed.end()), compressed.end());
 
        auto func = [compressed](int value) {
            return std::lower_bound(compressed.begin(), compressed.end(), value) - compressed.begin();
        };
 
        int count = compressed.size();
        return std::make_tuple(func, count);
    }
}
 
#endif // SORTED_UTILS_H