/*
 * Copyright 2013 Yuichiro Moriguchi
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.morilib.dc;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;

/**
 * 
 *
 *
 * @author MORIGUCHI, Yuichiro 2013/07/14
 */
public final class DcMath {

	//
	private static final int BASE = 16;
	private static final int LOG2BASE = 4;
	private static final BigInteger LIMIT_NRT =
		BigInteger.valueOf(Integer.MAX_VALUE);
//	private static final BigInteger CENTUM = BigInteger.valueOf(100);

	//
	private DcMath() {}

	/**
	 * 
	 * @param n
	 * @return
	 */
	public static final int minus1ToThe(int n) {
		return ((n & 1) == 0) ? 1 : -1;
	}

	/**
	 * 
	 * @param alpha
	 * @return
	 */
	public static double decimalPart(double x) {
		double r = Math.IEEEremainder(x, 1.0);

		return (r < 0) ? 1 + r : r;
	}

	/**
	 * 
	 * @param x
	 * @return
	 */
	public static boolean isInteger(double x) {
		return decimalPart(x) == 0.0;
	}

	private static int toInt(byte b) {
		return (b < 0) ? (b & 0x7f) + 128 : b;
	}

	private static int searchX(BigInteger v, BigInteger t) {
		BigInteger s;
		int x = 0;

		do {
			s = v.shiftLeft(LOG2BASE).add(BigInteger.valueOf(x));
		} while(s.multiply(BigInteger.valueOf(x++)).compareTo(t) <= 0);
		return x - 2;
	}

//	private static int searchX(BigInteger v, BigInteger t, int base) {
//		BigInteger s, b = BigInteger.valueOf(base);
//		int x = 0;
//
//		do {
//			s = v.multiply(b).add(BigInteger.valueOf(x));
//		} while(s.multiply(BigInteger.valueOf(x++)).compareTo(t) <= 0);
//		return x - 2;
//	}

	//
	static BigInteger[] _sqrt(BigInteger q) {
		BigInteger s = BigInteger.ZERO;
		BigInteger t = BigInteger.ZERO;
		BigInteger r = BigInteger.ZERO;
		int i = 0;
		byte[] a;

		if(q.signum() == 0) {
			return new BigInteger[] {
					BigInteger.ZERO, BigInteger.ZERO
			};
		} else if(q.signum() < 0) {
			throw new IllegalArgumentException();
		}

		a = q.toByteArray();
		for(; i < a.length; i++) {
			int x = 0;

			if(s.signum() == 0) {
				t = BigInteger.valueOf(toInt(a[i]));
				for(; x * x <= t.intValue(); x++);
				x--;
				s = BigInteger.valueOf(x);
			} else {
				t = t.shiftLeft(LOG2BASE * 2);
				t = t.add(BigInteger.valueOf(toInt(a[i])));
				x = searchX(s, t);
				s = s.shiftLeft(LOG2BASE).add(BigInteger.valueOf(x));
			}
			t = t.subtract(s.multiply(BigInteger.valueOf(x)));
			s = s.add(BigInteger.valueOf(x));
			r = r.shiftLeft(LOG2BASE).add(BigInteger.valueOf(x));
		}
		return new BigInteger[] { r, t, s };
	}

	/**
	 * 
	 * @param q
	 * @return
	 */
	public static BigInteger sqrt(BigInteger q) {
		BigInteger[] r2;

		r2 = _sqrt(q);
		return (r2[1].signum() == 0) ? r2[0] : r2[0].negate();
	}

	/**
	 * 
	 * @param d
	 * @return
	 */
	public static BigDecimal sqrt(BigDecimal d) {
		BigDecimal f, x;
		BigInteger[] q;
		BigInteger a;
		int s;

		f = d.setScale((s = d.scale()) * 2 + 2);
		a = f.unscaledValue();
		q = _sqrt(a);
		x = new BigDecimal(q[0], s + 1);
		x = x.setScale(d.scale(), RoundingMode.HALF_UP);
		return x;
	}

	//
	private static BigInteger[] split(BigInteger b, int n) {
		byte[] c = b.toByteArray();
		byte[] d;
		BigInteger[] r;
		BigInteger   x;
		int i, l = 0;

		for(; c[l] == 0; l++);
		d = new byte[(c.length - l) * 2];
		for(int k = l; k < c.length; k++) {
			d[(k - l) * 2]     = (byte)(toInt(c[k]) >> 4);
			d[(k - l) * 2 + 1] = (byte)(toInt(c[k]) & 0xf);
		}

		r = new BigInteger[(d.length + n - 1) / n];
		i = d.length % n;
		if(i > 0) {
			x = BigInteger.ZERO;
			for(int k = 0; k < i; k++) {
				x = x.shiftLeft(LOG2BASE).add(BigInteger.valueOf(
						toInt(d[k])));
			}
			r[0] = x;
		}

		for(; i < d.length; i += n) {
			x = BigInteger.ZERO;
			for(int k = 0; k < n; k++) {
				x = x.shiftLeft(LOG2BASE).add(BigInteger.valueOf(
						toInt(d[i + k])));
			}
			r[(i + n - 1) / n] = x;
		}
		return r;
	}

	/**
	 * 
	 * @param q
	 * @param n
	 * @return
	 */
	public static BigInteger nrtExact(BigInteger q, int n) {
		BigInteger[] a;
		BigInteger   r = BigInteger.ZERO;
		BigInteger   t = BigInteger.ZERO;
		int i = 0;

		if(q.signum() == 0) {
			return BigInteger.ZERO;
		} else if(q.signum() < 0) {
			throw new IllegalArgumentException();
		} else if(n < 0) {
			throw new IllegalArgumentException();
		}

		a = split(q, n);
		for(; i < a.length; i++) {
			BigInteger x;
			int b = 0;

			t = t.shiftLeft(LOG2BASE * n).add(a[i]);
			r = r.shiftLeft(LOG2BASE);
			for(; b < BASE; b++) {
				x = r.add(BigInteger.valueOf(b)).pow(n);
				if(x.compareTo(t) > 0) {
					break;
				}
			}
			r = r.add(BigInteger.valueOf(b - 1));
		}
		return (t.subtract(q).signum() == 0) ? r : r.negate();
	}

	/**
	 * 
	 * @param q
	 * @param n
	 * @return
	 */
	public static BigInteger nrtExact(BigInteger q, BigInteger n) {
		if(n.signum() < 0 || n.compareTo(LIMIT_NRT) > 0) {
			throw new IllegalArgumentException();
		}
		return nrtExact(q, n.intValue());
	}

}
