source: branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrie.java @ 1735

//   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 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;

// TODO: Auto-generated Javadoc
/**
 * <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<ITaskInstance> {

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

        /**
         * <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<ITaskInstance> {

                /** <p> the current maximum count </p>. */
                private int currentCount = 0;

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

                /*
                 * (non-Javadoc)
                 * 
                 * @see
                 * de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util
                 * .List, int)
                 */
                @Override
                public TrieProcessor.Result process(List<ITaskInstance> 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;
                        }
                }

        }

        /** The Constant serialVersionUID. */
        private static final long serialVersionUID = 1L;

        /** <p> the task handling strategy to be used for comparing tasks </p>. */
        private final 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;
        }

        /*
         * (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;
                }
        }

        /**
         * <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() {
                final MaxSequenceCountFinder processor = new MaxSequenceCountFinder();
                super.process(processor);
                return processor.getMaxCount();
        }

        /*
         * (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>.
         *
         * @param userSession the user session
         * @param maxOrder the max order
         * @param taskInstanceCountMap the task instance count map
         * @param processedTaskInstances the processed task instances
         * @param counterRecheckAt the counter recheck at
         */
        private void train(IUserSession userSession, int maxOrder,
                        Map<ITask, Counter> taskInstanceCountMap,
                        Counter processedTaskInstances, int counterRecheckAt) {
                final List<ITaskInstance> subsequence = new LinkedList<ITaskInstance>();

                int sequenceMaxCount = 0;

                for (final ITaskInstance currentTaskInstance : userSession) {

                        final int occurrenceCount = taskInstanceCountMap
                                        .get(currentTaskInstance.getTask()).count;

                        if (processedTaskInstances.count >= counterRecheckAt) {
                                sequenceMaxCount = getCurrentSequenceMaxCount();
                                processedTaskInstances.count = 0;
                        }

                        if (occurrenceCount < sequenceMaxCount) {
                                // 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);

                                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>
         * 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;
                }

                final SymbolMap<ITaskInstance, Counter> equalTaskInstancesMap = taskStrategy
                                .createSymbolMap();

                final Map<ITask, Counter> instanceCountMap = new HashMap<ITask, Counter>();

                System.out.println("preparing training");
                int noOfTaskInstances = 0;
                for (final IUserSession session : userSessions) {
                        for (final ITaskInstance taskInstance : session) {
                                Counter counter = equalTaskInstancesMap.getValue(taskInstance);

                                if (counter == null) {
                                        counter = new Counter();
                                        equalTaskInstancesMap.addSymbol(taskInstance, counter);
                                }

                                counter.count++;
                                instanceCountMap.put(taskInstance.getTask(), counter);

                                noOfTaskInstances++;
                        }
                }

                System.out.println("performing training of " + noOfTaskInstances
                                + " task instances");
                final Counter processedTaskInstances = new Counter();
                final int counterRecheckAt = noOfTaskInstances / 10; // recheck the
                                                                                                                                // maximum count
                                                                                                                                // after each
                // 10% of processed task instances
                for (final IUserSession session : userSessions) {
                        train(session, maxOrder, instanceCountMap, processedTaskInstances,
                                        counterRecheckAt);
                }

                updateKnownSymbols();
        }

}