using System;
using sharp.extensions;

namespace BigInt
{
	public static class Euclid
	{

		public static Tripple<Integer> extended(Integer a, Integer b)
		{
			if (b.isZero()){
				if (a != Integer.ONE){
					throw new ArgumentException("Euclid found GCD>1!");
				}
				return new Tripple<Integer>(a, Integer.ONE, Integer.ZERO);
			}
			Tripple<Integer> r = extended(b, a % b);
			return new Tripple<Integer>(r.X,r.Z,r.Y - ((a / b) * r.Z) );
		}

		/**
		 * Implementation of inverse() like found at
         * https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (14 Oct 2017)
         **/
		public static Integer inverse(Integer a,Integer m){
			Integer one, zero;

			rt act, next, future;

			one = Integer.ONE;
			zero = Integer.ZERO;

			act = new rt(m, zero);
			next = new rt(a, one);

			while (!next.r.isZero())
			{
				Integer q = act.r / next.r;
				future = new rt(
								act.r - (q * next.r),
				                act.t - (q * next.t)
				               );

				//Console.WriteLine("EUCLID:          q = {0}",q);
				//Console.WriteLine("EUCLID:    act:  r = {0}  /  t = {1}",act.r,act.t);
				//Console.WriteLine("EUCLID:   next:  r = {0}  /  t = {1}",next.r,next.t);
				//Console.WriteLine("EUCLID: future:  r = {0}  /  t = {1}",future.r,future.t);

				act = next;
				next = future;
			}

			if (act.r > one){
				return null;
			}
			if (act.t < 0){
				act.t += m;
			}
			
			return act.t;
		}

		private struct rt {
			public Integer r, t;

			public rt(Integer r,Integer t){
				this.r = r;
				this.t = t;
			}
		}

	}
}