Find the position of an integer value in a list of integers, or else find the position where it should be inserted while keeping the list ordered.

binarypos.cpp

/* Binary Search Plugin
 *
 * Find the position of an integer value in a list of integers,
 * or else find the position where it should be inserted while keeping the list ordered.
 *
 * Compiling and installation as a MySQL plugin:
 *
 * 1) g++ -shared -o binarypos.so binarypos.cpp
 * 2) sudo service mysql stop
 * 3) sudo cp ./binarypos.so /usr/lib/mysql/plugin/
 * 4) sudo service mysql start
 *
 * How to interpret return values:
 *
 * - A return value >= 0 indicates the position of the value in the list;
 * - A return value < 0 indicates the (translated) insert position for a value that isn't in the list.
 *   When the return value x is below 0, apply -x - 1 to get the insert position.
 *
 * Usage:
 *
 *  select binarypos("1718691890,1718692000,1718693000,1718694000",1718692795);
 *  > -3
 *  select binarypos("1718691890,1718692000,1718693000,1718694000",1718693000);
 *  > 2
 *
 * @author Richard Osseweyer ([email protected])
 *
 */
#include <bits/stdc++.h>
#include <mysql/mysql.h>
using namespace std;

extern "C" {
    bool binarypos_init(UDF_INIT *initid, UDF_ARGS *args, char *message);
    void binarypos_deinit(UDF_INIT *initid);
    vector<int> split(string str);
    int binarySearch(vector<int> vrr, int x);
    long long binarypos(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error);
}

vector<int> split(string str) {

    stringstream ss(str);
    vector<int> v;
    string t;
    char del = ',';

    while(getline(ss, t, del)) {
        v.push_back(stoi(t));
        //cout << stoi(t) << '\n';
    }

    return v;
}

int binarySearch(vector<int> vrr, int x) {

    int low = 0;
    int high = vrr.size() - 1;

    while (low <= high) {

        int mid = (low + high) >> 1; // divide by 2
        int midval = vrr[mid];
        if (midval == x) return mid;
        if (midval < x) low = mid + 1;
        else high = mid - 1;
    }
    // Nothing found: return negative insert position,
    // negative to indicate it was not found
    return -low - 1;
}

long long binarypos(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error) {

    string str = args->args[0];
    int x = *((long long*) args->args[1]);

    vector<int> vrr = split(str);
    int result = binarySearch(vrr, x);
    return result;
}

bool binarypos_init(UDF_INIT *initid, UDF_ARGS *args, char *message) {

    if (args->arg_count != 2) {
        strcpy(message,"binarypos(csv_string,find_int) requires two arguments");
        return 1;
    }
    if (args->arg_type[0] != STRING_RESULT || args->arg_type[1] != INT_RESULT) {
        strcpy(message,"binarypos(csv_string,find_int) requires a string and an integer");
        return 1;
    }
    return 0;
}

void binarypos_deinit(UDF_INIT *initid) {
}

/*
int main(void) {

    string str = "24234,54523, 67774,100000,400000";
    int x = 55555;
    vector<int> vrr = split(str);

    cout << vrr.size() << '\n';
    int result = binarySearch(vrr, x);

    cout << "result: " << result << '\n';
}
*/