Implement java.util.Random based on Harmony and gwt-java-math. Reimplement core functionality to avoid 'long' arithmetic where possible. Review by: scottb git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@7414 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/super/com/google/gwt/emul/java/util/Random.java b/user/super/com/google/gwt/emul/java/util/Random.java new file mode 100644 index 0000000..0ded4c2 --- /dev/null +++ b/user/super/com/google/gwt/emul/java/util/Random.java
@@ -0,0 +1,357 @@ +/* + * Copyright 2009 Google Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not + * use this file except in compliance with the License. You may obtain a copy of + * the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + */ + +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with this + * work for additional information regarding copyright ownership. The ASF + * licenses this file to You under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + * + * INCLUDES MODIFICATIONS BY RICHARD ZSCHECH AS WELL AS GOOGLE. + */ +package java.util; + +import java.io.Serializable; + +/** + * This class provides methods that generates pseudo-random numbers of different + * types, such as {@code int}, {@code long}, {@code double}, and {@code float}. + * It follows the algorithms specified in the JRE javadoc. + */ +public class Random implements Serializable { + + private static final double multiplierHi = 0x5de; + private static final double multiplierLo = 0xece66d; + private static final double twoToThe24 = 16777216.0; + private static final double twoToThe31 = 2147483648.0; + private static final double twoToThe32 = 4294967296.0; + private static final double twoToTheMinus24 = + 5.9604644775390625e-8; + private static final double twoToTheMinus26 = + 1.490116119384765625e-8; + private static final double twoToTheMinus31 = + 4.656612873077392578125e-10; + private static final double twoToTheMinus53 = + 1.1102230246251565404236316680908203125e-16; + private static final double[] twoToTheXMinus24 = new double[25]; + private static final double[] twoToTheXMinus48 = new double[33]; + + /** + * A value used to avoid two random number generators produced at the same + * time having the same seed. + */ + private static int uniqueSeed = 0; + + // Initialize power-of-two tables + static { + double twoToTheXMinus48Tmp = 1.52587890625e-5; // 1.0 / (1 << (48 - 32)); + for (int i = 32; i >= 0; i--) { + twoToTheXMinus48[i] = twoToTheXMinus48Tmp; + twoToTheXMinus48Tmp *= 0.5; + } + + double twoToTheXMinus24Tmp = 1.0; + for (int i = 24; i >= 0; i--) { + twoToTheXMinus24[i] = twoToTheXMinus24Tmp; + twoToTheXMinus24Tmp *= 0.5; + } + } + + /** + * Return the number of milliseconds since 1/1/1970 as a double + * in order to avoid the use os LongLib. + */ + private static native double currentTimeMillis() /*-{ + return (new Date()).getTime(); + }-*/; + + /** + * The boolean value indicating if the second Gaussian number is available. + * + * @serial + */ + private boolean haveNextNextGaussian = false; + + /** + * The second Gaussian generated number. + * + * @serial + */ + private double nextNextGaussian; + + /** + * The high 24 bits of the 48=bit seed value. + * + * @serial It is associated with the internal state of this generator. + */ + private double seedhi; + + /** + * The low 24 bits of the 48=bit seed value. + * + * @serial It is associated with the internal state of this generator. + */ + private double seedlo; + + /** + * Construct a random generator with the current time of day in milliseconds + * plus a unique counter value as the initial state. + * + * @see #setSeed + */ + public Random() { + double seed = uniqueSeed++ + currentTimeMillis(); + int hi = (int) Math.floor(seed * twoToTheMinus24) & 0xffffff; + int lo = (int) (seed - (hi * twoToThe24)); + setSeed(hi, lo); + } + + /** + * Construct a random generator with the given {@code seed} as the initial + * state. + * + * @param seed the seed that will determine the initial state of this random + * number generator. + * @see #setSeed + */ + public Random(long seed) { + setSeed(seed); + } + + /** + * Returns the next pseudo-random, uniformly distributed {@code boolean} value + * generated by this generator. + * + * @return a pseudo-random, uniformly distributed boolean value. + */ + public boolean nextBoolean() { + return nextInternal(1) != 0; + } + + /** + * Modifies the {@code byte} array by a random sequence of {@code byte}s + * generated by this random number generator. + * + * @param buf non-null array to contain the new random {@code byte}s. + * @see #next + */ + public void nextBytes(byte[] buf) { + if (buf == null) { + throw new NullPointerException(); + } + + int rand = 0, count = 0, loop = 0; + while (count < buf.length) { + if (loop == 0) { + rand = (int) nextInternal(32); + loop = 3; + } else { + loop--; + } + buf[count++] = (byte) rand; + rand >>= 8; + } + } + + /** + * Generates a normally distributed random {@code double} number between 0.0 + * inclusively and 1.0 exclusively. + * + * @return a random {@code double} in the range [0.0 - 1.0) + * @see #nextFloat + */ + public double nextDouble() { + return nextInternal(26) * twoToTheMinus26 + + nextInternal(27) * twoToTheMinus53; + } + + /** + * Generates a normally distributed random {@code float} number between 0.0 + * inclusively and 1.0 exclusively. + * + * @return float a random {@code float} number between [0.0 and 1.0) + * @see #nextDouble + */ + public float nextFloat() { + return (float) (nextInternal(24) * twoToTheMinus24); + } + + /** + * Pseudo-randomly generates (approximately) a normally distributed {@code + * double} value with mean 0.0 and a standard deviation value of {@code 1.0} + * using the <i>polar method<i> of G. E. P. Box, M. E. Muller, and G. + * Marsaglia, as described by Donald E. Knuth in <i>The Art of Computer + * Programming, Volume 2: Seminumerical Algorithms</i>, section 3.4.1, + * subsection C, algorithm P. + * + * @return a random {@code double} + * @see #nextDouble + */ + public synchronized double nextGaussian() { + if (haveNextNextGaussian) { + // if X1 has been returned, return the second Gaussian + haveNextNextGaussian = false; + return nextNextGaussian; + } + + double v1, v2, s; + do { + // Generates two independent random variables U1, U2 + v1 = 2 * nextDouble() - 1; + v2 = 2 * nextDouble() - 1; + s = v1 * v1 + v2 * v2; + } while (s >= 1); + + // See errata for TAOCP vol. 2, 3rd ed. for proper handling of s == 0 case + // (page 5 of http://www-cs-faculty.stanford.edu/~uno/err2.ps.gz) + double norm = (s == 0) ? 0.0 : Math.sqrt(-2.0 * Math.log(s) / s); + nextNextGaussian = v2 * norm; + haveNextNextGaussian = true; + return v1 * norm; + } + + /** + * Generates a uniformly distributed 32-bit {@code int} value from the random + * number sequence. + * + * @return a uniformly distributed {@code int} value. + * @see java.lang.Integer#MAX_VALUE + * @see java.lang.Integer#MIN_VALUE + * @see #next + * @see #nextLong + */ + public int nextInt() { + return (int) nextInternal(32); + } + + /** + * Returns a new pseudo-random {@code int} value which is uniformly + * distributed between 0 (inclusively) and the value of {@code n} + * (exclusively). + * + * @param n the exclusive upper border of the range [0 - n). + * @return a random {@code int}. + */ + public int nextInt(int n) { + if (n > 0) { + if ((n & -n) == n) { + return (int) ((n * nextInternal(31)) * twoToTheMinus31); + } + double bits, val; + do { + bits = nextInternal(31); + val = bits % n; + } while (bits - val + (n - 1) < 0); + return (int) val; + } + + throw new IllegalArgumentException(); + } + + /** + * Generates a uniformly distributed 64-bit integer value from the random + * number sequence. + * + * @return 64-bit random integer. + * @see java.lang.Integer#MAX_VALUE + * @see java.lang.Integer#MIN_VALUE + * @see #next + * @see #nextInt() + * @see #nextInt(int) + */ + public long nextLong() { + return ((long) nextInternal(32) << 32) + (long) nextInternal(32); + } + + /** + * Modifies the seed a using linear congruential formula presented in <i>The + * Art of Computer Programming, Volume 2</i>, Section 3.2.1. + * + * @param seed the seed that alters the state of the random number generator. + * @see #next + * @see #Random() + * @see #Random(long) + */ + public synchronized void setSeed(long seed) { + setSeed((int) ((seed >> 24) & 0xffffff), (int) (seed & 0xffffff)); + } + + /** + * Returns a pseudo-random uniformly distributed {@code int} value of the + * number of bits specified by the argument {@code bits} as described by + * Donald E. Knuth in <i>The Art of Computer Programming, Volume 2: + * Seminumerical Algorithms</i>, section 3.2.1. + * + * @param bits number of bits of the returned value. + * @return a pseudo-random generated int number. + * @see #nextBytes + * @see #nextDouble + * @see #nextFloat + * @see #nextInt() + * @see #nextInt(int) + * @see #nextGaussian + * @see #nextLong + */ + protected synchronized int next(int bits) { + return (int) nextInternal(bits); + } + + private synchronized double nextInternal(int bits) { + double hi = seedhi * multiplierLo + seedlo * multiplierHi; + double lo = seedlo * multiplierLo + 0xb; + double carry = Math.floor(lo * twoToTheMinus24); + hi += carry; + lo -= carry * twoToThe24; + hi %= twoToThe24; + + seedhi = hi; + seedlo = lo; + + if (bits <= 24) { + // High bits of seedhi, shifted right + return Math.floor(seedhi * twoToTheXMinus24[bits]); + } else { + // All bits of seedhi, shifted left + double h = seedhi * (1 << (bits - 24)); + // High bits of seedlo, shifted right + double l = Math.floor(seedlo * twoToTheXMinus48[bits]); + // Sum of high and low bits + double dval = h + l; + // Force sign based on bit 31 + if (dval >= twoToThe31) { + dval -= twoToThe32; + } + return dval; + } + } + + // seedhi and seedlo should be integers from 0 to 2^24 - 1 + private synchronized void setSeed(int seedhi, int seedlo) { + this.seedhi = seedhi ^ 0x5de; + this.seedlo = seedlo ^ 0xece66d; + haveNextNextGaussian = false; + } +}
diff --git a/user/test/com/google/gwt/emultest/EmulSuite.java b/user/test/com/google/gwt/emultest/EmulSuite.java index 34266e4..6e29683 100644 --- a/user/test/com/google/gwt/emultest/EmulSuite.java +++ b/user/test/com/google/gwt/emultest/EmulSuite.java
@@ -46,6 +46,7 @@ import com.google.gwt.emultest.java.util.LinkedHashMapTest; import com.google.gwt.emultest.java.util.LinkedListTest; import com.google.gwt.emultest.java.util.PriorityQueueTest; +import com.google.gwt.emultest.java.util.RandomTest; import com.google.gwt.emultest.java.util.StackTest; import com.google.gwt.junit.tools.GWTTestSuite; @@ -90,6 +91,7 @@ suite.addTestSuite(LinkedHashMapTest.class); suite.addTestSuite(LinkedListTest.class); suite.addTestSuite(PriorityQueueTest.class); + suite.addTestSuite(RandomTest.class); suite.addTestSuite(StackTest.class); suite.addTestSuite(SqlDateTest.class); suite.addTestSuite(SqlTimeTest.class);
diff --git a/user/test/com/google/gwt/emultest/java/util/RandomTest.java b/user/test/com/google/gwt/emultest/java/util/RandomTest.java new file mode 100644 index 0000000..3b09580 --- /dev/null +++ b/user/test/com/google/gwt/emultest/java/util/RandomTest.java
@@ -0,0 +1,157 @@ +/* + * Copyright 2008 Google Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not + * use this file except in compliance with the License. You may obtain a copy of + * the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + */ +package com.google.gwt.emultest.java.util; + +import com.google.gwt.junit.client.GWTTestCase; + +import java.util.Random; + +/** + * Tests for GWT's emulation of the JRE Random class. The JRE specifies the + * exact algorithm used to generate the pseudorandom output. + */ +public class RandomTest extends GWTTestCase { + + /** + * Sets module name so that javascript compiler can operate. + */ + @Override + public String getModuleName() { + return "com.google.gwt.emultest.EmulSuite"; + } + + public void testNextBytes() { + Random r = new Random(1); + byte[] b = new byte[5]; + r.nextBytes(b); + assertEquals((byte) 115, b[0]); + assertEquals((byte) -43, b[1]); + assertEquals((byte) 26, b[2]); + assertEquals((byte) -69, b[3]); + assertEquals((byte) -40, b[4]); + + try { + r.nextBytes(null); + fail("Expected NullPointerException"); + } catch (NullPointerException e) { + } + } + + public void testNextDouble() { + Random r = new Random(1); + assertEquals(0.7308781907032909, r.nextDouble()); + assertEquals(0.41008081149220166, r.nextDouble()); + assertEquals(0.20771484130971707, r.nextDouble()); + assertEquals(0.3327170559595112, r.nextDouble()); + assertEquals(0.9677559094241207, r.nextDouble()); + } + + public void testNextFloat() { + Random r = new Random(1); + assertEquals(0.7308782f, r.nextFloat()); + assertEquals(0.100473166f, r.nextFloat()); + assertEquals(0.4100808f, r.nextFloat()); + assertEquals(0.40743977f, r.nextFloat()); + assertEquals(0.2077148f, r.nextFloat()); + } + + public void testNextGaussian() { + Random r = new Random(1); + assertEquals(1.561581040188955, r.nextGaussian()); + assertEquals(-0.6081826070068602, r.nextGaussian()); + assertEquals(-1.0912278829447088, r.nextGaussian()); + assertEquals(-0.6245401364066232, r.nextGaussian()); + assertEquals(-1.1182832102556484, r.nextGaussian()); + } + + public void testNextInt() { + Random r = new Random(1); + assertEquals(-1155869325, r.nextInt()); + assertEquals(431529176, r.nextInt()); + assertEquals(1761283695, r.nextInt()); + assertEquals(1749940626, r.nextInt()); + assertEquals(892128508, r.nextInt()); + + try { + r.nextInt(0); + fail("Expected IlledgalArgumentException"); + } catch (IllegalArgumentException e) { + } + + try { + r.nextInt(-1); + fail("Expected IlledgalArgumentException"); + } catch (IllegalArgumentException e) { + } + } + + public void testNextInt100() { + Random r = new Random(1); + assertEquals(85, r.nextInt(100)); + assertEquals(88, r.nextInt(100)); + assertEquals(47, r.nextInt(100)); + assertEquals(13, r.nextInt(100)); + assertEquals(54, r.nextInt(100)); + } + + public void testNextInt128() { + Random r = new Random(1); + assertEquals(93, r.nextInt(128)); + assertEquals(12, r.nextInt(128)); + assertEquals(52, r.nextInt(128)); + assertEquals(52, r.nextInt(128)); + assertEquals(26, r.nextInt(128)); + } + + public void testNextLong() { + Random r = new Random(1); + assertEquals(-4964420948893066024L, r.nextLong()); + assertEquals(7564655870752979346L, r.nextLong()); + assertEquals(3831662765844904176L, r.nextLong()); + assertEquals(6137546356583794141L, r.nextLong()); + assertEquals(-594798593157429144L, r.nextLong()); + } + + public void testSetSeed() { + Random r = new Random(); + + r.setSeed(1); + byte[] b = new byte[1]; + r.nextBytes(b); + assertEquals((byte) 115, b[0]); + + r.setSeed(1); + assertEquals(0.7308781907032909, r.nextDouble()); + + r.setSeed(1); + assertEquals(0.7308782f, r.nextFloat()); + + r.setSeed(1); + assertEquals(1.561581040188955, r.nextGaussian()); + + r.setSeed(1); + assertEquals(-1155869325, r.nextInt()); + + r.setSeed(1); + assertEquals(85, r.nextInt(100)); + + r.setSeed(1); + assertEquals(93, r.nextInt(128)); + + r.setSeed(1); + assertEquals(-4964420948893066024L, r.nextLong()); + } +}