// 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;
/**
*
* TODO comment
*
*
* @author Patrick Harms
*/
class DefaultTaskSequenceDetectionRule implements TemporalRelationshipRule {
/**
*
* the task tree node factory to be used for creating substructures for the temporal
* relationships identified during rule
*
*/
private ITaskTreeNodeFactory taskTreeNodeFactory;
/**
*
* the task tree builder to be used for creating substructures for the temporal relationships
* identified during rule application
*
*/
private ITaskTreeBuilder taskTreeBuilder;
/**
*
* the node comparator to be used for comparing task tree nodes
*
*/
private SymbolComparator nodeComparator;
/**
*
* 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.
*
*/
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 createdSequences = new LinkedList();
int evisagedNoOfOccurrences = 0;
do {
timestamp1 = timestamp2;
Trie trie = new Trie(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> tasks =
trie.getSequencesWithOccurrenceCount(2, evisagedNoOfOccurrences);
tasks = sortAndRemovePermutationsOfShorterTasks(tasks);
timestamp2 = System.currentTimeMillis();
ms2 += timestamp2 - timestamp1;
timestamp1 = timestamp2;
if ((tasks != null) && (tasks.size() > 0)) {
Iterator> tasksIterator = tasks.iterator();
while (tasksIterator.hasNext()) {
List 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;
}
/**
*
* TODO: comment
*
*
* @param trie
* @param parent
*/
private void trainTrie(Trie trie,
ITaskTreeNode parent,
List createdSequences)
{
List children = parent.getChildren();
if ((children != null) && (children.size() > 0)) {
trie.train(children, children.size());
for (ITaskTreeNode child : children) {
trainTrie(trie, child, createdSequences);
}
}
}
/**
*
*/
private List>
sortAndRemovePermutationsOfShorterTasks(Collection> tasks)
{
// first of all create a sorted list of the tasks with the longest first
List> sortedTasks = new LinkedList>();
boolean added;
for (List 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 longTask = sortedTasks.get(i);
List shortTask = sortedTasks.get(j);
if (getSubListIndex(longTask, shortTask, 0) > -1) {
sortedTasks.remove(j);
}
else {
j++;
}
}
else {
j++;
}
}
}
return sortedTasks;
}
/**
*
* TODO: comment
*
*
* @param task
* @param parent
* @param treeBuilder
* @param nodeFactory
* @param result
*/
private void createSequenceForTaskOccurrences(String taskId,
List task,
ITaskTreeNode parent,
List createdSequences)
{
List 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);
}
/**
*
* TODO: comment
*
*
* @param trie
* @param object
* @return
*/
private int getSubListIndex(List list,
List 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;
}
}