/** Additions to $(STDMODULE _math).

Copyright: Denis Shelomovskij 2011-2012

License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).

Authors: Denis Shelomovskij
*/
module unstd.math;


public import std.math;

import core.bitop: bsr;


@safe pure nothrow @nogc:


/**
Returns $(D true) iff $(D n) is a power of 2.

Preconditions:
$(D n) must be non-zero.
*/
bool isPowerOf2(in size_t n)
in { assert(n > 0); }
body { return !((n - 1) & n); }

unittest
{
	static assert( isPowerOf2(1));
	static assert( isPowerOf2(2));
	static assert(!isPowerOf2(3));
	static assert( isPowerOf2(4));
	static assert(!isPowerOf2(5));
}


/**
Returns largest power of 2 which <= $(D n).

Preconditions:
$(D n) must be non-zero.
*/
size_t roundDownToPowerOf2(in size_t n)
in { assert(n > 0); }
body { return 1 << bsr(n); }

unittest
{
	alias down = roundDownToPowerOf2;
	static assert(!__traits(compiles, { enum e = down(0); }));
	static assert(down(1) == 1);
	static assert(down(2) == 2 && down(3) == 2);
	static assert(down(4) == 4 && down(5) == 4);
	static assert(down(6) == 4 && down(7) == 4);
	static assert(down(8) == 8 && down(9) == 8);
}


/**
Returns smallest power of 2 which >= $(D n).

Preconditions:
$(D n) must be non-zero.
*/
size_t roundUpToPowerOf2(in size_t n)
in { assert(n > 0); }
body { return 1 << (bsr(n) + !isPowerOf2(n)); }

unittest
{
	alias up = roundUpToPowerOf2;
	static assert(!__traits(compiles, { enum e = up(0); }));
	static assert(up(1) == 1);
	static assert(up(2) == 2);
	static assert(up(3) == 4 && up(4) == 4);
	static assert(up(5) == 8 && up(6) == 8);
	static assert(up(7) == 8 && up(8) == 8);
}


/**
Returns the base-2 logarithm of largest power of 2 which <= $(D n).

Preconditions:
$(D n) must be non-zero.
*/
ubyte log2RoundedDown(in size_t n)
in { assert(n > 0); }
body { return cast(ubyte) bsr(n); }

unittest
{
	static assert(log2RoundedDown(1) == 0);
	static assert(log2RoundedDown(1023) == 9);
	static assert(log2RoundedDown(1024) == 10);
	static assert(log2RoundedDown(1025) == 10);
}


/**
Returns the base-2 logarithm of smallest power of 2 which >= $(D n).

Preconditions:
$(D n) must be non-zero.
*/
ubyte log2RoundedUp(in size_t n)
in { assert(n > 0); }
body { return cast(ubyte) (bsr(n) + !isPowerOf2(n)); }

unittest
{
	static assert(log2RoundedUp(1) == 0);
	static assert(log2RoundedUp(1023) == 10);
	static assert(log2RoundedUp(1024) == 10);
	static assert(log2RoundedUp(1025) == 11);
}


/**
Aligns $(D n) up or down.

Preconditions:
$(D alignment) must be power of 2.
*/
size_t alignDown(in size_t alignment, in size_t n)
in { assert(isPowerOf2(alignment)); }
body
{
	return n & ~(alignment - 1); // alignment - 1: 0b11, 0b111, ...
}

/// ditto
size_t alignDown(size_t alignment)(in size_t n) if(isPowerOf2(alignment))
{ return .alignDown(alignment, n); }

/// ditto
size_t alignUp(in size_t alignment, in size_t n)
in { assert(isPowerOf2(alignment)); }
body
{
	return alignDown(alignment, n + alignment - 1);	
}

/// ditto
size_t alignUp(size_t alignment)(in size_t n) if(isPowerOf2(alignment))
{ return .alignUp(alignment, n); }

/**
Aligns $(D n) up or down.

Preconditions:
$(D alignment) must be power of 2.
*/
bool isAligned(in size_t alignment, in size_t n)
in { assert(isPowerOf2(alignment)); }
body
{
	return !(n & (alignment - 1)); // alignment - 1: 0b11, 0b111, ...
}

/// ditto
bool isAligned(size_t alignment)(in size_t n) if(isPowerOf2(alignment))
{ return .isAligned(alignment, n); }

unittest
{
	import unstd.generictuple;

	foreach(f; GenericTuple!(alignDown, alignUp, isAligned))
	{
		static assert(!__traits(compiles, f!0(1)));
		static assert(!__traits(compiles, { enum e = f(0, 1); }));
	}

	foreach(n; iotaTuple!5)
	{
		foreach(f; GenericTuple!(alignDown, alignUp))
		{
			static assert(f!1(n) == n);
			static assert(f(1, n) == n);
		}
		static assert(isAligned!1(n));
		static assert(isAligned(1, n));
	}

	foreach(alignment; expressionTuple!(2, 4, 8, 16))
	{
		static assert(!__traits(compiles, alignDown!(alignment + 1)(1)));
		static assert(!__traits(compiles, alignUp!(alignment + 1)(1)));
		
		alias down = alignDown!alignment;
		alias up = alignUp!alignment;
		alias aligned = isAligned!alignment;
		static assert(down(0) == 0 && up(0) == 0 && aligned(0));

		static assert(down(1) == 0);
		static assert(down(alignment - 1) == 0);
		static assert(down(alignment) == alignment);
		static assert(down(alignment + 1) == alignment);

		static assert(up(1) == alignment);
		static assert(up(alignment - 1) == alignment);
		static assert(up(alignment) == alignment);
		static assert(up(alignment + 1) == alignment * 2);

		static assert(!aligned(1));
		static assert(!aligned(alignment - 1));
		static assert( aligned(alignment));
		static assert(!aligned(alignment + 1));
	}

	static assert(alignDown!2(size_t.max) == size_t.max - 1);
	static assert(alignDown!16(size_t.max) == size_t.max - 15);
	static assert(alignUp!2(size_t.max - 1) == size_t.max - 1);
	static assert(alignUp!2(size_t.max) == 0);
	static assert(!isAligned!2(size_t.max));
	static assert( isAligned!16(size_t.max - 15));
}