TestDataStructures


1   /* Copyright (c) 2001-2005, The HSQL Development Group
2    * All rights reserved.
3    *
4    * Redistribution and use in source and binary forms, with or without
5    * modification, are permitted provided that the following conditions are met:
6    *
7    * Redistributions of source code must retain the above copyright notice, this
8    * list of conditions and the following disclaimer.
9    *
10   * Redistributions in binary form must reproduce the above copyright notice,
11   * this list of conditions and the following disclaimer in the documentation
12   * and/or other materials provided with the distribution.
13   *
14   * Neither the name of the HSQL Development Group nor the names of its
15   * contributors may be used to endorse or promote products derived from this
16   * software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  
31  
32  package org.hsqldb.test;
33  
34  import java.util.ArrayList  ;
35  import java.util.Enumeration  ;
36  import java.util.Random  ;
37  import java.util.Vector  ;
38  
39  import org.hsqldb.lib.HsqlArrayList;
40  import org.hsqldb.lib.HsqlLinkedList;
41  import org.hsqldb.lib.HsqlList;
42  import org.hsqldb.lib.StopWatch;
43  
44  import junit.framework.TestCase;
45  
46  /**
47   * Randomly excutes methods on the HsqlList data structures and compares the
48   * results with equivalent calls on the java vector class.
49   *
50   * @author dnordahl@users
51   */
52  public class TestDataStructures extends TestCase {
53  
54      private static final int NUMBER_OF_TEST_RUNS          = 100000;
55      private static final int NUMBER_OF_ITERATIONS_PER_RUN = 80;
56      private Random             randomGenerator;
57  
58      //Commands
59      private static final int ADD        = 1;
60      private static final int ADD_AT     = 2;
61      private static final int GET        = 3;
62      private static final int REMOVE     = 4;
63      private static final int SET        = 5;
64      private static final int OPTIMIZE   = 6;
65      private static final int REMOVE_ALL = 7;
66      private Vector             listCommandsCalled;
67  
68      /** Creates a new instance of TestDataStructures */
69      public TestDataStructures(String   s) {
70  
71          super(s);
72  
73          randomGenerator    = new Random  (System.currentTimeMillis());
74          listCommandsCalled = new Vector  (NUMBER_OF_ITERATIONS_PER_RUN);
75      }
76  
77      /** Runs a test on the hsqldb lists */
78      public void testLists() {
79  
80          HsqlArrayList  arrayList  = new HsqlArrayList();
81          HsqlLinkedList linkedList = new HsqlLinkedList();
82          Vector           vector     = new Vector  ();
83          Vector   listCommandsCalled = new Vector  (NUMBER_OF_ITERATIONS_PER_RUN);
84          Integer          tempInt    = null;
85          int            tempCommandCode;
86          int            tempPosition;
87          boolean        arrayListException  = false;
88          boolean        linkedListException = false;
89          boolean        vectorException     = false;
90          Object           arrayListObject     = null;
91          Object           linkedListObject    = null;
92          Object           vectorObject        = null;
93  
94          for (int i = 0; i < getRandomInt(3, 12); i++) {    // prime the contents with a couple items
95              tempInt = getRandomInteger();
96  
97              arrayList.add(tempInt);
98              linkedList.add(tempInt);
99              vector.addElement(tempInt);
100             listCommandsCalled.addElement("Add");
101         }
102 
103         compareLists(arrayList, linkedList, vector);
104 
105         for (int j = 0; j < NUMBER_OF_ITERATIONS_PER_RUN; j++) {
106             tempCommandCode = getRandomInt(0, 15);    // 0 and 8 are ignored or used for a special op
107 
108             switch (tempCommandCode) {
109 
110                 case ADD :
111                     tempInt = getRandomInteger();
112 
113                     listCommandsCalled.addElement("Add");
114                     arrayList.add(tempInt);
115                     linkedList.add(tempInt);
116                     vector.addElement(tempInt);
117                     break;
118 
119                 case ADD_AT :
120                     tempInt      = getRandomInteger();
121                     tempPosition = getRandomInt(0, vector.size() + 1);
122 
123                     listCommandsCalled.addElement("Add at " + tempPosition);
124 
125                     try {
126                         arrayList.add(tempPosition, tempInt);
127                     } catch (Exception   ex) {
128                         arrayListException = true;
129                     }
130 
131                     try {
132                         linkedList.add(tempPosition, tempInt);
133                     } catch (Exception   ex) {
134                         linkedListException = true;
135                     }
136 
137                     try {
138                         vector.insertElementAt(tempInt, tempPosition);
139                     } catch (Exception   ex) {
140                         vectorException = true;
141                     }
142                     break;
143 
144                 case GET :
145                     tempPosition = getRandomInt(0, vector.size() + 1);
146 
147                     listCommandsCalled.addElement("Get " + tempPosition);
148 
149                     try {
150                         arrayListObject = arrayList.get(tempPosition);
151                     } catch (Exception   ex) {
152                         arrayListException = true;
153                     }
154 
155                     try {
156                         linkedListObject = linkedList.get(tempPosition);
157                     } catch (Exception   ex) {
158                         linkedListException = true;
159                     }
160 
161                     try {
162                         vectorObject = vector.elementAt(tempPosition);
163                     } catch (Exception   ex) {
164                         vectorException = true;
165                     }
166                     break;
167 
168                 case REMOVE :
169                     tempPosition = getRandomInt(0, vector.size() + 1);
170 
171                     listCommandsCalled.addElement("Remove " + tempPosition);
172 
173                     try {
174                         arrayListObject = arrayList.remove(tempPosition);
175                     } catch (Exception   ex) {
176                         arrayListException = true;
177                     }
178 
179                     try {
180                         linkedListObject = linkedList.remove(tempPosition);
181                     } catch (Exception   ex) {
182                         linkedListException = true;
183                     }
184 
185                     try {
186                         vectorObject = vector.elementAt(tempPosition);
187 
188                         vector.removeElementAt(tempPosition);
189                     } catch (Exception   ex) {
190                         vectorException = true;
191                     }
192                     break;
193 
194                 case SET :
195                     tempInt      = getRandomInteger();
196                     tempPosition = getRandomInt(0, vector.size() + 1);
197 
198                     listCommandsCalled.addElement("Set " + tempPosition);
199 
200                     try {
201                         arrayList.set(tempPosition, tempInt);
202                     } catch (Exception   ex) {
203                         arrayListException = true;
204                     }
205 
206                     try {
207                         linkedList.set(tempPosition, tempInt);
208                     } catch (Exception   ex) {
209                         linkedListException = true;
210                     }
211 
212                     try {
213                         vector.setElementAt(tempInt, tempPosition);
214                     } catch (Exception   ex) {
215                         vectorException = true;
216                     }
217                     break;
218 
219                 case OPTIMIZE :
220                     listCommandsCalled.addElement("Optimize");
221                     arrayList.trim();
222                     vector.trimToSize();
223                     break;
224 
225                 case REMOVE_ALL :
226                     if (getRandomInt(0, 5) == 4) {    // to limit the frequency of this call
227                         listCommandsCalled.addElement("Remove all");
228 
229                         if (vector.size() == 0) {
230                             break;
231                         }
232 
233                         for (int k = arrayList.size() - 1; k >= 0; k--) {
234                             arrayList.remove(k);
235                             linkedList.remove(k);
236                         }
237 
238                         vector.removeAllElements();
239                     }
240                     break;
241 
242                 default :
243             }
244 
245             if (arrayListException || linkedListException
246                     || vectorException) {
247 
248                 // if an exception is thrown in vector but not one of the lists or vice versa
249                 if (!(arrayListException && linkedListException
250                         && vectorException)) {
251                     if (!(arrayListException && vectorException)) {
252                         System.out.println(
253                             "Exception descrepancy with vector and arraylist");
254                     } else if (!(linkedListException && vectorException)) {
255                         System.out.println(
256                             "Exception descrepancy with vector and linkedlist");
257                     } else {
258                         System.out.println("Error in TestDataStructures");
259                     }
260 
261                     this.printListCommandsCalled(listCommandsCalled);
262                     fail("test failed");
263 
264                     //System.exit(0);
265                 }
266 
267                 return;
268             }
269 
270             if (!objectEquals(linkedListObject, arrayListObject,
271                               vectorObject)) {
272                 System.out.println("Objects returned inconsistent");
273                 this.printListCommandsCalled(listCommandsCalled);
274                 fail("test failed");
275 
276                 //System.exit(0);
277             }
278 
279             compareLists(arrayList, linkedList, vector);
280         }
281     }
282 
283     /**
284      * Compare contents of lists to the vector.  Print out stuff if they are
285      * inconsistent and exit.
286      */
287     public void compareLists(HsqlArrayList arrayList,
288                              HsqlLinkedList linkedList, Vector   vector) {
289 
290         boolean arrayListError  = false;
291         boolean linkedListError = false;
292 
293         if (!equalsVector(arrayList, vector)) {
294             System.out.println("Error in array list implementation");
295 
296             arrayListError = true;
297         }
298 
299         if (!equalsVector(linkedList, vector)) {
300             System.out.println("Error in linked list implementation");
301 
302             linkedListError = true;
303         }
304 
305         if (arrayListError || linkedListError) {
306             this.printListCommandsCalled(listCommandsCalled);
307             System.out.flush();
308             fail("test failed");
309             System.exit(0);
310         }
311     }
312 
313     /** Prints the list of commands called so far */
314     public void printListCommandsCalled(Vector   commands) {
315 
316         int commandCode = 0;
317 
318         for (int i = 0; i < commands.size(); i++) {
319             System.out.println((String  ) commands.elementAt(i));
320         }
321 
322         System.out.flush();
323     }
324 
325     /** Returns whether three objects are equal */
326     private boolean objectEquals(Object   lObject, Object   aObject,
327                                  Object   vObject) {
328 
329         if (lObject == null && aObject == null && vObject == null) {
330             return true;
331         }
332 
333         try {
334             if (!lObject.equals(vObject)) {
335                 System.out.println("LinkList object returned inconsistent");
336 
337                 return false;
338             } else if (!aObject.equals(vObject)) {
339                 System.out.println("ArrayList object returned inconsistent");
340 
341                 return false;
342             } else {
343                 return true;
344             }
345         } catch (NullPointerException   ex) {
346             return false;
347         }
348     }
349 
350     /** Returns a random integer in the range of the lowBound and highBound */
351     private int getRandomInt(int lowBound, int highBound) {
352 
353         double random = randomGenerator.nextDouble();
354 
355         return ((int) (((highBound - lowBound) * random) + .5)) + lowBound;
356     }
357 
358     /**
359      * Returns an Integer object with a value between Integer.MIN_VALUE and
360      * Integer.MAX_VALUE
361      */
362     private Integer   getRandomInteger() {
363         return new Integer  (getRandomInt(0, (int) (Integer.MAX_VALUE
364                 / 100.0)));
365     }
366 
367     /** Tells whether the given list contains the same data as the vector */
368     private boolean equalsVector(HsqlList list, Vector   vector) {
369 
370         if (list.size() != vector.size()) {
371             return false;
372         }
373 
374         org.hsqldb.lib.Iterator listElements   = list.iterator();
375         Enumeration               vectorElements = vector.elements();
376         Object                    listObj        = null;
377         Object                    vectorObj      = null;
378 
379         while (listElements.hasNext()) {
380             listObj   = listElements.next();
381             vectorObj = vectorElements.nextElement();
382 
383             if (!listObj.equals(vectorObj)) {
384                 return false;
385             }
386         }
387 
388         return true;
389     }
390 
391     public void testGrowth() {
392 
393         HsqlArrayList d = new HsqlArrayList();
394 
395         for (int i = 0; i < 12; i++) {
396             d.add(new Integer  (i));
397         }
398 
399         for (int i = 0; i < d.size(); i++) {
400             System.out.println(d.get(i));
401         }
402 
403         d = new HsqlArrayList();
404 
405         for (int i = 0; i < 12; i++) {
406             d.add(new Integer  (i));
407         }
408 
409         d.set(11, new Integer  (11));
410 
411         for (int i = 0; i < d.size(); i++) {
412             System.out.println(d.get(i));
413         }
414 
415         org.hsqldb.lib.Iterator it = d.iterator();
416 
417         for (int i = 0; it.hasNext(); i++) {
418             Integer   value = (Integer  ) it.next();
419 
420             System.out.println(value);
421             assertEquals(i, value.intValue());
422         }
423 
424         //-
425         assertEquals(12, d.size());
426     }
427 
428     public void testSpeed() {
429 
430         randomGenerator = new Random  (System.currentTimeMillis());
431 
432         int           TEST_RUNS     = 100000;
433         int           LOOP_COUNT    = 1000;
434         HsqlArrayList arrayList     = new HsqlArrayList(TEST_RUNS);
435         ArrayList       utilArrayList = new ArrayList  (TEST_RUNS);
436         Vector          vector        = new Vector  (TEST_RUNS);
437         Integer         value         = new Integer  (randomGenerator.nextInt());
438         Integer         INT_0         = new Integer  (0);
439         StopWatch     sw            = new StopWatch();
440 
441         System.out.println(sw.currentElapsedTimeToMessage("time"));
442 
443         for (int i = 0; i < TEST_RUNS; i++) {
444             arrayList.add(INT_0);
445         }
446 
447         for (int i = 0; i < TEST_RUNS; i++) {
448             for (int j = 0; j < LOOP_COUNT; j++) {
449                 arrayList.set(i, INT_0);
450             }
451         }
452 
453         System.out.println(sw.currentElapsedTimeToMessage("time"));
454         sw.zero();
455 
456         for (int i = 0; i < TEST_RUNS; i++) {
457             utilArrayList.add(INT_0);
458         }
459 
460         for (int i = 0; i < TEST_RUNS; i++) {
461             for (int j = 0; j < LOOP_COUNT; j++) {
462                 utilArrayList.set(i, INT_0);
463             }
464         }
465 
466         System.out.println(sw.currentElapsedTimeToMessage("time"));
467         sw.zero();
468 
469         for (int i = 0; i < TEST_RUNS; i++) {
470             vector.addElement(INT_0);
471         }
472 
473         for (int i = 0; i < TEST_RUNS; i++) {
474             for (int j = 0; j < LOOP_COUNT; j++) {
475                 vector.setElementAt(INT_0, i);
476             }
477         }
478 
479         System.out.println(sw.currentElapsedTimeToMessage("time"));
480     }
481 
482     public static void main(String  [] args) {
483 
484         TestDataStructures test = new TestDataStructures("testLists");
485 
486         for (int i = 0; i < NUMBER_OF_TEST_RUNS; i++) {
487             test.testLists();
488 
489             if (i % 1000 == 0) {
490                 System.out.println("Finished " + i + " tests");
491                 System.out.flush();
492             }
493         }
494 
495         System.out.println(
496             "After " + NUMBER_OF_TEST_RUNS + " tests of a maximum of "
497             + NUMBER_OF_ITERATIONS_PER_RUN
498             + " list commands each test, the list tests passed");
499         test.testGrowth();
500     }
501 }
502
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags