Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs	(revision 10334)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs	(revision 10335)
@@ -2,34 +2,183 @@
 using System.Collections.Generic;
 using System.Diagnostics;
-using System.IO;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Grammars;
-using Attribute = HeuristicLab.Grammars.Attribute;
 
 namespace CodeGenerator {
   public class BruteForceCodeGen {
-
-    private string usings = @"
-using System.Collections.Generic;
-using System.Linq;
-using System;
-";
-
     private string solverTemplate = @"
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
 
+    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
+?TRANSITIONTABLE?
+    };
+    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
+       { -1, 0 }, // terminals
+?SUBTREECOUNTTABLE?
+    };
+
+    private static string[] symb = new string[] { ?SYMBOLNAMES? };
+    private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? };
+    private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? };
+
+    
+    public sealed class SolverState : ISolverState {
+      private class Node {
+        public int state;
+        public int count;
+        public List<Node> nodes;
+        public bool done;
+        private int nextAlt;
+        public Node(int state) {
+          this.state = state;
+          nodes = new List<Node>(transition[state].Length);
+          if (!hasAlternatives[state]) {
+            foreach (var t in transition[state]) { nodes.Add(new Node(t)); }
+          }
+        }
+
+        public int GetNextAlternative() {
+          System.Diagnostics.Debug.Assert(hasAlternatives[state]);
+          if(nodes.Count == 0 && !isTerminal[state]) { 
+            foreach(var targetState in transition[state]) nodes.Add(new Node(targetState));
+            nextAlt = 0; 
+            // begin with a terminal if possible
+            if(!isTerminal[nodes[nextAlt].state]) 
+              do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]);
+          }
+
+          throw new NotImplementedException(); // TODO: handle terminal classes correctly
+          return nextAlt;
+        }
+
+        public void Update() {
+          count++;
+          if(hasAlternatives[state] && !isTerminal[state]) {
+            nodes[GetNextAlternative()].Update();
+            // check if all nodes done and set this node to done
+            if(nodes.All(n=>n.done)) { 
+              this.done = true;
+            } else {
+              // must not walk nodes that are done
+              do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done);
+            }
+          } else {
+            if(isTerminal[state]) {
+              throw new NotImplementedException(); // TODO: handle terminal classes correctly
+              done = (nextAlt + 1) >= GetAlternativesCount(symb[state]);
+            } else {
+              // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one
+              Node minNode = nodes.First();
+              foreach(var node in nodes.Skip(1)) {
+                if(node.count < minNode.count) {
+                  minNode = node;
+                }
+              }
+              minNode.Update();
+              if(nodes.All(n=>n.done)) this.done = true;
+            }
+          }
+        }
+      }
+
+
+      ?ALTERNATIVESCOUNTMETHOD?
+
+
+      public int curDepth;
+      public int steps;
+      public int depth;
+      private readonly Stack<Node> nodes;
+      private readonly IGpdlProblem problem;
+      private readonly Node searchTree;
+
+      public SolverState(IGpdlProblem problem) {
+        this.problem = problem;
+        nodes = new Stack<Node>();
+        searchTree = new Node(0);
+        nodes.Push(searchTree);
+      }
+
+      public void Reset() {
+        System.Diagnostics.Debug.Assert(nodes.Count == 1);
+        steps = 0;
+        depth = 0;
+        curDepth = 0;
+      }
+
+      public int PeekNextAlternative() {
+        var curNode = nodes.Peek();
+        System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]);
+        return curNode.GetNextAlternative();
+      }
+
+      public void Follow(int idx) {
+        steps++;
+        curDepth++;
+        depth = Math.Max(depth, curDepth);
+        var curNode = nodes.Peek();
+        if(hasAlternatives[curNode.state]) {
+          nodes.Push(curNode.nodes[curNode.GetNextAlternative()]);
+        } else {
+          nodes.Push(curNode.nodes[idx]);
+        }
+      }
+
+      public void Unwind() {
+        nodes.Pop();
+        curDepth--;
+      }
+
+      public void Update() {
+        searchTree.Update();
+      }
+    }
+
     public static void Main(string[] args) {
-      var solver = new ?IDENT?Solver();
+      var problem = new ?IDENT?Problem();
+      var solver = new ?IDENT?Solver(problem);
       solver.Start();
     }
-
-    public ?IDENT?Solver() { 
-      Initialize();
-    }    
-
-    private void Initialize() {
-      ?INITCODE?
+    
+    private readonly ?IDENT?Problem problem;
+    public ?IDENT?Solver(?IDENT?Problem problem) {
+      this.problem = problem;
+    }
+
+    private void Start() {
+      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
+      int n = 0;
+      long sumDepth = 0;
+      long sumSize = 0;
+      var sumF = 0.0;
+      var sw = new System.Diagnostics.Stopwatch();
+      sw.Start();
+      var _state = new SolverState(problem);
+      while (true) {
+
+        var f = problem.Evaluate(_state);
+        _state.Update();
+
+        n++;
+        sumSize += _state.steps;
+        sumDepth += _state.depth;
+        sumF += f;
+        if (IsBetter(f, bestF)) {
+          // evaluate again with tracing to console
+          // problem.Evaluate(new SolverState(_state.seed, true));
+          bestF = f;
+          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.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);
+          sw.Reset();
+          sumSize = 0;
+          sumDepth = 0;
+          sumF = 0.0;
+          sw.Start();
+        }
+      }
     }
 
@@ -37,327 +186,123 @@
       return ?MAXIMIZATION? ? a > b : a < b;
     }
-
-    private class SearchTree {
-      private SearchTree[] subTrees;
-      public bool Done { get; private set; }
-      private int nextAlternative;
-
-      public SearchTree() {
-        Done = false;
-      }
-
-      public SearchTree GetSubtree(int i) {
-        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
-        return subTrees[i];
-      }
-
-      public int GetNextAlternative() {
-        System.Diagnostics.Debug.Assert(IsAlternativeNode);
-        return nextAlternative;
-      }
-
-      public bool IsUninitialized {
-        get { return subTrees == null; }
-      }
-
-      public void SetNumberOfSubtrees(int n) {
-        this.subTrees = new SearchTree[n]; 
-        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
-        nextAlternative = 0;
-      }
-
-      public void UpdatePath() {
-        System.Diagnostics.Debug.Assert(!Done);
-        if (IsUninitialized) { return; }
-        Count++;
-        if (subTrees.Length == 0) {
-          Done = true;
-        }
-        if (IsAlternativeNode) {
-          // update only the active alternative and calculate a new alternative
-          subTrees[nextAlternative].UpdatePath();
-
-          do {
-            nextAlternative = (nextAlternative + 1) % subTrees.Length;
-          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
-        } else {
-          // for sequenceNodes update all sub-trees
-          foreach (var t in subTrees) t.UpdatePath();
-        }
-        // set node to done if all nodes are non-null and done
-        this.Done = true;
-        foreach(var t in subTrees) {
-          if(t == null || !t.Done) 
-            { this.Done = false; break; }
-        }        
-      }
-
-      public bool IsAlternativeNode { get; set; }
-      public bool IsSequenceNode { get; set; }
-      public int Count { get; private set; }
-    }
-
-    private SearchTree tree;
-    private void Start() {
-      // start with empty tree
-      tree = new SearchTree();
-      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
-      int n = 0;
-      var sw = new System.Diagnostics.Stopwatch();
-      sw.Start();
-      while (!tree.Done) {
-
-        var f = Calculate();
-        // do one more run through the tree to update the path
-        tree.UpdatePath();
-
-        n++;
-        if (IsBetter(f, bestF)) bestF = f;
-        if (n % 100 == 0) {
-          sw.Stop();
-          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
-          sw.Reset();
-          sw.Start();
-        }
-      }
-    }
-
-    public double Calculate() {
-      ?FITNESSFUNCTION?
-    }
-
-    ?ADDITIONALCODE?
-
-    ?INTERPRETERSOURCE?
-
-    ?CONSTRAINTSSOURCE?
   }
 }";
 
 
-    /// <summary>
-    /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
-    /// </summary>
-    /// <param name="ast">An abstract syntax tree for a GPDL file</param>
-    public void Generate(GPDefNode ast) {
-      var problemSourceCode = new StringBuilder();
-      problemSourceCode.AppendLine(usings);
-
-      GenerateProblem(ast, problemSourceCode);
-
-      problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
-
-      // write the source file to disk
-      using (var stream = new StreamWriter(ast.Name + ".cs")) {
-        stream.WriteLine(problemSourceCode.ToString());
-      }
-    }
-
-    private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
-      var grammar = CreateGrammarFromAst(ast);
-      var problemClassCode =
-        solverTemplate
-          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
-          .Replace("?IDENT?", ast.Name)
-          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
-          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
-          .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
-          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
-          .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
-          ;
-
-      problemSourceCode.AppendLine(problemClassCode).AppendLine();
-    }
-
-    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
-
-      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
-      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
-      string startSymbolName = ast.Rules.First().NtSymbol;
-
-      // create startSymbol
-      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
-      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
-
-      // add all production rules
-      foreach (var rule in ast.Rules) {
-        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
-        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
-          g.AddProductionRule(ntSymbol, alt);
-        }
-        // local initialization code
-        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
-      }
-      return g;
-    }
-
-    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
-      return (from fieldDef in Util.ExtractParameters(formalParameters)
-              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
-        ToList();
-    }
-
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
-      foreach (var alt in altNode.Alternatives) {
-        yield return GetSequence(alt.Sequence, allSymbols);
-      }
-    }
-
-    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
-      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
-      var l = new List<ISymbol>();
-      foreach (var node in sequence) {
-        var callSymbolNode = node as CallSymbolNode;
-        var actionNode = node as RuleActionNode;
-        if (callSymbolNode != null) {
-          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
-          // create a new symbol with actual parameters
-          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
-        } else if (actionNode != null) {
-          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
-        }
-      }
-      return new Sequence(l);
-    }
-
-    // produces helper methods for the attributes of all terminal nodes
-    private string GenerateConstraintMethods(List<SymbolNode> symbols) {
-      var sb = new StringBuilder();
-      var terminals = symbols.OfType<TerminalNode>();
-      foreach (var t in terminals) {
-        sb.AppendLine(GenerateConstraintMethods(t));
+    public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) {
+      var solverSourceCode = new SourceBuilder();
+      solverSourceCode.Append(solverTemplate)
+        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
+        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
+        .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
+        .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
+        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
+        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
+        .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar))
+      ;
+
+      problemSourceCode.Append(solverSourceCode.ToString());
+    }
+
+    #region same as random search
+    private string GenerateTransitionTable(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+
+      // state idx = idx of the corresponding symbol in the grammar
+      var allSymbols = grammar.Symbols.ToList();
+      var attributes = new List<string>();
+      foreach (var s in grammar.Symbols) {
+        var targetStates = new List<int>();
+        if (grammar.IsTerminal(s)) {
+          foreach (var att in s.Attributes) {
+            targetStates.Add(allSymbols.Count + attributes.Count);
+            attributes.Add(s.Name + "_" + att);
+          }
+        } else {
+          if (grammar.NumberOfAlternatives(s) > 1) {
+            foreach (var alt in grammar.GetAlternatives(s)) {
+              // only single-symbol alternatives are supported
+              Debug.Assert(alt.Count() == 1);
+              targetStates.Add(allSymbols.IndexOf(alt.Single()));
+            }
+          } else {
+            // rule is a sequence of symbols
+            var seq = grammar.GetAlternatives(s).Single();
+            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
+          }
+        }
+
+        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
+
+        var idxOfSourceState = allSymbols.IndexOf(s);
+        sb.AppendFormat("// {0}", s).AppendLine();
+        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
+      }
+      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
+        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
+        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
       }
       return sb.ToString();
     }
-
-    // generates helper methods for the attributes of a given terminal node
-    private string GenerateConstraintMethods(TerminalNode t) {
-      var sb = new StringBuilder();
-      foreach (var c in t.Constraints) {
-        var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
-        if (c.Type == ConstraintNodeType.Range) {
-          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
-          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
-        } else if (c.Type == ConstraintNodeType.Set) {
-          sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-        }
-        sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
+    private string GenerateSubtreeCountTable(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+
+      // state idx = idx of the corresponding symbol in the grammar
+      var allSymbols = grammar.Symbols.ToList();
+      var attributes = new List<string>();
+      foreach (var s in grammar.Symbols) {
+        int subtreeCount;
+        if (grammar.IsTerminal(s)) {
+          subtreeCount = s.Attributes.Count();
+          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
+        } else {
+          if (grammar.NumberOfAlternatives(s) > 1) {
+            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
+            subtreeCount = 1;
+          } else {
+            subtreeCount = grammar.GetAlternative(s, 0).Count();
+          }
+        }
+
+        sb.AppendFormat("// {0}", s).AppendLine();
+        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
+      }
+
+      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
+        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
+        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
       }
       return sb.ToString();
     }
-
-    private string GenerateInterpreterSource(AttributedGrammar grammar) {
-      var sb = new StringBuilder();
-
-
-      // get formal parameters of start symbol
-      var attr = grammar.StartSymbol.Attributes;
-
-      var formalParameter = grammar.StartSymbol.GetAttributeString();
-      // actual parameter are the same as formalparameter only without type identifier
-      string actualParameter;
-      if (attr.Any())
-        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
-      else
-        actualParameter = string.Empty;
-
-      // generate entry method for evaluation. This is called from the min/max function
-      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
-      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
-      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
-      sb.AppendLine("}");
-
-      // generate methods for all nonterminals and terminals using the grammar instance
-      foreach (var s in grammar.NonTerminalSymbols) {
-        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
-      }
-      foreach (var s in grammar.TerminalSymbols) {
-        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
-      }
+    #endregion
+    private string GenerateAlternativesCountMethod(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+      sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock();
+      sb.AppendLine("switch(symbol) {");
+      foreach (var s in grammar.Symbols) {
+        sb.AppendFormat("case \"{0}\":", s.Name).AppendLine();
+        int altCount;
+        if (grammar.IsTerminal(s)) {
+          if (s.Attributes.Any()) {
+            sb.Append("switch(attribute) {").BeginBlock();
+            foreach (var att in s.Attributes) {
+              sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine();
+            }
+            sb.Append("} // switch").EndBlock();
+          } else {
+            sb.AppendLine("return 0;");
+          }
+        } else {
+          sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine();
+        }
+
+
+      }
+      sb.AppendLine("} // switch");
+      sb.Append("}").EndBlock();
       return sb.ToString();
-    }
-
-    private string GenerateTerminalInterpreterMethod(ISymbol s) {
-      var sb = new StringBuilder();
-      // if the terminal symbol has attributes then we must create values for these attributes
-      if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
-      else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
-
-      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
-      // each field must match a formal parameter, assign a value for each parameter
-      int i = 0;
-      foreach (var element in s.Attributes) {
-        // read next symbol
-        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
-        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
-      }
-      sb.AppendLine("}");
-      return sb.ToString();
-    }
-
-    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
-      var sb = new StringBuilder();
-      if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
-      else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
-
-      // generate local definitions
-      sb.AppendLine(g.GetLocalDefinitions(s));
-
-
-
-      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
-      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
-        .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
-
-      if (altsWithSemActions.Length > 1) {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
-
-        int i = 0;
-        sb.AppendLine("switch(tree.GetNextAlternative()) {");
-        // generate a case for each alternative
-        foreach (var alt in altsWithSemActions) {
-          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-          sb.AppendLine("SearchTree subtree = null; ");
-
-          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
-          // handling multiple non-terminals here would require a change in the structure of the search tree
-          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
-          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
-          foreach (var altSymb in alt) {
-            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
-            sb.AppendLine(GenerateSourceForAction(altSymb));
-          }
-          i++;
-          sb.AppendLine("break;").AppendLine("}");
-        }
-        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
-      } else {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
-        int j = 0;
-        sb.AppendLine("SearchTree subtree = null; ");
-        foreach (var altSymb in altsWithSemActions.Single()) {
-          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
-          sb.AppendLine(GenerateSourceForAction(altSymb));
-        }
-      }
-      sb.AppendLine("}");
-      return sb.ToString();
-    }
-
-    // helper for generating calls to other symbol methods
-    private string GenerateSourceForAction(ISymbol s) {
-      var action = s as SemanticSymbol;
-      if (action != null) {
-        return action.Code + ";";
-      } else {
-        if (!s.Attributes.Any())
-          return string.Format("{0}(subtree);", s.Name);
-        else
-          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
-      }
     }
   }
Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs	(revision 10334)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs	(revision 10335)
@@ -18,26 +18,24 @@
     private const string problemTemplate = @"
 namespace ?PROBLEMNAME? {
-  public interface IGpdlProblem {
-    int GetCardinality(string terminalSymbol, string attribute);
-  }
+
+  // generic interface for communication from problem interpretation to solver
   public interface ISolverState {
     void Reset();
-    int PeekNextAlternative();
-    void Follow(int idx);
-    void Unwind();
+    int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
+    void Follow(int idx); // next: derive the NT symbol with index=idx;
+    void Unwind(); // finished with deriving the NT symbol
   }
 
-  public sealed class ?IDENT?Problem : IGpdlProblem {
+  public sealed class ?IDENT?Problem {
    
-   private readonly Dictionary<string, Dictionary<string, int>> cardinalities = new Dictionary<string, Dictionary<string, int>>();
    public ?IDENT?Problem() { 
       Initialize();
-
-?CONSTRUCTORSOURCE?
-
     }    
 
     private void Initialize() {
+      // the following is the source code from the INIT section of the problem definition 
+#region INIT section
 ?INITSOURCE?
+#endregion
     }
 
@@ -45,16 +43,21 @@
     public double Evaluate(ISolverState _state) {
       this._state = _state;
+#region objective function (MINIMIZE / MAXIMIZE section)
 ?FITNESSFUNCTION?
-    }
-
+#endregion
+    }
+
+// additional code from the problem definition (CODE section)
+#region additional code
 ?ADDITIONALCODE?
-
+#endregion
+
+#region generated source for interpretation
 ?INTERPRETERSOURCE?
-
+#endregion
+
+#region generated code for the constraints for terminals
 ?CONSTRAINTSSOURCE?
-
-    public int GetCardinality(string terminal, string attribute) {
-      return cardinalities[terminal][attribute];
-    }
+#endregion
   }
 }";
@@ -76,5 +79,4 @@
         .Replace("?IDENT?", ast.Name);
 
-
       // write the source file to disk
       using (var stream = new StreamWriter(ast.Name + ".cs")) {
@@ -88,5 +90,4 @@
         .AppendLine(problemTemplate)
         .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
-        .Replace("?CONSTRUCTORSOURCE?", GenerateConstructorSource(ast))
         .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
         .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
@@ -99,8 +100,11 @@
       var grammar = CreateGrammarFromAst(ast);
       var randomSearchCodeGen = new RandomSearchCodeGen();
-      randomSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, ast.Terminals, solverSourceCode);
+      randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
+      //var bruteForceSearchCodeGen = new BruteForceCodeGen();
+      //bruteForceSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, solverSourceCode);
     }
 
     #region create grammar instance from AST
+    // should be refactored so that we can directly query the AST
     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
 
@@ -131,6 +135,6 @@
     private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
       return (from fieldDef in Util.ExtractParameters(formalParameters)
-              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
-        ToList();
+              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut)))
+              .ToList();
     }
 
@@ -178,36 +182,15 @@
           sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
-          // sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
-          sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ throw new NotSupportedException(\"range constraints for terminals are not supported.\"); }}", fieldType, t.Ident, c.Ident).AppendLine();
+          //sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ _state. }}", fieldType, t.Ident, c.Ident, )
         } else if (c.Type == ConstraintNodeType.Set) {
           sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-          sb.AppendFormat("private readonly {0}[] values_{1}_{2};", fieldType, t.Ident, c.Ident).AppendLine();
-          sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return values_{1}_{2}[_state.PeekNextAlternative()]; }}", fieldType, t.Ident, c.Ident).AppendLine();
-        }
-      }
-    }
-    private string GenerateConstructorSource(GPDefNode ast) {
-      var sb = new SourceBuilder();
-      // generate code to initialize the tables for terminals
-      foreach (var t in ast.Terminals.OfType<TerminalNode>()) {
-        if (t.Constraints.Any()) {
-          foreach (var constraint in t.Constraints) {
-            sb.AppendFormat("values_{0}_{1} = GetAllowed{0}_{1}().ToArray();", t.Ident, constraint.Ident);
-          }
-          sb.AppendFormat("cardinalities[\"{0}\"] = new Dictionary<string, int>() {{ ", t.Ident);
-          foreach (var constraint in t.Constraints) {
-            sb.AppendFormat("{{ \"{1}\", values_{0}_{1}.Length }}, ", t.Ident, constraint.Ident);
-          }
-          sb.Append("};").AppendLine();
-        }
-      }
-      return sb.ToString();
-    }
-
-
+        }
+      }
+    }
     #endregion
 
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
       var sb = new SourceBuilder();
+      GenerateInterpreterStart(grammar, sb);
 
       // generate methods for all nonterminals and terminals using the grammar instance
@@ -221,26 +204,27 @@
     }
 
+    private void GenerateInterpreterStart(AttributedGrammar grammar, SourceBuilder sb) {
+      var s = grammar.StartSymbol;
+      // create the method which can be called from the fitness function
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
+      else
+        sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+
+      // get formal parameters of start symbol
+      var attr = s.Attributes;
+
+      // actual parameter are the same as formalparameter only without type identifier
+      string actualParameter;
+      if (attr.Any())
+        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
+      else
+        actualParameter = string.Empty;
+      sb.AppendLine("_state.Reset();");
+      sb.AppendFormat("{0}(_state, {1});", s.Name, actualParameter).AppendLine();
+      sb.AppendLine("}").EndBlock();
+    }
+
     private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
-      // if this is the start symbol we additionally have to create the method which can be called from the fitness function
-      if (g.StartSymbol.Equals(s)) {
-        if (!s.Attributes.Any())
-          sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
-        else
-          sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
-
-        // get formal parameters of start symbol
-        var attr = g.StartSymbol.Attributes;
-
-        // actual parameter are the same as formalparameter only without type identifier
-        string actualParameter;
-        if (attr.Any())
-          actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
-        else
-          actualParameter = string.Empty;
-        sb.AppendLine("_state.Reset();");
-        sb.AppendFormat("{0}(_state, {1});", g.StartSymbol.Name, actualParameter).AppendLine();
-        sb.AppendLine("}").EndBlock();
-      }
-
       if (!s.Attributes.Any())
         sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
@@ -272,5 +256,5 @@
         sb.AppendFormat("case {0}: {{ ", i).BeginBlock();
 
-        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
+        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols)!
         // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
         Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
@@ -295,5 +279,5 @@
     }
 
-    private string GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
+    private void GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
       // if the terminal symbol has attributes then we must samples values for these attributes
       if (!s.Attributes.Any())
@@ -310,5 +294,4 @@
       }
       sb.Append("}").EndBlock();
-      return sb.ToString();
     }
   }
Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs	(revision 10334)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs	(revision 10335)
@@ -3,4 +3,5 @@
 using System.Diagnostics;
 using System.Linq;
+using System.Text;
 using HeuristicLab.Grammars;
 
@@ -13,4 +14,14 @@
     private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
     private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
+
+    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
+?TRANSITIONTABLE?
+    };
+    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
+       { -1, 0 }, // terminals
+?SUBTREECOUNTTABLE?
+    };
+    private static string[] symb = new string[] { ?SYMBOLNAMES? };
+
     
     public sealed class SolverState : ISolverState {
@@ -24,20 +35,14 @@
         }
       }
+
+      ?TERMINALNODEDEFINITIONS?
+
       public int curDepth;
       public int steps;
       public int depth;
       private readonly Stack<Tree> nodes;
-      private readonly IGpdlProblem problem;
-
-      private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
-?TRANSITIONTABLE?
-      };
-      private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
-         { -1, 0 }, // terminals
-?SUBTREECOUNTTABLE?
-      };
-      private static string[] symb = new string[] { ?SYMBOLNAMES? };
-
-      public SolverState(IGpdlProblem problem, int seed) {
+      private readonly ?IDENT?Problem problem;
+
+      public SolverState(?IDENT?Problem problem, int seed) {
         this.problem = problem;
         this.nodes = new Stack<Tree>();
@@ -59,4 +64,5 @@
         depth = Math.Max(depth, curDepth);
         var t = new Tree(state, altIdx);
+
         // t.symbol = symb.Length > state ? symb[state] : ""TERM"";
         // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
@@ -173,6 +179,4 @@
         sumF += f;
         if (IsBetter(f, bestF)) {
-          // evaluate again with tracing to console
-          // problem.Evaluate(new SolverState(_state.seed, true));
           bestF = f;
           Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
@@ -196,7 +200,10 @@
 }";
 
-    public void Generate(IGrammar grammar, bool maximization, IEnumerable<SymbolNode> terminalSymbols, SourceBuilder problemSourceCode) {
+    public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
       var solverSourceCode = new SourceBuilder();
       solverSourceCode.Append(solverTemplate)
+        // .Replace("?TERMINALFIELDS?", GenerateTerminalFields(grammar))
+        .Replace("?TERMINALNODEDEFINITIONS?", GenerateTerminalNodeDefinitions(terminals))
+        // .Replace("?CONSTRUCTORCODE?", GenerateConstructorCode(grammar))
         .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
         .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
@@ -204,4 +211,5 @@
         .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
         .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
+//        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
       ;
 
@@ -209,4 +217,51 @@
     }
 
+    private string GenerateTerminalNodeDefinitions(IEnumerable<TerminalNode> terminals) {
+      var sb = new SourceBuilder();
+
+      foreach (var terminal in terminals) {
+        GenerateTerminalNodeDefinitions(terminal, sb);
+      }
+      return sb.ToString();
+    }
+
+    private void GenerateTerminalNodeDefinitions(TerminalNode terminal, SourceBuilder sb) {
+      sb.AppendFormat("private class {0}Tree {{", terminal.Ident).BeginBlock();
+      foreach (var att in terminal.FieldDefinitions) {
+        sb.AppendFormat("{0} {1};", att.Type, att.Identifier).AppendLine();
+      }
+      sb.AppendFormat(" static {0}Tree Create(Random random, ?IDENT?Problem problem) {{", terminal.Ident).BeginBlock();
+      sb.AppendFormat("var t = new {0}Tree();", terminal.Ident);
+      foreach (var constr in terminal.Constraints) {
+        if (constr.Type == ConstraintNodeType.Set) {
+          sb.AppendLine("{").BeginBlock();
+          sb.AppendFormat(" var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident);
+          sb.AppendFormat("t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).AppendLine();
+          sb.AppendLine("}").EndBlock();
+        } else {
+          sb.AppendLine("{").BeginBlock();
+          sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident);
+          sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident);
+          sb.AppendFormat("t.{0} = random.NextDouble() * (max - min) + min ", constr.Ident).AppendLine();
+          sb.AppendLine("}").EndBlock();
+        }
+      }
+      sb.AppendLine("return t;");
+      sb.AppendLine("}").EndBlock();
+      sb.AppendLine("}").EndBlock();
+    }
+
+    //private string GenerateSampleTerminalSource(IGrammar grammar) {
+    //  StringBuilder sb = new StringBuilder();
+    //  foreach (var t in grammar.TerminalSymbols) {
+    //    sb.AppendFormat("public void {0}(ISolverState _state, {1}) {{", t.Name, t.GetAttributeString()).AppendLine();
+    //    foreach (var att in t.Attributes) {
+    //      // need constraints
+    //      sb.AppendFormat("{0}", att.Name);
+    //    }
+    //    sb.AppendLine("}");
+    //  }
+    //  return sb.ToString();
+    //}
 
 
@@ -287,10 +342,8 @@
       var sb = new SourceBuilder();
       int stateCount = 0;
-      var attributes = new List<Tuple<string, string>>();
       foreach (var s in grammar.Symbols) {
         sb.AppendFormat("case {0}: ", stateCount++);
         if (grammar.IsTerminal(s)) {
-          GenerateReturnStatement(s.Attributes.Count(), sb);
-          attributes.AddRange(s.Attributes.Select(att => Tuple.Create(s.Name, att.Name)));
+          // ignore
         } else {
           var terminalAltIndexes = grammar.GetAlternatives(s)
@@ -315,9 +368,4 @@
         }
       }
-      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
-        var terminalName = attributes[attIdx].Item1;
-        var attributeName = attributes[attIdx].Item2;
-        sb.AppendFormat("case {0}: return random.Next(problem.GetCardinality(\"{1}\", \"{2}\"));", attIdx + stateCount, terminalName, attributeName).AppendLine();
-      }
       return sb.ToString();
     }
Index: /branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj	(revision 10334)
+++ /branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj	(revision 10335)
@@ -7,5 +7,5 @@
     <SchemaVersion>2.0</SchemaVersion>
     <ProjectGuid>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</ProjectGuid>
-    <OutputType>Exe</OutputType>
+    <OutputType>Library</OutputType>
     <AppDesignerFolder>Properties</AppDesignerFolder>
     <RootNamespace>HeuristicLab.Grammars</RootNamespace>
@@ -107,7 +107,5 @@
     <Compile Include="SemanticSymbol.cs" />
     <Compile Include="Sequence.cs" />
-    <Compile Include="Test.cs" />
     <Compile Include="Symbol.cs" />
-    <Compile Include="Language.cs" />
     <Compile Include="Grammar.cs" />
     <Compile Include="Interfaces\IAttribute.cs" />
