Changeset 1747 for branches


Ignore:
Timestamp:
09/16/14 17:48:28 (10 years ago)
Author:
rkrimmel
Message:

I did it, i fixed ALL the bugs.

Location:
branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees
Files:
1 added
5 edited

Legend:

Unmodified
Added
Removed

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java

    r1742 r1747  
    149149         * Task id sum. Used for comparing and sorting matches 
    150150         * 
    151          * @return  
     151         * @return the int 
    152152         */ 
    153153        public int taskIdSum() { 
    … …  
    161161        } 
    162162         
    163         public Match cloneWithoutOccurences() throws CloneNotSupportedException  { 
    164                 Match result; 
    165                 result = (Match) this.clone(); 
    166                 result.occurrences.clear(); 
     163         
     164         
     165        /** 
     166         * Clone without occurrences. 
     167         * 
     168         * @return the match 
     169         * @throws CloneNotSupportedException the clone not supported exception 
     170         */ 
     171        public Match cloneWithoutOccurrences()   { 
     172                Match result = new Match(); 
     173                result.setFirstSequence(this.getFirstSequence()); 
     174                result.setSecondSequence(this.getSecondSequence()); 
    167175                return result; 
    168176        } 

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java

    r1734 r1747  
    22 *  
    33 */ 
     4 
    45package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; 
    56 
    … …  
    1314 */ 
    1415public class NumberSequence implements Serializable { 
    15          
    16         /** The Constant serialVersionUID. */ 
    17         private static final long serialVersionUID = -4604570107534055589L; 
    18          
    19         /** The sequence. */ 
    20         private int[] sequence; 
    21          
    22         /** The id. */ 
    23         private int id; 
    24  
    25         /** 
    26          * Instantiates a new number sequence. 
    27          * 
    28          * @param size the size 
    29          */ 
    30         public NumberSequence(int size) { 
    31  
    32                 sequence = new int[size]; 
    33         } 
    34  
    35         // Searching occurrences of pattern 
    36         /** 
    37          * Contains pattern. 
    38          * 
    39          * @param pattern the pattern 
    40          * @return the linked list 
    41          */ 
    42         public LinkedList<Integer> containsPattern(Match pattern) { 
    43                 final LinkedList<Integer> result = new LinkedList<Integer>(); 
    44                 int i = 0; 
    45                 final int[] pat1 = pattern.getFirstSequence().getSequence(); 
    46                 final int[] pat2 = pattern.getSecondSequence().getSequence(); 
    47  
    48                 while (i < sequence.length) { 
    49                         if (matches(i, pat1, pat2, 0, 0, false, false, false, false, false)) { 
    50                                 result.add(i); 
    51                         } 
    52                         i++; 
    53                 } 
    54                 return result; 
    55         } 
    56  
    57         /** 
    58          * Equals. 
    59          * 
    60          * @param n the n 
    61          * @return true, if successful 
    62          */ 
    63         public boolean equals(NumberSequence n) { 
    64                 final int[] seq = n.getSequence(); 
    65                 if (n.size() != this.size()) { 
    66                         return false; 
    67                 } 
    68                 for (int i = 0; i < n.size(); i++) { 
    69                         if (seq[i] != this.sequence[i]) { 
    70                                 return false; 
    71                         } 
    72                 } 
    73                 return true; 
    74         } 
    75  
    76         // Returns the number of times event occurs in this sequence 
    77         /** 
    78          * Event count. 
    79          * 
    80          * @param event the event 
    81          * @return the int 
    82          */ 
    83         public int eventCount(int event) { 
    84                 int count = 0; 
    85                 for (int i = 0; i < sequence.length; i++) { 
    86                         if (sequence[i] == event) { 
    87                                 count++; 
    88                         } 
    89                 } 
    90                 return count; 
    91         } 
    92  
    93         /** 
    94          * Gets the id. 
    95          * 
    96          * @return the id 
    97          */ 
    98         public int getId() { 
    99                 return id; 
    100         } 
    101  
    102         /** 
    103          * Gets the sequence. 
    104          * 
    105          * @return the sequence 
    106          */ 
    107         public int[] getSequence() { 
    108                 return sequence; 
    109         } 
    110  
    111         // Recursive check if sequence contains pattern at position i 
    112         /** 
    113          * Matches. 
    114          * 
    115          * @param i the i 
    116          * @param p1 the p1 
    117          * @param p2 the p2 
    118          * @param ip1 the ip1 
    119          * @param ip2 the ip2 
    120          * @param jumped1 the jumped1 
    121          * @param jumped2 the jumped2 
    122          * @param hadSelection the had selection 
    123          * @param matchseq1 the matchseq1 
    124          * @param matchseq2 the matchseq2 
    125          * @return true, if successful 
    126          */ 
    127         private boolean matches(int i, int[] p1, int[] p2, int ip1, int ip2, 
    128                         boolean jumped1, // True if there was a gap in Sequence 1 of the 
    129                                                                 // pattern 
    130                         boolean jumped2, // True if there was a gap in Sequence 2 of the 
    131                                                                 // pattern 
    132                         boolean hadSelection, // True if the last match was a selection 
    133                         boolean matchseq1, boolean matchseq2) { 
    134  
    135                 if (p1.length == ip1) { 
    136                         return true; 
    137                 } 
    138                 if (p2.length == ip2) { 
    139                         return true; 
    140                 } 
    141                 if (i == sequence.length) { 
    142                         return false; 
    143                 } 
    144  
    145                 final boolean foundselection = (!(p1[ip1] == p2[ip2]) && !((p1[ip1] == -1) || (p2[ip2] == -1))); 
    146                 final boolean matchInFirstPattern = (p1[ip1] == sequence[i]); 
    147                 final boolean matchInSecondPattern = (p2[ip2] == sequence[i]); 
    148  
    149                 if (foundselection && hadSelection) { 
    150                         if ((matchInFirstPattern && matchseq1) 
    151                                         || (matchInSecondPattern && matchseq2)) { 
    152                                 if (jumped1) { 
    153                                         return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, 
    154                                                         false, foundselection, matchInFirstPattern, 
    155                                                         matchInSecondPattern); 
    156                                 } 
    157                                 if (jumped2) { 
    158                                         return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, 
    159                                                         false, foundselection, matchInFirstPattern, 
    160                                                         matchInSecondPattern); 
    161                                 } 
    162                                 return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, 
    163                                                 foundselection, matchInFirstPattern, 
    164                                                 matchInSecondPattern); 
    165                         } else { 
    166                                 return false; 
    167                         } 
    168                 } 
    169  
    170                 if ((matchInFirstPattern || matchInSecondPattern) && jumped1) { 
    171                         return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, false, 
    172                                         foundselection, matchInFirstPattern, matchInSecondPattern); 
    173                 } 
    174                 if ((matchInFirstPattern || matchInSecondPattern) && jumped2) { 
    175                         return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, false, 
    176                                         foundselection, matchInFirstPattern, matchInSecondPattern); 
    177                 } 
    178                 if (matchInFirstPattern || matchInSecondPattern) { 
    179                         return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, 
    180                                         foundselection, matchInFirstPattern, matchInSecondPattern); 
    181                 } 
    182                 if (p1[ip1] == -1) { 
    183                         return matches(i, p1, p2, ip1 + 1, ip2, true, false, false, false, 
    184                                         false); 
    185                 } 
    186                 if (p2[ip2] == -1) { 
    187                         return matches(i, p1, p2, ip1, ip2 + 1, false, true, false, false, 
    188                                         false); 
    189                 } 
    190  
    191                 return false; 
    192         } 
    193  
    194         /** 
    195          * Prints the sequence. 
    196          */ 
    197         public void printSequence() { 
    198                 for (int i = 0; i < sequence.length; i++) { 
    199                         System.out.format("%5d", sequence[i]); 
    200                 } 
    201                 System.out.println(); 
    202         } 
    203  
    204         /** 
    205          * Sets the id. 
    206          * 
    207          * @param id the new id 
    208          */ 
    209         public void setId(int id) { 
    210                 this.id = id; 
    211         } 
    212  
    213         /** 
    214          * Sets the sequence. 
    215          * 
    216          * @param sequence the new sequence 
    217          */ 
    218         public void setSequence(int[] sequence) { 
    219                 this.sequence = sequence; 
    220         } 
    221  
    222         /** 
    223          * Shuffle. 
    224          * 
    225          * @return the number sequence 
    226          */ 
    227         public NumberSequence shuffle() { 
    228                 final NumberSequence result = new NumberSequence(sequence.length); 
    229                 result.setId(getId()); 
    230                 result.setSequence(this.sequence); 
    231                 final Random rgen = new Random(); 
    232  
    233                 for (int i = 0; i < result.sequence.length; i++) { 
    234                         final int randomPosition = rgen.nextInt(result.sequence.length); 
    235                         final int temp = result.sequence[i]; 
    236                         result.sequence[i] = result.sequence[randomPosition]; 
    237                         result.sequence[randomPosition] = temp; 
    238                 } 
    239                 return result; 
    240  
    241         } 
    242  
    243         /** 
    244          * Size. 
    245          * 
    246          * @return the int 
    247          */ 
    248         public int size() { 
    249                 return sequence.length; 
    250         } 
     16 
     17    /** The Constant serialVersionUID. */ 
     18    private static final long serialVersionUID = -4604570107534055589L; 
     19 
     20    /** The sequence. */ 
     21    private int[] sequence; 
     22 
     23    /** The id. */ 
     24    private int id; 
     25 
     26    /** 
     27     * Instantiates a new number sequence. 
     28     * 
     29     * @param size 
     30     *            the size 
     31     */ 
     32    public NumberSequence(int size) { 
     33 
     34        sequence = new int[size]; 
     35    } 
     36 
     37    // Searching occurrences of pattern 
     38    /** 
     39     * Contains pattern. 
     40     * 
     41     * @param pattern 
     42     *            the pattern 
     43     * @return the linked list 
     44     */ 
     45    public LinkedList<Integer> containsPattern(Match pattern) { 
     46        final LinkedList<Integer> result = new LinkedList<Integer>(); 
     47        int i = 0; 
     48        final int[] pat1 = pattern.getFirstSequence().getSequence(); 
     49        final int[] pat2 = pattern.getSecondSequence().getSequence(); 
     50 
     51        while (i < sequence.length) { 
     52            if (matches(i, pat1, pat2, 0, 0, false, false, false, false, false)) { 
     53                result.add(i); 
     54            } 
     55            i++; 
     56        } 
     57        return result; 
     58    } 
     59 
     60    /** 
     61     * Equals. 
     62     * 
     63     * @param n 
     64     *            the n 
     65     * @return true, if successful 
     66     */ 
     67    public boolean equals(NumberSequence n) { 
     68        final int[] seq = n.getSequence(); 
     69        if (n.size() != this.size()) { 
     70            return false; 
     71        } 
     72        for (int i = 0; i < n.size(); i++) { 
     73            if (seq[i] != this.sequence[i]) { 
     74                return false; 
     75            } 
     76        } 
     77        return true; 
     78    } 
     79 
     80    // Returns the number of times event occurs in this sequence 
     81    /** 
     82     * Event count. 
     83     * 
     84     * @param event 
     85     *            the event 
     86     * @return the int 
     87     */ 
     88    public int eventCount(int event) { 
     89        int count = 0; 
     90        for (int i = 0; i < sequence.length; i++) { 
     91            if (sequence[i] == event) { 
     92                count++; 
     93            } 
     94        } 
     95        return count; 
     96    } 
     97 
     98    /** 
     99     * Gets the id. 
     100     * 
     101     * @return the id 
     102     */ 
     103    public int getId() { 
     104        return id; 
     105    } 
     106 
     107    /** 
     108     * Gets the sequence. 
     109     * 
     110     * @return the sequence 
     111     */ 
     112    public int[] getSequence() { 
     113        return sequence; 
     114    } 
     115 
     116    // Recursive check if sequence contains pattern at position i 
     117    /** 
     118     * Matches. 
     119     * 
     120     * @param i 
     121     *            the position in the sequence 
     122     * @param p1 
     123     *            the p1 
     124     * @param p2 
     125     *            the p2 
     126     * @param ip1 
     127     *            the ip1 
     128     * @param ip2 
     129     *            the ip2 
     130     * @param jumped1 
     131     *            the jumped1 
     132     * @param jumped2 
     133     *            the jumped2 
     134     * @param hadSelection 
     135     *            the had selection 
     136     * @param matchseq1 
     137     *            the matchseq1 
     138     * @param matchseq2 
     139     *            the matchseq2 
     140     * @return true, if successful 
     141     */ 
     142    private boolean matches(int i, int[] p1, int[] p2, int ip1, int ip2, boolean jumped1, // True if 
     143                                                                                          // there 
     144                                                                                          // was a 
     145                                                                                          // gap in 
     146                                                                                          // Sequence 
     147                                                                                          // 1 of 
     148                                                                                          // the 
     149                                                                                          // pattern 
     150                            boolean jumped2, // True if there was a gap in Sequence 2 of the 
     151                                             // pattern 
     152                            boolean hadSelection, // True if the last match was a selection 
     153                            boolean matchseq1, 
     154                            boolean matchseq2) 
     155    { 
     156 
     157        if (p1.length == ip1) { 
     158            return true; 
     159        } 
     160        if (p2.length == ip2) { 
     161            return true; 
     162        } 
     163        if (i == sequence.length) { 
     164            return false; 
     165        } 
     166 
     167        final boolean foundselection = 
     168            (!(p1[ip1] == p2[ip2]) && !((p1[ip1] == -1) || (p2[ip2] == -1))); 
     169        final boolean matchInFirstPattern = (p1[ip1] == sequence[i]); 
     170        final boolean matchInSecondPattern = (p2[ip2] == sequence[i]); 
     171 
     172        if (foundselection && hadSelection) { 
     173            if ((matchInFirstPattern && matchseq1) || (matchInSecondPattern && matchseq2)) { 
     174                if (jumped1) { 
     175                    return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, false, foundselection, 
     176                                   matchInFirstPattern, matchInSecondPattern); 
     177                } 
     178                if (jumped2) { 
     179                    return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, false, foundselection, 
     180                                   matchInFirstPattern, matchInSecondPattern); 
     181                } 
     182                return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, foundselection, 
     183                               matchInFirstPattern, matchInSecondPattern); 
     184            } 
     185            else { 
     186                return false; 
     187            } 
     188        } 
     189 
     190        if ((matchInFirstPattern || matchInSecondPattern) && jumped1) { 
     191            return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, false, foundselection, 
     192                           matchInFirstPattern, matchInSecondPattern); 
     193        } 
     194        if ((matchInFirstPattern || matchInSecondPattern) && jumped2) { 
     195            return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, false, foundselection, 
     196                           matchInFirstPattern, matchInSecondPattern); 
     197 
     198        } 
     199        if (matchInFirstPattern || matchInSecondPattern) { 
     200            return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, foundselection, 
     201                           matchInFirstPattern, matchInSecondPattern); 
     202        } 
     203        if (p1[ip1] == -1) { 
     204            return matches(i, p1, p2, ip1 + 1, ip2, true, false, false, false, false); 
     205        } 
     206        if (p2[ip2] == -1) { 
     207            return matches(i, p1, p2, ip1, ip2 + 1, false, true, false, false, false); 
     208        } 
     209 
     210        return false; 
     211    } 
     212 
     213    /** 
     214     * Prints the sequence. 
     215     */ 
     216    public void printSequence() { 
     217        for (int i = 0; i < sequence.length; i++) { 
     218            System.out.format("%5d", sequence[i]); 
     219        } 
     220        System.out.println(); 
     221    } 
     222 
     223    /** 
     224     * Sets the id. 
     225     * 
     226     * @param id 
     227     *            the new id 
     228     */ 
     229    public void setId(int id) { 
     230        this.id = id; 
     231    } 
     232 
     233    /** 
     234     * Sets the sequence. 
     235     * 
     236     * @param sequence 
     237     *            the new sequence 
     238     */ 
     239    public void setSequence(int[] sequence) { 
     240        this.sequence = sequence; 
     241    } 
     242 
     243    /** 
     244     * Shuffle. 
     245     * 
     246     * @return the number sequence 
     247     */ 
     248    public NumberSequence shuffle() { 
     249        final NumberSequence result = new NumberSequence(sequence.length); 
     250        result.setId(getId()); 
     251        result.setSequence(this.sequence); 
     252        final Random rgen = new Random(); 
     253 
     254        for (int i = 0; i < result.sequence.length; i++) { 
     255            final int randomPosition = rgen.nextInt(result.sequence.length); 
     256            final int temp = result.sequence[i]; 
     257            result.sequence[i] = result.sequence[randomPosition]; 
     258            result.sequence[randomPosition] = temp; 
     259        } 
     260        return result; 
     261 
     262    } 
     263 
     264    /** 
     265     * Size. 
     266     * 
     267     * @return the int 
     268     */ 
     269    public int size() { 
     270        return sequence.length; 
     271    } 
    251272 
    252273} 

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java

    r1741 r1747  
    109109                        eti1 = (IEventTaskInstance) ti1; 
    110110                        index1 = getIndex(eti1); 
    111                         distance = distanceBetweenTaskAndInstance(task2, eti1); 
     111                        distance = distanceBetweenTaskAndInstance(task2, eti1)-3; 
    112112                } else if (!(ti1 instanceof IEventTaskInstance) 
    113113                                && (ti2 instanceof IEventTaskInstance)) { 
    … …  
    120120                        index1 = getIndex(task1); 
    121121                        index2 = getIndex(task2); 
    122                         distance = distanceBetweenTasks(task1, task2); 
     122                        distance = distanceBetweenTasks(task1, task2)-3; 
    123123                } else { 
    124124                        System.out.println("Unknown error"); 
    … …  
    212212                this.uniqueTasks = uniqueTasks; 
    213213                if (this.calculateNonEventTaskInstances) { 
    214                         matrix = new DynamicTriangleMatrix(uniqueTasks.size() + 1); 
     214                        matrix = new PreallocatedDynamicTriangleMatrix(uniqueTasks.size() + 1); 
    215215                        Console.traceln(Level.INFO, "searching EventTasks in Tasks"); 
    216216                        //searchEventTaskInstances(); 

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/RuleUtils.java

    r1743 r1747  
    1515package de.ugoe.cs.autoquest.tasktrees.temporalrelation; 
    1616 
     17import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 
    1718import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; 
    1819import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; 
    … …  
    6566                final ISequenceInstance subsequence = taskFactory 
    6667                                .createNewTaskInstance(model); 
    67                 /* 
     68                 
     69                //System.out.println("STARTINDEX: " + startIndex); 
     70                //System.out.println("PRINTING SEQUENCE: "); 
     71                //for(int i =0; i< parent.size();i++) { 
     72                //    System.out.println(i + ": " +parent.get(i)); 
     73                //} 
     74                System.out.println(); 
     75                 
    6876                System.out.println("PRINTING MODEL: "); 
    6977                for (int i = 0; i < subsequence.getSequence().getChildren().size(); i++) { 
    … …  
    97105                } 
    98106                System.out.println(); 
    99                 */ 
     107                 
    100108                // TODO: This is dirty, return this in addition with the sequence 
    101109                // instance instead 
    … …  
    110118                        //System.out.println("Trying to add " + parent.get(startIndex) 
    111119                        // + " to the model instance " + tempTask); 
    112                         if (tempTask.getType() == "optionality") { 
    113  
    114                                 if (((IMarkingTemporalRelationship) tempTask).getMarkedTask() == parent 
    115                                                 .get(startIndex).getTask()) { 
    116                                         // System.out.println("Adding OptionalInstance " + 
     120                        if (tempTask instanceof IOptional) { 
     121 
     122                                if (((IMarkingTemporalRelationship) tempTask).getMarkedTask().equals(parent 
     123                                              .get(startIndex).getTask())) { 
     124                                         //System.out.println("Adding OptionalInstance " + 
    117125                                        // parent.get(startIndex) + " to " + tempTask.getType()); 
    118126                                        final IOptionalInstance optional = taskFactory 
    … …  
    121129                                        taskBuilder.addChild(subsequence, optional); 
    122130                                } else { 
    123                                         // System.out.println("Adding Empty optional, not deleting anything from the input sequence"); 
     131                                         //System.out.println("Adding Empty optional, not deleting anything from the input sequence"); 
    124132                                        final IOptionalInstance optional = taskFactory 
    125133                                                        .createNewTaskInstance((IOptional) tempTask); 
    … …  
    211219                                        taskBuilder.addChild(subsequence, selection); 
    212220                                } 
    213                         } else if (tempTask.getType() == "sequence") { 
     221                        } else if (tempTask instanceof ISequence) { 
    214222                                taskBuilder.addChild(subsequence, parent.get(startIndex)); 
    215                         } else if (tempTask.getType() == "iteration") { 
     223                        } else if (tempTask instanceof IIteration) { 
    216224                                taskBuilder.addChild(subsequence, parent.get(startIndex)); 
    217225                        } else { 
    … …  
    227235        } 
    228236 
     237         
     238        /* 
     239        static boolean containsOptional(ISequence seq) { 
     240          for(int i = 0; i < seq.getChildren().size();i++) { 
     241              if(seq.getChildren().get(i) instanceof IOptional) { 
     242                  return true; 
     243              } 
     244          }   
     245              return false; 
     246        } 
     247         
     248        private boolean reachesEnd(ITaskInstanceList parent, ISequence model,int sequenceIndex,int modelIndex,int startIndex) { 
     249             
     250            if(modelIndex == model.getChildren().size()) { 
     251                return true; 
     252            } 
     253            ITask modelTask = model.getChildren().get(modelIndex); 
     254            ITask sessionTask = parent.get(startIndex+sequenceIndex).getTask(); 
     255            if(modelTask instanceof IOptional) { 
     256                    reachesEnd(parent,model,sequenceIndex++,modelIndex++,startIndex); 
     257                    reachesEnd(parent,model,sequenceIndex,modelIndex++,startIndex); 
     258            } 
     259             
     260            boolean taskfits=false; 
     261            if(modelTask instanceof ISequence) { 
     262                if(sessionTask.equals(((ISequence)modelTask).getChildren().get(0))) { 
     263                    taskfits=true; 
     264                } 
     265            } 
     266            if(modelTask instanceof IIteration) { 
     267                if(sessionTask.equals(((ISequence)modelTask).getChildren().get(0))) { 
     268                    taskfits=true; 
     269                } 
     270            } 
     271            if(modelTask instanceof ISelection) { 
     272                 
     273            } 
     274             
     275        return taskfits; 
     276             
     277             
     278             
     279        } 
     280        */ 
     281 
     282         
    229283        /** 
    230284         * <p> 

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java

    r1743 r1747  
    5858/** 
    5959 * <p> 
    60  * This class implements the major rule for creating task trees based on a set 
    61  * of recorded user sessions. For this, it first harmonizes all tasks. This 
    62  * eases later comparison. Then it searches the sessions for iterations and 
    63  * replaces them accordingly. Then it searches for sub sequences using alignment 
    64  * algorithms For each found sub sequence, it replaces the occurrences by 
    65  * creating appropriate {@link ISequence}s. Afterwards, again searches for 
    66  * iterations and then again for sub sequences until no more replacements are 
    67  * done. 
     60 * This class implements the major rule for creating task trees based on a set of recorded user 
     61 * sessions. For this, it first harmonizes all tasks. This eases later comparison. Then it searches 
     62 * the sessions for iterations and replaces them accordingly. Then it searches for sub sequences 
     63 * using alignment algorithms For each found sub sequence, it replaces the occurrences by creating 
     64 * appropriate {@link ISequence}s. Afterwards, again searches for iterations and then again for sub 
     65 * sequences until no more replacements are done. 
    6866 * </p> 
    6967 * <p> 
    … …  
    7472public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule { 
    7573 
    76         /** The n threads. */ 
    77         //public static int nThreads = Runtime.getRuntime().availableProcessors() - 1; 
    78         public static int nThreads = 1; 
    79  
    80         /** The iteration. */ 
    81         private int iteration = 0; 
    82  
    83         /** 
    84          * <p> 
    85          * the task factory to be used for creating substructures for the temporal 
    86          * relationships identified during rul application 
    87          * </p> 
    88          * . 
    89          */ 
    90         private final ITaskFactory taskFactory; 
    91  
    92         /** 
    93          * <p> 
    94          * the task builder to be used for creating substructures for the temporal 
    95          * relationships identified during rule application 
    96          * </p> 
    97          * . 
    98          */ 
    99         private final ITaskBuilder taskBuilder; 
    100  
    101         /** 
    102          * <p> 
    103          * the task handling strategy to be used for comparing tasks for 
    104          * preparation, i.e., before the tasks are harmonized 
    105          * </p> 
    106          */ 
    107         private final TaskHandlingStrategy preparationTaskHandlingStrategy; 
    108  
    109         /** 
    110          * <p> 
    111          * instantiates the rule and initializes it with a task equality to be 
    112          * considered when comparing tasks as well as a task factory and builder to 
    113          * be used for creating task structures. 
    114          * </p> 
    115          *  
    116          * @param minimalTaskEquality 
    117          *            the task equality to be considered when comparing tasks 
    118          * @param taskFactory 
    119          *            the task factory to be used for creating substructures 
    120          * @param taskBuilder 
    121          *            the task builder to be used for creating substructures 
    122          */ 
    123  
    124         SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality, 
    125                         ITaskFactory taskFactory, ITaskBuilder taskBuilder) { 
    126                 this.taskFactory = taskFactory; 
    127                 this.taskBuilder = taskBuilder; 
    128  
    129                 this.preparationTaskHandlingStrategy = new TaskHandlingStrategy( 
    130                                 minimalTaskEquality); 
    131         } 
    132  
    133         /* 
    134          * (non-Javadoc) 
    135          *  
    136          * @see 
    137          * de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply 
    138          * (java.util.List) 
    139          */ 
    140         @Override 
    141         public RuleApplicationResult apply(List<IUserSession> sessions) { 
    142                 final RuleApplicationData appData = new RuleApplicationData(sessions); 
    143  
    144                 harmonizeEventTaskInstancesModel(appData); 
    145  
    146                 Console.traceln(Level.INFO, "generating substitution matrix from " 
    147                                 + appData.getUniqueTasks().size() + " unique tasks"); 
    148                 appData.getStopWatch().start("substitution matrix"); 
    149                 appData.getSubmat().generate(appData.getUniqueTasks()); 
    150                 appData.getStopWatch().stop("substitution matrix"); 
    151  
    152                 Console.traceln(Level.INFO, "Starting main loop"); 
    153                 do { 
    154                         Console.traceln(Level.INFO, "Iteration Number: " + iteration); 
    155                         iteration++; 
    156                         appData.detectedAndReplacedTasks = false; 
    157                         appData.getStopWatch().start("whole loop"); 
    158                         detectAndReplaceIterations(appData); 
    159                         appData.getStopWatch().start("task replacement"); 
    160                         // Just does anything if the substitution matrix is created with the 
    161                         // option to do so 
    162                         appData.updateSubstitutionMatrix(); 
    163                         detectAndReplaceTasks(appData); // 
    164                         appData.getStopWatch().stop("task replacement"); 
    165                         appData.getStopWatch().stop("whole loop"); 
    166                         // appData.getStopWatch().dumpStatistics(System.out); 
    167                         appData.getStopWatch().reset(); 
    168  
    169                 } while (appData.detectedAndReplacedTasks()); 
    170  
    171                 Console.println("created " 
    172                                 + appData.getResult().getNewlyCreatedTasks().size() 
    173                                 + " new tasks and " 
    174                                 + appData.getResult().getNewlyCreatedTaskInstances().size() 
    175                                 + " appropriate instances\n"); 
    176  
    177                 if ((appData.getResult().getNewlyCreatedTasks().size() > 0) 
    178                                 || (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) { 
    179                         appData.getResult().setRuleApplicationStatus( 
    180                                         RuleApplicationStatus.FINISHED); 
    181                 } 
    182                 // new TaskTreeValidator().validate(appData.getSessions()); 
    183                 return appData.getResult(); 
    184         } 
    185  
    186         /** 
    187          * Creates the number sequences. 
    188          * 
    189          * @param appData 
    190          *            the app data 
    191          * @return the array list 
    192          */ 
    193         private ArrayList<NumberSequence> createNumberSequences( 
    194                         RuleApplicationData appData) { 
    195                 final ArrayList<NumberSequence> result = new ArrayList<NumberSequence>(); 
    196                 for (int i = 0; i < appData.getSessions().size(); i++) { 
    197                         final IUserSession session = appData.getSessions().get(i); 
    198                         final NumberSequence templist = new NumberSequence(session.size()); 
    199                         for (int j = 0; j < session.size(); j++) { 
    200                                 final ITaskInstance taskInstance = session.get(j); 
    201                                 templist.getSequence()[j] = taskInstance.getTask().getId(); 
    202                         } 
    203                         // Each NumberSequence is identified by its id, beginning to count 
    204                         // at zero 
    205                         templist.setId(i); 
    206                         result.add(templist); 
    207                 } 
    208                 return result; 
    209         } 
    210  
    211         /** 
    212          * <p> 
    213          * searches for direct iterations of single tasks in all sequences and 
    214          * replaces them with {@link IIteration}s, respectively appropriate 
    215          * instances. Also all single occurrences of a task that is iterated 
    216          * somewhen are replaced with iterations to have again an efficient way for 
    217          * task comparisons. 
    218          * </p> 
    219          *  
    220          * @param appData 
    221          *            the rule application data combining all data used for applying 
    222          *            this rule 
    223          */ 
    224         private void detectAndReplaceIterations(RuleApplicationData appData) { 
    225                 Console.traceln(Level.FINE, "detecting iterations"); 
    226                 appData.getStopWatch().start("detecting iterations"); 
    227  
    228                 final List<IUserSession> sessions = appData.getSessions(); 
    229  
    230                 final Set<ITask> iteratedTasks = searchIteratedTasks(sessions); 
    231  
    232                 if (iteratedTasks.size() > 0) { 
    233                         replaceIterationsOf(iteratedTasks, sessions, appData); 
    234                 } 
    235  
    236                 appData.getStopWatch().stop("detecting iterations"); 
    237                 Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() 
    238                                 + " iterated tasks"); 
    239         } 
    240  
    241         /** 
    242          * Detect and replace tasks. 
    243          * 
    244          * @param appData 
    245          *            the rule application data combining all data used for applying 
    246          *            this rule 
    247          */ 
    248         private void detectAndReplaceTasks(RuleApplicationData appData) { 
    249                 Console.traceln(Level.FINE, "detecting and replacing tasks"); 
    250                 appData.getStopWatch().start("detecting tasks"); 
    251  
    252                 // Create NumberSequences 
    253                 appData.setNumberSequences(this.createNumberSequences(appData)); 
    254  
    255                 // Generate pairwise alignments 
    256                 // appData.setMatchseqs(generatePairwiseAlignments(appData)); 
    257                 generatePairwiseAlignments(appData); 
    258                 Console.traceln(Level.FINE, "Found " + appData.getMatchseqs().size() 
    259                                 + " results"); 
    260                  
    261                 //Nothing found, we can end here 
    262                 if(appData.getMatchseqs().size()==0) { 
    263                         appData.detectedAndReplacedTasks=false; 
    264                         return; 
    265                 } 
    266                  
    267                 // Searching each match in all other sessions, counting its occurences 
    268                 searchMatchesInAllSessions(appData); 
    269  
    270                 // Sort results to get the most occurring results 
    271                 Console.traceln(Level.INFO, "sorting " + appData.getMatchseqs().size() 
    272                                 + " results"); 
    273                 final Comparator<Match> comparator = new Comparator<Match>() { 
    274                         @Override 
    275                         public int compare(Match m1, Match m2) { 
    276                                 int cmp = m2.occurenceCount() - m1.occurenceCount(); 
    277                                 if (cmp != 0) { 
    278                                         return cmp; 
    279                                 } else { 
    280                                         cmp = m2.size() - m1.size(); 
    281                                         if (cmp != 0) { 
    282                                                 return cmp; 
    283                                         } else { 
    284                                                 // This should rarely happen 
    285                                                 cmp = m2.ocurrenceIDSum() - m1.ocurrenceIDSum(); 
    286                                                 if (cmp != 0) { 
    287                                                         return cmp; 
    288                                                 } else { 
    289                                                         cmp = m2.taskIdSum() - m1.taskIdSum(); 
    290  
    291                                                         return cmp; 
    292                                                 } 
    293                                         } 
    294                                 } 
    295                         } 
    296                 }; 
    297  
    298                 Collections.sort(appData.getMatchseqs(), comparator); 
    299                 appData.getStopWatch().stop("detecting tasks"); 
    300  
    301                 Console.traceln(Level.INFO, "Preparing replacments"); 
    302                 prepareReplacements(appData); 
    303                 Console.traceln(Level.INFO, "Replacing matches in sessions"); 
    304                 appData.getStopWatch().start("replacing tasks"); 
    305                 replaceMatches(appData); 
    306                 appData.getStopWatch().stop("replacing tasks"); 
    307         } 
    308  
    309         // TODO: DEBUG METHOD 
    310         @SuppressWarnings("unused") 
    311         private void printMatches(RuleApplicationData appData) { 
    312                 LinkedList<Match> matchseqs = appData.getMatchseqs(); 
    313                 if (iteration > 1) { 
    314                         System.out.println("PRINTING MATCHES"); 
    315                         for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) { 
    316                                 Match m = it.next(); 
    317                                 m.getFirstSequence().printSequence(); 
    318                                 m.getSecondSequence().printSequence(); 
    319                                 for (Iterator<MatchOccurrence> jt = m.getOccurences() 
    320                                                 .iterator(); jt.hasNext();) { 
    321                                         MatchOccurrence mo = jt.next(); 
    322                                         System.out.print(mo.getSequenceId() + " "); 
    323                                 } 
    324                                 System.out.println(); 
    325                                 System.out.println(); 
    326                         } 
    327                 } 
    328         } 
    329  
    330         /** 
    331          * <p> 
    332          * harmonizes the event task instances by unifying tasks. This is done, as 
    333          * initially the event tasks being equal with respect to the considered task 
    334          * equality are distinct objects. The comparison of these distinct objects 
    335          * is more time consuming than comparing the object references. 
    336          * </p> 
    337          *  
    338          * @param appData 
    339          *            the rule application data combining all data used for applying 
    340          *            this rule 
    341          * @return Returns the unique tasks symbol map 
    342          */ 
    343         private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) { 
    344                 Console.traceln(Level.INFO, 
    345                                 "harmonizing task model of event task instances"); 
    346                 appData.getStopWatch().start("harmonizing event tasks"); 
    347                 final SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy 
    348                                 .createSymbolMap(); 
    349  
    350                 final TaskInstanceComparator comparator = preparationTaskHandlingStrategy 
    351                                 .getTaskComparator(); 
    352  
    353                 int unifiedTasks = 0; 
    354                 ITask task; 
    355                 final List<IUserSession> sessions = appData.getSessions(); 
    356                 for (int j = 0; j < sessions.size(); j++) { 
    357                         final IUserSession session = sessions.get(j); 
    358  
    359                         for (int i = 0; i < session.size(); i++) { 
    360                                 final ITaskInstance taskInstance = session.get(i); 
    361                                 task = uniqueTasks.getValue(taskInstance); 
    362  
    363                                 if (task == null) { 
    364                                         uniqueTasks.addSymbol(taskInstance, taskInstance.getTask()); 
    365                                         appData.getUniqueTasks().add(taskInstance.getTask()); 
    366                                         appData.getNumber2Task().put( 
    367                                                         taskInstance.getTask().getId(), 
    368                                                         taskInstance.getTask()); 
    369                                 } else { 
    370                                         taskBuilder.setTask(taskInstance, task); 
    371                                         unifiedTasks++; 
    372                                 } 
    373                         } 
    374                         comparator.clearBuffers(); 
    375                 } 
    376  
    377                 appData.getStopWatch().stop("harmonizing event tasks"); 
    378                 Console.traceln(Level.INFO, "harmonized " + unifiedTasks 
    379                                 + " task occurrences (still " + appData.getUniqueTasks().size() 
    380                                 + " different tasks)"); 
    381  
    382                 appData.getStopWatch().dumpStatistics(System.out); 
    383                 appData.getStopWatch().reset(); 
    384         } 
    385  
    386         /** 
    387          * <p> 
    388          * TODO clarify why this is done (in fact, ask Patrick Harms) 
    389          * </p> 
    390          * . 
    391          * 
    392          * @param iteration 
    393          *            the iteration 
    394          * @param iterationInstances 
    395          *            the iteration instances 
    396          */ 
    397         private void harmonizeIterationInstancesModel(IIteration iteration, 
    398                         List<IIterationInstance> iterationInstances) { 
    399                 final List<ITask> iteratedTaskVariants = new LinkedList<ITask>(); 
    400                 final TaskInstanceComparator comparator = preparationTaskHandlingStrategy 
    401                                 .getTaskComparator(); 
    402  
    403                 // merge the lexically different variants of iterated task to a unique 
    404                 // list 
    405                 for (final IIterationInstance iterationInstance : iterationInstances) { 
    406                         for (final ITaskInstance executionVariant : iterationInstance) { 
    407                                 final ITask candidate = executionVariant.getTask(); 
    408  
    409                                 boolean found = false; 
    410                                 for (final ITask taskVariant : iteratedTaskVariants) { 
    411                                         if (comparator.areLexicallyEqual(taskVariant, candidate)) { 
    412                                                 taskBuilder.setTask(executionVariant, taskVariant); 
    413                                                 found = true; 
    414                                                 break; 
    415                                         } 
    416                                 } 
    417  
    418                                 if (!found) { 
    419                                         iteratedTaskVariants.add(candidate); 
    420                                 } 
    421                         } 
    422                 } 
    423  
    424                 // if there are more than one lexically different variant of iterated 
    425                 // tasks, adapt the 
    426                 // iteration model to be a selection of different variants. In this case 
    427                 // also adapt 
    428                 // the generated iteration instances to correctly contain selection 
    429                 // instances. If there 
    430                 // is only one variant of an iterated task, simply set this as the 
    431                 // marked task of the 
    432                 // iteration. In this case, the instances can be preserved as is 
    433                 if (iteratedTaskVariants.size() > 1) { 
    434                         final ISelection selection = taskFactory.createNewSelection(); 
    435  
    436                         for (final ITask variant : iteratedTaskVariants) { 
    437                                 taskBuilder.addChild(selection, variant); 
    438                         } 
    439  
    440                         taskBuilder.setMarkedTask(iteration, selection); 
    441  
    442                         for (final IIterationInstance instance : iterationInstances) { 
    443                                 for (int i = 0; i < instance.size(); i++) { 
    444                                         final ISelectionInstance selectionInstance = taskFactory 
    445                                                         .createNewTaskInstance(selection); 
    446                                         taskBuilder.setChild(selectionInstance, instance.get(i)); 
    447                                         taskBuilder.setTaskInstance(instance, i, selectionInstance); 
    448                                 } 
    449                         } 
    450                 } else { 
    451                         taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0)); 
    452                 } 
    453         } 
    454  
    455         /** 
    456          * Match as sequence. 
    457          * 
    458          * @param appData 
    459          *            RuleApplicationData needed to keep track of all created tasks 
    460          * @param m 
    461          *            The match to be converted into a Task 
    462          * @return The task of the match with an ISequence as its root 
    463          */ 
    464         synchronized public ISequence matchAsSequence(RuleApplicationData appData, 
    465                         Match m) { 
    466                 final ISequence sequence = taskFactory.createNewSequence(); 
    467                 appData.newTaskCreated(sequence); 
    468  
    469                 final int[] first = m.getFirstSequence().getSequence(); 
    470                 final int[] second = m.getSecondSequence().getSequence(); 
    471  
    472                 // Both sequences of a match are equally long 
    473                 for (int i = 0; i < m.getFirstSequence().size(); i++) { 
    474  
    475                         // Two gaps aligned to each other: Have not seen it happening so 
    476                         // far, just to handle it 
    477                         if ((first[i] == -1) && (second[i] == -1)) { 
    478                                 // Do nothing here. 
    479                         } 
    480                         // Both events are equal, we can simply add the task referring to 
    481                         // the number 
    482                         else if (first[i] == second[i]) { 
    483                                 taskBuilder.addChild(sequence, 
    484                                                 appData.getNumber2Task().get(first[i])); 
    485                         } 
    486                         // We have a gap in the first sequence, we need to add the task of 
    487                         // the second sequence as optional 
    488                         else if ((first[i] == -1) && (second[i] != -1)) { 
    489                                 final IOptional optional = taskFactory.createNewOptional(); 
    490                                 appData.newTaskCreated(optional); 
    491                                 taskBuilder.setMarkedTask(optional, appData.getNumber2Task() 
    492                                                 .get(second[i])); 
    493                                 taskBuilder.addChild(sequence, optional); 
    494                         } 
    495                         // We have a gap in the second sequence, we need to add the task of 
    496                         // the first sequence as optional 
    497                         else if ((first[i] != -1) && (second[i] == -1)) { 
    498                                 final IOptional optional = taskFactory.createNewOptional(); 
    499                                 appData.newTaskCreated(optional); 
    500                                 taskBuilder.setMarkedTask(optional, appData.getNumber2Task() 
    501                                                 .get(first[i])); 
    502                                 taskBuilder.addChild(sequence, optional); 
    503                         } 
    504                         // Both tasks are not equal, we need to insert a selection here. 
    505                         // Now things get complicated. We first need to check 
    506                         // if the next position is not a selection. Then we can just create 
    507                         // a selection 
    508                         // of the both Tasks 
    509                         // In the other case (more than one selection following this 
    510                         // selection), we want to 
    511                         // create a selection of sequences where each sequence gets the 
    512                         // corresponding task of 
    513                         // the its sequence in the pattern. 
    514                         // 
    515                         else if (i < (first.length - 1)) { 
    516  
    517                                 if ((first[i] != second[i]) 
    518                                                 && (((first[i + 1] == second[i + 1]) 
    519                                                                 || (first[i + 1] == -1) || (second[i + 1] == -1)))) { 
    520  
    521                                         final ISelection selection = taskFactory 
    522                                                         .createNewSelection(); 
    523                                         appData.newTaskCreated(selection); 
    524                                         taskBuilder.addChild(selection, appData.getNumber2Task() 
    525                                                         .get(first[i])); 
    526                                         taskBuilder.addChild(selection, appData.getNumber2Task() 
    527                                                         .get(second[i])); 
    528                                         taskBuilder.addChild(sequence, selection); 
    529                                 } else { 
    530                                         boolean selectionfound = true; 
    531                                         final ISelection selection = taskFactory 
    532                                                         .createNewSelection(); 
    533                                         appData.newTaskCreated(selection); 
    534  
    535                                         final ISequence subsequence1 = taskFactory 
    536                                                         .createNewSequence(); 
    537                                         appData.newTaskCreated(subsequence1); 
    538  
    539                                         final ISequence subsequence2 = taskFactory 
    540                                                         .createNewSequence(); 
    541                                         appData.newTaskCreated(subsequence2); 
    542  
    543                                         taskBuilder.addChild(selection, subsequence1); 
    544                                         taskBuilder.addChild(selection, subsequence2); 
    545                                         taskBuilder.addChild(sequence, selection); 
    546                                         // TODO: We may not run till the end! 
    547                                         while ((i < (first.length - 1)) && selectionfound) { 
    548                                                 selectionfound = false; 
    549                                                 taskBuilder.addChild(subsequence1, appData 
    550                                                                 .getNumber2Task().get(first[i])); 
    551                                                 taskBuilder.addChild(subsequence2, appData 
    552                                                                 .getNumber2Task().get(second[i])); 
    553                                                 if ((first[i + 1] != second[i + 1]) 
    554                                                                 && (first[i + 1] != -1) 
    555                                                                 && (second[i + 1] != -1)) { 
    556                                                         selectionfound = true; 
    557                                                 } else { 
    558                                                         continue; 
    559                                                 } 
    560                                                 i++; 
    561                                         } 
    562                                         if ((i == (first.length - 1)) && selectionfound) { 
    563                                                 taskBuilder.addChild(subsequence1, appData 
    564                                                                 .getNumber2Task().get(first[i])); 
    565                                                 taskBuilder.addChild(subsequence2, appData 
    566                                                                 .getNumber2Task().get(second[i])); 
    567                                         } 
    568                                 } 
    569                         } else { 
    570                                 // i = length-1 
    571                                 if ((first[i] != second[i])) { 
    572  
    573                                         final ISelection selection = taskFactory 
    574                                                         .createNewSelection(); 
    575                                         appData.newTaskCreated(selection); 
    576                                         taskBuilder.addChild(selection, appData.getNumber2Task() 
    577                                                         .get(first[i])); 
    578                                         taskBuilder.addChild(selection, appData.getNumber2Task() 
    579                                                         .get(second[i])); 
    580                                         taskBuilder.addChild(sequence, selection); 
    581                                 } 
    582                         } 
    583  
    584                 } 
    585                 return sequence; 
    586         } 
    587  
    588         /** 
    589          * <p> 
    590          * replaces all occurrences of all tasks provided in the set with iterations 
    591          * </p> 
    592          * . 
    593          * 
    594          * @param iteratedTasks 
    595          *            the tasks to be replaced with iterations 
    596          * @param sessions 
    597          *            the sessions in which the tasks are to be replaced 
    598          * @param appData 
    599          *            the rule application data combining all data used for applying 
    600          *            this rule 
    601          */ 
    602         private void replaceIterationsOf(Set<ITask> iteratedTasks, 
    603                         List<IUserSession> sessions, RuleApplicationData appData) { 
    604                 final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>(); 
    605                 final Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>(); 
    606  
    607                 for (final ITask iteratedTask : iteratedTasks) { 
    608  
    609                         final IIteration iteration = taskFactory.createNewIteration(); 
    610                         appData.newTaskCreated(iteration); 
    611                         iterations.put(iteratedTask, iteration); 
    612                         iterationInstances.put(iteration, 
    613                                         new LinkedList<IIterationInstance>()); 
    614                 } 
    615  
    616                 IIterationInstance iterationInstance; 
    617  
    618                 for (final IUserSession session : sessions) { 
    619                         int index = 0; 
    620                         iterationInstance = null; 
    621  
    622                         while (index < session.size()) { 
    623                                 // we prepared the task instances to refer to unique tasks, if 
    624                                 // they are treated 
    625                                 // as equal. Therefore, we just compare the identity of the 
    626                                 // tasks of the task 
    627                                 // instances 
    628                                 final ITask currentTask = session.get(index).getTask(); 
    629                                 final IIteration iteration = iterations.get(currentTask); 
    630                                 if (iteration != null) { 
    631                                         if ((iterationInstance == null) 
    632                                                         || (iterationInstance.getTask() != iteration)) { 
    633                                                 iterationInstance = taskFactory 
    634                                                                 .createNewTaskInstance(iteration); 
    635                                                 iterationInstances.get(iteration) 
    636                                                                 .add(iterationInstance);// TODO:: Don't create 
    637                                                 // TaskInstances here, 
    638                                                 // use a set of tasks 
    639                                                 // instead 
    640                                                 taskBuilder.addTaskInstance(session, index, 
    641                                                                 iterationInstance); 
    642                                                 index++; 
    643                                         } 
    644  
    645                                         taskBuilder.addChild(iterationInstance, session.get(index)); 
    646                                         taskBuilder.removeTaskInstance(session, index); 
    647                                 } else { 
    648                                         if (iterationInstance != null) { 
    649                                                 iterationInstance = null; 
    650                                         } 
    651                                         index++; 
    652                                 } 
    653                         } 
    654                 } 
    655  
    656                 for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances 
    657                                 .entrySet()) { 
    658                         harmonizeIterationInstancesModel(entry.getKey(), entry.getValue()); 
    659                 } 
    660         } 
    661  
    662         private void prepareReplacements(RuleApplicationData appData) { 
    663                 appData.initializeQueues(appData.getSessions().size()); 
    664                  
    665                 for (Iterator<Match> it = appData.getMatchseqs().iterator(); it 
    666                                 .hasNext();) { 
    667                         Match m = it.next(); 
    668                         for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt 
    669                                         .hasNext();) { 
    670                                 MatchOccurrence mo = jt.next(); 
    671  
    672                                 Match emptyMatch = null; 
    673                                 try { 
    674                                         emptyMatch = m.cloneWithoutOccurences(); 
    675                                 } catch (CloneNotSupportedException e) { 
    676                                         e.printStackTrace(); 
    677                                 } 
    678                                 emptyMatch.addOccurence(mo); 
    679                                 appData.getPlannedReplacements()[mo.getSequenceId()].add(m); 
    680                         } 
    681                 } 
    682         } 
    683  
    684         /** 
    685          * Replace matches. 
    686          * 
    687          * @param appData 
    688          *            the app data 
    689          */ 
    690         private void replaceMatches(RuleApplicationData appData) { 
    691          
    692                 final int numberSeqSize = appData.getNumberSequences().size(); 
    693                 Console.traceln(Level.INFO, "replacing matches with " + nThreads + " threads"); 
    694                 int newThreads = nThreads; 
    695                 if (numberSeqSize < nThreads) { 
    696                         newThreads = numberSeqSize; 
    697                 } 
    698                 final int interval = numberSeqSize / newThreads; 
    699                 int rest = numberSeqSize % newThreads; 
    700                 final ExecutorService executor = Executors.newFixedThreadPool(nThreads); 
    701                 for (int i = 0; i <= (numberSeqSize - interval); i += interval) { 
    702                         int offset = 0; 
    703                         if (rest != 0) { 
    704                                 offset = 1; 
    705                                 rest--; 
    706                         } 
    707                         final int from = i; 
    708                         final int to = i + interval + offset - 1; 
    709                         Console.traceln(Level.FINE, 
    710                                         "Match replaceing: Creating thread with matches from " + from 
    711                                                         + " to " + to); 
    712                         // search each match in every other sequence 
    713                         final ParallelMatchReplacer replacer = new ParallelMatchReplacer( 
    714                                         appData, from, to); 
    715                         executor.execute(replacer); 
    716                         i += offset; 
    717                 } 
    718                 executor.shutdown(); 
    719                 try { 
    720                         executor.awaitTermination(2, TimeUnit.HOURS); 
    721                 } catch (final InterruptedException e) { 
    722                         e.printStackTrace(); 
    723                 } 
    724         } 
    725  
    726         /** 
    727          * <p> 
    728          * searches the provided sessions for task iterations. If a task is 
    729          * iterated, it is added to the returned set. 
    730          * </p> 
    731          * 
    732          * @param sessions 
    733          *            the sessions 
    734          * @return a set of tasks being iterated somewhere 
    735          */ 
    736         private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) { 
    737                 final Set<ITask> iteratedTasks = new HashSet<ITask>(); 
    738                 for (final IUserSession session : sessions) { 
    739                         for (int i = 0; i < (session.size() - 1); i++) { 
    740                                 // we prepared the task instances to refer to unique tasks, if 
    741                                 // they are treated 
    742                                 // as equal. Therefore, we just compare the identity of the 
    743                                 // tasks of the task 
    744                                 // instances 
    745                                 if (session.get(i).getTask() == session.get(i + 1).getTask()) { 
    746                                         iteratedTasks.add(session.get(i).getTask()); 
    747                                 } 
    748                         } 
    749                 } 
    750                 return iteratedTasks; 
    751         } 
    752  
    753         /** 
    754          * Generate pairwise alignments. 
    755          * 
    756          * @param appData 
    757          *            the app data 
    758          */ 
    759         private void generatePairwiseAlignments(RuleApplicationData appData) { 
    760                 final int numberSeqSize = appData.getNumberSequences().size(); 
    761                 appData.matchseqs = new LinkedList<Match>(); 
    762                 Console.traceln(Level.INFO, "generating pairwise alignments from " 
    763                                 + numberSeqSize + " sessions with " + nThreads + " threads"); 
    764  
    765                 int newThreads = nThreads; 
    766                 if (numberSeqSize < nThreads) { 
    767                         newThreads = numberSeqSize; 
    768                 } 
    769  
    770                 final ExecutorService executor = Executors 
    771                                 .newFixedThreadPool(newThreads); 
    772                 final int interval = numberSeqSize / newThreads; 
    773                 int rest = numberSeqSize % newThreads; 
    774                 Console.traceln(Level.FINE, "Interval: " + interval + " Rest: " + rest); 
    775                 for (int i = 0; i <= (numberSeqSize - interval); i += interval) { 
    776                         int offset = 0; 
    777                         if (rest != 0) { 
    778                                 offset = 1; 
    779                                 rest--; 
    780                         } 
    781  
    782                         final int from = i; 
    783                         final int to = i + interval + offset - 1; 
    784                         Console.traceln(Level.FINER, 
    785                                         "Aligning: Creating thread for sessions " + from + " till " 
    786                                                         + to); 
    787                         final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner( 
    788                                         appData, from, to); 
    789                         executor.execute(aligner); 
    790                         i += offset; 
    791                 } 
    792                 executor.shutdown(); 
    793                 try { 
    794                         executor.awaitTermination(2, TimeUnit.HOURS); 
    795                 } catch (final InterruptedException e) { 
    796                         e.printStackTrace(); 
    797                 } 
    798         } 
    799  
    800         /** 
    801          * Search matches in all sessions. 
    802          * 
    803          * @param appData 
    804          *            the app data 
    805          */ 
    806         private void searchMatchesInAllSessions(RuleApplicationData appData) { 
    807  
    808                 // Prepare parallel search of matchseqs 
    809                 final int matchSeqSize = appData.getMatchseqs().size(); 
    810                 Console.traceln(Level.INFO, "searching for patterns (" + matchSeqSize 
    811                                 + ") occuring most with " + nThreads + " threads"); 
    812                 int newThreads = nThreads; 
    813                 if (matchSeqSize < nThreads) { 
    814                         newThreads = matchSeqSize; 
    815                 } 
    816                 final int interval = matchSeqSize / newThreads; 
    817                 int rest = matchSeqSize % newThreads; 
    818                 final ExecutorService executor = Executors.newFixedThreadPool(nThreads); 
    819                 Console.traceln(Level.FINER, "Interval: " + interval + " Rest: " + rest); 
    820                 for (int i = 0; i <= (matchSeqSize - interval); i += interval) { 
    821                         int offset = 0; 
    822                         if (rest != 0) { 
    823                                 offset = 1; 
    824                                 rest--; 
    825                         } 
    826                         final int from = i; 
    827                         final int to = i + interval + offset - 1; 
    828                         Console.traceln(Level.FINE, 
    829                                         "Match finding: Creating thread with matches from " + from 
    830                                                         + " to " + to); 
    831                         // search each match in every other sequence 
    832                         final ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder( 
    833                                         appData, from, to); 
    834                         executor.execute(finder); 
    835                         i += offset; 
    836                 } 
    837                 executor.shutdown(); 
    838                 try { 
    839                         executor.awaitTermination(2, TimeUnit.HOURS); 
    840                 } catch (final InterruptedException e) { 
    841                         e.printStackTrace(); 
    842                 } 
    843  
    844         } 
    845  
    846         /* 
    847          * (non-Javadoc) 
    848          *  
    849          * @see java.lang.Object#toString() 
    850          */ 
    851         @Override 
    852         public String toString() { 
    853                 return "SequenceForTaskDetectionRuleAlignment"; 
    854         } 
    855  
    856         /** 
    857          * The Class ParallelMatchOcurrencesFinder. 
    858          */ 
    859         private class ParallelMatchOcurrencesFinder implements Runnable { 
    860  
    861                 /** The app data. */ 
    862                 private final RuleApplicationData appData; 
    863  
    864                 /** The from. */ 
    865                 private final int from; 
    866  
    867                 /** The to. */ 
    868                 private final int to; 
    869  
    870                 /** 
    871                  * Instantiates a new parallel match ocurrences finder. 
    872                  * 
    873                  * @param appData 
    874                  *            the app data 
    875                  * @param from 
    876                  *            the from 
    877                  * @param to 
    878                  *            the to 
    879                  */ 
    880                 ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from, 
    881                                 int to) { 
    882                         this.appData = appData; 
    883                         this.from = from; 
    884                         this.to = to; 
    885                 } 
    886  
    887                 /* 
    888                  * (non-Javadoc) 
    889                  *  
    890                  * @see java.lang.Runnable#run() 
    891                  */ 
    892                 @Override 
    893                 public void run() { 
    894                         int count = 0; 
    895                         final int size = to + 1 - from; 
    896  
    897                         for (int i = from; i <= to; i++) { 
    898                                 final Match pattern = appData.getMatchseqs().get(i); 
    899                                 count++; 
    900                                 RuleUtils.printProgressPercentage("Match finding progress", 
    901                                                 count, size); 
    902                                 // Skip sequences with more 0 events (scrolls) than other 
    903                                 // events. 
    904                                 // Both of the pattern sequences are equally long, so the zero 
    905                                 // counts just need to be smaller than the length of one 
    906                                 // sequence 
    907                                 if ((pattern.getFirstSequence().eventCount(0) 
    908                                                 + pattern.getSecondSequence().eventCount(0) + 1) > pattern 
    909                                                 .getFirstSequence().size()) { 
    910                                         continue; 
    911                                 } 
    912  
    913                                 for (int j = 0; j < appData.getNumberSequences().size(); j++) { 
    914                                         final LinkedList<Integer> startpositions = appData 
    915                                                         .getNumberSequences().get(j) 
    916                                                         .containsPattern(pattern); 
    917                                         if (startpositions.size() > 0) { 
    918                                                 for (final Iterator<Integer> jt = startpositions 
    919                                                                 .iterator(); jt.hasNext();) { 
    920                                                         final int start = jt.next(); 
    921                                                         pattern.addOccurence(new MatchOccurrence(start, 
    922                                                                         start + pattern.size(), j)); 
    923                                                 } 
    924                                         } 
    925                                 } 
    926                         } 
    927                 } 
    928         } 
    929  
    930         /** 
    931          * The Class ParallelPairwiseAligner. 
    932          */ 
    933         private class ParallelPairwiseAligner implements Runnable { 
    934  
    935                 /** The app data. */ 
    936                 private final RuleApplicationData appData; 
    937  
    938                 /** The from. */ 
    939                 private final int from; 
    940  
    941                 /** The to. */ 
    942                 private final int to; 
    943  
    944                 /** 
    945                  * Instantiates a new parallel pairwise aligner. 
    946                  * 
    947                  * @param appData 
    948                  *            the app data 
    949                  * @param from 
    950                  *            the from 
    951                  * @param to 
    952                  *            the to 
    953                  */ 
    954                 ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) { 
    955                         this.appData = appData; 
    956                         this.from = from; 
    957                         this.to = to; 
    958                 } 
    959  
    960                 /* 
    961                  * (non-Javadoc) 
    962                  *  
    963                  * @see java.lang.Runnable#run() 
    964                  */ 
    965                 @Override 
    966                 public void run() { 
    967                         int count = 0; 
    968                         final int size = to +1 - from; 
    969  
    970                         for (int i = from; i <= to; i++) { 
    971                                 final NumberSequence ns1 = appData.getNumberSequences().get(i); 
    972                                 count++; 
    973                                 RuleUtils.printProgressPercentage("Aligning Progress", count, 
    974                                                 size); 
    975                                 for (int j = 0; j < appData.getNumberSequences().size(); j++) { 
    976                                         final NumberSequence ns2 = appData.getNumberSequences() 
    977                                                         .get(j); 
    978                                         if (i != j) { 
    979                                                 final AlignmentAlgorithm aa = AlignmentAlgorithmFactory 
    980                                                                 .create(); 
    981                                                 aa.align(ns1, ns2, appData.getSubmat(), 9); 
    982                                                 synchronized (appData.getMatchseqs()) { 
    983                                                         appData.getMatchseqs().addAll(aa.getMatches()); 
    984                                                 } 
    985                                         } 
    986                                 } 
    987                         } 
    988                 } 
    989         } 
    990  
    991         /** 
    992          * The Class ParallelPairwiseAligner. 
    993          */ 
    994         private class ParallelMatchReplacer implements Runnable { 
    995  
    996                 /** The app data. */ 
    997                 private final RuleApplicationData appData; 
    998  
    999                 /** The from. */ 
    1000                 private final int from; 
    1001  
    1002                 /** The to. */ 
    1003                 private final int to; 
    1004  
    1005                 /** 
    1006                  * Instantiates a new parallel pairwise aligner. 
    1007                  * 
    1008                  * @param appData 
    1009                  *            the app data 
    1010                  * @param from 
    1011                  *            the from 
    1012                  * @param to 
    1013                  *            the to 
    1014                  */ 
    1015                 ParallelMatchReplacer(RuleApplicationData appData, int from, int to) { 
    1016                         this.appData = appData; 
    1017                         this.from = from; 
    1018                         this.to = to; 
    1019                 } 
    1020  
    1021                 /* 
    1022                  * (non-Javadoc) 
    1023                  *  
    1024                  * @see java.lang.Runnable#run() 
    1025                  */ 
    1026                 @Override 
    1027                 public void run() { 
    1028                         for (int i = from; i <= to; i++) { 
    1029                                  
    1030                                 /* 
    1031                                  * HashMap for keeping track in which sequence which replacement has 
    1032                                  * been performed. Neccessary for updating the indices of other 
    1033                                  * occurrences accordingly 
    1034                                  */ 
    1035                                 LinkedList<MatchOccurrence> replacedOccurrences = new LinkedList<MatchOccurrence>(); 
    1036                                 invalidOccurence: while (!appData.getPlannedReplacements()[i] 
    1037                                                 .isEmpty()) { 
    1038  
    1039                                         Match m = appData.getPlannedReplacements()[i].remove(); 
    1040                                         // Occurrences list has just one child 
    1041                                         MatchOccurrence oc = m.getOccurences().getFirst(); 
    1042                                         // check if we have any replaced occurrence with 
    1043                                         // indexes 
    1044                                         // smaller than ours. If so, we need to adjust 
    1045                                         // our start and end points of the replacement. 
    1046                                         // Also do a check if we have replaced this 
    1047                                         // specific MatchOccurence in this sequence already. 
    1048                                         // Jump to the next occurrence if this is the case. 
    1049                                         // This is no more necessary once the matches 
    1050                                         // are harmonized. 
    1051  
    1052                                         for (final Iterator<MatchOccurrence> jt = replacedOccurrences 
    1053                                                         .iterator(); jt.hasNext();) { 
    1054                                                 final MatchOccurrence tmpOC = jt.next(); 
    1055  
    1056                                                 if ((oc.getStartindex() >= tmpOC.getStartindex()) 
    1057                                                                 && (oc.getStartindex() <= tmpOC.getEndindex())) { 
    1058                                                         continue invalidOccurence; 
    1059                                                 } 
    1060                                                 if (oc.getEndindex() >= tmpOC.getStartindex()) { 
    1061                                                         continue invalidOccurence; 
    1062  
    1063                                                 } else if (oc.getStartindex() > tmpOC.getEndindex()) { 
    1064                                                         final int diff = tmpOC.getEndindex() 
    1065                                                                         - tmpOC.getStartindex(); 
    1066                                                         // Just to be sure. 
    1067                                                         if (diff > 0) { 
    1068                                                                 oc.setStartindex((oc.getStartindex() - diff) + 1); 
    1069                                                                 oc.setEndindex((oc.getEndindex() - diff) + 1); 
    1070                                                         } else { 
    1071                                                                 Console.traceln(Level.WARNING, 
    1072                                                                                 "End index of a Match before start. This should never happen"); 
    1073                                                         } 
    1074                                                 } 
    1075                                         } 
    1076                                         synchronized (appData) { 
    1077                                                 appData.detectedAndReplacedTasks = true; 
    1078                                         } 
    1079                                         final ISequence task = matchAsSequence(appData, m); 
    1080                                         final ISequenceInstance sequenceInstances = RuleUtils 
    1081                                                         .createNewSubSequenceInRange(appData.getSessions() 
    1082                                                                         .get(oc.getSequenceId()), oc 
    1083                                                                         .getStartindex(), oc.getEndindex(), task, 
    1084                                                                         taskFactory, taskBuilder); 
    1085  
    1086                                         // Adjust the length of the match regarding to the 
    1087                                         // length of 
    1088                                         // instance. (OptionalInstances may be shorter) 
    1089                                         oc.setEndindex((oc.getStartindex() + sequenceInstances 
    1090                                                         .size()) - RuleUtils.missedOptionals); 
    1091  
    1092                                         replacedOccurrences.add(oc); 
    1093                                 } 
    1094                         } 
    1095                 } 
    1096         } 
    1097  
    1098         /** 
    1099          * The Class RuleApplicationData. 
    1100          */ 
    1101         private static class RuleApplicationData implements Serializable { 
    1102  
    1103                 /** The Constant serialVersionUID. */ 
    1104                 private static final long serialVersionUID = -7559657686755522960L; 
    1105  
    1106                 /** 
    1107                  * The number2task HashMap. Since we align the tasks just by their 
    1108                  * integer id, we need this to convert them back to Tasks again 
    1109                  */ 
    1110                 private final HashMap<Integer, ITask> number2task; 
    1111  
    1112                 /** 
    1113                  * The unique tasks, keeps track about all unique tasks TODO: We 
    1114                  * Actually just need number2task here, this structure can be removed in 
    1115                  * the future. 
    1116                  */ 
    1117                 private final HashSet<ITask> uniqueTasks; 
    1118  
    1119                 /** 
    1120                  * The substitution matrix used by the alignment algorithm to be able to 
    1121                  * compare distances of tasks 
    1122                  */ 
    1123                 private final ObjectDistanceSubstitionMatrix submat; 
    1124  
    1125                 private PriorityQueue<Match>[] plannedReplacements; 
    1126  
    1127                 /** The list of all found matches */ 
    1128                 private LinkedList<Match> matchseqs; 
    1129  
    1130                 /** 
    1131                  * The generated NumberSequences. This is the integer representation of 
    1132                  * the user sessions 
    1133                  */ 
    1134                 private ArrayList<NumberSequence> numberseqs; 
    1135  
    1136                 /** The list of newly created tasks (of one iteration). */ 
    1137                 private final LinkedList<ITask> newTasks; 
    1138  
    1139                 /** The user sessions containing all EventTasks/Instances */ 
    1140                 private final List<IUserSession> sessions; 
    1141  
    1142                 /** True if we replaced something in the user sessions in one iteration. */ 
    1143                 private boolean detectedAndReplacedTasks; 
    1144  
    1145                 /** The result we return from this rule */ 
    1146                 private final RuleApplicationResult result; 
    1147  
    1148                 /** Stop Watch to measure performance */ 
    1149                 private final StopWatch stopWatch; 
    1150  
    1151                 /** 
    1152                  * Instantiates a new rule application data. 
    1153                  * 
    1154                  * @param sessions 
    1155                  *            The user sessions 
    1156                  */ 
    1157                 private RuleApplicationData(List<IUserSession> sessions) { 
    1158                         this.sessions = sessions; 
    1159                         numberseqs = new ArrayList<NumberSequence>(); 
    1160                         uniqueTasks = new HashSet<ITask>(); 
    1161                         number2task = new HashMap<Integer, ITask>(); 
    1162                         stopWatch = new StopWatch(); 
    1163                         result = new RuleApplicationResult(); 
    1164                         submat = new ObjectDistanceSubstitionMatrix(6, -3, false); 
    1165                         newTasks = new LinkedList<ITask>(); 
    1166                         this.detectedAndReplacedTasks = true; 
    1167                 } 
    1168  
    1169                 private void initializeQueues(int size) { 
    1170                         plannedReplacements = new PriorityQueue[size]; 
    1171                         for (int i = 0; i < size; i++) { 
    1172                                 plannedReplacements[i] = new PriorityQueue<Match>(); 
    1173                         } 
    1174                 } 
    1175  
    1176                 public Queue<Match>[] getPlannedReplacements() { 
    1177                         return plannedReplacements; 
    1178                 } 
    1179  
    1180                 /** 
    1181                  * Detected and replaced tasks. 
    1182                  * 
    1183                  * @return true, if successful 
    1184                  */ 
    1185                 private boolean detectedAndReplacedTasks() { 
    1186                         return detectedAndReplacedTasks; 
    1187                 } 
    1188  
    1189                 /** 
    1190                  * Gets the match sequences. 
    1191                  * 
    1192                  * @return the match sequences 
    1193                  */ 
    1194                 public LinkedList<Match> getMatchseqs() { 
    1195                         return matchseqs; 
    1196                 } 
    1197  
    1198                 /** 
    1199                  * Gets the new tasks. 
    1200                  * 
    1201                  * @return the new tasks 
    1202                  */ 
    1203                 public LinkedList<ITask> getNewTasks() { 
    1204                         return newTasks; 
    1205                 } 
    1206  
    1207                 /** 
    1208                  * Gets the number2task. 
    1209                  * 
    1210                  * @return the number2task HashMap 
    1211                  */ 
    1212                 private HashMap<Integer, ITask> getNumber2Task() { 
    1213                         return number2task; 
    1214                 } 
    1215  
    1216                 /** 
    1217                  * Gets the number sequences. 
    1218                  * 
    1219                  * @return the number sequences 
    1220                  */ 
    1221                 private ArrayList<NumberSequence> getNumberSequences() { 
    1222                         return numberseqs; 
    1223                 } 
    1224  
    1225                 /** 
    1226                  * Gets the result. 
    1227                  * 
    1228                  * @return the result 
    1229                  */ 
    1230                 private RuleApplicationResult getResult() { 
    1231                         return result; 
    1232                 } 
    1233  
    1234                 /** 
    1235                  * Gets the sessions. 
    1236                  * 
    1237                  * @return the UserSessions as List. 
    1238                  */ 
    1239                 private List<IUserSession> getSessions() { 
    1240                         return sessions; 
    1241                 } 
    1242  
    1243                 /** 
    1244                  * Gets the stop watch. 
    1245                  * 
    1246                  * @return the stopWatch 
    1247                  */ 
    1248                 private StopWatch getStopWatch() { 
    1249                         return stopWatch; 
    1250                 } 
    1251  
    1252                 /** 
    1253                  * Gets the substitution matrix. 
    1254                  * 
    1255                  * @return the substitution matrix 
    1256                  */ 
    1257                 private ObjectDistanceSubstitionMatrix getSubmat() { 
    1258                         return submat; 
    1259                 } 
    1260  
    1261                 /** 
    1262                  * Gets the unique tasks. 
    1263                  * 
    1264                  * @return the unique tasks 
    1265                  */ 
    1266                 private HashSet<ITask> getUniqueTasks() { 
    1267                         return uniqueTasks; 
    1268                 } 
    1269  
    1270                 /** 
    1271                  * New task created. 
    1272                  * 
    1273                  * @param task 
    1274                  *            can be called when new tasks are created to keep track of 
    1275                  *            all newly created tasks 
    1276                  */ 
    1277                 private void newTaskCreated(ITask task) { 
    1278                         number2task.put(task.getId(), task); 
    1279                         newTasks.add(task); 
    1280                 } 
    1281  
    1282                 /** 
    1283                  * Reset newly created tasks. 
    1284                  */ 
    1285                 synchronized private void resetNewlyCreatedTasks() { 
    1286                         uniqueTasks.addAll(newTasks); 
    1287                         newTasks.clear(); 
    1288                 } 
    1289  
    1290                 /** 
    1291                  * Sets the number sequences. 
    1292                  * 
    1293                  * @param numberseqs 
    1294                  *            the new number sequences 
    1295                  */ 
    1296                 private void setNumberSequences(ArrayList<NumberSequence> numberseqs) { 
    1297                         this.numberseqs = numberseqs; 
    1298                 } 
    1299  
    1300                 /** 
    1301                  * Update substitution matrix. 
    1302                  */ 
    1303                 private void updateSubstitutionMatrix() { 
    1304                         submat.update(getNewTasks()); 
    1305                         resetNewlyCreatedTasks(); 
    1306                 } 
    1307  
    1308         } 
     74    /** The n threads. */ 
     75    // public static int nThreads = Runtime.getRuntime().availableProcessors() - 1; 
     76    public static int nThreads = 1; 
     77 
     78    /** The iteration. */ 
     79    private int iteration = 0; 
     80 
     81    private int maxIterations = 1; 
     82 
     83    private static int alignmentThreshold = 9; 
     84    private static int gapPenalty = -3; 
     85 
     86    private static float maxSubstitutionScore = 6; 
     87 
     88    /** 
     89     * <p> 
     90     * the task factory to be used for creating substructures for the temporal relationships 
     91     * identified during rul application 
     92     * </p> 
     93     * . 
     94     */ 
     95    private final ITaskFactory taskFactory; 
     96 
     97    /** 
     98     * <p> 
     99     * the task builder to be used for creating substructures for the temporal relationships 
     100     * identified during rule application 
     101     * </p> 
     102     * . 
     103     */ 
     104    private final ITaskBuilder taskBuilder; 
     105 
     106    /** 
     107     * <p> 
     108     * the task handling strategy to be used for comparing tasks for preparation, i.e., before the 
     109     * tasks are harmonized 
     110     * </p> 
     111     */ 
     112    private final TaskHandlingStrategy preparationTaskHandlingStrategy; 
     113 
     114    /** 
     115     * <p> 
     116     * instantiates the rule and initializes it with a task equality to be considered when comparing 
     117     * tasks as well as a task factory and builder to be used for creating task structures. 
     118     * </p> 
     119     *  
     120     * @param minimalTaskEquality 
     121     *            the task equality to be considered when comparing tasks 
     122     * @param taskFactory 
     123     *            the task factory to be used for creating substructures 
     124     * @param taskBuilder 
     125     *            the task builder to be used for creating substructures 
     126     */ 
     127 
     128    SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality, 
     129                                          ITaskFactory taskFactory, 
     130                                          ITaskBuilder taskBuilder) 
     131    { 
     132        this.taskFactory = taskFactory; 
     133        this.taskBuilder = taskBuilder; 
     134 
     135        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality); 
     136    } 
     137 
     138    /* 
     139     * (non-Javadoc) 
     140     *  
     141     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply (java.util.List) 
     142     */ 
     143    @Override 
     144    public RuleApplicationResult apply(List<IUserSession> sessions) { 
     145        final RuleApplicationData appData = new RuleApplicationData(sessions); 
     146 
     147        harmonizeEventTaskInstancesModel(appData); 
     148 
     149        Console.traceln(Level.INFO, "generating substitution matrix from " + 
     150            appData.getUniqueTasks().size() + " unique tasks"); 
     151        appData.getStopWatch().start("substitution matrix"); 
     152        appData.getSubmat().generate(appData.getUniqueTasks()); 
     153        appData.getStopWatch().stop("substitution matrix"); 
     154 
     155        Console.traceln(Level.INFO, "Starting main loop"); 
     156        do { 
     157            Console.traceln(Level.INFO, "Iteration Number: " + iteration); 
     158            iteration++; 
     159            appData.detectedAndReplacedTasks = false; 
     160            appData.getStopWatch().start("whole loop"); 
     161            detectAndReplaceIterations(appData); 
     162            appData.getStopWatch().start("task replacement"); 
     163            // Just does anything if the substitution matrix is created with the 
     164            // option to do so 
     165            appData.updateSubstitutionMatrix(); 
     166            detectAndReplaceTasks(appData); // 
     167            appData.getStopWatch().stop("task replacement"); 
     168            appData.getStopWatch().stop("whole loop"); 
     169            // appData.getStopWatch().dumpStatistics(System.out); 
     170            appData.getStopWatch().reset(); 
     171 
     172            // } while (appData.detectedAndReplacedTasks()||iteration < maxIterations); 
     173        } 
     174        while (iteration < maxIterations); 
     175        Console.println("created " + appData.getResult().getNewlyCreatedTasks().size() + 
     176            " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() + 
     177            " appropriate instances\n"); 
     178 
     179        if ((appData.getResult().getNewlyCreatedTasks().size() > 0) || 
     180            (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) 
     181        { 
     182            appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED); 
     183        } 
     184        // new TaskTreeValidator().validate(appData.getSessions()); 
     185        return appData.getResult(); 
     186    } 
     187 
     188    /** 
     189     * Creates the number sequences. 
     190     * 
     191     * @param appData 
     192     *            the app data 
     193     * @return the array list 
     194     */ 
     195    private ArrayList<NumberSequence> createNumberSequences(RuleApplicationData appData) { 
     196        final ArrayList<NumberSequence> result = new ArrayList<NumberSequence>(); 
     197        for (int i = 0; i < appData.getSessions().size(); i++) { 
     198            final IUserSession session = appData.getSessions().get(i); 
     199            final NumberSequence templist = new NumberSequence(session.size()); 
     200            for (int j = 0; j < session.size(); j++) { 
     201                final ITaskInstance taskInstance = session.get(j); 
     202                templist.getSequence()[j] = taskInstance.getTask().getId(); 
     203            } 
     204            // Each NumberSequence is identified by its id, beginning to count 
     205            // at zero 
     206            templist.setId(i); 
     207            result.add(templist); 
     208        } 
     209        return result; 
     210    } 
     211 
     212    /** 
     213     * <p> 
     214     * searches for direct iterations of single tasks in all sequences and replaces them with 
     215     * {@link IIteration}s, respectively appropriate instances. Also all single occurrences of a 
     216     * task that is iterated somewhen are replaced with iterations to have again an efficient way 
     217     * for task comparisons. 
     218     * </p> 
     219     *  
     220     * @param appData 
     221     *            the rule application data combining all data used for applying this rule 
     222     */ 
     223    private void detectAndReplaceIterations(RuleApplicationData appData) { 
     224        Console.traceln(Level.FINE, "detecting iterations"); 
     225        appData.getStopWatch().start("detecting iterations"); 
     226 
     227        final List<IUserSession> sessions = appData.getSessions(); 
     228 
     229        final Set<ITask> iteratedTasks = searchIteratedTasks(sessions); 
     230 
     231        if (iteratedTasks.size() > 0) { 
     232            replaceIterationsOf(iteratedTasks, sessions, appData); 
     233        } 
     234 
     235        appData.getStopWatch().stop("detecting iterations"); 
     236        Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks"); 
     237    } 
     238 
     239    /** 
     240     * Detect and replace tasks. 
     241     * 
     242     * @param appData 
     243     *            the rule application data combining all data used for applying this rule 
     244     */ 
     245    private void detectAndReplaceTasks(RuleApplicationData appData) { 
     246        Console.traceln(Level.FINE, "detecting and replacing tasks"); 
     247        appData.getStopWatch().start("detecting tasks"); 
     248 
     249        // Create NumberSequences 
     250        appData.setNumberSequences(this.createNumberSequences(appData)); 
     251 
     252        // Generate pairwise alignments 
     253        // appData.setMatchseqs(generatePairwiseAlignments(appData)); 
     254        generatePairwiseAlignments(appData); 
     255        Console.traceln(Level.FINE, "Found " + appData.getMatchseqs().size() + " results"); 
     256 
     257        // Nothing found, we can end here 
     258        if (appData.getMatchseqs().size() == 0) { 
     259            appData.detectedAndReplacedTasks = false; 
     260            return; 
     261        } 
     262 
     263        // Searching each match in all other sessions, counting its occurences 
     264        searchMatchesInAllSessions(appData); 
     265 
     266        // Sort results to get the most occurring results 
     267        Console.traceln(Level.INFO, "sorting " + appData.getMatchseqs().size() + " results"); 
     268        final Comparator<Match> comparator = new Comparator<Match>() { 
     269            @Override 
     270            public int compare(Match m1, Match m2) { 
     271                int cmp = m2.occurenceCount() - m1.occurenceCount(); 
     272                if (cmp != 0) { 
     273                    return cmp; 
     274                } 
     275                else { 
     276                    cmp = m2.size() - m1.size(); 
     277                    if (cmp != 0) { 
     278                        return cmp; 
     279                    } 
     280                    else { 
     281                        // This should rarely happen 
     282                        cmp = m2.ocurrenceIDSum() - m1.ocurrenceIDSum(); 
     283                        if (cmp != 0) { 
     284                            return cmp; 
     285                        } 
     286                        else { 
     287                            cmp = m2.taskIdSum() - m1.taskIdSum(); 
     288 
     289                            return cmp; 
     290                        } 
     291                    } 
     292                } 
     293            } 
     294        }; 
     295 
     296        Collections.sort(appData.getMatchseqs(), comparator); 
     297        appData.getStopWatch().stop("detecting tasks"); 
     298 
     299        Console.traceln(Level.INFO, "Preparing replacments"); 
     300        prepareReplacements(appData); 
     301        Console.traceln(Level.INFO, "Replacing matches in sessions"); 
     302        appData.getStopWatch().start("replacing tasks"); 
     303        replaceMatches(appData); 
     304        appData.getStopWatch().stop("replacing tasks"); 
     305    } 
     306 
     307    // TODO: DEBUG METHOD 
     308    @SuppressWarnings("unused") 
     309    private void printMatches(RuleApplicationData appData) { 
     310        LinkedList<Match> matchseqs = appData.getMatchseqs(); 
     311        if (iteration > 1) { 
     312            System.out.println("PRINTING MATCHES"); 
     313            for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) { 
     314                Match m = it.next(); 
     315                m.getFirstSequence().printSequence(); 
     316                m.getSecondSequence().printSequence(); 
     317                for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt.hasNext();) { 
     318                    MatchOccurrence mo = jt.next(); 
     319                    System.out.print(mo.getSequenceId() + " "); 
     320                } 
     321                System.out.println(); 
     322                System.out.println(); 
     323            } 
     324        } 
     325    } 
     326 
     327    /** 
     328     * <p> 
     329     * harmonizes the event task instances by unifying tasks. This is done, as initially the event 
     330     * tasks being equal with respect to the considered task equality are distinct objects. The 
     331     * comparison of these distinct objects is more time consuming than comparing the object 
     332     * references. 
     333     * </p> 
     334     *  
     335     * @param appData 
     336     *            the rule application data combining all data used for applying this rule 
     337     * @return Returns the unique tasks symbol map 
     338     */ 
     339    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) { 
     340        Console.traceln(Level.INFO, "harmonizing task model of event task instances"); 
     341        appData.getStopWatch().start("harmonizing event tasks"); 
     342        final SymbolMap<ITaskInstance, ITask> uniqueTasks = 
     343            preparationTaskHandlingStrategy.createSymbolMap(); 
     344 
     345        final TaskInstanceComparator comparator = 
     346            preparationTaskHandlingStrategy.getTaskComparator(); 
     347 
     348        int unifiedTasks = 0; 
     349        ITask task; 
     350        final List<IUserSession> sessions = appData.getSessions(); 
     351        for (int j = 0; j < sessions.size(); j++) { 
     352            final IUserSession session = sessions.get(j); 
     353 
     354            for (int i = 0; i < session.size(); i++) { 
     355                final ITaskInstance taskInstance = session.get(i); 
     356                task = uniqueTasks.getValue(taskInstance); 
     357 
     358                if (task == null) { 
     359                    uniqueTasks.addSymbol(taskInstance, taskInstance.getTask()); 
     360                    appData.getUniqueTasks().add(taskInstance.getTask()); 
     361                    appData.getNumber2Task().put(taskInstance.getTask().getId(), 
     362                                                 taskInstance.getTask()); 
     363                } 
     364                else { 
     365                    taskBuilder.setTask(taskInstance, task); 
     366                    unifiedTasks++; 
     367                } 
     368            } 
     369            comparator.clearBuffers(); 
     370        } 
     371 
     372        appData.getStopWatch().stop("harmonizing event tasks"); 
     373        Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " + 
     374            appData.getUniqueTasks().size() + " different tasks)"); 
     375 
     376        appData.getStopWatch().dumpStatistics(System.out); 
     377        appData.getStopWatch().reset(); 
     378    } 
     379 
     380    /** 
     381     * <p> 
     382     * TODO clarify why this is done (in fact, ask Patrick Harms) 
     383     * </p> 
     384     * . 
     385     * 
     386     * @param iteration 
     387     *            the iteration 
     388     * @param iterationInstances 
     389     *            the iteration instances 
     390     */ 
     391    private void harmonizeIterationInstancesModel(IIteration iteration, 
     392                                                  List<IIterationInstance> iterationInstances) 
     393    { 
     394        final List<ITask> iteratedTaskVariants = new LinkedList<ITask>(); 
     395        final TaskInstanceComparator comparator = 
     396            preparationTaskHandlingStrategy.getTaskComparator(); 
     397 
     398        // merge the lexically different variants of iterated task to a unique 
     399        // list 
     400        for (final IIterationInstance iterationInstance : iterationInstances) { 
     401            for (final ITaskInstance executionVariant : iterationInstance) { 
     402                final ITask candidate = executionVariant.getTask(); 
     403 
     404                boolean found = false; 
     405                for (final ITask taskVariant : iteratedTaskVariants) { 
     406                    if (comparator.areLexicallyEqual(taskVariant, candidate)) { 
     407                        taskBuilder.setTask(executionVariant, taskVariant); 
     408                        found = true; 
     409                        break; 
     410                    } 
     411                } 
     412 
     413                if (!found) { 
     414                    iteratedTaskVariants.add(candidate); 
     415                } 
     416            } 
     417        } 
     418 
     419        // if there are more than one lexically different variant of iterated 
     420        // tasks, adapt the 
     421        // iteration model to be a selection of different variants. In this case 
     422        // also adapt 
     423        // the generated iteration instances to correctly contain selection 
     424        // instances. If there 
     425        // is only one variant of an iterated task, simply set this as the 
     426        // marked task of the 
     427        // iteration. In this case, the instances can be preserved as is 
     428        if (iteratedTaskVariants.size() > 1) { 
     429            final ISelection selection = taskFactory.createNewSelection(); 
     430 
     431            for (final ITask variant : iteratedTaskVariants) { 
     432                taskBuilder.addChild(selection, variant); 
     433            } 
     434 
     435            taskBuilder.setMarkedTask(iteration, selection); 
     436 
     437            for (final IIterationInstance instance : iterationInstances) { 
     438                for (int i = 0; i < instance.size(); i++) { 
     439                    final ISelectionInstance selectionInstance = 
     440                        taskFactory.createNewTaskInstance(selection); 
     441                    taskBuilder.setChild(selectionInstance, instance.get(i)); 
     442                    taskBuilder.setTaskInstance(instance, i, selectionInstance); 
     443                } 
     444            } 
     445        } 
     446        else { 
     447            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0)); 
     448        } 
     449    } 
     450 
     451    /** 
     452     * Match as sequence. 
     453     * 
     454     * @param appData 
     455     *            RuleApplicationData needed to keep track of all created tasks 
     456     * @param m 
     457     *            The match to be converted into a Task 
     458     * @return The task of the match with an ISequence as its root 
     459     */ 
     460    synchronized public ISequence matchAsSequence(RuleApplicationData appData, Match m) { 
     461        final ISequence sequence = taskFactory.createNewSequence(); 
     462        appData.newTaskCreated(sequence); 
     463 
     464        final int[] first = m.getFirstSequence().getSequence(); 
     465        final int[] second = m.getSecondSequence().getSequence(); 
     466 
     467        // Both sequences of a match are equally long 
     468        for (int i = 0; i < m.getFirstSequence().size(); i++) { 
     469 
     470            // Two gaps aligned to each other: Have not seen it happening so 
     471            // far, just to handle it 
     472            if ((first[i] == -1) && (second[i] == -1)) { 
     473                // Do nothing here. 
     474            } 
     475            // Both events are equal, we can simply add the task referring to 
     476            // the number 
     477            else if (first[i] == second[i]) { 
     478                taskBuilder.addChild(sequence, appData.getNumber2Task().get(first[i])); 
     479            } 
     480            // We have a gap in the first sequence, we need to add the task of 
     481            // the second sequence as optional 
     482            else if ((first[i] == -1) && (second[i] != -1)) { 
     483                final IOptional optional = taskFactory.createNewOptional(); 
     484                appData.newTaskCreated(optional); 
     485                taskBuilder.setMarkedTask(optional, appData.getNumber2Task().get(second[i])); 
     486                taskBuilder.addChild(sequence, optional); 
     487            } 
     488            // We have a gap in the second sequence, we need to add the task of 
     489            // the first sequence as optional 
     490            else if ((first[i] != -1) && (second[i] == -1)) { 
     491                final IOptional optional = taskFactory.createNewOptional(); 
     492                appData.newTaskCreated(optional); 
     493                taskBuilder.setMarkedTask(optional, appData.getNumber2Task().get(first[i])); 
     494                taskBuilder.addChild(sequence, optional); 
     495            } 
     496            // Both tasks are not equal, we need to insert a selection here. 
     497            // Now things get complicated. We first need to check 
     498            // if the next position is not a selection. Then we can just create 
     499            // a selection 
     500            // of the both Tasks 
     501            // In the other case (more than one selection following this 
     502            // selection), we want to 
     503            // create a selection of sequences where each sequence gets the 
     504            // corresponding task of 
     505            // the its sequence in the pattern. 
     506            // 
     507            else if (i < (first.length - 1)) { 
     508 
     509                if ((first[i] != second[i]) && 
     510                    (((first[i + 1] == second[i + 1]) || (first[i + 1] == -1) || (second[i + 1] == -1)))) 
     511                { 
     512 
     513                    final ISelection selection = taskFactory.createNewSelection(); 
     514                    appData.newTaskCreated(selection); 
     515                    taskBuilder.addChild(selection, appData.getNumber2Task().get(first[i])); 
     516                    taskBuilder.addChild(selection, appData.getNumber2Task().get(second[i])); 
     517                    taskBuilder.addChild(sequence, selection); 
     518                } 
     519                else { 
     520                    boolean selectionfound = true; 
     521                    final ISelection selection = taskFactory.createNewSelection(); 
     522                    appData.newTaskCreated(selection); 
     523 
     524                    final ISequence subsequence1 = taskFactory.createNewSequence(); 
     525                    appData.newTaskCreated(subsequence1); 
     526 
     527                    final ISequence subsequence2 = taskFactory.createNewSequence(); 
     528                    appData.newTaskCreated(subsequence2); 
     529 
     530                    taskBuilder.addChild(selection, subsequence1); 
     531                    taskBuilder.addChild(selection, subsequence2); 
     532                    taskBuilder.addChild(sequence, selection); 
     533                    // TODO: We may not run till the end! 
     534                    while ((i < (first.length - 1)) && selectionfound) { 
     535                        selectionfound = false; 
     536                        taskBuilder.addChild(subsequence1, appData.getNumber2Task().get(first[i])); 
     537                        taskBuilder.addChild(subsequence2, appData.getNumber2Task().get(second[i])); 
     538                        if ((first[i + 1] != second[i + 1]) && (first[i + 1] != -1) && 
     539                            (second[i + 1] != -1)) 
     540                        { 
     541                            selectionfound = true; 
     542                        } 
     543                        else { 
     544                            continue; 
     545                        } 
     546                        i++; 
     547                    } 
     548                    if ((i == (first.length - 1)) && selectionfound) { 
     549                        taskBuilder.addChild(subsequence1, appData.getNumber2Task().get(first[i])); 
     550                        taskBuilder.addChild(subsequence2, appData.getNumber2Task().get(second[i])); 
     551                    } 
     552                } 
     553            } 
     554            else { 
     555                // i = length-1 
     556                if ((first[i] != second[i])) { 
     557 
     558                    final ISelection selection = taskFactory.createNewSelection(); 
     559                    appData.newTaskCreated(selection); 
     560                    taskBuilder.addChild(selection, appData.getNumber2Task().get(first[i])); 
     561                    taskBuilder.addChild(selection, appData.getNumber2Task().get(second[i])); 
     562                    taskBuilder.addChild(sequence, selection); 
     563                } 
     564            } 
     565 
     566        } 
     567        return sequence; 
     568    } 
     569 
     570    /** 
     571     * <p> 
     572     * replaces all occurrences of all tasks provided in the set with iterations 
     573     * </p> 
     574     * . 
     575     * 
     576     * @param iteratedTasks 
     577     *            the tasks to be replaced with iterations 
     578     * @param sessions 
     579     *            the sessions in which the tasks are to be replaced 
     580     * @param appData 
     581     *            the rule application data combining all data used for applying this rule 
     582     */ 
     583    private void replaceIterationsOf(Set<ITask> iteratedTasks, 
     584                                     List<IUserSession> sessions, 
     585                                     RuleApplicationData appData) 
     586    { 
     587        final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>(); 
     588        final Map<IIteration, List<IIterationInstance>> iterationInstances = 
     589            new HashMap<IIteration, List<IIterationInstance>>(); 
     590 
     591        for (final ITask iteratedTask : iteratedTasks) { 
     592 
     593            final IIteration iteration = taskFactory.createNewIteration(); 
     594            appData.newTaskCreated(iteration); 
     595            iterations.put(iteratedTask, iteration); 
     596            iterationInstances.put(iteration, new LinkedList<IIterationInstance>()); 
     597        } 
     598 
     599        IIterationInstance iterationInstance; 
     600 
     601        for (final IUserSession session : sessions) { 
     602            int index = 0; 
     603            iterationInstance = null; 
     604 
     605            while (index < session.size()) { 
     606                // we prepared the task instances to refer to unique tasks, if 
     607                // they are treated 
     608                // as equal. Therefore, we just compare the identity of the 
     609                // tasks of the task 
     610                // instances 
     611                final ITask currentTask = session.get(index).getTask(); 
     612                final IIteration iteration = iterations.get(currentTask); 
     613                if (iteration != null) { 
     614                    if ((iterationInstance == null) || (iterationInstance.getTask() != iteration)) { 
     615                        iterationInstance = taskFactory.createNewTaskInstance(iteration); 
     616                        iterationInstances.get(iteration).add(iterationInstance);// TODO:: Don't 
     617                                                                                 // create 
     618                        // TaskInstances here, 
     619                        // use a set of tasks 
     620                        // instead 
     621                        taskBuilder.addTaskInstance(session, index, iterationInstance); 
     622                        index++; 
     623                    } 
     624 
     625                    taskBuilder.addChild(iterationInstance, session.get(index)); 
     626                    taskBuilder.removeTaskInstance(session, index); 
     627                } 
     628                else { 
     629                    if (iterationInstance != null) { 
     630                        iterationInstance = null; 
     631                    } 
     632                    index++; 
     633                } 
     634            } 
     635        } 
     636 
     637        for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances 
     638            .entrySet()) 
     639        { 
     640            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue()); 
     641        } 
     642    } 
     643 
     644    /** 
     645     * Prepare replacements. 
     646     * 
     647     * @param appData 
     648     *            the app data 
     649     */ 
     650    private void prepareReplacements(RuleApplicationData appData) { 
     651        appData.initializeQueues(appData.getSessions().size()); 
     652        int taskId=0; 
     653        for (Iterator<Match> it = appData.getMatchseqs().iterator(); it.hasNext();) { 
     654            Match m = it.next(); 
     655            if (m.getOccurences().size() > 2) { 
     656                final ISequence task = matchAsSequence(appData, m); 
     657                appData.getPreparedTasks().add(task); 
     658                 
     659                for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt.hasNext();) { 
     660                    MatchOccurrence mo = jt.next(); 
     661                    // System.out.println("Found this match in sequence " +mo.getSequenceId()); 
     662                    PlannedReplacement pr = new PlannedReplacement(taskId,mo); 
     663                    // System.out.println("Adding match to sequence " + mo.getSequenceId()); 
     664                    appData.getPlannedReplacements()[mo.getSequenceId()].add(pr); 
     665                } 
     666                taskId++; 
     667            } 
     668        } 
     669    } 
     670 
     671    /** 
     672     * Replace matches. 
     673     * 
     674     * @param appData 
     675     *            the app data 
     676     */ 
     677    private void replaceMatches(RuleApplicationData appData) { 
     678 
     679        final int numberSeqSize = appData.getNumberSequences().size(); 
     680        Console.traceln(Level.INFO, "replacing matches with " + nThreads + " threads"); 
     681        int newThreads = nThreads; 
     682        if (numberSeqSize < nThreads) { 
     683            newThreads = numberSeqSize; 
     684        } 
     685        final int interval = numberSeqSize / newThreads; 
     686        int rest = numberSeqSize % newThreads; 
     687        final ExecutorService executor = Executors.newFixedThreadPool(nThreads); 
     688        for (int i = 0; i <= (numberSeqSize - interval); i += interval) { 
     689            int offset = 0; 
     690            if (rest != 0) { 
     691                offset = 1; 
     692                rest--; 
     693            } 
     694            final int from = i; 
     695            final int to = i + interval + offset - 1; 
     696            Console.traceln(Level.FINE, "Match replacing: Creating thread with matches from " + 
     697                from + " to " + to); 
     698            // search each match in every other sequence 
     699            final ParallelMatchReplacer replacer = new ParallelMatchReplacer(appData, from, to); 
     700            executor.execute(replacer); 
     701            i += offset; 
     702        } 
     703        executor.shutdown(); 
     704        try { 
     705            executor.awaitTermination(2, TimeUnit.HOURS); 
     706        } 
     707        catch (final InterruptedException e) { 
     708            e.printStackTrace(); 
     709        } 
     710    } 
     711 
     712    /** 
     713     * <p> 
     714     * searches the provided sessions for task iterations. If a task is iterated, it is added to the 
     715     * returned set. 
     716     * </p> 
     717     * 
     718     * @param sessions 
     719     *            the sessions 
     720     * @return a set of tasks being iterated somewhere 
     721     */ 
     722    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) { 
     723        final Set<ITask> iteratedTasks = new HashSet<ITask>(); 
     724        for (final IUserSession session : sessions) { 
     725            for (int i = 0; i < (session.size() - 1); i++) { 
     726                // we prepared the task instances to refer to unique tasks, if 
     727                // they are treated 
     728                // as equal. Therefore, we just compare the identity of the 
     729                // tasks of the task 
     730                // instances 
     731                if (session.get(i).getTask() == session.get(i + 1).getTask()) { 
     732                    iteratedTasks.add(session.get(i).getTask()); 
     733                } 
     734            } 
     735        } 
     736        return iteratedTasks; 
     737    } 
     738 
     739    /** 
     740     * Generate pairwise alignments. 
     741     * 
     742     * @param appData 
     743     *            the app data 
     744     */ 
     745    private void generatePairwiseAlignments(RuleApplicationData appData) { 
     746        final int numberSeqSize = appData.getNumberSequences().size(); 
     747        appData.matchseqs = new LinkedList<Match>(); 
     748        Console.traceln(Level.INFO, "generating pairwise alignments from " + numberSeqSize + 
     749            " sessions with " + nThreads + " threads"); 
     750 
     751        int newThreads = nThreads; 
     752        if (numberSeqSize < nThreads) { 
     753            newThreads = numberSeqSize; 
     754        } 
     755 
     756        final ExecutorService executor = Executors.newFixedThreadPool(newThreads); 
     757        final int interval = numberSeqSize / newThreads; 
     758        int rest = numberSeqSize % newThreads; 
     759        Console.traceln(Level.FINE, "Interval: " + interval + " Rest: " + rest); 
     760        for (int i = 0; i <= (numberSeqSize - interval); i += interval) { 
     761            int offset = 0; 
     762            if (rest != 0) { 
     763                offset = 1; 
     764                rest--; 
     765            } 
     766 
     767            final int from = i; 
     768            final int to = i + interval + offset - 1; 
     769            Console.traceln(Level.FINER, "Aligning: Creating thread for sessions " + from + 
     770                " till " + to); 
     771            final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(appData, from, to); 
     772            executor.execute(aligner); 
     773            i += offset; 
     774        } 
     775        executor.shutdown(); 
     776        try { 
     777            executor.awaitTermination(2, TimeUnit.HOURS); 
     778        } 
     779        catch (final InterruptedException e) { 
     780            e.printStackTrace(); 
     781        } 
     782    } 
     783 
     784    /** 
     785     * Search matches in all sessions. 
     786     * 
     787     * @param appData 
     788     *            the app data 
     789     */ 
     790    private void searchMatchesInAllSessions(RuleApplicationData appData) { 
     791 
     792        // Prepare parallel search of matchseqs 
     793        final int matchSeqSize = appData.getMatchseqs().size(); 
     794        Console.traceln(Level.INFO, "searching for patterns (" + matchSeqSize + 
     795            ") occuring most with " + nThreads + " threads"); 
     796        int newThreads = nThreads; 
     797        if (matchSeqSize < nThreads) { 
     798            newThreads = matchSeqSize; 
     799        } 
     800        final int interval = matchSeqSize / newThreads; 
     801        int rest = matchSeqSize % newThreads; 
     802        final ExecutorService executor = Executors.newFixedThreadPool(nThreads); 
     803        Console.traceln(Level.FINER, "Interval: " + interval + " Rest: " + rest); 
     804        for (int i = 0; i <= (matchSeqSize - interval); i += interval) { 
     805            int offset = 0; 
     806            if (rest != 0) { 
     807                offset = 1; 
     808                rest--; 
     809            } 
     810            final int from = i; 
     811            final int to = i + interval + offset - 1; 
     812            Console.traceln(Level.FINE, "Match finding: Creating thread with matches from " + from + 
     813                " to " + to); 
     814            // search each match in every other sequence 
     815            final ParallelMatchOcurrencesFinder finder = 
     816                new ParallelMatchOcurrencesFinder(appData, from, to); 
     817            executor.execute(finder); 
     818            i += offset; 
     819        } 
     820        executor.shutdown(); 
     821        try { 
     822            executor.awaitTermination(2, TimeUnit.HOURS); 
     823        } 
     824        catch (final InterruptedException e) { 
     825            e.printStackTrace(); 
     826        } 
     827 
     828    } 
     829 
     830    /* 
     831     * (non-Javadoc) 
     832     *  
     833     * @see java.lang.Object#toString() 
     834     */ 
     835    @Override 
     836    public String toString() { 
     837        return "SequenceForTaskDetectionRuleAlignment"; 
     838    } 
     839 
     840    /** 
     841     * The Class ParallelMatchOcurrencesFinder. 
     842     */ 
     843    private class ParallelMatchOcurrencesFinder implements Runnable { 
     844 
     845        /** The app data. */ 
     846        private final RuleApplicationData appData; 
     847 
     848        /** The from. */ 
     849        private final int from; 
     850 
     851        /** The to. */ 
     852        private final int to; 
     853 
     854        /** 
     855         * Instantiates a new parallel match ocurrences finder. 
     856         * 
     857         * @param appData 
     858         *            the app data 
     859         * @param from 
     860         *            the from 
     861         * @param to 
     862         *            the to 
     863         */ 
     864        ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from, int to) { 
     865            this.appData = appData; 
     866            this.from = from; 
     867            this.to = to; 
     868        } 
     869 
     870        /* 
     871         * (non-Javadoc) 
     872         *  
     873         * @see java.lang.Runnable#run() 
     874         */ 
     875        @Override 
     876        public void run() { 
     877            int count = 0; 
     878            final int size = to + 1 - from; 
     879 
     880            for (int i = from; i <= to; i++) { 
     881                final Match pattern = appData.getMatchseqs().get(i); 
     882                count++; 
     883                RuleUtils.printProgressPercentage("Match finding progress", count, size); 
     884                // Skip sequences with more 0 events (scrolls) than other 
     885                // events. 
     886                // Both of the pattern sequences are equally long, so the zero 
     887                // counts just need to be smaller than the length of one 
     888                // sequence 
     889                if ((pattern.getFirstSequence().eventCount(0) + 
     890                    pattern.getSecondSequence().eventCount(0) + 1) > pattern.getFirstSequence() 
     891                    .size()) 
     892                { 
     893                    continue; 
     894                } 
     895 
     896                for (int j = 0; j < appData.getNumberSequences().size(); j++) { 
     897                    final LinkedList<Integer> startpositions = 
     898                        appData.getNumberSequences().get(j).containsPattern(pattern); 
     899                    if (startpositions.size() > 0) { 
     900                        for (final Iterator<Integer> jt = startpositions.iterator(); jt.hasNext();) 
     901                        { 
     902                            final int start = jt.next(); 
     903                            pattern.addOccurence(new MatchOccurrence(start, start + pattern.size(), 
     904                                                                     j)); 
     905                        } 
     906                    } 
     907                } 
     908            } 
     909        } 
     910    } 
     911 
     912    /** 
     913     * The Class ParallelPairwiseAligner. 
     914     */ 
     915    private class ParallelPairwiseAligner implements Runnable { 
     916 
     917        /** The app data. */ 
     918        private final RuleApplicationData appData; 
     919 
     920        /** The from. */ 
     921        private final int from; 
     922 
     923        /** The to. */ 
     924        private final int to; 
     925 
     926        /** 
     927         * Instantiates a new parallel pairwise aligner. 
     928         * 
     929         * @param appData 
     930         *            the app data 
     931         * @param from 
     932         *            the from 
     933         * @param to 
     934         *            the to 
     935         */ 
     936        ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) { 
     937            this.appData = appData; 
     938            this.from = from; 
     939            this.to = to; 
     940        } 
     941 
     942        /* 
     943         * (non-Javadoc) 
     944         *  
     945         * @see java.lang.Runnable#run() 
     946         */ 
     947        @Override 
     948        public void run() { 
     949            int count = 0; 
     950            final int size = to + 1 - from; 
     951 
     952            for (int i = from; i <= to; i++) { 
     953                final NumberSequence ns1 = appData.getNumberSequences().get(i); 
     954                count++; 
     955                RuleUtils.printProgressPercentage("Aligning Progress", count, size); 
     956                for (int j = 0; j < appData.getNumberSequences().size(); j++) { 
     957                    final NumberSequence ns2 = appData.getNumberSequences().get(j); 
     958                    if (i != j) { 
     959                        final AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); 
     960                        // threshold was 9 
     961                        aa.align(ns1, ns2, appData.getSubmat(), 
     962                                 SequenceForTaskDetectionRuleAlignment.alignmentThreshold); 
     963                        synchronized (appData.getMatchseqs()) { 
     964                            appData.getMatchseqs().addAll(aa.getMatches()); 
     965                        } 
     966                    } 
     967                } 
     968            } 
     969        } 
     970    } 
     971 
     972    /** 
     973     * The Class ParallelPairwiseAligner. 
     974     */ 
     975    private class ParallelMatchReplacer implements Runnable { 
     976 
     977        /** The app data. */ 
     978        private final RuleApplicationData appData; 
     979 
     980        /** The from. */ 
     981        private final int from; 
     982 
     983        /** The to. */ 
     984        private final int to; 
     985 
     986        /** 
     987         * Instantiates a new parallel pairwise aligner. 
     988         * 
     989         * @param appData 
     990         *            the app data 
     991         * @param from 
     992         *            the from 
     993         * @param to 
     994         *            the to 
     995         */ 
     996        ParallelMatchReplacer(RuleApplicationData appData, int from, int to) { 
     997            this.appData = appData; 
     998            this.from = from; 
     999            this.to = to; 
     1000        } 
     1001 
     1002        /* 
     1003         * (non-Javadoc) 
     1004         *  
     1005         * @see java.lang.Runnable#run() 
     1006         */ 
     1007        @Override 
     1008        public void run() { 
     1009            for (int i = from; i <= to; i++) { 
     1010                System.out.println("Replacing in SEQUENCE " + i); 
     1011                /* 
     1012                 * HashMap for keeping track in which sequence which replacement has been performed. 
     1013                 * Neccessary for updating the indices of other occurrences accordingly 
     1014                 */ 
     1015                LinkedList<MatchOccurrence> replacedOccurrences = new LinkedList<MatchOccurrence>(); 
     1016                invalidOccurence: while (!appData.getPlannedReplacements()[i].isEmpty()) { 
     1017 
     1018                    PlannedReplacement pr = appData.getPlannedReplacements()[i].remove(); 
     1019                     
     1020                    MatchOccurrence oc = pr.getOccurrence(); 
     1021                    // check if we have any replaced occurrence with 
     1022                    // indexes 
     1023                    // smaller than ours. If so, we need to adjust 
     1024                    // our start and end points of the replacement. 
     1025                    // Also do a check if we have replaced this 
     1026                    // specific MatchOccurence in this sequence already. 
     1027                    // Jump to the next occurrence if this is the case. 
     1028                    // This is no more necessary once the matches 
     1029                    // are harmonized. 
     1030 
     1031                    for (final Iterator<MatchOccurrence> jt = replacedOccurrences.iterator(); jt 
     1032                        .hasNext();) 
     1033                    { 
     1034                        final MatchOccurrence tmpOC = jt.next(); 
     1035 
     1036                        if ((oc.getStartindex() >= tmpOC.getStartindex()) && 
     1037                            (oc.getStartindex() <= tmpOC.getEndindex())) 
     1038                        { 
     1039                            continue invalidOccurence; 
     1040                        } 
     1041                        if (oc.getEndindex() >= tmpOC.getStartindex()) { 
     1042                            continue invalidOccurence; 
     1043 
     1044                        } 
     1045                        else if (oc.getStartindex() > tmpOC.getEndindex()) { 
     1046                            final int diff = tmpOC.getEndindex() - tmpOC.getStartindex(); 
     1047                            // Just to be sure. 
     1048                            if (diff > 0) { 
     1049                                oc.setStartindex((oc.getStartindex() - diff) + 1); 
     1050                                oc.setEndindex((oc.getEndindex() - diff) + 1); 
     1051                            } 
     1052                            else { 
     1053                                Console 
     1054                                    .traceln(Level.WARNING, 
     1055                                             "End index of a Match before start. This should never happen"); 
     1056                            } 
     1057                        } 
     1058                    } 
     1059                    synchronized (appData) { 
     1060                        appData.detectedAndReplacedTasks = true; 
     1061                    } 
     1062                    
     1063 
     1064                    System.out.println("Replacing in Sequence " + oc.getSequenceId() + 
     1065                        " at position " + oc.getStartindex() + " till " + oc.getEndindex()); 
     1066                    final ISequenceInstance sequenceInstances = 
     1067                        RuleUtils.createNewSubSequenceInRange(appData.getSessions() 
     1068                                                                  .get(oc.getSequenceId()), oc 
     1069                                                                  .getStartindex(), oc 
     1070                                                                  .getEndindex(), (ISequence) appData.getPreparedTasks().get(pr.getMatchId()), 
     1071                                                              taskFactory, taskBuilder); 
     1072 
     1073                    // Adjust the length of the match regarding to the 
     1074                    // length of 
     1075                    // instance. (OptionalInstances may be shorter) 
     1076                    oc.setEndindex((oc.getStartindex() + sequenceInstances.size()) - 
     1077                        RuleUtils.missedOptionals); 
     1078 
     1079                    replacedOccurrences.add(oc); 
     1080 
     1081                } 
     1082            } 
     1083        } 
     1084    } 
     1085     
     1086    private static class PlannedReplacement { 
     1087        private int matchId; 
     1088        private int getMatchId() { 
     1089            return matchId; 
     1090        } 
     1091 
     1092        private MatchOccurrence getOccurrence() { 
     1093            return occurrence; 
     1094        } 
     1095 
     1096        private MatchOccurrence occurrence; 
     1097         
     1098        private PlannedReplacement(int matchId,MatchOccurrence occurrence) { 
     1099            this.matchId = matchId; 
     1100            this.occurrence = occurrence; 
     1101        } 
     1102    } 
     1103 
     1104    /** 
     1105     * The Class RuleApplicationData. 
     1106     */ 
     1107    private static class RuleApplicationData implements Serializable { 
     1108 
     1109        /** The Constant serialVersionUID. */ 
     1110        private static final long serialVersionUID = -7559657686755522960L; 
     1111 
     1112        /** 
     1113         * The number2task HashMap. Since we align the tasks just by their integer id, we need this 
     1114         * to convert them back to Tasks again 
     1115         */ 
     1116        private final HashMap<Integer, ITask> number2task; 
     1117 
     1118        /** 
     1119         * The unique tasks, keeps track about all unique tasks TODO: We Actually just need 
     1120         * number2task here, this structure can be removed in the future. 
     1121         */ 
     1122        private final HashSet<ITask> uniqueTasks; 
     1123 
     1124        /** 
     1125         * The substitution matrix used by the alignment algorithm to be able to compare distances 
     1126         * of tasks 
     1127         */ 
     1128        private final ObjectDistanceSubstitionMatrix submat; 
     1129 
     1130        private LinkedList<PlannedReplacement>[] plannedReplacements; 
     1131 
     1132        /** The list of all found matches */ 
     1133        private LinkedList<Match> matchseqs; 
     1134         
     1135        private ArrayList<ITask> preparedTasks; 
     1136 
     1137        public ArrayList<ITask> getPreparedTasks() { 
     1138            return preparedTasks; 
     1139        } 
     1140 
     1141        /** 
     1142         * The generated NumberSequences. This is the integer representation of the user sessions 
     1143         */ 
     1144        private ArrayList<NumberSequence> numberseqs; 
     1145 
     1146        /** The list of newly created tasks (of one iteration). */ 
     1147        private final LinkedList<ITask> newTasks; 
     1148 
     1149        /** The user sessions containing all EventTasks/Instances */ 
     1150        private final List<IUserSession> sessions; 
     1151 
     1152        /** True if we replaced something in the user sessions in one iteration. */ 
     1153        private boolean detectedAndReplacedTasks; 
     1154 
     1155        /** The result we return from this rule */ 
     1156        private final RuleApplicationResult result; 
     1157 
     1158        /** Stop Watch to measure performance */ 
     1159        private final StopWatch stopWatch; 
     1160 
     1161        /** 
     1162         * Instantiates a new rule application data. 
     1163         * 
     1164         * @param sessions 
     1165         *            The user sessions 
     1166         */ 
     1167        private RuleApplicationData(List<IUserSession> sessions) { 
     1168            this.sessions = sessions; 
     1169            numberseqs = new ArrayList<NumberSequence>(); 
     1170            uniqueTasks = new HashSet<ITask>(); 
     1171            number2task = new HashMap<Integer, ITask>(); 
     1172            stopWatch = new StopWatch(); 
     1173            result = new RuleApplicationResult(); 
     1174            preparedTasks = new ArrayList<ITask>(); 
     1175            submat = new ObjectDistanceSubstitionMatrix(maxSubstitutionScore, gapPenalty, false); 
     1176            newTasks = new LinkedList<ITask>(); 
     1177            this.detectedAndReplacedTasks = true; 
     1178        } 
     1179 
     1180        private void initializeQueues(int size) { 
     1181            plannedReplacements = new LinkedList[size]; 
     1182            for (int i = 0; i < size; i++) { 
     1183                plannedReplacements[i] = new LinkedList<PlannedReplacement>(); 
     1184            } 
     1185        } 
     1186 
     1187        public Queue<PlannedReplacement>[] getPlannedReplacements() { 
     1188            return plannedReplacements; 
     1189        } 
     1190 
     1191        /** 
     1192         * Detected and replaced tasks. 
     1193         * 
     1194         * @return true, if successful 
     1195         */ 
     1196        private boolean detectedAndReplacedTasks() { 
     1197            return detectedAndReplacedTasks; 
     1198        } 
     1199 
     1200        /** 
     1201         * Gets the match sequences. 
     1202         * 
     1203         * @return the match sequences 
     1204         */ 
     1205        public LinkedList<Match> getMatchseqs() { 
     1206            return matchseqs; 
     1207        } 
     1208 
     1209        /** 
     1210         * Gets the new tasks. 
     1211         * 
     1212         * @return the new tasks 
     1213         */ 
     1214        public LinkedList<ITask> getNewTasks() { 
     1215            return newTasks; 
     1216        } 
     1217 
     1218        /** 
     1219         * Gets the number2task. 
     1220         * 
     1221         * @return the number2task HashMap 
     1222         */ 
     1223        private HashMap<Integer, ITask> getNumber2Task() { 
     1224            return number2task; 
     1225        } 
     1226 
     1227        /** 
     1228         * Gets the number sequences. 
     1229         * 
     1230         * @return the number sequences 
     1231         */ 
     1232        private ArrayList<NumberSequence> getNumberSequences() { 
     1233            return numberseqs; 
     1234        } 
     1235 
     1236        /** 
     1237         * Gets the result. 
     1238         * 
     1239         * @return the result 
     1240         */ 
     1241        private RuleApplicationResult getResult() { 
     1242            return result; 
     1243        } 
     1244 
     1245        /** 
     1246         * Gets the sessions. 
     1247         * 
     1248         * @return the UserSessions as List. 
     1249         */ 
     1250        private List<IUserSession> getSessions() { 
     1251            return sessions; 
     1252        } 
     1253 
     1254        /** 
     1255         * Gets the stop watch. 
     1256         * 
     1257         * @return the stopWatch 
     1258         */ 
     1259        private StopWatch getStopWatch() { 
     1260            return stopWatch; 
     1261        } 
     1262 
     1263        /** 
     1264         * Gets the substitution matrix. 
     1265         * 
     1266         * @return the substitution matrix 
     1267         */ 
     1268        private ObjectDistanceSubstitionMatrix getSubmat() { 
     1269            return submat; 
     1270        } 
     1271 
     1272        /** 
     1273         * Gets the unique tasks. 
     1274         * 
     1275         * @return the unique tasks 
     1276         */ 
     1277        private HashSet<ITask> getUniqueTasks() { 
     1278            return uniqueTasks; 
     1279        } 
     1280 
     1281        /** 
     1282         * New task created. 
     1283         * 
     1284         * @param task 
     1285         *            can be called when new tasks are created to keep track of all newly created 
     1286         *            tasks 
     1287         */ 
     1288        private void newTaskCreated(ITask task) { 
     1289            number2task.put(task.getId(), task); 
     1290            newTasks.add(task); 
     1291        } 
     1292 
     1293        /** 
     1294         * Reset newly created tasks. 
     1295         */ 
     1296        synchronized private void resetNewlyCreatedTasks() { 
     1297            uniqueTasks.addAll(newTasks); 
     1298            newTasks.clear(); 
     1299        } 
     1300 
     1301        /** 
     1302         * Sets the number sequences. 
     1303         * 
     1304         * @param numberseqs 
     1305         *            the new number sequences 
     1306         */ 
     1307        private void setNumberSequences(ArrayList<NumberSequence> numberseqs) { 
     1308            this.numberseqs = numberseqs; 
     1309        } 
     1310 
     1311        /** 
     1312         * Update substitution matrix. 
     1313         */ 
     1314        private void updateSubstitutionMatrix() { 
     1315            submat.update(getNewTasks()); 
     1316            resetNewlyCreatedTasks(); 
     1317        } 
     1318 
     1319    } 
    13091320 
    13101321} 
Note: See TracChangeset for help on using the changeset viewer.