using System;
using System.Collections.Generic;

    public class Polynomial
    {
        #region Fields
        /// <summary>
        /// The Internal Array that Stores the Coefficients as they are Input.
        /// To Access Coefficients use Indexer.
        /// </summary>
        Complex[] Coefficients { get; set; }
        #endregion

        #region Constructors
        /// <summary>
        /// Creates a Polynomial from an Array of Coefficients.
        /// </summary>
        /// <param name="coefficients">The Coefficients in Decreasing Order of Degrees.</param>
        public Polynomial(params Complex[] coefficients)
        {
            if (coefficients == null || coefficients.Length < 1) throw new IndexOutOfRangeException();
            else Coefficients = coefficients;
            Clean();
            if (Degree < 0) throw new Exception("Degree must be atleast one.");
        }

        /// <summary>
        /// Computes the monomial x^degree.
        /// </summary>
        public static Polynomial Monomial(int degree)
        {
            if (degree < 0) throw new Exception("Degree must be atleast one.");

            List<Complex> coeffs = new List<Complex>(degree + 1);

            for (int i = 0; i < degree; i++) coeffs.Add(0);
            coeffs.Add(1);
            coeffs.Reverse();

            return new Polynomial(coeffs.ToArray());
        }
        #endregion

        #region Indexer
        /// <summary>
        /// Gets or Sets the Coefficient of a Term.
        /// </summary>
        /// <param name="index">The Degree of the Required Term.</param>
        /// <returns>The Coefficient of the specified Degree Term.</returns>
        public Complex this[int index]
        {
            get
            {
                if (index > Degree | index < 0) return 0;
                return Coefficients[Degree - index];
            }
            set
            {
                if (index > Degree | index < 0) throw new IndexOutOfRangeException();
                Complex[] temp = (Complex[])Coefficients.Clone();
                Coefficients[Degree - index] = value;
                Clean();
                if (Degree < 1)
                {
                    Coefficients = temp;
                    throw new ArgumentException("Degree cannot be less than 1.");
                }
            }
        }
        #endregion

        #region Properties
        /// <summary>
        /// Gets the Degree of the Polynomial.
        /// </summary>
        public int Degree { get { return Coefficients.Length - 1; } }
        #endregion

        #region Methods
        /// <summary>
        /// Removes leading Zero terms.
        /// </summary>
        void Clean()
        {
            int i;

            for (i = Degree; i >= 0 && this[i] == 0; --i) ;

            List<Complex> coeffs = new List<Complex>(i + 1);

            for (int k = 0; k <= i; ++k) coeffs.Add(this[k]);
            coeffs.Reverse();

            Coefficients = coeffs.ToArray();
        }

        /// <summary>
        /// Evaluates the value of the Polynomial at a Value.
        /// </summary>
        /// <param name="Z">The Complex Number to Evaluate the Polynomial at.</param>
        /// <returns>The Value of the Polynomial at the input Value.</returns>
        public Complex Evaluate(Complex Z)
        {
            Complex Result = this[Degree];

            for (int i = Degree - 1; i >= 0; --i) Result = this[i] + Z * Result;

            return Result;
        }
        #endregion

        /// <summary>
        /// Divides Dividend Polynomial by Divisor Polynomial
        /// </summary>
        /// <returns>Quotient Polynomial</returns>
        public static Polynomial Divide(Polynomial Dividend, Polynomial Divisor, out Polynomial Remainder)
        {
            if (Dividend.Degree < Divisor.Degree) throw new InvalidOperationException();

            List<Complex> Result = new List<Complex>();

            Remainder = (Polynomial)Dividend.MemberwiseClone();

            int Offset = Dividend.Degree - Divisor.Degree;

            for (int i = 0; i <= Offset; ++i)
            {
                Result.Add(Remainder.Coefficients[0] / Divisor.Coefficients[0]);

                Remainder -= Result[i] * (Divisor * Monomial(Offset - i));
            }

            return new Polynomial(Result.ToArray());
        }

        /// <summary>
        /// Normalizes the polynomial, i.e. divides each coefficient by the
        /// coefficient of the greatest term if it is != 1.
        /// </summary>
        public void Normalize()
        {
            this.Clean();
            if (this[Degree] != 1) for (int k = 0; k <= Degree; k++) this[k] /= this[Degree];
        }

        #region Parsing
        /// <summary>
        /// Parses a Real Polynomial from a String.
        /// </summary>
        /// <param name="s">The String representation of the Real Polynomial to Parse. Eg: 4x^3 + 3x^2 - 23x + 20</param>
        public static Polynomial Parse(string s)
        {
            Dictionary<int, double> Work = new Dictionary<int, double>();
            string temp = string.Empty;
            s = s.Trim();
            int degree = 0;

            try
            {
                foreach (char c in s)
                {
                    if (c == '+' || c == '-')
                    {
                        KeyValuePair<int, double> Pair = ParseTerm(temp);
                        Work.Add(Pair.Key, Pair.Value);
                        if (Pair.Key > degree) degree = Pair.Key;
                        temp = c.ToString();
                    }
                    else if (c == '=') break;
                    else temp += c;
                }

                KeyValuePair<int, double> PairX = ParseTerm(temp);
                Work.Add(PairX.Key, PairX.Value);
            }
            catch { throw new FormatException("Input string was not of the correct format."); }
            return new Polynomial(Work, degree);
        }

        Polynomial(Dictionary<int, double> a, int degree)
        {
            List<Complex> list = new List<Complex>(degree);
            for (int i = 0; i <= degree; ++i) list.Add(a.ContainsKey(i) ? a[i] : 0);
            list.Reverse();
            Coefficients = list.ToArray();
            Clean();
        }

        static KeyValuePair<int, double> ParseTerm(string s)
        {
            int Power;
            double Coefficient;

            if (s.Length > 0)
            {
                if (s.IndexOf("x^") > -1)
                {
                    string coeff = s.Substring(0, s.IndexOf("x^")).Replace("+", "").Replace(" ", "");
                    int IndexOfX = s.IndexOf("x^");
                    string pow = s.Substring(IndexOfX + 2, (s.Length - 1) - (IndexOfX + 1));
                    if (coeff == "-") Coefficient = -1;
                    else if (coeff == "+" | coeff == "") Coefficient = 1;
                    else Coefficient = Double.Parse(coeff);
                    Power = int.Parse(pow);
                }
                else if (s.IndexOf("x") > -1)
                {
                    string coeff = s.Substring(0, s.IndexOf("x")).Replace("+", "").Replace(" ", "");
                    if (coeff == "-") Coefficient = -1;
                    else if (coeff == "+" | coeff == "") Coefficient = 1;
                    else Coefficient = Double.Parse(coeff);
                    Power = 1;
                }
                else
                {
                    Power = 0;
                    Coefficient = Double.Parse(s.Replace("+", "").Replace(" ", ""));
                }
            }
            else Coefficient = Power = 0;

            return new KeyValuePair<int, double>(Power, Coefficient);
        }

        #endregion

        #region Calculus
        /// <summary>
        /// Differentiates given polynomial p.
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Polynomial Derivative
        {
            get
            {
                List<Complex> buf = new List<Complex>(Degree);

                for (int i = 0; i < Degree; i++) buf.Add((i + 1) * this[i + 1]);

                buf.Reverse();

                return new Polynomial(buf.ToArray());
            }
        }

        /// <summary>
        /// Integrates given polynomial p.
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Polynomial Integral
        {
            get
            {
                List<Complex> buf = new List<Complex>(Degree + 2);

                for (int i = 1; i < Degree + 2; i++) buf.Add(this[i - 1] / i);

                buf.Reverse();

                buf.Add(0);

                return new Polynomial(buf.ToArray());
            }
        }

        public Complex Differentiate(Complex Z) { return Derivative.Evaluate(Z); }

        public Complex Intergrate(Complex LowerLimit, Complex UpperLimit)
        {
            Polynomial Px = Integral;
            return Integral.Evaluate(UpperLimit) - Integral.Evaluate(LowerLimit);
        }
        #endregion

        #region Override
        public override bool Equals(object obj)
        {
            return (obj is Polynomial) ? this == (Polynomial)obj : false;
        }

        public static new bool Equals(object o1, object o2)
        {
            return (o1 is Polynomial && o2 is Polynomial) ? (Polynomial)o1 == (Polynomial)o2 : false;
        }
        #endregion

        #region Operator Overloading
        public static bool operator ==(Polynomial P1, Polynomial P2)
        {
            if (P1.Degree != P2.Degree) return false;

            for (int i = 0; i <= P1.Degree; ++i) if (P1[i] != P2[i]) return false;

            return true;
        }

        public static bool operator !=(Polynomial P1, Polynomial P2) { return !(P1 == P2); }

        /// <summary>
        /// Adds two Polynomial.
        /// </summary>
        /// <param name="P1">First Polynomial</param>
        /// <param name="P2">Second Polynomial</param>
        /// <returns>Resultant Polynomial</returns>
        public static Polynomial operator +(Polynomial P1, Polynomial P2)
        {
            int MaxDegree = Math.Max(P1.Degree, P2.Degree);
            List<Complex> Coeffs = new List<Complex>();

            for (int i = 0; i <= MaxDegree; ++i) Coeffs.Add(P1[i] + P2[i]);

            Coeffs.Reverse();

            return new Polynomial(Coeffs.ToArray());
        }

        public static Polynomial operator -(Polynomial P1, Polynomial P2)
        {
            return P1 + (-P2);
        }

        public static Polynomial operator -(Polynomial P)
        {
            List<Complex> Coeffs = new List<Complex>();

            for (int i = 0; i <= P.Degree; ++i) Coeffs.Add(-P[i]);

            Coeffs.Reverse();

            return new Polynomial(Coeffs.ToArray());
        }

        public static Polynomial operator *(Polynomial P, Complex Z)
        {
            List<Complex> Coeffs = new List<Complex>();

            for (int i = 0; i <= P.Degree; ++i) Coeffs.Add(Z * P[i]);

            Coeffs.Reverse();

            return new Polynomial(Coeffs.ToArray());
        }

        public static Polynomial operator *(Complex Z, Polynomial P) { return P * Z; }

        public static Polynomial operator *(Polynomial P1, Polynomial P2)
        {
            int MaxDegree = P1.Degree + P2.Degree;
            List<Complex> Coeffs = new List<Complex>(MaxDegree);

            for (int i = 0; i <= MaxDegree; ++i) Coeffs.Add(0);

            for (int i = 0; i <= P1.Degree; ++i) for (int j = 0; j <= P2.Degree; ++j) Coeffs[i + j] += P1[i] * P2[j];

            Coeffs.Reverse();

            return new Polynomial(Coeffs.ToArray());
        }

        public static Polynomial operator /(Polynomial P, Complex Z)
        {
            List<Complex> Coeffs = new List<Complex>();

            for (int i = 0; i <= P.Degree; ++i) Coeffs.Add(P[i] / Z);

            Coeffs.Reverse();

            return new Polynomial(Coeffs.ToArray());
        }

        public static Polynomial operator ^(Polynomial P, int I)
        {
            if (I < 1) throw new Exception("Exponent must be greater than Zero.");
            Polynomial Result = P;
            for (int i = 1; i < I; ++i) Result *= P;
            return Result;
        }
        #endregion

        #region Roots
        /// <summary>
        /// Gets the Sum of Roots of the Polynomial.
        /// </summary>
        public Complex SumOfRoots { get { return -Coefficients[1] / Coefficients[0]; } }

        /// <summary>
        /// Gets the Product of Roots of the Polynomial.
        /// </summary>
        public Complex ProductOfRoots { get { return Math.Pow(-1, Degree) * Coefficients[Degree] / Coefficients[0]; } }

        /// <summary>
        /// Gets the Roots (or Zeroes or Solutions) of the Polynomial.
        /// </summary>
        public ComplexPolynomialRootFinder Roots
        {
            get
            {
                if (Degree < 1) throw new Exception("A Zero Degree Polynomial cannot be solved.");
                return new ComplexPolynomialRootFinder(Coefficients);
            }
        }
        #endregion

        #region ToString
        /// <summary>
        /// Gets a String Representing the Polynomial.
        /// </summary>
        public override string ToString()
        {
            string Result = "p(x) = ";

            for (int i = Coefficients.Length; i > 1; --i)
            {
                Complex Val = Coefficients[Coefficients.Length - i];

                bool NotPurelyRealImag = !Val.IsReal && !Val.IsPurelyImaginary;
                bool IsNegative = Val.Imaginary < 0 && Val.Real < 0;

                bool ImagPossitive = Val.IsPurelyImaginary && Val.Imaginary > 0;
                bool ImagNegative = Val.IsPurelyImaginary && Val.Imaginary < 0;

                bool RealPossitive = Val.IsReal && Val.Real > 0;
                bool RealNegative = Val.IsReal && Val.Real < 0;

                if (Val == 0) continue;
                else
                {
                    if (i != Coefficients.Length && ((NotPurelyRealImag && !IsNegative) || ImagPossitive || RealPossitive)) Result += " + ";
                    else if (RealNegative || ImagNegative || IsNegative) Result += " - ";
                    if (NotPurelyRealImag) Result += "(";
                    if (Val != 1 && Val != -1 && Val != Complex.Iota && Val != -Complex.Iota)
                    {
                        if (IsNegative) Result += (-Val).ToString();
                        else if (Val.Imaginary == 0) Result += Math.Abs(Val.Real).ToString();
                        else if (Val.Real == 0) Result += Math.Abs(Val.Imaginary).ToString() + "i";
                        else Result += Val.ToString();
                    }
                    else if (Val == Complex.Iota || Val == -Complex.Iota) Result += "i";
                    if (NotPurelyRealImag) Result += ")";
                    Result += i - 1 == 1 ? "x" : "x" + Superscript(i - 1);
                }
            }
            Complex C = Coefficients[Coefficients.Length - 1];

            if (C != 0)
            {
                if ((C.IsReal && C.Real > 0) || ((!C.IsReal && !C.IsPurelyImaginary) && !(C.Imaginary < 0 && C.Real < 0)) || (C.IsPurelyImaginary && C.Imaginary > 0))
                    Result += " + ";
                else if ((C.IsReal && C.Real < 0) || (C.IsPurelyImaginary && C.Imaginary < 0) || (C.Imaginary < 0 && C.Real < 0)) Result += " - ";
                if (!C.IsReal && !C.IsPurelyImaginary) Result += "(";
                if (C != 1 && C != -1 && C != Complex.Iota && C != -Complex.Iota)
                {
                    if (C.Imaginary < 0 && C.Real < 0) Result += (-C).ToString();
                    else if (C.IsReal) Result += Math.Abs(C.Real).ToString();
                    else if (C.IsPurelyImaginary) Result += Math.Abs(C.Imaginary).ToString() + "i";
                    else Result += C.ToString();
                }
                else if (C == Complex.Iota || C == -Complex.Iota) Result += "i";
                else Result += 1;
                if (!C.IsReal && !C.IsPurelyImaginary) Result += ")";
            }

            return Result;
        }

        /// <summary>
        /// Returns the provided number in Superscript form.
        /// </summary>
        /// <param name="n">The number to transform into Superscript.</param>
        /// <returns>The Superscript form of the provided number.</returns>
        static string Superscript(int n)
        {
            string Result = string.Empty;

            foreach (char i in n.ToString())
            {
                switch (i)
                {
                    case '0': Result += '⁰'; break;
                    case '1': Result += '¹'; break;
                    case '2': Result += '²'; break;
                    case '3': Result += '³'; break;
                    case '4': Result += '⁴'; break;
                    case '5': Result += '⁵'; break;
                    case '6': Result += '⁶'; break;
                    case '7': Result += '⁷'; break;
                    case '8': Result += '⁸'; break;
                    case '9': Result += '⁹'; break;
                }
            }

            return Result;
        }
        #endregion
    }