Circular Binary Index
I am creating a tool to combine multiple streams at the closest timestamp. The streams might not sync, so I store the last n
(maybe -> 500) elements in a fixed size circular buffer. I would like to use sortedIndex
( notsearch
) to find where the element will fit in the buffer. I need this index to find the stream element just before and immediately after the timestamp.
Edge handling around corner questions doesn't matter, I don't care if you return the index outside of the array or 0
for the largest value. I was playing with this one last night and couldn't figure out how it works.
The function contract is below and is based on _.sortedIndex
( implementation )
/**
* Binary search for finding the closest computed (by iterator) value
* in some sorted circular array
*
* @param {Array} array a circular array-like
* @param {Object} value to search for an index
* @param {Function} iterator to compute the compare value of an item
*/
function sortedIndex(array, value, iterator) {
var low = 0,
high = array.length;
while (low != high && iterator(array[low]) > iterator(array[high])) {
// The binary search I failed to implement
}
return low;
}
Some test cases (again handle differently around corner cases without problems): http://jsbin.com/yusilaba/1/edit
function identity(x) {
return x;
}
function property(prop) {
return function(x) {
return x[prop];
};
}
test('sortedIndex should work on simple case', function(t) {
var array = [1, 2, 3, 4];
equal(sortedIndex(array, 2, identity), 1, 'equal case sorts towards left');
equal(sortedIndex(array, 2.5, identity), 2);
equal(sortedIndex(array, 10, identity), 0);
equal(sortedIndex(array, -10, identity), 3);
array = [{a: 1}, {a: 2}, {a: 3}, {a: 4}];
equal(sortedIndex(array, {a: 2}, property('a')), 1);
equal(sortedIndex(array, {a: 2.5}, property('a')), 2);
equal(sortedIndex(array, {a: 10}, property('a')), 0);
equal(sortedIndex(array, {a: -10}, property('a')), 3);
});
test('sortedIndex should work on circular collections', function() {
var array = [2, 3, 4, 1, 1.5];
equal(sortedIndex(array, 2, identity), 0, 'equal case sorts towards left');
equal(sortedIndex(array, 2.5, identity), 1);
equal(sortedIndex(array, 10, identity), 3);
equal(sortedIndex(array, -10, identity), 2);
equal(sortedIndex(array, 5, identity), 4);
equal(sortedIndex(array, 3.5, identity), 3);
array = [{a: 2}, {a: 3}, {a: 4}, {a: 1}, {a: 1.5}];
equal(sortedIndex(array, {a: 2}, property('a')), 0, 'equal case sorts towards left');
equal(sortedIndex(array, {a: 2.5}, property('a')), 1);
equal(sortedIndex(array, {a: 10}, property('a')), 3);
equal(sortedIndex(array, {a: -10}, property('a')), 2);
});
Edit --- Here's my completed version https://github.com/trevnorris/cbuffer/pull/14
sortedIndex : function(value, comparitor, context) {
var low = this.start,
high = this.size - 1;
// Tricky part is finding if its before or after the pivot
// we can get this info by checking if the target is less than
// the last item. After that it just a typical binary search.
if (low && comparitor.call(context, value, this.data[high]) > 0) {
low = 0, high = this.end;
}
while (low < high) {
var mid = (low + high) >>> 1;
if (comparitor.call(context, value, this.data[mid]) > 0) low = mid + 1;
else high = mid;
}
// http://stackoverflow.com/a/18618273/1517919
return (((low - this.start) % this.size) + this.size) % this.size;
}
source to share
Here is what I came up with (it passes your test cases). Basically, it does a regular binary search when the array is sorted. When it is circular (ex: [2,3,4,1]) it finds the vault (which is the index of the start of the circle, so in this example index 3, which matches 4 in the array, will be the hinge), then the binary searches for the part the array in which the axis is located.
function findPivot(arr, low, high, iterable){
// base cases
if (high < low) return -1;
if (high == low) return low;
var mid = Math.floor((low + high)/2);
if (mid < high && iterable(arr[mid]) > iterable(arr[mid + 1]))
return mid;
if (mid > low && iterable(arr[mid]) < iterable(arr[mid - 1]))
return (mid-1);
if (iterable(arr[low]) >= iterable(arr[mid]))
return findPivot(arr, low, mid-1, iterable);
else
return findPivot(arr, mid + 1, high, iterable);
}
function binarySearch(arr, low, high, val, iterable)
{
if (high < low)
return low;
var mid = Math.floor((low + high)/2);
if (iterable(val) == iterable(arr[mid]))
return mid;
if (iterable(val) > iterable(arr[mid]))
return binarySearch(arr, (mid + 1), high, val, iterable);
else
return binarySearch(arr, low, (mid -1), val, iterable);
}
function sortedIndex(array, value, iterable) {
var arr_size = array.length;
var pivot = findPivot(array, 0, arr_size-1, iterable);
if (pivot == -1) {
if(iterable(array[arr_size-1]) < iterable(value)){
return 0;
} else if(iterable(array[0]) > iterable(value)){
return arr_size-1;
}
return binarySearch(array, 0, arr_size-1, value, iterable);
}
if(iterable(array[pivot]) < iterable(value)){
return pivot+1;
} else if(iterable(array[pivot+1]) > iterable(value)){
return pivot;
}
if (iterable(array[pivot]) == iterable(value))
return pivot;
if (iterable(array[0]) <= iterable(value))
return binarySearch(array, 0, pivot-1, value, iterable);
else
return binarySearch(array, pivot+1, arr_size-1, value, iterable);
}
Here's the test cases: http://jsbin.com/ratufewa/1/edit
Hopefully this is in the right direction.
Iterative solution http://jsbin.com/ratufewa/3/edit :
function findPivot(arr, low, high, iterable)
{
while(true){
// base cases
if (high < low) return -1;
if (high == low) return low;
var mid = (low + high) >>> 1;
if (mid < high && iterable(arr[mid]) > iterable(arr[mid + 1]))
return mid;
if (mid > low && iterable(arr[mid]) < iterable(arr[mid - 1]))
return (mid-1);
if (iterable(arr[low]) >= iterable(arr[mid]))
high = mid-1;
else
low = mid + 1;
}
}
function binarySearch(arr, low, high, val, iterable)
{
while(true){
if (high < low)
return low;
var mid = (low + high) >>> 1;
if (iterable(val) == iterable(arr[mid]))
return mid;
if (iterable(val) > iterable(arr[mid]))
low = mid + 1;
else
high = mid -1;
}
}
function sortedIndex(array, value, iterable) {
var arr_size = array.length;
var pivot = findPivot(array, 0, arr_size-1, iterable);
if (pivot == -1) {
if(iterable(array[arr_size-1]) < iterable(value)){
return 0;
} else if(iterable(array[0]) > iterable(value)){
return arr_size-1;
}
return binarySearch(array, 0, arr_size-1, value, iterable);
}
if(iterable(array[pivot]) < iterable(value)){
return pivot+1;
} else if(iterable(array[pivot+1]) > iterable(value)){
return pivot;
}
if (iterable(array[pivot]) == iterable(value))
return pivot;
if (iterable(array[0]) <= iterable(value))
return binarySearch(array, 0, pivot-1, value, iterable);
else
return binarySearch(array, pivot+1, arr_size-1, value, iterable);
}
source to share
Typically, in a circular buffer, you store the beginning and end of the actually occupied locations. With this information, it should be pretty trivial as we can distinguish three cases:
function sortedIndex(buffer, item, getValue) {
if (buffer.start < buffer.end)
// do standard binary search between start and end indices
else if (getValue(buffer[0]) <= getValue(item))
// do standard binary search between 0 and end index
else // getValue(buffer[0] > getValue(item)
// do standard binary search between start and buffer.length
}
source to share