using System;
using System.Diagnostics;

namespace Gcd
{
    /// <summary>
    /// Provide methods with integers.
    /// </summary>
    public static class IntegerExtensions
    {
        /// <summary>
        /// Calculates GCD of two integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or two numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(int a, int b)
        {
            if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b), "Argument b out of range");
            }

            a = Math.Abs(a);
            b = Math.Abs(b);

            if (a == 0 && b == 0)
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            while (a != 0 && b != 0)
            {
                if (a > b)
                {
                    a = a % b;
                }
                else
                {
                    b = b % a;
                }
            }

            return a + b;
        }

        /// <summary>
        /// Calculates GCD of three integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="c">Third integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(int a, int b, int c)
        {
            if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b), "Argument b out of range");
            }

            if (c == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(c), "Argument c out of range");
            }

            if (a == 0 && b == 0 && c == 0)
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            a = Math.Abs(a);
            b = Math.Abs(b);
            c = Math.Abs(c);

            while (a != 0 && b != 0)
            {
                if (a > b)
                {
                    a = a % b;
                }
                else
                {
                    b = b % a;
                }
            }

            int n = a + b;

            while (n != 0 && c != 0)
            {
                if (n > c)
                {
                    n = n % c;
                }
                else
                {
                    c = c % n;
                }
            }

            return c + n;
        }

        /// <summary>
        /// Calculates the GCD of integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="other">Other integers.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(int a, int b, params int[] other)
        {
            if (a == int.MinValue || b == int.MinValue || IsMinValue(other))
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (a == 0 && b == 0 && AllZeros(other))
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            a = Math.Abs(a);
            b = Math.Abs(b);
            AbsArray(other);

            while (a != 0 && b != 0)
            {
                if (a > b)
                {
                    a = a % b;
                }
                else
                {
                    b = b % a;
                }
            }

            int gcd = a + b;

            for (int i = 0; i < other.Length; i++)
            {
                while (gcd != 0 && other[i] != 0)
                {
                    if (gcd > other[i])
                    {
                        gcd = gcd % other[i];
                    }
                    else
                    {
                        other[i] = other[i] % gcd;
                    }
                }

                gcd = gcd + other[i];
            }

            return gcd;
        }

        public static bool AllZeros(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] != 0)
                {
                    return false;
                }
            }

            return true;
        }

        public static bool IsMinValue(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] == int.MinValue)
                {
                    return true;
                }
            }

            return false;
        }

        public static void AbsArray(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            for (int i = 0; i < array.Length; i++)
            {
                array[i] = Math.Abs(array[i]);
            }
        }

        /// <summary>
        /// Calculates GCD of two integers [-int.MaxValue;int.MaxValue] by the Stein algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or two numbers are int.MinValue.</exception>
        public static int GetGcdByStein(int a, int b)
        {
            if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b), "Argument b out of range");
            }

            if (a == 0 && b == 0)
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            a = Math.Abs(a);
            b = Math.Abs(b);

            if (a == 0)
            {
                return b;
            }
            else if (b == 0)
            {
                return a;
            }
            else if (a == b)
            {
                return a;
            }
            else if (a % 2 == 0 && b % 2 == 0)
            {
                return 2 * GetGcdByStein(a / 2, b / 2);
            }
            else if (a % 2 == 0 && b % 2 != 0)
            {
                return GetGcdByStein(a / 2, b);
            }
            else if (a % 2 != 0 && b % 2 == 0)
            {
                return GetGcdByStein(a, b / 2);
            }
            else if (a > b)
            {
                return GetGcdByStein((a - b) / 2, b);
            }
            else
            {
                return GetGcdByStein((b - a) / 2, a);
            }
        }

        /// <summary>
        /// Calculates GCD of three integers [-int.MaxValue;int.MaxValue] by the Stein algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="c">Third integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByStein(int a, int b, int c)
        {
            if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b), "Argument b out of range");
            }

            if (c == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(c), "Argument c out of range");
            }

            if (a == 0 && b == 0 && c == 0)
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            a = Math.Abs(a);
            b = Math.Abs(b);
            c = Math.Abs(c);

            if (a == 0)
            {
                return GetGcdByStein(b, c);
            }
            else if (b == 0)
            {
                return GetGcdByStein(a, c);
            }
            else if (a == b)
            {
                return GetGcdByStein(a, c);
            }
            else if (a % 2 == 0 && b % 2 == 0)
            {
                return GetGcdByStein(2 * GetGcdByStein(a / 2, b / 2), c);
            }
            else if (a % 2 == 0 && b % 2 != 0)
            {
                return GetGcdByStein(GetGcdByStein(a / 2, b), c);
            }
            else if (a % 2 != 0 && b % 2 == 0)
            {
                return GetGcdByStein(GetGcdByStein(a, b / 2), c);
            }
            else if (a > b)
            {
                return GetGcdByStein(GetGcdByStein((a - b) / 2, b), c);
            }
            else
            {
                return GetGcdByStein(GetGcdByStein((b - a) / 2, a), c);
            }
        }

        /// <summary>
        /// Calculates the GCD of integers [-int.MaxValue;int.MaxValue] by the Stein algorithm.
        /// </summary>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="other">Other integers.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByStein(int a, int b, params int[] other)
        {
            if (a == int.MinValue || b == int.MinValue || IsMinValue(other))
            {
                throw new ArgumentOutOfRangeException(nameof(a), "Argument a out of range");
            }

            if (a == 0 && b == 0 && AllZeros(other))
            {
                throw new ArgumentException("Argument's can't be 0 at the same time", nameof(a));
            }

            a = Math.Abs(a);
            b = Math.Abs(b);
            AbsArray(other);

            int gcd = 1;

            if (!AllZeros(other))
            {
                gcd = other[0];
                for (int i = 0; i < other.Length - 1; i++)
                {
                    gcd = GetGcdByStein(gcd, other[i + 1]);
                }
            }

            if (a == 0)
            {
                return GetGcdByStein(b, gcd);
            }
            else if (b == 0)
            {
                return GetGcdByStein(a, gcd);
            }
            else if (a == b)
            {
                return GetGcdByStein(a, gcd);
            }
            else if (a % 2 == 0 && b % 2 == 0)
            {
                return GetGcdByStein(2 * GetGcdByStein(a / 2, b / 2), gcd);
            }
            else if (a % 2 == 0 && b % 2 != 0)
            {
                return GetGcdByStein(GetGcdByStein(a / 2, b), gcd);
            }
            else if (a % 2 != 0 && b % 2 == 0)
            {
                return GetGcdByStein(GetGcdByStein(a, b / 2), gcd);
            }
            else if (a > b)
            {
                return GetGcdByStein(GetGcdByStein((a - b) / 2, b), gcd);
            }
            else
            {
                return GetGcdByStein(GetGcdByStein((b - a) / 2, a), gcd);
            }
        }

        /// <summary>
        /// Calculates GCD of two integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or two numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(out long elapsedTicks, int a, int b)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByEuclidean(a, b);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }

        /// <summary>
        /// Calculates GCD of three integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="c">Third integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(out long elapsedTicks, int a, int b, int c)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByEuclidean(a, b, c);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }

        /// <summary>
        /// Calculates the GCD of integers from [-int.MaxValue;int.MaxValue] by the Euclidean algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in Ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="other">Other integers.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByEuclidean(out long elapsedTicks, int a, int b, params int[] other)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByEuclidean(a, b, other);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }

        /// <summary>
        /// Calculates GCD of two integers from [-int.MaxValue;int.MaxValue] by the Stein algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or two numbers are int.MinValue.</exception>
        public static int GetGcdByStein(out long elapsedTicks, int a, int b)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByStein(a, b);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }

        /// <summary>
        /// Calculates GCD of three integers from [-int.MaxValue;int.MaxValue] by the Stein algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="c">Third integer.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByStein(out long elapsedTicks, int a, int b, int c)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByStein(a, b, c);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }

        /// <summary>
        /// Calculates the GCD of integers from [-int.MaxValue;int.MaxValue] by the Stein algorithm with elapsed time.
        /// </summary>
        /// <param name="elapsedTicks">Method execution time in Ticks.</param>
        /// <param name="a">First integer.</param>
        /// <param name="b">Second integer.</param>
        /// <param name="other">Other integers.</param>
        /// <returns>The GCD value.</returns>
        /// <exception cref="ArgumentException">Thrown when all numbers are 0 at the same time.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when one or more numbers are int.MinValue.</exception>
        public static int GetGcdByStein(out long elapsedTicks, int a, int b, params int[] other)
        {
            var timer = new Stopwatch();
            timer.Start();
            int result = GetGcdByStein(a, b, other);
            timer.Stop();
            elapsedTicks = timer.ElapsedTicks;

            return result;
        }
    }
}