source: trunk/quest-core-tasktrees/src/main/java/de/ugoe/cs/quest/tasktrees/temporalrelation/DefaultIterationDetectionRule.java @ 439

//-------------------------------------------------------------------------------------------------
// Module    : $RCSfile: DefaultIterationDetectionRule.java,v $
// Version   : $Revision: 0.0 $  $Author: patrick $  $Date: 19.02.2012 $
// Project   : TaskTreeCreator
// Creation  : 2012 by patrick
// Copyright : Patrick Harms, 2012
//-------------------------------------------------------------------------------------------------
package de.ugoe.cs.quest.tasktrees.temporalrelation;

import java.util.ArrayList;
import java.util.List;

import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEquality;
import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEqualityRuleManager;
import de.ugoe.cs.quest.tasktrees.treeifc.Iteration;
import de.ugoe.cs.quest.tasktrees.treeifc.Selection;
import de.ugoe.cs.quest.tasktrees.treeifc.Sequence;
import de.ugoe.cs.quest.tasktrees.treeifc.TaskTreeBuilder;
import de.ugoe.cs.quest.tasktrees.treeifc.TaskTreeNode;
import de.ugoe.cs.quest.tasktrees.treeifc.TaskTreeNodeFactory;

//-------------------------------------------------------------------------------------------------
/**
 * TODO comment
 * 
 * @version $Revision: $ $Date: 19.02.2012$
 * @author 2012, last modified by $Author: patrick$
 */
//-------------------------------------------------------------------------------------------------
public class DefaultIterationDetectionRule implements TemporalRelationshipRule
{
  /** */
  private NodeEqualityRuleManager mNodeEqualityRuleManager;

  //-----------------------------------------------------------------------------------------------
  /**
   * TODO: comment
   *
   */
  //-----------------------------------------------------------------------------------------------
  DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager)
  {
    super();
    mNodeEqualityRuleManager = nodeEqualityRuleManager;
  }

  //-----------------------------------------------------------------------------------------------
  /* (non-Javadoc)
   * @see TemporalRelationshipRule#apply(TaskTreeNode, TaskTreeBuilder, TaskTreeNodeFactory)
   */
  //-----------------------------------------------------------------------------------------------
  @Override
  public RuleApplicationResult apply(TaskTreeNode        parent,
                                     TaskTreeBuilder     treeBuilder,
                                     TaskTreeNodeFactory nodeFactory,
                                     boolean             finalize)
  {
    if (!(parent instanceof Sequence))
    {
      return null;
    }
    
    // parent must already have at least 2 children
    if ((parent.getChildren() == null) || (parent.getChildren().size() < 2))
    {
      return null;
    }
    
    // iterations represent as a list of nodes that splits up in several equal sublists. If
    // the remaining nodes also start an equal sublist, then the iteration may not be completed
    // yet. So wait for further interactions to only identify completed iterations.
    
    // to find longer iterations first, start with long sequences
    for (int end = parent.getChildren().size() - 1; end > 0; end--)
    {
      for (int start = 0; start < end; start++)
      {
        List<TaskTreeNode[]> equalVariants =
          getEqualSublistVariantsInBoundaries(parent, start, end);
        
        if (equalVariants != null)
        {
          if (!finalize)
          {
            // check, if the iteration may go on. This may be the case, if the detected iteration
            // finishes with the last child of the parent, or if the remaining children, which were
            // not identified as part of the iteration, start a further occurrence of the iteration
            if (end == (parent.getChildren().size() - 1))
            {
              RuleApplicationResult result = new RuleApplicationResult();
              result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
              return result;
            }
            
            boolean allNodesEqual = true;
            for (int i = 0; ((allNodesEqual) && (i < equalVariants.get(0).length)); i++)
            {
              if ((end + i + 1) >= parent.getChildren().size())
              {
                break;
              }
              
              NodeEquality nodeEquality = mNodeEqualityRuleManager.applyRules
                (equalVariants.get(0)[i], parent.getChildren().get(end + i + 1));
              
              allNodesEqual &=
                nodeEquality.getStructuralEquality() || nodeEquality.getSemanticalEquality();
            }
            
            if (allNodesEqual)
            {
              RuleApplicationResult result = new RuleApplicationResult();
              result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
              return result;
            }
          }
          
          RuleApplicationResult result = new RuleApplicationResult();
          Iteration newIteration = nodeFactory.createNewIteration();
          result.addNewlyCreatedParentNode(newIteration);
          
          if (equalVariants.size() == 1)
          {
            // all children are the same. Create an iteration of this child
            if (equalVariants.get(0).length == 1)
            {
              // all children are the same. Create an iteration of this child
              treeBuilder.setChild(newIteration, equalVariants.get(0)[0]);
            }
            else
            {
              // there was an iteration of structurally equal sequences
              Sequence sequence = nodeFactory.createNewSequence();
              result.addNewlyCreatedParentNode(sequence);
              
              for (TaskTreeNode node : equalVariants.get(0))
              {
                treeBuilder.addChild(sequence, node);
              }
              
              treeBuilder.setChild(newIteration, sequence);
            }
          }
          else
          {
            // there are distinct variants of semantically equal subsequences or children -->
            // create an iterated selection
            Selection selection = nodeFactory.createNewSelection();
            result.addNewlyCreatedParentNode(selection);
            
            for (TaskTreeNode[] variant : equalVariants)
            {
              if (variant.length == 1)
              {
                treeBuilder.addChild(selection, variant[0]);
              }
              else
              {
                Sequence sequence = nodeFactory.createNewSequence();
                result.addNewlyCreatedParentNode(sequence);
                
                for (TaskTreeNode node : variant)
                {
                  treeBuilder.addChild(sequence, node);
                }
                
                treeBuilder.addChild(selection, sequence);
              }
            }
            
            treeBuilder.setChild(newIteration, selection);
          }
          
          // remove iterated children
          for (int j = end; j >= start; j--)
          {
            treeBuilder.removeChild((Sequence) parent, j);
          }

          // add the new iteration instead
          treeBuilder.addChild((Sequence) parent, start, newIteration);

          result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED);
          return result;
        }
      }
    }
    
    return null;
  }

  //-----------------------------------------------------------------------------------------------
  /**
   * TODO: comment
   *
   * @return
   */
  //-----------------------------------------------------------------------------------------------
  private List<TaskTreeNode[]> getEqualSublistVariantsInBoundaries(TaskTreeNode parent,
                                                                   int          start,
                                                                   int          end)
  {
    List<TaskTreeNode[]> equalVariants = null;
    
    int noOfChildrenInBoundaries = end - start + 1;
    
    for (int subListLength = 1; subListLength <= (noOfChildrenInBoundaries / 2); subListLength++)
    {
      if ((noOfChildrenInBoundaries % subListLength) == 0)
      {
        equalVariants = getEqualSublistVariantsForSubListLength(parent, start, end, subListLength);
      
        if (equalVariants != null)
        {
          return equalVariants;
        }
      }
    }
    
    return null;
  }

  //-----------------------------------------------------------------------------------------------
  /**
   *
   */
  //-----------------------------------------------------------------------------------------------
  private List<TaskTreeNode[]> getEqualSublistVariantsForSubListLength(TaskTreeNode parent,
                                                                       int          start,
                                                                       int          end,
                                                                       int          subListLength)
  {
    List<TaskTreeNode[]> equalVariants = new ArrayList<TaskTreeNode[]>();
    TaskTreeNode[] firstVariant = new TaskTreeNode[subListLength];
    
    for (int i = 0; i < subListLength; i++)
    {
      firstVariant[i] = parent.getChildren().get(start + i);
    }
    
    equalVariants.add(firstVariant);
    
    for (int parentIdx = (start + subListLength); parentIdx <= end; parentIdx += subListLength)
    {
      TaskTreeNode[] otherVariant = new TaskTreeNode[subListLength];
      
      for (int i = 0; i < subListLength; i++)
      {
        NodeEquality nodeEquality = mNodeEqualityRuleManager.applyRules
          (firstVariant[i], parent.getChildren().get(parentIdx + i));
    
        if (!nodeEquality.getStructuralEquality())
        {
          if (nodeEquality.getSemanticalEquality())
          {
            otherVariant[i] = parent.getChildren().get(parentIdx + i);
          }
          else
          {
            return null;
          }
        }
      }
      
      // check, if there is a semantically equal other variant. If so, add it to the list of
      // variants
      boolean semanticallyUnequal = false;
      for (int i = 0; i < subListLength; i++)
      {
        if (otherVariant[i] == null)
        {
          otherVariant[i] = firstVariant[i];
        }
        else
        {
          semanticallyUnequal = true;
        }
      }
      
      if (semanticallyUnequal)
      {
        equalVariants.add(otherVariant);
      }
    }
    
    return equalVariants;
  }

}