src/main/gov/nasa/jpf/util/PairPermutationGenerator.java

   1 /*
   2  * Copyright (C) 2015, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.util;
  19
  20 import java.util.NoSuchElementException;
  21
  22 /**
  23  * a generator for pair-wise permutations, which only considers permutations
  24  * for each pair of elements, regardless of position. This reduces the
  25  * number of generated permutations from N! to sum(i=1..N){N-i} + 1.
  26  * This can be used to test order dependencies between two concurrent
  27  * entities (threads, state machines etc), based on the same assumptions
  28  * that are used in pair-wise testing
  29  */
  30 public class PairPermutationGenerator extends PermutationGenerator {
  31
  32   protected int i, j;
  33
  34   public PairPermutationGenerator (int nElements){
  35     super(nElements);
  36   }
  37
  38   @Override
  39   public void reset(){
  40     initPermutations();
  41     i = 0;
  42     j = 0;
  43   }
  44
  45   public static long computeNumberOfPermutations (int n){
  46     long v = 1;
  47     for (int l=1; l<n; l++){
  48       v += (n - l);
  49     }
  50     return v;
  51   }
  52
  53   @Override
  54   protected long computeNumberOfPermutations(){
  55     return computeNumberOfPermutations(nElements);
  56   }
  57
  58   @Override
  59   public int[] next (){
  60     int n = permutation.length;
  61
  62     if (nGenerated == 0){ // the initial order
  63       nGenerated = 1;
  64       return permutation;
  65
  66     } else if (nGenerated > 1){
  67       if (nGenerated == nPermutations){
  68         throw new NoSuchElementException();
  69       }
  70       swap(permutation, i, j); // revert last permutation
  71     }
  72
  73
  74     if (++j == n){
  75       if (++i == n){
  76         throw new NoSuchElementException();
  77       } else {
  78         j = i+1;
  79       }
  80     }
  81
  82     swap(permutation, i, j);
  83     nGenerated++;
  84     return permutation;
  85   }
  86
  87 }