Index: branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs
===================================================================
--- branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs	(revision 10388)
+++ branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs	(revision 10392)
@@ -10,75 +10,56 @@
 
     private string solverTemplate = @"
+
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
-    public class SearchTreeNode {
-      public bool ready = false;
-      public SearchTreeNode[] children;
-      public int state;
-      public int nextAltIdx;
 
-      public SearchTreeNode(int state) {
-        // do not initialize children yet to save mem
-        nextAltIdx = 0;
+    private readonly ?IDENT?Problem problem;
+    private readonly Random random;
+
+    private IEnumerable<Tree> GenerateTrees(int parentState, int depth) {
+      if(depth<=1) {
+        if(Grammar.subtreeCount[parentState] == 0) 
+          foreach(var terminal in CreateTerminalNodes(parentState, problem)) 
+            yield return terminal;
+      } else if(Grammar.subtreeCount[parentState] == 1) {
+        for(int altIdx = 0; altIdx < Grammar.transition[parentState].Length; altIdx++) {
+          var targetState = Grammar.transition[parentState][altIdx];
+          foreach(var subtree in GenerateTrees(targetState, depth - 1)) {
+            var solution = new Tree(altIdx, new Tree[1] {subtree});
+            yield return solution;
+          }
+        }
+      } else if(Grammar.subtreeCount[parentState] > 1) {
+        var trees = new IEnumerable<Tree>[Grammar.subtreeCount[parentState]];
+        for(int subtreeIdx = 0; subtreeIdx < Grammar.subtreeCount[parentState]; subtreeIdx++) {
+          trees[subtreeIdx] = GenerateTrees(Grammar.transition[parentState][subtreeIdx], depth - 1);
+        }
+        foreach(var e in CartesianProduct(trees)) {
+          yield return new Tree(-1, e.ToArray()); // altIdx is ignored
+        }
+      } 
+    }
+
+    public IEnumerable<IEnumerable<Tree>> CartesianProduct(IEnumerable<IEnumerable<Tree>> sets) {
+      if(sets.Count() == 1) { 
+        foreach(var e in sets.First()) {
+          yield return new Tree[] {e};
+        }
       }
-      public SearchTreeNode GetNextNode() {
-        if(children == null) {
-          int nChildren = Grammar.subtreeCount[state] == 1 ? Grammar.transitions[state].Length : Grammar.subtreeCount[state];
-          children = new SearchTreeNode[nChildren];
-        }
-        if(children[nextAltIdx] == null) {
-          children[nextAltIdx] = 
+      else {
+        var firstSet = sets.First();
+        foreach(var e in firstSet) {
+          foreach(var p in CartesianProduct(sets.Skip(1))) {
+            yield return new Tree[] {e}.Concat(p);
+          }
         }
       }
     }
 
-
-    private readonly ?IDENT?Problem problem;
-    private readonly Random random;
-    private SearchTreeNode searchTree = null;
-
-    private IEnumerable<Tree> GenerateTrees(int maxDepth) {
-      if(searchTree==null) searchTree = new SearchTreeNode(0);
-      
-    }
-
-    private Tree GenerateTree(SearchTreeNode node) {
-      curDepth += 1;
-      steps += 1;
-      depth = Math.Max(depth, curDepth);
-      Tree t = null;
-
-      // terminals
-      if(Grammar.subtreeCount[state] == 0) {
-        t = CreateTerminalNode(state, random, problem);
-      } else {
-        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
-        if(Grammar.subtreeCount[state] == 1) {
-          var targetStates = Grammar.transition[state];
-          var altIdx = SampleAlternative(random, state, curDepth);
-          var alternative = SampleTree(targetStates[altIdx], ref steps, ref curDepth, ref depth);
-          t = new Tree(altIdx, new Tree[] { alternative });
-        } else {
-          // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
-          Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
-          for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
-            subtrees[i] = SampleTree(Grammar.transition[state][i], ref steps, ref curDepth, ref depth);
-          }
-          t = new Tree(-1, subtrees); // alternative index is ignored
-        }
-      }
-      curDepth -=1;
-      return t;
-    }
-
-    private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
+    private static IEnumerable<Tree> CreateTerminalNodes(int state, ?IDENT?Problem problem) {
       switch(state) {
         ?CREATETERMINALNODECODE?
         default: { throw new ArgumentException(""Unknown state index"" + state); }
       }
-    }
-
-    private int NextAlternative(SearchTreeNode node) {
-?RETURNNEXTALTERNATIVECODE?
     }
 
@@ -95,4 +76,5 @@
 
     private void Start() {
+      const int MAX_SECONDS = 100000;
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
@@ -100,23 +82,31 @@
       long sumSize = 0;
       var sumF = 0.0;
+      var terminationTimer = new Stopwatch();
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
-      for(int d = 1; d < 20; d++) {
-        foreach(var t in GenerateTrees(d)) {
+      terminationTimer.Start();
+      for(int depth = 1; terminationTimer.Elapsed.TotalSeconds < MAX_SECONDS; depth ++) {
+        Console.WriteLine(""Depth {0}:"", depth);
+        foreach(var t in GenerateTrees(0, depth)) {
           var f = problem.Evaluate(t);
-          
+          //t.PrintTree(0); Console.WriteLine();
+          var size = t.GetSize();
+          sumSize += size;
+          sumDepth += depth;
           n++;    
           sumF += f;
           if (problem.IsBetter(f, bestF)) {
             bestF = f;
-            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, 0, 0);
+            Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, size, depth);
           }
           if (n % 1000 == 0) {
             sw.Stop();
-            Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
+            Console.WriteLine(""{6,5:0.0s}: {0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"",
+                              n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds, terminationTimer.Elapsed.TotalSeconds);
             sumSize = 0;
             sumDepth = 0;
             sumF = 0.0;
             sw.Restart();
+            if(terminationTimer.Elapsed.TotalSeconds >= MAX_SECONDS) break;
           }
         }
@@ -130,44 +120,8 @@
       solverSourceCode.Append(solverTemplate)
         .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
-        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
         .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
       ;
 
       problemSourceCode.Append(solverSourceCode.ToString());
-    }
-
-
-
-    private string GenerateSampleAlternativeSource(IGrammar grammar) {
-      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
-      var sb = new SourceBuilder();
-      int stateCount = 0;
-      foreach (var s in grammar.Symbols) {
-        sb.AppendFormat("case {0}: ", stateCount++);
-        if (grammar.IsTerminal(s)) {
-          // ignore
-        } else {
-          var terminalAltIndexes = grammar.GetAlternatives(s)
-            .Select((alt, idx) => new { alt, idx })
-            .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
-            .Select(p => p.idx);
-          var nonTerminalAltIndexes = grammar.GetAlternatives(s)
-            .Select((alt, idx) => new { alt, idx })
-            .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
-            .Select(p => p.idx);
-          var hasTerminalAlts = terminalAltIndexes.Any();
-          var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
-          if (hasTerminalAlts && hasNonTerminalAlts) {
-            sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
-            GenerateReturnStatement(terminalAltIndexes, sb);
-            sb.Append("} else {");
-            GenerateReturnStatement(nonTerminalAltIndexes, sb);
-            sb.Append("}").EndBlock();
-          } else {
-            GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
-          }
-        }
-      }
-      return sb.ToString();
     }
 
@@ -179,44 +133,27 @@
         if (grammar.IsTerminal(s)) {
           sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
-          sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
           var terminal = terminals.Single(t => t.Ident == s.Name);
+          if (terminal.Constraints.Any(c => c.Type == ConstraintNodeType.Range)) {
+            throw new NotSupportedException("Sorry the brute force solver does not support RANGE constraints");
+          }
+          sb.AppendFormat("{0}Tree t = null;", terminal.Ident).AppendLine();
+          // create nested loop to produce all combinations of values (only set constraints)
           foreach (var constr in terminal.Constraints) {
-            if (constr.Type == ConstraintNodeType.Set) {
-              sb.Append("{").BeginBlock();
-              sb.AppendLine("throw new NotImplementedException(\"Enumeration of terminal values is not implemented.\");");
-              sb.AppendFormat("//var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
-              sb.AppendFormat("//t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock();
-              sb.AppendLine("}");
-            } else {
-              sb.Append("{").BeginBlock();
-              sb.AppendLine("throw new NotSupportedException(\"The brute force solver does not support RANGE constraints\");");
-              sb.AppendLine("}");
-            }
+            sb.AppendFormat("foreach(var {1} in problem.GetAllowed{0}_{1}()) {{;", terminal.Ident, constr.Ident).BeginBlock();
           }
-          sb.AppendLine("return t;").EndBlock();
-          sb.Append("}");
+          sb.AppendFormat("t = new {0}Tree();", terminal.Ident).AppendLine();
+
+          foreach (var constr in terminal.Constraints.Reverse()) {
+            sb.AppendFormat("t.{0} = {0};", constr.Ident).EndBlock();
+            sb.AppendLine("}");
+          }
+
+          sb.AppendLine("yield return t; ").EndBlock();
+
+          sb.AppendLine(" break; }");
         }
       }
       return sb.ToString();
     }
-
-    private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
-      if (idxs.Count() == 1) {
-        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
-      } else {
-        var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
-        sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
-      }
-    }
-
-    private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
-      if (nAlts > 1) {
-        sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
-      } else if (nAlts == 1) {
-        sb.AppendLine("return 0; ");
-      } else {
-        sb.AppendLine("throw new InvalidProgramException();");
-      }
-    }
   }
 }
