Full.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 la forma de inicialización Full. En este tipo de
 * inicialización, se crearán árboles de tal forma que todas las ramas tendrán
 * la misma profundidad. De tal forma que será necesario especificar un
 * intervalo de profundidades mínima y máxima en la que estará comprendida la
 * profundidad del árbol que se generará, sin exceder el número máximo de nodos
 * permitido.
 * 
 * @author jirsis
 * @since 2.0
 */
public class Full implements InitializeTreeMethod {
  private static final long serialVersionUID = 3387278132317051831L;
  
  private static final int DEFAULT_MAX_ATTEMPTS = 100;
  private static final String PROGEN_ACTIVE_SEARCH_PROPERTY = "progen.activeSearch";
  /** Profundidad mínima que tendrá el árbol resultante. */
  private int minDepth;
  /** Profundidad máxima que tendrá el árbol resultante. */
  private int maxDepth;
  /** Número de nodos máximo que puede tener el árbol construído. */
  private int maxNodes;

  /**
   * Número máximo de intentos durante los que se intentará generar un árbol
   * válido.
   */
  private int maxAttempts;

  /**
   * Profundidad temporal del árbol, según se va construyendo. Siempre deberá
   * tener un valor entre los valores mínimo y máximo.
   */
  private int currentDepth;

  /**
   * 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 Full() {
    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;
    currentDepth = Math.max((int) (Math.random() * (maxDepth - minDepth + 1) + minDepth), root.getDepth());
    while (!generated && conditionGeneration()) {
      generated = generate(grammar, root, grammar.getRandomProductions(root.getSymbol()));
      if (!generated) {
        updateCondition();
      }
    }

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

  /**
   * Actualiza el valor de la condición de salida, según sea la condición de
   * búsqueda activa o el máximo de intentos posibles.
   */
  private void updateCondition() {
    final boolean activeSearchEnable = ProGenContext.getOptionalProperty(PROGEN_ACTIVE_SEARCH_PROPERTY, false);
    if (activeSearchEnable) {
      activeSearchConditionUpdate();
    } else {
      maxAttemptsConditionUpdate();
    }
  }

  /**
   * Actualiza la condición de máximo de intentos.
   */
  private void maxAttemptsConditionUpdate() {
    currentDepth = (int) (Math.random() * (maxDepth - minDepth + 1) + minDepth);
    maxAttempts--;
  }

  /**
   * Actualiza la condición de búsqueda activa.
   */
  private void activeSearchConditionUpdate() {
    currentDepth--;
  }

  /**
   * Comprueba si se cumple el valor de la condición o no.
   * 
   * @return Si se cumple la condición.
   */
  private boolean conditionGeneration() {
    final boolean activeSearchEnable = ProGenContext.getOptionalProperty(PROGEN_ACTIVE_SEARCH_PROPERTY, false);
    boolean condition = true;
    if (activeSearchEnable) {
      condition = activeSearchCondition();
    } else {
      condition = maxAttemptsCondition();
    }
    return condition;
  }

  /**
   * Comprueba si la profundidad actual es superior a la profundidad mínima.
   * 
   * @return <code>true</code> si la profundidad actual es mayor que la mínima
   *         definida.
   */
  private boolean activeSearchCondition() {
    return currentDepth >= minDepth;
  }

  /**
   * Comprueba si no se ha superado el número máximo de intentos posible.
   * 
   * @return <code>true</code> si no se ha excedido el número máximo de intentos
   *         disponibles.
   */
  private boolean maxAttemptsCondition() {
    return maxAttempts > 0;
  }

  /**
   * 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() > currentDepth) {
      generated = false;
    } else {
      while (!generated && stack.size() > 0) {
        generated = true;
        node.setProduction(stack.remove(0));
        generated = generateChildrens(grammar, node);
        tryNextProduction(node, generated);
      }
    }

    return generated;
  }

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

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

  private boolean defineChildrenForThisNode(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());
      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);
  }

}