ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/loops/DequeBash.java
(Generate patch)

Comparing jsr166/src/test/loops/DequeBash.java (file contents):
Revision 1.2 by dl, Fri Sep 16 11:15:56 2005 UTC vs.
Revision 1.15 by jsr166, Sun Oct 23 02:21:56 2016 UTC

# Line 1 | Line 1
1   /*
2   * Written by Josh Bloch of Google Inc. and released to the public domain,
3 < * as explained at http://creativecommons.org/licenses/publicdomain.
3 > * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
4   */
5  
6 – import java.util.*;
6   import java.io.*;
7 + import java.util.*;
8  
9   /**
10   * Interface-based Deque tester.  This test currently makes three
# Line 22 | Line 22 | public class DequeBash {
22      static int nextHead = -1;
23      static int size() { return nextTail - nextHead - 1; }
24  
25 <    
26 <    static int random(int bound) {
27 <        int x = seed;
28 <        int t = (x % 127773) * 16807 - (x / 127773) * 2836;
29 <        seed = (t > 0)? t : t + 0x7fffffff;
30 <        return (t & 0x7fffffff) % bound;
31 <    }
32 <
33 <    static int random() {
34 <        int x = seed;
35 <        int t = (x % 127773) * 16807 - (x / 127773) * 2836;
36 <        seed = (t > 0)? t : t + 0x7fffffff;
37 <        return (t & 0x7fffffff);
38 <    }
39 <
40 <    public static void main(String args[]) throws Exception {
41 <        Class cls = Class.forName(args[0]);
42 <        int n = 1000000;
43 <
44 <        for (int j = 0; j < 3; ++j) {
45 <            Deque<Integer> deque = (Deque<Integer>) cls.newInstance();
25 >    static int random() {
26 >        int r = seed;
27 >        r ^= r << 13;   // xorshift
28 >        r ^= r >>> 17;
29 >        return seed = r ^ (r << 5);
30 >    }
31 >
32 >    static int random(int bound) {
33 >        return (random() & 0x7fffffff) % bound;
34 >    }
35 >
36 >    public static void main(String[] args) throws Exception {
37 >        Class<?> cls = Class.forName(args[0]);
38 >        long startTime = System.nanoTime();
39 >        for (int j = 0; j < 200; ++j) {
40 >            @SuppressWarnings("unchecked")
41 >            Deque<Integer> deque =
42 >                (Deque<Integer>) cls.getConstructor().newInstance();
43              nextTail =  0;
44              nextHead = -1;
45 <            long start = System.currentTimeMillis();
49 <            mainTest(deque, n);
50 <            long end = System.currentTimeMillis();
51 <            System.out.println("Time: " + (end - start) + "ms");
45 >            mainTest(deque, (random() & ((1 << 20) - 1)));
46              if (deque.isEmpty()) System.out.print(" ");
47 +            if ((j % 10) == 9) System.out.print(".");
48          }
49 +        long now = System.nanoTime();
50 +        long elapsedTimeMillis = (now - startTime) / (1000L * 1000L);
51 +        System.out.printf("\ntotal time %d ms\n", elapsedTimeMillis);
52  
53      }
54  
# Line 71 | Line 69 | public class DequeBash {
69  
70              // Test serialization and copying
71              if ((i & 4095) == 0) {
72 <                testEqual(deque, deepCopy(deque));
73 <                testEqual(deque, (Deque<Integer>) deque.getClass().
76 <                          getConstructor(Collection.class).newInstance(deque));
72 >                testEqual(deque, serialClone(deque));
73 >                testEqual(deque, copyConstructorClone(deque));
74              }
75 <            
75 >
76              // Test fancy removal stuff once in a blue moon
77              if ((i & 8191) == 0)
78                  testRemove(deque);
79 <            
83 <         }
79 >        }
80  
81          // Stupid tests for clear, toString
82          deque.clear();
# Line 91 | Line 87 | public class DequeBash {
87              throw new Exception("Deque.toString():  " + deque.toString());
88      }
89  
90 <    static void testIter(Deque<Integer> deque) throws Exception {                
90 >    static void testIter(Deque<Integer> deque) throws Exception {
91          int next = nextHead + 1;
92          int count = 0;
93          for (int j : deque) {
# Line 103 | Line 99 | public class DequeBash {
99              throw new Exception("Count " + count + " != " + size());
100      }
101  
102 <    static void testDescendingIter(Deque<Integer> deque) throws Exception {                
102 >    static void testDescendingIter(Deque<Integer> deque) throws Exception {
103          int next = deque.size() + nextHead;
104          int count = 0;
105          for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) {
# Line 124 | Line 120 | public class DequeBash {
120              throw new Exception(
121                                  "IsEmpty " + deque.isEmpty() + ", size " + size());
122          // Check head and tail
123 <        if (size() == 0)
123 >        if (size() == 0)
124              testEmpty(deque);
125 <        else
125 >        else
126              nonEmptyTest(deque);
127  
128      }
129  
130 <    static void nonEmptyTest(Deque<Integer> deque) throws Exception {            
130 >    static void nonEmptyTest(Deque<Integer> deque) throws Exception {
131          if (deque.getFirst() != nextHead + 1)
132 <            throw new Exception("getFirst got: " +
132 >            throw new Exception("getFirst got: " +
133                                  deque.getFirst() + " expecting " + (nextHead + 1));
134          if (deque.element() != nextHead + 1)
135              throw new Exception("element got: " + deque.element() +
# Line 144 | Line 140 | public class DequeBash {
140          if (deque.peek() != nextHead + 1)
141              throw new Exception("peek got: " +  deque.peek() +
142                                  " expecting " + (nextHead + 1));
143 <        
143 >
144          if (deque.peekLast() != nextTail - 1)
145              throw new Exception("peekLast got: " + deque.peekLast() +
146                                  " expecting " + (nextTail - 1));
147          if (deque.getLast() != nextTail - 1)
148 <            throw new Exception("getLast got: " +
148 >            throw new Exception("getLast got: " +
149                                  deque.getLast() + " expecting " + (nextTail - 1));
150 <    }        
155 <    
150 >    }
151  
152      static void randomOp(Deque<Integer> deque) throws Exception {
153 <        
153 >
154          // Perform a random operation
155 <        switch(random() & 3) {
155 >        switch (random() & 3) {
156          case 0:
157 <            switch(random() & 3) {
157 >            switch (random() & 3) {
158              case 0: deque.addLast(nextTail++);   break;
159              case 1: deque.offerLast(nextTail++); break;
160              case 2: deque.offer(nextTail++);     break;
# Line 172 | Line 167 | public class DequeBash {
167                  int result = 666;
168                  boolean threw = false;
169                  try {
170 <                    switch(random(3)) {
170 >                    switch (random(3)) {
171                      case 0: result = deque.removeFirst(); break;
172                      case 1: result = deque.remove();      break;
173                      case 2: result = deque.pop();         break;
174                      default: throw new Exception("How'd we get here");
175                      }
176 <                } catch(NoSuchElementException e) {
176 >                } catch (NoSuchElementException e) {
177                      threw = true;
178                  }
179                  if (!threw)
180                      throw new Exception("Remove-no exception: " + result);
181              } else { // deque nonempty
182                  int result = -1;
183 <                switch(random(5)) {
183 >                switch (random(5)) {
184                  case 0: result = deque.removeFirst(); break;
185                  case 1: result = deque.remove();      break;
186                  case 2: result = deque.pop();         break;
# Line 199 | Line 194 | public class DequeBash {
194              }
195              break;
196          case 2:
197 <            switch(random(3)) {
197 >            switch (random(3)) {
198              case 0: deque.addFirst(nextHead--);   break;
199              case 1: deque.offerFirst(nextHead--); break;
200              case 2: deque.push(nextHead--);       break;
# Line 212 | Line 207 | public class DequeBash {
207                  boolean threw = false;
208                  try {
209                      result = deque.removeLast();
210 <                } catch(NoSuchElementException e) {
210 >                } catch (NoSuchElementException e) {
211                      threw = true;
212                  }
213                  if (!threw)
214                      throw new Exception("Remove-no exception: " + result);
215              } else { // deque nonempty
216 <                int result = ((random() & 1) == 0?
216 >                int result = ((random() & 1) == 0 ?
217                                deque.removeLast() : deque.pollLast());
218                  if (result != --nextTail)
219                      throw new Exception(
220 <                                        "Removed "+ result + " expecting "+(nextTail + 1));
220 >                        "Removed "+ result + " expecting "+(nextTail + 1));
221              }
222              break;
223          default:
# Line 230 | Line 225 | public class DequeBash {
225          }
226      }
227  
233 –
228      private static void testEqual(Deque<Integer> d1, Deque<Integer> d2)
229          throws Exception
230      {
231          if (d1.size() != d2.size())
232              throw new Exception("Size " + d1.size() + " != " + d2.size());
233          Iterator<Integer> it = d2.iterator();
234 <        for(int i : d1) {
234 >        for (int i : d1) {
235              int j = it.next();
236              if (j != i)
237                  throw new Exception("Element " + j + " != " + i);
238          }
239  
240 <        for(int i : d1)
240 >        for (int i : d1)
241              if (!d2.contains(i))
242                  throw new Exception("d2 doesn't contain " + i);
243 <        for(int i : d2)
243 >        for (int i : d2)
244              if (!d1.contains(i))
245                  throw new Exception("d2 doesn't contain " + i);
246  
# Line 270 | Line 264 | public class DequeBash {
264              throw new Exception("d2 contains all of {Integer.MIN_VALUE }");
265      }
266  
267 <    private static <T> T deepCopy(T o) {
268 <        try {
269 <            ByteArrayOutputStream bos = new ByteArrayOutputStream();
270 <            ObjectOutputStream oos = new ObjectOutputStream(bos);
271 <            oos.writeObject(o);
272 <            oos.flush();
273 <            ByteArrayInputStream bin = new ByteArrayInputStream(
274 <                bos.toByteArray());
275 <            ObjectInputStream ois = new ObjectInputStream(bin);
267 >    @SuppressWarnings("unchecked")
268 >    private static <T> T copyConstructorClone(T o) throws Exception {
269 >        return (T) o.getClass().getConstructor(Collection.class).newInstance(o);
270 >    }
271 >
272 >    @SuppressWarnings("unchecked")
273 >    private static <T> T serialClone(T o) throws Exception {
274 >        ByteArrayOutputStream bos = new ByteArrayOutputStream();
275 >        ObjectOutputStream oos = new ObjectOutputStream(bos);
276 >        oos.writeObject(o);
277 >        oos.flush();
278 >        oos.close();
279 >        ByteArrayInputStream bin =
280 >            new ByteArrayInputStream(bos.toByteArray());
281 >        ObjectInputStream ois = new ObjectInputStream(bin);
282              return (T) ois.readObject();
283 –        } catch(Exception e) {
284 –            throw new IllegalArgumentException(e);
285 –        }
283      }
284  
285      private static void testRemove(Deque<Integer> deque) throws Exception {
286 <        Deque<Integer> copy = null;
287 <        switch(random() & 1) {
288 <          case 0:
292 <            copy = (Deque<Integer>) deque.getClass().
293 <                getConstructor(Collection.class).newInstance(deque);
294 <            break;
295 <          case 1:
296 <            copy = deepCopy(deque);
297 <            break;
298 <          default:
299 <            throw new Exception("How'd we get here");
300 <        }
286 >        Deque<Integer> copy = ((random() & 1) == 0) ?
287 >            copyConstructorClone(deque) :
288 >            serialClone(deque);
289  
290          int numRemoved = 0;
291          for (Iterator<Integer> it = copy.iterator(); it.hasNext(); ) {
# Line 320 | Line 308 | public class DequeBash {
308                  throw new Exception(e + " missing.");
309  
310              boolean removed = false;
311 <            switch(random(3)) {
311 >            switch (random(3)) {
312                  case 0:  removed = copy.remove(e);                break;
313                  case 1:  removed = copy.removeFirstOccurrence(e); break;
314                  case 2:  removed = copy.removeLastOccurrence(e);  break;
315 <                default: throw new Exception("How'd we get here");            
315 >                default: throw new Exception("How'd we get here");
316              }
317              if (!removed)
318                  throw new Exception(e + " not removed.");
# Line 335 | Line 323 | public class DequeBash {
323  
324          testEmpty(copy);
325  
326 <        copy = (Deque<Integer>) deque.getClass().
339 <            getConstructor(Collection.class).newInstance(deque);
326 >        copy = copyConstructorClone(deque);
327          copy.retainAll(deque);
328          testEqual(deque, copy);
329          copy.removeAll(deque);
# Line 368 | Line 355 | public class DequeBash {
355              boolean threw = false;
356              int result = 666;
357              try {
358 <                result = ((random() & 1) == 0?
358 >                result = ((random() & 1) == 0 ?
359                            deque.getFirst() : deque.element());
360 <            } catch(NoSuchElementException e) {
360 >            } catch (NoSuchElementException e) {
361                  threw = true;
362              }
363              if (!threw)
# Line 378 | Line 365 | public class DequeBash {
365              threw = false;
366              try {
367                  result = deque.getLast();
368 <            } catch(NoSuchElementException e) {
368 >            } catch (NoSuchElementException e) {
369                  threw = true;
370              }
371              if (!threw)

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines