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 

    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      */

    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      */

    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      */

    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 }