home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / JBuilder8.iso / Solaris / resource / jre / demo / jfc / SwingSet2 / src / Permuter.java < prev    next >
Encoding:
Java Source  |  2002-09-06  |  3.6 KB  |  120 lines
  1. /*
  2.  * Copyright (c) 2002 Sun Microsystems, Inc. All  Rights Reserved.
  3.  * 
  4.  * Redistribution and use in source and binary forms, with or without
  5.  * modification, are permitted provided that the following conditions
  6.  * are met:
  7.  * 
  8.  * -Redistributions of source code must retain the above copyright
  9.  *  notice, this list of conditions and the following disclaimer.
  10.  * 
  11.  * -Redistribution in binary form must reproduct the above copyright
  12.  *  notice, this list of conditions and the following disclaimer in
  13.  *  the documentation and/or other materials provided with the distribution.
  14.  * 
  15.  * Neither the name of Sun Microsystems, Inc. or the names of contributors
  16.  * may be used to endorse or promote products derived from this software
  17.  * without specific prior written permission.
  18.  * 
  19.  * This software is provided "AS IS," without a warranty of any kind. ALL
  20.  * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
  21.  * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
  22.  * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT
  23.  * BE LIABLE FOR ANY DAMAGES OR LIABILITIES SUFFERED BY LICENSEE AS A RESULT
  24.  * OF OR RELATING TO USE, MODIFICATION OR DISTRIBUTION OF THE SOFTWARE OR ITS
  25.  * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
  26.  * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
  27.  * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
  28.  * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE SOFTWARE, EVEN
  29.  * IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
  30.  * 
  31.  * You acknowledge that Software is not designed, licensed or intended for
  32.  * use in the design, construction, operation or maintenance of any nuclear
  33.  * facility.
  34.  */
  35.  
  36. /*
  37.  * @(#)Permuter.java    1.5 02/06/13
  38.  */
  39.  
  40.  
  41.  
  42. import java.util.Random;
  43.  
  44. /**
  45.  * An object that implements a cheesy pseudorandom permutation of the integers
  46.  * from zero to some user-specified value. (The permutation is a linear
  47.  * function.) 
  48.  *
  49.  * @version 1.5 06/13/02
  50.  * @author Josh Bloch
  51.  */
  52. class Permuter {
  53.     /**
  54.      * The size of the permutation.
  55.      */
  56.     private int modulus;
  57.  
  58.     /**
  59.      * Nonnegative integer less than n that is relatively prime to m.
  60.      */
  61.     private int multiplier;
  62.  
  63.     /**
  64.      * Pseudorandom nonnegative integer less than n.
  65.      */
  66.     private int addend = 22;
  67.  
  68.     public Permuter(int n) {
  69.         if (n<0) {
  70.             throw new IllegalArgumentException();
  71.     }
  72.         modulus = n;
  73.         if (n==1) {
  74.             return;
  75.     }
  76.  
  77.         // Initialize the multiplier and offset
  78.         multiplier = (int) Math.sqrt(n);
  79.         while (gcd(multiplier, n) != 1) {
  80.             if (++multiplier == n) {
  81.                 multiplier = 1;
  82.         }
  83.     }
  84.     }
  85.  
  86.     /**
  87.      * Returns the integer to which this permuter maps the specified integer.
  88.      * The specified integer must be between 0 and n-1, and the returned
  89.      * integer will be as well.
  90.      */
  91.     public int map(int i) {
  92.         return (multiplier * i + addend) % modulus;
  93.     }
  94.  
  95.     /**
  96.      * Calculate GCD of a and b, which are assumed to be non-negative.
  97.      */
  98.     private static int gcd(int a, int b) {
  99.         while(b != 0) {
  100.             int tmp = a % b;
  101.             a = b;
  102.             b = tmp;
  103.         }
  104.         return a;
  105.     }
  106.  
  107.     /**
  108.      * Simple test.  Takes modulus on command line and prints out permutation.
  109.      */
  110.     public static void main(String[] args) {
  111.         int modulus = Integer.parseInt(args[0]);
  112.         Permuter p = new Permuter(modulus);
  113.         for (int i=0; i<modulus; i++) {
  114.             System.out.print(p.map(i)+" ");
  115.     }
  116.         System.out.println();
  117.     }
  118. }
  119.  
  120.