001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.test;
032:
033: import java.util.ArrayList;
034: import java.util.Enumeration;
035: import java.util.Random;
036: import java.util.Vector;
037:
038: import org.hsqldb.lib.HsqlArrayList;
039: import org.hsqldb.lib.HsqlLinkedList;
040: import org.hsqldb.lib.HsqlList;
041: import org.hsqldb.lib.StopWatch;
042:
043: import junit.framework.TestCase;
044:
045: /**
046: * Randomly excutes methods on the HsqlList data structures and compares the
047: * results with equivalent calls on the java vector class.
048: *
049: * @author dnordahl@users
050: */
051: public class TestDataStructures extends TestCase {
052:
053: private static final int NUMBER_OF_TEST_RUNS = 100000;
054: private static final int NUMBER_OF_ITERATIONS_PER_RUN = 80;
055: private Random randomGenerator;
056:
057: //Commands
058: private static final int ADD = 1;
059: private static final int ADD_AT = 2;
060: private static final int GET = 3;
061: private static final int REMOVE = 4;
062: private static final int SET = 5;
063: private static final int OPTIMIZE = 6;
064: private static final int REMOVE_ALL = 7;
065: private Vector listCommandsCalled;
066:
067: /** Creates a new instance of TestDataStructures */
068: public TestDataStructures(String s) {
069:
070: super (s);
071:
072: randomGenerator = new Random(System.currentTimeMillis());
073: listCommandsCalled = new Vector(NUMBER_OF_ITERATIONS_PER_RUN);
074: }
075:
076: /** Runs a test on the hsqldb lists */
077: public void testLists() {
078:
079: HsqlArrayList arrayList = new HsqlArrayList();
080: HsqlLinkedList linkedList = new HsqlLinkedList();
081: Vector vector = new Vector();
082: Vector listCommandsCalled = new Vector(
083: NUMBER_OF_ITERATIONS_PER_RUN);
084: Integer tempInt = null;
085: int tempCommandCode;
086: int tempPosition;
087: boolean arrayListException = false;
088: boolean linkedListException = false;
089: boolean vectorException = false;
090: Object arrayListObject = null;
091: Object linkedListObject = null;
092: Object vectorObject = null;
093:
094: for (int i = 0; i < getRandomInt(3, 12); i++) { // prime the contents with a couple items
095: tempInt = getRandomInteger();
096:
097: arrayList.add(tempInt);
098: linkedList.add(tempInt);
099: 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 && vectorException)) {
250: if (!(arrayListException && vectorException)) {
251: System.out
252: .println("Exception descrepancy with vector and arraylist");
253: } else if (!(linkedListException && vectorException)) {
254: System.out
255: .println("Exception descrepancy with vector and linkedlist");
256: } else {
257: System.out
258: .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
336: .println("LinkList object returned inconsistent");
337:
338: return false;
339: } else if (!aObject.equals(vObject)) {
340: System.out
341: .println("ArrayList object returned inconsistent");
342:
343: return false;
344: } else {
345: return true;
346: }
347: } catch (NullPointerException ex) {
348: return false;
349: }
350: }
351:
352: /** Returns a random integer in the range of the lowBound and highBound */
353: private int getRandomInt(int lowBound, int highBound) {
354:
355: double random = randomGenerator.nextDouble();
356:
357: return ((int) (((highBound - lowBound) * random) + .5))
358: + lowBound;
359: }
360:
361: /**
362: * Returns an Integer object with a value between Integer.MIN_VALUE and
363: * Integer.MAX_VALUE
364: */
365: private Integer getRandomInteger() {
366: return new Integer(getRandomInt(0,
367: (int) (Integer.MAX_VALUE / 100.0)));
368: }
369:
370: /** Tells whether the given list contains the same data as the vector */
371: private boolean equalsVector(HsqlList list, Vector vector) {
372:
373: if (list.size() != vector.size()) {
374: return false;
375: }
376:
377: org.hsqldb.lib.Iterator listElements = list.iterator();
378: Enumeration vectorElements = vector.elements();
379: Object listObj = null;
380: Object vectorObj = null;
381:
382: while (listElements.hasNext()) {
383: listObj = listElements.next();
384: vectorObj = vectorElements.nextElement();
385:
386: if (!listObj.equals(vectorObj)) {
387: return false;
388: }
389: }
390:
391: return true;
392: }
393:
394: public void testGrowth() {
395:
396: HsqlArrayList d = new HsqlArrayList();
397:
398: for (int i = 0; i < 12; i++) {
399: d.add(new Integer(i));
400: }
401:
402: for (int i = 0; i < d.size(); i++) {
403: System.out.println(d.get(i));
404: }
405:
406: d = new HsqlArrayList();
407:
408: for (int i = 0; i < 12; i++) {
409: d.add(new Integer(i));
410: }
411:
412: d.set(11, new Integer(11));
413:
414: for (int i = 0; i < d.size(); i++) {
415: System.out.println(d.get(i));
416: }
417:
418: org.hsqldb.lib.Iterator it = d.iterator();
419:
420: for (int i = 0; it.hasNext(); i++) {
421: Integer value = (Integer) it.next();
422:
423: System.out.println(value);
424: assertEquals(i, value.intValue());
425: }
426:
427: //-
428: assertEquals(12, d.size());
429: }
430:
431: public void testSpeed() {
432:
433: randomGenerator = new Random(System.currentTimeMillis());
434:
435: int TEST_RUNS = 100000;
436: int LOOP_COUNT = 1000;
437: HsqlArrayList arrayList = new HsqlArrayList(TEST_RUNS);
438: ArrayList utilArrayList = new ArrayList(TEST_RUNS);
439: Vector vector = new Vector(TEST_RUNS);
440: Integer value = new Integer(randomGenerator.nextInt());
441: Integer INT_0 = new Integer(0);
442: StopWatch sw = new StopWatch();
443:
444: System.out.println(sw.currentElapsedTimeToMessage("time"));
445:
446: for (int i = 0; i < TEST_RUNS; i++) {
447: arrayList.add(INT_0);
448: }
449:
450: for (int i = 0; i < TEST_RUNS; i++) {
451: for (int j = 0; j < LOOP_COUNT; j++) {
452: arrayList.set(i, INT_0);
453: }
454: }
455:
456: System.out.println(sw.currentElapsedTimeToMessage("time"));
457: sw.zero();
458:
459: for (int i = 0; i < TEST_RUNS; i++) {
460: utilArrayList.add(INT_0);
461: }
462:
463: for (int i = 0; i < TEST_RUNS; i++) {
464: for (int j = 0; j < LOOP_COUNT; j++) {
465: utilArrayList.set(i, INT_0);
466: }
467: }
468:
469: System.out.println(sw.currentElapsedTimeToMessage("time"));
470: sw.zero();
471:
472: for (int i = 0; i < TEST_RUNS; i++) {
473: vector.addElement(INT_0);
474: }
475:
476: for (int i = 0; i < TEST_RUNS; i++) {
477: for (int j = 0; j < LOOP_COUNT; j++) {
478: vector.setElementAt(INT_0, i);
479: }
480: }
481:
482: System.out.println(sw.currentElapsedTimeToMessage("time"));
483: }
484:
485: public static void main(String[] args) {
486:
487: TestDataStructures test = new TestDataStructures("testLists");
488:
489: for (int i = 0; i < NUMBER_OF_TEST_RUNS; i++) {
490: test.testLists();
491:
492: if (i % 1000 == 0) {
493: System.out.println("Finished " + i + " tests");
494: System.out.flush();
495: }
496: }
497:
498: System.out.println("After " + NUMBER_OF_TEST_RUNS
499: + " tests of a maximum of "
500: + NUMBER_OF_ITERATIONS_PER_RUN
501: + " list commands each test, the list tests passed");
502: test.testGrowth();
503: }
504: }
|