Index: branches/BottomUpTreeEvaluation/BakedTreeEvaluator.cs
===================================================================
--- branches/BottomUpTreeEvaluation/BakedTreeEvaluator.cs	(revision 326)
+++ branches/BottomUpTreeEvaluation/BakedTreeEvaluator.cs	(revision 327)
@@ -31,5 +31,5 @@
   internal static class BakedTreeEvaluator {
     private const int MAX_TREE_SIZE = 4096;
-
+    private const int MAX_TREE_DEPTH = 20;
     private class Instr {
       public double d_arg0;
@@ -40,6 +40,6 @@
     }
 
-    private static Instr[] codeArr;
-    private static int PC;
+    private static int[] nInstr;
+    private static Instr[,] evaluationTable;
     private static Dataset dataset;
     private static int sampleIndex;
@@ -47,18 +47,30 @@
 
     static BakedTreeEvaluator() {
-      codeArr = new Instr[MAX_TREE_SIZE];
-      for(int i = 0; i < MAX_TREE_SIZE; i++) {
-        codeArr[i] = new Instr();
+      evaluationTable = new Instr[MAX_TREE_SIZE, MAX_TREE_DEPTH];
+      nInstr = new int[MAX_TREE_DEPTH];
+      for(int j = 0; j < MAX_TREE_DEPTH; j++) {
+        for(int i = 0; i < MAX_TREE_SIZE; i++) {
+          evaluationTable[i, j] = new Instr();
+        }
       }
     }
 
     public static void ResetEvaluator(List<LightWeightFunction> linearRepresentation) {
-      int i = 0;
-      foreach(LightWeightFunction f in linearRepresentation) {
-        TranslateToInstr(f, codeArr[i++]);
-      }
-    }
-
-    private static Instr TranslateToInstr(LightWeightFunction f, Instr instr) {
+      int length;
+      for(int i = 0; i < MAX_TREE_DEPTH; i++) nInstr[i] = 0;
+      TranslateToInstr(0, linearRepresentation, out length);
+    }
+
+    private static int TranslateToInstr(int pos, List<LightWeightFunction> linearRepresentation, out int branchLength) {
+      int height = 0;
+      int length = 1;
+      LightWeightFunction f = linearRepresentation[pos];
+      for(int i = 0; i < f.arity; i++) {
+        int curBranchLength;
+        int curBranchHeight = TranslateToInstr(pos + length, linearRepresentation, out curBranchLength);
+        if(curBranchHeight > height) height = curBranchHeight;
+        length += curBranchLength;
+      }
+      Instr instr = evaluationTable[nInstr[height], height];
       instr.arity = f.arity;
       instr.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
@@ -75,162 +87,216 @@
           }
       }
-      return instr;
-    }
+      nInstr[height]++;
+      branchLength = length;
+      return height;
+    }
+
+    //private static Instr TranslateToInstr(LightWeightFunction f, Instr instr) {
+    //  instr.arity = f.arity;
+    //  instr.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
+    //  switch(instr.symbol) {
+    //    case EvaluatorSymbolTable.VARIABLE: {
+    //        instr.i_arg0 = (int)f.data[0]; // var
+    //        instr.d_arg0 = f.data[1]; // weight
+    //        instr.i_arg1 = (int)f.data[2]; // sample-offset
+    //        break;
+    //      }
+    //    case EvaluatorSymbolTable.CONSTANT: {
+    //        instr.d_arg0 = f.data[0]; // value
+    //        break;
+    //      }
+    //  }
+    //  return instr;
+    //}
 
     internal static double Evaluate(Dataset dataset, int sampleIndex) {
-      PC = 0;
       BakedTreeEvaluator.sampleIndex = sampleIndex;
       BakedTreeEvaluator.dataset = dataset;
-      return EvaluateBakedCode();
-    }
-
-    private static double EvaluateBakedCode() {
-      Instr currInstr = codeArr[PC++];
-      switch(currInstr.symbol) {
-        case EvaluatorSymbolTable.VARIABLE: {
-            int row = sampleIndex + currInstr.i_arg1;
-            if(row < 0 || row >= dataset.Rows) return double.NaN;
-            else return currInstr.d_arg0 * dataset.GetValue(row, currInstr.i_arg0);
+      return EvaluateTable();
+    }
+
+    private static double EvaluateTable() {
+      int terminalP = 0;
+      for(; terminalP < nInstr[0]; terminalP += 2) {
+        Instr curInstr0 = evaluationTable[terminalP, 0];
+        Instr curInstr1 = evaluationTable[terminalP + 1, 0];
+        if(curInstr0.symbol == EvaluatorSymbolTable.VARIABLE) {
+          int row = sampleIndex + curInstr0.i_arg1;
+          if(row < 0 || row >= dataset.Rows) curInstr0.d_arg0 = double.NaN;
+          else curInstr0.d_arg0 = curInstr0.d_arg0 * dataset.GetValue(row, curInstr0.i_arg0);
+        }
+        if(curInstr1.symbol == EvaluatorSymbolTable.VARIABLE) {
+          int row = sampleIndex + curInstr1.i_arg1;
+          if(row < 0 || row >= dataset.Rows) curInstr1.d_arg0 = double.NaN;
+          else curInstr1.d_arg0 = curInstr1.d_arg0 * dataset.GetValue(row, curInstr1.i_arg0);
+        }
+      }
+
+      int curLevel = 1;
+      while(nInstr[curLevel] > 0) {
+        int lastLayerInstrP = 0;
+        for(int curLayerInstrP = 0; curLayerInstrP < nInstr[curLevel]; curLayerInstrP++) {
+          Instr curInstr = evaluationTable[curLayerInstrP, curLevel];
+          switch(curInstr.symbol) {
+            case EvaluatorSymbolTable.MULTIPLICATION: {
+                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                for(int i = 1; i < curInstr.arity; i++) {
+                  curInstr.d_arg0 *= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                }
+                lastLayerInstrP += curInstr.arity;
+                break;
+              }
+            case EvaluatorSymbolTable.ADDITION: {
+                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                for(int i = 1; i < curInstr.arity; i++) {
+                  curInstr.d_arg0 += evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                }
+                lastLayerInstrP += curInstr.arity;
+                break;
+              }
+            case EvaluatorSymbolTable.SUBTRACTION: {
+                if(curInstr.arity == 1) {
+                  curInstr.d_arg0 = -evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                } else {
+                  curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                  for(int i = 1; i < curInstr.arity; i++) {
+                    curInstr.d_arg0 -= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                  }
+                  lastLayerInstrP += curInstr.arity;
+                }
+                break;
+              }
+            case EvaluatorSymbolTable.DIVISION: {
+                if(curInstr.arity == 1) {
+                  curInstr.d_arg0 = 1.0 / evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                } else {
+                  curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                  for(int i = 1; i < curInstr.arity; i++) {
+                    curInstr.d_arg0 /= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                  }
+                  lastLayerInstrP += curInstr.arity;
+                }
+                if(double.IsInfinity(curInstr.d_arg0)) curInstr.d_arg0 = 0.0;
+                break;
+              }
+            case EvaluatorSymbolTable.AVERAGE: {
+                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                for(int i = 1; i < curInstr.arity; i++) {
+                  curInstr.d_arg0 += evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                }
+                lastLayerInstrP += curInstr.arity;
+                curInstr.d_arg0 /= curInstr.arity;
+                break;
+              }
+            case EvaluatorSymbolTable.COSINUS: {
+                curInstr.d_arg0 = Math.Cos(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            case EvaluatorSymbolTable.SINUS: {
+                curInstr.d_arg0 = Math.Sin(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            case EvaluatorSymbolTable.EXP: {
+                curInstr.d_arg0 = Math.Exp(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            case EvaluatorSymbolTable.LOG: {
+                curInstr.d_arg0 = Math.Log(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            case EvaluatorSymbolTable.POWER: {
+                double x = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                double p = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                curInstr.d_arg0 = Math.Pow(x, p);
+                break;
+              }
+            case EvaluatorSymbolTable.SIGNUM: {
+                double value = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                if(double.IsNaN(value)) curInstr.d_arg0 = double.NaN;
+                else curInstr.d_arg0 = Math.Sign(value);
+                break;
+              }
+            case EvaluatorSymbolTable.SQRT: {
+                curInstr.d_arg0 = Math.Sqrt(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            case EvaluatorSymbolTable.TANGENS: {
+                curInstr.d_arg0 = Math.Tan(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                break;
+              }
+            //case EvaluatorSymbolTable.AND: {
+            //    double result = 1.0;
+            //    // have to evaluate all sub-trees, skipping would probably not lead to a big gain because 
+            //    // we have to iterate over the linear structure anyway
+            //    for(int i = 0; i < currInstr.arity; i++) {
+            //      double x = Math.Round(EvaluateBakedCode());
+            //      if(x == 0 || x == 1.0) result *= x;
+            //      else result = double.NaN;
+            //    }
+            //    return result;
+            //  }
+            //case EvaluatorSymbolTable.EQU: {
+            //    double x = EvaluateBakedCode();
+            //    double y = EvaluateBakedCode();
+            //    if(x == y) return 1.0; else return 0.0;
+            //  }
+            //case EvaluatorSymbolTable.GT: {
+            //    double x = EvaluateBakedCode();
+            //    double y = EvaluateBakedCode();
+            //    if(x > y) return 1.0;
+            //    else return 0.0;
+            //  }
+            //case EvaluatorSymbolTable.IFTE: {
+            //    double condition = Math.Round(EvaluateBakedCode());
+            //    double x = EvaluateBakedCode();
+            //    double y = EvaluateBakedCode();
+            //    if(condition < .5) return x;
+            //    else if(condition >= .5) return y;
+            //    else return double.NaN;
+            //  }
+            //case EvaluatorSymbolTable.LT: {
+            //    double x = EvaluateBakedCode();
+            //    double y = EvaluateBakedCode();
+            //    if(x < y) return 1.0;
+            //    else return 0.0;
+            //  }
+            //case EvaluatorSymbolTable.NOT: {
+            //    double result = Math.Round(EvaluateBakedCode());
+            //    if(result == 0.0) return 1.0;
+            //    else if(result == 1.0) return 0.0;
+            //    else return double.NaN;
+            //  }
+            //case EvaluatorSymbolTable.OR: {
+            //    double result = 0.0; // default is false
+            //    for(int i = 0; i < currInstr.arity; i++) {
+            //      double x = Math.Round(EvaluateBakedCode());
+            //      if(x == 1.0 && result == 0.0) result = 1.0; // found first true (1.0) => set to true
+            //      else if(x != 0.0) result = double.NaN; // if it was not true it can only be false (0.0) all other cases are undefined => (NaN)
+            //    }
+            //    return result;
+            //  }
+            //case EvaluatorSymbolTable.XOR: {
+            //    double x = Math.Round(EvaluateBakedCode());
+            //    double y = Math.Round(EvaluateBakedCode());
+            //    if(x == 0.0 && y == 0.0) return 0.0;
+            //    if(x == 1.0 && y == 0.0) return 1.0;
+            //    if(x == 0.0 && y == 1.0) return 1.0;
+            //    if(x == 1.0 && y == 1.0) return 0.0;
+            //    return double.NaN;
+            //  }
+            default: {
+                throw new NotImplementedException();
+              }
           }
-        case EvaluatorSymbolTable.CONSTANT: {
-            return currInstr.d_arg0;
-          }
-        case EvaluatorSymbolTable.MULTIPLICATION: {
-            double result = EvaluateBakedCode();
-            for(int i = 1; i < currInstr.arity; i++) {
-              result *= EvaluateBakedCode();
-            }
-            return result;
-          }
-        case EvaluatorSymbolTable.ADDITION: {
-            double sum = EvaluateBakedCode();
-            for(int i = 1; i < currInstr.arity; i++) {
-              sum += EvaluateBakedCode();
-            }
-            return sum;
-          }
-        case EvaluatorSymbolTable.SUBTRACTION: {
-            if(currInstr.arity == 1) {
-              return -EvaluateBakedCode();
-            } else {
-              double result = EvaluateBakedCode();
-              for(int i = 1; i < currInstr.arity; i++) {
-                result -= EvaluateBakedCode();
-              }
-              return result;
-            }
-          }
-        case EvaluatorSymbolTable.DIVISION: {
-            double result;
-            if(currInstr.arity == 1) {
-              result = 1.0 / EvaluateBakedCode();
-            } else {
-              result = EvaluateBakedCode();
-              for(int i = 1; i < currInstr.arity; i++) {
-                result /= EvaluateBakedCode();
-              }
-            }
-            if(double.IsInfinity(result)) return 0.0;
-            else return result;
-          }
-        case EvaluatorSymbolTable.AVERAGE: {
-            double sum = EvaluateBakedCode();
-            for(int i = 1; i < currInstr.arity; i++) {
-              sum += EvaluateBakedCode();
-            }
-            return sum / currInstr.arity;
-          }
-        case EvaluatorSymbolTable.COSINUS: {
-            return Math.Cos(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.SINUS: {
-            return Math.Sin(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.EXP: {
-            return Math.Exp(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.LOG: {
-            return Math.Log(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.POWER: {
-            double x = EvaluateBakedCode();
-            double p = EvaluateBakedCode();
-            return Math.Pow(x, p);
-          }
-        case EvaluatorSymbolTable.SIGNUM: {
-            double value = EvaluateBakedCode();
-            if(double.IsNaN(value)) return double.NaN;
-            else return Math.Sign(value);
-          }
-        case EvaluatorSymbolTable.SQRT: {
-            return Math.Sqrt(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.TANGENS: {
-            return Math.Tan(EvaluateBakedCode());
-          }
-        case EvaluatorSymbolTable.AND: {
-            double result = 1.0;
-            // have to evaluate all sub-trees, skipping would probably not lead to a big gain because 
-            // we have to iterate over the linear structure anyway
-            for(int i = 0; i < currInstr.arity; i++) {
-              double x = Math.Round(EvaluateBakedCode());
-              if(x == 0 || x == 1.0) result *= x;
-              else result = double.NaN;
-            }
-            return result;
-          }
-        case EvaluatorSymbolTable.EQU: {
-            double x = EvaluateBakedCode();
-            double y = EvaluateBakedCode();
-            if(x == y) return 1.0; else return 0.0;
-          }
-        case EvaluatorSymbolTable.GT: {
-            double x = EvaluateBakedCode();
-            double y = EvaluateBakedCode();
-            if(x > y) return 1.0;
-            else return 0.0;
-          }
-        case EvaluatorSymbolTable.IFTE: {
-            double condition = Math.Round(EvaluateBakedCode());
-            double x = EvaluateBakedCode();
-            double y = EvaluateBakedCode();
-            if(condition < .5) return x;
-            else if(condition >= .5) return y;
-            else return double.NaN;
-          }
-        case EvaluatorSymbolTable.LT: {
-            double x = EvaluateBakedCode();
-            double y = EvaluateBakedCode();
-            if(x < y) return 1.0;
-            else return 0.0;
-          }
-        case EvaluatorSymbolTable.NOT: {
-            double result = Math.Round(EvaluateBakedCode());
-            if(result == 0.0) return 1.0;
-            else if(result == 1.0) return 0.0;
-            else return double.NaN;
-          }
-        case EvaluatorSymbolTable.OR: {
-            double result = 0.0; // default is false
-            for(int i = 0; i < currInstr.arity; i++) {
-              double x = Math.Round(EvaluateBakedCode());
-              if(x == 1.0 && result == 0.0) result = 1.0; // found first true (1.0) => set to true
-              else if(x != 0.0) result = double.NaN; // if it was not true it can only be false (0.0) all other cases are undefined => (NaN)
-            }
-            return result;
-          }
-        case EvaluatorSymbolTable.XOR: {
-            double x = Math.Round(EvaluateBakedCode());
-            double y = Math.Round(EvaluateBakedCode());
-            if(x == 0.0 && y == 0.0) return 0.0;
-            if(x == 1.0 && y == 0.0) return 1.0;
-            if(x == 0.0 && y == 1.0) return 1.0;
-            if(x == 1.0 && y == 1.0) return 0.0;
-            return double.NaN;
-          }
-        default: {
-            throw new NotImplementedException();
-          }
-      }
+        }
+        // copy remaining results from previous layer to current layer (identiy function)
+        int r = 0;
+        for(; lastLayerInstrP < nInstr[curLevel - 1]; lastLayerInstrP++) {
+          evaluationTable[nInstr[curLevel] + r, curLevel].d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+          r++;
+        }
+        curLevel++;
+      }
+      return evaluationTable[0, curLevel - 1].d_arg0;
     }
   }
