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

namespace EvoBoat.EvoAlg.IntDivision
{
    public class IntDivisionSolutionFactory<P, S> : SolutionFactory<P, S, IntVector>
        where P : IntDivisionProblem<S>
        where S : class, ISolution<IntVector>, new()
    {
        public IntDivisionSolutionFactory(P problem, int seed = 0) : base(problem, seed)
        { }

        public override S CreateEmpty()
        {
            return new S() { Content = new IntVector(Problem.Dimension) };
        }

        public override S CreateRandom()
        {
            int[] x = new int[Problem.Dimension];
            RandDivide(Rand, Problem.Total, Problem.Dimension, ref x);
            if (x.Sum() != Problem.Total)
                x[0]++;
            return new S() { Content = new IntVector(x) };
        }

        /// <summary>
        /// 将sum随机划分为K份，结果存放在数组x的第0~(K-1)位
        /// </summary>
        void RandDivide(Random rand, int sum, int K, ref int[] x)
        {
            if (K == 1 || sum <= 1)
            {
                x[0] = sum;
                return;
            }
            if (sum == K)
            {
                for (int k = 0; k < K; k++)
                    x[k] = 1;
                return;
            }
            int i, avg = (int)Math.Round((double)sum / K);
            double r = Rand.NextDouble(), p = 0.5, delta = 0.25;
            for (i = 0; i < K; i++)
            {
                if (r < p)
                {
                    x[K - 1] = rand.Next(i * avg, (i + 1) * avg);
                    break;
                }
                p += delta;
                delta /= 2;
            }
            if (x[K - 1] > sum)
                x[K - 1] = sum;
            RandDivide(rand, sum - x[K - 1], K - 1, ref x);
        }
    }
}
