/** 
 * A D programming language implementation of the 
 * General Decimal Arithmetic Specification, 
 * Version 1.70, (25 March 2009).
 *
 * by Paul D. Anderson
 *
 * Boost Software License - Version 1.0 - August 17th, 2003
 *
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
**/

module decimal.bcd;

import std.algorithm: max;
import std.conv: ConvError;
import std.math;
import std.stdio: write, writeln;
import std.string: strip;

alias ubyte Digit;

public immutable Bcd ZERO = { digits:[0] };
public immutable Bcd ONE  = { digits:[1] };
public immutable Bcd NEG_ONE = { sign:true, digits:[1] };

/+static this() {
	immutable(Bcd) MAX_LONG = cast(immutable) Bcd(long.max);
//	MAX_LONG = cast(immutable) Bcd(long.max);
	}+/

/**
 * Enumeration of available rounding modes.
 */
public enum Rounding {
	HALF_EVEN,
	HALF_DOWN,
	HALF_UP,
	DOWN,
	UP,
	FLOOR,
	CEILING,
}

/**
 * Provides BCD-encoded integral values of arbitrary length.
 *
 * Advantages of BCD:
 * To/from string is easy.
 * Easy to pull values of individual digits.
 * Easy to multiply and divide by powers of 10.
 * 
 * Disadvantages of BCD:
 * Significantly less compact representation.
 * Operations are carried out bytewise, requiring more iterations.
 * Extra steps required for addition.
 *
 */
public struct Bcd {

//--------------------------------
// members
//-------------------------------- 

	/**
	 * The sign of the BCD integer. Sign is kept explicitly
	 * and not encoded in the number.
	 **/
	private bool sign = false;
	
	/**
	 * An array of decimal digits in reverse (right-to-left) order
	 * representing an integral value. 
	 * Trailing zeros have no effect on the value of the number;
	 * they correspond to leading zeros in a left-to-right representation.
	**/
	private Digit[] digits = [ 0 ];
	
//--------------------------------
// construction
//-------------------------------- 

	//--------------------------------
	// copy construction
	//-------------------------------- 


	/**
	 * Copy constructor. Returns a (non-const) copy of the argument.
	 */
	public this(const Bcd bcd) {
		sign = bcd.sign;
		digits = bcd.digits.dup;
	}
	
	/**
	 * Copies a BCD integer and adjusts the number of digits,
	 * padding or turncating, if necessary.
	 */
	public this(const Bcd bcd, uint numDigits) {
		this(bcd);
		setNumDigits(numDigits);
	}
	
	//--------------------------------
	// construction from integer types.
	//-------------------------------- 

	/**
	 * Constructs a BCD integer from a (signed) byte, short, int or long value.
	 */
	public this(const long n) {
		ulong m;	
		if (n < 0) {
			sign = true;
			m = std.math.abs(n);
		}
		else {
			sign = false;
			m = n;
		}
		Digit[20] dig;
		int i = 0;
		do {
			ulong q = m/10;
			ulong r = m%10;
			dig[i] = cast(Digit) r;
			m = q;
			i++;
		} while (m > 0);
		digits = dig[0..i].dup;
	}
		
	/**
	 * Constructs a BCD integer from a (signed) byte, short,
	 * int or long value, and then adjusts the number of digits,
	 * padding or truncating as needed.
	 */
	public this(const long n, uint numDigits) {
		this = n;
		setNumDigits(numDigits);
	}
		
	unittest {
		write("this(long)..");
		Bcd p;
		p = -1234;
		assert(p == Bcd("-1234"));
		p = 12345678L;
		assert(p == Bcd("12345678"));
		p = Bcd(-19166586400L);
		assert(p == Bcd("-19166586400"));
		p = Bcd(139676498390L);
		assert(p == Bcd("139676498390"));
		writeln("passed");
	}

	//--------------------------------
	// construction from a string.
	//-------------------------------- 

	/**
	 * Constructs a BCD integer from a string representation.
	 * If the string has leading zeros they are retained internally.
	 */
	public this(const string str) {
		this = parse(str);
	}
	
//--------------------------------
// member access functions
//-------------------------------- 

	//--------------------------------
	// access to the sign of the number
	//-------------------------------- 

	const bool isSigned() {
		return sign;
	}
	
	void setSign(bool sign) {
		this.sign = sign;
	}
	
	//--------------------------------
	// access to the digits
	//-------------------------------- 

	/**
	 * Returns the number of digits in this BCD integer.
	 * Includes leading zero digits.
	 */
	const uint numDigits() {
		return digits.length;
	}
	
	/**
	 * Adjusts the number of digits in this BCD integer,
	 * padding or truncating if necessary. 
	 * If truncating, first leading zeros are stripped away, then
	 * the remainder is clipped.
	 */
	void setNumDigits(uint n) {
		if (n == 0) n++;
		digits.length = n;
	}

/+	/**
	 * Adjusts the number of digits in this BCD integer,
	 * padding or truncating if necessary. 
	 * If truncating, first leading zeros are stripped away, then
	 * the remainder is clipped.
	 */
	void setNumDigits(uint n) {
		stripl(this);
		if (n > digits.length) {
			digits.length = n;
		}
		else {
			this = truncate(this, n);
		}
	}+/
	
/+unittest {
	write("setWidth...");
	Bcd a;
	a = 1234567;
	a.setNumDigits(5);
	assert(a == Bcd(12345));
	a.setNumDigits(9);
	assert(a.toString == "000012345");
	writeln("passed");
}+/

	/**
	 * Returns the first digit of this BCD integer. If the
	 * integer has leading zeros this function will return 
	 * zero, but the value of the number is not necessarily zero.
	 */
	const uint firstDigit() {
		return digits[$-1];
	}
	
	/**
	 * Returns the last digit of this BCD integer.
	 */
	const uint lastDigit() {
		return digits[0];
	}
	
	/**
	 * Returns the specified digit of this BCD integer. The index is 
	 * zero based, i.e., getDigit(0) returns the first digit.
	 */
	const int getDigit(int n) {
		return digits[$-n-1];
	}
	
	/**
	 * Sets the specified digit of this BCD integer to the specified value.
	 * The index is zero based, i.e., getDigit(0) returns the first digit.
	 */
	void setDigit(uint n, Digit value) {
		assert(value < 10);
		digits[$-n-1] = value;
	}
	
/+	unittest {
		write("digits...");
		Bcd bcd;
		bcd = 12345678;
		assert(bcd.numDigits() == 8);
		assert(bcd.firstDigit() == 1);
		assert(bcd.lastDigit() == 8);
		assert(bcd.getDigit(3) == 4);
		bcd.setDigit(3, 7);
		assert(bcd.getDigit(3) == 7);
		bcd.setNumDigits(10);
		assert(bcd.numDigits == 10);
		assert(bcd.firstDigit() == 0);
		assert(bcd.getDigit(5) == 7);
		bcd.setNumDigits(5);
		assert(bcd.getDigit(2) == 3);
		writeln("passed");
	}+/
	
//--------------------------------
// Common object functions.
//-------------------------------- 

	/**
	 * Returns a string representation of this BCD integer.
	 * Leading zeros are displayed. The sign is displayed if
	 * the number is negative.
	 */
	const string toString() {
		return format(this);
	}
	
	unittest {
		write("toString...");
		writeln("passed");
	}
	
	/**
	 * Returns a hash code for this BCD integer.
	 */
	const hash_t toHash() {
		hash_t hash = 0;
		foreach(Digit digit; digits) {
			hash += digit;
		}
		return hash;
	}
	
	unittest {
		write("toHash...");
		writeln("passed");
	}
	
	/**
	 * Returns a mutable copy of this BCD integer.
	 */
	const Bcd dup() {
		Bcd bcd;
		bcd.sign = this.sign;
		bcd.digits = digits.dup;
		return bcd;
	}
	
//--------------------------------
// Utility functions.
//-------------------------------- 

	/**
	 * Returns true if the internal representation of
	 * this BCD integer has leading zeros.
	 */
	const bool hasLeadingZeros() {
		return numDigits > 1 && firstDigit == 0;
	}
	
	unittest {
	write("hasLeadingZeros...");
	assert(!ZERO.hasLeadingZeros);
	Bcd b = Bcd(0);
	assert(!b.hasLeadingZeros);
	b = "-00000001";
	assert(b.hasLeadingZeros);
	b = "-00000000";
	assert(b.hasLeadingZeros);
	writeln("passed");
	}
	
	/**
	 * Returns true if the value of this BCD integer is zero.
	 * Ignores leading zeros and sign.
	 */
	const bool isZero() {
		Bcd b = canonical(this);
		if (b.numDigits > 1) return false;
		return b.lastDigit == 0;
	}
	
	unittest {
	write("isZero.........");
	assert(ZERO.isZero);
	Bcd b = Bcd(0);
	assert(b.isZero);
	b = "-00000001";
	assert(!b.isZero);
	b = "-00000000";
	assert(b.isZero);
	writeln("passed");
	}
	
//--------------------------------
// casting operators.
//-------------------------------- 

	const long opCast() {
		Bcd MAX_LONG = Bcd(long.max);
		Bcd MIN_LONG = Bcd(long.min);

		if (this > MAX_LONG || this < MIN_LONG)
			throw new Exception("Can't cast -- out of range");
		
		long n = 0;
		foreach_reverse(Digit digit; digits) {
			n = 10*n + digit;
		}
		return this.sign ? -n : n;
	}
	
	unittest {
	write("cast(long)...");
	Bcd a;
	a = "12345678901234567890123456";
//	long n = cast(long) a;
	a = 12345678L;
	long n = cast(long) a;
	assert(n == 12345678L);
	int m = cast(int) a;
	assert(m == 12345678L);
	a = -a;
	m = cast(int) a;
	assert(m == -12345678L);
	
	writeln("passed");
}


//--------------------------------
// Assignment operators.
//-------------------------------- 

	/**
	 * Assignment operator for BCD integer to BCD integer operations.
	 */
	Bcd opAssign(const Bcd that) {
		this.sign = that.sign;
		this.digits = that.digits.dup;
		return this;
	}
	
	/**
	 * Converts the string argument into a BCD integer and assigns it 
	 * to this BCD integer.
	 */
	void opAssign(const string str) {
		this = Bcd(str);
	}
	
	/**
	 * Converts the integer argument into a BCD integer and assigns it 
	 * to this BCD integer.
	 */
	void opAssign(const long n) {
		this = Bcd(n);
	}
	
	
	// index operator
	Digit opIndex(uint index) {
		return this.digits[index];
	}
	
	// index assign operator
	void opIndexAssign(Digit value, uint index) {
		this.digits[index] = value;
	}
	
//--------------------------------
// unary operators
//-------------------------------- 
	
	const Bcd opPos() {
		return this.dup;
	}
	
	const Bcd opNeg() {
		return negate(this);
	}
	
	const Bcd opCom() {
		return twosComp(this);
	}
	
	const Bcd opNot() {
		return not(this);
	}
	
	Bcd opPostInc() {
		this = this + ONE;
		return this;
	}
	
	Bcd opPostDec() {
		this = this - ONE;
		return this;
	}
	
	const Bcd opShl(int n) {
		return shift(this, n);
	}
	
	Bcd opShlAssign(int n) {
		this = this << n;
		return this;
	}
	
	const Bcd opShr(int n) {
		return shift(this, -n);
	}
	
	Bcd opShrAssign(int n) {
		this = this >> n;
		return this;
	}
	
//--------------------------------
// binary operators
//-------------------------------- 
	
	const Bcd opAdd(T:Bcd)(const T addend) {
		return add(this, addend);
	}
	
	const Bcd opAdd(T)(const T addend) {
		return add(this, Bcd(addend));
	}
	
	Bcd opAddAssign(T)(const T addend) {
		this = this + addend;
		return this;
	}

	const Bcd opSub(T:Bcd)(const T addend) {
		return subtract(this, addend);
	}
	
	const Bcd opSub(T)(const T addend) {
		return subtract(this, Bcd(addend));
	}
	
	Bcd opSubAssign(T)(const T addend) {
		this = this - addend;
		return this;
	}

	const Bcd opMul(T:Bcd)(const T b) {
		return multiply(this, b);
	}
	
	const Bcd opMul(T)(const T b) {
		return multiply(this, Bcd(b));
	}
	
	Bcd opMulAssign(T)(const T b) {
		this = this * b;
		return this;
	}

	unittest {
		write("multiply...");
		Bcd a, b, c;
		a = 105, b = -22;
		c = a * b;
		assert(c == -2310);
		c = 45;
		c *= 1205;
	//	writeln("c = ", c);
		assert(c == 54225);
		writeln("passed");
	}

	const Bcd opDiv(T:Bcd)(const T b) {
		Bcd rem;
		return divide(this, b, rem);
	}
	
	unittest {
		write("opDiv...");
		Bcd a, b;
		a = 7;
		b = 3;
		assert(a/b == 2);
		writeln("passed");
	}
	
	const Bcd opDiv(T)(const T b) {
		Bcd rem;
		return divide(this, Bcd(b), rem);
	}
	
	Bcd opDivAssign(T)(const T b) {
		this = this / b;
		return this;
	}

	const Bcd opMod(T:Bcd)(const T b) {
		Bcd rem;
		divide(this, b, rem);
		return rem;
	}
	
	unittest {
		write("opMod...");
		Bcd a, b;
		a = 7;
		b = 3;
		assert(a % b == 1);
		writeln("passed");
	}
	
	const Bcd opMod(T)(const T b) {
		Bcd rem;
		divide(this, Bcd(b), rem);
		return rem;
	}
	
	Bcd opModAssign(T)(const T b) {
		this = this % b;
		return this;
	}

	const Bcd opAnd(const Bcd a) {
		return and(this, a);
	}
	
	Bcd opAndAssign(const Bcd a) {
		this = this & a;
		return this;
	}

	const Bcd opOr(const Bcd a) {
		return or(this, a);
	}
	
	Bcd opOrAssign(const Bcd a) {
		this = this | a;
		return this;
	}

	const Bcd opXor(const Bcd a) {
		return xor(this, a);
	}
	
	Bcd opXorAssign(const Bcd a) {
		this = this ^ a;
		return this;
	}

//--------------------------------
// comparison, equality operators
//-------------------------------- 
	
	const int opCmp(T:Bcd)(const T that) {
		return compare(this, that);
	}
	
	unittest {
		write("compare...");
		Bcd a,b;
		a = 100;
		b = 5;
		assert(a > b);
		a = -100;
		b = 5;
		assert(a < b);
		a = -100;
		b = -5;
		assert(a < b);
		a = 100;
		b = -5;
		assert(a > b);
		a = 5;
		b = 100;
		assert(a < b);
		assert(b > a);
		writeln("passed");
	}
	
	const int opCmp(T)(const T that) {
		return opCmp(Bcd(that));
	}
	
	const bool opEquals(T:Bcd)(const T that) {
		Bcd a = canonical(this);
		Bcd b = canonical(that);
		// TODO: this is wrong -- signs can differ -0 and + 0
		if (this.sign != that.sign) return false;
		if (a.digits.length != b.digits.length) return false;
		foreach_reverse(int i, Digit digit; a.digits) {
			if (digit != b.digits[i]) return false;
		}
		return true;
	}
	
	const bool opEquals(T)(const T that) {
		return opEquals(Bcd(that));
	}

	unittest {
	write("equals...");	
	assert(Bcd(0) == Bcd(0));
	assert(Bcd(4) == Bcd(4));
	assert(Bcd(40) == Bcd(40));
	assert(Bcd(-400) == Bcd(-400));
	assert(Bcd(12345678) == Bcd(+12345678));
	assert(Bcd(40) != Bcd(53));
	assert(Bcd(402) != Bcd(531));
	assert(Bcd(402) != Bcd(-402));
    assert(Bcd(65432) != Bcd(65431));
	assert(Bcd(2) != Bcd(1));
	assert(Bcd(1) != Bcd(2));
	writeln("passed");
	}
	
} // end struct Bcd


public bool isCanonical(const Bcd a) {
	// no leading zeros
	if (a.hasLeadingZeros) return false;
	// not -0
/+	if (a.numDigits == 1 && a.firstDigit == 0) return !a.sign;+/
	return true;
}

// Strips leading zeros and changes sign if == -0
public Bcd canonical(const Bcd a) {
	Bcd d = a.dup;
	if (isCanonical(a)) return d;
	stripl(d);
/+	if (d.numDigits == 1 && d.firstDigit == 0) {
		d.sign = false;
	}+/
	return d;
}


private void clipFirst(ref Bcd a, uint n = 1) {
	if (n == 0) return;
	if (n >= a.digits.length) a = ZERO;
	else a.digits = a.digits[0..$-n];
}

private void clipLast(ref Bcd a, uint n = 1) {
	if (n == 0) return;
	if (n >= a.digits.length) a = ZERO;
	else a.digits = a.digits[n..$];
}

unittest {
	write("clipping....");
	Bcd a;
	a = 12345;
	clipFirst(a);
	assert(a == 2345);
	clipLast(a);
	assert(a == 234);
	a = 1234567890;
	clipFirst(a, 3);
	assert(a == 4567890);
	clipLast(a, 5);
	assert(a == 45);
	clipLast(a, 5);
	assert(a == 0);
	writeln("passed");
}


/**
 * Strips leading zeros from the specified decint.
 */
private void stripl(ref Bcd a) {
	if (a.hasLeadingZeros) {
		foreach_reverse(int i, Digit digit; a.digits) {
			if (i == 0 || digit != 0) {
				a.digits.length = i+1;
				break;
			}
		}
	} 
}

unittest {
	write("stripl......");
	Bcd b = Bcd("+00023");
	assert(b.toString == "00023");
	stripl(b);
	assert(b.toString == "23");
	b = "-00050432";
	stripl(b);
	assert(b.toString == "-50432");
	b = "-000";
	stripl(b);
	assert(b.toString == "-0");
	writeln("passed");
}

/**
 * Strips trailing zeros from the specified decint.
 */
private void stripr(ref Bcd a) {
	int len = a.digits.length;
	foreach(int i, Digit digit; a.digits) {
		if (i == len-1 || digit != 0) {
			a.digits = a.digits[i..$];
			break;
		}
	}
}

unittest {
	write("stripl......");
	Bcd b;
	b = 23;
	stripr(b);
	assert(b == 23);
	b = "-5000";
	stripr(b);
	assert(b.toString == "-5");
	b = "-000";
	stripr(b);
	assert(b.toString == "-0");
	writeln("passed");
}

//public string format(const Bcd bcd, bool showPlus = false, bool showLeadingZeros = false) {
public string format(const Bcd bcd) {
	int len = bcd.digits.length;
	if (bcd.isSigned) len++;
//	if (bcd.isSigned || bcd.hasLeadingZeros) len++;
	char[] str = new char[len];
	
	int index = 0;
	if (bcd.sign) {
		str[index] = '-';
		index++;
	}
/+	if (bcd.hasLeadingZeros) {
		str[index] = '+';
		index++;
	}+/
	foreach_reverse(Digit digit; bcd.digits) {
		str[index] = cast(char) digit + '0';
		index++;
	}
	return str.idup;
}

public Bcd parse(string str) {
	Bcd bcd;
	// are leading zeros retained?
	bool lz = false;

	// strip whitespace, convert to char array
	char[] str1 = str.strip.dup;
	
	// check for leading '-'
	if (str1[0] == '-') {
		bcd.sign = true;
		str1 = str1[1..$];
		lz = true;
	}
	
	// check for leading '+'
	if (str1[0] == '+') {
		bcd.sign = false;
		str1 = str1[1..$];
		lz = true;
	}
	
	// verify chars are digits, strip out underscores
	int index = 0;
	char[] str2 = new char[str1.length];
	foreach_reverse(char ch; str1) {
		if (isDigit(ch)) {
			str2[index] = ch;
			index++;
			continue;
	    }
		if (ch == '_') {
			continue;
		}
		throw (new ConvError("Invalid character: " ~ ch));
	}
	str2.length = index;
	
	bcd.digits.length = index;
	foreach(int i, char ch; str2) {
		bcd.digits[i] = cast(Digit)(ch - '0');
	}

	if (!lz) return canonical(bcd);	
	return bcd;
}

private bool isDigit(const char ch) {
	return (ch >= '0' && ch <= '9');
}

public Bcd negate(const Bcd a) {
	Bcd b = a.dup;
	b.sign = !a.sign;
	return b;
}

public Bcd abs(const Bcd a) {
	return a.isSigned ? -a: +a;
}

public int compare(const Bcd m, const Bcd n) {
	Bcd a = canonical(m);
	Bcd b = canonical(n);
	if (!a.isSigned && b.isSigned) return 1;
	if (a.isSigned && !b.isSigned) return -1;
	if (!a.isSigned) {
		if (a.digits.length > b.digits.length) return 1;
		if (a.digits.length < b.digits.length) return -1;
		foreach_reverse(int i, Digit digit; a.digits) {
			if (digit > b.digits[i]) return 1;
			if (digit < b.digits[i]) return -1;
		}
	}
	else {
		if (a.digits.length > b.digits.length) return -1;
		if (a.digits.length < b.digits.length) return 11;
		foreach_reverse(int i, Digit digit; a.digits) {
			if (digit > b.digits[i]) return -1;
			if (digit < b.digits[i]) return 1;
		}
	}
	return 0;
}
	
unittest {
	write("strip...");
	Bcd bcd;
	bcd = "+00123";
	assert(bcd.toString == "00123");
	bcd = canonical(bcd);
//	writeln("bcd = ", bcd);
	assert(bcd.toString == "123");
	bcd = "+000";
//	writeln("bcd = ", bcd);
	assert(bcd.toString == "000");
	bcd = canonical(bcd);
//	writeln("bcd = ", bcd);
	writeln("passed");
}
	
private bool sameLength(const Bcd a, const Bcd b) {
	return a.numDigits == b.numDigits;
}

private int setSameLength(ref Bcd a, ref Bcd b) {
	if (sameLength(a, b)) return a.numDigits;
	uint alen = a.numDigits;
	uint blen = b.numDigits;
	if (alen > blen) {
		b.setNumDigits(alen);
	}
	else {
		a.setNumDigits(blen);
	}
	return a.numDigits();
}

// TODO: really? private?
private Bcd twosComp(const Bcd a) {
	Bcd b = Bcd(0, a.numDigits);
	foreach(int i, Digit digit; a.digits) {
		b.digits[i] = digit == 0 ? 1 : 0 ;
	}
	return b;
}

unittest {
	write("com...");
	Bcd bcd;
	bcd = 123;
	assert(twosComp(bcd).toString == "000");
	bcd = 40509;
	assert(twosComp(bcd).toString == "01010");
//	writeln("bcd = ", bcd);
//	writeln("~bcd = ", twosComp(bcd));
	writeln("passed");
}
	
public int sgn(const Bcd bcd) {
	if (bcd.isZero) return 0;
	return bcd.isSigned ? -1 : 1;
}

public Bcd not(const Bcd a) {
	Bcd b = a.dup;
	foreach(Digit digit; b.digits) {
		digit = not(digit);
	}
	return b;
}

private Digit not(const Digit a) {
	return a != 0;
}

public Bcd and(const Bcd x, const Bcd y) {
	Bcd a = x.dup;
	Bcd b = y.dup;
	int len = setSameLength(a,b);
	Bcd result = Bcd(0, len);
	for (int i = 0; i < len; i++) {
		result[i] = and(a[i], b[i]);
	}
	return result;
}

private Digit and(const Digit a, const Digit b) {
	return a != 0 && b != 0;
}

unittest {
	write("and...");
	Bcd a;
	Bcd b;
	a = 123000;
	b = 123000;
	assert(and(a,b).toString == "111000");
	b = 12300;
	assert(and(a,b).toString == "011000");
	a = 1234567;
	b = 7654321;
	assert(and(a,b).toString == "1111111");
	a = 1010;
	b = 101;
//	writeln("a = ", a);
//	writeln("b = ", b);
//	writeln("and = ", and(a,b));
	assert(and(a,b).isZero);
	writeln("passed");
}

// TODO: looks like there's some room for templates or mixins here.
public Bcd or(const Bcd x, const Bcd y) {
	Bcd a = x.dup;
	Bcd b = y.dup;
	int len = setSameLength(a,b);
	Bcd result = Bcd(0, len);
	for (int i = 0; i < len; i++) {
		result[i] = or(a[i], b[i]);
	}
	return result;
}

private Digit or(const Digit a, const Digit b) {
	return a != 0 || b != 0;
}

public Bcd xor(const Bcd x, const Bcd y) {
	Bcd a = x.dup;
	Bcd b = y.dup;
	int len = setSameLength(a,b);
	Bcd result = Bcd(0, len);
	for (int i = 0; i < len; i++) {
		result[i] = xor(a[i], b[i]);
	}
	return result;
}

private Digit xor(const Digit a, const Digit b) {
	return (a == 0 && b != 0) || (a != 0 && b == 0);
}

// TODO: watch the leading zeros
public Bcd add(const Bcd x, const Bcd y) {
	Bcd a = x.dup;
	Bcd b = y.dup;
	Bcd sum;
	if (a.sign == b.sign) {
		sum = simpleAdd(a, b);
		stripl(sum);
		sum.sign = a.sign;
		return sum;
	}
	else { // signs differ
		bool sign;
		switch (compare(abs(a), abs(b))) {
			case 0:
				return ZERO.dup;
			case 1:
				sign = a.isSigned;
				break;
			case -1:
				sign = b.isSigned;
				break;
		}
		setSameLength(a, b);
		sum = simpleAdd(a, tensComp(b));
		if (sum.firstDigit == 1) {
			sum.digits = sum.digits[0..$-1];
		}
		else {
			sum = tensComp(sum);
		}
		stripl(sum);
		sum.sign = sign;
	}
	return sum;
}

unittest {
	write("add....");
	Bcd a, b;
	a = 1234;
	b = 4321;
	assert(a + b == 5555);
	a = 2000;
	b = 1;
	assert(a + b == 2001);
	a = -2000;
	b = -1;
	assert(a + b == -2001);
	a = 2000;
	b = -1;
	assert(a + b == 1999);
	a = -123;
	b = 1;
	assert(a + b == -122);
	a = 123;
	b = -1;
	assert(a + b == 122);
	a = -1;
	b = 123;
//	writeln();
//	writeln("a + b = ", a + b);
	assert(a + b == 122);
	a = -123;
	b = 1;
	assert(a + b == -122);
	a = 1;
	b = -123;
	assert(a + b == -122);
	writeln("passed");
}

Bcd subtract(const Bcd a, const Bcd b) {
	return add(a, negate(b));
}

/**
 * Adds two BCD integers without regard to sign
**/
private Bcd simpleAdd(const Bcd a, const Bcd b) {
	Bcd x = a.dup;
	Bcd y = b.dup;
	int len = setSameLength(x, y);
	Bcd sum = Bcd(0, len+1);
	Digit carry = 0;
	uint i;
	// TODO: this is the place to stop adding zeros and
	// just copy the rest of the digits.
	for (i = 0; i < len; i++) {
		sum[i] = add(x[i], y[i], carry);
	}
	if (carry) {
		sum[i] = 1;
	}
	else {
		stripl(sum);
	}
	return sum;
}

// TODO: need a clipFirst, clipLast method

/**
 * Adds two digits and a carry digit.
 * Returns the (single-digit) sum and sets or resets the carry digit.
**/
private Digit add(const Digit a, const Digit b, ref Digit carry) {
	Digit sum = a + b + carry;
	carry = sum > 9;
	if (carry) sum -= 10;
	return sum;
}

unittest {
	write("simpleAdd...");
	Bcd a, b;
	a = 123;
	b = 222;
	Bcd sum = simpleAdd(a,b);
	assert(sum == 345);
	a = 2;
	b = 102000;
	sum = simpleAdd(a,b);
	assert(sum == 102002);
	writeln("passed");
}

private Bcd tensComp(const Bcd a) {
/+	foreach(Digit digit; a.digits) {
		digit = 9 - digit;
	}
	a = simpleAdd(a, ONE);
	return a;+/

	Bcd x = Bcd(0, a.numDigits);
	foreach (int i, digit; a.digits) {
		x[i] = 9 - digit;
	}
	return simpleAdd(x, ONE);
}

unittest {
	write("tensComp...");
	Bcd a, b, c;
	a = 123456;
	b = tensComp(a);
//	writeln("a = ", a);
//	writeln("b = ", b);
	c = 876544;
	assert(b == c);
	a = Bcd(0, 4);
	b = tensComp(a);
	c = 10000;
	assert(b == c);
	a = Bcd(1, 4);
	b = tensComp(a);
	c = 9999;
	assert(b == c);
	a = 9999;
	b = tensComp(a);
	c = 1;
	assert(b == c);
	a = 10000;
	b = tensComp(a);
	c = 90000;
	assert(b == c);
	a = 1;
	b = tensComp(a);
	c = 9;
//	writeln("a = ", a);
//	writeln("b = ", b);
	assert(b == c);
	writeln("passed");
}

// TODO: there are lots of ways to speed this up.
public Bcd multiply(const Bcd a, const Bcd b) {
	Bcd n, m;
	Bcd p = Bcd(0, a.numDigits + b.numDigits);
	if (a.numDigits > b.numDigits) {
		n = canonical(a);
		m = canonical(b);	
	}
	else {
		n = canonical(b);
		m = canonical(a);
	}
	foreach(uint i, Digit d; m.digits) {
		if (d == 0) continue;
//        writeln("mul(n, m[i]) = ", mul(n, m[i]));
//		writeln("pow10(mul(n, m[i]), i) = ", pow10(mul(n, m[i]), i));
		p = simpleAdd(p, pow10(mul(n, m[i]), i)); 
	}
	p.sign = a.sign ^ b.sign;
	return p;	
}

unittest {
	write("mul...");
	Bcd a, b, p;
	a = 2105, b = 301;
	p = multiply(a, b);
	assert(p == Bcd(633605));
	b = 800, a = 23958233;
	p = multiply(a, b);
	assert(p == Bcd("19166586400"));
	b = 5830, a = 23958233;
	p = multiply(a, b);
	assert(p == Bcd("139676498390"));
	writeln("passed");
}

private Bcd mul(const Bcd a, Digit m) {
	Bcd p = Bcd(0, a.numDigits+1);
	Digit c = 0;
	int i = 0;
	foreach (Digit d; a.digits) {
		p[i] = mul(m, d, c);
		i++;
	}
	if (c) p[i] = c;
	return p;
}

unittest {
	write("mul...");
	Bcd a, p;
	Digit m;
	a = 2105, m = 3;
	p = mul(a, m);
	assert(p == Bcd(6315));
	writeln("passed");
}

private Digit mul(Digit a, Digit b, ref Digit c) {
	Digit p = a * b + c;
	c = p / 10;
	return p % 10;
}

unittest {
	write("mul...");
	Digit a, b, c, d;
	a = 2, b = 3, c = 0;
	d = mul(a,b,c);
	assert(d == 6);
	assert(c == 0);
	a = 9, b = 8, c = 0;
	d = mul(a,b,c);
	assert(d == 2);
	assert(c == 7);
	writeln("passed");
}

public Bcd divide(const Bcd a, const Bcd b, out Bcd r) {

	if (b == ZERO) throw new Exception("Divide by zero");
	if (a == ZERO) return ZERO.dup;
	
	Bcd d = canonical(abs(b));
	r = canonical(abs(a));
	Bcd q;
	Bcd p = d;
	Bcd m;
	
	// shift the divisor
	do {
		m = p;
		p <<= 1;
	} while (p <= r && p > m);
	
	while (m >= d) {
		q <<= 1;
		// subtract repeatedly
		while (m <= r) {
			r -= m;
			q++;
		}
		m >>= 1;
	}
	
	// adjust the sign
	r.sign = a.sign;
	q.sign = a.sign != b.sign;
	return q;
}

unittest {
	write("divide...");
	Bcd a, b, q, r;
	a = 144;
	b = 12;
	q = divide(a, b, r);
	assert(q == 12);
	assert(r == 0);
	a = 144;
	b = 14;
	q = divide(a, b, r);
	assert(q == 10);
	assert(r == 4);
	a = 142351;
	b = 12;
	q = divide(a, b, r);
//	writeln("q = ", q);
//	writeln("r = ", r);
	assert(q == 11862);
	assert(r == 7);
	a = 2;
	b = 12;
	q = divide(a, b, r);
	assert(q == 0);
	assert(r == 2);
	a = 7;
	b = 3;
	q = divide(a, b, r);
	assert(q == 2);
	assert(r == 1);
	a = 7;
	b = -3;
	q = divide(a, b, r);
	assert(q == -2);
	assert(r == 1);
	a = -7;
	b = 3;
	q = divide(a, b, r);
	assert(q == -2);
	assert(r == -1);
	a = -7;
	b = -3;
	q = divide(a, b, r);
	assert(q == 2);
	assert(r == -1);
	writeln("passed");
}


public Bcd truncate(const Bcd a, int n) {
	return truncate(a, n, Bcd());
}

unittest {
	write("truncate....");
	Bcd a;
	a = 1234567;
	assert(truncate(a,3) == 123);
	a = 10256;
	assert(truncate(a,5) == 10256);
	a = 8500;
	assert(truncate(a,1) == 8);
	a = -8500;
	assert(truncate(a,1) == -8);
	a = -8500;
	assert(truncate(a,-1) == 0);
	writeln("passed");
}

/** 
 * Truncate to the specified number of digits
 */
public Bcd truncate(const Bcd a, int n, out Bcd r) {
	if (n <= 0) {
		r = canonical(a);
		return ZERO.dup;
	}
	if (n >= a.numDigits) {
		r = ZERO.dup;
		return canonical(a);
	}
	Bcd b;
	b.digits = a.digits[$-n..$].dup;
	b.sign = a.sign;
	r.digits = a.digits[0..$-n].dup;
	return b;
}

unittest {
	write("truncRem...");
	Bcd a;
	Bcd r;
	a = 1234567;
	assert(truncate(a, 3, r) == 123);
	assert(r == 4567);
	a = 10256;
	assert(truncate(a,5,r) == 10256);
	assert(r == 0);
	a = 8500;
	assert(truncate(a,1,r) == 8);
	assert(r == 500);
	a = -8500;
	assert(truncate(a,1,r) == -8);
	assert(r == 500);
	a = -8500;
//	writeln("truncate(a, 6, r) = ", truncate(a, 6, r));
//	writeln("r = ", r);
	assert(truncate(a,6,r) == -8500);
	assert(r == 0);
	writeln("passed");
}

public Bcd pad(Bcd a, int n) {
	if (n <= a.numDigits) return a.dup;
	return Bcd(a,n);
}

unittest {
	write("pad.........");
	Bcd a;
	a = 1234567;
	assert(pad(a,3) == 1234567);
	a = 10256;
//	writeln("pad(a,9) = ", pad(a,9));
	assert(pad(a,9).toString == "000010256");
	a = 8500;
	assert(pad(a,6).toString == "008500");
	a = -8500;
	assert(pad(a,6).toString == "-008500");
	writeln("passed");
}

public Bcd pow10(const Bcd a, uint n) {
	Bcd b = canonical(a);
	if (n == 0 || b == 0) return b;
	Digit[] zeros = new Digit[n];
	b.digits = zeros ~ b.digits;
	return b;
}

public Bcd pow10(uint n) {
	return pow10(ONE, n);
}

unittest {
	write("pow10...");
	Bcd a, b;
	a = 21345;
	a = pow10(a, 12);
	assert(a == Bcd("21345000000000000"));
	a = pow10(a, 0);
	assert(a == "21345000000000000"); 
	a = pow10(9);
	assert(a == Bcd("1000000000"));
	writeln("passed");
}

public Bcd power(const Bcd a, uint n) {
	Bcd b = canonical(a);
	Bcd p = ONE.dup;
	while (n > 0) {
		if (n & 1) {
			p *= b;
			if (n == 1) return p;
		}
		b *= b;
		n /= 2;
	}
	return p;
}

unittest {
	write("power.......");
	Bcd a;
	a = 2;
	int n = 3;
	assert(power(a,n) == 8);
	writeln("passed");
}


public Bcd shift(const Bcd a, int n) {
	if (n == 0) return canonical(a);
	if (n > 0) {	// shift left
		return pow10(a, n);
	}
	else {			// shift right
		if (-n >= a.numDigits) return ZERO.dup;
		return truncate(a, a.numDigits + n);
	}
}

unittest {
	write("shift.......");
	Bcd a, b;
	a = 1234;
	b = shift(a, 1);
	assert(b.toString == "12340");
	b = shift(a, 2);
	assert(b.toString == "123400");
	b = shift(a, -1);
//	writeln("b = ", b);
	assert(b.toString == "123");
	b = shift(a, 0);
	assert(b.toString == "1234");
	b = shift(a, -12);
/+	writeln("b = ", b);+/
	assert(b.toString == "0");
	b = shift(a, -4);
	assert(b.toString == "0");
	writeln("passed");
}

public Bcd shiftFixed(const Bcd a, int n) {
	if (n == 0) return a.dup;
	Bcd b = Bcd(0, a.numDigits);
	if (std.math.abs(n) >= a.numDigits) return b; 
	if (n > 0) {	// shiftFixed left
		b.digits[0..$-n] = a.digits[n..$];
	}
	else {			// shiftFixed right
		n = -n;
		b.digits[n..$] = a.digits[0..$-n];
	}
	return b;
}

unittest {
	write("shiftFixed...");
	Bcd a, b;
	a = 1234;
	b = shiftFixed(a, 1);
	assert(b.toString == "0123");
	b = shiftFixed(a, 2);
	assert(b.toString == "0012");
	b = shiftFixed(a, -1);
	assert(b.toString == "2340");
	b = shiftFixed(a, 0);
	assert(b.toString == "1234");
	b = shiftFixed(a, 12);
	assert(b.toString == "0000");
	b = shiftFixed(a, -4);
	assert(b.toString == "0000");
	writeln("passed");
}

public Bcd rotate(const Bcd a, int n) {
	if (n == 0) return a.dup;
	Bcd b = Bcd(0, a.numDigits);
	if (std.math.abs(n) >= a.numDigits) {
		bool sign = n < 0;
		n = std.math.abs(n) % a.numDigits;
		if (sign) n = -n;
	}
	if (n > 0) {	// rotate left
		b.digits[0..$-n] = a.digits[n..$];
		b.digits[$-n..$] = a.digits[0..n];
	}
	else {			// rotate right
		n = -n;
		b.digits[n..$] = a.digits[0..$-n];
		b.digits[0..n] = a.digits[$-n..$];
	}
	return b;
}

unittest {
	write("rotate...");
	Bcd a, b;
	a = 1234;
	b = rotate(a, 1);
	assert(b.toString == "4123");
	b = rotate(a, 2);
	assert(b.toString == "3412");
	b = rotate(a, -1);
	assert(b.toString == "2341");
	b = rotate(a, 0);
	assert(b.toString == "1234");
	b = rotate(a, 12);
	assert(b.toString == "1234");
	b = rotate(a, -4);
	assert(b.toString == "1234");
	writeln("passed");
}

/**
 * Rounds the specified integer to the specified number of digits.
 * The rounding mode governs the method of rounding.
 */
public Bcd round(const Bcd a, int n, Rounding mode) {
	Bcd r;
	Bcd b = truncate(a, n, r);
	return round(b, r, mode);
//	return b;
}

/**
 * Rounds the (truncated) integer based on its remainder and the rounding
 * mode.
 */
public Bcd round(const Bcd a, const Bcd r, const Rounding mode) {
	Bcd b = canonical(a);
	ubyte rfd = r.firstDigit;
	switch (mode) {
		case Rounding.DOWN:
			return b;

		case Rounding.HALF_UP:
			if (rfd >= 5) b++;
			return b;

		case Rounding.HALF_EVEN:
			if (rfd < 5) return b;
			if (rfd > 5) return ++b;
            Bcd p = r.dup;
			stripr(p);
			if (p.numDigits > 1) return ++b;
			// to reach this point the remainder must be exactly 5
			// if odd, increment
			if (b.lastDigit & 1 != 0) b++;
			return b;
			
		case Rounding.CEILING:
			if (!b.isSigned && !r.isZero) b++;
			return b;
			
		case Rounding.FLOOR:
			if (b.isSigned && !r.isZero) b++;
			return b;
			
		case Rounding.HALF_DOWN:
			if (rfd < 5) return b;
			if (rfd > 5) return ++b;
            Bcd p = r.dup;
			stripr(p);
			if (p.numDigits > 1) return ++b;
			// to reach this point the remainder must be exactly 5
			return b;
			
		case Rounding.UP:
			if (!r.isZero) b++;
			return b;
	}
	return b;
}

unittest {
	write("rounding....");
	Bcd a, b;
	a = 12345;
	b = round(a, 4, Rounding.DOWN);
	assert(b == 1234);
	b = round(a, 4, Rounding.HALF_UP);
	assert(b == 1235);
	b = round(a, 4, Rounding.CEILING);
	assert(b == 1235);
	b = round(a, 4, Rounding.HALF_EVEN);
	assert(b == 1234);
	b = round(a, 4, Rounding.FLOOR);
	assert(b == 1234);
	b = round(a, 4, Rounding.HALF_DOWN);
	assert(b == 1234);
	b = round(a, 4, Rounding.UP);
	assert(b == 1235);
	writeln("passed");
}


//==========================================

public void main() {
	writeln();
	writeln("If you got this far all the unit tests were successful.");
	writeln();
	writeln("      Congratulations!");
	Bcd bcd;
	writeln("bcd = ", format(bcd));
	bcd = parse("12");
	writeln("bcd = ", format(bcd));
	bcd = parse("012");
	writeln("bcd = ", format(bcd));
	bcd = parse("-012");
	writeln("bcd = ", format(bcd));
	bcd = parse("+012");
	writeln("bcd = ", format(bcd));
	bcd = parse("-0");
	writeln("bcd = ", format(bcd));
	bcd = parse("012_345_678");
	writeln("bcd = ", format(bcd));

/+	
	writeln("OK!");+/
}