source: branches/ExperimentalFunctionsBaking/BakedFunctionTree.cs @ 203

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Core;
using HeuristicLab.DataAnalysis;
using HeuristicLab.Data;

namespace HeuristicLab.Functions {
  class BakedFunctionTree : ItemBase, IFunctionTree {
    private List<double> code;
    private static double nextFunctionSymbol = 10000;
    private static Dictionary<double, IFunction> symbolTable = new Dictionary<double, IFunction>();
    private static Dictionary<IFunction, double> reverseSymbolTable = new Dictionary<IFunction, double>();
    private static double additionSymbol = -1;
    private static double substractionSymbol = -1;
    private static double multiplicationSymbol = -1;
    private static double divisionSymbol = -1;
    private static double variableSymbol = -1;
    private static double constantSymbol = -1;

    internal BakedFunctionTree() {
      code = new List<double>();
    }

    internal BakedFunctionTree(IFunction function) : this() {
      code.Add(0);
      code.Add(MapFunction(function));
      code.Add(0);
      treesExpanded = true;
      subTrees = new List<IFunctionTree>();
      variables = new List<IVariable>();
      variablesExpanded = true;
      foreach(IVariableInfo variableInfo in function.VariableInfos) {
        if(variableInfo.Local) {
          variables.Add((IVariable)function.GetVariable(variableInfo.FormalName).Clone());
        }
      }
    }

    internal BakedFunctionTree(IFunctionTree tree) : this() {
      code.Add(0);
      code.Add(MapFunction(tree.Function));
      code.Add((byte)tree.LocalVariables.Count);
      foreach(IVariable variable in tree.LocalVariables) {
        IItem value = variable.Value;
        code.Add(GetDoubleValue(value));
      }
      foreach(IFunctionTree subTree in tree.SubTrees) {
        AddSubTree(new BakedFunctionTree(subTree));
      }
    }

    private double GetDoubleValue(IItem value) {
      if(value is DoubleData) {
        return ((DoubleData)value).Data;
      } else if(value is ConstrainedDoubleData) {
        return ((ConstrainedDoubleData)value).Data;
      } else if(value is IntData) {
        return ((IntData)value).Data;
      } else if(value is ConstrainedIntData) {
        return ((ConstrainedIntData)value).Data;
      } else throw new NotSupportedException("Invalid datatype of local variable for GP");
    }

    private double MapFunction(IFunction function) {
      if(!reverseSymbolTable.ContainsKey(function)) {
        reverseSymbolTable[function] = nextFunctionSymbol;
        symbolTable[nextFunctionSymbol] = function;
        if(function is Variable) {
          variableSymbol = nextFunctionSymbol;
        } else if(function is Constant) {
          constantSymbol = nextFunctionSymbol;
        } else if(function is Addition) {
          additionSymbol = nextFunctionSymbol;
        } else if(function is Substraction) {
          substractionSymbol = nextFunctionSymbol;
        } else if(function is Multiplication) {
          multiplicationSymbol = nextFunctionSymbol;
        } else if(function is Division) {
          divisionSymbol = nextFunctionSymbol;
        } else throw new NotSupportedException("Unsupported function " + function);

        nextFunctionSymbol++;
      }
      return reverseSymbolTable[function];
    }

    private int BranchLength(int branchRoot) {
      double arity = code[branchRoot];
      int nLocalVariables = (int)code[branchRoot + 2];
      int len = 3 + nLocalVariables;
      int subBranchStart = branchRoot + len;
      for(int i = 0; i < arity; i++) {
        int branchLen = BranchLength(subBranchStart);
        len += branchLen;
        subBranchStart += branchLen;
      }
      return len;
    }

    private void FlattenTrees() {
      if(treesExpanded) {
        code[0] = subTrees.Count;
        foreach(BakedFunctionTree subTree in subTrees) {
          subTree.FlattenVariables();
          subTree.FlattenTrees();
          code.AddRange(subTree.code);
        }
        treesExpanded = false;
        subTrees.Clear();
      }
    }

    private void FlattenVariables() {
      if(variablesExpanded) {
        code[2] = variables.Count;
        int localVariableIndex = 3;
        foreach(IVariable variable in variables) {
          code.Insert(localVariableIndex, GetDoubleValue(variable.Value));
          localVariableIndex++;
        }
        variablesExpanded = false;
        variables.Clear();
      }
    }

    private bool treesExpanded = false;
    private List<IFunctionTree> subTrees;
    public IList<IFunctionTree> SubTrees {
      get {
        if(!treesExpanded) {
          subTrees = new List<IFunctionTree>();
          double arity = code[0];
          int nLocalVariables = (int)code[2];
          int branchIndex = 3 + nLocalVariables;
          for(int i = 0; i < arity; i++) {
            BakedFunctionTree subTree = new BakedFunctionTree();
            int branchLen = BranchLength(branchIndex);
            subTree.code = code.GetRange(branchIndex, branchLen);
            branchIndex += branchLen;
            subTrees.Add(subTree);
          }
          treesExpanded = true;
          code.RemoveRange(3 + nLocalVariables, code.Count - (3 + nLocalVariables));
          code[0] = 0;
        }
        return subTrees;
      }
    }

    private bool variablesExpanded = false;
    private List<IVariable> variables;
    public ICollection<IVariable> LocalVariables {
      get {
        if(!variablesExpanded) {
          variables = new List<IVariable>();
          IFunction function = symbolTable[code[1]];
          int localVariableIndex = 3;
          foreach(IVariableInfo variableInfo in function.VariableInfos) {
            if(variableInfo.Local) {
              IVariable clone = (IVariable)function.GetVariable(variableInfo.FormalName).Clone();
              IItem value = clone.Value;
              if(value is ConstrainedDoubleData) {
                ((ConstrainedDoubleData)value).Data = code[localVariableIndex];
              } else if(value is ConstrainedIntData) {
                ((ConstrainedIntData)value).Data = (int)code[localVariableIndex];
              } else if(value is DoubleData) {
                ((DoubleData)value).Data = code[localVariableIndex];
              } else if(value is IntData) {
                ((IntData)value).Data = (int)code[localVariableIndex];
              } else throw new NotSupportedException("Invalid local variable type for GP.");
              variables.Add(clone);
              localVariableIndex++;
            }
          }
          variablesExpanded = true;
          code[2] = 0;
          code.RemoveRange(3, variables.Count); 
        }
        return variables;
      }
    }

    public IFunction Function {
      get { return symbolTable[code[1]]; }
    }

    public IVariable GetLocalVariable(string name) {
      throw new NotImplementedException();
    }

    public void AddVariable(IVariable variable) {
      throw new NotImplementedException();
    }

    public void RemoveVariable(string name) {
      throw new NotImplementedException();
    }

    public void AddSubTree(IFunctionTree tree) {
      if(treesExpanded) {
        subTrees.Add(tree);
      } else {
        //code.AddRange(((BakedFunctionTree)tree).code);
        //code[0] = code[0] + 1;
        throw new NotImplementedException();
      }
    }

    public void InsertSubTree(int index, IFunctionTree tree) {
      if(treesExpanded) {
        subTrees.Insert(index, tree);
      } else {
        //byte nLocalVariables = code[2];
        //// skip branches
        //int currentBranchIndex = 3 + nLocalVariables;
        //for(int i = 0; i < index; i++) {
        //  int branchLength = BranchLength(currentBranchIndex);
        //  currentBranchIndex += branchLength;
        //}
        
        //code.InsertRange(currentBranchIndex, ((BakedFunctionTree)tree).code);
        //code[0] = code[0] + 1;

        throw new NotImplementedException();
      }
    }

    public void RemoveSubTree(int index) {
      if(treesExpanded) {
        subTrees.RemoveAt(index);
      } else {
        //int nLocalVariables = (int)code[2];
        //// skip branches
        //int currentBranchIndex = 3 + nLocalVariables;
        //for(int i = 0; i < index; i++) {
        //  int branchLength = BranchLength(currentBranchIndex);
        //  currentBranchIndex += branchLength;
        //}
        //int deletedBranchLength = BranchLength(currentBranchIndex);
        //code.RemoveRange(currentBranchIndex, deletedBranchLength);
        //code[0] = code[0] - 1;
        throw new NotImplementedException();
      }
    }

    private int PC;
    public double Evaluate(Dataset dataset, int sampleIndex) {
      PC = 0;
      FlattenVariables();
      FlattenTrees();
      return EvaluateBakedCode(dataset, sampleIndex);
    }

    private double EvaluateBakedCode(Dataset dataset, int sampleIndex) {
      double arity = code[PC++];
      double functionSymbol = code[PC++];
      double nLocalVariables = code[PC++];
      if(functionSymbol == variableSymbol) {
        int var = (int)code[PC++];
        double weight = code[PC++];
        int offset = (int)code[PC++];
        return weight * dataset.GetValue(sampleIndex+offset, var);
      } else if(functionSymbol == constantSymbol) {
        double value = code[PC++];
        return value;
      } else if(functionSymbol == additionSymbol) {
        double sum = 0.0;
        for(int i = 0; i < arity; i++) {
          sum += EvaluateBakedCode(dataset, sampleIndex);
        }
        return sum;
      } else if(functionSymbol == substractionSymbol) {
        if(arity == 1) {
          return -EvaluateBakedCode(dataset, sampleIndex);
        } else {
          double result = EvaluateBakedCode(dataset, sampleIndex);
          for(int i = 1; i < arity; i++) {
            result -= EvaluateBakedCode(dataset, sampleIndex);
          }
          return result;
        }
      } else if(functionSymbol == multiplicationSymbol) {
        double result = 1.0;
        for(int i = 0; i < arity; i++) {
          result *= EvaluateBakedCode(dataset, sampleIndex);
        }
        return result;
      } else if(functionSymbol == divisionSymbol) {
        if(arity == 1) {
          double divisor = EvaluateBakedCode(dataset, sampleIndex);
          if(divisor == 0) return 0;
          else return 1.0 / divisor;
        } else {
          double result = EvaluateBakedCode(dataset, sampleIndex);
          for(int i = 1; i < arity; i++) {
            double divisor = EvaluateBakedCode(dataset, sampleIndex);
            if(divisor == 0) result = 0; 
            else result /= divisor;
          }
          return result;
        }
      } else { throw new NotSupportedException(); }
    }

    public override System.Xml.XmlNode GetXmlNode(string name, System.Xml.XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
      throw new NotImplementedException();
    }

    public override void Populate(System.Xml.XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
      throw new NotImplementedException();
    }

    public override object Clone(IDictionary<Guid, object> clonedObjects) {
      BakedFunctionTree clone = new BakedFunctionTree();
      if(treesExpanded || variablesExpanded) throw new InvalidOperationException();
      //if(treesExpanded) FlattenTrees();
      //if(variablesExpanded) FlattenVariables();
      clone.code = new List<double>(code);
      return clone;
    }
  }
}