#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 .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Core;
using HeuristicLab.DataAnalysis;
using HeuristicLab.Data;
using System.Xml;
using System.Globalization;
namespace HeuristicLab.Functions {
class BakedFunctionTree : ItemBase, IFunctionTree {
private List code;
private List data;
private static EvaluatorSymbolTable symbolTable = EvaluatorSymbolTable.SymbolTable;
public BakedFunctionTree() {
code = new List();
data = new List();
}
internal BakedFunctionTree(IFunction function)
: this() {
code.Add(0);
code.Add(symbolTable.MapFunction(function));
code.Add(0);
treesExpanded = true;
subTrees = new List();
variables = new List();
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(symbolTable.MapFunction(tree.Function));
code.Add(tree.LocalVariables.Count);
foreach(IVariable variable in tree.LocalVariables) {
IItem value = variable.Value;
data.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 void BranchLength(int branchRoot, out int codeLength, out int dataLength) {
int arity = code[branchRoot];
int nLocalVariables = code[branchRoot + 2];
codeLength = 3;
dataLength = nLocalVariables;
int subBranchStart = branchRoot + codeLength;
for(int i = 0; i < arity; i++) {
int branchCodeLength;
int branchDataLength;
BranchLength(subBranchStart, out branchCodeLength, out branchDataLength);
subBranchStart += branchCodeLength;
codeLength += branchCodeLength;
dataLength += branchDataLength;
}
}
private void FlattenTrees() {
if(treesExpanded) {
code[0] = subTrees.Count;
foreach(BakedFunctionTree subTree in subTrees) {
subTree.FlattenVariables();
subTree.FlattenTrees();
code.AddRange(subTree.code);
data.AddRange(subTree.data);
}
treesExpanded = false;
subTrees = null;
}
}
private void FlattenVariables() {
if(variablesExpanded) {
code[2] = variables.Count;
foreach(IVariable variable in variables) {
data.Add(GetDoubleValue(variable.Value));
}
variablesExpanded = false;
variables = null;
}
}
private bool treesExpanded = false;
private List subTrees;
public IList SubTrees {
get {
if(!treesExpanded) {
subTrees = new List();
int arity = code[0];
int nLocalVariables = code[2];
int branchIndex = 3;
int dataIndex = nLocalVariables; // skip my local variables to reach the local variables of the first branch
for(int i = 0; i < arity; i++) {
BakedFunctionTree subTree = new BakedFunctionTree();
int codeLength;
int dataLength;
BranchLength(branchIndex, out codeLength, out dataLength);
subTree.code = code.GetRange(branchIndex, codeLength);
subTree.data = data.GetRange(dataIndex, dataLength);
branchIndex += codeLength;
dataIndex += dataLength;
subTrees.Add(subTree);
}
treesExpanded = true;
code.RemoveRange(3, code.Count - 3);
code[0] = 0;
data.RemoveRange(nLocalVariables, data.Count - nLocalVariables);
}
return subTrees;
}
}
private bool variablesExpanded = false;
private List variables;
public ICollection LocalVariables {
get {
if(!variablesExpanded) {
variables = new List();
IFunction function = symbolTable.MapSymbol(code[1]);
int localVariableIndex = 0;
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 = data[localVariableIndex];
} else if(value is ConstrainedIntData) {
((ConstrainedIntData)value).Data = (int)data[localVariableIndex];
} else if(value is DoubleData) {
((DoubleData)value).Data = data[localVariableIndex];
} else if(value is IntData) {
((IntData)value).Data = (int)data[localVariableIndex];
} else throw new NotSupportedException("Invalid local variable type for GP.");
variables.Add(clone);
localVariableIndex++;
}
}
variablesExpanded = true;
code[2] = 0;
data.RemoveRange(0, variables.Count);
}
return variables;
}
}
public IFunction Function {
get { return symbolTable.MapSymbol(code[1]); }
}
public IVariable GetLocalVariable(string name) {
foreach(IVariable var in LocalVariables) {
if(var.Name == name) return var;
}
return null;
}
public void AddVariable(IVariable variable) {
throw new NotSupportedException();
}
public void RemoveVariable(string name) {
throw new NotSupportedException();
}
public void AddSubTree(IFunctionTree tree) {
if(!treesExpanded) throw new InvalidOperationException();
subTrees.Add(tree);
}
public void InsertSubTree(int index, IFunctionTree tree) {
if(!treesExpanded) throw new InvalidOperationException();
subTrees.Insert(index, tree);
}
public void RemoveSubTree(int index) {
// sanity check
if(!treesExpanded) throw new InvalidOperationException();
subTrees.RemoveAt(index);
}
private BakedTreeEvaluator evaluator = null;
public double Evaluate(Dataset dataset, int sampleIndex) {
FlattenVariables();
FlattenTrees();
if(evaluator == null) evaluator = new BakedTreeEvaluator(code, data);
return evaluator.Evaluate(dataset, sampleIndex);
}
public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary persistedObjects) {
FlattenVariables();
FlattenTrees();
XmlNode node = base.GetXmlNode(name, document, persistedObjects);
if(evaluator != null) {
XmlNode evaluatorNode = PersistenceManager.Persist("Evaluator", evaluator, document, persistedObjects);
node.AppendChild(evaluatorNode);
}
XmlAttribute codeAttribute = document.CreateAttribute("Code");
codeAttribute.Value = GetString(code);
node.Attributes.Append(codeAttribute);
XmlAttribute dataAttribute = document.CreateAttribute("Data");
dataAttribute.Value = GetString(data);
node.Attributes.Append(dataAttribute);
return node;
}
public override void Populate(XmlNode node, IDictionary restoredObjects) {
base.Populate(node, restoredObjects);
XmlNode evaluatorNode = node.SelectSingleNode("Evaluator");
if(evaluatorNode != null) {
this.evaluator = (BakedTreeEvaluator)PersistenceManager.Restore(evaluatorNode, restoredObjects);
}
code = GetList(node.Attributes["Code"].Value, s => int.Parse(s, CultureInfo.InvariantCulture));
data = GetList(node.Attributes["Data"].Value, s => double.Parse(s, CultureInfo.InvariantCulture));
treesExpanded = false;
variablesExpanded = false;
}
private string GetString(IEnumerable xs) where T : IConvertible {
StringBuilder builder = new StringBuilder();
foreach(T x in xs) {
builder.Append(x.ToString(CultureInfo.InvariantCulture) + "; ");
}
if(builder.Length > 0) builder.Remove(builder.Length - 2, 2);
return builder.ToString();
}
private List GetList(string s, Converter converter) {
List result = new List();
string[] tokens = s.Split(new char[] {';',' '}, StringSplitOptions.RemoveEmptyEntries);
foreach(string token in tokens) {
T x = converter(token.Trim());
result.Add(x);
}
return result;
}
public override object Clone(IDictionary clonedObjects) {
BakedFunctionTree clone = new BakedFunctionTree();
// in case the user (de)serialized the tree between evaluation and selection we have to flatten the tree again.
if(treesExpanded) FlattenTrees();
if(variablesExpanded) FlattenVariables();
clone.code.AddRange(code);
clone.data.AddRange(data);
return clone;
}
public override IView CreateView() {
return new FunctionTreeView(this);
}
}
}