binarysearch

import std.functional : binaryFun;
debug import std.stdio;

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.infEqual(0) == heystack.length);
	assert (heystack.infEqual(2) == heystack.length);
	assert (heystack.infEqual(4) == heystack.length);
	assert (heystack.infEqual(6) == heystack.length);
	assert (heystack.infEqual(1) == 0);
	assert (heystack.infEqual(3) == 2);
	assert (heystack.infEqual(5) == 6);
}

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.supEqual(0) == -1);
	assert (heystack.supEqual(2) == -1);
	assert (heystack.supEqual(4) == -1);
	assert (heystack.supEqual(6) == -1);
	assert (heystack.supEqual(1) == 1);
	assert (heystack.supEqual(3) == 5);
	assert (heystack.supEqual(5) == 7);
}

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.infGreat(0) == 0);
	assert (heystack.infGreat(1) == 2);
	assert (heystack.infGreat(2) == 2);
	assert (heystack.infGreat(3) == 6);
	assert (heystack.infGreat(4) == 6);
	assert (heystack.infGreat(5) == heystack.length);
	assert (heystack.infGreat(6) == heystack.length);
}

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.supSmall(0) == -1);
	assert (heystack.supSmall(1) == -1);
	assert (heystack.supSmall(2) == 1);
	assert (heystack.supSmall(3) == 1);
	assert (heystack.supSmall(4) == 5);
	assert (heystack.supSmall(5) == 5);
	assert (heystack.supSmall(6) == 7);
}

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.infGrtEq(0) == 0);
	assert (heystack.infGrtEq(1) == 0);
	assert (heystack.infGrtEq(2) == 2);
	assert (heystack.infGrtEq(3) == 2);
	assert (heystack.infGrtEq(4) == 6);
	assert (heystack.infGrtEq(5) == 6);
	assert (heystack.infGrtEq(6) == heystack.length);
}

unittest ///
{
	auto heystack = [1, 1, 3, 3, 3, 3, 5, 5];
	assert (heystack.supSmlEq(0) == -1);
	assert (heystack.supSmlEq(1) == 1);
	assert (heystack.supSmlEq(2) == 1);
	assert (heystack.supSmlEq(3) == 5);
	assert (heystack.supSmlEq(4) == 5);
	assert (heystack.supSmlEq(5) == 7);
	assert (heystack.supSmlEq(6) == 7);
}

/** Binary search methods from an array.
 *
 * alias less is used to compare only Needle and ElementType!Heystack:
 * one can search needle.f in heystack.map!g by modifying alias less.
**/
ptrdiff_t infEqual(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		// loop invariant: if (answer < length) then left <= answer < right.
		immutable middle = left.mp(right);
		if (less(needle, heystack[middle]))
			right = middle;
		else if (needle == heystack[middle])
		{
			if (right == middle + 1) // we need this to avoid infinite loops when there are more than one needles in heystack.
				return needle == heystack[left] ? left : middle;
			right = middle + 1;
		}
		else
			left = middle;
		debug (infEqual) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return needle == heystack[left] ? left : heystack.length;
}

/// ditto
ptrdiff_t supEqual(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		immutable middle = left.mp(right);
		if (less(needle, heystack[middle]))
			right = middle;
		else
			left = middle;
		debug (supEqual) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return needle == heystack[left] ? left : -1;
}

/// ditto
ptrdiff_t infGreat(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	if (!less(needle, heystack[$-1]))
		return heystack.length;
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		immutable middle = left.mp(right);
		if (!less(needle, heystack[middle - 1]))
			left = middle;
		else
			right = middle;
		debug (infGreat) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return left;
}

/// ditto
ptrdiff_t supSmall(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	if (less(needle, heystack[0]) || needle == heystack[0])
		return -1;
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		immutable middle = left.mp(right);
		if (less(needle, heystack[middle]) || needle == heystack[middle])
			right = middle;
		else
			left = middle;
		debug (supSmall) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return left;
}

/// ditto
ptrdiff_t infGrtEq(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	if (!less(needle, heystack[$-1]) && needle != heystack[$-1])
		return heystack.length;
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		immutable middle = left.mp(right);
		if (!less(needle, heystack[middle - 1]) && needle != heystack[middle-1])
			left = middle;
		else
			right = middle;
		debug (infGrtEq) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return left;
}

/// ditto
ptrdiff_t supSmlEq(alias less=binaryFun!"a<b", Heystack, Needle)(Heystack heystack, Needle needle)
{
	if (less(needle, heystack[0]))
		return -1;
	size_t left, right = heystack.length;
	while (left + 1 < right)
	{
		immutable middle = left.mp(right);
		if (less(needle, heystack[middle]))
			right = middle;
		else
			left = middle;
		debug (supSmlEq) stderr.writefln("[%(%d %)]", heystack[left..right]);
	}
	return left;
}

private size_t mp(size_t left, size_t right)
in
{
	assert (left + 1 < right);
}
out (middle)
{
	assert (left < middle);
	assert (middle < right);
}
body
{
	return left + ((right - left) >> 1);
}

diff.txt

pre / post
infEqual post:
	return needle == heystack[left] ? left : heystack.length;
supEqual post:
	return needle == heystack[left] ? left : -1;
infGreat pre:
	if (!less(needle, heystack[$-1]))
		return heystack.length;
supSmall pre:
	if (less(needle, heystack[0]) || needle == heystack[0])
		return -1;
infGrtEq pre:
	if (!less(needle, heystack[$-1]) && needle != heystack[$-1])
		return heystack.length;
supSmlEq pre:
	if (less(needle, heystack[0]))
		return -1;

loop
infEqual
	if (less(needle, heystack[middle]))
		right = middle;
	else if (needle == heystack[middle])
	{
		if (right == middle + 1) // we need this to avoid infinite loops when there are more than one needles in heystack.
			return needle == heystack[left] ? left : middle;
		right = middle + 1;
	}
	else
		left = middle;
supEqual
	if (less(needle, heystack[middle]))
		right = middle;
	else
		left = middle;
infGreat
	if (!less(needle, heystack[middle - 1]))
		left = middle;
	else
		right = middle;
supSmall
	if (less(needle, heystack[middle]) || needle == heystack[middle])
		right = middle;
	else
		left = middle;
infGrtEq
	if (!less(needle, heystack[middle - 1]) && needle != heystack[middle-1])
		left = middle;
	else
		right = middle;
supSmlEq
	if (less(needle, heystack[middle]))
		right = middle;
	else
		left = middle;