--- jsr166/src/test/loops/DequeBash.java 2005/09/16 11:15:56 1.2 +++ jsr166/src/test/loops/DequeBash.java 2016/10/23 02:21:56 1.15 @@ -1,10 +1,10 @@ /* * Written by Josh Bloch of Google Inc. and released to the public domain, - * as explained at http://creativecommons.org/licenses/publicdomain. + * as explained at http://creativecommons.org/publicdomain/zero/1.0/. */ -import java.util.*; import java.io.*; +import java.util.*; /** * Interface-based Deque tester. This test currently makes three @@ -22,35 +22,33 @@ public class DequeBash { static int nextHead = -1; static int size() { return nextTail - nextHead - 1; } - - static int random(int bound) { - int x = seed; - int t = (x % 127773) * 16807 - (x / 127773) * 2836; - seed = (t > 0)? t : t + 0x7fffffff; - return (t & 0x7fffffff) % bound; - } - - static int random() { - int x = seed; - int t = (x % 127773) * 16807 - (x / 127773) * 2836; - seed = (t > 0)? t : t + 0x7fffffff; - return (t & 0x7fffffff); - } - - public static void main(String args[]) throws Exception { - Class cls = Class.forName(args[0]); - int n = 1000000; - - for (int j = 0; j < 3; ++j) { - Deque deque = (Deque) cls.newInstance(); + static int random() { + int r = seed; + r ^= r << 13; // xorshift + r ^= r >>> 17; + return seed = r ^ (r << 5); + } + + static int random(int bound) { + return (random() & 0x7fffffff) % bound; + } + + public static void main(String[] args) throws Exception { + Class cls = Class.forName(args[0]); + long startTime = System.nanoTime(); + for (int j = 0; j < 200; ++j) { + @SuppressWarnings("unchecked") + Deque deque = + (Deque) cls.getConstructor().newInstance(); nextTail = 0; nextHead = -1; - long start = System.currentTimeMillis(); - mainTest(deque, n); - long end = System.currentTimeMillis(); - System.out.println("Time: " + (end - start) + "ms"); + mainTest(deque, (random() & ((1 << 20) - 1))); if (deque.isEmpty()) System.out.print(" "); + if ((j % 10) == 9) System.out.print("."); } + long now = System.nanoTime(); + long elapsedTimeMillis = (now - startTime) / (1000L * 1000L); + System.out.printf("\ntotal time %d ms\n", elapsedTimeMillis); } @@ -71,16 +69,14 @@ public class DequeBash { // Test serialization and copying if ((i & 4095) == 0) { - testEqual(deque, deepCopy(deque)); - testEqual(deque, (Deque) deque.getClass(). - getConstructor(Collection.class).newInstance(deque)); + testEqual(deque, serialClone(deque)); + testEqual(deque, copyConstructorClone(deque)); } - + // Test fancy removal stuff once in a blue moon if ((i & 8191) == 0) testRemove(deque); - - } + } // Stupid tests for clear, toString deque.clear(); @@ -91,7 +87,7 @@ public class DequeBash { throw new Exception("Deque.toString(): " + deque.toString()); } - static void testIter(Deque deque) throws Exception { + static void testIter(Deque deque) throws Exception { int next = nextHead + 1; int count = 0; for (int j : deque) { @@ -103,7 +99,7 @@ public class DequeBash { throw new Exception("Count " + count + " != " + size()); } - static void testDescendingIter(Deque deque) throws Exception { + static void testDescendingIter(Deque deque) throws Exception { int next = deque.size() + nextHead; int count = 0; for (Iterator it = deque.descendingIterator(); it.hasNext();) { @@ -124,16 +120,16 @@ public class DequeBash { throw new Exception( "IsEmpty " + deque.isEmpty() + ", size " + size()); // Check head and tail - if (size() == 0) + if (size() == 0) testEmpty(deque); - else + else nonEmptyTest(deque); } - static void nonEmptyTest(Deque deque) throws Exception { + static void nonEmptyTest(Deque deque) throws Exception { if (deque.getFirst() != nextHead + 1) - throw new Exception("getFirst got: " + + throw new Exception("getFirst got: " + deque.getFirst() + " expecting " + (nextHead + 1)); if (deque.element() != nextHead + 1) throw new Exception("element got: " + deque.element() + @@ -144,22 +140,21 @@ public class DequeBash { if (deque.peek() != nextHead + 1) throw new Exception("peek got: " + deque.peek() + " expecting " + (nextHead + 1)); - + if (deque.peekLast() != nextTail - 1) throw new Exception("peekLast got: " + deque.peekLast() + " expecting " + (nextTail - 1)); if (deque.getLast() != nextTail - 1) - throw new Exception("getLast got: " + + throw new Exception("getLast got: " + deque.getLast() + " expecting " + (nextTail - 1)); - } - + } static void randomOp(Deque deque) throws Exception { - + // Perform a random operation - switch(random() & 3) { + switch (random() & 3) { case 0: - switch(random() & 3) { + switch (random() & 3) { case 0: deque.addLast(nextTail++); break; case 1: deque.offerLast(nextTail++); break; case 2: deque.offer(nextTail++); break; @@ -172,20 +167,20 @@ public class DequeBash { int result = 666; boolean threw = false; try { - switch(random(3)) { + switch (random(3)) { case 0: result = deque.removeFirst(); break; case 1: result = deque.remove(); break; case 2: result = deque.pop(); break; default: throw new Exception("How'd we get here"); } - } catch(NoSuchElementException e) { + } catch (NoSuchElementException e) { threw = true; } if (!threw) throw new Exception("Remove-no exception: " + result); } else { // deque nonempty int result = -1; - switch(random(5)) { + switch (random(5)) { case 0: result = deque.removeFirst(); break; case 1: result = deque.remove(); break; case 2: result = deque.pop(); break; @@ -199,7 +194,7 @@ public class DequeBash { } break; case 2: - switch(random(3)) { + switch (random(3)) { case 0: deque.addFirst(nextHead--); break; case 1: deque.offerFirst(nextHead--); break; case 2: deque.push(nextHead--); break; @@ -212,17 +207,17 @@ public class DequeBash { boolean threw = false; try { result = deque.removeLast(); - } catch(NoSuchElementException e) { + } catch (NoSuchElementException e) { threw = true; } if (!threw) throw new Exception("Remove-no exception: " + result); } else { // deque nonempty - int result = ((random() & 1) == 0? + int result = ((random() & 1) == 0 ? deque.removeLast() : deque.pollLast()); if (result != --nextTail) throw new Exception( - "Removed "+ result + " expecting "+(nextTail + 1)); + "Removed "+ result + " expecting "+(nextTail + 1)); } break; default: @@ -230,23 +225,22 @@ public class DequeBash { } } - private static void testEqual(Deque d1, Deque d2) throws Exception { if (d1.size() != d2.size()) throw new Exception("Size " + d1.size() + " != " + d2.size()); Iterator it = d2.iterator(); - for(int i : d1) { + for (int i : d1) { int j = it.next(); if (j != i) throw new Exception("Element " + j + " != " + i); } - for(int i : d1) + for (int i : d1) if (!d2.contains(i)) throw new Exception("d2 doesn't contain " + i); - for(int i : d2) + for (int i : d2) if (!d1.contains(i)) throw new Exception("d2 doesn't contain " + i); @@ -270,34 +264,28 @@ public class DequeBash { throw new Exception("d2 contains all of {Integer.MIN_VALUE }"); } - private static T deepCopy(T o) { - try { - ByteArrayOutputStream bos = new ByteArrayOutputStream(); - ObjectOutputStream oos = new ObjectOutputStream(bos); - oos.writeObject(o); - oos.flush(); - ByteArrayInputStream bin = new ByteArrayInputStream( - bos.toByteArray()); - ObjectInputStream ois = new ObjectInputStream(bin); + @SuppressWarnings("unchecked") + private static T copyConstructorClone(T o) throws Exception { + return (T) o.getClass().getConstructor(Collection.class).newInstance(o); + } + + @SuppressWarnings("unchecked") + private static T serialClone(T o) throws Exception { + ByteArrayOutputStream bos = new ByteArrayOutputStream(); + ObjectOutputStream oos = new ObjectOutputStream(bos); + oos.writeObject(o); + oos.flush(); + oos.close(); + ByteArrayInputStream bin = + new ByteArrayInputStream(bos.toByteArray()); + ObjectInputStream ois = new ObjectInputStream(bin); return (T) ois.readObject(); - } catch(Exception e) { - throw new IllegalArgumentException(e); - } } private static void testRemove(Deque deque) throws Exception { - Deque copy = null; - switch(random() & 1) { - case 0: - copy = (Deque) deque.getClass(). - getConstructor(Collection.class).newInstance(deque); - break; - case 1: - copy = deepCopy(deque); - break; - default: - throw new Exception("How'd we get here"); - } + Deque copy = ((random() & 1) == 0) ? + copyConstructorClone(deque) : + serialClone(deque); int numRemoved = 0; for (Iterator it = copy.iterator(); it.hasNext(); ) { @@ -320,11 +308,11 @@ public class DequeBash { throw new Exception(e + " missing."); boolean removed = false; - switch(random(3)) { + switch (random(3)) { case 0: removed = copy.remove(e); break; case 1: removed = copy.removeFirstOccurrence(e); break; case 2: removed = copy.removeLastOccurrence(e); break; - default: throw new Exception("How'd we get here"); + default: throw new Exception("How'd we get here"); } if (!removed) throw new Exception(e + " not removed."); @@ -335,8 +323,7 @@ public class DequeBash { testEmpty(copy); - copy = (Deque) deque.getClass(). - getConstructor(Collection.class).newInstance(deque); + copy = copyConstructorClone(deque); copy.retainAll(deque); testEqual(deque, copy); copy.removeAll(deque); @@ -368,9 +355,9 @@ public class DequeBash { boolean threw = false; int result = 666; try { - result = ((random() & 1) == 0? + result = ((random() & 1) == 0 ? deque.getFirst() : deque.element()); - } catch(NoSuchElementException e) { + } catch (NoSuchElementException e) { threw = true; } if (!threw) @@ -378,7 +365,7 @@ public class DequeBash { threw = false; try { result = deque.getLast(); - } catch(NoSuchElementException e) { + } catch (NoSuchElementException e) { threw = true; } if (!threw)