Index: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs
===================================================================
--- branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs	(revision 14778)
+++ branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs	(revision 14834)
@@ -20,17 +20,18 @@
 #endregion
 
-using System;
-using System.Collections.Generic;
-using System.Linq;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Data;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Random;
-using HeuristicLab.Selection;
+namespace HeuristicLab.Problems.ProgramSynthesis.Push.Selector {
+  using System;
+  using System.Collections.Generic;
+  using System.Linq;
 
-namespace HeuristicLab.Misc {
-  using HeuristicLab.Problems.ProgramSynthesis.Push.Selector;
+  using HeuristicLab.Common;
+  using HeuristicLab.Core;
+  using HeuristicLab.Data;
+  using HeuristicLab.Parameters;
+  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Extensions;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Problem;
+  using HeuristicLab.Selection;
+  using Random;
 
   /// <summary>
@@ -44,5 +45,5 @@
     public ILookupParameter<ItemArray<DoubleArray>> CaseQualitiesParameter
     {
-      get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters["CaseQualities"]; }
+      get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters[PushProblem.CaseQualitiesScopeParameterName]; }
     }
 
@@ -54,83 +55,66 @@
     }
 
-    public LexicaseSelector()
-      : base() {
-      Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("CaseQualities", "The quality of every single training case for each individual."));
+    public LexicaseSelector() {
+      this.Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>(
+        PushProblem.CaseQualitiesScopeParameterName,
+        "The quality of every single training case for each individual."));
     }
 
-    protected override IScope[] Select(List<IScope> scopes) {
-      int count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
-      bool copy = CopySelectedParameter.Value.Value;
-      IRandom random = RandomParameter.ActualValue;
-      bool maximization = MaximizationParameter.ActualValue.Value;
-      List<double> qualities = QualityParameter.ActualValue.Where(x => IsValidQuality(x.Value)).Select(x => x.Value).ToList();
-      List<DoubleArray> caseQualities = CaseQualitiesParameter.ActualValue.ToList();
+    protected override IScope[] Select(List<IScope> population) {
+      var count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
+      var copy = CopySelectedParameter.Value.Value;
+      var maximization = MaximizationParameter.ActualValue.Value;
+      var random = RandomParameter.ActualValue;
+      var selected = new IScope[count];
+      var caseQualities = CaseQualitiesParameter.ActualValue;
+      var repeats = Math.Ceiling(count / (double)population.Count);
+      var caseCount = caseQualities[0].Length;
+      var source = population.Select((x, i) => Tuple.Create(i, x));
 
-      // remove scopes, qualities and case qualities, if the case qualities are empty
-      var removeindices = Enumerable.Range(0, caseQualities.Count)
-                                    .Zip(caseQualities, (i, c) => new { Index = i, CaseQuality = c })
-                                    .Where(c => c.CaseQuality.Count() == 0)
-                                    .Select(c => c.Index)
-                                    .Reverse();
-      foreach (var i in removeindices) {
-        scopes.RemoveAt(i);
-        qualities.RemoveAt(i);
-        caseQualities.RemoveAt(i);
+      for (var k = 0; k < repeats; k++) {
+        // The fitness cases are shuffled.
+        var fitnessCaseIndexes = Enumerable.Range(0, caseCount).Shuffle(random).ToArray();
+        var pool = source.ToList();
+        var countLimit = Math.Min(count - k * population.Count, population.Count);
+
+        for (var i = 0; i < countLimit; i++) {
+          var bestIndividuals = pool;
+
+          for (var j = 0; j < fitnessCaseIndexes.Length && bestIndividuals.Count > 1; j++)
+            bestIndividuals = GetBestIndividuals(maximization, caseQualities, bestIndividuals, fitnessCaseIndexes[j]);
+
+          /*  If only one individual remains, it is the chosen parent. If no more fitness cases are left, a parent is
+              chosen randomly from the remaining individuals */
+          var currentSelected = bestIndividuals.Count == 1 ? bestIndividuals[0] : bestIndividuals.Random(random);
+          selected[k * population.Count + i] = copy ? (IScope)currentSelected.Item2.Clone() : currentSelected.Item2;
+
+          pool.Remove(currentSelected);
+        }
       }
 
-      if (caseQualities.Any(x => x.Count() != caseQualities[0].Length)) { throw new ArgumentException("Not all case qualities have the same length"); }
-
-      IScope[] selected = new IScope[count];
-
-      for (int i = 0; i < count; i++) {
-        int index = LexicaseSelect(caseQualities, RandomParameter.ActualValue, maximization);
-
-        if (copy)
-          selected[i] = (IScope)scopes[index].Clone();
-        else {
-          selected[i] = scopes[index];
-          scopes.RemoveAt(index);
-          qualities.RemoveAt(index);
-          caseQualities.RemoveAt(index);
-        }
-      }
       return selected;
     }
 
-    private int LexicaseSelect(List<DoubleArray> caseQualities, IRandom random, bool maximization) {
-      IList<int> candidates = Enumerable.Range(0, caseQualities.Count()).ToList();
-      IEnumerable<int> order = Enumerable.Range(0, caseQualities[0].Count()).Shuffle(random);
+    private static List<Tuple<int, IScope>> GetBestIndividuals(bool maximization, ItemArray<DoubleArray> caseQualities, List<Tuple<int, IScope>> bestIndividuals, int index) {
+      var bestFitness = maximization ? double.NegativeInfinity : double.PositiveInfinity;
+      var result = new List<Tuple<int, IScope>>();
 
-      foreach (int curCase in order) {
-        List<int> nextCandidates = new List<int>();
-        double best = maximization ? double.NegativeInfinity : double.PositiveInfinity;
-        foreach (int candidate in candidates) {
-          if (caseQualities[candidate][curCase].IsAlmost(best)) {
-            // if the individuals is as good as the best one, add it
-            nextCandidates.Add(candidate);
-          } else if (((maximization) && (caseQualities[candidate][curCase] > best)) ||
-             ((!maximization) && (caseQualities[candidate][curCase] < best))) {
-            // if the individuals is better than the best one, remove all previous candidates and add the new one
-            nextCandidates.Clear();
-            nextCandidates.Add(candidate);
-            // also set the nes best quality value
-            best = caseQualities[candidate][curCase];
-          }
-          // else {do nothing}
+      for (var l = 0; l < bestIndividuals.Count; l++) {
+        var individual = bestIndividuals[l];
+        var caseQuality = caseQualities[individual.Item1][index];
+
+        if (bestFitness == caseQuality) {
+          result.Add(individual);
+        } else if (maximization && bestFitness < caseQuality ||
+                  !maximization && bestFitness > caseQuality) {
+          bestFitness = caseQuality;
+          result.Clear();
+          result.Add(individual);
         }
 
-        if (nextCandidates.Count == 1) {
-          return nextCandidates.First();
-        } else if (nextCandidates.Count < 1) {
-          return candidates.SampleRandom(random);
-        }
-        candidates = nextCandidates;
+        bestIndividuals = result;
       }
 
-
-      if (candidates.Count == 1) {
-        return candidates.First();
-      }
-      return candidates.SampleRandom(random);
+      return bestIndividuals;
     }
   }
