Randomized slide to front

rstf.d

// Suggested in http://forum.dlang.org/post/n3ifba$ulq$1@digitalmars.com

// TODO: constraints for needle search aren't accurate

///
template randomSlideToFront(alias pred = "a == b")
{
	import std.random : isUniformRNG;
	import std.range.primitives;
	import std.traits : ifTestable;

	private Range rstfImpl(Range, RNG, Needles...)(Range range, ref RNG rndGen,
		Needles needles)
	{
		import std.algorithm.mutation : swapAt;
		import std.algorithm.searching : countUntil;
		import std.random : uniform;

		immutable index = countUntil!pred(range, needles);
		if (index == -1)
		{
			static if (isInfinite!Range)
				assert(false);
			else
				return range[$ .. $];
		}
		else
		{
			immutable swapTargetIndex = uniform(0, index, rndGen);
			swapAt(range, swapTargetIndex, index);
			return range[swapTargetIndex .. $];
		}
	}

	/++
	 + Perform linear search in range and slide the found element(s) a random
	 + number of slots toward the front of the _range.
	 +
	 + With repeated searches, oft-searched elements gradually creep toward the
	 + front where they will be found in shorter time. Randomized sliding toward
	 + the front avoids some pitfalls of classic Bring to Front, for example:
	 + the former performs well also when searches are alternated between two
	 + elements.
	 +
	 + Can either be called with one or more _needles and an optional binary
	 + predicate, or without _needles and a required unary predicate.
	 +
	 + Params:
	 +    pred = binary predicate determining equality of elements and _needles
	 +    (defaults to $(D a == b))
	 +    range = _range to search in
	 +    rndGen = random number generator to use when determining the number of
	 +    slots to slide (defaults to $(XREF random, _rndGen))
	 +    needle = first _needle to search for
	 +    needles = optional, variadic set of other _needles to search for
	 +
	 + Params:
	 +    pred = unary predicate returning $(D true) for a matching element
	 +    range = _range to search in
	 +    rndGen = random number generator to use when determining the number of
	 +    slots to slide (defaults to $(XREF random, _rndGen))
	 +
	 + Returns:
	 +    range advanced such that the front element is the one searched for
	 +    after it has been slid toward the front of the _range, or an empty
	 +    _range when the search didn't yield a match
	 +/
	Range randomSlideToFront(Range, Needle, Needles...)(Range range,
		Needle needle, Needles needles)
		if (isRandomAccessRange!Range && hasSlicing!Range &&
			hasAssignableElements!Range)
	{
		import std.random : rndGen;
		return rstfImpl(range, rndGen, needle, needles);
	}

	/// Ditto
	Range randomSlideToFront(Range, RNG, Needle, Needles...)(Range range,
		ref RNG rndGen, Needle needle, Needles needles)
		if (isRandomAccessRange!Range && hasSlicing!Range &&
			hasAssignableElements!Range && isUniformRNG!RNG)
	{
		return rstfImpl(range, rndGen, needle, needles);
	}

	/// Ditto
	Range randomSlideToFront(Range)(Range range)
		if (isRandomAccessRange!Range && hasSlicing!Range &&
			hasAssignableElements!Range && ifTestable!(ElementType!Range, pred))
	{
		import std.random : rndGen;
		return rstfImpl(range, rndGen);
	}

	/// Ditto
	Range randomSlideToFront(Range, RNG)(Range range, ref RNG rndGen)
		if (isRandomAccessRange!Range && hasSlicing!Range &&
			hasAssignableElements!Range && isUniformRNG!RNG &&
			ifTestable!(ElementType!Range, pred))
	{
		return rstfImpl(range, rndGen);
	}
}

///
@safe unittest
{
	import std.range.primitives;

	int[5] array = [1, 2, 3, 4, 5];
	assert(array[].randomSlideToFront(3).front == 3);
	assert(array[2] < 3);

	array = [1, 2, 3, 4, 5];
	assert(array[].randomSlideToFront(6, 3, 0, 9).front == 3);
	assert(array[2] < 3);

	array = [1, 2, 3, 4, 5];
	assert(array[].randomSlideToFront!(a => a > 3).front == 4);
	assert(array[3] < 4);

	assert(array[].randomSlideToFront(6).empty);
}

@safe unittest
{
	import std.internal.test.dummyrange, std.meta, std.random;

	alias DummyRanges = AliasSeq!(
		DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Random),
		DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random),
		);//DummyRange!(ReturnBy.Reference, Length.No, RangeType.Random));

	auto rndGen = Random(unpredictableSeed);

	foreach (DummyRange; DummyRanges)
	{
		DummyRange r;
		r.reinit();
		assert(r.randomSlideToFront(5).front == 5);
		assert(r[4] < 5);

		assert(r.randomSlideToFront(6, rndGen).front == 6);
		assert(r[5] < 6);
	}
}