Grow.java

package progen.kernel.tree;

import java.util.List;

import progen.context.ProGenContext;
import progen.kernel.grammar.Grammar;
import progen.kernel.grammar.Production;

/**
 * Clase que implementa el método de inicialización de árboles grow. Esta forma
 * de inicializar un árbol, consiste en generar un árbol tal que todos los nodos
 * hoja estén a una profundidad mínima del parámetro definido y al menos uno de
 * esos nodos hoja, a la profundidad máxima especificada; siempre y cuando no se
 * exceda el número total de nodos que se permita por configuración.
 * 
 * @author jirsis
 * @since 2.0
 */
public class Grow implements InitializeTreeMethod {

  private static final int DEFAULT_MAX_ATTEMPTS = 100;
  private static final long serialVersionUID = 7620491297926843935L;
  /** Profundidad mínima de los nodos. */
  private int minDepth;
  /** Profundidad máxima de los nodos. */
  private int maxDepth;
  /** Número máximo de nodos que se permiten en el árbol. */
  private int maxNodes;
  /**
   * Número máximo de intentos durante los que se intentará generar un árbol
   * válido.
   */
  private int maxAttempts;

  /**
   * Constructor genérico de la clase, en la que se inicializan los atributos en
   * función de la definición proporcionada en el fichero de propiedades del
   * dominio implementado por el usuario.
   */
  public Grow() {
    maxNodes = ProGenContext.getOptionalProperty("progen.population.max-nodes", Integer.MAX_VALUE);
    minDepth = 0;
    maxDepth = 0;
    maxAttempts = ProGenContext.getOptionalProperty("progen.max-attempts", DEFAULT_MAX_ATTEMPTS);
    final String[] intervalDepth = ProGenContext.getMandatoryProperty("progen.population.init-depth-interval").split(",");
    minDepth = Integer.parseInt(intervalDepth[0]);
    if (intervalDepth.length == 2) {
      maxDepth = Integer.parseInt(intervalDepth[1]);
    } else {
      maxDepth = minDepth;
    }
  }

  @Override
  public void generate(Grammar grammar, Node root) {
    boolean generated = false;

    while (!generated && maxAttempts > 0) {
      generated = generate(grammar, root, grammar.getRandomProductions(root.getSymbol()));
      if (!generated) {
        maxAttempts--;
      }
    }

    if (!generated) {
      throw new IncompatibleOptionsInitTreeMethodException(maxNodes, minDepth, maxDepth);
    }
  }

  /**
   * Método recursivo que va generando realmente el árbol de tal forma que se
   * van almacenando en el parámetro <code>stack</code> las producciones que
   * pueden generar ciertos elementos y que serán utilizados en caso de que
   * después de terminar de utilizar una producción determinada no se haya
   * podido cumplir con la condición impuesta en el inicializador.
   * 
   * @param grammar
   *          Gramática de la que se obtendrán las distintas producciones que
   *          generarán el árbol.
   * @param node
   *          Nodo que se está expandiendo en un determinado momento.
   * @param stack
   *          Conjunto de producciones que se podrían utilizar en caso de que no
   *          se pueda acabar de forma satisfactoria. Serán las producciones
   *          utilizadas en la parte de back-tracking del algoritmo.
   * @return <code>true</code> si se terminó de generar correctamente el nodo y
   *         <code>false</code> en caso contrario.
   */
  /*
   * Como optimización del proceso, se hacen primero las comprobaciones sobre un
   * nodo y una vez se cumplan, se procederá a generar los distintos hijos, en
   * función de la producción escogida. Las comprobaciones que se hacen sobre
   * cada nodo consisten en: - comprobar la profundidad máxima - si es una hoja,
   * comprobar la profundidad mínima - comprobar que no se supere el número
   * máximo de nodos
   * 
   * Estas comprobaciones sería más intuitivo hacerlas después de generar todos
   * los hijos, pero resulta mucho más eficiente si se realizan antes, dado que
   * evita tener que generar y evaluar subramas del árbol, que se terminarán
   * eliminando en muchos casos.
   */
  private boolean generate(Grammar grammar, Node node, List<Production> stack) {
    boolean generated = false;

    if (node.getDepth() > maxDepth) {
      generated = false;
    } else {
      while (!generated && stack.size() > 0) {
        generated = true;
        node.setProduction(stack.remove(0));
        generated = generateChildren(grammar, node);
        tryNextNode(node, generated);

      }
    }

    return generated;
  }

  private boolean generateChildren(Grammar grammar, Node node) {
    boolean generated;
    if (node.isLeaf() && node.getDepth() < minDepth) {
      generated = false;
    } else if (maxNodeExceded(node)) {
      generated = false;
    } else {
      generated = generateChildrenOfNode(grammar, node);
    }
    return generated;
  }

  private void tryNextNode(Node node, boolean generated) {
    if (!generated) {
      node.clearNode();
    }
  }

  private boolean generateChildrenOfNode(Grammar grammar, Node node) {
    boolean generated = true;
    List<Production> branchStack;
    Node branch;
    final int initialBranch = (int) (Math.random() * node.getBranches().size());
    for (int i = 0; generated && i < node.getBranches().size(); i++) {
      branch = node.getBranches().get((i + initialBranch) % node.getBranches().size());
      // for(Node branch: node.getBranches()){
      branchStack = grammar.getRandomProductions(branch.getSymbol());
      generated &= generate(grammar, branch, branchStack);
    }
    return generated;
  }

  /**
   * Comprueba que el árbol no haya excedido el número total de nodos
   * permitidos.
   * 
   * @param node
   *          Nodo actual, que forma parte de un árbol, del que se calculará el
   *          número total de nodos que cuelgan de la raíz.
   * @return <code>true</code> si se ha excedido el número máximo de nodos,
   *         <code>false</code> en caso contrario.
   */
  private boolean maxNodeExceded(Node node) {
    Node iterator = node;
    while (!iterator.isRoot()) {
      iterator= iterator.getParent();
    }
    return iterator.getTotalNodes() > maxNodes;
  }

  @Override
  public void updateMaximunDepth() {
    maxDepth = ProGenContext.getOptionalProperty("progen.population.max-depth.updated", maxDepth);
  }

  @Override
  public void updateMaximunNodes() {
    maxNodes = ProGenContext.getOptionalProperty("progen.population.max-nodes.updated", maxNodes);
  }

  @Override
  public void updateMinimunDepth() {
    minDepth = ProGenContext.getOptionalProperty("progen.population.min-depth.updated", minDepth);
  }
}