using System;

namespace GeneticAlgorithm
{
    /// <summary>
	/// Genetic Algorithm class
	/// </summary>
	public class GA
	{
		private double _totalFitness;
		private List<Genome> _thisGeneration;
		private List<Genome> _nextGeneration;
		private List<double> _fitnessTable;
		private static Random _random = new Random();
		public Func<double[], double> FitnessFunction { get; set; }
		public int PopulationSize { get; set; }
		public int GenerationSize { get; set; }
		public int GenomeSize { get; set; }
		public double MutationRate { get; set; }
		public string FitnessFile { get; set; }
		public double CrossoverRate { get; set; }
		public bool Elitism { get; set; }
		
		/// <summary>
		/// Default constructor sets mutation rate to 5%, crossover to 80%, population to 100, and generations to 2000.
		/// </summary>
		public GA()
			: this(0.8, 0.05, 100, 2000, 2)
		{
		}
		
		public GA(int genomeSize)
			: this(0.8, 0.05, 100, 2000, genomeSize)
		{
		}
		
		public GA(double crossoverRate, double mutationRate, int populationSize, int generationSize, int genomeSize)
		{
			Elitism = false;
			MutationRate = mutationRate;
			CrossoverRate = crossoverRate;
			PopulationSize = populationSize;
			GenerationSize = generationSize;
			GenomeSize = genomeSize;
			FitnessFile = "";
		}
		
		/// <summary>
		/// Method which starts the GA executing.
		/// </summary>
		public void Go()
		{
			if (FitnessFunction == null)
				throw new ArgumentNullException("Need to supply fitness function");
			if (GenomeSize == 0)
				throw new IndexOutOfRangeException("Genome size not set");
			
			//  Create the fitness table.
			_fitnessTable = new List<double>();
			_thisGeneration = new List<Genome>(GenerationSize);
			_nextGeneration = new List<Genome>(GenerationSize);
			
			Genome.MutationRate = MutationRate;
			CreateGenomes();
			RankPopulation();
			StreamWriter outputFitness = null;
			bool write = false;

			if (FitnessFile != "")
			{
				write = true;
				outputFitness = new StreamWriter(FitnessFile);
			}

			for (int i = 0; i < GenerationSize; i++)
			{
				CreateNextGeneration();
				RankPopulation();
				if (write)
				{
					if (outputFitness != null)
					{
						double d = (double)((Genome)_thisGeneration[PopulationSize - 1]).Fitness;
						outputFitness.WriteLine("{0},{1}", i, d);
					}
				}
			}

			if (outputFitness != null)
				outputFitness.Close();
		}

		/// <summary>
		/// After ranking all the genomes by fitness, use a 'roulette wheel' selection
		/// method.  This allocates a large probability of selection to those with the
		/// highest fitness.
		/// </summary>
		/// <returns>Random individual biased towards highest fitness</returns>
		private int RouletteSelection()
		{
			double randomFitness = _random.NextDouble() * _totalFitness;
			int idx = -1;
			int mid;
			int first = 0;
			int last = PopulationSize - 1;
			mid = (last - first) / 2;

			//  ArrayList's BinarySearch is for exact values only
			//  so do this by hand.
			while (idx == -1 && first <= last)
			{
				if (randomFitness < _fitnessTable[mid])
				{
					last = mid;
				}
				else if (randomFitness > _fitnessTable[mid])
				{
					first = mid;
				}
				mid = (first + last) / 2;

				//  lies between i and i+1
				if ((last - first) == 1)
					idx = last;
			}
			return idx;
		}

		/// <summary>
		/// Rank population and sort in order of fitness.
		/// </summary>
		private void RankPopulation()
		{
			_totalFitness = 0;
			for (int i = 0; i < PopulationSize; i++)
			{
				Genome g = ((Genome)_thisGeneration[i]);
				g.Fitness = FitnessFunction(g.Genes);
				_totalFitness += g.Fitness;
			}

			_thisGeneration.Sort(new GenomeComparer());

			//  now sorted in order of fitness.
			double fitness = 0.0;
			_fitnessTable.Clear();

			for (int i = 0; i < PopulationSize; i++)
			{
				fitness += ((Genome)_thisGeneration[i]).Fitness;
				_fitnessTable.Add((double)fitness);
			}
		}

		/// <summary>
		/// Create the *initial* genomes by repeated calling the supplied fitness function
		/// </summary>
		private void CreateGenomes()
		{
			for (int i = 0; i < PopulationSize; i++)
			{
				Genome genome = new Genome(GenomeSize);
				_thisGeneration.Add(genome);
			}
		}

		private void CreateNextGeneration()
		{
			_nextGeneration.Clear();
			Genome genome = null;

			if (Elitism)
				genome = _thisGeneration[PopulationSize - 1];

			for (int i = 0; i < PopulationSize; i += 2)
			{
				int pidx1 = RouletteSelection();
				int pidx2 = RouletteSelection();

				Genome parent1, parent2, child1, child2;
				parent1 = _thisGeneration[pidx1];
				parent2 = _thisGeneration[pidx2];

				if (_random.NextDouble() < CrossoverRate)
				{
					parent1.Crossover(ref parent2, out child1, out child2);
				}
				else
				{
					child1 = parent1;
					child2 = parent2;
				}

				child1.Mutate();
				child2.Mutate();

				_nextGeneration.Add(child1);
				_nextGeneration.Add(child2);
			}

			if (Elitism && genome != null)
				_nextGeneration[0] = genome;

			_thisGeneration.Clear();

			for (int i = 0; i < PopulationSize; i++)
				_thisGeneration.Add(_nextGeneration[i]);
		}

		public void GetBest(out double[] values, out double fitness)
		{
			Genome genome = _thisGeneration[PopulationSize - 1];
			values = new double[genome.Length];
			genome.GetValues(ref values);
			fitness = (double)genome.Fitness;
		}

		public void GetWorst(out double[] values, out double fitness)
		{
			GetNthGenome(0, out values, out fitness);
		}

		public void GetNthGenome(int n, out double[] values, out double fitness)
		{
			if (n < 0 || n > PopulationSize - 1)
				throw new ArgumentOutOfRangeException("n too large, or too small");
			
			Genome genome = _thisGeneration[n];
			values = new double[genome.Length];
			genome.GetValues(ref values);
			fitness = (double)genome.Fitness;
		}
	}
}