| /* Copyright (c) 2001-2010, The HSQL Development Group |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are met: |
| * |
| * Redistributions of source code must retain the above copyright notice, this |
| * list of conditions and the following disclaimer. |
| * |
| * Redistributions in binary form must reproduce the above copyright notice, |
| * this list of conditions and the following disclaimer in the documentation |
| * and/or other materials provided with the distribution. |
| * |
| * Neither the name of the HSQL Development Group nor the names of its |
| * contributors may be used to endorse or promote products derived from this |
| * software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, |
| * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| |
| package org.hsqldb.test; |
| |
| import java.util.ArrayList; |
| import java.util.Enumeration; |
| import java.util.Random; |
| import java.util.Vector; |
| |
| import org.hsqldb.lib.HsqlArrayList; |
| import org.hsqldb.lib.HsqlLinkedList; |
| import org.hsqldb.lib.HsqlList; |
| import org.hsqldb.lib.StopWatch; |
| |
| import junit.framework.TestCase; |
| |
| /** |
| * Randomly excutes methods on the HsqlList data structures and compares the |
| * results with equivalent calls on the java vector class. |
| * |
| * @author dnordahl@users |
| */ |
| public class TestDataStructures extends TestCase { |
| |
| private static final int NUMBER_OF_TEST_RUNS = 100000; |
| private static final int NUMBER_OF_ITERATIONS_PER_RUN = 80; |
| private Random randomGenerator; |
| |
| //Commands |
| private static final int ADD = 1; |
| private static final int ADD_AT = 2; |
| private static final int GET = 3; |
| private static final int REMOVE = 4; |
| private static final int SET = 5; |
| private static final int OPTIMIZE = 6; |
| private static final int REMOVE_ALL = 7; |
| private Vector listCommandsCalled; |
| |
| /** Creates a new instance of TestDataStructures */ |
| public TestDataStructures(String s) { |
| |
| super(s); |
| |
| randomGenerator = new Random(System.currentTimeMillis()); |
| listCommandsCalled = new Vector(NUMBER_OF_ITERATIONS_PER_RUN); |
| } |
| |
| /** Runs a test on the hsqldb lists */ |
| public void testLists() { |
| |
| HsqlArrayList arrayList = new HsqlArrayList(); |
| HsqlLinkedList linkedList = new HsqlLinkedList(); |
| Vector vector = new Vector(); |
| Vector listCommandsCalled = new Vector(NUMBER_OF_ITERATIONS_PER_RUN); |
| Integer tempInt = null; |
| int tempCommandCode; |
| int tempPosition; |
| boolean arrayListException = false; |
| boolean linkedListException = false; |
| boolean vectorException = false; |
| Object arrayListObject = null; |
| Object linkedListObject = null; |
| Object vectorObject = null; |
| |
| for (int i = 0; i < getRandomInt(3, 12); i++) { // prime the contents with a couple items |
| tempInt = getRandomInteger(); |
| |
| arrayList.add(tempInt); |
| linkedList.add(tempInt); |
| vector.addElement(tempInt); |
| listCommandsCalled.addElement("Add"); |
| } |
| |
| compareLists(arrayList, linkedList, vector); |
| |
| for (int j = 0; j < NUMBER_OF_ITERATIONS_PER_RUN; j++) { |
| tempCommandCode = getRandomInt(0, 15); // 0 and 8 are ignored or used for a special op |
| |
| switch (tempCommandCode) { |
| |
| case ADD : |
| tempInt = getRandomInteger(); |
| |
| listCommandsCalled.addElement("Add"); |
| arrayList.add(tempInt); |
| linkedList.add(tempInt); |
| vector.addElement(tempInt); |
| break; |
| |
| case ADD_AT : |
| tempInt = getRandomInteger(); |
| tempPosition = getRandomInt(0, vector.size()); |
| |
| listCommandsCalled.addElement("Add at " + tempPosition); |
| |
| try { |
| arrayList.add(tempPosition, tempInt); |
| } catch (Exception ex) { |
| arrayListException = true; |
| } |
| |
| try { |
| linkedList.add(tempPosition, tempInt); |
| } catch (Exception ex) { |
| linkedListException = true; |
| } |
| |
| try { |
| vector.insertElementAt(tempInt, tempPosition); |
| } catch (Exception ex) { |
| vectorException = true; |
| } |
| break; |
| |
| case GET : |
| tempPosition = getRandomInt(0, vector.size() -1); |
| |
| listCommandsCalled.addElement("Get " + tempPosition); |
| |
| try { |
| arrayListObject = arrayList.get(tempPosition); |
| } catch (Exception ex) { |
| arrayListException = true; |
| } |
| |
| try { |
| linkedListObject = linkedList.get(tempPosition); |
| } catch (Exception ex) { |
| linkedListException = true; |
| } |
| |
| try { |
| vectorObject = vector.elementAt(tempPosition); |
| } catch (Exception ex) { |
| vectorException = true; |
| } |
| break; |
| |
| case REMOVE : |
| tempPosition = getRandomInt(0, vector.size() - 1); |
| |
| listCommandsCalled.addElement("Remove " + tempPosition); |
| |
| try { |
| arrayListObject = arrayList.remove(tempPosition); |
| } catch (Exception ex) { |
| arrayListException = true; |
| } |
| |
| try { |
| linkedListObject = linkedList.remove(tempPosition); |
| } catch (Exception ex) { |
| linkedListException = true; |
| } |
| |
| try { |
| vectorObject = vector.elementAt(tempPosition); |
| |
| vector.removeElementAt(tempPosition); |
| } catch (Exception ex) { |
| vectorException = true; |
| } |
| break; |
| |
| case SET : |
| tempInt = getRandomInteger(); |
| tempPosition = getRandomInt(0, vector.size() -1); |
| |
| listCommandsCalled.addElement("Set " + tempPosition); |
| |
| try { |
| arrayList.set(tempPosition, tempInt); |
| } catch (Exception ex) { |
| arrayListException = true; |
| } |
| |
| try { |
| linkedList.set(tempPosition, tempInt); |
| } catch (Exception ex) { |
| linkedListException = true; |
| } |
| |
| try { |
| vector.setElementAt(tempInt, tempPosition); |
| } catch (Exception ex) { |
| vectorException = true; |
| } |
| break; |
| |
| case OPTIMIZE : |
| listCommandsCalled.addElement("Optimize"); |
| arrayList.trim(); |
| vector.trimToSize(); |
| break; |
| |
| case REMOVE_ALL : |
| if (getRandomInt(0, 5) == 4) { // to limit the frequency of this call |
| listCommandsCalled.addElement("Remove all"); |
| |
| if (vector.size() == 0) { |
| break; |
| } |
| |
| for (int k = arrayList.size() - 1; k >= 0; k--) { |
| arrayList.remove(k); |
| linkedList.remove(k); |
| } |
| |
| vector.removeAllElements(); |
| } |
| break; |
| |
| default : |
| } |
| |
| if (arrayListException || linkedListException || vectorException) { |
| |
| // if an exception is thrown in vector but not one of the lists or vice versa |
| if (!(arrayListException && linkedListException |
| && vectorException)) { |
| if (!(arrayListException && vectorException)) { |
| System.out.println( |
| "Exception descrepancy with vector and arraylist"); |
| } else if (!(linkedListException && vectorException)) { |
| System.out.println( |
| "Exception descrepancy with vector and linkedlist"); |
| } else { |
| System.out.println("Error in TestDataStructures"); |
| } |
| |
| this.printListCommandsCalled(listCommandsCalled); |
| fail("test failed"); |
| |
| //System.exit(0); |
| } |
| |
| return; |
| } |
| |
| if (!objectEquals(linkedListObject, arrayListObject, |
| vectorObject)) { |
| System.out.println("Objects returned inconsistent"); |
| this.printListCommandsCalled(listCommandsCalled); |
| fail("test failed"); |
| |
| //System.exit(0); |
| } |
| |
| compareLists(arrayList, linkedList, vector); |
| } |
| } |
| |
| /** |
| * Compare contents of lists to the vector. Print out stuff if they are |
| * inconsistent and exit. |
| */ |
| public void compareLists(HsqlArrayList arrayList, |
| HsqlLinkedList linkedList, Vector vector) { |
| |
| boolean arrayListError = false; |
| boolean linkedListError = false; |
| |
| if (!equalsVector(arrayList, vector)) { |
| System.out.println("Error in array list implementation"); |
| |
| arrayListError = true; |
| } |
| |
| if (!equalsVector(linkedList, vector)) { |
| System.out.println("Error in linked list implementation"); |
| |
| linkedListError = true; |
| } |
| |
| if (arrayListError || linkedListError) { |
| this.printListCommandsCalled(listCommandsCalled); |
| System.out.flush(); |
| fail("test failed"); |
| } |
| } |
| |
| /** Prints the list of commands called so far */ |
| public void printListCommandsCalled(Vector commands) { |
| |
| int commandCode = 0; |
| |
| for (int i = 0; i < commands.size(); i++) { |
| System.out.println((String) commands.elementAt(i)); |
| } |
| |
| System.out.flush(); |
| } |
| |
| /** Returns whether three objects are equal */ |
| private boolean objectEquals(Object lObject, Object aObject, |
| Object vObject) { |
| |
| if (lObject == null && aObject == null && vObject == null) { |
| return true; |
| } |
| |
| try { |
| if (!lObject.equals(vObject)) { |
| System.out.println("LinkList object returned inconsistent"); |
| |
| return false; |
| } else if (!aObject.equals(vObject)) { |
| System.out.println("ArrayList object returned inconsistent"); |
| |
| return false; |
| } else { |
| return true; |
| } |
| } catch (NullPointerException ex) { |
| return false; |
| } |
| } |
| |
| /** Returns a random integer in the range of the lowBound and highBound */ |
| private int getRandomInt(int lowBound, int highBound) { |
| |
| double random = randomGenerator.nextDouble(); |
| |
| return ((int) (((highBound - lowBound) * random) + .5)) + lowBound; |
| } |
| |
| /** |
| * Returns an Integer object with a value between Integer.MIN_VALUE and |
| * Integer.MAX_VALUE |
| */ |
| private Integer getRandomInteger() { |
| return new Integer(getRandomInt(0, (int) (Integer.MAX_VALUE / 100.0))); |
| } |
| |
| /** Tells whether the given list contains the same data as the vector */ |
| private boolean equalsVector(HsqlList list, Vector vector) { |
| |
| if (list.size() != vector.size()) { |
| return false; |
| } |
| |
| org.hsqldb.lib.Iterator listElements = list.iterator(); |
| Enumeration vectorElements = vector.elements(); |
| Object listObj = null; |
| Object vectorObj = null; |
| |
| while (listElements.hasNext()) { |
| listObj = listElements.next(); |
| vectorObj = vectorElements.nextElement(); |
| |
| if (!listObj.equals(vectorObj)) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| public void testGrowth() { |
| |
| HsqlArrayList d = new HsqlArrayList(); |
| |
| for (int i = 0; i < 12; i++) { |
| d.add(new Integer(i)); |
| } |
| |
| for (int i = 0; i < d.size(); i++) { |
| System.out.println(d.get(i)); |
| } |
| |
| d = new HsqlArrayList(); |
| |
| for (int i = 0; i < 12; i++) { |
| d.add(new Integer(i)); |
| } |
| |
| d.set(11, new Integer(11)); |
| |
| for (int i = 0; i < d.size(); i++) { |
| System.out.println(d.get(i)); |
| } |
| |
| org.hsqldb.lib.Iterator it = d.iterator(); |
| |
| for (int i = 0; it.hasNext(); i++) { |
| Integer value = (Integer) it.next(); |
| |
| System.out.println(value); |
| assertEquals(i, value.intValue()); |
| } |
| |
| //- |
| assertEquals(12, d.size()); |
| } |
| |
| public void testSpeed() { |
| |
| randomGenerator = new Random(System.currentTimeMillis()); |
| |
| int TEST_RUNS = 100000; |
| int LOOP_COUNT = 1000; |
| HsqlArrayList arrayList = new HsqlArrayList(TEST_RUNS); |
| ArrayList utilArrayList = new ArrayList(TEST_RUNS); |
| Vector vector = new Vector(TEST_RUNS); |
| Integer value = new Integer(randomGenerator.nextInt()); |
| Integer INT_0 = new Integer(0); |
| StopWatch sw = new StopWatch(); |
| |
| System.out.println(sw.currentElapsedTimeToMessage("time")); |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| arrayList.add(INT_0); |
| } |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| for (int j = 0; j < LOOP_COUNT; j++) { |
| arrayList.set(i, INT_0); |
| } |
| } |
| |
| System.out.println(sw.currentElapsedTimeToMessage("time HsqlArrayLsit")); |
| sw.zero(); |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| utilArrayList.add(INT_0); |
| } |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| for (int j = 0; j < LOOP_COUNT; j++) { |
| utilArrayList.set(i, INT_0); |
| } |
| } |
| |
| System.out.println(sw.currentElapsedTimeToMessage("time ArrayList")); |
| sw.zero(); |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| vector.addElement(INT_0); |
| } |
| |
| for (int i = 0; i < TEST_RUNS; i++) { |
| for (int j = 0; j < LOOP_COUNT; j++) { |
| vector.setElementAt(INT_0, i); |
| } |
| } |
| |
| System.out.println(sw.currentElapsedTimeToMessage("time Vector")); |
| } |
| |
| public static void main(String[] args) { |
| |
| TestDataStructures test = new TestDataStructures("testLists"); |
| |
| for (int i = 0; i < NUMBER_OF_TEST_RUNS; i++) { |
| test.testLists(); |
| |
| if (i % 1000 == 0) { |
| System.out.println("Finished " + i + " tests"); |
| System.out.flush(); |
| } |
| } |
| |
| System.out.println( |
| "After " + NUMBER_OF_TEST_RUNS + " tests of a maximum of " |
| + NUMBER_OF_ITERATIONS_PER_RUN |
| + " list commands each test, the list tests passed"); |
| test.testGrowth(); |
| } |
| } |