Node.java

package progen.kernel.tree;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import progen.kernel.functions.NullFunction;
import progen.kernel.grammar.GrammarNonTerminalSymbol;
import progen.kernel.grammar.GrammarTerminalSymbol;
import progen.kernel.grammar.Production;
import progen.userprogram.UserProgram;

/**
 * Clase que proporciona todos los métodos necesarios para gestionar un nodo,
 * así como de la modificación de su contenido y calculo de la ejecución del
 * mismo.
 * 
 * @author jirsis
 * @since 1.0
 * @version 2.0
 */
public class Node implements Cloneable, Serializable {
  private static final long serialVersionUID = 8802106541230059873L;
  
  /** Número total de nodos que cuelgan de un nodo concreto */
  private int totalNodes;
  /** Profundidad a la que está dentro del árbol. */
  private int depth;
  /** Enlace al nodo padre. */
  private Node parent;
  /** Conjunto de nodos hijos */
  private List<Node> branches;
  /** Simbolo que representa a este nodo */
  private GrammarNonTerminalSymbol symbol;
  /** Función que contiene el nodo */
  private GrammarTerminalSymbol function;

  /**
   * Constructor que recibe el símbolo no terminal que contendrá el nodo.
   * 
   * @param symbol
   *          Símbolo que estará almacenado en el nodo.
   */
  public Node(GrammarNonTerminalSymbol symbol) {
    this.parent = null;
    this.branches = new ArrayList<Node>();
    this.symbol = symbol;
    this.function = new GrammarTerminalSymbol(new NullFunction(symbol.toString()));
    this.depth = 0;
    this.totalNodes = 1;
  }

  /**
   * Constructor de copia que recibe un nodo en el que basarse para duplicar.
   * 
   * @param node
   *          El nodo del que obtener la información de copia.
   * @param parent
   *          El nodo padre del nodo a copiar.
   */
  private Node(Node node, Node parent) {
    this.depth = node.depth;
    this.function = node.function;
    this.parent = parent;
    this.symbol = node.symbol;
    this.totalNodes = node.totalNodes;

    this.branches = new ArrayList<Node>();
    for (Node branch : node.branches) {
      this.branches.add(new Node(branch, this));
    }

  }

  /**
   * Constructor de la clase que recibe un símbolo no terminal y el padre para
   * que queden enlazados.
   * 
   * @param symbol
   *          Símbolo no terminal que se almacenará en el nodo.
   * @param parent
   *          Nodo que será el pader del actual.
   */
  public Node(GrammarNonTerminalSymbol symbol, Node parent) {
    // se enlazan el padre y el hijo
    this.parent = parent;
    parent.getBranches().add(this);

    this.branches = new ArrayList<Node>();
    this.symbol = symbol;
    this.function = new GrammarTerminalSymbol(new NullFunction(symbol.toString()));
    this.depth = parent.getDepth() + 1;
    this.totalNodes = 0;
    addTotalNodes(1);
  }

  /**
   * Especifica la función que contiene el nodo.
   * 
   * @param function
   *          La función que contiene el nodo.
   */
  public void setFunction(GrammarTerminalSymbol function) {
    this.function = function;
  }

  /**
   * Devuelve el número total de nodos que cuelgan de uno concreto.
   * 
   * @return el número total de nodos.
   */
  public int getTotalNodes() {
    return totalNodes;
  }

  /**
   * Devuelve el nodo padre del nodo actual
   * 
   * @return el padre del nodo actual o <code>null</code> en caso de ser la
   *         raíz.
   */
  public Node getParent() {
    return parent;
  }

  /**
   * Devuelve la función que contiene en el nodo.
   * 
   * @return la función que contiene el nodo.
   */
  public GrammarTerminalSymbol getFunction() {
    return function;
  }

  /**
   * Devuelve el símbolo no terminal de la gramática que generó este nodo.
   * 
   * @return el símbolo no terminal de la gramática que generó el nodo.
   */
  public GrammarNonTerminalSymbol getSymbol() {
    return symbol;
  }

  /**
   * Devuelve una lista con todas las ramas del nodo.
   * 
   * @return conjunto de ramas que cuelgan del nodo.
   */
  public List<Node> getBranches() {
    return branches;
  }

  /**
   * Devuelve la profundidad a la que se encuentra un nodo.
   * 
   * @return la profundidad a la que está el nodo.
   */
  public int getDepth() {
    return depth;
  }

  /**
   * Define a que profundidad se encunetra el nodo y actualiza la profundidad de
   * todas sus ramas.
   * 
   * @param depth
   *          la nueva profundidad.
   */
  private void setDepth(int depth) {
    this.depth = depth;
    for (Node node : branches) {
      node.setDepth(depth + 1);
    }
  }

  /**
   * Completa la información del nodo a partir de una producción pasada por
   * parámetro.
   * 
   * @param production
   *          La producción de la que obtiene la información.
   */
  public void setProduction(Production production) {
    symbol = production.getLeft();
    function = production.getFunction();
    for (int i = 0; i < production.getArgs().length; i++) {
      new Node(production.getArgs()[i], this);
    }
  }

  /**
   * Define una rama en una posición concreta, actualizando la información
   * relativa a la posición dentro del árbol del que forma parte.
   * 
   * @param branch
   *          Rama a colocar.
   * @param branchPosition
   *          Posición de la rama.
   */
  public void setBranch(Node branch, int branchPosition) {
    this.addTotalNodes(branch.getTotalNodes());
    branch.parent = this;
    branch.setDepth(depth + 1);
    if (branchPosition > branches.size()) {
      branches.add(branchPosition - 1, branch);
    } else {
      branches.add(branchPosition, branch);
    }

  }

  /**
   * Separa al nodo del árbol del que forma parte quedando como raíz del
   * subárbol que definía. Actualiza y define todos los atributos de tal forma
   * que es la raíz de un árbol.
   * 
   * @return El nodo ráiz del subárbol que definía.
   */
  public Node branch() {
    if (!this.isRoot()) {
      parent.addTotalNodes(-this.totalNodes);

      int thisNode = 0;
      for (int i = 0; i < parent.getBranches().size(); i++) {
        if (this == parent.getBranches().get(i)) {
          thisNode = i;
        }
      }
      parent.branches.remove(thisNode);
      parent = null;
      depth = 0;
    }
    return this;
  }

  /**
   * Actualiza el número total de nodos que cuelgan de un nodo y de los nodos
   * que están por encima de él hasta llegar a la raíz.
   * 
   * @param totalNodes
   *          El número de nodos a actualizar.
   */
  public void addTotalNodes(int totalNodes) {
    if (parent != null) {
      parent.addTotalNodes(totalNodes);
    }
    this.totalNodes += totalNodes;
  }

  /**
   * Limpia el contenido del nodo en concreto y de todas las ramas que tenía.
   */
  public void clearNode() {
    function = new GrammarTerminalSymbol(new NullFunction(symbol.toString()));
    for (int i = 0; i < branches.size(); i++) {
      addTotalNodes(-branches.get(i).getTotalNodes());
    }
    branches.clear();

  }

  /**
   * Comprueba si el nodo es un nodo hoja o no, esto es, si tiene alguna rama o
   * no.
   * 
   * @return <code>true</code> si es una hoja y <code>false</code> en caso
   *         contrario.
   */
  public boolean isLeaf() {
    return branches.size() == 0;
  }

  /**
   * Comprueba si el nodo es un nodo raíz o no, esto es, si tiene algún nodo que
   * sea padre suyo.
   * 
   * @return <code>true</code> si es la raíz y <code>false</code> en caso
   *         contrario.
   */
  public boolean isRoot() {
    return parent == null;
  }

  @Override
  public String toString() {
    final StringBuilder node = new StringBuilder();
    if (isLeaf()) {
      node.append(function);
    } else {
      node.append("(").append(function);
      for (int i = 0; i < branches.size(); i++) {
        node.append(" ").append(branches.get(i).toString());
      }
      node.append(" )");
    }
    return node.toString();
  }

  /**
   * Evalúa el nodo llamando a la función que contiene.
   * 
   * @param userProgram
   *          Representación del dominio implementado por el usuario.
   * @param returnAddr
   *          Dirección de retorno de las llamadas a ADFs.
   * @return Valor después de ejecutar la función del nodo.
   */
  public Object evaluate(UserProgram userProgram, Map<String, Object> returnAddr) {
    return function.getFunction().evaluate(branches, userProgram, returnAddr);
  }

  /**
   * Devuelve el nodo que se encuentra en la posición solicitada, recorriendo
   * todos los hijos siguiendo en pre-orden.
   * 
   * @param position
   *          La posición del nodo buscado.
   * @return El nodo que está en la posición solicitada o <code>null</code> si
   *         solicitó un nodo fuera de los rangos permitidos.
   */
  public Node getNode(int position) {
    Node node = null;
    // si se busca un numero < 0 o mayor que el numero de nodos total
    if (position < this.getTotalNodes() && position >= 0) {
      node = findNode(position);
    }
    return node;
  }

  /**
   * Método recursivo que recorre todos los nodos a partir del actual buscando
   * el que esté en la posción
   * 
   * @param position
   *          Posición del nodo que se quiere buscar.
   * @return Nodo que está en la posición requerida.
   */
  private Node findNode(int position) {
    Node node = null;
    int currentPosition = position;
    if (currentPosition == 0) {
      node = this;
    } else {
      for (int i = 0; node == null && i < branches.size(); i++) {
        node = branches.get(i).findNode(currentPosition - 1);
        currentPosition -= branches.get(i).getTotalNodes();
      }
    }
    return node;
  }

  /**
   * Devuelve la profundidad a la que se encuentra el nodo más profundo de todos
   * los hijos que tenga un nodo concreto.
   * 
   * @return La profundidad a la que se encuentra el nodo que está más profundo.
   */
  public int getMaximunDepth() {
    int maxDepth = 0;
    if (this.isLeaf()) {
      maxDepth = depth;
    } else {
      for (Node branch : branches) {
        maxDepth = Math.max(maxDepth, branch.getMaximunDepth());
      }
    }
    return maxDepth;
  }
  
  /**
   * La clonación de un nodo implica crear nuevos nodos copia a partir de uno
   * dado. Se recomienda clonar a partir de un nodo raíz.
   * 
   * @return Node clonado.
   * @see java.lang.Object#clone()
   */
  public Node clone() {
    try {
      super.clone();
    } catch (CloneNotSupportedException e) {
      // ignore this exception
    }
    
    return new Node(this, this.parent);
  }
}