import jdsl.Comparator;
import jdsl.InvalidKeyException;

import jdsl.Locator;
import jdsl.InvalidLocatorException;

import jdsl.tree.RedBlackTree;
import jdsl.dictionary.Dictionary;

import java.util.Random;
import java.util.TreeMap;

import com.objectspace.jgl.OrderedMap;


public class TestTree {

    public static void main(String[] args) {

	int MAX = 10000;

	int[] insert_array = new int[MAX];
	int[] remove_array = new int[MAX];

	Random rand = new Random( );

	for (int i = 0; i < MAX/10; ++i) 
	    insert_array[(0x7fffffff & rand.nextInt( )) % MAX] = 1;

	for (int i = 0; i < MAX/10; ++i)
	    remove_array[(0x7fffffff & rand.nextInt( )) % MAX] = 1;

	Dictionary dict = new Dictionary(new RedBlackTree( ));
	TreeMap    tree = new TreeMap( );
	OrderedMap map  = new OrderedMap(true);

	long start;
	long stop;

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    dict.insertItem(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Insert(" + MAX + "):mine = " + (stop - start));

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    tree.put(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Insert(" + MAX + "):java = " + (stop - start));

	start = System.currentTimeMillis( );
	
	for (int i = 0; i < MAX; ++i)
	    map.add(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Insert(" + MAX + "):jgl  = " + (stop - start)); 
	System.out.println("");

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    dict.findItem(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Find  (" + MAX + "):mine = " + (stop - start));

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    tree.get(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Find  (" + MAX + "):java = " + (stop - start));

	start = System.currentTimeMillis( );
	
	for (int i = 0; i < MAX; ++i)
	    map.get(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Find  (" + MAX + "):jgl  = " + (stop - start)); 
	System.out.println("");

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    dict.removeItem(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Remove(" + MAX + "):mine = " + (stop - start));

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    tree.remove(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Remove(" + MAX + "):java = " + (stop - start));

	start = System.currentTimeMillis( );
	
	for (int i = 0; i < MAX; ++i)
	    map.remove(new Integer(i), 1);

	stop  = System.currentTimeMillis( );
	System.out.println("Remove(" + MAX + "):jgl  = " + (stop - start)); 
	System.out.println("");

	for (int i = 0; i < MAX; ++i) {
	    dict.insertItem(new Integer(i), new Integer(i));
	    tree.put(new Integer(i), new Integer(i));
	}

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i) 
	    if (insert_array[i] == 1)
		dict.insertItem(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Random Insert:mine = " + (stop - start));

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    if (insert_array[i] == 1)
		tree.put(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Random Insert:java = " + (stop - start));

	start = System.currentTimeMillis( );
	
	for (int i = 0; i < MAX; ++i)
	    if (insert_array[i] == 1)
		map.add(new Integer(i), new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Random Insert:jgl  = " + (stop - start)); 
	System.out.println("");

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    if (remove_array[i] == 1)
		dict.removeItem(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Random Remove:mine = " + (stop - start));

	start = System.currentTimeMillis( );

	for (int i = 0; i < MAX; ++i)
	    if (remove_array[i] == 1)
		tree.remove(new Integer(i));

	stop  = System.currentTimeMillis( );
	System.out.println("Random Remove:java = " + (stop - start));

	start = System.currentTimeMillis( );
	
	for (int i = 0; i < MAX; ++i)
	    if (remove_array[i] == 1)
		map.remove(new Integer(i), 1);

	stop  = System.currentTimeMillis( );
	System.out.println("Random Remove:jgl  = " + (stop - start)); 
	System.out.println("");
	
    }	
}