source: branches/2895_PushGP_GenealogyAnalysis/HeuristicLab.Problems.ProgramSynthesis/Push/Data/Tree/TreeExtensions.cs @ 17709

using System;
using System.Collections.Generic;

namespace HeuristicLab.Problems.ProgramSynthesis {
  using System.Linq;

  public static class TreeExtensions {
    private static readonly Expression ExecNoop = ExpressionTable.GetStatelessExpression<ExecNoopExpression>();
    private static readonly Expression CodeNoop = ExpressionTable.GetStatelessExpression<CodeNoopExpression>();

    public static TreeNode<T> ToTree<T>(
      this IEnumerable<T> items,
      Predicate<T> isChild,
      Func<T, IReadOnlyList<T>> childrenResolver) {
      var tree = new TreeNode<T>();

      foreach (var item in items) {
        if (isChild(item)) {
          var subNode = childrenResolver(item).ToTree(isChild, childrenResolver);
          subNode.Value = item;
          tree.AddNode(subNode);
        } else {
          tree.Add(item);
        }
      }

      return tree;
    }

    public static IEnumerable<TreeNode<T>> DepthLast<T>(this TreeNode<T> node) {
      foreach (var child in node.Children) {
        if (child.Children.Count > 0) {
          foreach (var subChild in child.DepthLast()) {
            yield return subChild;
          }
        } else yield return child;
      }

      yield return node;
    }

    public static IEnumerable<T> DepthLast<T>(this TreeNode<T> node, Func<IEnumerable<T>, T> resolveParent) {
      foreach (var child in node.Children) {
        if (child.Children.Count > 0) {
          var subExpressions = child.DepthLast(resolveParent);
          yield return resolveParent(subExpressions);
        } else yield return child.Value;
      }
    }

    public static PushProgram ToPushProgramWithoutNoopExpressions(this TreeNode<Expression> tree) {
      return ToPushProgram(tree, e => !ReferenceEquals(e, ExecNoop) && !ReferenceEquals(e, CodeNoop));
    }

    public static PushProgram ToPushProgram(this TreeNode<Expression> tree, Func<Expression, bool> condition = null) {
      // wrap into program as depthlast expects that tree represents program and not a single expression
      if (tree.Count == 1) {
        var tmp = tree;
        tree = new TreeNode<Expression>();
        tree.AddNode(tmp);
      }

      var expressions = tree.DepthLast(e => ResolveProgram(e, condition));

      return ResolveProgram(expressions, condition);
    }

    public static TreeNode<Expression> ToTree(this PushProgram program) {
      var tree = program.Expressions.ToTree(e => e.IsProgram, e => ((PushProgram)e).Expressions);
      tree.Value = program;

      return tree;
    }

    private static PushProgram ResolveProgram(IEnumerable<Expression> expressions, Func<Expression, bool> condition = null) {

      if (condition != null) {
        expressions = expressions.Where(condition);
      }

      return new PushProgram(expressions.ToList());
    }
  }

}