module RandomSample;

import std.range;
import std.random;
import std.stdio;

struct RandomSample( R ) if ( isInputRange!R ) {
	R range;
	ElementType!( R )[] _front;
	bool empty;
	Random rnd;
	ulong pos;
	
	this( R r, size_t num ) {
		static if ( isForwardRange!R ) {
			range = r.save;
		} else {
			range = r;
		}
		_front = array( take( range, num ) );
		static if ( isForwardRange!R ) {
			popFrontN( range, num );
		}
		
		empty = false;
		rnd = Random( unpredictableSeed );
		pos = num;
	}
	
	@property ElementType!(R)[] front( ) {
		return _front.dup;
	}
	
	void popFront( ) {
		assert( !empty );
		if ( uniform( 0, pos, rnd ) < _front.length ) {
			_front[ uniform( 0, _front.length, rnd ) ] = range.front;
		}
		range.popFront( );
		pos++;
		empty = range.empty;
	}
}

RandomSample!R randomSampleRange( R )( R r, size_t num = 1 ) if ( isInputRange!R ) {
	return RandomSample!R( r, num );
}

T[] randomSampleImpl( T, R )( T[] result, R r ) {
	auto rnd = Random( unpredictableSeed );
	foreach ( i, e; r ) {
		if ( uniform( 0, result.length + i + 1, rnd ) < result.length ) {
			result[ uniform( 0, result.length, rnd ) ] = e;
		}
	}
	return result;
}

ElementType!( R )[] randomSample( R )( R r, size_t num = 1 ) if ( isInputRange!R && !isForwardRange!R ) {
	auto result = array( take( r, num ) );
	return randomSampleImpl( result, rr );
}

ElementType!( R )[] randomSample( R )( R r, size_t num = 1 ) if ( isForwardRange!R ) {
	auto rr = r.save;
	auto result = array( take( rr, num ) );
	popFrontN( rr, num );
	return randomSampleImpl( result, rr );
}

void main( ) {
	writeln( "Range sample:" );
	foreach ( e; randomSampleRange( "Sample text", 3 ) ) {
		writeln( e );
	}
	writeln( "Single sample:" );
	writeln( randomSample( "Sample text", 3 ) );
}