using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Reflection;

namespace EvoBoat.EvoAlg
{
    public delegate S SingleSolutionOperator<S>(S sol);
    public delegate S SingleSolutionOperatorWithInd<S>(S sol, int index);
    public delegate S DoubleSolutionOperator<S>(S sol1, S sol2);
    public delegate Tuple<S, S> DoubleToDoubleSolutionOperator<S>(S sol1, S sol2);
    
    public abstract class EAlg<P, S, R, e> : IAlg<P, S, R>
        where P : IProblem<S, R>
        where S : class, ISolution<R>, new()
        where R : IVector<e>
    {
        public const double epsilon = 0.00000000001;
        public string Name { get; set; }

        public P Problem { get; set; }

        public SolutionFactory<P, S, R> Factory { get; set; }

        protected S[] pop;
        /// <summary>
        /// Population of solutions
        /// </summary>
        public S[] Pop { get { return pop; } }
        IEnumerable<S> IAlg<P, S, R>.Pop { get { return pop; } }

        protected int size = 30;
        public int Size
        {
            get { return size; }
            set { size = value; }
        }
        public int SizeMin { get; set; }

        protected double obest;
        protected S best, worst;
        protected int iBest, iWorst;
        /// <summary>
        /// The best solution found so far
        /// </summary>
        public S Best { get { return best; } }
        /// <summary>
        /// The worst solution in the population
        /// </summary>
        public S Worst { get { return worst; } set { worst = value; } }
        /// <summary>
        /// Index of the best solution in the population
        /// </summary>
        public int IndBest { get { return iBest; } }
        /// <summary>
        /// Index of the worst solution in the population
        /// </summary>
        public int IndWorst { get { return iWorst; } set { iWorst = value; } }

        public Random Rand { get; set; }

        protected bool[,] linkMatrix;
        public bool[,] LinkMatrix
        {
            get { return linkMatrix; }
        }

        public Func<bool[,], bool[,]> FunSetToplogy { get; set; }

        protected int[] bestNeighborIndices; //Best neighbor of the solutions
        protected double[] sumNeighborProbs; //Sum of the selection probabilities of the neighbors

        protected int iter, iters, nfe, nfes;
        /// <summary>
        /// Current number of iterations
        /// </summary>
        public int Iter { get { return iter; } }
        /// <summary>
        /// Max number of iterations
        /// </summary>
        public int Iters { get { return iters; } set { iters = value; } }
        /// <summary>
        /// Current number of fitness evaluations
        /// </summary>
        public int Nfe { get { return nfe; } }
        /// <summary>
        /// Max number of fitness evaluations
        /// </summary>
        public int Nfes { get { return nfes; } set { nfes = value; } }

        public EAlg()
        {
            Rand = new Random((int)DateTime.Now.Ticks);
        }

        public EAlg(int seed = 0)
        {
            Rand = new Random(seed);
        }

        public EAlg(P problem, int seed = 0)
        {
            this.Problem = problem;
            if (seed == 0)
                Rand = new Random((int)DateTime.Now.Ticks);
            else
                Rand = new Random(seed);
        }

        public override string ToString()
        {
            return Name;
        }

        public virtual double Evaluate(S sol)
        {
            sol.Fit = Problem.Evaluate(sol);
            nfe++;
            return sol.Fit;
        }

        /// <summary>
        /// Initialize control parameters 
        /// </summary>
        public abstract void SetParameters();

        /// <summary>
        /// Initialize the factory for creating initial solutions
        /// </summary>
        public abstract void SetFactory();

        /// <summary>
        /// Update control parameters
        /// </summary>
        public abstract void Calculate();

        /// <summary>
        /// Perform an iteration of evolution 
        /// </summary>
        public abstract void Evolve();

        /// <summary>
        /// Initialize the population
        /// </summary>
        public virtual void InitPop()
        {
            pop = Factory.CreatePop(size);
            this.Evaluate(pop[0]);
            best = worst = pop[0];
            for (int i = 1; i < size; i++)
            {
                this.Evaluate(pop[i]);
                if (pop[i].Fit < best.Fit)
                {
                    best = pop[i];
                    iBest = i;
                }
                else if (pop[i].Fit > worst.Fit)
                {
                    worst = pop[i];
                    iWorst = i;
                }
            }
            obest = best.Fit;
        }

        public virtual void UpdateBest()
        {
            if (best == null)
            {
                best = pop[0];
                iBest = 0;
            }
            for (int i = 0; i < pop.Length; i++)
                if (pop[i].Fit < best.Fit)
                {
                    best = pop[i];
                    iBest = i;
                }
        }

        public virtual void UpdateWorst()
        {
            worst = pop[0];
            iWorst = 0;
            for (int i = 0; i < pop.Length; i++)
                if (pop[i].Fit > worst.Fit)
                {
                    worst = pop[i];
                    iWorst = i;
                }
        }

        public virtual void UpdateBestWorst()
        {
            if (best == null)
            {
                best = pop[0];
                iBest = 0;
            }
            worst = pop[0];
            iWorst = 0;
            for (int i = 0; i < pop.Length; i++)
                if (pop[i].Fit < best.Fit)
                {
                    best = pop[i];
                    iBest = i;
                }
                else if (pop[i].Fit > worst.Fit)
                {
                    worst = pop[i];
                    iWorst = i;
                }
        }

        public virtual void ReduceSize()
        {
            if (pop.Length > SizeMin)
            {
                if(iWorst != pop.Length - 1)
                    pop[iWorst] = pop[pop.Length - 1];
                pop = pop.Take(pop.Length - 1).ToArray();
                this.UpdateWorst();
            }
        }

        public int RandomSelectIndex(int n, int exi)
        {
            int r = Rand.Next(n);
            while (r == exi)
                r = Rand.Next(n);
            return r;
        }

        public Tuple<int, int> RandomSelectTwoIndicies(int n)
        {
            int r1 = Rand.Next(n);
            int r2 = Rand.Next(n);
            while (r2 == r1)
                r2 = Rand.Next(n);
            return new Tuple<int, int>(r1, r2);
        }

        public Tuple<int, int> RandomSelectTwoIndicies(int n, int exi)
        {
            int r1 = Rand.Next(n);
            while (r1 == exi)
                r1 = Rand.Next(n);
            int r2 = Rand.Next(n);
            while (r2 == exi || r2 == r1)
                r2 = Rand.Next(n);
            return new Tuple<int, int>(r1, r2);
        }
        
        public Tuple<int, int> RandomSelectTwoIndicies(int n, int exi1, int exi2)
        {
            int r1 = Rand.Next(n);
            while (r1 == exi1 || r1 == exi2)
                r1 = Rand.Next(n);
            int r2 = Rand.Next(n);
            while (r2 == exi1 || r2 == exi2 || r2 == r1)
                r2 = Rand.Next(n);
            return new Tuple<int, int>(r1, r2);
        }

        public Tuple<int, int, int> RandomSelectThreeIndices(int n, int exi)
        {
            int r1 = Rand.Next(n);
            while (r1 == exi)
                r1 = Rand.Next(n);
            int r2 = Rand.Next(n);
            while (r2 == exi || r2 == r1)
                r2 = Rand.Next(n);
            int r3 = Rand.Next(n);
            while (r3 == exi || r3 == r1 || r3 == r2)
                r3 = Rand.Next(n);
            return new Tuple<int, int, int>(r1, r2, r3);
        }

        public Tuple<int, int, int, int> RandomSelectFourIndicies(int n, int exi)
        {
            int r1 = Rand.Next(n);
            while (r1 == exi)
                r1 = Rand.Next(n);
            int r2 = Rand.Next(n);
            while (r2 == exi || r2 == r1)
                r2 = Rand.Next(n);
            int r3 = Rand.Next(n);
            while (r3 == exi || r3 == r1 || r3 == r2)
                r3 = Rand.Next(n);
            int r4 = Rand.Next(n);
            while (r4 == exi || r4 == r1 || r4 == r2 || r4 == r3)
                r4 = Rand.Next(n);
            return new Tuple<int, int, int, int>(r1, r2, r3, r4);
        }

        public int[] RandomSelectKIndicies(int n, int K)
        {
            if (K > n)
                throw new ArgumentOutOfRangeException("K must be less than n");
            int[] sels = new int[K];
            List<int> list = new List<int>(n);
            for (int i = 0; i < n; i++)
                list.Add(i);
            int k = 0, j;
            while (k < K)
            {
                j = Rand.Next(list.Count);
                sels[k++] = list[j];
                list.RemoveAt(j);
            }
            return sels;
        }

        public int[] RandomSelectKIndicies(int n, int K, int exi)
        {
            if (K >= n)
                throw new ArgumentOutOfRangeException("K must be less than n");
            int[] sels = new int[K];
            List<int> list = new List<int>(n);
            for (int i = 0; i < n; i++)
                if (i != exi)
                    list.Add(i);
            int k = 0, j;
            while (k < K)
            {
                j = Rand.Next(list.Count);
                sels[k++] = list[j];
                list.RemoveAt(j);
            }
            return sels;
        }

        /// <summary>
        /// Randomly select an index from collection based on the probabilities specified in pbs
        /// </summary>
        public int RouletteSelect<T>(T[] collection, double[] pbs, double sum = 0)
        {
            if (sum == 0)
                sum = pbs.Sum();
            double r = Rand.NextDouble() * sum;
            double cp = 0;
            int i = 0;
            for (; i < collection.Length; i++)
            {
                cp += pbs[i];
                if (r <= cp)
                    break;
            }
            return i;
        }


        /// <summary>
        /// Randomly select an index other than exi from collection based on the probabilities specified in pbs
        /// </summary>
        public int RouletteSelect<T>(T[] collection, int exi, double[] pbs, double sum = 0)
        {
            if (sum == 0)
                sum = pbs.Sum();
            sum -= pbs[exi];
            double r = Rand.NextDouble() * sum;
            double cp = 0;
            int i = 0;
            for (; i < collection.Length; i++)
            {
                if (i == exi) continue;
                cp += pbs[i];
                if (r <= cp)
                    break;
            }
            return i;
        }

        /// <summary>
        /// Randomly select two indicies from collection based on the probabilities specified in pbs
        /// </summary>
        public virtual Tuple<int, int> RouletteSelectTwo<T>(T[] collection, double[] pbs, double sum = 0)
        {
            if (sum == 0)
                sum = pbs.Sum();
            int i = RouletteSelect(collection, pbs, sum);
            int j = RouletteSelect(collection, i, pbs, sum);
            return new Tuple<int, int>(i, j);
        }

        public virtual int RandomlySelectNeighbor(int index)
        {
            List<int> candidates = new List<int>(pop.Length);
            for (int i = 0; i < pop.Length; i++)
                if (i != index && linkMatrix[index, i])
                    candidates.Add(i);
            if (candidates.Count == 0) return -1;
            return candidates[Rand.Next(candidates.Count)];
        }

        public virtual int RouletteSelectNeighbor(Func<S, int, double> fun, int index)
        {
            int sel = -1;
            double r = Rand.NextDouble() * sumNeighborProbs[index];
            double cEm = 0;
            for (int i = 0; i < pop.Length; i++)
            {
                if (i != index && linkMatrix[index, i])
                {
                    cEm += fun(pop[i], i);
                    if (r < cEm)
                    {
                        sel = i;
                        break;
                    }
                }
            }
            if (sel < 0) return RandomlySelectNeighbor(index);
            return sel;
        }

        public void ComputeBestNeighbors()
        {
            bestNeighborIndices = new int[pop.Length];
            int i, j, k;
            double tv;
            for (i = 0; i < pop.Length; i++)
            {
                k = -1;
                tv = double.PositiveInfinity;
                for (j = 0; j < pop.Length; j++)
                {
                    if (i!=j && linkMatrix[i, j] && pop[j].Fit < tv)
                    {
                        k = j;
                        tv = pop[k].Fit;
                    }
                }
                bestNeighborIndices[i] = k;
            }
        }

        public void ComputeSumNeighborProbs(Func<S, int, double> fun)
        {
            sumNeighborProbs = new double[pop.Length];
            for (int i = 0; i < pop.Length; i++)
                for (int j = 0; j < pop.Length; j++)
                    if (i != j && linkMatrix[i, j])
                        sumNeighborProbs[i] += fun(pop[j], j);
        }

        public virtual S Solve(int iters)
        {
            this.iters = iters;
            this.InitPop();
            while (iter < iters)
            {
                this.Calculate();
                this.Evolve();
            }
            return best;
        }

        public virtual S Solve(int iters, out long time)
        {
            this.iters = iters;
            Stopwatch watch = new Stopwatch();
            watch.Start();
            this.InitPop();
            while (iter < iters)
            {
                this.Calculate();
                this.Evolve();
            }
            watch.Stop();
            time = watch.ElapsedMilliseconds;
            return best;
        }

        public virtual S SolveAndWatch(int iters, out long time, out List<double> data, int interval = 1)
        {
            this.iters = iters;
            data = new List<double>();
            Stopwatch watch = new Stopwatch();
            watch.Start();
            this.InitPop();
            while (iter <= iters)
            {
                this.Calculate();
                this.Evolve();
                if (iter % interval == 0)
                    data.Add(best.Fit);
            }
            watch.Stop();
            time = watch.ElapsedMilliseconds;
            return best;
        }

        public virtual S SolveF(int nfes)
        {
            this.nfes = nfes;
            if (iters == 0)
            {
                if (Name != null && Name.Contains("Harmony"))
                    iters = nfes;
                else if (SizeMin == 0 || SizeMin == size)
                    iters = nfes / size;
                else
                    iters = nfes * 2 / (size + SizeMin);
            }
            this.InitPop();
            while (nfe < nfes)
            {
                this.Calculate();
                this.Evolve();
            }
            return best;
        }

        public virtual S SolveF(int nfes, out long time)
        {
            this.nfes = nfes;
            if (iters == 0)
            {
                if (Name != null && Name.Contains("Harmony"))
                    iters = nfes;
                else if (SizeMin == 0 || SizeMin == size)
                    iters = nfes / size;
                else
                    iters = nfes * 2 / (size + SizeMin);
            }
            Stopwatch watch = new Stopwatch();
            watch.Start();
            this.InitPop();
            while (nfe <= nfes)
            {
                this.Calculate();
                this.Evolve();
            }
            watch.Stop();
            time = watch.ElapsedMilliseconds;
            return best;
        }

        public virtual S SolveFAndWatch(int nfes, out long time, out List<double> data, int interval)
        {
            this.nfes = nfes;
            if (iters == 0)
            {
                if (Name != null && Name.Contains("Harmony"))
                    iters = nfes;
                else if (SizeMin == 0 || SizeMin == size)
                    iters = nfes / size;
                else
                    iters = nfes * 2 / (size + SizeMin);
            }
            data = new List<double>();
            Stopwatch watch = new Stopwatch();
            watch.Start();
            this.InitPop();
            int k = 0;
            while (nfe <= nfes)
            {
                this.Calculate();
                this.Evolve();
                if ((nfe >= interval * k) && (nfe < interval * (k + 1)))
                {
                    data.Add(best.Fit);
                    k++;
                }
            }
            watch.Stop();
            time = watch.ElapsedMilliseconds;
            return best;
        }

        public virtual S SolveFAndWatch(int nfes, double th, out long num, out List<double> data, int interval)
        {
            num = -1;
            this.nfes = nfes;
            if (iters == 0)
            {
                if (Name != null && Name.Contains("Harmony"))
                    iters = nfes;
                else if (SizeMin == 0 || SizeMin == size)
                    iters = nfes / size;
                else
                    iters = nfes * 2 / (size + SizeMin);
            }
            data = new List<double>();
            this.InitPop();
            int k = 0;
            while (nfe <= nfes)
            {
                this.Calculate();
                this.Evolve();
                if (num < 0 && best.Fit <= th)
                    num = nfe;
                if ((nfe >= interval * k) && (nfe < interval * (k + 1)))
                {
                    data.Add(best.Fit);
                    k++;
                }
            }
            if (num == -1)
                num = nfes;
            return best;
        }

        /// <summary>
        /// reset the algorithm
        /// </summary>
        public virtual void Reset()
        {
            best = null;
            worst = null;
            linkMatrix = null;
            Rand = new Random((int)DateTime.Now.Ticks);
            nfe = iter = 0;
        }

        public static bool[,] SetRingTopology(bool[,] linkMatrix)
        {
            int n = linkMatrix.GetLength(0);
            linkMatrix = new bool[n, n];
            linkMatrix[0, n - 1] = linkMatrix[n - 1, 0] = true;
            for (int i = 0; i < n - 1; i++)
                linkMatrix[i, i + 1] = linkMatrix[i + 1, i] = true;
            return linkMatrix;
        }

        public static bool[,] SetSquareTopology(bool[,] linkMatrix)
        {
            int k = 10;
            int n = linkMatrix.GetLength(0);
            if (n < k)
                throw new ArgumentException("The size of a population with square topology cannot be less than 10");
            linkMatrix = new bool[n, n];
            for (int i = 0; i < n - 1; i++)
            {
                linkMatrix[i, i + 1] = linkMatrix[i + 1, i] = true;
                linkMatrix[i, (i + k) % n] = linkMatrix[(i + k) % n, i] = true;
            }
            linkMatrix[0, n - 1] = linkMatrix[n - 1, 0] = true;
            linkMatrix[k - 1, n - 1] = linkMatrix[n - 1, k - 1] = true;
            return linkMatrix;
        }

        public static Func<bool[,], bool[,]> SetRandomTopology(Random Rand, int KSize)
        {
            return new Func<bool[,], bool[,]>(linkMatrix =>
            {
                int n = linkMatrix.GetLength(0);
                linkMatrix = new bool[n, n];
                double prob = 1.0 - Math.Pow(1.0 - 1.0 / n, KSize);
                bool iso;
                for (int i = 0; i < n; i++)
                {
                    iso = true;
                    for (int j = 0; j < n; j++)
                        if (i != j && Rand.NextDouble() < prob)
                        {
                            linkMatrix[i, j] = linkMatrix[j, i] = true;
                            iso = false;
                        }
                    if (iso)
                    {
                        int j = Rand.Next(n);
                        while (i == j)
                            j = Rand.Next(n);
                        linkMatrix[i, j] = linkMatrix[j, i] = true;
                    }
                }
                return linkMatrix;
            });
        }
    }
}
