ksearch.hh

/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2014 President and Fellows of Harvard College
 * Copyright (c) 2012-2014 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#ifndef KSEARCH_HH
#define KSEARCH_HH 1
#include "kpermuter.hh"

template <typename KA, typename T>
struct key_comparator {
    int operator()(const KA& ka, const T& n, int p) {
        return n.compare_key(ka, p);
    }
};

struct key_indexed_position {
    int i;
    int p;
    inline key_indexed_position() {
    }
    inline constexpr key_indexed_position(int i_, int p_)
        : i(i_), p(p_) {
    }
};


template <typename KA, typename T, typename F>
int key_upper_bound_by(const KA& ka, const T& n, F comparator)
{
    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
    int l = 0, r = perm.size();
    while (l < r) {
        int m = (l + r) >> 1;
        int mp = perm[m];
        int cmp = comparator(ka, n, mp);
        if (cmp < 0)
            r = m;
        else if (cmp == 0)
            return m + 1;
        else
            l = m + 1;
    }
    return l;
}

template <typename KA, typename T>
inline int key_upper_bound(const KA& ka, const T& n)
{
    return key_upper_bound_by(ka, n, key_comparator<KA, T>());
}

template <typename KA, typename T, typename F>
key_indexed_position key_lower_bound_by(const KA& ka, const T& n, F comparator)
{
    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
    int l = 0, r = perm.size();
    while (l < r) {
        int m = (l + r) >> 1;
        int mp = perm[m];
        int cmp = comparator(ka, n, mp);
        if (cmp < 0)
            r = m;
        else if (cmp == 0)
            return key_indexed_position(m, mp);
        else
            l = m + 1;
    }
    return key_indexed_position(l, -1);
}

template <typename KA, typename T>
inline key_indexed_position key_lower_bound(const KA& ka, const T& n)
{
    return key_lower_bound_by(ka, n, key_comparator<KA, T>());
}


template <typename KA, typename T, typename F>
int key_find_upper_bound_by(const KA& ka, const T& n, F comparator)
{
    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
    int l = 0, r = perm.size();
    while (l < r) {
        int lp = perm[l];
        int cmp = comparator(ka, n, lp);
        if (cmp < 0)
            break;
        else
            ++l;
    }
    return l;
}

template <typename KA, typename T, typename F>
key_indexed_position key_find_lower_bound_by(const KA& ka, const T& n, F comparator)
{
    typename key_permuter<T>::type perm = key_permuter<T>::permutation(n);
    int l = 0, r = perm.size();
    while (l < r) {
        int lp = perm[l];
        int cmp = comparator(ka, n, lp);
        if (cmp < 0)
            break;
        else if (cmp == 0)
            return key_indexed_position(l, lp);
        else
            ++l;
    }
    return key_indexed_position(l, -1);
}


struct key_bound_binary {
    static constexpr bool is_binary = true;
    template <typename KA, typename T>
    static inline int upper(const KA& ka, const T& n) {
        return key_upper_bound_by(ka, n, key_comparator<KA, T>());
    }
    template <typename KA, typename T>
    static inline key_indexed_position lower(const KA& ka, const T& n) {
        return key_lower_bound_by(ka, n, key_comparator<KA, T>());
    }
    template <typename KA, typename T, typename F>
    static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
        return key_lower_bound_by(ka, n, comparator);
    }
};

struct key_bound_linear {
    static constexpr bool is_binary = false;
    template <typename KA, typename T>
    static inline int upper(const KA& ka, const T& n) {
        return key_find_upper_bound_by(ka, n, key_comparator<KA, T>());
    }
    template <typename KA, typename T>
    static inline key_indexed_position lower(const KA& ka, const T& n) {
        return key_find_lower_bound_by(ka, n, key_comparator<KA, T>());
    }
    template <typename KA, typename T, typename F>
    static inline key_indexed_position lower_by(const KA& ka, const T& n, F comparator) {
        return key_find_lower_bound_by(ka, n, comparator);
    }
};


enum {
    bound_method_fast = 0,
    bound_method_binary,
    bound_method_linear
};
template <int max_size, int method = bound_method_fast> struct key_bound {};
template <int max_size> struct key_bound<max_size, bound_method_binary> {
    typedef key_bound_binary type;
};
template <int max_size> struct key_bound<max_size, bound_method_linear> {
    typedef key_bound_linear type;
};
template <int max_size> struct key_bound<max_size, bound_method_fast> {
    typedef typename key_bound<max_size, (max_size > 16 ? bound_method_binary : bound_method_linear)>::type type;
};

#endif