KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > demo > swingset > Permuter


1 /*
2  * Copyright (c) 2003 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.6 03/01/23
38  */
39 package demo.swingset;
40
41
42 import java.util.Random JavaDoc;
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.6 01/23/03
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 JavaDoc();
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 JavaDoc[] 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
Popular Tags