source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/DefaultTaskSequenceDetectionRule.java @ 1113

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.tasktrees.temporalrelation;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality;
import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory;
import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator;
import de.ugoe.cs.autoquest.usageprofiles.Trie;

/**
 * <p>
 * TODO comment
 * </p>
 * 
 * @author Patrick Harms
 */
class DefaultTaskSequenceDetectionRule implements TemporalRelationshipRule {
    
    /**
     * <p>
     * the task tree node factory to be used for creating substructures for the temporal
     * relationships identified during rule
     * </p>
     */
    private ITaskTreeNodeFactory taskTreeNodeFactory;
    /**
     * <p>
     * the task tree builder to be used for creating substructures for the temporal relationships
     * identified during rule application
     * </p>
     */
    private ITaskTreeBuilder taskTreeBuilder;

    /**
     * <p>
     * the node comparator to be used for comparing task tree nodes
     * </p>
     */
    private SymbolComparator<ITaskTreeNode> nodeComparator;

    /**
     * <p>
     * instantiates the rule and initializes it with a node equality rule manager and the minimal
     * node equality identified sublist must have to consider them as iterated.
     * </p>
     */
    DefaultTaskSequenceDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager,
                                     NodeEquality            minimalNodeEquality,
                                     ITaskTreeNodeFactory    taskTreeNodeFactory,
                                     ITaskTreeBuilder        taskTreeBuilder)
    {
        this.taskTreeNodeFactory = taskTreeNodeFactory;
        this.taskTreeBuilder = taskTreeBuilder;
        
        this.nodeComparator =
            new TaskTreeNodeComparator(nodeEqualityRuleManager, minimalNodeEquality);
    }

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.tasktree.temporalrelation.TemporalRelationshipRule#apply(TaskTreeNode,
     * boolean)
     */
    @Override
    public RuleApplicationResult apply(ITaskTreeNode parent, boolean finalize) {
        if (!(parent instanceof ISequence)) {
            return null;
        }

        if (!finalize) {
            // the rule is always feasible as tasks may occur at any time
            RuleApplicationResult result = new RuleApplicationResult();
            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
            return result;
        }

        long timestamp1;
        long timestamp2 = System.currentTimeMillis();
        long ms1 = 0;
        long ms2 = 0;
        long ms3 = 0;
        long ms4 = 0;
        
        List<ISequence> createdSequences = new LinkedList<ISequence>();
        
        int evisagedNoOfOccurrences = 0;
        
        do {
            timestamp1 = timestamp2;
            Trie<ITaskTreeNode> trie = new Trie<ITaskTreeNode>(nodeComparator);
        
            System.out.println("training trie");
            trainTrie(trie, parent, createdSequences);

            timestamp2 = System.currentTimeMillis();
            ms1 += timestamp2 - timestamp1;
            timestamp1 = timestamp2;

            System.out.println("determining most prominent tasks");
            Collection<List<ITaskTreeNode>> tasks =
                trie.getSequencesWithOccurrenceCount(2, evisagedNoOfOccurrences);
            
            tasks = sortAndRemovePermutationsOfShorterTasks(tasks); 
        
            timestamp2 = System.currentTimeMillis();
            ms2 += timestamp2 - timestamp1;
            timestamp1 = timestamp2;

            if ((tasks != null) && (tasks.size() > 0)) {
                Iterator<List<ITaskTreeNode>> tasksIterator = tasks.iterator();
                
                while (tasksIterator.hasNext()) {
                    List<ITaskTreeNode> task = tasksIterator.next();
                    evisagedNoOfOccurrences = trie.getCount(task);

                    // only tasks occurring more often than once are of interest
                    if (evisagedNoOfOccurrences > 1) {
                        timestamp2 = System.currentTimeMillis();
                        ms3 += timestamp2 - timestamp1;
                        timestamp1 = timestamp2;

                        String taskId = "task " + RuleUtils.getNewId();
                        System.out.println("creating sequences for task " + taskId + ": " + task);
                        createSequenceForTaskOccurrences(taskId, task, parent, createdSequences);

                        timestamp2 = System.currentTimeMillis();
                        ms4 += timestamp2 - timestamp1;
                        timestamp1 = timestamp2;
                    }
                }
            }
            
            evisagedNoOfOccurrences--;
        }
        while (evisagedNoOfOccurrences > 1);
        
        System.out.println(ms1 + "   " + ms2 + "   " + ms3 + "   " + ms4);
        RuleApplicationResult result = new RuleApplicationResult();
        
        if (createdSequences.size() > 0) {
            for (ISequence sequence : createdSequences) {
                result.addNewlyCreatedParentNode(sequence);
            }
            
            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED);
        }

        
        return result;
    }

    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param trie
     * @param parent
     */
    private void trainTrie(Trie<ITaskTreeNode> trie,
                           ITaskTreeNode       parent,
                           List<ISequence>     createdSequences)
    {
        List<ITaskTreeNode> children = parent.getChildren();
        
        if ((children != null) && (children.size() > 0)) {
            trie.train(children, children.size());
            
            for (ITaskTreeNode child : children) {
                trainTrie(trie, child, createdSequences);
            }
        }
    }

    /**
     *
     */
    private List<List<ITaskTreeNode>>
        sortAndRemovePermutationsOfShorterTasks(Collection<List<ITaskTreeNode>> tasks)
    {
        // first of all create a sorted list of the tasks with the longest first
        List<List<ITaskTreeNode>> sortedTasks = new LinkedList<List<ITaskTreeNode>>();
        
        boolean added;
        for (List<ITaskTreeNode> task : tasks) {
            added = false;
            for (int i = 0; i < sortedTasks.size(); i++) {
                if (sortedTasks.get(i).size() < task.size()) {
                    sortedTasks.add(i, task);
                    added = true;
                    break;
                }
            }
            
            if (!added) {
                sortedTasks.add(task);
            }
        }
        
        // now iterate the sorted list and for each task remove all other tasks that are shorter
        // (i.e. come later in the sorted list) and that represent a subpart of the task
        for (int i = 0; i < sortedTasks.size(); i++) {
            for (int j = i + 1; j < sortedTasks.size();) {
                if (sortedTasks.get(j).size() < sortedTasks.get(i).size()) {
                    // found a task that is a potential subtask. Check for this and remove the
                    // subtask if needed
                    List<ITaskTreeNode> longTask = sortedTasks.get(i);
                    List<ITaskTreeNode> shortTask = sortedTasks.get(j);
                    
                    if (getSubListIndex(longTask, shortTask, 0) > -1) {
                        sortedTasks.remove(j);
                    }
                    else {
                        j++;
                    }
                }
                else {
                    j++;
                }
            }
        }
        
        return sortedTasks;
    }

    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param task
     * @param parent
     * @param treeBuilder
     * @param nodeFactory
     * @param result
     */
    private void createSequenceForTaskOccurrences(String              taskId,
                                                  List<ITaskTreeNode> task,
                                                  ITaskTreeNode       parent,
                                                  List<ISequence>     createdSequences)
    {
        List<ITaskTreeNode> children = parent.getChildren();
        
        if ((children == null) || (children.size() == 0)) {
            return;
        }
        
        // first traverse the children
        for (ITaskTreeNode child : children) {
            createSequenceForTaskOccurrences(taskId, task, child, createdSequences);
        }
        
        // now check the children themselves for an occurrence of the task
        int index = -1;
        
        do {
            index = getSubListIndex(children, task, ++index);
            
            if (index > -1) {
                if (task.size() < children.size()) {
                    ISequence sequence = RuleUtils.createNewSubSequenceInRange
                        (parent, index, index + task.size() - 1, taskId,
                         taskTreeNodeFactory, taskTreeBuilder);
                    
                    createdSequences.add(sequence);
                 
                    children = parent.getChildren();
                }
                else {
                    // the whole list of children is an occurrence of this task. Just set the
                    // description of the parent and break up
                    String description = parent.getDescription();
                    
                    if ((description != null) && (description.length() > 0)) {
                        description += "; " + taskId;
                    }
                    else {
                        description = taskId;
                    }
                    
                    taskTreeBuilder.setDescription(parent, description);
                    break;
                }
            }
        }
        while (index > -1);
    }

    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param trie
     * @param object
     * @return
     */
    private int getSubListIndex(List<ITaskTreeNode> list,
                                List<ITaskTreeNode> subList,
                                int                 startIndex)
    {
        boolean matchFound;
        int result = -1;
        
        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
            matchFound = true;
            
            for (int j = 0; j < subList.size(); j++) {
                if (!nodeComparator.equals(list.get(i + j), subList.get(j))) {
                    matchFound = false;
                    break;
                }
            }
            
            if (matchFound) {
                result = i;
                break;
            }
        }
        
        return result;
    }
    
}