Ignore:
Timestamp:
03/18/13 11:54:15 (11 years ago)
Author:
pharms
Message:
  • complete refactoring of task detection
  • many performance improvements in task detection
  • improved merging of sequences using Myers diff algorithm
File:
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java

    r1119 r1127  
    2121import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality; 
    2222import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager; 
     23import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 
     24import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; 
    2325import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; 
    2426import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder; 
    2527import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode; 
    2628import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory; 
    27 import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator; 
    2829import de.ugoe.cs.autoquest.usageprofiles.Trie; 
    2930import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor; 
     31import de.ugoe.cs.util.console.Console; 
    3032 
    3133/** 
    … …  
    3638 * @author Patrick Harms 
    3739 */ 
    38 class DefaultTaskSequenceDetectionRule implements TemporalRelationshipRule { 
     40class SequenceForTaskDetectionRule implements TemporalRelationshipRule { 
    3941     
    4042    /** 
    … …  
    5860     * </p> 
    5961     */ 
    60     private SymbolComparator<ITaskTreeNode> nodeComparator; 
     62    private TaskTreeNodeComparator nodeComparator; 
    6163 
    6264    /** 
    … …  
    6668     * </p> 
    6769     */ 
    68     DefaultTaskSequenceDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, 
    69                                      NodeEquality            minimalNodeEquality, 
    70                                      ITaskTreeNodeFactory    taskTreeNodeFactory, 
    71                                      ITaskTreeBuilder        taskTreeBuilder) 
     70    SequenceForTaskDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, 
     71                                 NodeEquality            minimalNodeEquality, 
     72                                 ITaskTreeNodeFactory    taskTreeNodeFactory, 
     73                                 ITaskTreeBuilder        taskTreeBuilder) 
    7274    { 
    7375        this.taskTreeNodeFactory = taskTreeNodeFactory; 
    … …  
    8385    @Override 
    8486    public String toString() { 
    85         return "DefaultTaskSequenceDetectionRule"; 
     87        return "SequenceForTaskDetectionRule"; 
    8688    } 
    8789 
    … …  
    101103            // the rule is always feasible as tasks may occur at any time 
    102104            RuleApplicationResult result = new RuleApplicationResult(); 
    103             result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); 
     105            result.setRuleApplicationStatus(RuleApplicationStatus.FEASIBLE); 
    104106            return result; 
    105107        } 
    106108 
    107         RuleApplicationData<ITaskTreeNode> appData = new RuleApplicationData<ITaskTreeNode>(parent); 
    108          
    109         appData.getStopWatch().start("whole rule application"); 
    110          
     109        List<ITaskTreeNode> children = parent.getChildren(); 
     110        List<ISequence> sessions = new LinkedList<ISequence>(); 
     111         
     112        for (ITaskTreeNode child : children) { 
     113            if (child instanceof ISequence) { 
     114                sessions.add((ISequence) child); 
     115            } 
     116            else { 
     117                Console.println("provided parent is no parent of sessions"); 
     118                return null; 
     119            } 
     120        } 
     121         
     122        RuleApplicationData appData = new RuleApplicationData(sessions); 
     123 
     124        boolean finished = false; 
     125         
     126        // this is the real rule application. Loop while something is replaced. 
    111127        do { 
    112             getSequencesOccuringMostOften(appData); 
    113              
    114             if ((appData.getLastFoundSequences().size() > 0) && 
    115                 (appData.getLastFoundSequences().getOccurrenceCount() > 1)) 
    116             { 
    117                 System.out.println("found " + appData.getLastFoundSequences().size() + 
    118                                    " tasks occurring " + 
    119                                    appData.getLastFoundSequences().getOccurrenceCount() + " times"); 
    120  
    121                 for (List<ITaskTreeNode> task : appData.getLastFoundSequences()) { 
    122                     // only tasks occurring more often than once are of interest 
    123                     appData.stopWatch.start("creating task sequences"); 
    124  
    125                     String taskId = "task " + RuleUtils.getNewId(); 
    126                     System.out.println(taskId + ": " + task); 
    127                      
    128                     appData.resetReplacementCounter(); 
    129                     createSequenceForTaskOccurrences(taskId, task, parent, appData); 
    130                      
    131                     if (appData.getReplacementCounter() < 
    132                         appData.getLastFoundSequences().getOccurrenceCount()) 
    133                     { 
    134                         System.out.println(taskId + ": replaced task only " + 
    135                                            appData.getReplacementCounter() + 
    136                                            " times instead of expected " + 
    137                                            appData.getLastFoundSequences().getOccurrenceCount()); 
    138                          
    139                     } 
    140  
    141                     appData.stopWatch.stop("creating task sequences"); 
     128            System.out.println(); 
     129             
     130            appData.getStopWatch().start("whole loop"); 
     131            detectAndReplaceIterations(appData); 
     132            //mergeEqualTasks(appData); 
     133            appData.getStopWatch().start("task replacement"); 
     134            detectAndReplaceTasks(appData); 
     135            appData.getStopWatch().stop("task replacement"); 
     136            appData.getStopWatch().stop("whole loop"); 
     137             
     138            //((TaskTreeNodeComparator) nodeComparator).getStopWatch().dumpStatistics(System.out); 
     139            //((TaskTreeNodeComparator) nodeComparator).getStopWatch().reset(); 
     140             
     141            appData.getStopWatch().dumpStatistics(System.out); 
     142            appData.getStopWatch().reset(); 
     143             
     144            finished = (appData.getReplacementCounter() == 0); 
     145        } 
     146        while (!finished); 
     147         
     148        System.out.println("created " + appData.getResult().getNewlyCreatedParentNodes().size() + 
     149                           " new parent nodes\n"); 
     150         
     151        if (appData.getResult().getNewlyCreatedParentNodes().size() > 0) { 
     152            appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED); 
     153        } 
     154         
     155        return appData.getResult(); 
     156    } 
     157 
     158    /** 
     159     * <p> 
     160     * TODO: comment 
     161     * </p> 
     162     * 
     163     * @param appData 
     164     */ 
     165    private void detectAndReplaceIterations(RuleApplicationData appData) { 
     166        System.out.print("detecting iterations"); 
     167        appData.getStopWatch().start("detecting iterations"); 
     168         
     169        List<ISequence> sessions = appData.getSessions(); 
     170        int foundIterations = 0; 
     171         
     172        for (ISequence session : sessions) { 
     173            foundIterations += detectAndReplaceIterations(session, appData); 
     174        } 
     175         
     176        appData.getStopWatch().stop("detecting iterations"); 
     177        System.out.println(" --> found " + foundIterations); 
     178    } 
     179 
     180    /** 
     181     * <p> 
     182     * TODO: comment 
     183     * </p> 
     184     * 
     185     * @param appData 
     186     */ 
     187    private int detectAndReplaceIterations(ISequence           session, 
     188                                           RuleApplicationData appData) 
     189    { 
     190        int count = 0; 
     191         
     192        TemporalRelationshipRule rule = new SimpleIterationDetectionRule 
     193            (nodeComparator, taskTreeNodeFactory, taskTreeBuilder); 
     194 
     195        RuleApplicationResult result = rule.apply(session, true); 
     196             
     197        if ((result != null) && (result.getNewlyCreatedParentNodes() != null)) { 
     198            for (ITaskTreeNode newParent : result.getNewlyCreatedParentNodes()) { 
     199                appData.getResult().addNewlyCreatedParentNode(newParent); 
     200                if (newParent instanceof IIteration) { 
     201                    count++; 
    142202                } 
    143203            } 
    144              
    145         } 
    146         while (appData.getLastFoundSequences().getOccurrenceCount() > 2); 
    147          
    148         appData.getStopWatch().stop("whole rule application"); 
    149         appData.getStopWatch().dumpStatistics(System.out); 
    150          
    151         if (appData.getResult().getNewlyCreatedParentNodes().size() > 0) { 
    152             appData.getResult().setRuleApplicationStatus 
    153                 (RuleApplicationStatus.RULE_APPLICATION_FINISHED); 
    154         } 
    155          
    156         System.out.println(appData.getResult().getNewlyCreatedParentNodes().size()); 
    157          
    158         for (ITaskTreeNode node : appData.getResult().getNewlyCreatedParentNodes()) { 
    159             for (ITaskTreeNode child : node.getChildren()) { 
    160                 System.out.println(child); 
    161             } 
    162             System.out.println(); 
    163         } 
    164          
    165         return appData.getResult(); 
     204        } 
     205         
     206        return count; 
     207    } 
     208 
     209//    /** 
     210//     * <p> 
     211//     * TODO: comment 
     212//     * </p> 
     213//     * 
     214//     * @param appData 
     215//     */ 
     216//    private void mergeEqualTasks(RuleApplicationData appData) { 
     217//        System.out.println("merging equal tasks"); 
     218//        appData.getStopWatch().start("merging equal tasks"); 
     219//         
     220//        int replacements = 0; 
     221//        List<ISequence> sessions = appData.getSessions(); 
     222//         
     223//        IdentityHashMap<ITaskTreeNode, ITaskTreeNode> replacedChildren = 
     224//            new IdentityHashMap<ITaskTreeNode, ITaskTreeNode>(); 
     225//         
     226//        for (int sessionIdx1 = 0; sessionIdx1 < sessions.size(); sessionIdx1++) { 
     227//            List<ITaskTreeNode> children1 = appData.getSessions().get(sessionIdx1).getChildren(); 
     228//            for (int childIdx1 = 0; childIdx1 < children1.size(); childIdx1++) { 
     229//                // this is the child of which we search equal other children to merge and to 
     230//                // replace with one single unique node 
     231//                ITaskTreeNode child1 = children1.get(childIdx1); 
     232//                 
     233//                if (replacedChildren.containsKey(child1)) { 
     234//                    continue; 
     235//                } 
     236//                 
     237//                // now search for all other children that are equal. Also record the session they 
     238//                // belong to as well as the index in that session 
     239//                List<ITaskTreeNode> equalChildren = new LinkedList<ITaskTreeNode>(); 
     240//                List<Integer> sessionIndexes = new LinkedList<Integer>(); 
     241//                List<Integer> childIndexes = new LinkedList<Integer>(); 
     242// 
     243//                // add all information about the current child 
     244//                equalChildren.add(child1); 
     245//                sessionIndexes.add(sessionIdx1); 
     246//                childIndexes.add(childIdx1); 
     247//                 
     248//                for (int sessionIdx2 = sessionIdx1; sessionIdx2 < sessions.size(); sessionIdx2++) { 
     249//                    List<ITaskTreeNode> children2 = 
     250//                          appData.getSessions().get(sessionIdx2).getChildren(); 
     251//                     
     252//                    int startIndex = (sessionIdx1 == sessionIdx2) ? childIdx1 + 1 : 0; 
     253//                     
     254//                    for (int childIdx2 = startIndex; childIdx2 < children2.size(); childIdx2++) { 
     255//                        ITaskTreeNode child2 = children2.get(childIdx2); 
     256//                         
     257//                        if ((child1 != child2) && (nodeComparator.equals(child1, child2))) { 
     258//                            // this is an equal child --> record its occurrence 
     259//                            equalChildren.add(child2); 
     260//                            sessionIndexes.add(sessionIdx2); 
     261//                            childIndexes.add(childIdx2); 
     262//                        } 
     263//                    } 
     264//                } 
     265//                 
     266//                // now merge the found children 
     267//                if (equalChildren.size() > 1) { 
     268//                    ITaskTreeNode replacement = 
     269//                        mergeVariantsOfTasks(child1.toString(), equalChildren); 
     270// 
     271//                    for (int i = 0; i < sessionIndexes.size(); i++) { 
     272//                        taskTreeBuilder.setChild(appData.getSessions().get(sessionIndexes.get(i)), 
     273//                                                 childIndexes.get(i), replacement); 
     274//                     
     275//                        replacements++; 
     276//                    } 
     277//                     
     278//                    // remember the replacement to prevent comparison of merged nodes 
     279//                    replacedChildren.put(replacement, replacement); 
     280//                     
     281//                    System.out.println 
     282//                        ("replaced " + sessionIndexes.size() + " occurrences of " + child1); 
     283//                } 
     284//            } 
     285//        } 
     286// 
     287//        appData.getStopWatch().stop("merging equal tasks"); 
     288//         
     289//        System.out.println("replaced " + replacements + " equal tasks with unique replacements"); 
     290//    } 
     291// 
     292    /** 
     293     * <p> 
     294     * TODO: comment 
     295     * </p> 
     296     * 
     297     * @param appData 
     298     */ 
     299    private void detectAndReplaceTasks(RuleApplicationData appData) { 
     300        System.out.println("detecting and replacing tasks"); 
     301        appData.getStopWatch().start("detecting tasks"); 
     302         
     303        getSequencesOccuringMostOften(appData); 
     304 
     305        appData.getStopWatch().stop("detecting tasks"); 
     306        appData.getStopWatch().start("replacing tasks"); 
     307         
     308        replaceSequencesOccurringMostOften(appData); 
     309         
     310        appData.getStopWatch().stop("replacing tasks"); 
     311        System.out.println("detected and replaced " + appData.getLastFoundTasks().size() + " tasks"); 
    166312    } 
    167313 
    … …  
    174320     * @return 
    175321     */ 
    176     private void getSequencesOccuringMostOften(RuleApplicationData<ITaskTreeNode> appData) { 
    177         System.out.println("determining most prominent tasks with a maximum of " + 
    178                            (appData.getLastFoundSequences().getOccurrenceCount() - 1) + 
    179                            " occurrences"); 
    180  
    181         Sequences<ITaskTreeNode> sequences; 
     322    private void getSequencesOccuringMostOften(RuleApplicationData appData) { 
     323        System.out.println("determining most prominent tasks"); 
     324 
     325        Tasks tasks; 
    182326        boolean createNewTrie = (appData.getLastTrie() == null) || 
    183327            appData.getReplacementCounter() > 0; // tree has changed 
    … …  
    188332            } 
    189333             
    190             /*PathDumper dumper = new PathDumper(); 
    191             trie.process(dumper); 
    192          
    193             dumper.dump();*/ 
    194          
    195             appData.getStopWatch().start("determining tasks"); 
    196  
    197             MaxCountAndLongestSequenceFinder finder = new MaxCountAndLongestSequenceFinder 
    198                   (appData.getLastFoundSequences().getOccurrenceCount() - 1); 
     334            MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder(); 
    199335            appData.getLastTrie().process(finder); 
    200336         
    201             sequences = finder.getFoundSequences(); 
     337            tasks = finder.getFoundTasks(); 
    202338             
    203339            createNewTrie = false; 
    204340             
    205             for (List<ITaskTreeNode> task : sequences) { 
     341            for (List<ITaskTreeNode> task : tasks) { 
    206342                if (task.size() >= appData.getTrainedSequenceLength()) { 
    207343                    // Trie must be recreated with a longer sequence length to be sure that 
    … …  
    212348                } 
    213349            } 
    214              
    215             appData.getStopWatch().stop("determining tasks"); 
    216350        } 
    217351        while (createNewTrie); 
    218352         
    219         appData.setLastFoundSequences(sequences); 
     353        appData.setLastFoundTasks(tasks); 
     354 
     355        System.out.println("found " + appData.getLastFoundTasks().size() + " tasks occurring " + 
     356                           appData.getLastFoundTasks().getOccurrenceCount() + " times"); 
    220357    } 
    221358 
    … …  
    228365     * @return 
    229366     */ 
    230     private void createNewTrie(RuleApplicationData<ITaskTreeNode> appData) { 
     367    private void createNewTrie(RuleApplicationData appData) { 
    231368        System.out.println("training trie with a maximum sequence length of " + 
    232369                           appData.getTrainedSequenceLength()); 
    … …  
    235372        appData.setLastTrie(new Trie<ITaskTreeNode>(nodeComparator)); 
    236373     
    237         trainTrie(appData.getTree(), appData); 
     374        List<ISequence> sessions = appData.getSessions(); 
     375         
     376        for (ISequence session : sessions) { 
     377            trainTrie(session, appData); 
     378        } 
     379         
    238380        appData.getStopWatch().stop("training trie"); 
    239381    } 
    … …  
    247389     * @param parent 
    248390     */ 
    249     private void trainTrie(ITaskTreeNode parent, RuleApplicationData<ITaskTreeNode> appData) { 
    250         // prevent training of already replaces sequences as those shall not be replaced anymore 
    251         if (!appData.getResult().getNewlyCreatedParentNodes().contains(parent)) { 
    252             List<ITaskTreeNode> children = parent.getChildren(); 
    253          
    254             if ((children != null) && (children.size() > 0)) { 
     391    private void trainTrie(ISequence session, RuleApplicationData appData) { 
     392        List<ITaskTreeNode> children = session.getChildren(); 
     393         
     394        if ((children != null) && (children.size() > 0)) { 
     395            appData.getLastTrie().train(children, appData.getTrainedSequenceLength()); 
     396        } 
     397    } 
     398 
     399    /** 
     400     * <p> 
     401     * TODO: comment 
     402     * </p> 
     403     * 
     404     * @param appData 
     405     */ 
     406    private void replaceSequencesOccurringMostOften(RuleApplicationData appData) { 
     407        appData.resetReplacementCounter(); 
     408 
     409        if ((appData.getLastFoundTasks().size() > 0) && 
     410            (appData.getLastFoundTasks().getOccurrenceCount() > 1)) 
     411        { 
     412            System.out.println("replacing tasks occurrences with merged variants of all versions"); 
     413 
     414            for (List<ITaskTreeNode> task : appData.getLastFoundTasks()) { 
     415                String taskId = "task " + RuleUtils.getNewId(); 
     416                System.out.println("replacing " + taskId + ": " + task); 
     417 
     418                appData.clearTaskOccurrences(); 
     419                determineVariantsOfTaskOccurrences(task, appData.getSessions(), appData); 
    255420                 
    256                 /*System.out.println(); 
    257                 for (int i = 0; i < children.size(); i++) { 
    258                     System.out.println(children.get(i)); 
    259                 }*/ 
     421                appData.getStopWatch().start("merging task nodes"); 
     422                ITaskTreeNode taskReplacement = mergeVariantsOfTaskOccurrence(taskId, appData); 
     423                appData.getStopWatch().stop("merging task nodes"); 
     424 
     425                appData.resetReplacementCounter(); 
     426                replaceTaskOccurrences(task, taskReplacement, appData.getSessions(), appData); 
     427 
     428                if (appData.getReplacementCounter() > 0) { 
     429                    appData.getResult().addNewlyCreatedParentNode(taskReplacement); 
     430                } 
     431 
     432                if (appData.getReplacementCounter() < 
     433                    appData.getLastFoundTasks().getOccurrenceCount()) 
     434                { 
     435                    System.out.println(taskId + ": replaced task only " + 
     436                                       appData.getReplacementCounter() + 
     437                                       " times instead of expected " + 
     438                                       appData.getLastFoundTasks().getOccurrenceCount()); 
     439                } 
     440            } 
     441        } 
     442         
     443    } 
     444 
     445    /** 
     446     * <p> 
     447     * TODO: comment 
     448     * </p> 
     449     * 
     450     * @param tree 
     451     */ 
     452    private void determineVariantsOfTaskOccurrences(List<ITaskTreeNode> task, 
     453                                                    List<ISequence>     sessions, 
     454                                                    RuleApplicationData appData) 
     455    { 
     456        for (ISequence session : sessions) { 
     457            int index = -1; 
    260458                 
    261                 appData.getLastTrie().train(children, appData.getTrainedSequenceLength()); 
    262              
    263                 for (ITaskTreeNode child : children) { 
    264                     trainTrie(child, appData); 
     459            List<ITaskTreeNode> children = session.getChildren(); 
     460 
     461            do { 
     462                index = getSubListIndex(children, task, ++index); 
     463 
     464                if (index > -1) { 
     465                    ISequence taskOccurrence = RuleUtils.getSubSequenceInRange 
     466                            (session, index, index + task.size() - 1, null, 
     467                             taskTreeNodeFactory, taskTreeBuilder); 
     468 
     469                    appData.addTaskOccurrence(taskOccurrence); 
     470 
     471                    // let the index point to the last element the belongs the identified occurrence 
     472                    index += task.size() - 1; 
    265473                } 
    266474            } 
     475            while (index > -1); 
     476        } 
     477    } 
     478 
     479    /** 
     480     * <p> 
     481     * TODO: comment 
     482     * </p> 
     483     * 
     484     * @param appData 
     485     * @return 
     486     */ 
     487    private ITaskTreeNode mergeVariantsOfTaskOccurrence(String              taskId, 
     488                                                        RuleApplicationData appData) 
     489    { 
     490        return mergeVariantsOfTasks(taskId, appData.getTaskOccurrences()); 
     491    } 
     492 
     493    /** 
     494     * <p> 
     495     * TODO: comment 
     496     * </p> 
     497     * 
     498     * @param appData 
     499     * @return 
     500     */ 
     501    private ITaskTreeNode mergeVariantsOfTasks(String description, List<ITaskTreeNode> variants) { 
     502        // merge but preserve lexically distinct variants 
     503        TaskTreeNodeMerger merger = new TaskTreeNodeMerger 
     504            (taskTreeNodeFactory, taskTreeBuilder, nodeComparator); 
     505         
     506        merger.mergeTaskNodes(variants); 
     507         
     508        if (variants.size() == 1) { 
     509            ITaskTreeNode replacement = variants.get(0); 
     510            taskTreeBuilder.setDescription(replacement, description); 
     511            return replacement; 
     512        } 
     513        else { 
     514            ISelection selection = taskTreeNodeFactory.createNewSelection(); 
     515            taskTreeBuilder.setDescription(selection, "variants of task " + description); 
     516             
     517            for (ITaskTreeNode variant : variants) { 
     518                taskTreeBuilder.addChild(selection, variant); 
     519            } 
     520             
     521            return selection; 
    267522        } 
    268523    } 
    … …  
    279534     * @param result 
    280535     */ 
    281     private void createSequenceForTaskOccurrences(String                             taskId, 
    282                                                   List<ITaskTreeNode>                task, 
    283                                                   ITaskTreeNode                      parent, 
    284                                                   RuleApplicationData<ITaskTreeNode> appData) 
     536    private void replaceTaskOccurrences(List<ITaskTreeNode> task, 
     537                                        ITaskTreeNode       replacement, 
     538                                        List<ISequence>     sessions, 
     539                                        RuleApplicationData appData) 
    285540    { 
    286         List<ITaskTreeNode> children = parent.getChildren(); 
    287          
    288         if ((children == null) || (children.size() == 0)) { 
    289             return; 
    290         } 
    291          
    292         // first traverse the children 
    293         for (ITaskTreeNode child : children) { 
    294             createSequenceForTaskOccurrences(taskId, task, child, appData); 
    295         } 
    296          
    297541        // now check the children themselves for an occurrence of the task 
    298         int index = -1; 
    299          
    300         do { 
    301             index = getSubListIndex(children, task, ++index); 
    302              
    303             if (index > -1) { 
    304                 if (task.size() < children.size()) { 
    305                     ISequence sequence = RuleUtils.createNewSubSequenceInRange 
    306                         (parent, index, index + task.size() - 1, taskId, 
    307                          taskTreeNodeFactory, taskTreeBuilder); 
    308                      
    309                     appData.getResult().addNewlyCreatedParentNode(sequence); 
    310                     appData.incrementReplacementCounter(); 
    311                   
    312                     children = parent.getChildren(); 
    313                 } 
    314                 else { 
    315                     // the whole list of children is an occurrence of this task. Just set the 
    316                     // description of the parent and break up 
    317                     String description = parent.getDescription(); 
    318                      
    319                     if ((description != null) && (description.length() > 0)) { 
    320                         description += "; " + taskId; 
     542        for (int i = 0; i < sessions.size(); i++) { 
     543            ISequence session = sessions.get(i); 
     544             
     545            int index = -1; 
     546         
     547            List<ITaskTreeNode> children = session.getChildren(); 
     548 
     549            do { 
     550                index = getSubListIndex(children, task, ++index); 
     551 
     552                if (index > -1) { 
     553                    if ((!(replacement instanceof ISequence)) || 
     554                        (task.size() < children.size())) 
     555                    { 
     556                        for (int j = index; j < index + task.size(); j++) { 
     557                            taskTreeBuilder.removeChild(session, index); 
     558                        } 
     559 
     560                        taskTreeBuilder.addChild(session, index, replacement); 
     561                        appData.incrementReplacementCounter(); 
     562 
     563                        children = session.getChildren(); 
    321564                    } 
    322565                    else { 
    323                         description = taskId; 
     566                        // the whole list of children is an occurrence of this task. So ask the 
     567                        // caller of the method to replace the whole node 
     568                        sessions.set(i, (ISequence) replacement); 
     569                        appData.incrementReplacementCounter(); 
     570                        break; 
    324571                    } 
    325                      
    326                     taskTreeBuilder.setDescription(parent, description); 
    327                     break; 
    328572                } 
    329573            } 
    330         } 
    331         while (index > -1); 
     574            while (index > -1); 
     575        } 
    332576    } 
    333577 
    … …  
    356600                    break; 
    357601                } 
    358                 else if (!nodeComparator.equals(subList.get(j), list.get(i + j))){ 
    359                     throw new RuntimeException("comparator not commutative"); 
    360                 } 
    361602            } 
    362603             
    … …  
    377618     * @author Patrick Harms 
    378619     */ 
    379     private class MaxCountAndLongestSequenceFinder implements TrieProcessor<ITaskTreeNode> { 
    380          
    381         /** 
    382          *  
    383          */ 
    384         private int maxCount; 
     620    private class MaxCountAndLongestTasksFinder implements TrieProcessor<ITaskTreeNode> { 
    385621         
    386622        /** 
    … …  
    392628         *  
    393629         */ 
    394         private List<List<ITaskTreeNode>> foundSequences = new LinkedList<List<ITaskTreeNode>>(); 
     630        private List<List<ITaskTreeNode>> foundTasks = new LinkedList<List<ITaskTreeNode>>(); 
    395631 
    396632        /** 
    … …  
    401637         * @param maxCount 
    402638         */ 
    403         public MaxCountAndLongestSequenceFinder(int maxCount) { 
     639        public MaxCountAndLongestTasksFinder() { 
    404640            super(); 
    405             this.maxCount = maxCount; 
    406641            this.currentCount = 0; 
    407642        } 
    … …  
    411646         */ 
    412647        @Override 
    413         public TrieProcessor.Result process(List<ITaskTreeNode> sequence, int count) { 
    414             if (sequence.size() < 2) { 
     648        public TrieProcessor.Result process(List<ITaskTreeNode> task, int count) { 
     649            if (task.size() < 2) { 
    415650                // ignore single nodes 
    416651                return TrieProcessor.Result.CONTINUE; 
    … …  
    422657            } 
    423658 
    424             if (count > this.maxCount) { 
    425                 // ignore sequences that occur too often 
    426                 return TrieProcessor.Result.CONTINUE; 
    427             } 
    428              
    429659            if (this.currentCount > count) { 
    430660                // ignore this children of this node, as they may have only smaller counts than 
    431                 // the already found sequences 
     661                // the already found tasks 
    432662                return TrieProcessor.Result.SKIP_NODE; 
    433663            } 
    434664             
    435665            if (this.currentCount < count) { 
    436                 // the provided sequence occurs more often that all sequences found so far. 
    437                 // clear all found sequences and use the new count as the one searched for 
    438                 foundSequences.clear(); 
     666                // the provided task occurs more often that all tasks found so far. 
     667                // clear all found tasks and use the new count as the one searched for 
     668                foundTasks.clear(); 
    439669                this.currentCount = count; 
    440670            } 
    441671             
    442672            if (this.currentCount == count) { 
    443                 // the sequence is of interest. Sort it into the other found sequences so that 
     673                // the task is of interest. Sort it into the other found tasks so that 
    444674                // the longest come first 
    445675                boolean added = false; 
    446                 for (int i = 0; i < foundSequences.size(); i++) { 
    447                     if (foundSequences.get(i).size() < sequence.size()) { 
     676                for (int i = 0; i < foundTasks.size(); i++) { 
     677                    if (foundTasks.get(i).size() < task.size()) { 
    448678                        // defensive copy 
    449                         foundSequences.add(i, new LinkedList<ITaskTreeNode>(sequence)); // defensive copy 
     679                        foundTasks.add(i, new LinkedList<ITaskTreeNode>(task)); // defensive copy 
    450680                        added = true; 
    451681                        break; 
    … …  
    454684                 
    455685                if (!added) { 
    456                     foundSequences.add(new LinkedList<ITaskTreeNode>(sequence)); // defensive copy 
     686                    foundTasks.add(new LinkedList<ITaskTreeNode>(task)); // defensive copy 
    457687                } 
    458688            } 
    … …  
    468698         * @return 
    469699         */ 
    470         public Sequences<ITaskTreeNode> getFoundSequences() { 
     700        public Tasks getFoundTasks() { 
    471701            removePermutationsOfShorterTasks(); 
    472             return new Sequences<ITaskTreeNode>(currentCount, foundSequences); 
     702            return new Tasks(currentCount, foundTasks); 
    473703        } 
    474704 
    … …  
    482712            // now iterate the sorted list and for each task remove all other tasks that are shorter 
    483713            // (i.e. come later in the sorted list) and that represent a subpart of the task 
    484             for (int i = 0; i < foundSequences.size(); i++) { 
    485                 for (int j = i + 1; j < foundSequences.size();) { 
    486                     if (foundSequences.get(j).size() < foundSequences.get(i).size()) { 
     714            for (int i = 0; i < foundTasks.size(); i++) { 
     715                for (int j = i + 1; j < foundTasks.size();) { 
     716                    if (foundTasks.get(j).size() < foundTasks.get(i).size()) { 
    487717                        // found a task that is a potential subtask. Check for this and remove the 
    488718                        // subtask if needed 
    489                         List<ITaskTreeNode> longTask = foundSequences.get(i); 
    490                         List<ITaskTreeNode> shortTask = foundSequences.get(j); 
     719                        List<ITaskTreeNode> longTask = foundTasks.get(i); 
     720                        List<ITaskTreeNode> shortTask = foundTasks.get(j); 
    491721                         
    492722                        if (getSubListIndex(longTask, shortTask, 0) > -1) { 
    493                             foundSequences.remove(j); 
     723                            foundTasks.remove(j); 
    494724                        } 
    495725                        else { 
    … …  
    509739     *  
    510740     */ 
    511     private class RuleApplicationData<T> { 
    512          
    513         /** 
    514          *  
    515          */ 
    516         private T tree; 
     741    private class RuleApplicationData { 
     742         
     743        /** 
     744         *  
     745         */ 
     746        private List<ISequence> sessions; 
     747         
     748        /** 
     749         *  
     750         */ 
     751        private Trie<ITaskTreeNode> lastTrie; 
     752         
     753        /** 
     754         * default and minimum trained sequence length is 3 
     755         */ 
     756        private int trainedSequenceLength = 3; 
     757         
     758        /** 
     759         *  
     760         */ 
     761        private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null); 
     762         
     763        /** 
     764         *  
     765         */ 
     766        private List<ITaskTreeNode> taskOccurrences = new LinkedList<ITaskTreeNode>(); 
     767         
     768        /** 
     769         *  
     770         */ 
     771        private int replacementCounter; 
    517772         
    518773        /** 
    … …  
    524779         *  
    525780         */ 
    526         private Sequences<T> lastFoundSequences = new Sequences<T>(Integer.MAX_VALUE, null); 
    527          
    528         /** 
    529          *  
    530          */ 
    531         private Trie<T> lastTrie; 
    532          
    533         /** 
    534          * default and minimum trained sequence length is 3 
    535          */ 
    536         private int trainedSequenceLength = 3; 
    537          
    538         /** 
    539          *  
    540          */ 
    541         private int replacementCounter; 
    542          
    543         /** 
    544          *  
    545          */ 
    546781        private StopWatch stopWatch = new StopWatch(); 
    547782         
    … …  
    549784         *  
    550785         */ 
    551         private RuleApplicationData(T tree) { 
    552             this.tree = tree; 
    553         } 
    554  
    555         /** 
    556          * @return the lastFoundSequences 
    557          */ 
    558         private Sequences<T> getLastFoundSequences() { 
    559             return lastFoundSequences; 
    560         } 
    561  
    562         /** 
    563          * @param lastFoundSequences the lastFoundSequences to set 
    564          */ 
    565         private void setLastFoundSequences(Sequences<T> lastFoundSequences) { 
    566             this.lastFoundSequences = lastFoundSequences; 
     786        private RuleApplicationData(List<ISequence> sessions) { 
     787            this.sessions = sessions; 
     788        } 
     789 
     790        /** 
     791         * @return the tree 
     792         */ 
     793        private List<ISequence> getSessions() { 
     794            return sessions; 
     795        } 
     796 
     797        /** 
     798         * @param lastTrie the lastTrie to set 
     799         */ 
     800        private void setLastTrie(Trie<ITaskTreeNode> lastTrie) { 
     801            this.lastTrie = lastTrie; 
    567802        } 
    568803 
    … …  
    570805         * @return the lastTrie 
    571806         */ 
    572         private Trie<T> getLastTrie() { 
     807        private Trie<ITaskTreeNode> getLastTrie() { 
    573808            return lastTrie; 
     809        } 
     810 
     811        /** 
     812         * @param trainedSequenceLength the trainedSequenceLength to set 
     813         */ 
     814        private void setTrainedSequenceLength(int trainedSequenceLength) { 
     815            this.trainedSequenceLength = trainedSequenceLength; 
    574816        } 
    575817 
    … …  
    582824 
    583825        /** 
    584          * @param trainedSequenceLength the trainedSequenceLength to set 
    585          */ 
    586         private void setTrainedSequenceLength(int trainedSequenceLength) { 
    587             this.trainedSequenceLength = trainedSequenceLength; 
    588         } 
    589  
    590         /** 
    591          * @param lastTrie the lastTrie to set 
    592          */ 
    593         private void setLastTrie(Trie<T> lastTrie) { 
    594             this.lastTrie = lastTrie; 
    595         } 
    596  
    597         /** 
    598          * @return the tree 
    599          */ 
    600         private T getTree() { 
    601             return tree; 
    602         } 
    603  
     826         * @param lastFoundSequences the lastFoundSequences to set 
     827         */ 
     828        private void setLastFoundTasks(Tasks lastFoundSequences) { 
     829            this.lastFoundTasks = lastFoundSequences; 
     830        } 
     831 
     832        /** 
     833         * @return the lastFoundSequences 
     834         */ 
     835        private Tasks getLastFoundTasks() { 
     836            return lastFoundTasks; 
     837        } 
     838 
     839        /** 
     840         * @return the taskOccurrences 
     841         */ 
     842        private void clearTaskOccurrences() { 
     843            taskOccurrences.clear(); 
     844        } 
     845 
     846        /** 
     847         * @return the taskOccurrences 
     848         */ 
     849        private void addTaskOccurrence(ITaskTreeNode taskOccurrence) { 
     850            taskOccurrences.add(taskOccurrence); 
     851        } 
     852 
     853        /** 
     854         * @return the taskOccurrences 
     855         */ 
     856        private List<ITaskTreeNode> getTaskOccurrences() { 
     857            return taskOccurrences; 
     858        } 
     859 
     860        /** 
     861         * 
     862         */ 
     863        private void resetReplacementCounter() { 
     864            replacementCounter = 0; 
     865        } 
     866 
     867        /** 
     868         * 
     869         */ 
     870        private void incrementReplacementCounter() { 
     871            replacementCounter++; 
     872        } 
     873 
     874        /** 
     875         * 
     876         */ 
     877        private int getReplacementCounter() { 
     878            return replacementCounter; 
     879        } 
     880         
    604881        /** 
    605882         * @return the result 
    … …  
    616893        } 
    617894 
    618         /** 
    619          * 
    620          */ 
    621         private void resetReplacementCounter() { 
    622             replacementCounter = 0; 
    623         } 
    624  
    625         /** 
    626          * 
    627          */ 
    628         private void incrementReplacementCounter() { 
    629             replacementCounter++; 
    630         } 
    631  
    632         /** 
    633          * 
    634          */ 
    635         private int getReplacementCounter() { 
    636             return replacementCounter; 
    637         } 
    638895    } 
    639896     
    … …  
    646903     * @author Patrick Harms 
    647904     */ 
    648     private class Sequences<T> implements Iterable<List<T>> { 
     905    private class Tasks implements Iterable<List<ITaskTreeNode>> { 
    649906         
    650907        /** 
    … …  
    656913         *  
    657914         */ 
    658         private List<List<T>> sequences; 
     915        private List<List<ITaskTreeNode>> sequences; 
    659916 
    660917        /** 
    … …  
    666923         * @param sequences 
    667924         */ 
    668         private Sequences(int occurrenceCount, List<List<T>> sequences) { 
     925        private Tasks(int occurrenceCount, List<List<ITaskTreeNode>> sequences) { 
    669926            super(); 
    670927            this.occurrenceCount = occurrenceCount; 
    … …  
    702959         */ 
    703960        @Override 
    704         public Iterator<List<T>> iterator() { 
     961        public Iterator<List<ITaskTreeNode>> iterator() { 
    705962            return this.sequences.iterator(); 
    706963        } 
Note: See TracChangeset for help on using the changeset viewer.