| /* |
| * Copyright (c) 2007, 2016, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package com.sun.swingset3.demos.list; |
| |
| /** |
| * An object that implements a cheesy pseudorandom permutation of the integers |
| * from zero to some user-specified value. (The permutation is a linear |
| * function.) |
| * |
| * @version 1.9 11/17/05 |
| * @author Josh Bloch |
| */ |
| class Permuter { |
| |
| /** |
| * The size of the permutation. |
| */ |
| private int modulus; |
| |
| /** |
| * Nonnegative integer less than n that is relatively prime to m. |
| */ |
| private int multiplier; |
| |
| /** |
| * Pseudorandom nonnegative integer less than n. |
| */ |
| private static final int ADDEND = 22; |
| |
| public Permuter(int n) { |
| if (n < 0) { |
| throw new IllegalArgumentException(); |
| } |
| modulus = n; |
| if (n == 1) { |
| return; |
| } |
| |
| // Initialize the multiplier and offset |
| multiplier = (int) Math.sqrt(n); |
| while (gcd(multiplier, n) != 1) { |
| if (++multiplier == n) { |
| multiplier = 1; |
| } |
| } |
| } |
| |
| /** |
| * Returns the integer to which this permuter maps the specified integer. |
| * The specified integer must be between 0 and n-1, and the returned integer |
| * will be as well. |
| */ |
| public int map(int i) { |
| return (multiplier * i + ADDEND) % modulus; |
| } |
| |
| /** |
| * Calculate GCD of a and b, which are assumed to be non-negative. |
| */ |
| private static int gcd(int a, int b) { |
| while (b != 0) { |
| int tmp = a % b; |
| a = b; |
| b = tmp; |
| } |
| return a; |
| } |
| |
| /** |
| * Simple test. Takes modulus on command line and prints out permutation. |
| */ |
| public static void main(String[] args) { |
| int modulus = Integer.parseInt(args[0]); |
| Permuter p = new Permuter(modulus); |
| for (int i = 0; i < modulus; i++) { |
| System.out.print(p.map(i) + " "); |
| } |
| System.out.println(); |
| } |
| } |