//
// File:        AutoTest.java
//
// Language:    Java 1.02
// Description: Automatic testing of a "SkipList" proposed by William Pugh
//
//              Tests run automatically on different skip lists.
//              You can edit the constant parameters in the array.
//
// Author:  Thomas Wenger, Jan-7-1998
//

import java.util.Random;    // Randomizer to produce test input

public class AutoTest {

  ///////////////////////////////////////////////////////////////////////////
  // array of constants to stear the test:
  //   Make changes here to verify performance of other parameters
  //
  public static final float[]   PROBABILITY      = { 0.50f  };
  public static final int[]     INITIAL_LOAD     = { 20000, 40000, 80000 };
  public static final boolean[] INPUT_IS_SORTED  = { false, true };
  public static final int NUM_OF_TEST_OPERATIONS = 1000;


  ///////////////////////////////////////////////////////////////////////////
  // main:
  //
  public static void main(String args[])  throws java.io.IOException {
 

    System.out.println("Testing skip-list. Please wait.");
    
    // perform tests for all kind of input keys:
    for (int sortSel=0; sortSel<INPUT_IS_SORTED.length; sortSel++) {
      
      String s = (INPUT_IS_SORTED[sortSel]? "sorted." : "random order.");
      System.out.println("Keys are " + s);

      // perform tests for all number of keys basically in list:
      for (int numSel=0; numSel<INITIAL_LOAD.length; numSel++) {

        System.out.println("  Size of list: " + INITIAL_LOAD[numSel] 
                                + " elements."); 
        //
        // prepare the test input in an array;
        //
        Random rnd = new Random(1234);   // get a randomizer with seed=1234
        int[] keys = new int[INITIAL_LOAD[numSel]];
        for (int i=0; i<INITIAL_LOAD[numSel]; i++) {
          keys[i] = (INPUT_IS_SORTED[sortSel]? i : Math.abs(rnd.nextInt()-1) );			
        }
        
        // perform tests for all probabilities:
        for (int probSel=0; probSel<PROBABILITY.length; probSel++) {

          System.out.println("    Probability: " + PROBABILITY[probSel]); 

          //
          // init the skip list as wished:
          //
          float prob = PROBABILITY[probSel];
          int numb = INITIAL_LOAD[numSel];
          
          // calculate maxLevel according to paper:
          int maxLevel = (int)Math.ceil(Math.log(numb) / Math.log(1/prob))-1;

          // use constructor (2) to build a skip exactly as wished:
          SkipList aSkipList = new SkipList(prob, maxLevel);
                
          // insert great number of elements before we measure:
          
          // execute the insertions:
          for (int i=0; i<INITIAL_LOAD[numSel]; i++) {
            aSkipList.insert(keys[i], 0);
          }
          

          // begin with time measurements:
          
          ///////////////////////////////////////////////////////////////////
          // search some elements:
          //
          
          // get system time before start:
          long start = System.currentTimeMillis();
          
          // execute the searches:
          for (int i=0; i<NUM_OF_TEST_OPERATIONS; i++) {
            aSkipList.search(keys[i]);
          }
          
          // get system time after search and calculate duration:
          long stop = System.currentTimeMillis();
          float duration = stop - start;
          
          // output results:
          System.out.println("      Search took " + duration/NUM_OF_TEST_OPERATIONS
                                        + " ms per element.");
          
          ///////////////////////////////////////////////////////////////////
          // delete some elements:
          //
          
          // get system time before start:
          start = System.currentTimeMillis();
          
          // execute the deletions:
          for (int i=0; i<NUM_OF_TEST_OPERATIONS; i++) {
            aSkipList.delete(keys[i]);
          }
          
          // get system time after deletion and calculate duration:
          stop = System.currentTimeMillis();
          duration = stop - start;
          
          // output results:
          System.out.println("      Delete took " + duration/NUM_OF_TEST_OPERATIONS
                                       + " ms per element.");

          
          ///////////////////////////////////////////////////////////////////
          // insert some elements:
          //
          
          // get system time before start:
          start = System.currentTimeMillis();
          
          // execute the deletions:
          for (int i=0; i<NUM_OF_TEST_OPERATIONS; i++) {
            aSkipList.insert(keys[i],0);
          }
          
          // get system time after deletion and calculate duration:
          stop = System.currentTimeMillis();
          duration = stop - start;
          
          // output results:
          System.out.println("      Insert took " + duration/NUM_OF_TEST_OPERATIONS
                                         + " ms per element.");
          System.out.println();
        }
      }
    }
    
    // wait for a key to be pressed:
    System.out.println("Press enter key to continue.");
    java.io.DataInputStream in = new java.io.DataInputStream(System.in);
    String dummy = in.readLine();
  }

}