src/main/gov/nasa/jpf/util/PermutationGenerator.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.io.PrintStream;
  21
  22 /**
  23  * base type for permutation generators
  24  */
  25 public abstract class PermutationGenerator {
  26
  27   protected final int nElements;
  28
  29   protected int[] permutation;   // array containing permutation
  30
  31   protected long nPermutations;
  32   protected long nGenerated;
  33
  34   protected PermutationGenerator (int nElements){
  35     this.nElements = nElements;
  36     nPermutations = computeNumberOfPermutations();
  37
  38     initPermutations();
  39   }
  40
  41   protected void initPermutations (){
  42     permutation = new int[nElements];
  43
  44     // initialize element array in order, starting with firstIdx
  45     for (int i=0; i<nElements; i++){
  46       permutation[i] = i;
  47     }
  48
  49     nGenerated = 0;
  50   }
  51
  52   protected abstract long computeNumberOfPermutations();
  53   public abstract void reset();
  54
  55   public long getNumberOfPermutations(){
  56     return nPermutations;
  57   }
  58
  59   public long getNumberOfGeneratedPermutations(){
  60     return nGenerated;
  61   }
  62
  63   static void swap(int[] a, int i, int j){
  64     int tmp = a[j];
  65     a[j] = a[i];
  66     a[i] = tmp;
  67   }
  68
  69   /**
  70    * for debugging purposes
  71    */
  72   public void printOn (PrintStream ps){
  73     printOn( ps, nGenerated, permutation);
  74   }
  75
  76   public static void printOn (PrintStream ps, long nGenerated, int[] perm){
  77     ps.printf("%2d: [", nGenerated);
  78     for (int k=0; k<perm.length; k++){
  79       if (k > 0) ps.print(',');
  80       ps.print(perm[k]);
  81     }
  82     ps.println(']');
  83   }
  84
  85
  86   //--- the public iteration interface, following Iterator
  87   public boolean hasNext(){
  88     return (nGenerated < nPermutations);
  89   }
  90
  91   /**
  92    * return the next permutation or throw a NoSuchElementException if there is none.
  93    *
  94    * NOTE - this does not guarantee to return a different object on each call,
  95    * i.e. the caller has to clone if the result is stored directly
  96    */
  97   public abstract int[] next(); // the work horse, throws NoSuchElementException
  98 }