import java.util.*;

/* 
 * Internal class to provide memory store for the various values generated
 * when trying to determine a hash function for a particular set of keys.
 */
class HashFunctionDetails
{
  public int remainder;
  public int biggestIndex;
  public int smallestIndex;
  public int collectionSize;
  public int memoryFactor;
  public int divisor;
  public String toString()
  {
    StringBuffer sb = new StringBuffer();
    sb.append("remainder: ").append(remainder);
    sb.append(" biggestIndex: ").append(biggestIndex);
    sb.append(" smallestIndex: ").append(smallestIndex);
    sb.append(" collectionSize: ").append(collectionSize);
    sb.append(" memoryFactor: ").append(memoryFactor);
    sb.append(" divisor: ").append(divisor);
    return sb.toString();
  }
}

/*
 * A simple key class
 */
class Key {
  int id;
  public Key(int id) {this.id = id;}
  public int hashCode() {return id;}
  public boolean equals(Object o) {return (o instanceof Key) && ( ((Key)o).id == id);}
}

/*
 * Minimal perfect hashmap class, uses the perfect hashmap tables
 * to produce the minimal mapping.
 *
 * I've optimized the class so that only one extra array lookup is needed,
 * rather than going through an instance of a PerfectHashMap
 */
class MinimalPerfectKeyHashMap
{

  //Key array from the perfect hashmap
  Key[] keys;
  //array of values for the keys from the perfect hashmap. Each key
  //maps to an integer from 0 to the size of the key set, giving us
  //our minimal perfect hashmap
  int[] map;
  //The values array
  Object[] values;
  //The divisor argument for the remainder operator
  int hfRemainder;

  MinimalPerfectKeyHashMap(int size, Key[] keys, int[] map, int remainder)
  {
    this.keys = keys;
    values = new Object[size];
    this.map = map;
    this.hfRemainder = remainder;
  }

  public void put(Key key, Object value)
  {
    int index = key.id % hfRemainder;
    keys[index] = key;
    values[map[index]] = value;
  }

  public Object get(Key key)
  {
    //optimized to avoid the extra variable. Note that this means
    //we are not testing that the key is equal, which may not be
    //appropriate for every application.
    //int index = key.id % hfRemainder;
    return values[map[key.id % hfRemainder]];
  }
}

public class PerfectKeyHashMap
{

  //Keys array
  Key[] keys;
  //The values array
  Object[] values;
  //The divisor argument for the remainder operator
  int hfRemainder;

  PerfectKeyHashMap(int remainder, int size)
  {
    hfRemainder = remainder;
    keys = new Key[size];
    values = new Object[size];
  }

  public void put(Key key, Object value)
  {
    int index = key.id % hfRemainder;
    keys[index] = key;
    values[index] = value;
  }

  public Object get(Key key)
  {
    //Note that we are not testing that the key is equal,
    //which may not be appropriate for every application.
    int index = key.id % hfRemainder;
    return values[index];
  }

  //The following are all to help determine the perfect hash functions.
  static final int KEY_POOL_SIZE = 500;
  static Random random;

  static Key[] keyPool = new Key[KEY_POOL_SIZE];
  static Key[] workingKeyPool = new Key[KEY_POOL_SIZE];
  static void initializeRandom() {random = new Random(543212345);}
  static {initializeRandom(); for (int i = 0; i < keyPool.length; i++) keyPool[i] = new Key(0);}
  static int keyPoolSize = KEY_POOL_SIZE;

  static HashFunctionDetails reusableHashFunctionDetails = new HashFunctionDetails();
  static intHashMap cachedHashMap = new intHashMap();
  static int[] indexes = new int[KEY_POOL_SIZE];


  public static void main(String[] args)
    throws Exception
  {
     if(args.length < 1)
     {
       System.out.println("Ignore the first set of results. They are to ensure HotSpot optimizations kick in before measurements start. Otherwise the repeated tests of any one class using different sizes gets skewed in favor of the second test.");
       testSimpleRemainderSpeed(1000);
       System.out.println("Starting measureable tests.");
       testSimpleRemainderSpeed(10000);

       testSimpleRemainder();
     }
     else if (args[0].toUpperCase().equals("TEST_SIMPLE_REMAINDER"))
       testSimpleRemainder();
     else if (args[0].toUpperCase().equals("TEST_SIMPLE_REMAINDER_SPEED"))
     {
       System.out.println("Ignore the first set of results. They are to ensure HotSpot optimizations kick in before measurements start. Otherwise the repeated tests of any one class using different sizes gets skewed in favor of the second test.");
       testSimpleRemainderSpeed(1000);
       System.out.println("Starting measureable tests.");
       testSimpleRemainderSpeed(10000);
     }
  }

  /* Test lots of randomly generated sets of keys for their sizes
   * to get the biggest and averages
   */
  public static void testSimpleRemainder()
    throws Exception
  {
    int REPEAT = 10000;
    initializeRandom();
    int biggestFactor = 0;
    int totalMemoryFactor = 0;
    int i;
    int tests = 0;
    for (int j = 1; j <= REPEAT; j++)
    {
      tests++;
      if ( (i = testSimpleRemainder1()) > biggestFactor)
      {
        totalMemoryFactor += i;
        biggestFactor = i;
        System.out.println("New biggest memory factor: " + biggestFactor + " out of " +
		tests + " tests");
      }
      else
      {
        totalMemoryFactor += i;
      }
      if (tests % 1000 == 0) System.out.println("Test " + tests);
    }
    System.out.println("Average memory factor is: " + (totalMemoryFactor/tests));
  }

  public static int testSimpleRemainder1()
    throws Exception
  {
    int size = setWorkingPool();
    return getPerfectMap(workingKeyPool, size).memoryFactor;
  }

  /* Create the random set of keys
   */
  static int setWorkingPool()
  {
    cachedHashMap.clear();
    keyPoolSize = KEY_POOL_SIZE;
    int randomSize = random.nextInt(KEY_POOL_SIZE-4)+5; //5-500
    for (int i = randomSize-1; i >= 0; i--)
    {
      keyPool[--keyPoolSize].id = random.nextInt(9999)+1; //1-10000
      workingKeyPool[i] = keyPool[keyPoolSize];
      while(cachedHashMap.put(workingKeyPool[i].id, Boolean.TRUE) == Boolean.TRUE)
      {
        workingKeyPool[i].id = random.nextInt(9999)+1;
      }
    }
    return randomSize;
  }

  /* Work out the perfect hash function details for this key set.
   * Keep trying remainders until one produces a unique set.
   */
  public static HashFunctionDetails getPerfectMap(Key[] keys, int poolSize)
  {
    int remainder = poolSize;
    while(!testRemainder(remainder, keys, indexes, cachedHashMap, poolSize))
    {
      remainder++;
    }
    int biggestKey = cachedHashMap.biggestKey();
    reusableHashFunctionDetails.remainder = remainder;
    reusableHashFunctionDetails.biggestIndex = biggestKey;
    reusableHashFunctionDetails.smallestIndex = cachedHashMap.smallestKey();
    reusableHashFunctionDetails.collectionSize = poolSize;
    reusableHashFunctionDetails.memoryFactor = ((biggestKey/poolSize)+1);
    return reusableHashFunctionDetails;
  }

  /* Work out the perfect hash function details for this key set
   */
  public static boolean testRemainder(int remainder, Key[] keys, int[] indexes, intHashMap intmap, int poolSize)
  {
      intmap.clear();
      //Assign keys to the hash. If the assignment doesn't return a previous
      //assignment, then it is unique, otherwise it duplicates another key value
      //return false.
      for (int i = 0; i < poolSize; i++)
      {
        indexes[i] = keys[i].id % remainder;
        if (intmap.put(indexes[i], Boolean.TRUE) == Boolean.TRUE)
          return false;
      }
      return true;
  }

  public static void testSimpleRemainderSpeed(int REPEAT)
    throws Exception
  {
//    int REPEAT = 10000;
    initializeRandom();
    int size = setWorkingPool();
    getPerfectMap(workingKeyPool, size);
    int divisor = reusableHashFunctionDetails.remainder;
    int initialCapacity = 89;
    while(initialCapacity < size) {initialCapacity = initialCapacity*2 + 1;}
    HashMap standardMap;
    PerfectKeyHashMap myMap;

    long totalPutTime = 0;
    long totalPut2Time = 0;
    long totalGetTime = 0;
    long time;
    Object o;
    for (int j = 1; j < REPEAT; j++)
    {
      standardMap = new HashMap(initialCapacity * reusableHashFunctionDetails.memoryFactor);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        standardMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        standardMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = standardMap.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;

      standardMap = null;
    }
    System.out.println("Time taken to update standard HashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor 
         + ") is: " + totalPutTime);
    System.out.println("Time taken to update2 standard HashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor 
         + ") is: " + totalPut2Time);
    System.out.println("Time taken to read standard HashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor
         + ") is: " + totalGetTime);
    System.out.println();

    totalPutTime = 0;
    totalPut2Time = 0;
    totalGetTime = 0;
    for (int j = 1; j < REPEAT; j++)
    {
      standardMap = new HashMap(initialCapacity);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        standardMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        standardMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = standardMap.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;
     
      standardMap = null;
    }
    System.out.println("Time taken to update standard HashMap("
         + initialCapacity +  ") is: " + totalPutTime);
    System.out.println("Time taken to update2 standard HashMap("
         + initialCapacity +  ") is: " + totalPut2Time);
    System.out.println("Time taken to read standard HashMap("
         + initialCapacity + ") is: " + totalGetTime);
    System.out.println();

    totalPutTime = 0;
    totalPut2Time = 0;
    totalGetTime = 0;
    KeyHashMap keymap;
    for (int j = 1; j < REPEAT; j++)
    {
      keymap = new KeyHashMap(initialCapacity);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        keymap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        keymap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = keymap.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;
     
      keymap = null;
    }
    System.out.println("Time taken to update KeyHashMap("
         + initialCapacity +  ") is: " + totalPutTime);
    System.out.println("Time taken to update2 KeyHashMap("
         + initialCapacity +  ") is: " + totalPut2Time);
    System.out.println("Time taken to read KeyHashMap("
         + initialCapacity + ") is: " + totalGetTime);
    System.out.println();

    totalPutTime = 0;
    totalPut2Time = 0;
    totalGetTime = 0;
    for (int j = 1; j < REPEAT; j++)
    {
      keymap = new KeyHashMap(initialCapacity * reusableHashFunctionDetails.memoryFactor);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        keymap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        keymap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = keymap.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;
     
      keymap = null;
    }
    System.out.println("Time taken to update KeyHashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor 
         + ") is: " + totalPutTime);
    System.out.println("Time taken to update2 KeyHashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor 
         + ") is: " + totalPut2Time);
    System.out.println("Time taken to read KeyHashMap("
         + initialCapacity * reusableHashFunctionDetails.memoryFactor
         + ") is: " + totalGetTime);
    System.out.println();

    totalPutTime = 0;
    totalGetTime = 0;
    totalPut2Time = 0;
//System.out.println(reusableHashFunctionDetails);
    for (int j = 1; j <= REPEAT; j++)
    {
      myMap = new PerfectKeyHashMap(divisor, reusableHashFunctionDetails.biggestIndex+1);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        myMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        myMap.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = myMap.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;

      myMap = null;
    }
    System.out.println("Time taken to update PerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalPutTime);
    System.out.println("Time taken to update2 PerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalPut2Time);
    System.out.println("Time taken to update PerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalGetTime);
    System.out.println();

    PerfectKeyHashMap map = new PerfectKeyHashMap(divisor, reusableHashFunctionDetails.biggestIndex+1);
    for (int i = size-1; i >= 0; i--)
        map.put(workingKeyPool[i], new Integer(i));
    Key[] keysarray = map.keys;
    int[] maparray = new int[keysarray.length];
    for (int i = keysarray.length-1; i >= 0; i--)
        maparray[i] = (map.values[i] == null) ? -1 : ((Integer) (map.values[i])).intValue();
    MinimalPerfectKeyHashMap myMap2;
    for (int j = 1; j <= REPEAT; j++)
    {
      myMap2 = new MinimalPerfectKeyHashMap(size, keysarray, maparray, divisor);
      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        myMap2.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPutTime += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        myMap2.put(workingKeyPool[i], Boolean.TRUE);
      time = System.currentTimeMillis() - time;
      totalPut2Time += time;

      time = System.currentTimeMillis();
      for (int i = size-1; i >= 0; i--)
        o = myMap2.get(workingKeyPool[i]);
      time = System.currentTimeMillis() - time;
      totalGetTime += time;

      myMap2 = null;
    }
    System.out.println("Time taken to update MinimalPerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalPutTime);
    System.out.println("Time taken to update2 MinimalPerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalPut2Time);
    System.out.println("Time taken to update MinimalPerfectKeyHashMap("
         + divisor + ", " + (reusableHashFunctionDetails.biggestIndex+1) + ") is: " + totalGetTime);
    System.out.println();

  }

}

/* Optimized HashMap implementation for keys which are Key objects.
 */
class KeyHashMap
{

  protected KeyHashMapEntry table[];
  protected int count;
  protected int threshold;
  protected float loadFactor;

  public KeyHashMap() {this(89, 0.75f);}
  public KeyHashMap(int initialCapacity) {this(initialCapacity, 0.75f);}
  public KeyHashMap(int initialCapacity, float loadFactor)
  {
    if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal Load factor: "+
                                               loadFactor);
    if (initialCapacity==0)
      initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new KeyHashMapEntry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
  }

  public boolean isEmpty() {return count == 0;}
  public int size() {return count;}

  public Object get(Key key)
  {
    KeyHashMapEntry tab[] = table;
    //Assume no null keys
    int hash = key.id;
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (KeyHashMapEntry e = tab[index]; e != null; e = e.next)
      if ((e.hash == hash) && (key.id == e.key.id))
        return e.value;
    return null;
  }

  public Object put(Key key, Object value)
  {
    KeyHashMapEntry tab[] = table;
    int hash = 0;
    int index = 0;

    // First check if the key is already in the CustomHashMap.
    //If so, replace the value.

    //Assume no null keys
    hash = key.id;
    index = (hash & 0x7FFFFFFF) % tab.length;
    for (KeyHashMapEntry e = tab[index] ; e != null ; e = e.next)
    {
      if ((e.hash == hash) && (key.id == e.key.id))
      {
        Object old = e.value;
        e.value = value;
        return old;
      }
    }

    //Still here. Means that this is a new key.
    if (count >= threshold)
    {
      // Rehash the table if the threshold is exceeded
      rehash();

      tab = table;
      index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    KeyHashMapEntry e = new KeyHashMapEntry(hash, key, value, tab[index]);
    tab[index] = e;
    count++;
    return null;
  }

  private void rehash()
  {
    int oldCapacity = table.length;
    KeyHashMapEntry oldMap[] = table;

    int newCapacity = oldCapacity * 2 + 1;
    KeyHashMapEntry newMap[] = new KeyHashMapEntry[newCapacity];

    threshold = (int)(newCapacity * loadFactor);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;)
    {
      for (KeyHashMapEntry old = oldMap[i] ; old != null ; )
      {
        KeyHashMapEntry e = old;
        old = old.next;

        int index = (e.hash & 0x7FFFFFFF) % newCapacity;
        e.next = newMap[index];
        newMap[index] = e;
      }
    }
  }

}

/* Node class for KeyHashMap
 */
class KeyHashMapEntry
{
  int hash;
  Key key;
  Object value;
  KeyHashMapEntry next;

  protected KeyHashMapEntry(int hash, Key key, Object value, KeyHashMapEntry next)
  {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }
}



/* A HashMap implementation which has int keys and Object values.
 * For assistance in working out perfect hash functions.
 */
class intHashMap
{
  //Use nearest prime above 234347, which is 234361
  public intHashMap() {this(89, 0.75f);}

  protected intHashMapEntry table[];
  protected int count;
  protected int threshold;
  protected float loadFactor;

  public intHashMap(int initialCapacity) {this(initialCapacity, 0.75f);}
  public intHashMap(int initialCapacity, float loadFactor)
  {
    if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal Load factor: "+
                                               loadFactor);
    if (initialCapacity==0)
      initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new intHashMapEntry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
  }

  public boolean isEmpty() {return count == 0;}
  public int size() {return count;}

  public Object get(int key)
  {
    intHashMapEntry tab[] = table;

      int hash = key;
      int index = (hash & 0x7FFFFFFF) % tab.length;
      for (intHashMapEntry e = tab[index]; e != null; e = e.next)
        if ((e.hash == hash) && (key == e.key))
          return e.value;
    return null;
  }

  public Object put(int key, Object value)
  {
    intHashMapEntry tab[] = table;
    int hash = 0;
    int index = 0;

    // First check if the key is already in the CustomHashMap.
    //If so, replace the value.
      hash = key;
      index = (hash & 0x7FFFFFFF) % tab.length;
      for (intHashMapEntry e = tab[index] ; e != null ; e = e.next)
      {
        if ((e.hash == hash) && (key == e.key))
        {
          Object old = e.value;
          e.value = value;
          return old;
        }
      }

    //Still here. Means that this is a new key.
    if (count >= threshold)
    {
      // Rehash the table if the threshold is exceeded
      rehash();

      tab = table;
      index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    intHashMapEntry e = new intHashMapEntry(hash, key, value, tab[index]);
    tab[index] = e;
    count++;
    return null;
  }
  private void rehash()
  {
    int oldCapacity = table.length;
    intHashMapEntry oldMap[] = table;

    int newCapacity = oldCapacity * 2 + 1;
    intHashMapEntry newMap[] = new intHashMapEntry[newCapacity];

    threshold = (int)(newCapacity * loadFactor);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;)
    {
      for (intHashMapEntry old = oldMap[i] ; old != null ; )
      {
        intHashMapEntry e = old;
        old = old.next;

        int index = (e.hash & 0x7FFFFFFF) % newCapacity;
        e.next = newMap[index];
        newMap[index] = e;
      }
    }
  }

  public void clear()
  {
    intHashMapEntry tab[] = table;
    for (int index = tab.length; --index >= 0; )
      tab[index] = null;
    count = 0;
  }

  public int biggestKey()
  {
    intHashMapEntry tab[] = table;
    int biggest = Integer.MIN_VALUE;

    for (int i = tab.length ; i-- > 0 ;)
    {
      for (intHashMapEntry e = tab[i] ; e != null ; e = e.next)
      {
        if (biggest < e.key)
          biggest = e.key;
      }
    }
    return biggest;
  }

  public int smallestKey()
  {
    intHashMapEntry tab[] = table;
    int smallest = Integer.MAX_VALUE;

    for (int i = tab.length ; i-- > 0 ;)
    {
      for (intHashMapEntry e = tab[i] ; e != null ; e = e.next)
      {
        if (smallest > e.key)
          smallest = e.key;
      }
    }
    return smallest;
  }

  public void sortKeysInto(int arr[], int startKey, int endKey)
  {
    intHashMapEntry tab[] = table;
    int idx = startKey;
    for (int i = tab.length ; i-- > 0 ;)
    {
      for (intHashMapEntry e = tab[i] ; e != null ; e = e.next)
      {
        arr[idx++] = e.key;
      }
    }
    quicksort(arr, startKey, endKey);
  }

  public static void quicksort(int[] arr, int lo, int hi)
  {
    if( lo >= hi ) 
      return;

    int mid = ( lo + hi ) / 2;
    int tmp;
    int middle = arr[ mid ];

    if( arr[ lo ] > middle)
    {
      arr[ mid ] = arr[ lo ];
      arr[ lo ] = middle;
      middle = arr[ mid ];
    }

    if( middle > arr[hi])
    {
      arr[ mid ] = arr[ hi ];
      arr[ hi ] = middle;
      middle = arr[ mid ];

      if( arr[ lo ] > middle)
      {
        arr[ mid ] = arr[ lo ];
        arr[ lo ] = middle;
        middle = arr[ mid ];
      }
    }

    int left = lo + 1;
    int right = hi - 1;

    if( left >= right ) 
      return;

    for( ;; ) 
    {
      while( arr[ right ] > middle)
      {
        right--;
      }

      while( left < right && arr[ left ] <= middle)
      {
        left++;
      }

      if( left < right )
      {
        tmp = arr[ left ];
        arr[ left ] = arr[ right ];
        arr[ right ] = tmp;
        right--;
      }
      else
      {
        break;
      }
    }

    quicksort(arr, lo, left);
    quicksort(arr, left + 1, hi);
  }

}

class intHashMapEntry
{
  int hash;
  int key;
  Object value;
  intHashMapEntry next;

  protected intHashMapEntry(int hash, int key, Object value, intHashMapEntry next)
  {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }
}