Ignore:
Timestamp:
09/05/14 19:33:12 (10 years ago)
Author:
rkrimmel
Message:

Used Eclipse code cleanup

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

Legend:

Unmodified
Added
Removed

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

    r1593 r1733  
    55public class Alignment { 
    66        ArrayList<NumberSequence> alingment; 
    7          
    8          
     7 
    98} 

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

    r1649 r1733  
    66 
    77public interface AlignmentAlgorithm { 
    8          
     8 
     9        void align(NumberSequence input1, NumberSequence input2, 
     10                        SubstitutionMatrix submat, float threshold); 
     11 
     12        public abstract ArrayList<NumberSequence> getAlignment(); 
     13 
    914        /** 
    1015         * Get the alignment score between the two input strings. 
    … …  
    1217        public abstract double getAlignmentScore(); 
    1318 
    14         public abstract ArrayList<NumberSequence> getAlignment(); 
     19        public abstract ArrayList<Match> getMatches(); 
     20 
     21        public double getMaxScore(); 
     22 
     23        public abstract void printAlignment(); 
    1524 
    1625        public abstract void printDPMatrix(); 
    1726 
    18         public abstract void printAlignment(); 
    19  
    20         public abstract ArrayList<Match> getMatches(); 
    21          
    22         public double getMaxScore(); 
    23  
    24         void align(NumberSequence input1, NumberSequence input2, 
    25                         SubstitutionMatrix submat, float threshold); 
    26  
    2727} 

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

    r1616 r1733  
    11package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; 
    22 
     3public class AlignmentAlgorithmFactory { 
    34 
    4 public class AlignmentAlgorithmFactory { 
    5          
    6         public static void setDefaultAlgorithm(String algorithmname) { 
    7                 //TODO: check for valid algorihm class names here 
    8                 algorithmclass = algorithmname; 
    9         } 
    10          
    11         private static String algorithmclass = "de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated"; 
    12          
    13          
    14          
    155        public static AlignmentAlgorithm create() { 
    166                Class<?> newclass; 
    177                Object object = null; 
    188                try { 
    19                          newclass = Class.forName(algorithmclass); 
    20                          object = newclass.newInstance(); 
    21                          
    22                 } catch (ClassNotFoundException | SecurityException | InstantiationException | IllegalAccessException | IllegalArgumentException e) { 
     9                        newclass = Class.forName(algorithmclass); 
     10                        object = newclass.newInstance(); 
     11 
     12                } catch (ClassNotFoundException | SecurityException 
     13                                | InstantiationException | IllegalAccessException 
     14                                | IllegalArgumentException e) { 
    2315                        e.printStackTrace(); 
    2416                } 
    2517                return (AlignmentAlgorithm) object; 
    2618        } 
     19 
     20        public static void setDefaultAlgorithm(String algorithmname) { 
     21                // TODO: check for valid algorihm class names here 
     22                algorithmclass = algorithmname; 
     23        } 
     24 
     25        private static String algorithmclass = "de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated"; 
    2726} 

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

    r1553 r1733  
    77import de.ugoe.cs.autoquest.eventcore.guimodel.IGUIElement; 
    88 
     9public class AlignmentHelpers extends GUIModel { 
    910 
    10 public class AlignmentHelpers extends GUIModel { 
    11          
     11        public static int distanceBetween(IGUIElement first, IGUIElement second) { 
    1212 
    13          
    14         /** 
    15          *  
    16          */ 
    17         private static final long serialVersionUID = -2593092958275693133L; 
     13                int hopcount1 = 0; 
     14                int hopcount2 = 0; 
     15                final List<IGUIElement> tmp = new ArrayList<IGUIElement>(); 
     16                tmp.add(first); 
     17                tmp.add(second); 
     18                final IGUIElement commonDenominator = getCommonDenominator(tmp); 
     19 
     20                while (!(first.equals(commonDenominator))) { 
     21                        first = first.getParent(); 
     22                        hopcount1++; 
     23                } 
     24 
     25                while (!(second.equals(commonDenominator))) { 
     26                        second = second.getParent(); 
     27                        hopcount2++; 
     28                } 
     29 
     30                return hopcount1 + hopcount2; 
     31        } 
    1832 
    1933        /** 
    … …  
    2438         * </p> 
    2539         */ 
    26         private static IGUIElement getCommonDenominator(List<IGUIElement> guiElements) { 
     40        private static IGUIElement getCommonDenominator( 
     41                        List<IGUIElement> guiElements) { 
    2742                IGUIElement commonDenominator = null; 
    2843 
    2944                if (guiElements.size() > 0) { 
    30                         List<IGUIElement> commonDenominatorPath = new ArrayList<IGUIElement>(); 
     45                        final List<IGUIElement> commonDenominatorPath = new ArrayList<IGUIElement>(); 
    3146 
    3247                        // create a reference list using the first GUI element 
    … …  
    4964                        // well as it subsequent 
    5065                        // siblings 
    51                         List<IGUIElement> currentPath = new ArrayList<IGUIElement>(); 
     66                        final List<IGUIElement> currentPath = new ArrayList<IGUIElement>(); 
    5267                        for (int i = 1; i < guiElements.size(); i++) { 
    5368                                currentPath.clear(); 
    … …  
    5570                                while (guiElement != null) { 
    5671                                        // if (guiElementMatchesConsideredTypes(guiElement)) { 
    57                                     currentPath.add(0, guiElement); 
     72                                        currentPath.add(0, guiElement); 
    5873                                        // } 
    5974                                        guiElement = guiElement.getParent(); 
    … …  
    8499        } 
    85100 
    86         public static int distanceBetween(IGUIElement first, IGUIElement second) { 
    87  
    88                 int hopcount1 = 0; 
    89                 int hopcount2 = 0; 
    90                 List<IGUIElement> tmp = new ArrayList<IGUIElement>(); 
    91                 tmp.add(first); 
    92                 tmp.add(second); 
    93                 IGUIElement commonDenominator = getCommonDenominator(tmp); 
    94                  
    95                 while(!(first.equals(commonDenominator))) { 
    96                         first = first.getParent(); 
    97                         hopcount1++; 
    98                 } 
    99                  
    100                 while(!(second.equals(commonDenominator))) { 
    101                         second = second.getParent(); 
    102                         hopcount2++; 
    103                 } 
    104  
    105                 return hopcount1 + hopcount2; 
    106         } 
     101        /** 
     102         *  
     103         */ 
     104        private static final long serialVersionUID = -2593092958275693133L; 
    107105 
    108106} 

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

    r1578 r1733  
    22 
    33public class Constants { 
    4          
     4 
    55        public static final int GAP_SYMBOL = -1; 
    66        public static final int UNMATCHED_SYMBOL = -2; 

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

    r1717 r1733  
    55import java.util.LinkedList; 
    66 
    7  
    8  
    9 public class Match implements Serializable{ 
     7public class Match implements Serializable { 
    108        /** 
    119         *  
    … …  
    1311        private static final long serialVersionUID = -3206992723755714741L; 
    1412 
    15         private ArrayList<NumberSequence> matchseqs; 
     13        private final ArrayList<NumberSequence> matchseqs; 
    1614 
    1715        private LinkedList<MatchOccurence> occurences; 
    … …  
    2422        } 
    2523 
    26         public NumberSequence getFirstSequence() { 
    27                 return matchseqs.get(0); 
    28         } 
    29  
    30         public NumberSequence getSecondSequence() { 
    31                 return matchseqs.get(1); 
    32         } 
    33  
    34         public void setFirstSequence(NumberSequence seq) { 
    35                 matchseqs.set(0, seq); 
    36         } 
    37  
    38         public void setSecondSequence(NumberSequence seq) { 
    39                 matchseqs.set(1, seq); 
    40         } 
    41  
    4224        public void addOccurence(MatchOccurence occurence) { 
    4325                occurences.add(occurence); 
    4426        } 
    4527 
    46         public int occurenceCount() { 
    47                 return occurences.size(); 
    48         } 
    49          
    50         public int size() { 
    51                 //Both sequences should be equally long 
    52                 return matchseqs.get(0).size(); 
     28        public void addOccurencesOf(Match m) { 
     29                occurences.addAll(m.getOccurences()); 
    5330        } 
    5431 
    … …  
    6340        } 
    6441 
     42        public NumberSequence getFirstSequence() { 
     43                return matchseqs.get(0); 
     44        } 
     45 
    6546        public LinkedList<MatchOccurence> getOccurences() { 
    6647                return occurences; 
     48        } 
     49 
     50        public NumberSequence getSecondSequence() { 
     51                return matchseqs.get(1); 
     52        } 
     53 
     54        public int occurenceCount() { 
     55                return occurences.size(); 
     56        } 
     57 
     58        public void setFirstSequence(NumberSequence seq) { 
     59                matchseqs.set(0, seq); 
    6760        } 
    6861 
    … …  
    7164        } 
    7265 
    73          
    74         public void addOccurencesOf(Match m) { 
    75                 occurences.addAll(m.getOccurences()); 
     66        public void setSecondSequence(NumberSequence seq) { 
     67                matchseqs.set(1, seq); 
    7668        } 
    77          
    78          
    79     
     69 
     70        public int size() { 
     71                // Both sequences should be equally long 
     72                return matchseqs.get(0).size(); 
     73        } 
    8074 
    8175} 

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

    r1717 r1733  
    33import java.io.Serializable; 
    44 
    5 public class MatchOccurence implements Serializable{ 
     5public class MatchOccurence implements Serializable { 
    66        /** 
    77         *  
    … …  
    1111        private int endindex; 
    1212        private int sequenceId; 
    13          
     13 
    1414        public MatchOccurence(int startindex, int endindex, int sequenceId) { 
    1515                this.startindex = startindex; 
    … …  
    1717                this.sequenceId = sequenceId; 
    1818        } 
    19          
     19 
    2020        public int getEndindex() { 
    2121                return endindex; 
     22        } 
     23 
     24        public int getSequenceId() { 
     25                return sequenceId; 
     26        } 
     27 
     28        public int getStartindex() { 
     29                return startindex; 
    2230        } 
    2331 
    … …  
    2634        } 
    2735 
    28         public int getStartindex() { 
    29                 return startindex; 
     36        public void setSequenceId(int sequenceId) { 
     37                this.sequenceId = sequenceId; 
    3038        } 
     39 
    3140        public void setStartindex(int startindex) { 
    3241                this.startindex = startindex; 
    3342        } 
    34         public int getSequenceId() { 
    35                 return sequenceId; 
    36         } 
    37  
    38         public void setSequenceId(int sequenceId) { 
    39                 this.sequenceId = sequenceId; 
    40         } 
    4143} 

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

    r1568 r1733  
    66        private int xvalue; 
    77        private int yvalue; 
    8          
    9         public MatrixEntry(float score, MatrixEntry previous)   { 
     8 
     9        public MatrixEntry() { 
     10        } 
     11 
     12        public MatrixEntry(float score, MatrixEntry previous) { 
    1013                this.score = score; 
    1114                this.previous = previous; 
    1215        } 
    13          
    14         public MatrixEntry() { 
     16 
     17        public MatrixEntry getPrevious() { 
     18                return previous; 
    1519        } 
    1620 
    1721        public double getScore() { 
    1822                return score; 
    19         } 
    20         public void setScore(double score) { 
    21                 this.score = score; 
    22         } 
    23         public MatrixEntry getPrevious() { 
    24                 return previous; 
    25         } 
    26         public void setPrevious(MatrixEntry previous) { 
    27                 this.previous = previous; 
    2823        } 
    2924 
    … …  
    3227        } 
    3328 
     29        public int getYvalue() { 
     30                return yvalue; 
     31        } 
     32 
     33        public void setPrevious(MatrixEntry previous) { 
     34                this.previous = previous; 
     35        } 
     36 
     37        public void setScore(double score) { 
     38                this.score = score; 
     39        } 
     40 
    3441        public void setXvalue(int xvalue) { 
    3542                this.xvalue = xvalue; 
    36         } 
    37  
    38         public int getYvalue() { 
    39                 return yvalue; 
    4043        } 
    4144 

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

    r1620 r1733  
    88import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Constants; 
    99 
    10  
    1110public class NeedlemanWunsch implements AlignmentAlgorithm { 
    1211 
    … …  
    3938        private SubstitutionMatrix submat; 
    4039 
     40        @Override 
     41        public void align(NumberSequence input1, NumberSequence input2, 
     42                        SubstitutionMatrix submat, float threshold) { 
     43                this.input1 = input1.getSequence(); 
     44                this.input2 = input2.getSequence(); 
     45                length1 = input1.size(); 
     46                length2 = input2.size(); 
     47                this.submat = submat; 
     48 
     49                // System.out.println("Starting SmithWaterman algorithm with a " 
     50                // + submat.getClass() + " Substitution Matrix: " + 
     51                // submat.getClass().getCanonicalName()); 
     52 
     53                matrix = new MatrixEntry[length1 + 1][length2 + 1]; 
     54                alignment = new ArrayList<NumberSequence>(); 
     55 
     56                for (int i = 0; i < (length1 + 1); i++) { 
     57                        for (int j = 0; j < (length2 + 1); j++) { 
     58                                matrix[i][j] = new MatrixEntry(); 
     59                        } 
     60                } 
     61 
     62                buildMatrix(); 
     63                traceback(); 
     64 
     65        } 
     66 
     67        /** 
     68         * Build the score matrix using dynamic programming. 
     69         */ 
     70        private void buildMatrix() { 
     71                if (submat.getGapPenalty() >= 0) { 
     72                        throw new Error("Indel score must be negative"); 
     73                } 
     74 
     75                // it's a gap 
     76                matrix[0][0].setScore(0); 
     77                matrix[0][0].setPrevious(null); // starting point 
     78 
     79                // the first column 
     80                for (int j = 1; j <= length2; j++) { 
     81                        matrix[0][j].setScore(j * submat.getGapPenalty()); 
     82                        matrix[0][j].setPrevious(matrix[0][j - 1]); 
     83                        matrix[0][j].setYvalue(input2[j - 1]); 
     84                        matrix[0][j].setXvalue(Constants.GAP_SYMBOL); 
     85                } 
     86                // the first row 
     87 
     88                for (int j = 1; j <= length1; j++) { 
     89                        matrix[j][0].setScore(j * submat.getGapPenalty()); 
     90                        matrix[j][0].setPrevious(matrix[j - 1][0]); 
     91                        matrix[j][0].setXvalue(input1[j - 1]); 
     92                        matrix[j][0].setYvalue(Constants.GAP_SYMBOL); 
     93                } 
     94 
     95                for (int i = 1; i <= length1; i++) { 
     96 
     97                        for (int j = 1; j <= length2; j++) { 
     98                                final double diagScore = matrix[i - 1][j - 1].getScore() 
     99                                                + similarity(i, j); 
     100                                final double upScore = matrix[i][j - 1].getScore() 
     101                                                + submat.getGapPenalty(); 
     102                                final double leftScore = matrix[i - 1][j].getScore() 
     103                                                + submat.getGapPenalty(); 
     104 
     105                                matrix[i][j].setScore(Math.max(diagScore, 
     106                                                Math.max(upScore, leftScore))); 
     107 
     108                                // find the directions that give the maximum scores. 
     109                                // TODO: Multiple directions are ignored, we choose the first 
     110                                // maximum score 
     111                                // True if we had a match 
     112                                if (diagScore == matrix[i][j].getScore()) { 
     113                                        matrix[i][j].setPrevious(matrix[i - 1][j - 1]); 
     114                                        matrix[i][j].setXvalue(input1[i - 1]); 
     115                                        matrix[i][j].setYvalue(input2[j - 1]); 
     116                                } 
     117                                // true if we took an event from sequence x and not from y 
     118                                if (leftScore == matrix[i][j].getScore()) { 
     119                                        matrix[i][j].setXvalue(input1[i - 1]); 
     120                                        matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
     121                                        matrix[i][j].setPrevious(matrix[i - 1][j]); 
     122                                } 
     123                                // true if we took an event from sequence y and not from x 
     124                                if (upScore == matrix[i][j].getScore()) { 
     125                                        matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
     126                                        matrix[i][j].setYvalue(input2[j - 1]); 
     127                                        matrix[i][j].setPrevious(matrix[i][j - 1]); 
     128                                } 
     129                        } 
     130                } 
     131        } 
     132 
     133        /* 
     134         * (non-Javadoc) 
     135         *  
     136         * @see 
     137         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     138         * #getAlignment() 
     139         */ 
     140        @Override 
     141        public ArrayList<NumberSequence> getAlignment() { 
     142                return alignment; 
     143        } 
     144 
     145        /* 
     146         * (non-Javadoc) 
     147         *  
     148         * @see 
     149         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     150         * #getAlignmentScore() 
     151         */ 
     152        @Override 
     153        public double getAlignmentScore() { 
     154                return getMaxScore(); 
     155        } 
     156 
     157        @Override 
     158        public ArrayList<Match> getMatches() { 
     159                // TODO Auto-generated method stub 
     160                return null; 
     161        } 
     162 
     163        /** 
     164         * Get the maximum value in the score matrix. 
     165         */ 
     166        @Override 
     167        public double getMaxScore() { 
     168                double maxScore = 0; 
     169 
     170                // skip the first row and column 
     171                for (int i = 1; i <= length1; i++) { 
     172                        for (int j = 1; j <= length2; j++) { 
     173                                if (matrix[i][j].getScore() > maxScore) { 
     174                                        maxScore = matrix[i][j].getScore(); 
     175                                } 
     176                        } 
     177                } 
     178 
     179                return maxScore; 
     180        } 
     181 
     182        @Override 
     183        public void printAlignment() { 
     184                final int[] tmp1 = alignment.get(0).getSequence(); 
     185                final int[] tmp2 = alignment.get(1).getSequence(); 
     186                for (int i = 0; i < tmp1.length; i++) { 
     187                        if (tmp1[i] == Constants.GAP_SYMBOL) { 
     188                                System.out.print("  ___"); 
     189                        } else if (tmp1[i] == Constants.UNMATCHED_SYMBOL) { 
     190                                System.out.print("  ..."); 
     191                        } else { 
     192                                System.out.format("%5d", tmp1[i]); 
     193                        } 
     194 
     195                } 
     196                System.out.println(); 
     197                for (int i = 0; i < tmp2.length; i++) { 
     198                        if (tmp2[i] == Constants.GAP_SYMBOL) { 
     199                                System.out.print("  ___"); 
     200                        } else if (tmp2[i] == Constants.UNMATCHED_SYMBOL) { 
     201                                System.out.print("  ..."); 
     202                        } else { 
     203                                System.out.format("%5d", tmp2[i]); 
     204                        } 
     205 
     206                } 
     207                System.out.println(); 
     208 
     209        } 
     210 
     211        /** 
     212         * print the dynmaic programming matrix 
     213         */ 
     214        @Override 
     215        public void printDPMatrix() { 
     216                System.out.print("          "); 
     217                for (int i = 1; i <= length1; i++) { 
     218                        System.out.format("%5d", input1[i - 1]); 
     219                } 
     220                System.out.println(); 
     221                for (int j = 0; j <= length2; j++) { 
     222                        if (j > 0) { 
     223                                System.out.format("%5d ", input2[j - 1]); 
     224                        } else { 
     225                                System.out.print("      "); 
     226                        } 
     227                        for (int i = 0; i <= length1; i++) { 
     228                                System.out.format("%4.1f ", matrix[i][j].getScore()); 
     229                        } 
     230                        System.out.println(); 
     231                } 
     232        } 
     233 
     234        public void setAlignment(ArrayList<NumberSequence> alignment) { 
     235                this.alignment = alignment; 
     236        } 
    41237 
    42238        /** 
    … …  
    54250        } 
    55251 
    56         /** 
    57          * Build the score matrix using dynamic programming. 
    58          */ 
    59         private void buildMatrix() { 
    60                 if (submat.getGapPenalty() >= 0) { 
    61                         throw new Error("Indel score must be negative"); 
    62                 } 
    63  
    64                 // it's a gap 
    65                 matrix[0][0].setScore(0); 
    66                 matrix[0][0].setPrevious(null); // starting point 
    67  
    68                 // the first column 
    69                 for (int j = 1; j <= length2; j++) { 
    70                         matrix[0][j].setScore(j*submat.getGapPenalty()); 
    71                         matrix[0][j].setPrevious(matrix[0][j - 1]); 
    72                         matrix[0][j].setYvalue(input2[j-1]); 
    73                         matrix[0][j].setXvalue(Constants.GAP_SYMBOL); 
    74                 } 
    75                 // the first row 
    76  
    77                 for (int j = 1; j <= length1; j++) { 
    78                         matrix[j][0].setScore(j*submat.getGapPenalty()); 
    79                         matrix[j][0].setPrevious(matrix[j - 1][0]); 
    80                         matrix[j][0].setXvalue(input1[j-1]); 
    81                         matrix[j][0].setYvalue(Constants.GAP_SYMBOL); 
    82                 } 
    83  
    84                 for (int i = 1; i <= length1; i++) { 
    85  
    86                         for (int j = 1; j <= length2; j++) { 
    87                                 double diagScore = matrix[i - 1][j - 1].getScore() 
    88                                                 + similarity(i, j); 
    89                                 double upScore = matrix[i][j - 1].getScore() 
    90                                                 + submat.getGapPenalty(); 
    91                                 double leftScore = matrix[i - 1][j].getScore() 
    92                                                 + submat.getGapPenalty(); 
    93  
    94                                 matrix[i][j].setScore(Math.max(diagScore, 
    95                                                 Math.max(upScore, leftScore))); 
    96  
    97                                 // find the directions that give the maximum scores. 
    98                                 // TODO: Multiple directions are ignored, we choose the first 
    99                                 // maximum score 
    100                                 // True if we had a match 
    101                                 if (diagScore == matrix[i][j].getScore()) { 
    102                                         matrix[i][j].setPrevious(matrix[i - 1][j - 1]); 
    103                                         matrix[i][j].setXvalue(input1[i - 1]); 
    104                                         matrix[i][j].setYvalue(input2[j - 1]); 
    105                                 } 
    106                                 // true if we took an event from sequence x and not from y 
    107                                 if (leftScore == matrix[i][j].getScore()) { 
    108                                         matrix[i][j].setXvalue(input1[i - 1]); 
    109                                         matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
    110                                         matrix[i][j].setPrevious(matrix[i - 1][j]); 
    111                                 } 
    112                                 // true if we took an event from sequence y and not from x 
    113                                 if (upScore == matrix[i][j].getScore()) { 
    114                                         matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
    115                                         matrix[i][j].setYvalue(input2[j - 1]); 
    116                                         matrix[i][j].setPrevious(matrix[i][j - 1]); 
    117                                 } 
    118                         } 
    119                 } 
    120         } 
    121  
    122         /** 
    123          * Get the maximum value in the score matrix. 
    124          */ 
    125         public double getMaxScore() { 
    126                 double maxScore = 0; 
    127  
    128                 // skip the first row and column 
    129                 for (int i = 1; i <= length1; i++) { 
    130                         for (int j = 1; j <= length2; j++) { 
    131                                 if (matrix[i][j].getScore() > maxScore) { 
    132                                         maxScore = matrix[i][j].getScore(); 
    133                                 } 
    134                         } 
    135                 } 
    136  
    137                 return maxScore; 
    138         } 
    139  
    140         /* 
    141          * (non-Javadoc) 
    142          *  
    143          * @see 
    144          * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
    145          * #getAlignmentScore() 
    146          */ 
    147         @Override 
    148         public double getAlignmentScore() { 
    149                 return getMaxScore(); 
    150         } 
    151  
    152252        public void traceback() { 
    153253                MatrixEntry tmp = matrix[length1][length2]; 
    154                 LinkedList<Integer> aligned1 = new LinkedList<Integer>(); 
    155                 LinkedList<Integer> aligned2 = new LinkedList<Integer>(); 
     254                final LinkedList<Integer> aligned1 = new LinkedList<Integer>(); 
     255                final LinkedList<Integer> aligned2 = new LinkedList<Integer>(); 
    156256                while (tmp.getPrevious() != null) { 
    157                          
     257 
    158258                        aligned1.add(new Integer(tmp.getXvalue())); 
    159259                        aligned2.add(new Integer(tmp.getYvalue())); 
    160260 
    161261                        tmp = tmp.getPrevious(); 
    162                 }  
    163                  
     262                } 
     263 
    164264                // reverse order of the alignment 
    165                 int reversed1[] = new int[aligned1.size()]; 
    166                 int reversed2[] = new int[aligned2.size()]; 
     265                final int reversed1[] = new int[aligned1.size()]; 
     266                final int reversed2[] = new int[aligned2.size()]; 
    167267 
    168268                int count = 0; 
    169                 for (Iterator<Integer> it = aligned1.iterator(); it.hasNext();) { 
     269                for (final Iterator<Integer> it = aligned1.iterator(); it.hasNext();) { 
    170270                        count++; 
    171271                        reversed1[reversed1.length - count] = it.next(); 
    172                          
     272 
    173273                } 
    174274                count = 0; 
    175                 for (Iterator<Integer> it = aligned2.iterator(); it.hasNext();) { 
     275                for (final Iterator<Integer> it = aligned2.iterator(); it.hasNext();) { 
    176276                        count++; 
    177277                        reversed2[reversed2.length - count] = it.next(); 
    178278                } 
    179279 
    180                 NumberSequence ns1 = new NumberSequence(reversed1.length); 
    181                 NumberSequence ns2 = new NumberSequence(reversed2.length); 
     280                final NumberSequence ns1 = new NumberSequence(reversed1.length); 
     281                final NumberSequence ns2 = new NumberSequence(reversed2.length); 
    182282                ns1.setSequence(reversed1); 
    183283                ns2.setSequence(reversed2); 
    … …  
    187287        } 
    188288 
    189          
    190         /** 
    191          * print the dynmaic programming matrix 
    192          */ 
    193         public void printDPMatrix() { 
    194                 System.out.print("          "); 
    195                 for (int i = 1; i <= length1; i++) 
    196                         System.out.format("%5d", input1[i - 1]); 
    197                 System.out.println(); 
    198                 for (int j = 0; j <= length2; j++) { 
    199                         if (j > 0) 
    200                                 System.out.format("%5d ", input2[j - 1]); 
    201                         else { 
    202                                 System.out.print("      "); 
    203                         } 
    204                         for (int i = 0; i <= length1; i++) { 
    205                                         System.out.format("%4.1f ", matrix[i][j].getScore()); 
    206                         } 
    207                         System.out.println(); 
    208                 } 
    209         } 
    210          
    211         public void printAlignment() { 
    212                 int[] tmp1 = alignment.get(0).getSequence(); 
    213                 int[] tmp2 = alignment.get(1).getSequence(); 
    214                 for (int i=0; i< tmp1.length;i++) { 
    215                         if(tmp1[i] == Constants.GAP_SYMBOL) { 
    216                                 System.out.print("  ___"); 
    217                         } 
    218                         else if(tmp1[i] == Constants.UNMATCHED_SYMBOL) { 
    219                                 System.out.print("  ..."); 
    220                         } 
    221                         else { 
    222                                 System.out.format("%5d", tmp1[i]); 
    223                         } 
    224                          
    225                 } 
    226                 System.out.println(); 
    227                 for (int i=0; i< tmp2.length;i++) { 
    228                         if(tmp2[i] == Constants.GAP_SYMBOL) { 
    229                                 System.out.print("  ___"); 
    230                         } 
    231                         else if(tmp2[i] == Constants.UNMATCHED_SYMBOL) { 
    232                                 System.out.print("  ..."); 
    233                         } 
    234                         else { 
    235                                 System.out.format("%5d", tmp2[i]); 
    236                         } 
    237                          
    238                 } 
    239                 System.out.println(); 
    240                  
    241                  
    242          
    243         } 
    244  
    245         /* 
    246          * (non-Javadoc) 
    247          *  
    248          * @see 
    249          * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
    250          * #getAlignment() 
    251          */ 
    252         @Override 
    253         public ArrayList<NumberSequence> getAlignment() { 
    254                 return alignment; 
    255         } 
    256  
    257         public void setAlignment(ArrayList<NumberSequence> alignment) { 
    258                 this.alignment = alignment; 
    259         } 
    260  
    261         @Override 
    262         public ArrayList<Match> getMatches() { 
    263                 // TODO Auto-generated method stub 
    264                 return null; 
    265         } 
    266  
    267         @Override 
    268         public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    269                         float threshold) { 
    270                 this.input1 = input1.getSequence(); 
    271                 this.input2 = input2.getSequence(); 
    272                 length1 = input1.size(); 
    273                 length2 = input2.size(); 
    274                 this.submat = submat; 
    275  
    276                 // System.out.println("Starting SmithWaterman algorithm with a " 
    277                 // + submat.getClass() + " Substitution Matrix: " + 
    278                 // submat.getClass().getCanonicalName()); 
    279  
    280                 matrix = new MatrixEntry[length1 + 1][length2 + 1]; 
    281                 alignment = new ArrayList<NumberSequence>(); 
    282  
    283                 for (int i = 0; i < length1+1; i++) { 
    284                         for (int j = 0; j < length2+1; j++) { 
    285                                 matrix[i][j] = new MatrixEntry(); 
    286                         } 
    287                 } 
    288  
    289                 buildMatrix(); 
    290                 traceback(); 
    291                  
    292         } 
    293  
    294  
    295  
    296289} 

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

    r1717 r1733  
    55import java.util.Random; 
    66 
    7 public class NumberSequence implements Serializable{ 
     7public class NumberSequence implements Serializable { 
    88        /** 
    99         *  
    … …  
    1818        } 
    1919 
    20         public int[] getSequence() { 
    21                 return sequence; 
    22         } 
     20        // Searching occurrences of pattern 
     21        public LinkedList<Integer> containsPattern(Match pattern) { 
     22                final LinkedList<Integer> result = new LinkedList<Integer>(); 
     23                int i = 0; 
     24                final int[] pat1 = pattern.getFirstSequence().getSequence(); 
     25                final int[] pat2 = pattern.getSecondSequence().getSequence(); 
    2326 
    24         public void setSequence(int[] sequence) { 
    25                 this.sequence = sequence; 
    26         } 
    27  
    28         public void printSequence() { 
    29                 for (int i = 0; i < sequence.length; i++) { 
    30                         System.out.format("%5d", sequence[i]); 
    31                 } 
    32                 System.out.println(); 
    33         } 
    34  
    35         public NumberSequence shuffle() { 
    36                 NumberSequence result = new NumberSequence(sequence.length); 
    37                 result.setId(getId()); 
    38                 result.setSequence(this.sequence); 
    39                 Random rgen = new Random(); 
    40  
    41                 for (int i = 0; i < result.sequence.length; i++) { 
    42                         int randomPosition = rgen.nextInt(result.sequence.length); 
    43                         int temp = result.sequence[i]; 
    44                         result.sequence[i] = result.sequence[randomPosition]; 
    45                         result.sequence[randomPosition] = temp; 
    46                 } 
    47                 return result; 
    48  
    49         } 
    50  
    51         //Recursive check if sequence contains pattern at position i 
    52         private boolean matches(int i,  
    53                                 int[] p1,  
    54                                 int[] p2 , 
    55                                 int ip1, 
    56                                 int ip2, 
    57                                 boolean jumped1, //True if there was a gap in Sequence 1 of the pattern 
    58                                 boolean jumped2, //True if there was a gap in Sequence 2 of the pattern 
    59                                 boolean hadSelection, //True if the last match was a selection  
    60                                 boolean matchseq1, 
    61                                 boolean matchseq2) { 
    62                  
    63                 if(p1.length==ip1) { 
    64                         return true; 
    65                 } 
    66                 if(p2.length==ip2) { 
    67                         return true; 
    68                 } 
    69                 if(i==sequence.length) { 
    70                         return false; 
    71                 } 
    72  
    73                 boolean foundselection=(!(p1[ip1] == p2[ip2])&&!(p1[ip1]==-1||p2[ip2]==-1)); 
    74                 boolean matchInFirstPattern = (p1[ip1]==sequence[i]); 
    75                 boolean matchInSecondPattern = (p2[ip2]==sequence[i]); 
    76                  
    77                 if(foundselection && hadSelection) { 
    78                         if((matchInFirstPattern && matchseq1) || (matchInSecondPattern && matchseq2)){ 
    79                                 if(jumped1) { 
    80                                         return matches(i+1,p1,p2,ip1+1,ip2+2,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    81                                 } 
    82                                 if(jumped2) { 
    83                                         return matches(i+1,p1,p2,ip1+2,ip2+1,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    84                                 } 
    85                                 return matches(i+1,p1,p2,ip1+1,ip2+1,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    86                         }        
    87                         else { 
    88                                 return false; 
    89                         } 
    90                 } 
    91  
    92                 if((matchInFirstPattern||matchInSecondPattern) && jumped1) { 
    93                         return matches(i+1,p1,p2,ip1+1,ip2+2,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    94                 } 
    95                 if((matchInFirstPattern||matchInSecondPattern) && jumped2) { 
    96                         return matches(i+1,p1,p2,ip1+2,ip2+1,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    97                 } 
    98                 if(matchInFirstPattern||matchInSecondPattern) { 
    99                         return matches(i+1,p1,p2,ip1+1,ip2+1,false,false,foundselection,matchInFirstPattern,matchInSecondPattern); 
    100                 } 
    101                 if(p1[ip1]==-1) { 
    102                         return matches(i,p1,p2,ip1+1,ip2,true,false,false,false,false); 
    103                 } 
    104                 if(p2[ip2]==-1) { 
    105                         return matches(i,p1,p2,ip1,ip2+1,false,true,false,false,false); 
    106                 } 
    107          
    108                 return false; 
    109         } 
    110          
    111         //Searching occurrences of pattern 
    112         public LinkedList<Integer> containsPattern(Match pattern) { 
    113                 LinkedList<Integer> result = new LinkedList<Integer>(); 
    114                 int i = 0; 
    115                 int[] pat1 = pattern.getFirstSequence().getSequence(); 
    116                 int[] pat2 = pattern.getSecondSequence().getSequence(); 
    117  
    118                 while (i < sequence.length ) { 
    119                         if(matches(i,pat1,pat2,0,0,false,false,false,false,false)) { 
     27                while (i < sequence.length) { 
     28                        if (matches(i, pat1, pat2, 0, 0, false, false, false, false, false)) { 
    12029                                result.add(i); 
    12130                        } 
    … …  
    12332                } 
    12433                return result; 
     34        } 
     35 
     36        public boolean equals(NumberSequence n) { 
     37                final int[] seq = n.getSequence(); 
     38                if (n.size() != this.size()) { 
     39                        return false; 
     40                } 
     41                for (int i = 0; i < n.size(); i++) { 
     42                        if (seq[i] != this.sequence[i]) { 
     43                                return false; 
     44                        } 
     45                } 
     46                return true; 
    12547        } 
    12648 
    … …  
    13658        } 
    13759 
    138         public int size() { 
    139                 return sequence.length; 
     60        public int getId() { 
     61                return id; 
    14062        } 
    14163 
    142         public int getId() { 
    143                 return id; 
     64        public int[] getSequence() { 
     65                return sequence; 
     66        } 
     67 
     68        // Recursive check if sequence contains pattern at position i 
     69        private boolean matches(int i, int[] p1, int[] p2, int ip1, int ip2, 
     70                        boolean jumped1, // True if there was a gap in Sequence 1 of the 
     71                                                                // pattern 
     72                        boolean jumped2, // True if there was a gap in Sequence 2 of the 
     73                                                                // pattern 
     74                        boolean hadSelection, // True if the last match was a selection 
     75                        boolean matchseq1, boolean matchseq2) { 
     76 
     77                if (p1.length == ip1) { 
     78                        return true; 
     79                } 
     80                if (p2.length == ip2) { 
     81                        return true; 
     82                } 
     83                if (i == sequence.length) { 
     84                        return false; 
     85                } 
     86 
     87                final boolean foundselection = (!(p1[ip1] == p2[ip2]) && !((p1[ip1] == -1) || (p2[ip2] == -1))); 
     88                final boolean matchInFirstPattern = (p1[ip1] == sequence[i]); 
     89                final boolean matchInSecondPattern = (p2[ip2] == sequence[i]); 
     90 
     91                if (foundselection && hadSelection) { 
     92                        if ((matchInFirstPattern && matchseq1) 
     93                                        || (matchInSecondPattern && matchseq2)) { 
     94                                if (jumped1) { 
     95                                        return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, 
     96                                                        false, foundselection, matchInFirstPattern, 
     97                                                        matchInSecondPattern); 
     98                                } 
     99                                if (jumped2) { 
     100                                        return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, 
     101                                                        false, foundselection, matchInFirstPattern, 
     102                                                        matchInSecondPattern); 
     103                                } 
     104                                return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, 
     105                                                foundselection, matchInFirstPattern, 
     106                                                matchInSecondPattern); 
     107                        } else { 
     108                                return false; 
     109                        } 
     110                } 
     111 
     112                if ((matchInFirstPattern || matchInSecondPattern) && jumped1) { 
     113                        return matches(i + 1, p1, p2, ip1 + 1, ip2 + 2, false, false, 
     114                                        foundselection, matchInFirstPattern, matchInSecondPattern); 
     115                } 
     116                if ((matchInFirstPattern || matchInSecondPattern) && jumped2) { 
     117                        return matches(i + 1, p1, p2, ip1 + 2, ip2 + 1, false, false, 
     118                                        foundselection, matchInFirstPattern, matchInSecondPattern); 
     119                } 
     120                if (matchInFirstPattern || matchInSecondPattern) { 
     121                        return matches(i + 1, p1, p2, ip1 + 1, ip2 + 1, false, false, 
     122                                        foundselection, matchInFirstPattern, matchInSecondPattern); 
     123                } 
     124                if (p1[ip1] == -1) { 
     125                        return matches(i, p1, p2, ip1 + 1, ip2, true, false, false, false, 
     126                                        false); 
     127                } 
     128                if (p2[ip2] == -1) { 
     129                        return matches(i, p1, p2, ip1, ip2 + 1, false, true, false, false, 
     130                                        false); 
     131                } 
     132 
     133                return false; 
     134        } 
     135 
     136        public void printSequence() { 
     137                for (int i = 0; i < sequence.length; i++) { 
     138                        System.out.format("%5d", sequence[i]); 
     139                } 
     140                System.out.println(); 
    144141        } 
    145142 
    … …  
    148145        } 
    149146 
    150         public boolean equals(NumberSequence n) { 
    151                 int[] seq = n.getSequence(); 
    152                 if (n.size() != this.size()) { 
    153                         return false; 
     147        public void setSequence(int[] sequence) { 
     148                this.sequence = sequence; 
     149        } 
     150 
     151        public NumberSequence shuffle() { 
     152                final NumberSequence result = new NumberSequence(sequence.length); 
     153                result.setId(getId()); 
     154                result.setSequence(this.sequence); 
     155                final Random rgen = new Random(); 
     156 
     157                for (int i = 0; i < result.sequence.length; i++) { 
     158                        final int randomPosition = rgen.nextInt(result.sequence.length); 
     159                        final int temp = result.sequence[i]; 
     160                        result.sequence[i] = result.sequence[randomPosition]; 
     161                        result.sequence[randomPosition] = temp; 
    154162                } 
    155                 for (int i = 0; i < n.size(); i++) { 
    156                         if (seq[i] != this.sequence[i]) { 
    157                                 return false; 
    158                         } 
    159                 } 
    160                 return true; 
     163                return result; 
     164 
     165        } 
     166 
     167        public int size() { 
     168                return sequence.length; 
    161169        } 
    162170 

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

    r1620 r1733  
    3838        private SubstitutionMatrix submat; 
    3939 
     40        @Override 
     41        public void align(NumberSequence input1, NumberSequence input2, 
     42                        SubstitutionMatrix submat, float threshold) { 
     43                this.input1 = input1.getSequence(); 
     44                this.input2 = input2.getSequence(); 
     45                length1 = input1.size(); 
     46                length2 = input2.size(); 
     47                this.submat = submat; 
     48 
     49                // System.out.println("Starting SmithWaterman algorithm with a " 
     50                // + submat.getClass() + " Substitution Matrix: " + 
     51                // submat.getClass().getCanonicalName()); 
     52 
     53                matrix = new MatrixEntry[length1 + 1][length2 + 1]; 
     54                alignment = new ArrayList<NumberSequence>(); 
     55 
     56                for (int i = 0; i < (length1 + 1); i++) { 
     57                        for (int j = 0; j < (length2 + 1); j++) { 
     58                                matrix[i][j] = new MatrixEntry(); 
     59                        } 
     60                } 
     61 
     62                buildMatrix(); 
     63                traceback(); 
     64 
     65        } 
     66 
     67        /** 
     68         * Build the score matrix using dynamic programming. 
     69         */ 
     70        private void buildMatrix() { 
     71                if (submat.getGapPenalty() >= 0) { 
     72                        throw new Error("Indel score must be negative"); 
     73                } 
     74 
     75                // it's a gap 
     76                matrix[0][0].setScore(0); 
     77                matrix[0][0].setPrevious(null); // starting point 
     78 
     79                // the first column 
     80                for (int j = 1; j < length2; j++) { 
     81                        matrix[0][j].setScore(0); 
     82                        matrix[0][j].setPrevious(matrix[0][j - 1]); 
     83                        matrix[0][j].setYvalue(input2[j]); 
     84                        matrix[0][j].setXvalue(Constants.GAP_SYMBOL); 
     85                } 
     86                // the first row 
     87 
     88                for (int j = 1; j < length1; j++) { 
     89                        matrix[j][0].setScore(0); 
     90                        matrix[j][0].setPrevious(matrix[j - 1][0]); 
     91                        matrix[j][0].setXvalue(input1[j]); 
     92                        matrix[j][0].setYvalue(Constants.GAP_SYMBOL); 
     93                } 
     94 
     95                for (int i = 1; i < length1; i++) { 
     96 
     97                        for (int j = 1; j < length2; j++) { 
     98                                final double diagScore = matrix[i - 1][j - 1].getScore() 
     99                                                + similarity(i, j); 
     100                                final double upScore = matrix[i][j - 1].getScore() 
     101                                                + submat.getGapPenalty(); 
     102                                final double leftScore = matrix[i - 1][j].getScore() 
     103                                                + submat.getGapPenalty(); 
     104 
     105                                matrix[i][j].setScore(Math.max(diagScore, 
     106                                                Math.max(upScore, Math.max(leftScore, 0)))); 
     107 
     108                                // find the directions that give the maximum scores. 
     109                                // TODO: Multiple directions are ignored, we choose the first 
     110                                // maximum score 
     111                                // True if we had a match 
     112                                if (diagScore == matrix[i][j].getScore()) { 
     113                                        matrix[i][j].setPrevious(matrix[i - 1][j - 1]); 
     114                                        matrix[i][j].setXvalue(input1[i - 1]); 
     115                                        matrix[i][j].setYvalue(input2[j - 1]); 
     116                                } 
     117                                // true if we took an event from sequence x and not from y 
     118                                if (leftScore == matrix[i][j].getScore()) { 
     119                                        matrix[i][j].setXvalue(input1[i - 1]); 
     120                                        matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
     121                                        matrix[i][j].setPrevious(matrix[i - 1][j]); 
     122                                } 
     123                                // true if we took an event from sequence y and not from x 
     124                                if (upScore == matrix[i][j].getScore()) { 
     125                                        matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
     126                                        matrix[i][j].setYvalue(input2[j - 1]); 
     127                                        matrix[i][j].setPrevious(matrix[i][j - 1]); 
     128                                } 
     129                                if (0 == matrix[i][j].getScore()) { 
     130                                        matrix[i][j].setPrevious(matrix[0][0]); 
     131                                        matrix[i][j].setXvalue(-2); 
     132                                        matrix[i][j].setYvalue(-2); 
     133                                } 
     134                        } 
     135 
     136                        // Set the complete score cell 
     137 
     138                } 
     139        } 
     140 
     141        /* 
     142         * (non-Javadoc) 
     143         *  
     144         * @see 
     145         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     146         * #getAlignment() 
     147         */ 
     148        @Override 
     149        public ArrayList<NumberSequence> getAlignment() { 
     150                return alignment; 
     151        } 
     152 
     153        /* 
     154         * (non-Javadoc) 
     155         *  
     156         * @see 
     157         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     158         * #getAlignmentScore() 
     159         */ 
     160        @Override 
     161        public double getAlignmentScore() { 
     162                return getMaxScore(); 
     163        } 
     164 
     165        @Override 
     166        public ArrayList<Match> getMatches() { 
     167                // TODO Auto-generated method stub 
     168                return null; 
     169        } 
     170 
     171        /** 
     172         * Get the maximum value in the score matrix. 
     173         */ 
     174        @Override 
     175        public double getMaxScore() { 
     176                double maxScore = 0; 
     177 
     178                // skip the first row and column 
     179                for (int i = 1; i <= length1; i++) { 
     180                        for (int j = 1; j < length2; j++) { 
     181                                if (matrix[i][j].getScore() > maxScore) { 
     182                                        maxScore = matrix[i][j].getScore(); 
     183                                } 
     184                        } 
     185                } 
     186 
     187                return maxScore; 
     188        } 
     189 
     190        @Override 
     191        public void printAlignment() { 
     192                MatrixEntry tmp = matrix[length1 + 1][0]; 
     193                String aligned1 = ""; 
     194                String aligned2 = ""; 
     195                int count = 0; 
     196                do { 
     197                        String append1 = ""; 
     198                        String append2 = ""; 
     199 
     200                        if (tmp.getXvalue() == Constants.GAP_SYMBOL) { 
     201                                append1 = "  ___"; 
     202                        } else { 
     203                                append1 = String.format("%5d", tmp.getXvalue()); 
     204                        } 
     205 
     206                        if (tmp.getYvalue() == Constants.GAP_SYMBOL) { 
     207                                append2 = "  ___"; 
     208                        } else { 
     209                                append2 = String.format("%5d", tmp.getYvalue()); 
     210                        } 
     211                        if (count != 0) { 
     212                                aligned1 = append1 + aligned1; 
     213                                aligned2 = append2 + aligned2; 
     214                        } 
     215 
     216                        tmp = tmp.getPrevious(); 
     217                        count++; 
     218 
     219                } while (tmp != null); 
     220                System.out.println(aligned1); 
     221                System.out.println(aligned2); 
     222        } 
     223 
     224        /** 
     225         * print the dynmaic programming matrix 
     226         */ 
     227        @Override 
     228        public void printDPMatrix() { 
     229                System.out.print("          "); 
     230                for (int i = 1; i <= length1; i++) { 
     231                        System.out.format("%5d", input1[i - 1]); 
     232                } 
     233                System.out.println(); 
     234                for (int j = 0; j <= length2; j++) { 
     235                        if (j > 0) { 
     236                                System.out.format("%5d ", input2[j - 1]); 
     237                        } else { 
     238                                System.out.print("      "); 
     239                        } 
     240                        for (int i = 0; i <= length1; i++) { 
     241                                System.out.format("%4.1f ", matrix[i][j].getScore()); 
     242                        } 
     243                        System.out.println(); 
     244                } 
     245        } 
     246 
     247        public void setAlignment(ArrayList<NumberSequence> alignment) { 
     248                this.alignment = alignment; 
     249        } 
    40250 
    41251        /** 
    … …  
    53263        } 
    54264 
    55         /** 
    56          * Build the score matrix using dynamic programming. 
    57          */ 
    58         private void buildMatrix() { 
    59                 if (submat.getGapPenalty() >= 0) { 
    60                         throw new Error("Indel score must be negative"); 
    61                 } 
    62  
    63                 // it's a gap 
    64                 matrix[0][0].setScore(0); 
    65                 matrix[0][0].setPrevious(null); // starting point 
    66  
    67                 // the first column 
    68                 for (int j = 1; j < length2; j++) { 
    69                         matrix[0][j].setScore(0); 
    70                         matrix[0][j].setPrevious(matrix[0][j - 1]); 
    71                         matrix[0][j].setYvalue(input2[j]); 
    72                         matrix[0][j].setXvalue(Constants.GAP_SYMBOL); 
    73                 } 
    74                 // the first row 
    75  
    76                 for (int j = 1; j < length1; j++) { 
    77                         matrix[j][0].setScore(0); 
    78                         matrix[j][0].setPrevious(matrix[j - 1][0]); 
    79                         matrix[j][0].setXvalue(input1[j]); 
    80                         matrix[j][0].setYvalue(Constants.GAP_SYMBOL); 
    81                 } 
    82  
    83                 for (int i = 1; i < length1; i++) { 
    84  
    85                         for (int j = 1; j < length2; j++) { 
    86                                 double diagScore = matrix[i - 1][j - 1].getScore() 
    87                                                 + similarity(i, j); 
    88                                 double upScore = matrix[i][j - 1].getScore() 
    89                                                 + submat.getGapPenalty(); 
    90                                 double leftScore = matrix[i - 1][j].getScore() 
    91                                                 + submat.getGapPenalty(); 
    92  
    93                                 matrix[i][j].setScore(Math.max(diagScore, 
    94                                                 Math.max(upScore, Math.max(leftScore, 0)))); 
    95  
    96                                 // find the directions that give the maximum scores. 
    97                                 // TODO: Multiple directions are ignored, we choose the first 
    98                                 // maximum score 
    99                                 // True if we had a match 
    100                                 if (diagScore == matrix[i][j].getScore()) { 
    101                                         matrix[i][j].setPrevious(matrix[i - 1][j - 1]); 
    102                                         matrix[i][j].setXvalue(input1[i - 1]); 
    103                                         matrix[i][j].setYvalue(input2[j - 1]); 
    104                                 } 
    105                                 // true if we took an event from sequence x and not from y 
    106                                 if (leftScore == matrix[i][j].getScore()) { 
    107                                         matrix[i][j].setXvalue(input1[i - 1]); 
    108                                         matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
    109                                         matrix[i][j].setPrevious(matrix[i - 1][j]); 
    110                                 } 
    111                                 // true if we took an event from sequence y and not from x 
    112                                 if (upScore == matrix[i][j].getScore()) { 
    113                                         matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
    114                                         matrix[i][j].setYvalue(input2[j - 1]); 
    115                                         matrix[i][j].setPrevious(matrix[i][j - 1]); 
    116                                 } 
    117                                 if (0 == matrix[i][j].getScore()) { 
    118                                         matrix[i][j].setPrevious(matrix[0][0]); 
    119                                         matrix[i][j].setXvalue(-2); 
    120                                         matrix[i][j].setYvalue(-2); 
    121                                 } 
    122                         } 
    123  
    124                         // Set the complete score cell 
    125  
    126                 } 
    127         } 
    128  
    129         /** 
    130          * Get the maximum value in the score matrix. 
    131          */ 
    132         public double getMaxScore() { 
    133                 double maxScore = 0; 
    134  
    135                 // skip the first row and column 
    136                 for (int i = 1; i <= length1; i++) { 
    137                         for (int j = 1; j < length2; j++) { 
    138                                 if (matrix[i][j].getScore() > maxScore) { 
    139                                         maxScore = matrix[i][j].getScore(); 
    140                                 } 
    141                         } 
    142                 } 
    143  
    144                 return maxScore; 
    145         } 
    146  
    147         /* 
    148          * (non-Javadoc) 
    149          *  
    150          * @see 
    151          * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
    152          * #getAlignmentScore() 
    153          */ 
    154         @Override 
    155         public double getAlignmentScore() { 
    156                 return getMaxScore(); 
    157         } 
    158  
    159265        public void traceback() { 
    160266                MatrixEntry tmp = matrix[length1][length2]; 
    161                 int aligned1[] = new int[length1 + length2 + 2]; 
    162                 int aligned2[] = new int[length1 + length2 + 2]; 
     267                final int aligned1[] = new int[length1 + length2 + 2]; 
     268                final int aligned2[] = new int[length1 + length2 + 2]; 
    163269                int count = 0; 
    164270                do { 
    165                         if (length1 + length2 + 2 == count) { 
     271                        if ((length1 + length2 + 2) == count) { 
    166272                                Console.traceln(Level.WARNING, 
    167273                                                "Traceback longer than both sequences summed up!"); 
    … …  
    177283                count--; 
    178284                // reverse order of the alignment 
    179                 int reversed1[] = new int[count]; 
    180                 int reversed2[] = new int[count]; 
     285                final int reversed1[] = new int[count]; 
     286                final int reversed2[] = new int[count]; 
    181287 
    182288                for (int i = count - 1; i > 0; i--) { 
    … …  
    185291                } 
    186292 
    187                 NumberSequence ns1 = new NumberSequence(reversed1.length); 
    188                 NumberSequence ns2 = new NumberSequence(reversed2.length); 
     293                final NumberSequence ns1 = new NumberSequence(reversed1.length); 
     294                final NumberSequence ns2 = new NumberSequence(reversed2.length); 
    189295                ns1.setSequence(reversed1); 
    190296                ns2.setSequence(reversed2); 
    … …  
    194300        } 
    195301 
    196         public void printAlignment() { 
    197                 MatrixEntry tmp = matrix[length1 + 1][0]; 
    198                 String aligned1 = ""; 
    199                 String aligned2 = ""; 
    200                 int count = 0; 
    201                 do { 
    202                         String append1 = ""; 
    203                         String append2 = ""; 
    204  
    205                         if (tmp.getXvalue() == Constants.GAP_SYMBOL) { 
    206                                 append1 = "  ___"; 
    207                         } else { 
    208                                 append1 = String.format("%5d", tmp.getXvalue()); 
    209                         } 
    210  
    211                         if (tmp.getYvalue() == Constants.GAP_SYMBOL) { 
    212                                 append2 = "  ___"; 
    213                         } else { 
    214                                 append2 = String.format("%5d", tmp.getYvalue()); 
    215                         } 
    216                         if (count != 0) { 
    217                                 aligned1 = append1 + aligned1; 
    218                                 aligned2 = append2 + aligned2; 
    219                         } 
    220  
    221                         tmp = tmp.getPrevious(); 
    222                         count++; 
    223  
    224                 } while (tmp != null); 
    225                 System.out.println(aligned1); 
    226                 System.out.println(aligned2); 
    227         } 
    228  
    229         /** 
    230          * print the dynmaic programming matrix 
    231          */ 
    232         public void printDPMatrix() { 
    233                 System.out.print("          "); 
    234                 for (int i = 1; i <= length1; i++) 
    235                         System.out.format("%5d", input1[i - 1]); 
    236                 System.out.println(); 
    237                 for (int j = 0; j <= length2; j++) { 
    238                         if (j > 0) 
    239                                 System.out.format("%5d ", input2[j - 1]); 
    240                         else { 
    241                                 System.out.print("      "); 
    242                         } 
    243                         for (int i = 0; i <= length1; i++) { 
    244                                         System.out.format("%4.1f ", matrix[i][j].getScore()); 
    245                         } 
    246                         System.out.println(); 
    247                 } 
    248         } 
    249  
    250         /* 
    251          * (non-Javadoc) 
    252          *  
    253          * @see 
    254          * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
    255          * #getAlignment() 
    256          */ 
    257         @Override 
    258         public ArrayList<NumberSequence> getAlignment() { 
    259                 return alignment; 
    260         } 
    261  
    262         public void setAlignment(ArrayList<NumberSequence> alignment) { 
    263                 this.alignment = alignment; 
    264         } 
    265  
    266         @Override 
    267         public ArrayList<Match> getMatches() { 
    268                 // TODO Auto-generated method stub 
    269                 return null; 
    270         } 
    271  
    272         @Override 
    273         public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    274                         float threshold) { 
    275                 this.input1 = input1.getSequence(); 
    276                 this.input2 = input2.getSequence(); 
    277                 length1 = input1.size(); 
    278                 length2 = input2.size(); 
    279                 this.submat = submat; 
    280  
    281                 // System.out.println("Starting SmithWaterman algorithm with a " 
    282                 // + submat.getClass() + " Substitution Matrix: " + 
    283                 // submat.getClass().getCanonicalName()); 
    284  
    285                 matrix = new MatrixEntry[length1 + 1][length2 + 1]; 
    286                 alignment = new ArrayList<NumberSequence>(); 
    287  
    288                 for (int i = 0; i < length1+1; i++) { 
    289                         for (int j = 0; j < length2+1; j++) { 
    290                                 matrix[i][j] = new MatrixEntry(); 
    291                         } 
    292                 } 
    293  
    294                 buildMatrix(); 
    295                 traceback(); 
    296                  
    297         } 
    298  
    299302} 

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

    r1654 r1733  
    55import java.util.LinkedList; 
    66 
    7  
    87import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.SubstitutionMatrix; 
    98import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Constants; 
    109 
    11  
    1210public class SmithWatermanRepeated implements AlignmentAlgorithm { 
    1311 
    … …  
    3331        private MatrixEntry[][] matrix; 
    3432 
    35  
    3633        private ArrayList<NumberSequence> alignment; 
    37          
     34 
    3835        private float scoreThreshold; 
    3936 
    … …  
    4441 
    4542        public SmithWatermanRepeated() { 
    46          
     43 
     44        } 
     45 
     46        @Override 
     47        public void align(NumberSequence input1, NumberSequence input2, 
     48                        SubstitutionMatrix submat, float threshold) { 
     49 
     50                alignment = new ArrayList<NumberSequence>(); 
     51                alignment.add(input1); 
     52                alignment.add(input2); 
     53 
     54                this.input1 = input1.getSequence(); 
     55                this.input2 = input2.getSequence(); 
     56 
     57                length1 = input1.size(); 
     58                length2 = input2.size(); 
     59                this.submat = submat; 
     60 
     61                // System.out.println("Starting SmithWaterman algorithm with a " 
     62                // + submat.getClass() + " Substitution Matrix: " + 
     63                // submat.getClass().getCanonicalName()); 
     64                this.scoreThreshold = threshold; 
     65 
     66                matrix = new MatrixEntry[length1 + 2][length2 + 1]; 
     67 
     68                for (int i = 0; i <= (length1 + 1); i++) { 
     69                        for (int j = 0; j <= length2; j++) { 
     70                                matrix[i][j] = new MatrixEntry(); 
     71                        } 
     72                } 
     73 
     74                // Console.traceln(Level.INFO,"Generating DP Matrix"); 
     75                buildMatrix(); 
     76                // Console.traceln(Level.INFO,"Doing traceback"); 
     77                traceback(); 
     78        } 
     79 
     80        /** 
     81         * Build the score matrix using dynamic programming. 
     82         */ 
     83        private void buildMatrix() { 
     84                if (submat.getGapPenalty() >= 0) { 
     85                        throw new Error("Indel score must be negative"); 
     86                } 
     87 
     88                // it's a gap 
     89                matrix[0][0].setScore(0); 
     90                matrix[0][0].setPrevious(null); // starting point 
     91                matrix[0][0].setXvalue(Constants.UNMATCHED_SYMBOL); 
     92                matrix[0][0].setYvalue(Constants.UNMATCHED_SYMBOL); 
     93 
     94                // the first column 
     95                for (int j = 1; j < length2; j++) { 
     96                        matrix[0][j].setScore(0); 
     97                        // We don't need to go back to [0][0] if we reached matrix[0][x], so 
     98                        // just end here 
     99                        // matrix[0][j].setPrevious(matrix[0][j-1]); 
     100                        matrix[0][j].setPrevious(null); 
     101                } 
     102 
     103                for (int i = 1; i < (length1 + 2); i++) { 
     104 
     105                        // Formula for first row: 
     106                        // F(i,0) = max { F(i-1,0), F(i-1,j)-T j=1,...,m 
     107 
     108                        final double firstRowLeftScore = matrix[i - 1][0].getScore(); 
     109                        // for sequences of length 1 
     110                        double tempMax; 
     111                        int maxRowIndex; 
     112                        if (length2 == 1) { 
     113                                tempMax = matrix[i - 1][0].getScore(); 
     114                                maxRowIndex = 0; 
     115                        } else { 
     116                                tempMax = matrix[i - 1][1].getScore(); 
     117                                maxRowIndex = 1; 
     118                                // position of the maximal score of the previous row 
     119 
     120                                for (int j = 2; j <= length2; j++) { 
     121                                        if (matrix[i - 1][j].getScore() > tempMax) { 
     122                                                tempMax = matrix[i - 1][j].getScore(); 
     123                                                maxRowIndex = j; 
     124                                        } 
     125                                } 
     126 
     127                        } 
     128 
     129                        tempMax -= scoreThreshold; 
     130                        matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax)); 
     131                        if (tempMax == matrix[i][0].getScore()) { 
     132                                matrix[i][0].setPrevious(matrix[i - 1][maxRowIndex]); 
     133                        } 
     134 
     135                        if (firstRowLeftScore == matrix[i][0].getScore()) { 
     136                                matrix[i][0].setPrevious(matrix[i - 1][0]); 
     137                        } 
     138 
     139                        // The last additional score is not related to a character in the 
     140                        // input sequence, it's the total score. Therefore we don't need to 
     141                        // save something for it 
     142                        // and can end here 
     143                        if (i < (length1 + 1)) { 
     144                                matrix[i][0].setXvalue(input1[i - 1]); 
     145                                matrix[i][0].setYvalue(Constants.UNMATCHED_SYMBOL); 
     146                        } else { 
     147                                return; 
     148                        } 
     149 
     150                        for (int j = 1; j <= length2; j++) { 
     151                                final double diagScore = matrix[i - 1][j - 1].getScore() 
     152                                                + similarity(i, j); 
     153                                final double upScore = matrix[i][j - 1].getScore() 
     154                                                + submat.getGapPenalty(); 
     155                                final double leftScore = matrix[i - 1][j].getScore() 
     156                                                + submat.getGapPenalty(); 
     157 
     158                                matrix[i][j].setScore(Math.max( 
     159                                                diagScore, 
     160                                                Math.max(upScore, 
     161                                                                Math.max(leftScore, matrix[i][0].getScore())))); 
     162 
     163                                // find the directions that give the maximum scores. 
     164                                // TODO: Multiple directions are ignored, we choose the first 
     165                                // maximum score 
     166                                // True if we had a match 
     167                                if (diagScore == matrix[i][j].getScore()) { 
     168                                        matrix[i][j].setPrevious(matrix[i - 1][j - 1]); 
     169                                        matrix[i][j].setXvalue(input1[i - 1]); 
     170                                        matrix[i][j].setYvalue(input2[j - 1]); 
     171                                } 
     172                                // true if we took an event from sequence x and not from y 
     173                                if (leftScore == matrix[i][j].getScore()) { 
     174                                        matrix[i][j].setXvalue(input1[i - 1]); 
     175                                        matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
     176                                        matrix[i][j].setPrevious(matrix[i - 1][j]); 
     177                                } 
     178                                // true if we took an event from sequence y and not from x 
     179                                if (upScore == matrix[i][j].getScore()) { 
     180                                        matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
     181                                        matrix[i][j].setYvalue(input2[j - 1]); 
     182                                        matrix[i][j].setPrevious(matrix[i][j - 1]); 
     183                                } 
     184                                // true if we ended a matching region 
     185                                if (matrix[i][0].getScore() == matrix[i][j].getScore()) { 
     186                                        matrix[i][j].setPrevious(matrix[i][0]); 
     187                                        matrix[i][j].setXvalue(input1[i - 1]); 
     188                                        matrix[i][j].setYvalue(Constants.UNMATCHED_SYMBOL); 
     189                                } 
     190                        } 
     191 
     192                        // Set the complete score cell 
     193 
     194                } 
     195        } 
     196 
     197        /* 
     198         * (non-Javadoc) 
     199         *  
     200         * @see 
     201         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     202         * #getAlignment() 
     203         */ 
     204        @Override 
     205        public ArrayList<NumberSequence> getAlignment() { 
     206                return alignment; 
     207        } 
     208 
     209        /* 
     210         * (non-Javadoc) 
     211         *  
     212         * @see 
     213         * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm 
     214         * #getAlignmentScore() 
     215         */ 
     216        @Override 
     217        public double getAlignmentScore() { 
     218                return matrix[length1 + 1][0].getScore(); 
     219        } 
     220 
     221        @Override 
     222        public ArrayList<Match> getMatches() { 
     223                final ArrayList<Match> result = new ArrayList<Match>(); 
     224 
     225                // both alignment sequences should be equally long 
     226                int i = 0; 
     227                final int[] seq1 = alignment.get(0).getSequence(); 
     228                final int[] seq2 = alignment.get(1).getSequence(); 
     229                int start = 0; 
     230                while (i < seq1.length) { 
     231                        if (seq2[i] != Constants.UNMATCHED_SYMBOL) { 
     232                                start = i; 
     233                                int count = 0; 
     234                                while ((i < seq2.length) 
     235                                                && (seq2[i] != Constants.UNMATCHED_SYMBOL)) { 
     236                                        i++; 
     237                                        count++; 
     238                                } 
     239                                // I am really missing memcpy here? How does one do this better 
     240                                // in java? 
     241                                final int[] tmp1 = new int[count]; 
     242                                final int[] tmp2 = new int[count]; 
     243                                for (int j = 0; j < count; j++) { 
     244                                        tmp1[j] = seq1[start + j]; 
     245                                        tmp2[j] = seq2[start + j]; 
     246                                } 
     247                                final NumberSequence tmpns1 = new NumberSequence(count); 
     248                                final NumberSequence tmpns2 = new NumberSequence(count); 
     249                                tmpns1.setSequence(tmp1); 
     250                                tmpns2.setSequence(tmp2); 
     251                                final Match tmpal = new Match(); 
     252                                tmpal.setFirstSequence(tmpns1); 
     253                                tmpal.setSecondSequence(tmpns2); 
     254                                // tmpal.addOccurence(new 
     255                                // MatchOccurence(start,alignment.get(0).getId())); 
     256                                // tmpal.addOccurence(new 
     257                                // MatchOccurence(start,alignment.get(1).getId())); 
     258                                result.add(tmpal); 
     259                        } 
     260                        i++; 
     261                } 
     262                return result; 
     263        } 
     264 
     265        /** 
     266         * Get the maximum value in the score matrix. 
     267         */ 
     268        @Override 
     269        public double getMaxScore() { 
     270                double maxScore = 0; 
     271 
     272                // skip the first row and column 
     273                for (int i = 1; i <= length1; i++) { 
     274                        for (int j = 1; j <= length2; j++) { 
     275                                if (matrix[i][j].getScore() > maxScore) { 
     276                                        maxScore = matrix[i][j].getScore(); 
     277                                } 
     278                        } 
     279                } 
     280 
     281                return maxScore; 
     282        } 
     283 
     284        @Override 
     285        public void printAlignment() { 
     286                final int[] tmp1 = alignment.get(0).getSequence(); 
     287                final int[] tmp2 = alignment.get(1).getSequence(); 
     288                for (int i = 0; i < tmp1.length; i++) { 
     289                        if (tmp1[i] == Constants.GAP_SYMBOL) { 
     290                                System.out.print("  ___"); 
     291                        } else if (tmp1[i] == Constants.UNMATCHED_SYMBOL) { 
     292                                System.out.print("  ..."); 
     293                        } else { 
     294                                System.out.format("%5d", tmp1[i]); 
     295                        } 
     296 
     297                } 
     298                System.out.println(); 
     299                for (int i = 0; i < tmp2.length; i++) { 
     300                        if (tmp2[i] == Constants.GAP_SYMBOL) { 
     301                                System.out.print("  ___"); 
     302                        } else if (tmp2[i] == Constants.UNMATCHED_SYMBOL) { 
     303                                System.out.print("  ..."); 
     304                        } else { 
     305                                System.out.format("%5d", tmp2[i]); 
     306                        } 
     307 
     308                } 
     309                System.out.println(); 
     310 
     311        } 
     312 
     313        /** 
     314         * print the dynmaic programming matrix 
     315         */ 
     316        @Override 
     317        public void printDPMatrix() { 
     318                System.out.print("          "); 
     319                for (int i = 1; i <= length1; i++) { 
     320                        System.out.format("%5d", input1[i - 1]); 
     321                } 
     322                System.out.println(); 
     323                for (int j = 0; j <= length2; j++) { 
     324                        if (j > 0) { 
     325                                System.out.format("%5d ", input2[j - 1]); 
     326                        } else { 
     327                                System.out.print("      "); 
     328                        } 
     329                        for (int i = 0; i <= (length1 + 1); i++) { 
     330                                if ((i < (length1 + 1)) || ((i == (length1 + 1)) && (j == 0))) { 
     331                                        System.out.format("%4.1f ", matrix[i][j].getScore()); 
     332                                } 
     333 
     334                        } 
     335                        System.out.println(); 
     336                } 
     337        } 
     338 
     339        public void setAlignment(ArrayList<NumberSequence> alignment) { 
     340                this.alignment = alignment; 
    47341        } 
    48342 
    … …  
    57351         * @return Cost of substitution of the character in str1 by the one in str2 
    58352         */ 
    59         private double similarity(int i, int j) {  
     353        private double similarity(int i, int j) { 
    60354                return submat.getScore(input1[i - 1], input2[j - 1]); 
    61355        } 
    62356 
    63         /** 
    64          * Build the score matrix using dynamic programming. 
    65          */ 
    66         private void buildMatrix() { 
    67                 if (submat.getGapPenalty() >= 0) { 
    68                         throw new Error("Indel score must be negative"); 
    69                 } 
    70                  
    71                 // it's a gap 
    72                 matrix[0][0].setScore(0); 
    73                 matrix[0][0].setPrevious(null); // starting point 
    74                 matrix[0][0].setXvalue(Constants.UNMATCHED_SYMBOL); 
    75                 matrix[0][0].setYvalue(Constants.UNMATCHED_SYMBOL); 
    76  
    77                 // the first column 
    78                 for (int j = 1; j < length2; j++) { 
    79                         matrix[0][j].setScore(0); 
    80                         //We don't need to go back to [0][0] if we reached matrix[0][x], so just end here 
    81                         //matrix[0][j].setPrevious(matrix[0][j-1]); 
    82                         matrix[0][j].setPrevious(null);  
    83                 } 
    84                  
    85                  
    86                  
    87                 for (int i = 1; i < length1 + 2; i++) { 
    88                  
    89                         // Formula for first row: 
    90                         // F(i,0) = max { F(i-1,0), F(i-1,j)-T  j=1,...,m 
    91                          
    92                         double firstRowLeftScore = matrix[i-1][0].getScore(); 
    93                         //for sequences of length 1 
    94                         double tempMax; 
    95                         int maxRowIndex; 
    96                         if(length2 == 1) { 
    97                                 tempMax = matrix[i-1][0].getScore(); 
    98                                 maxRowIndex = 0; 
    99                         } else { 
    100                                 tempMax = matrix[i-1][1].getScore(); 
    101                                 maxRowIndex = 1; 
    102                                 //position of the maximal score of the previous row 
    103                                  
    104                                 for(int j = 2; j <= length2;j++) { 
    105                                         if(matrix[i-1][j].getScore() > tempMax) { 
    106                                                 tempMax = matrix[i-1][j].getScore(); 
    107                                                 maxRowIndex = j; 
    108                                         } 
    109                                 } 
    110  
    111                         } 
    112                                          
    113                         tempMax -= scoreThreshold; 
    114                         matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax)); 
    115                         if(tempMax == matrix[i][0].getScore()){ 
    116                                 matrix[i][0].setPrevious(matrix[i-1][maxRowIndex]); 
    117                         } 
    118                          
    119                         if(firstRowLeftScore == matrix[i][0].getScore()) { 
    120                                 matrix[i][0].setPrevious(matrix[i-1][0]); 
    121                         } 
    122                          
    123                         //The last additional score is not related to a character in the input sequence, it's the total score. Therefore we don't need to save something for it 
    124                         //and can end here 
    125                         if(i<length1+1) { 
    126                                 matrix[i][0].setXvalue(input1[i-1]); 
    127                                 matrix[i][0].setYvalue(Constants.UNMATCHED_SYMBOL); 
    128                         } 
    129                         else { 
    130                                 return; 
    131                         } 
    132                   
    133                          
    134                          
    135                         for (int j = 1; j <= length2; j++) { 
    136                                 double diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j); 
    137                                 double upScore = matrix[i][j - 1].getScore() + submat.getGapPenalty(); 
    138                                 double leftScore = matrix[i - 1][j].getScore() + submat.getGapPenalty(); 
    139  
    140                                 matrix[i][j].setScore(Math.max(diagScore,Math.max(upScore, Math.max(leftScore,matrix[i][0].getScore())))); 
    141  
    142                                 // find the directions that give the maximum scores. 
    143                                 // TODO: Multiple directions are ignored, we choose the first maximum score  
    144                                 //True if we had a match 
    145                                 if (diagScore == matrix[i][j].getScore()) { 
    146                                         matrix[i][j].setPrevious(matrix[i-1][j-1]); 
    147                                         matrix[i][j].setXvalue(input1[i-1]); 
    148                                         matrix[i][j].setYvalue(input2[j-1]); 
    149                                 } 
    150                                 //true if we took an event from sequence x and not from y 
    151                                 if (leftScore == matrix[i][j].getScore()) { 
    152                                         matrix[i][j].setXvalue(input1[i-1]); 
    153                                         matrix[i][j].setYvalue(Constants.GAP_SYMBOL); 
    154                                         matrix[i][j].setPrevious(matrix[i-1][j]); 
    155                                 } 
    156                                 //true if we took an event from sequence y and not from x 
    157                                 if (upScore == matrix[i][j].getScore()) { 
    158                                         matrix[i][j].setXvalue(Constants.GAP_SYMBOL); 
    159                                         matrix[i][j].setYvalue(input2[j-1]); 
    160                                         matrix[i][j].setPrevious(matrix[i][j-1]); 
    161                                 } 
    162                                 //true if we ended a matching region  
    163                                 if (matrix[i][0].getScore() == matrix[i][j].getScore()) { 
    164                                         matrix[i][j].setPrevious(matrix[i][0]); 
    165                                         matrix[i][j].setXvalue(input1[i-1]); 
    166                                         matrix[i][j].setYvalue(Constants.UNMATCHED_SYMBOL); 
    167                                 } 
    168                         } 
    169                          
    170                         //Set the complete score cell 
    171                          
    172                 } 
    173         } 
    174  
    175         /** 
    176          * Get the maximum value in the score matrix. 
    177          */ 
    178         public double getMaxScore() { 
    179                 double maxScore = 0; 
    180  
    181                 // skip the first row and column 
    182                 for (int i = 1; i <= length1; i++) { 
    183                         for (int j = 1; j <= length2; j++) { 
    184                                 if (matrix[i][j].getScore() > maxScore) { 
    185                                         maxScore = matrix[i][j].getScore(); 
    186                                 } 
    187                         } 
    188                 } 
    189  
    190                 return maxScore; 
    191         } 
    192  
    193         /* (non-Javadoc) 
    194          * @see de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm#getAlignmentScore() 
    195          */ 
    196         @Override 
    197         public double getAlignmentScore() { 
    198                 return matrix[length1+1][0].getScore(); 
    199         } 
    200  
    201357        public void traceback() { 
    202                 MatrixEntry tmp = matrix[length1+1][0].getPrevious(); 
    203                 LinkedList<Integer> aligned1 = new LinkedList<Integer>(); 
    204                 LinkedList<Integer> aligned2 = new LinkedList<Integer>(); 
     358                MatrixEntry tmp = matrix[length1 + 1][0].getPrevious(); 
     359                final LinkedList<Integer> aligned1 = new LinkedList<Integer>(); 
     360                final LinkedList<Integer> aligned2 = new LinkedList<Integer>(); 
    205361                while (tmp.getPrevious() != null) { 
    206                          
     362 
    207363                        aligned1.add(new Integer(tmp.getXvalue())); 
    208364                        aligned2.add(new Integer(tmp.getYvalue())); 
    209365 
    210366                        tmp = tmp.getPrevious(); 
    211                 }  
    212                  
     367                } 
     368 
    213369                // reverse order of the alignment 
    214                 int reversed1[] = new int[aligned1.size()]; 
    215                 int reversed2[] = new int[aligned2.size()]; 
     370                final int reversed1[] = new int[aligned1.size()]; 
     371                final int reversed2[] = new int[aligned2.size()]; 
    216372 
    217373                int count = 0; 
    218                 for (Iterator<Integer> it = aligned1.iterator(); it.hasNext();) { 
     374                for (final Iterator<Integer> it = aligned1.iterator(); it.hasNext();) { 
    219375                        count++; 
    220376                        reversed1[reversed1.length - count] = it.next(); 
    221                          
     377 
    222378                } 
    223379                count = 0; 
    224                 for (Iterator<Integer> it = aligned2.iterator(); it.hasNext();) { 
     380                for (final Iterator<Integer> it = aligned2.iterator(); it.hasNext();) { 
    225381                        count++; 
    226382                        reversed2[reversed2.length - count] = it.next(); 
    227383                } 
    228384 
    229                  
    230                 NumberSequence ns1 = new NumberSequence(reversed1.length); 
    231                 NumberSequence ns2 = new NumberSequence(reversed2.length); 
     385                final NumberSequence ns1 = new NumberSequence(reversed1.length); 
     386                final NumberSequence ns2 = new NumberSequence(reversed2.length); 
    232387                ns1.setSequence(reversed1); 
    233388                ns2.setSequence(reversed2); 
    234389                ns1.setId(alignment.get(0).getId()); 
    235390                ns2.setId(alignment.get(1).getId()); 
    236                  
     391 
    237392                alignment.set(0, ns1); 
    238393                alignment.set(1, ns2); 
    239394        } 
    240          
    241  
    242          
    243         public void printAlignment() { 
    244                 int[] tmp1 = alignment.get(0).getSequence(); 
    245                 int[] tmp2 = alignment.get(1).getSequence(); 
    246                 for (int i=0; i< tmp1.length;i++) { 
    247                         if(tmp1[i] == Constants.GAP_SYMBOL) { 
    248                                 System.out.print("  ___"); 
    249                         } 
    250                         else if(tmp1[i] == Constants.UNMATCHED_SYMBOL) { 
    251                                 System.out.print("  ..."); 
    252                         } 
    253                         else { 
    254                                 System.out.format("%5d", tmp1[i]); 
    255                         } 
    256                          
    257                 } 
    258                 System.out.println(); 
    259                 for (int i=0; i< tmp2.length;i++) { 
    260                         if(tmp2[i] == Constants.GAP_SYMBOL) { 
    261                                 System.out.print("  ___"); 
    262                         } 
    263                         else if(tmp2[i] == Constants.UNMATCHED_SYMBOL) { 
    264                                 System.out.print("  ..."); 
    265                         } 
    266                         else { 
    267                                 System.out.format("%5d", tmp2[i]); 
    268                         } 
    269                          
    270                 } 
    271                 System.out.println(); 
    272                  
    273                  
    274          
    275         } 
    276          
    277         public ArrayList<Match> getMatches() { 
    278                 ArrayList<Match> result = new ArrayList<Match>(); 
    279                  
    280                 //both alignment sequences should be equally long 
    281                 int i = 0; 
    282                 int[] seq1 = alignment.get(0).getSequence(); 
    283                 int[] seq2 = alignment.get(1).getSequence(); 
    284                 int start = 0; 
    285                 while (i < seq1.length){ 
    286                         if(seq2[i] != Constants.UNMATCHED_SYMBOL) { 
    287                                 start = i; 
    288                                 int count = 0; 
    289                                 while(i < seq2.length && seq2[i] != Constants.UNMATCHED_SYMBOL) { 
    290                                         i++; 
    291                                         count++; 
    292                                 } 
    293                                 //I am really missing memcpy here? How does one do this better in java?  
    294                                 int[] tmp1 = new int[count]; 
    295                                 int[] tmp2 = new int[count]; 
    296                                 for (int j = 0; j<count;j++) { 
    297                                         tmp1[j] = seq1[start+j]; 
    298                                         tmp2[j] = seq2[start+j]; 
    299                                 } 
    300                                 NumberSequence tmpns1 = new NumberSequence(count); 
    301                                 NumberSequence tmpns2 = new NumberSequence(count); 
    302                                 tmpns1.setSequence(tmp1); 
    303                                 tmpns2.setSequence(tmp2); 
    304                                 Match tmpal = new Match(); 
    305                                 tmpal.setFirstSequence(tmpns1); 
    306                                 tmpal.setSecondSequence(tmpns2); 
    307                                 //tmpal.addOccurence(new MatchOccurence(start,alignment.get(0).getId())); 
    308                                 //tmpal.addOccurence(new MatchOccurence(start,alignment.get(1).getId())); 
    309                                 result.add(tmpal); 
    310                         } 
    311                         i++; 
    312                 } 
    313                 return result; 
    314         } 
    315          
    316         /** 
    317          * print the dynmaic programming matrix 
    318          */ 
    319         public void printDPMatrix() { 
    320                 System.out.print("          "); 
    321                 for (int i = 1; i <= length1; i++) 
    322                         System.out.format("%5d", input1[i - 1]); 
    323                 System.out.println(); 
    324                 for (int j = 0; j <= length2; j++) { 
    325                         if (j > 0) 
    326                                 System.out.format("%5d ",input2[j - 1]); 
    327                         else{ 
    328                                 System.out.print("      "); 
    329                         } 
    330                         for (int i = 0; i <= length1 + 1; i++) { 
    331                                 if((i<length1+1) || (i==length1+1 && j==0))     { 
    332                                         System.out.format("%4.1f ",matrix[i][j].getScore()); 
    333                                 } 
    334                                  
    335                         }                        
    336                         System.out.println(); 
    337                 } 
    338         } 
    339  
    340  
    341         /* (non-Javadoc) 
    342          * @see de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm#getAlignment() 
    343          */ 
    344         @Override 
    345         public ArrayList<NumberSequence> getAlignment() { 
    346                 return alignment; 
    347         } 
    348  
    349         public void setAlignment(ArrayList<NumberSequence> alignment) { 
    350                 this.alignment = alignment; 
    351         } 
    352  
    353         @Override 
    354         public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    355                         float threshold) { 
    356                  
    357                 alignment = new ArrayList<NumberSequence>(); 
    358                 alignment.add(input1); 
    359                 alignment.add(input2); 
    360                  
    361                 this.input1=input1.getSequence(); 
    362                 this.input2=input2.getSequence(); 
    363                  
    364                 length1 = input1.size(); 
    365                 length2 = input2.size(); 
    366                 this.submat = submat; 
    367  
    368                 //System.out.println("Starting SmithWaterman algorithm with a " 
    369                 //              + submat.getClass() + " Substitution Matrix: " + submat.getClass().getCanonicalName()); 
    370                 this.scoreThreshold = threshold; 
    371                  
    372                 matrix = new MatrixEntry[length1+2][length2+1]; 
    373                  
    374                  
    375                 for (int i = 0; i <= length1+1; i++) { 
    376                         for(int j = 0; j<= length2; j++) { 
    377                                 matrix[i][j] = new MatrixEntry(); 
    378                         } 
    379                 } 
    380          
    381                 //Console.traceln(Level.INFO,"Generating DP Matrix"); 
    382                 buildMatrix(); 
    383                 //Console.traceln(Level.INFO,"Doing traceback"); 
    384                 traceback(); 
    385         } 
    386395 
    387396} 

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

    r1702 r1733  
    99import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; 
    1010 
    11  
    1211/** 
    1312 * @author Ralph Krimmel 
    … …  
    1615public class DifferenceSubstitutionMatrix implements SubstitutionMatrix { 
    1716 
    18         private int[] input1; 
    19         private int[] input2; 
    20         private int maxValue; 
    21          
    22         public DifferenceSubstitutionMatrix(int[] input1,int[] input2) { 
     17        private final int[] input1; 
     18        private final int[] input2; 
     19        private final int maxValue; 
     20 
     21        public DifferenceSubstitutionMatrix(int[] input1, int[] input2) { 
    2322                this.input1 = input1; 
    2423                this.input2 = input2; 
    2524                this.maxValue = getMaxValue(); 
    2625        } 
    27          
    28         /* (non-Javadoc) 
    29          * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int) 
    30          */ 
    31         public float getScore(int pos1, int pos2) { 
    32                 return maxValue - (input1[pos1] - input2[pos2]); 
    33         } 
    34          
    35         private int getMaxValue() { 
    36                 int max = input1[0]; 
    37                 for (int i=0; i < input1.length; i++) { 
    38                         if(input1[i] > max) { 
    39                                 max = input1[i]; 
    40                         } 
    41                 } 
    42                 for (int j=0; j < input2.length; j++) { 
    43                         if(input2[j] > max) { 
    44                                 max = input2[j]; 
    45                         } 
    46                 } 
    47                 return max; 
     26 
     27        @Override 
     28        public void generate(HashSet<ITask> uniqueTasks) { 
    4829        } 
    4930 
    … …  
    5334        } 
    5435 
     36        private int getMaxValue() { 
     37                int max = input1[0]; 
     38                for (int i = 0; i < input1.length; i++) { 
     39                        if (input1[i] > max) { 
     40                                max = input1[i]; 
     41                        } 
     42                } 
     43                for (int j = 0; j < input2.length; j++) { 
     44                        if (input2[j] > max) { 
     45                                max = input2[j]; 
     46                        } 
     47                } 
     48                return max; 
     49        } 
    5550 
     51        /* 
     52         * (non-Javadoc) 
     53         *  
     54         * @see 
     55         * de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, 
     56         * int) 
     57         */ 
    5658        @Override 
    57         public void generate(HashSet<ITask> uniqueTasks) { 
     59        public float getScore(int pos1, int pos2) { 
     60                return maxValue - (input1[pos1] - input2[pos2]); 
    5861        } 
    5962 

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

    r1702 r1733  
    99 
    1010        @Override 
    11         public float getScore(int pos1, int pos2) { 
    12                 if(pos1==pos2) { 
    13                         return 1; 
    14                 } 
    15                 else { 
    16                         return 0; 
    17                 } 
     11        public void generate(HashSet<ITask> uniqueTasks) { 
    1812        } 
    1913 
    … …  
    2418 
    2519        @Override 
    26         public void generate(HashSet<ITask> uniqueTasks) { 
     20        public float getScore(int pos1, int pos2) { 
     21                if (pos1 == pos2) { 
     22                        return 1; 
     23                } else { 
     24                        return 0; 
     25                } 
    2726        } 
    2827 
    … …  
    3029        public void update(LinkedList<ITask> newlyGeneratedTasks) { 
    3130                // TODO Auto-generated method stub 
    32                  
     31 
    3332        } 
    34          
    3533 
    3634} 

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

    r1702 r1733  
    55//Must be initialized! 
    66public class DynamicTriangleMatrix implements ITriangleMatrix { 
    7          
    8         private ArrayList<Float> matrix; 
     7 
     8        private final ArrayList<Float> matrix; 
    99        protected int size; 
    1010        private float initalizationValue; 
    11          
    12          
    13          
    14         //Increases the size 
    15         /* (non-Javadoc) 
    16          * @see de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#increaseSize(int) 
     11 
     12        public DynamicTriangleMatrix(int size) { 
     13                this.size = size; 
     14                matrix = new ArrayList<Float>(); 
     15                matrix.ensureCapacity(size * (size + (1 / 2))); 
     16        } 
     17 
     18        /* 
     19         * (non-Javadoc) 
     20         *  
     21         * @see 
     22         * de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#get(int, 
     23         * int) 
     24         */ 
     25        @Override 
     26        public float get(int first, int second) { 
     27                final int row = Math.min(first, second); 
     28                final int col = Math.max(first, second); 
     29                return matrix.get((row * size) 
     30                                - (((row * (row + 1)) / 2) - (size - col))); 
     31 
     32        } 
     33 
     34        // Increases the size 
     35        /* 
     36         * (non-Javadoc) 
     37         *  
     38         * @see 
     39         * de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#increaseSize 
     40         * (int) 
    1741         */ 
    1842        @Override 
    1943        public void increaseSize(int count) { 
    20                 int oldsize = size; 
     44                final int oldsize = size; 
    2145                this.size += count; 
    22                 matrix.ensureCapacity(size*(size+1/2)); 
    23                 for(int i=0;i<(oldsize*count)+(count*(count+1)/2);i++) { 
     46                matrix.ensureCapacity(size * (size + (1 / 2))); 
     47                for (int i = 0; i < ((oldsize * count) + ((count * (count + 1)) / 2)); i++) { 
    2448                        matrix.add(this.initalizationValue); 
    2549                } 
    2650        } 
    2751 
    28  
    29         public DynamicTriangleMatrix(int size) { 
    30                 this.size = size; 
    31                 matrix = new ArrayList<Float>(); 
    32                 matrix.ensureCapacity(size*(size+1/2)); 
    33         } 
    34  
    35          
    36         /* (non-Javadoc) 
    37          * @see de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#get(int, int) 
    38          */ 
    39         @Override 
    40         public float get(int first, int second) { 
    41                 int row = Math.min(first, second); 
    42                 int col = Math.max(first, second); 
    43                 return matrix.get(row*size-(row*(row+1)/2 - (size-col))); 
    44                  
    45         } 
    46          
    47         /* (non-Javadoc) 
    48          * @see de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#set(int, int, float) 
    49          */ 
    50         @Override 
    51         public void set(int first, int second, float value) { 
    52                 int row = Math.min(first, second); 
    53                 int col = Math.max(first, second); 
    54                 matrix.set(row*size-(row*(row+1)/2 - (size-col)),value); 
    55         } 
    56  
    57         /* (non-Javadoc) 
    58          * @see de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#initialize(float) 
     52        /* 
     53         * (non-Javadoc) 
     54         *  
     55         * @see 
     56         * de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#initialize 
     57         * (float) 
    5958         */ 
    6059        @Override 
    … …  
    6261                this.initalizationValue = value; 
    6362                matrix.clear(); 
    64                 for (int i=0; i < this.size*(this.size+1)/2; i++) { 
     63                for (int i = 0; i < ((this.size * (this.size + 1)) / 2); i++) { 
    6564                        matrix.add(value); 
    6665                } 
    6766        } 
    68          
    69          
    70         /* (non-Javadoc) 
    71          * @see de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#toString() 
     67 
     68        /* 
     69         * (non-Javadoc) 
     70         *  
     71         * @see 
     72         * de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#set(int, 
     73         * int, float) 
     74         */ 
     75        @Override 
     76        public void set(int first, int second, float value) { 
     77                final int row = Math.min(first, second); 
     78                final int col = Math.max(first, second); 
     79                matrix.set((row * size) - (((row * (row + 1)) / 2) - (size - col)), 
     80                                value); 
     81        } 
     82 
     83        @Override 
     84        public int size() { 
     85                return size; 
     86        } 
     87 
     88        /* 
     89         * (non-Javadoc) 
     90         *  
     91         * @see 
     92         * de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ITriangleMatrix#toString 
     93         * () 
    7294         */ 
    7395        @Override 
    … …  
    7597                String result = ""; 
    7698                for (int i = 0; i < size; i++) { 
    77                         for(int j = 0; j< size; j++) { 
    78                                 if(i<j) { 
    79                                         if(Float.isInfinite(this.get(i,j))) { 
     99                        for (int j = 0; j < size; j++) { 
     100                                if (i < j) { 
     101                                        if (Float.isInfinite(this.get(i, j))) { 
    80102                                                result = result + " -------"; 
     103                                        } else { 
     104                                                result = result 
     105                                                                + String.format("%+8.2f", this.get(i, j)); 
    81106                                        } 
    82                                         else { 
    83                                                 result = result + String.format("%+8.2f",this.get(i,j)); 
    84                                         } 
    85                                 } 
    86                                 else { 
     107                                } else { 
    87108                                        result = result + ("        "); 
    88109                                } 
    … …  
    92113                return result; 
    93114        } 
    94  
    95  
    96         @Override 
    97         public int size() { 
    98                 return size; 
    99         } 
    100115} 

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

    r1695 r1733  
    77import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; 
    88 
    9 public class EventTaskInstancesListGenerator extends DefaultTaskTraversingVisitor { 
    10          
    11                 private LinkedList<IEventTaskInstance> eventlist; 
    12                  
    13                 public LinkedList<IEventTaskInstance> getEventlist() { 
    14                         return eventlist; 
     9public class EventTaskInstancesListGenerator extends 
     10                DefaultTaskTraversingVisitor { 
     11 
     12        private LinkedList<IEventTaskInstance> eventlist; 
     13 
     14        public EventTaskInstancesListGenerator() { 
     15                eventlist = new LinkedList<IEventTaskInstance>(); 
     16        } 
     17 
     18        public LinkedList<IEventTaskInstance> getEventlist() { 
     19                return eventlist; 
     20        } 
     21 
     22        public void setEventlist(LinkedList<IEventTaskInstance> eventlist) { 
     23                this.eventlist = eventlist; 
     24        } 
     25 
     26        @Override 
     27        public void visit(IEventTask eventTask) { 
     28                if (eventTask.getInstances().size() > 0) { 
     29                        final IEventTaskInstance eti = (IEventTaskInstance) eventTask 
     30                                        .getInstances().iterator().next(); 
     31                        // System.out.println("Adding eventtaskinstance to list: " + eti); 
     32                        eventlist.add(eti); 
    1533                } 
     34        } 
    1635 
    17                 public void setEventlist(LinkedList<IEventTaskInstance> eventlist) { 
    18                         this.eventlist = eventlist; 
    19                 } 
    20  
    21                 @Override 
    22             public void visit(IEventTask eventTask) { 
    23                         if(eventTask.getInstances().size() > 0) { 
    24                                 IEventTaskInstance eti = (IEventTaskInstance) eventTask.getInstances().iterator().next(); 
    25                                 //System.out.println("Adding eventtaskinstance to list: " + eti); 
    26                                 eventlist.add(eti); 
    27                         } 
    28             } 
    29           
    30                 public EventTaskInstancesListGenerator() { 
    31                         eventlist = new LinkedList<IEventTaskInstance>();        
    32                 } 
    33          
    3436} 

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

    r1702 r1733  
    33public interface ITriangleMatrix { 
    44 
    5         //Increases the size 
     5        public abstract float get(int first, int second); 
     6 
     7        // Increases the size 
    68        public abstract void increaseSize(int count) throws Exception; 
    79 
    8         public abstract float get(int first, int second); 
     10        public abstract void initialize(float value); 
    911 
    1012        public abstract void set(int first, int second, float value); 
    1113 
    12         public abstract void initialize(float value); 
     14        public abstract int size(); 
    1315 
     16        @Override 
    1417        public abstract String toString(); 
    1518 
    16         public abstract int size(); 
    17  
    1819} 

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

    r1702 r1733  
    1515public class NearbySubstitutionMatrix implements SubstitutionMatrix { 
    1616 
    17         private int[] input1; 
    18         private int[] input2; 
    19         private int range; 
    20          
    21         public NearbySubstitutionMatrix(int[] input1,int[] input2, int range) { 
     17        private final int[] input1; 
     18        private final int[] input2; 
     19        private final int range; 
     20 
     21        public NearbySubstitutionMatrix(int[] input1, int[] input2, int range) { 
    2222                this.input1 = input1; 
    2323                this.input2 = input2; 
    2424                this.range = range; 
    2525        } 
    26          
    27         /* (non-Javadoc) 
    28          * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int) 
    29          */ 
    30         public float getScore(int pos1, int pos2) { 
    31                 int difference = Math.abs(input1[pos1]-input2[pos2]);  
    32                 if(difference < range) { 
    33                         return range-difference; 
    34                 } 
    35                 else { 
    36                         return -range; 
    37                 } 
    38         } 
    39  
    40  
    41         @Override 
    42         public float getGapPenalty() { 
    43                 return -range-1; 
    44         } 
    45  
    46  
    4726 
    4827        @Override 
    … …  
    5130 
    5231        @Override 
     32        public float getGapPenalty() { 
     33                return -range - 1; 
     34        } 
     35 
     36        /* 
     37         * (non-Javadoc) 
     38         *  
     39         * @see 
     40         * de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, 
     41         * int) 
     42         */ 
     43        @Override 
     44        public float getScore(int pos1, int pos2) { 
     45                final int difference = Math.abs(input1[pos1] - input2[pos2]); 
     46                if (difference < range) { 
     47                        return range - difference; 
     48                } else { 
     49                        return -range; 
     50                } 
     51        } 
     52 
     53        @Override 
    5354        public void update(LinkedList<ITask> newlyGeneratedTasks) { 
    5455        } 
    5556 
    56          
    57  
    5857} 

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

    r1711 r1733  
    1717import de.ugoe.cs.util.console.Console; 
    1818 
    19  
    20  
    21 public class ObjectDistanceSubstitionMatrix implements SubstitutionMatrix,Serializable { 
     19public class ObjectDistanceSubstitionMatrix implements SubstitutionMatrix, 
     20                Serializable { 
    2221 
    2322        /** 
    … …  
    2524         */ 
    2625        private static final long serialVersionUID = -4253258274617754083L; 
    27         private HashMap<Integer, Integer> idmapping; 
     26        private final HashMap<Integer, Integer> idmapping; 
    2827        private ITriangleMatrix matrix; 
    2928        private HashSet<ITask> uniqueTasks; 
    3029        private float gapPenalty; 
    3130        private int index = 0; 
    32         private HashMap<Integer, LinkedList<IEventTaskInstance>> etisOfTasks; 
     31        private final HashMap<Integer, LinkedList<IEventTaskInstance>> etisOfTasks; 
    3332        private boolean calculateNonTaskInstances = true; 
    3433        private int firstRoundMaxIndex = 0; 
    3534 
    36         private double positiveThreshold; 
    37  
    38         public ObjectDistanceSubstitionMatrix( 
    39                 float positiveThreshold, int gapPenalty, 
    40                 boolean calculateNonTaskInstances) { 
     35        private final double positiveThreshold; 
     36 
     37        public ObjectDistanceSubstitionMatrix(float positiveThreshold, 
     38                        int gapPenalty, boolean calculateNonTaskInstances) { 
    4139                this.positiveThreshold = positiveThreshold; 
    4240                idmapping = new HashMap<Integer, Integer>(); 
    … …  
    4543                this.calculateNonTaskInstances = calculateNonTaskInstances; 
    4644 
    47         } 
    48  
    49         public float getGapPenalty() { 
    50                 return gapPenalty; 
    51         } 
    52  
    53         public void setGapPenalty(float gapPenalty) { 
    54                 this.gapPenalty = gapPenalty; 
    55         } 
    56  
    57         //TODO: Merge this with updateEventTaskInstances 
    58         private void searchEventTaskInstances() { 
    59                 for (Iterator<ITask> it = uniqueTasks.iterator(); it.hasNext();) { 
    60                         ITask task = it.next(); 
    61                         if (!(task instanceof IEventTask)) { 
    62                                 EventTaskInstancesListGenerator etlg = new EventTaskInstancesListGenerator(); 
    63                                 task.accept(etlg); 
    64                                 LinkedList<IEventTaskInstance> eventTaskInstances = etlg 
    65                                                 .getEventlist(); 
    66                                 etisOfTasks.put(task.getId(), eventTaskInstances); 
    67                         } 
    68                 } 
    69         } 
    70          
    71         public void updateEventTaskInstances(LinkedList<ITask> newTasks){ 
    72                 for (Iterator<ITask> it = newTasks.iterator();it.hasNext();) { 
    73                         ITask task = it.next(); 
    74                         if (!(task instanceof IEventTask)) { 
    75                                 EventTaskInstancesListGenerator etlg = new EventTaskInstancesListGenerator(); 
    76                                 task.accept(etlg); 
    77                                 LinkedList<IEventTaskInstance> eventTaskInstances = etlg 
    78                                                 .getEventlist(); 
    79                                 etisOfTasks.put(task.getId(), eventTaskInstances); 
    80                         } 
    81                 } 
    82         } 
    83          
    84         //Just Calculate the distance between the new tasks and the matrix. 
    85         public void update(LinkedList<ITask> newTasks) { 
    86  
    87                 if (this.calculateNonTaskInstances) { 
    88                         try { 
    89                                 matrix.increaseSize(newTasks.size()); 
    90                                 System.out.println("Subsitution matrix size is now " + matrix.size()*(matrix.size()+1)/2); 
    91                                 Console.traceln(Level.INFO, "searching EventTasks in Tasks"); 
    92                         } catch (Exception e) { 
    93                                 Console.logException(e); 
    94                         } 
    95                         this.updateEventTaskInstances(newTasks); 
    96                         for(Iterator<ITask> it = newTasks.iterator();it.hasNext();) { 
    97                                 ITask task1 = it.next(); 
    98                                 for (Iterator<ITask> jt = uniqueTasks.iterator(); jt.hasNext();) { 
    99                                         ITask task2 = jt.next(); 
    100                                         computeDistance(task1,task2); 
    101                                 } 
    102                         } 
    103                 } 
    10445        } 
    10546 
    … …  
    11253                // We just need to the first instance here 
    11354                if (task1.getInstances().size() > 0) { 
    114                         ti1 = (ITaskInstance) task1.getInstances().iterator() 
    115                                         .next(); 
     55                        ti1 = task1.getInstances().iterator().next(); 
    11656                } 
    11757                if (task2.getInstances().size() > 0) { 
    118                         ti2 = (ITaskInstance) task2.getInstances().iterator() 
    119                                         .next(); 
     58                        ti2 = task2.getInstances().iterator().next(); 
    12059                } 
    12160                IEventTaskInstance eti1 = null; 
    12261                IEventTaskInstance eti2 = null; 
    12362 
    124                 if (ti1 instanceof IEventTaskInstance 
    125                                 && ti2 instanceof IEventTaskInstance) { 
     63                if ((ti1 instanceof IEventTaskInstance) 
     64                                && (ti2 instanceof IEventTaskInstance)) { 
    12665                        eti1 = (IEventTaskInstance) ti1; 
    12766                        index1 = getIndex(eti1); 
    … …  
    12968                        index2 = getIndex(eti2); 
    13069                        distance = distanceBetweenInstances(eti1, eti2); 
    131                 } else if (ti1 instanceof IEventTaskInstance 
     70                } else if ((ti1 instanceof IEventTaskInstance) 
    13271                                && !(ti2 instanceof IEventTaskInstance)) { 
    133                         task1 = ((ITaskInstance) ti1).getTask(); 
     72                        task1 = ti1.getTask(); 
    13473                        index2 = getIndex(task2); 
    13574                        eti1 = (IEventTaskInstance) ti1; 
    … …  
    13776                        distance = distanceBetweenTaskAndInstance(task2, eti1); 
    13877                } else if (!(ti1 instanceof IEventTaskInstance) 
    139                                 && ti2 instanceof IEventTaskInstance) { 
     78                                && (ti2 instanceof IEventTaskInstance)) { 
    14079                        index1 = getIndex(task1); 
    14180                        eti2 = (IEventTaskInstance) ti2; 
    … …  
    15291                matrix.set(index1, index2, distance); 
    15392        } 
    154          
    155          
     93 
     94        private float distanceBetweenInstances(IEventTaskInstance eti1, 
     95                        IEventTaskInstance eti2) { 
     96                final IGUIElement first = (IGUIElement) eti1.getEvent().getTarget(); 
     97                final IGUIElement second = (IGUIElement) eti2.getEvent().getTarget(); 
     98                float distance = -1 * AlignmentHelpers.distanceBetween(first, second); 
     99                distance += positiveThreshold; 
     100                return distance; 
     101        } 
     102 
     103        private float distanceBetweenTaskAndInstance(ITask task1, 
     104                        IEventTaskInstance eti1) { 
     105                if (this.calculateNonTaskInstances) { 
     106                        float tmpDistance = 0; 
     107                        // System.out.println(etisOfTasks); 
     108                        final LinkedList<IEventTaskInstance> eventTaskInstances = etisOfTasks 
     109                                        .get(task1.getId()); 
     110                        for (final Iterator<IEventTaskInstance> it = eventTaskInstances 
     111                                        .iterator(); it.hasNext();) { 
     112                                final IEventTaskInstance eti2 = it.next(); 
     113                                // int taskId1 = eti1.getTask().getId(); 
     114                                // int taskId2 = eti2.getTask().getId(); 
     115                                // if (scoreExists(taskId1, taskId2)) { 
     116                                // tmpDistance += getScore(taskId1, taskId2); 
     117                                // } else { 
     118                                final float dist = distanceBetweenInstances(eti1, eti2); 
     119                                matrix.set(getIndex(eti1), getIndex(eti2), dist); 
     120                                tmpDistance += dist; 
     121                                // } 
     122                        } 
     123                        return tmpDistance / eventTaskInstances.size(); 
     124                } else { 
     125                        return 0; 
     126                } 
     127        } 
     128 
     129        private float distanceBetweenTasks(ITask task1, ITask task2) { 
     130                if (this.calculateNonTaskInstances) { 
     131                        final LinkedList<IEventTaskInstance> eventTaskInstances = etisOfTasks 
     132                                        .get(task1.getId()); 
     133                        float tmpDistance = 0; 
     134                        for (final Iterator<IEventTaskInstance> it = eventTaskInstances 
     135                                        .iterator(); it.hasNext();) { 
     136                                final IEventTaskInstance eti1 = it.next(); 
     137                                tmpDistance += distanceBetweenTaskAndInstance(task2, eti1); 
     138                        } 
     139 
     140                        return tmpDistance / eventTaskInstances.size(); 
     141                } else { 
     142                        return 0; 
     143                } 
     144        } 
     145 
     146        @Override 
    156147        public void generate(HashSet<ITask> uniqueTasks) { 
    157148                this.uniqueTasks = uniqueTasks; 
    … …  
    160151                        Console.traceln(Level.INFO, "searching EventTasks in Tasks"); 
    161152                        searchEventTaskInstances(); 
    162                 } 
    163                 else{ 
    164                         matrix = new StaticTriangleMatrix(uniqueTasks.size()+1); 
     153                } else { 
     154                        matrix = new StaticTriangleMatrix(uniqueTasks.size() + 1); 
    165155                } 
    166156                matrix.initialize(0); 
    167                        
    168                 int count=0; 
    169                 int size=uniqueTasks.size(); 
    170                 for (Iterator<ITask> it = uniqueTasks.iterator(); it.hasNext();) { 
    171                         ITask task1 = it.next(); 
     157 
     158                int count = 0; 
     159                final int size = uniqueTasks.size(); 
     160                for (final Iterator<ITask> it = uniqueTasks.iterator(); it.hasNext();) { 
     161                        final ITask task1 = it.next(); 
    172162                        count++; 
    173                         if((count%(size/100)==0)) { 
    174                                 Console.traceln(Level.INFO,(Math.round((float) count/size*100))+ "%"); 
    175                         } 
    176                         for (Iterator<ITask> jt = uniqueTasks.iterator(); jt.hasNext();) { 
    177                                 ITask task2 = jt.next(); 
    178                                 computeDistance(task1,task2); 
    179                         } 
    180                 } 
    181                 this.firstRoundMaxIndex=index; 
    182         } 
    183          
    184                  
    185  
    186          
    187          
    188  
    189         private float distanceBetweenTaskAndInstance(ITask task1, 
    190                         IEventTaskInstance eti1) { 
    191                 if (this.calculateNonTaskInstances) { 
    192                         float tmpDistance = 0; 
    193                         //System.out.println(etisOfTasks); 
    194                         LinkedList<IEventTaskInstance> eventTaskInstances = etisOfTasks 
    195                                         .get(task1.getId()); 
    196                         for (Iterator<IEventTaskInstance> it = eventTaskInstances 
    197                                         .iterator(); it.hasNext();) { 
    198                                 IEventTaskInstance eti2 = it.next(); 
    199                                 //int taskId1 = eti1.getTask().getId(); 
    200                                 //int taskId2 = eti2.getTask().getId(); 
    201                                 //if (scoreExists(taskId1, taskId2)) { 
    202                                 //      tmpDistance += getScore(taskId1, taskId2); 
    203                                 //} else { 
    204                                         float dist = distanceBetweenInstances(eti1, eti2); 
    205                                         matrix.set(getIndex(eti1), getIndex(eti2), dist); 
    206                                         tmpDistance += dist; 
    207                                 //} 
    208                         } 
    209                         return tmpDistance / eventTaskInstances.size(); 
    210                 } else { 
    211                         return 0; 
    212                 } 
    213         } 
    214  
    215         //public boolean scoreExists(int id, int id2) { 
    216                 //return idmapping.containsKey(id) && idmapping.containsKey(id2); 
    217         //      return false; 
    218         //} 
    219  
    220         private float distanceBetweenTasks(ITask task1, ITask task2) { 
    221                 if (this.calculateNonTaskInstances) { 
    222                         LinkedList<IEventTaskInstance> eventTaskInstances = etisOfTasks 
    223                                         .get(task1.getId()); 
    224                         float tmpDistance = 0; 
    225                         for (Iterator<IEventTaskInstance> it = eventTaskInstances 
    226                                         .iterator(); it.hasNext();) { 
    227                                 IEventTaskInstance eti1 = it.next(); 
    228                                 tmpDistance += distanceBetweenTaskAndInstance(task2, eti1); 
    229                         } 
    230  
    231                         return tmpDistance / eventTaskInstances.size(); 
    232                 } else { 
    233                         return 0; 
    234                 } 
    235         } 
    236  
    237         synchronized private int getIndex(ITask task) { 
    238                 int tempindex = -1; 
    239  
    240                 if (!idmapping.containsKey(task.getId())) { 
    241                          
    242                         idmapping.put(task.getId(), index); 
    243                         tempindex = index; 
    244                         index++; 
    245                 } else { 
    246                         tempindex = idmapping.get(task.getId()); 
    247                 } 
    248  
    249                 return tempindex; 
     163                        if (((count % (size / 100)) == 0)) { 
     164                                Console.traceln(Level.INFO, 
     165                                                (Math.round(((float) count / size) * 100)) + "%"); 
     166                        } 
     167                        for (final Iterator<ITask> jt = uniqueTasks.iterator(); jt 
     168                                        .hasNext();) { 
     169                                final ITask task2 = jt.next(); 
     170                                computeDistance(task1, task2); 
     171                        } 
     172                } 
     173                this.firstRoundMaxIndex = index; 
     174        } 
     175 
     176        @Override 
     177        public float getGapPenalty() { 
     178                return gapPenalty; 
    250179        } 
    251180 
    … …  
    260189                } 
    261190                return tempindex; 
     191        } 
     192 
     193        synchronized private int getIndex(ITask task) { 
     194                int tempindex = -1; 
     195 
     196                if (!idmapping.containsKey(task.getId())) { 
     197 
     198                        idmapping.put(task.getId(), index); 
     199                        tempindex = index; 
     200                        index++; 
     201                } else { 
     202                        tempindex = idmapping.get(task.getId()); 
     203                } 
     204 
     205                return tempindex; 
     206        } 
     207 
     208        // public boolean scoreExists(int id, int id2) { 
     209        // return idmapping.containsKey(id) && idmapping.containsKey(id2); 
     210        // return false; 
     211        // } 
     212 
     213        @Override 
     214        public float getScore(int taskId1, int taskId2) { 
     215                if ((taskId1 == Constants.GAP_SYMBOL) 
     216                                || (taskId1 == Constants.UNMATCHED_SYMBOL) 
     217                                || (taskId2 == Constants.GAP_SYMBOL) 
     218                                || (taskId2 == Constants.UNMATCHED_SYMBOL)) { 
     219                        return 0; 
     220                } else if ((this.calculateNonTaskInstances == false) 
     221                                && ((taskId1 > this.firstRoundMaxIndex) || (taskId2 > this.firstRoundMaxIndex))) { 
     222                        return 0; 
     223                } else { 
     224                        final Integer first = idmapping.get(taskId1); 
     225                        final Integer second = idmapping.get(taskId2); 
     226                        return matrix.get(first, second); 
     227                } 
     228 
     229        } 
     230 
     231        // TODO: Merge this with updateEventTaskInstances 
     232        private void searchEventTaskInstances() { 
     233                for (final Iterator<ITask> it = uniqueTasks.iterator(); it.hasNext();) { 
     234                        final ITask task = it.next(); 
     235                        if (!(task instanceof IEventTask)) { 
     236                                final EventTaskInstancesListGenerator etlg = new EventTaskInstancesListGenerator(); 
     237                                task.accept(etlg); 
     238                                final LinkedList<IEventTaskInstance> eventTaskInstances = etlg 
     239                                                .getEventlist(); 
     240                                etisOfTasks.put(task.getId(), eventTaskInstances); 
     241                        } 
     242                } 
     243        } 
     244 
     245        public void setGapPenalty(float gapPenalty) { 
     246                this.gapPenalty = gapPenalty; 
    262247        }; 
    263248 
    264         private float distanceBetweenInstances(IEventTaskInstance eti1, 
    265                         IEventTaskInstance eti2) { 
    266                 IGUIElement first = (IGUIElement) eti1.getEvent().getTarget(); 
    267                 IGUIElement second = (IGUIElement) eti2.getEvent().getTarget(); 
    268                 float distance = -1 * AlignmentHelpers.distanceBetween(first, second); 
    269                 distance += positiveThreshold; 
    270                 return distance; 
    271         } 
    272  
     249        @Override 
    273250        public String toString() { 
    274251                return matrix.toString(); 
    275252        } 
    276253 
    277         public float getScore(int taskId1, int taskId2) { 
    278                 if (taskId1 == Constants.GAP_SYMBOL 
    279                                 || taskId1 == Constants.UNMATCHED_SYMBOL 
    280                                 || taskId2 == Constants.GAP_SYMBOL 
    281                                 || taskId2 == Constants.UNMATCHED_SYMBOL) { 
    282                         return 0; 
    283                 } else if(this.calculateNonTaskInstances==false &&       
    284                                 (taskId1>this.firstRoundMaxIndex 
    285                                 || taskId2>this.firstRoundMaxIndex)) { 
    286                         return 0; 
    287                 } else { 
    288                         Integer first = idmapping.get(taskId1); 
    289                         Integer second = idmapping.get(taskId2); 
    290                         return matrix.get(first, second); 
    291                 } 
    292  
     254        // Just Calculate the distance between the new tasks and the matrix. 
     255        @Override 
     256        public void update(LinkedList<ITask> newTasks) { 
     257 
     258                if (this.calculateNonTaskInstances) { 
     259                        try { 
     260                                matrix.increaseSize(newTasks.size()); 
     261                                System.out.println("Subsitution matrix size is now " 
     262                                                + ((matrix.size() * (matrix.size() + 1)) / 2)); 
     263                                Console.traceln(Level.INFO, "searching EventTasks in Tasks"); 
     264                        } catch (final Exception e) { 
     265                                Console.logException(e); 
     266                        } 
     267                        this.updateEventTaskInstances(newTasks); 
     268                        for (final Iterator<ITask> it = newTasks.iterator(); it.hasNext();) { 
     269                                final ITask task1 = it.next(); 
     270                                for (final Iterator<ITask> jt = uniqueTasks.iterator(); jt 
     271                                                .hasNext();) { 
     272                                        final ITask task2 = jt.next(); 
     273                                        computeDistance(task1, task2); 
     274                                } 
     275                        } 
     276                } 
     277        } 
     278 
     279        public void updateEventTaskInstances(LinkedList<ITask> newTasks) { 
     280                for (final Iterator<ITask> it = newTasks.iterator(); it.hasNext();) { 
     281                        final ITask task = it.next(); 
     282                        if (!(task instanceof IEventTask)) { 
     283                                final EventTaskInstancesListGenerator etlg = new EventTaskInstancesListGenerator(); 
     284                                task.accept(etlg); 
     285                                final LinkedList<IEventTaskInstance> eventTaskInstances = etlg 
     286                                                .getEventlist(); 
     287                                etisOfTasks.put(task.getId(), eventTaskInstances); 
     288                        } 
     289                } 
    293290        } 
    294291} 

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

    r1707 r1733  
    33import java.io.Serializable; 
    44 
    5 public class StaticTriangleMatrix implements ITriangleMatrix,Serializable { 
    6          
     5public class StaticTriangleMatrix implements ITriangleMatrix, Serializable { 
     6 
    77        /** 
    88         *  
    99         */ 
    1010        private static final long serialVersionUID = 7599542322424894866L; 
    11         private float[] matrix; 
     11        private final float[] matrix; 
    1212        protected int size; 
    13          
    14          
     13 
    1514        public StaticTriangleMatrix(int size) { 
    1615                this.size = size; 
    17                 matrix = new float [size*(size+1)/2]; 
    18         } 
    19          
    20         public float get(int first, int second) { 
    21                 int row = Math.min(first, second); 
    22                 int col = Math.max(first, second); 
    23                 return matrix[row*size-(row*(row+1)/2 - (size-col))]; 
    24                  
    25         } 
    26          
    27         public void set(int first, int second, float value) { 
    28                 int row = Math.min(first, second); 
    29                 int col = Math.max(first, second); 
    30                 matrix[row*size-(row*(row+1)/2 - (size-col))] = value; 
     16                matrix = new float[(size * (size + 1)) / 2]; 
    3117        } 
    3218 
     19        @Override 
     20        public float get(int first, int second) { 
     21                final int row = Math.min(first, second); 
     22                final int col = Math.max(first, second); 
     23                return matrix[(row * size) - (((row * (row + 1)) / 2) - (size - col))]; 
     24 
     25        } 
     26 
     27        @Override 
     28        public void increaseSize(int count) throws Exception { 
     29                throw new Exception( 
     30                                "Cannot call this function on this implementation of ITriangle Matrix"); 
     31 
     32        } 
     33 
     34        @Override 
    3335        public void initialize(float value) { 
    34                 for (int i=0; i < matrix.length; i++) { 
     36                for (int i = 0; i < matrix.length; i++) { 
    3537                        matrix[i] = value; 
    3638                } 
    3739        } 
    38          
    3940 
    40          
     41        @Override 
     42        public void set(int first, int second, float value) { 
     43                final int row = Math.min(first, second); 
     44                final int col = Math.max(first, second); 
     45                matrix[(row * size) - (((row * (row + 1)) / 2) - (size - col))] = value; 
     46        } 
     47 
     48        @Override 
     49        public int size() { 
     50                return size; 
     51        } 
     52 
     53        @Override 
    4154        public String toString() { 
    4255                String result = ""; 
    4356                for (int i = 0; i < size; i++) { 
    44                         for(int j = 0; j< size; j++) { 
    45                                 if(i<j) { 
    46                                         if(Float.isInfinite(this.get(i,j))) { 
     57                        for (int j = 0; j < size; j++) { 
     58                                if (i < j) { 
     59                                        if (Float.isInfinite(this.get(i, j))) { 
    4760                                                result = result + " -------"; 
     61                                        } else { 
     62                                                result = result 
     63                                                                + String.format("%+8.2f", this.get(i, j)); 
    4864                                        } 
    49                                         else { 
    50                                                 result = result + String.format("%+8.2f",this.get(i,j)); 
    51                                         } 
    52                                 } 
    53                                 else { 
     65                                } else { 
    5466                                        result = result + ("        "); 
    5567                                } 
    … …  
    5971                return result; 
    6072        } 
    61  
    62         @Override 
    63         public void increaseSize(int count) throws Exception { 
    64                 throw new Exception("Cannot call this function on this implementation of ITriangle Matrix"); 
    65                  
    66         } 
    67  
    68         @Override 
    69         public int size() { 
    70                 return size; 
    71         } 
    7273} 

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

    r1702 r1733  
    66import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; 
    77 
     8public interface SubstitutionMatrix { 
    89 
     10        public void generate(HashSet<ITask> uniqueTasks); 
    911 
    10 public interface SubstitutionMatrix { 
    11          
     12        public float getGapPenalty(); 
    1213 
    1314        public float getScore(int pos1, int pos2); 
    1415 
    15         public float getGapPenalty(); 
    16  
    17         public void generate(HashSet<ITask> uniqueTasks); 
    18          
    1916        public void update(LinkedList<ITask> newlyGeneratedTasks); 
    2017 
    21          
    2218} 

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

    r1702 r1733  
    11package de.ugoe.cs.autoquest.tasktrees.alignment.matrix; 
    2  
    3  
    42 
    53public class UPGMAMatrix extends StaticTriangleMatrix { 
    … …  
    97        } 
    108 
     9        @Override 
    1110        public int size() { 
    1211                return size; 
    1312        } 
    1413 
     14        @Override 
    1515        public String toString() { 
    1616                String result = ""; 
    … …  
    1919                } 
    2020                result += "\n"; 
    21                  
     21 
    2222                for (int i = 0; i < size; i++) { 
    23                         for(int j = 0; j< size; j++) { 
    24                                 if(i<j) { 
    25                                         if(Double.isInfinite(this.get(i,j))) { 
     23                        for (int j = 0; j < size; j++) { 
     24                                if (i < j) { 
     25                                        if (Double.isInfinite(this.get(i, j))) { 
    2626                                                result = result + " -------"; 
     27                                        } else { 
     28                                                result = result 
     29                                                                + String.format("%+8.2f", this.get(i, j)); 
    2730                                        } 
    28                                         else { 
    29                                                 result = result + String.format("%+8.2f",this.get(i,j)); 
    30                                         } 
    31                                 } 
    32                                 else { 
     31                                } else { 
    3332                                        result = result + ("        "); 
    3433                                } 
    … …  
    3938        } 
    4039 
    41          
    42  
    4340} 
Note: See TracChangeset for help on using the changeset viewer.