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

//   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.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.logging.Level;

import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
import de.ugoe.cs.autoquest.usageprofiles.Trie;
import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * This trie implementation is a performance optimization for generating task trees. It does not
 * create a full trie but adds only those subsequences having a chance of occurring most often.
 * For this, it initially counts the number of occurrences of each task instance. Then, during
 * training, it regularly determines the number of the currently most often occurring sequence. If
 * this number is higher than the count of a task instance to be trained, the task instance is
 * skipped the not added to the trie.
 * </p>
 * 
 * @author Patrick Harms
 */
class TaskInstanceTrie extends Trie<ITask> {

    /**  */
    private static final long serialVersionUID = 1L;

    /**
     * <p>
     * the task handling strategy to be used for comparing tasks
     * </p>
     */
    private TaskHandlingStrategy taskStrategy;
    
    /**
     * <p>
     * instantiated the trie with the task handling strategy to be used
     * </p>
     *
     * @param taskStrategy the task handling strategy to be used for comparing tasks
     */
    public TaskInstanceTrie(TaskHandlingStrategy taskStrategy) {
        super(taskStrategy);
        this.taskStrategy = taskStrategy;
    }

    /**
     * <p>
     * trains this trie with the provided user sessions up to the provided maximum depth using
     * the optimization described in the description of this class.
     * </p>
     * 
     * @param userSessions the sessions for which this trie is to be trained
     * @param maxOrder     the depth of the trie
     */
    public void trainSessions(List<IUserSession> userSessions, int maxOrder) {
        if (maxOrder < 1) {
            return;
        }
        
        SymbolMap<ITask, Counter> equalTaskInstancesMap =
            taskStrategy.createSymbolMap();
        
        Map<ITask, Counter> instanceCountMap = new HashMap<ITask, Counter>();
        Console.traceln(Level.FINEST, "preparing training");
        int noOfTaskInstances = 0;
        for (IUserSession session : userSessions) {
            for (ITaskInstance taskInstance : session) {
                Counter counter = equalTaskInstancesMap.getValue(taskInstance.getTask());
                
                if (counter == null) {
                    counter = new Counter();
                    equalTaskInstancesMap.addSymbol(taskInstance.getTask(), counter);
                }
                
                counter.count++;
                instanceCountMap.put(taskInstance.getTask(), counter);
                
                noOfTaskInstances++;
            }
        }
        
        Console.traceln
            (Level.FINEST, "performing training of " + noOfTaskInstances + " task instances");
        
        Counter processedTaskInstances = new Counter();
        Counter currentSequenceMaxCount = new Counter();
        int counterRecheckAt = noOfTaskInstances / 20; // recheck the maximum count after each
                                                       // 10% of processed task instances
        for (IUserSession session : userSessions) {
            train(session, maxOrder, instanceCountMap, processedTaskInstances,
                  currentSequenceMaxCount, counterRecheckAt);
        }      
        
        updateKnownSymbols();
    }
    
    /* (non-Javadoc)
     * @see de.ugoe.cs.autoquest.usageprofiles.Trie#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        else if (other instanceof TaskInstanceTrie) {
            return super.equals(other);
        }
        else {
            return false;
        }
    }

    /* (non-Javadoc)
     * @see de.ugoe.cs.autoquest.usageprofiles.Trie#hashCode()
     */
    @Override
    public int hashCode() {
        return super.hashCode();
    }

    /**
     * <p>
     * internally used convenience method for implementing the training optimization
     * </p>
     */
    private void train(IUserSession        userSession,
                       int                 maxOrder,
                       Map<ITask, Counter> taskInstanceCountMap,
                       Counter             processedTaskInstances,
                       Counter             currentSequenceMaxCount,
                       int                 counterRecheckAt)
    {
        List<ITask> subsequence = new LinkedList<ITask>();
        
        for (ITaskInstance currentTaskInstance : userSession) {
            
            int occurrenceCount = taskInstanceCountMap.get(currentTaskInstance.getTask()).count;
            
            if (processedTaskInstances.count >= counterRecheckAt) {
                currentSequenceMaxCount.count = getCurrentSequenceMaxCount();
                processedTaskInstances.count = 0;
            }
            
            if (occurrenceCount < currentSequenceMaxCount.count) {
                // this task instance does not need to be considered, as it occurs not often enough
                // to be part of a sequence, that occurs most often. Therefore train all remaining
                // sequences so far and go on, until the next useful sequence is found.
                
                while (subsequence.size() > 1) {
                    add(subsequence);
                    subsequence.remove(0);
                }
                
                subsequence.clear();
            }
            else {
                subsequence.add(currentTaskInstance.getTask());

                if (subsequence.size() == maxOrder) {
                    add(subsequence);
                    subsequence.remove(0);
                }
            }
            
            processedTaskInstances.count++;
        }
        
        // add shorter remaining subsequences, if any
        while (subsequence.size() > 1) {
            add(subsequence);
            subsequence.remove(0);
        }
    }

    /**
     * <p>
     * determines the current maximum count of sequences of a minimal length of two. Task instances
     * occuring more seldom do not have to be considered anymore
     * </p>
     *
     * @return the current maximum count of sequences of a minimal length of two
     */
    private int getCurrentSequenceMaxCount() {
        MaxSequenceCountFinder processor = new MaxSequenceCountFinder();
        super.process(processor);
        return processor.getMaxCount();
    }

    /**
     * <p>
     * trie processor identifying the current maximum count of sequences of a minimal length of two
     * </p>
     * 
     * @author Patrick Harms
     */
    private static class MaxSequenceCountFinder implements TrieProcessor<ITask> {
        
        /**
         * <p>
         * the current maximum count
         * </p>
         */
        private int currentCount = 0;
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
         */
        @Override
        public TrieProcessor.Result process(List<ITask> foundTask, int count) {
            if (foundTask.size() == 2) {
                this.currentCount = Math.max(this.currentCount, count);
                
                // do not consider children
                return TrieProcessor.Result.SKIP_NODE;
            }
            else {
                return TrieProcessor.Result.CONTINUE;
            }
        }

        /**
         * <p>
         * returns the current maximum count
         * </p>
         */
        private int getMaxCount() {
            return currentCount;
        }

    }
    
    /**
     * <p>
     * counter object to be able to call something by the counters reference
     * </p>
     * 
     * @author Patrick Harms
     */
    private static class Counter {
        int count = 0;
    }
        
}