1 /*
2  * Copyright (c) 2007, 2016, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 package com.sun.swingset3.demos.list;
24 
25 /**
26  * An object that implements a cheesy pseudorandom permutation of the integers
27  * from zero to some user-specified value. (The permutation is a linear
28  * function.)
29  *
30  * @version 1.9 11/17/05
31  * @author Josh Bloch
32  */
33 class Permuter {
34 
35     /**
36      * The size of the permutation.
37      */
38     private int modulus;
39 
40     /**
41      * Nonnegative integer less than n that is relatively prime to m.
42      */
43     private int multiplier;
44 
45     /**
46      * Pseudorandom nonnegative integer less than n.
47      */
48     private static final int ADDEND = 22;
49 
Permuter(int n)50     public Permuter(int n) {
51         if (n < 0) {
52             throw new IllegalArgumentException();
53         }
54         modulus = n;
55         if (n == 1) {
56             return;
57         }
58 
59         // Initialize the multiplier and offset
60         multiplier = (int) Math.sqrt(n);
61         while (gcd(multiplier, n) != 1) {
62             if (++multiplier == n) {
63                 multiplier = 1;
64             }
65         }
66     }
67 
68     /**
69      * Returns the integer to which this permuter maps the specified integer.
70      * The specified integer must be between 0 and n-1, and the returned integer
71      * will be as well.
72      */
map(int i)73     public int map(int i) {
74         return (multiplier * i + ADDEND) % modulus;
75     }
76 
77     /**
78      * Calculate GCD of a and b, which are assumed to be non-negative.
79      */
gcd(int a, int b)80     private static int gcd(int a, int b) {
81         while (b != 0) {
82             int tmp = a % b;
83             a = b;
84             b = tmp;
85         }
86         return a;
87     }
88 
89     /**
90      * Simple test. Takes modulus on command line and prints out permutation.
91      */
main(String[] args)92     public static void main(String[] args) {
93         int modulus = Integer.parseInt(args[0]);
94         Permuter p = new Permuter(modulus);
95         for (int i = 0; i < modulus; i++) {
96             System.out.print(p.map(i) + " ");
97         }
98         System.out.println();
99     }
100 }
101