contrib/psg/src/peersim/util/RandPermutation.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.util;
  20
  21 import java.util.NoSuchElementException;
  22 import java.util.Random;
  23
  24 /**
  25 * This class provides a random permutation of indexes. Useful for
  26 * random sampling without replacement.
  27 */
  28 public class RandPermutation implements IndexIterator {
  29
  30
  31 // ======================= private fields ============================
  32 // ===================================================================
  33
  34
  35 private int[] buffer = null;
  36
  37 private int len = 0;
  38
  39 private int pointer = 0;
  40
  41 private final Random r;
  42
  43
  44 // ======================= initialization ============================
  45 // ===================================================================
  46
  47
  48 /** Sets source of randomness to be used. You need to call
  49 * {@link #reset} to fully initialize the object.
  50 * @param r Source of randomness
  51 */
  52 public RandPermutation( Random r ) { this.r=r; }
  53
  54 // -------------------------------------------------------------------
  55
  56 /** Sets source of randomness and initial size. It calls
  57 * {@link #setPermutation} to fully initialize the object with a
  58 * permuation ready to use.
  59 * @param r Source of randomness
  60 * @param k size of permutation
  61 */
  62 public RandPermutation( int k, Random r ) {
  63
  64         this.r=r;
  65         setPermutation(k);
  66 }
  67
  68
  69 // ======================= public methods ============================
  70 // ===================================================================
  71
  72
  73 /**
  74 * It calculates a random permutation of the integers from 0 to k-1.
  75 * The permutation can be read using method {@link #get}.
  76 * If the previous permutation was of the same length, it is more efficient.
  77 * Note that after calling this the object is reset, so {@link #next} can
  78 * be called k times, even if {@link #get} was called an arbitrary number of
  79 * times. Note however that mixing {@link #get} and {@link #next} results in
  80 * incorrect behavior for {@link #get} (but {@link #next} works fine).
  81 * The idea is to use this method only in connection with {@link #get}.
  82 */
  83 public void setPermutation(int k) {
  84
  85         reset(k);
  86
  87         for(int i=len; i>1; i--)
  88         {
  89                 int j = r.nextInt(i);
  90                 int a = buffer[j];
  91                 buffer[j] = buffer[i-1];
  92                 buffer[i-1] = a;
  93         }
  94 }
  95
  96 // -------------------------------------------------------------------
  97
  98 /**
  99 * Returns the ith element of the permutation set by {@link #setPermutation}.
 100 * If {@link #next} is called after {@link #setPermutation} and before
 101 * this method, then the behavior of this method is unspecified.
 102 */
 103 public int get(int i) {
 104
 105         if( i >= len ) throw new IndexOutOfBoundsException();
 106         return buffer[i];
 107 }
 108
 109 // -------------------------------------------------------------------
 110
 111 /**
 112 * It initiates a random permutation of the integers from 0 to k-1.
 113 * It does not actually calculate the permutation.
 114 * The permutation can be read using method {@link #next}.
 115 * Calls to {@link #get} return undefined values, so {@link #next} must be used.
 116 * If the previous permutation was of the same length, it is more efficient.
 117 */
 118 public void reset(int k) {
 119
 120         pointer = k;
 121         if( len == k ) return;
 122
 123         if( buffer == null || buffer.length < k )
 124         {
 125                 buffer = new int[k];
 126         }
 127
 128         len = k;
 129         for( int i=0; i<len; ++i ) buffer[i]=i;
 130 }
 131
 132 // -------------------------------------------------------------------
 133
 134 /** Next random sample without replacement */
 135 public int next() {
 136
 137         if( pointer < 1 ) throw new NoSuchElementException();
 138
 139         int j = r.nextInt(pointer);
 140         int a = buffer[j];
 141         buffer[j] = buffer[pointer-1];
 142         buffer[pointer-1] = a;
 143
 144         return buffer[--pointer];
 145 }
 146
 147 // -------------------------------------------------------------------
 148
 149 public boolean hasNext() { return pointer > 0; }
 150
 151 // -------------------------------------------------------------------
 152
 153 /*
 154 public static void main( String pars[] ) throws Exception {
 155
 156         RandPermutation rp = new RandPermutation(new Random());
 157
 158         int k;
 159
 160         k = Integer.parseInt(pars[0]);
 161         rp.setPermutation(k);
 162         for(int i=0; i<k; ++i) System.out.println(rp.get(i));
 163
 164         System.out.println();
 165
 166         k = Integer.parseInt(pars[1]);
 167         rp.reset(k);
 168         while(rp.hasNext()) System.out.println(rp.next());
 169
 170         System.out.println();
 171
 172         k = Integer.parseInt(pars[2]);
 173         rp.reset(k);
 174         while(rp.hasNext()) System.out.println(rp.next());
 175         System.out.println(rp.next());
 176 }
 177 */
 178 }