import std.range;
import std.functional;
import std.array;
import core.exception;
import std.exception;
import std.typecons;

/**
 * Returns the most extreme value as well as the number of items in $(D range) matching the most
 * extreme value, as decided by the predicate $(D pred). Will return 0 for empty ranges, 1 or more
 * for ranges of one or more items.
----
assert( extremumCount!"a<b"( [1, 2, 3, 1, 2, 3] ) == 2 );
assert( extremumCount!"a.length<b.length"( ["a", "bc", "de", "fg"] ) == 1 );
----
 */
Tuple!( ElementType!Range, size_t ) extremumCount( alias pred, Range )( Range range ) if ( isInputRange!Range ) {
	alias binaryFun!pred fn;
	
	if ( range.empty ) {
		return typeof(return)( ElementType!( Range ).init, 0);
	}
	
	size_t result = 1;
	
	ElementType!Range extremeElement = range.front;
	range.popFront( );
	
	foreach ( e; range ) {
		if ( fn( e, extremeElement ) ) {
			extremeElement = e;
			result = 1;
		} else if ( !fn( extremeElement, e ) ) {
			result++;
		}
	}
	
	return tuple( extremeElement, result );
}

unittest {
	assert( extremumCount!"a<b"( [1, 2, 3, 1, 2, 3] ) == tuple( 1, 2 ) );
	assert( extremumCount!"a>b"( [1, 2, 3, 1, 2, 3] ) == tuple( 3, 2 ) );
	assert( extremumCount!"a>b"( new int[0] ) == tuple( 0, 0 ) );
	assert( extremumCount!"a.length<b.length"( ["a", "bc", "de", "fg"] ) == tuple( "a", 1 ) );
	assert( extremumCount!"a.length>b.length"( ["a", "bc", "d", "ef"] ) == tuple( "bc", 2 ) );
}

/**
 * Returns the position of the element of the most extreme value in the forward range $(D range), as
 * decided by the predicate $(D pred).
 * i.e. a  subrange of $(D range) starting at the position of the element of the most extreme value
 * and with the same ending as $(D range).
----
assert( extremumPos!"a<b"( [1, 2, 3, 1, 2, 3] ) == [1, 2, 3, 1, 2, 3] );
assert( extremumPos!"a>b"( [1, 2, 3, 1, 2, 3] ) == [3, 1, 2, 3] );
----
 */
Range extremumPos( alias pred, Range )( Range range ) if ( isForwardRange!Range ) {
	alias binaryFun!pred fn;
	
	if ( range.empty ) {
		return range;
	}
	
	Range result = range.save( );
	
	for ( ; !range.empty; range.popFront( )) {
		if ( fn( range.front, result.front ) && !fn( result.front, range.front ) ) {
			result = range.save( );
		}
	}
	
	return result;
}

unittest {
	assert( extremumPos!"a<b"( [1, 2, 3, 1, 2, 3] ) == [1, 2, 3, 1, 2, 3] );
	assert( extremumPos!"a>b"( [1, 2, 3, 1, 2, 3] ) == [3, 1, 2, 3] );
}

/**
 * Returns an array of all the elements of $(D range) matching the most extreme value, as
 * determined by the predicate $(D pred). Will return 0 for empty ranges, 1 or more for non-empty.
----
assert( extremumArg!"a.length<b.length"( ["a", "bc", "d", "ef"] ) == ["a", "d"] );
assert( extremumArg!"a<b"( new int[0] ) == [] );
assert( extremumArg!"a<b"( [1, 2, 3, 1, 2, 3] ) == [1, 1] );
----
 */
ElementType!Range[] extremumArg( alias pred, Range )( Range range ) if ( isInputRange!Range ) {
	alias binaryFun!pred fn;
	
	if ( range.empty ) {
		return [];
	}
	
	auto result = Appender!( ElementType!( Range )[] )( );
	result.put( range.front );
	range.popFront( );
	
	foreach ( e; range ) {
		if ( fn( e, result.data[0] ) ) {
			result.clear( );
			result.put( e );
		} else if ( !fn( result.data[0], e ) ) {
			result.put( e );
		}
	}
	
	return result.data;
}

unittest {
	assert( extremumArg!"a.length<b.length"( ["a", "bc", "d", "ef"] ) == ["a", "d"] );
	assert( extremumArg!"a.length>b.length"( ["a", "bc", "d", "ef"] ) == ["bc", "ef"] );
	assert( extremumArg!"a<b"( [1,2,3] ) == [1] );
	assert( extremumArg!"a<b"( new int[0] ) == [] );
	assert( extremumArg!"a<b"( [1, 2, 3, 1, 2, 3] ) == [1, 1] );
	assert( extremumArg!"a>b"( [1, 2, 3, 1, 2, 3] ) == [3, 3] );
	assert( extremumArg!"(a|1)>(b|1)"( [1, 2, 3, 1, 2, 3] ) == [2, 3, 2, 3] );
}

/**
 * Returns the first element of $(D range) with the most extreme value, as determined by
 * $(D pred).
 * An exception is thrown if $(D range) is empty.
----
assert( extremum!"a<b"([1,2,3]) == 1 );
assert( extremum!"a<b"([1,2,3,1,2,3]) == 1 );
----
 */
ElementType!Range extremum( alias pred, Range )( Range range ) if ( isInputRange!Range ) {
	alias binaryFun!pred fn;
	
	if ( range.empty ) {
		throw new RangeError("Range violation");
	}
	
	ElementType!Range result = range.front;
	range.popFront( );
	
	foreach ( e; range ) {
		if ( fn( e, result ) ) {
			result = e;
		}
	}
	
	return result;
}

unittest {
	assert( extremum!"a<b"([1,2,3]) == 1 );
	assert( extremum!"a<b"([1,2,3,1,2,3]) == 1 );
	assert( extremum!"a.length>b.length"( ["a", "bc", "d", "ef"] ) == "bc" );
	assertThrown!RangeError( extremum!"a<b"( new int[0] ) );
}

/**
 * Returns an array of all minimal elements of $(D range), optionally determined by the unary
 * function $(D fun).
----
assert( minArg( [1, 2, 3, 1, 2, 3] ) == [1, 1] );
assert( minArg!"3 - a.length"( ["ab", "c", "de", "f"] ) == ["ab", "de"] );
assert( minArg("Bananas") == "B" );
----
 */
ElementType!Range[] minArg( Range )( Range range ) if ( isInputRange!Range ) {
	return extremumArg!"a<b"( range );
}

ElementType!Range[] minArg( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremumArg!( ( a, b ){ return fn( a ) < fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) < fn( b ); };
	return extremumArg!fn2( range );
}

unittest {
	assert( minArg( [1, 2, 3, 1, 2, 3] ) == [1, 1] );
	assert( minArg!"a"( [1, 2, 3, 1, 2, 3] ) == [1, 1] );
	assert( minArg( ["a", "bc", "c", "de"] ) == ["a"] );
	assert( minArg!"a.length"( [[1], [2], [3,4], [5,6]] ) == [[1], [2]] );
	assert( minArg!"3 - a.length"( ["ab", "c", "de", "f"] ) == ["ab", "de"] );
	assert( minArg("bananas") == "aaa" );
	assert( minArg("Bananas") == "B" );
}

/**
 * Returns the minimal element of $(D range), optionally determined by the unary function $(D fun).
----
assert( min( ["a", "bc", "c", "de"] ) == "a" );
assert( min!"a.length"( [[1], [2], [3,4], [5,6]] ) == [1] );
----
 */
ElementType!Range min( Range )( Range range ) if ( isInputRange!Range ) {
	return extremum!"a<b"( range );
}

ElementType!Range min( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) < fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) < fn( b ); };
	return extremum!fn2( range );
}

unittest {
	assert( min( [1, 2, 3, 1, 2, 3] ) == 1);
	assert( min!"a"( [1, 2, 3, 1, 2, 3] ) == 1 );
	assert( min( ["a", "bc", "c", "de"] ) == "a" );
	assert( min!"a.length"( [[1], [2], [3,4], [5,6]] ) == [1] );
	assert( min!"3 - a.length"( ["ab", "c", "de", "f"] ) == "ab" );
	assert( min("bananas") == 'a' );
	assert( min("Bananas") == 'B' );
}

/**
 * Returns the minimal element of $(D range), along with the number of occurences. The minimal
 * element may optionally be determined by the unary function $(D fun).
----
assert( minCount( [1, 2, 3, 1, 2] ) == tuple( 1, 2 ) );
assert( minCount( "bananas" ) == tuple( 'a', 3 ) );
----
 */
Tuple!( ElementType!Range, size_t ) minCount( Range )( Range range ) if ( isInputRange!Range ) {
	return extremumCount!"a<b"( range );
}

Tuple!( ElementType!Range, size_t ) minCount( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) < fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) < fn( b ); };
	return extremumCount!fn2( range );
}

unittest {
	assert( minCount( [1, 2, 3, 1, 2] ) == tuple( 1, 2 ) );
	assert( minCount( "bananas" ) == tuple( 'a', 3 ) );
	assert( minCount( "" ) == tuple( dchar.init, 0 ) );
	assert( minCount!"a.length"( ["a", "bc", "d", "ef"] ) == tuple( "a", 2 ) );
}

/**
 * Returns the position of the minimal element of forward range $(D range), i.e. a subrange of
 * $(D range) starting at the position of its smallest element, and having the same ending as
 * $(D range). The smallest element may optionally be determined by the unary function $(D fun).
----
assert( minPos( "teaspoon" ) == "aspoon" );
assert( minPos!"a.length"( ["ab", "bc", "d", "ef"] ) == ["d", "ef"] );
----
 */
Range minPos( Range )( Range range ) if ( isForwardRange!Range ) {
	return extremumPos!"a<b"( range );
}

Range minPos( alias fun, Range )( Range range ) if ( isForwardRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) < fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) < fn( b ); };
	return extremumPos!fn2( range );
}

unittest {
	assert( minPos( [1, 2, 3, 1, 2, 3] ) == [1, 2, 3, 1, 2, 3] );
	assert( minPos( "teaspoon" ) == "aspoon" );
	assert( minPos!"a.length"( ["ab", "bc", "d", "ef"] ) == ["d", "ef"] );
}


/**
 * Returns an array of all maximal elements of $(D range), optionally determined by the unary
 * function $(D fun).
----
assert( maxArg( ["a", "bc", "c", "de"] ) == ["de"] );
assert( maxArg!"a.length"( [[1], [2], [3,4], [5,6]] ) == [[3,4], [5,6]] );
----
 */
ElementType!Range[] maxArg( Range )( Range range ) if ( isInputRange!Range ) {
	return extremumArg!"a>b"( range );
}

ElementType!Range[] maxArg( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) > fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) > fn( b ); };
	return extremumArg!fn2( range );
}

unittest {
	assert( maxArg( [1, 2, 3, 1, 2, 3] ) == [3, 3] );
	assert( maxArg!"a"( [1, 2, 3, 1, 2, 3] ) == [3, 3] );
	assert( maxArg( ["a", "bc", "c", "de"] ) == ["de"] );
	assert( maxArg!"a.length"( [[1], [2], [3,4], [5,6]] ) == [[3,4], [5,6]] );
	assert( maxArg!"3 - a.length"( ["ab", "c", "de", "f"] ) == ["c", "f"] );
	assert( maxArg("bananas") == "s" );
	assert( maxArg("Seashore") == "s" );
}


/**
 * Returns the maximal element of $(D range), optionally determined by the unary function $(D fun).
----
	assert( max( [1, 2, 3, 1, 2, 3] ) == 3 );
	assert( max("bananas") == 's' );
	assert( max!"a.length"( [[1], [2], [3,4], [5,6]] ) == [3,4] );
----
 */
ElementType!Range max( Range )( Range range ) if ( isInputRange!Range ) {
	return extremum!"a>b"( range );
}

ElementType!Range max( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremumArg!( ( a, b ){ return fn( a ) > fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) > fn( b ); };
	return extremum!fn2( range );
}

unittest {
	assert( max( [1, 2, 3, 1, 2, 3] ) == 3 );
	assert( max!"a"( [1, 2, 3, 1, 2, 3] ) == 3 );
	assert( max( ["a", "bc", "c", "de"] ) == "de" );
	assert( max!"a.length"( [[1], [2], [3,4], [5,6]] ) == [3,4] );
	assert( max!"3 - a.length"( ["ab", "c", "de", "f"] ) == "c" );
	assert( max("bananas") == 's' );
	assert( max("Seashore") == 's' );
}


/**
 * Returns the maximal element of $(D range), along with the number of occurences. The maximal
 * element may optionally be determined by the unary function $(D fun).
----
assert( maxCount( [1, 2, 3, 2, 3] ) == tuple( 3, 2 ) );
assert( maxCount( "bananas" ) == tuple( 's', 1 ) );
----
 */
Tuple!( ElementType!Range, size_t ) maxCount( Range )( Range range ) if ( isInputRange!Range ) {
	return extremumCount!"a>b"( range );
}

Tuple!( ElementType!Range, size_t )  maxCount( alias fun, Range )( Range range ) if ( isInputRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) > fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) > fn( b ); };
	return extremumCount!fn2( range );
}

unittest {
	assert( maxCount( [1, 2, 3, 2, 3] ) == tuple( 3, 2 ) );
	assert( maxCount( "bananas" ) == tuple( 's', 1 ) );
	assert( maxCount( "" ) == tuple( dchar.init, 0 ) );
	assert( maxCount!"a.length"( ["a", "bc", "d", "ef"] ) == tuple( "bc", 2 ) );
}


/**
 * Returns the position of the maximal element of forward range $(D range), i.e. a subrange of
 * $(D range) starting at the position of its largest element, and having the same ending as
 * $(D range). The largest element may optionally be determined by the unary function $(D fun).
----
assert( maxPos( "Teaspoon" ) == "spoon" );
assert( maxPos!"a.length"( ["a", "bc", "d", "ef"] ) == ["bc", "d", "ef"] );
----
 */
Range maxPos( Range )( Range range ) if ( isForwardRange!Range ) {
	return extremumPos!"a>b"( range );
}

Range maxPos( alias fun, Range )( Range range ) if ( isForwardRange!Range ) {
	alias unaryFun!fun fn;
	//return extremum!( ( a, b ){ return fn( a ) > fn( b ); } )( range ); // Bug.
	
	auto fn2 = ( ElementType!Range a, ElementType!Range b ){ return fn( a ) > fn( b ); };
	return extremumPos!fn2( range );
}

unittest {
	assert( maxPos( [1, 2, 3, 1, 2, 3] ) == [3, 1, 2, 3] );
	assert( maxPos( "Teaspoon" ) == "spoon" );
	assert( maxPos!"a.length"( ["a", "bc", "d", "ef"] ) == ["bc", "d", "ef"] );
}