+/* 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