source: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs @ 12909

using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
  internal class SearchTree {
    private class Node {
      internal Node parent;
      internal Node[] children;
      // children == null -> never visited
      // children[i] != null -> visited at least once, still allowed
      // children[i] = null -> fully explored
    }

    private Node root;

    // for iteration
    private Node currentNode;

    public SearchTree() {
      root = new Node();
      currentNode = root;
    }

    public void ResetPosition() {
      currentNode = root;
    }

    public bool IsLeafNode() {
      return currentNode.children == null;
    }

    public void ExpandCurrentNode<T>(IEnumerable<T> actions) {
      Contract.Assert(actions.Any());
      Contract.Assert(currentNode.children == null);
      currentNode.children = actions.Select(_ => new Node() { parent = currentNode }).ToArray();
    }

    public void Follow(int action) {
      Contract.Assert(currentNode.children != null);
      Contract.Assert(currentNode.children[action] != null);
      currentNode = currentNode.children[action];
    }

    public IEnumerable<int> PossibleActions {
      get {
        return Enumerable.Range(0, currentNode.children.Length)
                         .Where(i => currentNode.children[i] != null);
      }
    }

    public void RemoveBranch(int action) {
      Contract.Assert(currentNode.children != null);
      Contract.Assert(currentNode.children[action] != null);
      currentNode.children[action] = null;

      RemoveRecursively(currentNode);
    }

    private void RemoveRecursively(Node node) {
      if (node == null) return;
      // when the last child has been removed we must remove the current node from it's parent
      if (node.children.All(ch => ch == null) && node.parent != null) {
        node.parent.children[Array.IndexOf(node.parent.children, node)] = null;
        RemoveRecursively(node.parent);
      }
    }
  }
}