Ignore:
Timestamp:
08/17/12 09:05:19 (12 years ago)
Author:
sherbold
Message:
  • adapted to quest coding style
Location:
trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/DrawFromAllSequencesGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    1718/** 
    1819 * <p> 
    19  * Generates a test suite by drawing from all possible sequences of a fixed 
    20  * length according to the probabilities of the sequences in a 
    21  * {@link IStochasticProcess}. 
     20 * Generates a test suite by drawing from all possible sequences of a fixed length according to the 
     21 * probabilities of the sequences in a {@link IStochasticProcess}. 
    2222 * </p> 
    2323 *  
    … …  
    2727public class DrawFromAllSequencesGenerator { 
    2828 
    29         /** 
    30         * <p> 
    31         * Number of sequences in the test suite. 
    32         * </p> 
    33         */ 
    34         private final int numSequences; 
     29    /** 
     30    * <p> 
     31    * Number of sequences in the test suite. 
     32    * </p> 
     33    */ 
     34    private final int numSequences; 
    3535 
    36         /** 
    37         * <p> 
    38         * Minimal length of a test sequence. 
    39         * </p> 
    40         */ 
    41         private final int minLength; 
     36    /** 
     37    * <p> 
     38    * Minimal length of a test sequence. 
     39    * </p> 
     40    */ 
     41    private final int minLength; 
    4242 
    43         /** 
    44         * <p> 
    45         * Maximal length of a test sequence. 
    46         * </p> 
    47         */ 
    48         private final int maxLength; 
     43    /** 
     44    * <p> 
     45    * Maximal length of a test sequence. 
     46    * </p> 
     47    */ 
     48    private final int maxLength; 
    4949 
    50         /** 
    51          * <p> 
    52          * In case this member is true, only test cases that end in the global end 
    53          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    54          * can be any event. 
    55          * </p> 
    56          */ 
    57         private final boolean validEnd; 
     50    /** 
     51     * <p> 
     52     * In case this member is true, only test cases that end in the global end event 
     53     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     54     * </p> 
     55     */ 
     56    private final boolean validEnd; 
    5857 
    59         /** 
    60         * <p> 
    61          * If this member is true, the generated test suite contains all possible 
    62          * sequences and {@link #numSequences} is ignored. 
    63         * </p> 
    64         */ 
    65         private final boolean generateAll; 
     58    /** 
     59    * <p> 
     60     * If this member is true, the generated test suite contains all possible sequences and 
     61     * {@link #numSequences} is ignored. 
     62    * </p> 
     63    */ 
     64    private final boolean generateAll; 
    6665 
    67         /** 
    68          * <p> 
    69          * Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the 
    70          * validity of the parameters: 
    71          * <ul> 
    72          * <li>numSequences must at least be 1 
    73          * <li>maxLength must at least be 1 
    74          * <li>minLength must be less than or equal to maxLength 
    75          * </ul> 
    76          * If one of these conditions is violated an 
    77          * {@link InvalidParameterException} is thrown. 
    78          * </p> 
    79          *  
    80          * @param numSequences 
    81          *            number of sequences desired for the test suite 
    82          * @param minLength 
    83          *            minimal length of a test sequence 
    84          * @param maxLength 
    85          *            maximal length of a test sequence 
    86          * @param validEnd 
    87          *            defines if test cases have to end with the global end event 
    88          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    89          * @param generateAll 
    90          *            if this parameter is true, the test suite contains all 
    91          *            possible sequences and numSequences is ignored 
    92          */ 
    93         public DrawFromAllSequencesGenerator(int numSequences, int minLength, 
    94                         int maxLength, boolean validEnd, boolean generateAll) { 
    95                 // check validity of the parameters 
    96                 if (numSequences < 1) { 
    97                         throw new InvalidParameterException( 
    98                                         "number of sequences must be at least 1 but is " 
    99                                                         + numSequences); 
    100                 } 
    101                 if (maxLength < 1) { 
    102                         throw new InvalidParameterException( 
    103                                         "maximal allowed length of test cases must be at least 1 but is " 
    104                                                         + maxLength); 
    105                 } 
    106                 if (minLength > maxLength) { 
    107                         throw new InvalidParameterException( 
    108                                         "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " 
    109                                                         + minLength + " ; max length: " + maxLength + ")"); 
    110                 } 
    111                 this.numSequences = numSequences; 
    112                 this.minLength = minLength; 
    113                 this.maxLength = maxLength; 
    114                 this.validEnd = validEnd; 
    115                 this.generateAll = generateAll; 
    116         } 
     66    /** 
     67     * <p> 
     68     * Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the validity of the 
     69     * parameters: 
     70     * <ul> 
     71     * <li>numSequences must at least be 1 
     72     * <li>maxLength must at least be 1 
     73     * <li>minLength must be less than or equal to maxLength 
     74     * </ul> 
     75     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     76     * </p> 
     77     *  
     78     * @param numSequences 
     79     *            number of sequences desired for the test suite 
     80     * @param minLength 
     81     *            minimal length of a test sequence 
     82     * @param maxLength 
     83     *            maximal length of a test sequence 
     84     * @param validEnd 
     85     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     86     *            (see {@link #validEnd}) 
     87     * @param generateAll 
     88     *            if this parameter is true, the test suite contains all possible sequences and 
     89     *            numSequences is ignored 
     90     */ 
     91    public DrawFromAllSequencesGenerator(int numSequences, 
     92                                         int minLength, 
     93                                         int maxLength, 
     94                                         boolean validEnd, 
     95                                         boolean generateAll) 
     96    { 
     97        // check validity of the parameters 
     98        if (numSequences < 1) { 
     99            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     100                numSequences); 
     101        } 
     102        if (maxLength < 1) { 
     103            throw new InvalidParameterException( 
     104                                                "maximal allowed length of test cases must be at least 1 but is " + 
     105                                                    maxLength); 
     106        } 
     107        if (minLength > maxLength) { 
     108            throw new InvalidParameterException( 
     109                                                "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " + 
     110                                                    minLength + " ; max length: " + maxLength + ")"); 
     111        } 
     112        this.numSequences = numSequences; 
     113        this.minLength = minLength; 
     114        this.maxLength = maxLength; 
     115        this.validEnd = validEnd; 
     116        this.generateAll = generateAll; 
     117    } 
    117118 
    118         /** 
    119          * <p> 
    120          * Generates a test suite by drawing from all possible sequences with valid 
    121          * lengths. 
    122          * </p> 
    123          *  
    124          * @param model 
    125          *            model used to determine the probability of each possible 
    126          *            sequence 
    127          * @return the test suite 
    128          */ 
    129         public Collection<List<Event>> generateTestSuite( 
    130                         IStochasticProcess model) { 
    131                 if (model == null) { 
    132                         throw new InvalidParameterException("model must not be null!"); 
    133                 } 
     119    /** 
     120     * <p> 
     121     * Generates a test suite by drawing from all possible sequences with valid lengths. 
     122     * </p> 
     123     *  
     124     * @param model 
     125     *            model used to determine the probability of each possible sequence 
     126     * @return the test suite 
     127     */ 
     128    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     129        if (model == null) { 
     130            throw new InvalidParameterException("model must not be null!"); 
     131        } 
    134132 
    135                 Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
    136                 for (int length = minLength; length <= maxLength; length++) { 
    137                         if (validEnd) { 
    138                                 sequences.addAll(model.generateValidSequences(length + 2)); 
    139                         } else { 
    140                                 sequences.addAll(model.generateSequences(length + 1, true)); 
    141                         } 
    142                 } 
    143                 Console.traceln("" + sequences.size() + " possible"); 
    144                 if (!generateAll && numSequences < sequences.size()) { 
    145                         List<Double> probabilities = new ArrayList<Double>(sequences.size()); 
    146                         double probSum = 0.0; 
    147                         for (List<Event> sequence : sequences) { 
    148                                 double prob = model.getProbability(sequence); 
    149                                 probabilities.add(prob); 
    150                                 probSum += prob; 
    151                         } 
    152                         Set<Integer> drawnSequences = new HashSet<Integer>(numSequences); 
    153                         Random r = new Random(); 
    154                         while (drawnSequences.size() < numSequences) { 
    155                                 double randVal = r.nextDouble() * probSum; 
    156                                 double sum = 0.0d; 
    157                                 int index = -1; 
    158                                 while (sum < randVal) { 
    159                                         index++; 
    160                                         double currentProb = probabilities.get(index); 
    161                                         sum += currentProb; 
    162                                 } 
    163                                 if (!drawnSequences.contains(index)) { 
    164                                         drawnSequences.add(index); 
    165                                         probSum -= probabilities.get(index); 
    166                                         probabilities.set(index, 0.0d); 
    167                                 } 
    168                         } 
    169                         Collection<List<Event>> retainedSequences = new LinkedList<List<Event>>(); 
    170                         int index = 0; 
    171                         for (List<Event> sequence : sequences) { 
    172                                 if (drawnSequences.contains(index)) { 
    173                                         retainedSequences.add(sequence); 
    174                                 } 
    175                                 index++; 
    176                         } 
    177                         sequences = retainedSequences; 
    178                 } 
    179                 return sequences; 
    180         } 
     133        Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
     134        for (int length = minLength; length <= maxLength; length++) { 
     135            if (validEnd) { 
     136                sequences.addAll(model.generateValidSequences(length + 2)); 
     137            } 
     138            else { 
     139                sequences.addAll(model.generateSequences(length + 1, true)); 
     140            } 
     141        } 
     142        Console.traceln("" + sequences.size() + " possible"); 
     143        if (!generateAll && numSequences < sequences.size()) { 
     144            List<Double> probabilities = new ArrayList<Double>(sequences.size()); 
     145            double probSum = 0.0; 
     146            for (List<Event> sequence : sequences) { 
     147                double prob = model.getProbability(sequence); 
     148                probabilities.add(prob); 
     149                probSum += prob; 
     150            } 
     151            Set<Integer> drawnSequences = new HashSet<Integer>(numSequences); 
     152            Random r = new Random(); 
     153            while (drawnSequences.size() < numSequences) { 
     154                double randVal = r.nextDouble() * probSum; 
     155                double sum = 0.0d; 
     156                int index = -1; 
     157                while (sum < randVal) { 
     158                    index++; 
     159                    double currentProb = probabilities.get(index); 
     160                    sum += currentProb; 
     161                } 
     162                if (!drawnSequences.contains(index)) { 
     163                    drawnSequences.add(index); 
     164                    probSum -= probabilities.get(index); 
     165                    probabilities.set(index, 0.0d); 
     166                } 
     167            } 
     168            Collection<List<Event>> retainedSequences = new LinkedList<List<Event>>(); 
     169            int index = 0; 
     170            for (List<Event> sequence : sequences) { 
     171                if (drawnSequences.contains(index)) { 
     172                    retainedSequences.add(sequence); 
     173                } 
     174                index++; 
     175            } 
     176            sequences = retainedSequences; 
     177        } 
     178        return sequences; 
     179    } 
    181180 
    182181} 

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    1516/** 
    1617 * <p> 
    17  * Generates a test suite with a hybrid approach that is a mixture of random 
    18  * walks and drawing from all possible sequences. 
     18 * Generates a test suite with a hybrid approach that is a mixture of random walks and drawing from 
     19 * all possible sequences. 
    1920 * </p> 
    2021 *  
    … …  
    2425public class HybridGenerator { 
    2526 
    26         /** 
    27          * <p> 
    28          * Number of sequences in the test suite. 
    29          * </p> 
    30          */ 
    31         private final int numSequences; 
    32  
    33         /** 
    34          * <p> 
    35          * Length of a test sequence. 
    36          * </p> 
    37          */ 
    38         private final int length; 
    39  
    40         /** 
    41          * <p> 
    42          * Maximal length where it is possible to generate all sequences and draw 
    43          * from them. 
    44          * </p> 
    45          */ 
    46         private final int maxLengthAll; 
    47  
    48         /** 
    49          * <p> 
    50          * In case this member is true, only test cases that end in the global end 
    51          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    52          * can be any event. 
    53          * </p> 
    54          */ 
    55         private final boolean validEnd; 
    56  
    57         /** 
    58          * <p> 
    59          * Constructor. Creates a new HybridGenerator and ensures the validity of 
    60          * the parameters: 
    61          * <ul> 
    62          * <li>numSequences must at least be 1 
    63          * <li>length must be at least 1 
    64          * </ul> 
    65          * If one of these conditions is violated an 
    66          * {@link InvalidParameterException} is thrown. 
    67          * </p> 
    68          *  
    69          * @param numSequences 
    70          *            number of sequences desired for the test suite 
    71          * @param length 
    72          *            length of a test sequence 
    73          * @param maxLengthAll 
    74          *            maximal length where it is possible to generate all sequences 
    75          *            and draw from them 
    76          * @param validEnd 
    77          *            defines if test cases have to end with the global end event 
    78          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    79          */ 
    80         public HybridGenerator(int numSequences, int length, int maxLengthAll, 
    81                         boolean validEnd) { 
    82                 // check validity of the parameters 
    83                 if (numSequences < 1) { 
    84                         throw new InvalidParameterException( 
    85                                         "number of sequences must be at least 1 but is " 
    86                                                         + numSequences); 
    87                 } 
    88                 if (length < 1) { 
    89                         throw new InvalidParameterException( 
    90                                         "length of test cases must be at least 1 but is " + length); 
    91                 } 
    92                 this.numSequences = numSequences; 
    93                 this.length = length; 
    94                 this.maxLengthAll = maxLengthAll; 
    95                 this.validEnd = validEnd; 
    96         } 
    97  
    98         /** 
    99          * <p> 
    100          * Generates a test suite with a hybrid approach that is a mixture of random 
    101          * walks and drawing from all possible sequences 
    102          * </p> 
    103          *  
    104          * @param model 
    105          *            model used to determine the probability of each possible 
    106          *            sequence 
    107          * @return the test suite 
    108          */ 
    109         public Collection<List<Event>> generateTestSuite( 
    110                         IStochasticProcess model) { 
    111                 if (model == null) { 
    112                         throw new InvalidParameterException("model must not be null!"); 
    113                 } 
    114                  
    115                 Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
    116  
    117                 List<List<Event>> seqsTmp = new ArrayList<List<Event>>( 
    118                                 model.generateSequences(maxLengthAll + 1, true)); 
    119  
    120                 Console.traceln("" + seqsTmp.size() + " of length " + maxLengthAll 
    121                                 + " possible"); 
    122                 List<Double> probabilities = new ArrayList<Double>(seqsTmp.size()); 
    123                 double probSum = 0.0; 
    124                 for (List<Event> sequence : seqsTmp) { 
    125                         double prob = model.getProbability(sequence); 
    126                         probabilities.add(prob); 
    127                         probSum += prob; 
    128                 } 
    129  
    130                 Random r = new Random(); 
    131                 int j = 0; 
    132                 while (sequences.size() < numSequences && j <= numSequences * 100) { 
    133                         j++; 
    134                         double randVal = r.nextDouble() * probSum; 
    135                         double sum = 0.0d; 
    136                         int index = -1; 
    137                         while (sum < randVal) { 
    138                                 index++; 
    139                                 double currentProb = probabilities.get(index); 
    140                                 sum += currentProb; 
    141                         } 
    142                         List<Event> seqTmp = seqsTmp.get(index); 
    143                         if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) { 
    144                                 List<Event> sequence; 
    145                                 if (validEnd) { 
    146                                         sequence = finishSequence(seqTmp, model, length + 2, 
    147                                                         validEnd); 
    148                                         if( sequence!= null && sequence.size()!=length+2 ) { 
    149                                                 sequence = null; 
    150                                         } 
    151                                 } else { 
    152                                         sequence = finishSequence(seqTmp, model, length + 1, 
    153                                                         validEnd); 
    154                                         if( sequence!= null && sequence.size()!=length+1 ) { 
    155                                                 sequence = null; 
    156                                         } 
    157                                 } 
    158                                 if( sequence!=null ) { 
    159                                         sequences.add(sequence); 
    160                                 } 
    161                         } 
    162                 } 
    163                  
    164                 return sequences; 
    165         } 
    166  
    167         /** 
    168          * <p> 
    169          * Finishes a sequence with a random walk. 
    170          * </p> 
    171          *  
    172          * @param sequence 
    173          *            sequence to be finished 
    174          * @param model 
    175          *            model used for the random walk 
    176          * @param length 
    177          *            desired length of the sequence 
    178          * @param validEnd 
    179          *            if the sequence should end in {@link Event#ENDEVENT}. 
    180          * @return finished sequence of the desired length 
    181          */ 
    182         private List<Event> finishSequence( 
    183                         List<Event> sequence, IStochasticProcess model, 
    184                         int length, boolean validEnd) { 
    185                 Random r = new Random(); 
    186                 boolean endFound = false; 
    187                 List<Event> sequenceCopy = new LinkedList<Event>(sequence); 
    188                 final int maxIter = 30000; 
    189                 int iter = 0; 
    190                 while (!endFound && iter < maxIter) { 
    191                         iter++; 
    192                         sequenceCopy = new LinkedList<Event>(sequence); 
    193                         while (!endFound && sequenceCopy.size() <= length) { 
    194                                 double randVal = r.nextDouble(); 
    195                                 double probSum = 0.0; 
    196                                 for (Event symbol : model.getEvents()) { 
    197                                         probSum += model.getProbability(sequenceCopy, symbol); 
    198                                         if (probSum >= randVal) { 
    199                                                 if (!(Event.STARTEVENT.equals(symbol) || (!validEnd && Event.ENDEVENT 
    200                                                                 .equals(symbol)))) { 
    201                                                         // only add the symbol the sequence if it is not 
    202                                                         // START 
    203                                                         // or END 
    204                                                         sequenceCopy.add(symbol); 
    205                                                 } 
    206                                                 endFound = Event.ENDEVENT.equals(symbol) 
    207                                                                 || (!validEnd && sequenceCopy.size() == length); 
    208                                                 break; 
    209                                         } 
    210                                 } 
    211                         } 
    212                 } 
    213                 if (iter == maxIter) { 
    214                         return null; 
    215                 } 
    216                 return sequenceCopy; 
    217         } 
     27    /** 
     28     * <p> 
     29     * Number of sequences in the test suite. 
     30     * </p> 
     31     */ 
     32    private final int numSequences; 
     33 
     34    /** 
     35     * <p> 
     36     * Length of a test sequence. 
     37     * </p> 
     38     */ 
     39    private final int length; 
     40 
     41    /** 
     42     * <p> 
     43     * Maximal length where it is possible to generate all sequences and draw from them. 
     44     * </p> 
     45     */ 
     46    private final int maxLengthAll; 
     47 
     48    /** 
     49     * <p> 
     50     * In case this member is true, only test cases that end in the global end event 
     51     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     52     * </p> 
     53     */ 
     54    private final boolean validEnd; 
     55 
     56    /** 
     57     * <p> 
     58     * Constructor. Creates a new HybridGenerator and ensures the validity of the parameters: 
     59     * <ul> 
     60     * <li>numSequences must at least be 1 
     61     * <li>length must be at least 1 
     62     * </ul> 
     63     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     64     * </p> 
     65     *  
     66     * @param numSequences 
     67     *            number of sequences desired for the test suite 
     68     * @param length 
     69     *            length of a test sequence 
     70     * @param maxLengthAll 
     71     *            maximal length where it is possible to generate all sequences and draw from them 
     72     * @param validEnd 
     73     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     74     *            (see {@link #validEnd}) 
     75     */ 
     76    public HybridGenerator(int numSequences, int length, int maxLengthAll, boolean validEnd) { 
     77        // check validity of the parameters 
     78        if (numSequences < 1) { 
     79            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     80                numSequences); 
     81        } 
     82        if (length < 1) { 
     83            throw new InvalidParameterException("length of test cases must be at least 1 but is " + 
     84                length); 
     85        } 
     86        this.numSequences = numSequences; 
     87        this.length = length; 
     88        this.maxLengthAll = maxLengthAll; 
     89        this.validEnd = validEnd; 
     90    } 
     91 
     92    /** 
     93     * <p> 
     94     * Generates a test suite with a hybrid approach that is a mixture of random walks and drawing 
     95     * from all possible sequences 
     96     * </p> 
     97     *  
     98     * @param model 
     99     *            model used to determine the probability of each possible sequence 
     100     * @return the test suite 
     101     */ 
     102    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     103        if (model == null) { 
     104            throw new InvalidParameterException("model must not be null!"); 
     105        } 
     106 
     107        Collection<List<Event>> sequences = new LinkedHashSet<List<Event>>(); 
     108 
     109        List<List<Event>> seqsTmp = 
     110            new ArrayList<List<Event>>(model.generateSequences(maxLengthAll + 1, true)); 
     111 
     112        Console.traceln("" + seqsTmp.size() + " of length " + maxLengthAll + " possible"); 
     113        List<Double> probabilities = new ArrayList<Double>(seqsTmp.size()); 
     114        double probSum = 0.0; 
     115        for (List<Event> sequence : seqsTmp) { 
     116            double prob = model.getProbability(sequence); 
     117            probabilities.add(prob); 
     118            probSum += prob; 
     119        } 
     120 
     121        Random r = new Random(); 
     122        int j = 0; 
     123        while (sequences.size() < numSequences && j <= numSequences * 100) { 
     124            j++; 
     125            double randVal = r.nextDouble() * probSum; 
     126            double sum = 0.0d; 
     127            int index = -1; 
     128            while (sum < randVal) { 
     129                index++; 
     130                double currentProb = probabilities.get(index); 
     131                sum += currentProb; 
     132            } 
     133            List<Event> seqTmp = seqsTmp.get(index); 
     134            if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) { 
     135                List<Event> sequence; 
     136                if (validEnd) { 
     137                    sequence = finishSequence(seqTmp, model, length + 2, validEnd); 
     138                    if (sequence != null && sequence.size() != length + 2) { 
     139                        sequence = null; 
     140                    } 
     141                } 
     142                else { 
     143                    sequence = finishSequence(seqTmp, model, length + 1, validEnd); 
     144                    if (sequence != null && sequence.size() != length + 1) { 
     145                        sequence = null; 
     146                    } 
     147                } 
     148                if (sequence != null) { 
     149                    sequences.add(sequence); 
     150                } 
     151            } 
     152        } 
     153 
     154        return sequences; 
     155    } 
     156 
     157    /** 
     158     * <p> 
     159     * Finishes a sequence with a random walk. 
     160     * </p> 
     161     *  
     162     * @param sequence 
     163     *            sequence to be finished 
     164     * @param model 
     165     *            model used for the random walk 
     166     * @param length 
     167     *            desired length of the sequence 
     168     * @param validEnd 
     169     *            if the sequence should end in {@link Event#ENDEVENT}. 
     170     * @return finished sequence of the desired length 
     171     */ 
     172    private List<Event> finishSequence(List<Event> sequence, 
     173                                       IStochasticProcess model, 
     174                                       int length, 
     175                                       boolean validEnd) 
     176    { 
     177        Random r = new Random(); 
     178        boolean endFound = false; 
     179        List<Event> sequenceCopy = new LinkedList<Event>(sequence); 
     180        final int maxIter = 30000; 
     181        int iter = 0; 
     182        while (!endFound && iter < maxIter) { 
     183            iter++; 
     184            sequenceCopy = new LinkedList<Event>(sequence); 
     185            while (!endFound && sequenceCopy.size() <= length) { 
     186                double randVal = r.nextDouble(); 
     187                double probSum = 0.0; 
     188                for (Event symbol : model.getEvents()) { 
     189                    probSum += model.getProbability(sequenceCopy, symbol); 
     190                    if (probSum >= randVal) { 
     191                        if (!(Event.STARTEVENT.equals(symbol) || (!validEnd && Event.ENDEVENT 
     192                            .equals(symbol)))) 
     193                        { 
     194                            // only add the symbol the sequence if it is not 
     195                            // START 
     196                            // or END 
     197                            sequenceCopy.add(symbol); 
     198                        } 
     199                        endFound = 
     200                            Event.ENDEVENT.equals(symbol) || 
     201                                (!validEnd && sequenceCopy.size() == length); 
     202                        break; 
     203                    } 
     204                } 
     205            } 
     206        } 
     207        if (iter == maxIter) { 
     208            return null; 
     209        } 
     210        return sequenceCopy; 
     211    } 
    218212 
    219213} 

  • trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.testgeneration; 
    23 
    … …  
    2021public class RandomWalkGenerator { 
    2122 
    22         /** 
    23         * <p> 
    24         * Number of sequences in the test suite. 
    25         * </p> 
    26         */ 
    27         private final int numSequences; 
     23    /** 
     24    * <p> 
     25    * Number of sequences in the test suite. 
     26    * </p> 
     27    */ 
     28    private final int numSequences; 
    2829 
    29         /** 
    30         * <p> 
    31         * Minimal length of a test sequence. 
    32         * </p> 
    33         */ 
    34         private final int minLength; 
     30    /** 
     31    * <p> 
     32    * Minimal length of a test sequence. 
     33    * </p> 
     34    */ 
     35    private final int minLength; 
    3536 
    36         /** 
    37         * <p> 
    38         * Maximal length of a test sequence. 
    39         * </p> 
    40         */ 
    41         private final int maxLength; 
     37    /** 
     38    * <p> 
     39    * Maximal length of a test sequence. 
     40    * </p> 
     41    */ 
     42    private final int maxLength; 
    4243 
    43         /** 
    44          * <p> 
    45          * In case this member is true, only test cases that end in the global end 
    46          * event {@link Event#ENDEVENT} are generated. If it is false, the end event 
    47          * can be any event. 
    48          * </p> 
    49          */ 
    50         private final boolean validEnd; 
     44    /** 
     45     * <p> 
     46     * In case this member is true, only test cases that end in the global end event 
     47     * {@link Event#ENDEVENT} are generated. If it is false, the end event can be any event. 
     48     * </p> 
     49     */ 
     50    private final boolean validEnd; 
    5151 
    52         /** 
    53          * <p> 
    54          * Maximal number of random walks performed before aborting the test case 
    55          * generation and returning a test suite with less than 
    56          * {@link #numSequences} test cases. This can happen if too many generated 
    57          * random walks have to be discarded because their length is not between 
    58          * {@link #minLength} and {@link #maxLength}. 
    59          * </p> 
    60          */ 
    61         private final long maxIter; 
     52    /** 
     53     * <p> 
     54     * Maximal number of random walks performed before aborting the test case generation and 
     55     * returning a test suite with less than {@link #numSequences} test cases. This can happen if 
     56     * too many generated random walks have to be discarded because their length is not between 
     57     * {@link #minLength} and {@link #maxLength}. 
     58     * </p> 
     59     */ 
     60    private final long maxIter; 
    6261 
    63         /** 
    64         * <p> 
    65         * Actual number of random walks performed to generate the test suite. 
    66         * </p> 
    67         */ 
    68         private long actualIter = -1; 
     62    /** 
     63    * <p> 
     64    * Actual number of random walks performed to generate the test suite. 
     65    * </p> 
     66    */ 
     67    private long actualIter = -1; 
    6968 
    70         /** 
    71          * <p> 
    72          * Constructor. Creates a new RandomWalkGenerator and ensures the validity 
    73          * of the parameters: 
    74          * <ul> 
    75          * <li>numSequences must at least be 1 
    76          * <li>maxLength must at least be 1 
    77          * <li>minLength must be less than or equal to maxLength 
    78          * <li>maxIter must be greater than or equal to numSequences 
    79          * </ul> 
    80          * If one of these conditions is violated an 
    81          * {@link InvalidParameterException} is thrown. 
    82          * </p> 
    83          *  
    84          * @param numSequences 
    85          *            number of sequences desired for the test suite 
    86          * @param minLength 
    87          *            minimal length of a test sequence 
    88          * @param maxLength 
    89          *            maximal length of a test sequence 
    90          * @param validEnd 
    91          *            defines if test cases have to end with the global end event 
    92          *            {@link Event#ENDEVENT} (see {@link #validEnd}) 
    93          * @param maxIter 
    94          *            maximal number of random walks before aborting the test case 
    95          *            generation (see {@link #maxIter}) 
    96          */ 
    97         public RandomWalkGenerator(int numSequences, int minLength, int maxLength, 
    98                         boolean validEnd, long maxIter) { 
    99                 // check validity of the parameters 
    100                 if (numSequences < 1) { 
    101                         throw new InvalidParameterException( 
    102                                         "number of sequences must be at least 1 but is " 
    103                                                         + numSequences); 
    104                 } 
    105                 if (maxLength < 1) { 
    106                         throw new InvalidParameterException( 
    107                                         "maximal allowed length of test cases must be at least 1 but is " 
    108                                                         + maxLength); 
    109                 } 
    110                 if (minLength > maxLength) { 
    111                         throw new InvalidParameterException( 
    112                                         "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " 
    113                                                         + minLength + " ; max length: " + maxLength + ")"); 
    114                 } 
    115                 if (maxIter < numSequences) { 
    116                         throw new InvalidParameterException( 
    117                                         "maximal number of iterations must greater than or equal to the number of sequences (number of sequences: " 
    118                                                         + numSequences 
    119                                                         + " ; max iterations: " 
    120                                                         + maxIter 
    121                                                         + ")"); 
    122                 } 
    123                 this.numSequences = numSequences; 
    124                 this.minLength = minLength; 
    125                 this.maxLength = maxLength; 
    126                 this.validEnd = validEnd; 
    127                 this.maxIter = maxIter; 
    128         } 
     69    /** 
     70     * <p> 
     71     * Constructor. Creates a new RandomWalkGenerator and ensures the validity of the parameters: 
     72     * <ul> 
     73     * <li>numSequences must at least be 1 
     74     * <li>maxLength must at least be 1 
     75     * <li>minLength must be less than or equal to maxLength 
     76     * <li>maxIter must be greater than or equal to numSequences 
     77     * </ul> 
     78     * If one of these conditions is violated an {@link InvalidParameterException} is thrown. 
     79     * </p> 
     80     *  
     81     * @param numSequences 
     82     *            number of sequences desired for the test suite 
     83     * @param minLength 
     84     *            minimal length of a test sequence 
     85     * @param maxLength 
     86     *            maximal length of a test sequence 
     87     * @param validEnd 
     88     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT} 
     89     *            (see {@link #validEnd}) 
     90     * @param maxIter 
     91     *            maximal number of random walks before aborting the test case generation (see 
     92     *            {@link #maxIter}) 
     93     */ 
     94    public RandomWalkGenerator(int numSequences, 
     95                               int minLength, 
     96                               int maxLength, 
     97                               boolean validEnd, 
     98                               long maxIter) 
     99    { 
     100        // check validity of the parameters 
     101        if (numSequences < 1) { 
     102            throw new InvalidParameterException("number of sequences must be at least 1 but is " + 
     103                numSequences); 
     104        } 
     105        if (maxLength < 1) { 
     106            throw new InvalidParameterException( 
     107                                                "maximal allowed length of test cases must be at least 1 but is " + 
     108                                                    maxLength); 
     109        } 
     110        if (minLength > maxLength) { 
     111            throw new InvalidParameterException( 
     112                                                "minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: " + 
     113                                                    minLength + " ; max length: " + maxLength + ")"); 
     114        } 
     115        if (maxIter < numSequences) { 
     116            throw new InvalidParameterException( 
     117                                                "maximal number of iterations must greater than or equal to the number of sequences (number of sequences: " + 
     118                                                    numSequences + 
     119                                                    " ; max iterations: " + 
     120                                                    maxIter + 
     121                                                    ")"); 
     122        } 
     123        this.numSequences = numSequences; 
     124        this.minLength = minLength; 
     125        this.maxLength = maxLength; 
     126        this.validEnd = validEnd; 
     127        this.maxIter = maxIter; 
     128    } 
    129129 
    130         /** 
    131          * <p> 
    132          * Generates a test suite by repeatedly randomly walking a stochastic 
    133          * process. 
    134          * </p> 
    135          *  
    136          * @param model 
    137          *            stochastic process which performs the random walks 
    138          * @return the test suite 
    139          */ 
    140         public Collection<List<Event>> generateTestSuite( 
    141                         IStochasticProcess model) { 
    142                 if (model == null) { 
    143                         throw new InvalidParameterException("model must not be null!"); 
    144                 } 
     130    /** 
     131     * <p> 
     132     * Generates a test suite by repeatedly randomly walking a stochastic process. 
     133     * </p> 
     134     *  
     135     * @param model 
     136     *            stochastic process which performs the random walks 
     137     * @return the test suite 
     138     */ 
     139    public Collection<List<Event>> generateTestSuite(IStochasticProcess model) { 
     140        if (model == null) { 
     141            throw new InvalidParameterException("model must not be null!"); 
     142        } 
    145143 
    146                 Set<List<Event>> sequences = new HashSet<List<Event>>( 
    147                                 numSequences); 
    148                 actualIter = 0; 
    149                 while (sequences.size() < numSequences && actualIter < maxIter) { 
    150                         List<Event> generatedSequence = model.randomSequence( 
    151                                         maxLength, validEnd); 
    152                         if (generatedSequence.size() >= minLength 
    153                                         && generatedSequence.size() <= maxLength) { 
    154                                 ((List<Event>) generatedSequence).add(0, Event.STARTEVENT); 
    155                                 if (validEnd) { 
    156                                         ((List<Event>) generatedSequence).add(Event.ENDEVENT); 
    157                                 } 
    158                                 sequences.add(generatedSequence); 
    159                         } 
    160                         actualIter++; 
    161                 } 
     144        Set<List<Event>> sequences = new HashSet<List<Event>>(numSequences); 
     145        actualIter = 0; 
     146        while (sequences.size() < numSequences && actualIter < maxIter) { 
     147            List<Event> generatedSequence = model.randomSequence(maxLength, validEnd); 
     148            if (generatedSequence.size() >= minLength && generatedSequence.size() <= maxLength) { 
     149                ((List<Event>) generatedSequence).add(0, Event.STARTEVENT); 
     150                if (validEnd) { 
     151                    ((List<Event>) generatedSequence).add(Event.ENDEVENT); 
     152                } 
     153                sequences.add(generatedSequence); 
     154            } 
     155            actualIter++; 
     156        } 
    162157 
    163                 return sequences; 
    164         } 
     158        return sequences; 
     159    } 
    165160 
    166         /** 
    167          * <p> 
    168          * Returns the actual number of random walks performed during the last call 
    169          * of {@link #generateTestSuite(IStochasticProcess)} or -1 if 
    170          * {@link #generateTestSuite(IStochasticProcess)} has not been called yet. 
    171          * </p> 
    172          *  
    173          * @return actual number of random walks or -1 if 
    174          *         {@link #generateTestSuite(IStochasticProcess)} has not been 
    175          *         called 
    176          */ 
    177         public long getActualIter() { 
    178                 return actualIter; 
    179         } 
     161    /** 
     162     * <p> 
     163     * Returns the actual number of random walks performed during the last call of 
     164     * {@link #generateTestSuite(IStochasticProcess)} or -1 if 
     165     * {@link #generateTestSuite(IStochasticProcess)} has not been called yet. 
     166     * </p> 
     167     *  
     168     * @return actual number of random walks or -1 if {@link #generateTestSuite(IStochasticProcess)} 
     169     *         has not been called 
     170     */ 
     171    public long getActualIter() { 
     172        return actualIter; 
     173    } 
    180174} 
Note: See TracChangeset for help on using the changeset viewer.