Java/Ant issues

ant build file

<project name="Project 3" default="compile" basedir=".">

  <description>
    A build file for Project 3
  </description>
  
  <!-- global properties for this build file -->
  <property name="source.dir" location="src"/>
  <property name="build.dir" location="bin"/>
  <property name="doc.dir" location="doc"/>
  <!-- <property name="main.class" value="Proj1.class"/> -->
  
  <!-- set up some directories used by this project -->
  <target name="init" description="setup project directories">
    <mkdir dir="${build.dir}"/>
    <mkdir dir="${doc.dir}"/>
  </target>
  
  <!-- Compile the java code in ${src.dir} into ${build.dir} -->
  <target name="compile" depends="init" description="compile java sources">
    <javac srcdir="${source.dir}" destdir="${build.dir}"/>
  </target>

  <!-- execute the program with the fully qualified name in ${build.dir} -->
  <target name="run" description="run the project">
    <java dir="${build.dir}" classname="BinarySearchTree" fork="yes">
    	
    </java>
  </target>
	
  <!-- Delete the build & doc directories and Emacs backup (*~) files -->
  <target name="clean" description="tidy up the workspace">
    <delete dir="${build.dir}"/>
    <delete dir="${doc.dir}"/>
    <delete>
      <fileset defaultexcludes="no" dir="${source.dir}" includes="**/*~"/>
    </delete>
  </target>

  <!-- Generate javadocs for current project into ${doc.dir} -->
  <target name="doc" depends="init" description="generate documentation">
    <javadoc sourcepath="${source.dir}" destdir="${doc.dir}" sourcefiles="src/BinarySearchTree.java"/>
  </target>

</project>

Random Binary Search Tree

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Random;
import java.util.Scanner;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// boolean contains( x )  --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// int size( )            --> Return number of elements of the tree
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
 * Implements an unbalanced binary search tree. Note that all "matching" is
 * based on the compareTo method.
 * 
 * @author Kevin Qualters
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
	/**
	 * Construct the tree.
	 */
	public BinarySearchTree() {
		root = null;
	}

	/**
	 * Insert into the tree; duplicates are ignored.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void insert(AnyType x) {
		root = insert(x, root);
	}

	/**
	 * Insert into the tree; duplicates are ignored.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void randomizeinsert(AnyType x) {
		root = randomizedinsert(x, root);
	}

	/**
	 * Return the number of levels of the tree.
	 * 
	 */

	public int height() {
		return height(root);
	}

	private static Random random = new Random(123456789);

	/**
	 * Remove from the tree. Nothing is done if x is not found.
	 * 
	 * @param x
	 *            the item to remove.
	 */
	public void remove(AnyType x) {
		root = remove(x, root);
	}

	/**
	 * Find the smallest item in the tree.
	 * 
	 * @return smallest item or null if empty.
	 * @throws Exception
	 */
	public AnyType findMin() throws Exception {
		if (isEmpty())
			throw new Exception();
		return findMin(root).element;
	}

	/**
	 * Find the largest item in the tree.
	 * 
	 * @return the largest item of null if empty.
	 * @throws Exception
	 */
	public AnyType findMax() throws Exception {
		if (isEmpty())
			throw new Exception();
		return findMax(root).element;
	}

	/**
	 * Find an item in the tree.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return true if not found.
	 */
	public boolean contains(AnyType x) {
		return contains(x, root);
	}

	/**
	 * Make the tree logically empty.
	 */
	public void makeEmpty() {
		root = null;
	}

	/**
	 * Test if the tree is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * Print the tree contents in sorted order.
	 */
	public void printTree() {
		if (isEmpty())
			System.out.println("Empty tree");
		else
			printTree(root);
	}

	/**
	 * Print the tree contents in level order.
	 */
	public void orderPrintTree(int L) {
		for (int i = 0; i <= L && i < height(); i++) {
			System.out.print("Lavel " + i + ": ");
			printElement(root, i, 0);
			System.out.print("\n");
		}

	}

	private void printElement(BinaryNode<AnyType> t, int L, int currentLevel) {
		if (t != null) {
			printElement(t.left, L, currentLevel + 1);
			if (currentLevel == L)
				System.out.print(t.element + " ");
			printElement(t.right, L, currentLevel + 1);
		}

	}

	/**
	 * Internal method to insert into a subtree.
	 * 
	 * @param x
	 *            the item to insert.
	 * @param t
	 *            the node that roots the subtree.
	 * @return the new root of the subtree.
	 */
	private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
		if (t == null)
			return new BinaryNode<AnyType>(x, null, null);

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0) {
			t.left = insert(x, t.left);
			t.size++;
		} else if (compareResult > 0) {
			t.right = insert(x, t.right);
			t.size++;
		}

		else
			; // Duplicate; do nothing
		return t;
	}

	private BinaryNode<AnyType> insert(BinaryNode<AnyType> node,
			BinaryNode<AnyType> t) {
		if (t == null)
			return node;

		int compareResult = node.element.compareTo(t.element);

		if (compareResult < 0) {
			t.left = insert(node, t.left);
			t.size++;
		} else if (compareResult > 0) {
			t.right = insert(node, t.right);
			t.size++;
		}

		else
			; // Duplicate; do nothing
		return t;
	}

	/**
	 * Internal method to insert into a subtree.
	 * 
	 * @param x
	 *            the item to insert.
	 * @param t
	 *            the node that roots the subtree.
	 * @return the new root of the subtree.
	 */
	private BinaryNode<AnyType> randomizedinsert(AnyType x,
			BinaryNode<AnyType> t) {
		if (t == null)
			return new BinaryNode<AnyType>(x, null, null);

		int r = random.nextInt(t.size + 1);
		// System.out.println("Size: " + t.size + ", r: " + r);
		if (r == t.size) {
			System.out.println("Insert at root " + t.element + " node " + x);
			return insertAtRoot(x, t);

		} else {
			int compareResult = x.compareTo(t.element);

			if (compareResult < 0)
				t.left = randomizedinsert(x, t.left);
			else if (compareResult > 0)
				t.right = randomizedinsert(x, t.right);
			else
				; // Duplicate; do nothing
		}
		t.size = ((t.left != null) ? t.left.size : 0)
				+ ((t.right != null) ? t.right.size : 0) + 1;
		return t;
	}

	private BinaryNode<AnyType> insertAtRoot(AnyType x, BinaryNode<AnyType> t) {
		BinaryNode<AnyType> temp = new BinaryNode<AnyType>(x);
		insert(temp, t);
		rotateElement(temp, t);
		return temp;
	}

	/**
	 * Internal method to remove from a subtree.
	 * 
	 * @param x
	 *            the item to remove.
	 * @param t
	 *            the node that roots the subtree.
	 * @return the new root of the subtree.
	 */
	private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
		if (t == null)
			return t; // Item not found; do nothing

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			t.left = remove(x, t.left);
		else if (compareResult > 0)
			t.right = remove(x, t.right);
		else if (t.left != null && t.right != null) // Two children
		{
			t.element = findMin(t.right).element;
			t.right = remove(t.element, t.right);
		} else
			t = (t.left != null) ? t.left : t.right;
		return t;
	}

	/**
	 * Internal method to find the smallest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the subtree.
	 * @return node containing the smallest item.
	 */
	private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
		if (t == null)
			return null;
		else if (t.left == null)
			return t;
		return findMin(t.left);
	}

	/**
	 * Internal method to find the largest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the subtree.
	 * @return node containing the largest item.
	 */
	private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
		if (t != null)
			while (t.right != null)
				t = t.right;

		return t;
	}

	/**
	 * Internal method to find an item in a subtree.
	 * 
	 * @param x
	 *            is item to search for.
	 * @param t
	 *            the node that roots the subtree.
	 * @return node containing the matched item.
	 */
	private boolean contains(AnyType x, BinaryNode<AnyType> t) {
		if (t == null)
			return false;

		int compareResult = x.compareTo(t.element);

		if (compareResult < 0)
			return contains(x, t.left);
		else if (compareResult > 0)
			return contains(x, t.right);
		else
			return true; // Match
	}

	/**
	 * Internal method to print a subtree in sorted order.
	 * 
	 * @param t
	 *            the node that roots the subtree.
	 */
	private void printTree(BinaryNode<AnyType> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element + " size = " + t.size);
			printTree(t.right);
		}
	}

	/**
	 * Internal method to compute height of a subtree.
	 * 
	 * @param t
	 *            the node that roots the subtree.
	 */
	private int height(BinaryNode<AnyType> t) {
		if (t == null)
			return 0;
		else
			return 1 + Math.max(height(t.left), height(t.right));
	}

	private void rotateWithLeft(BinaryNode<AnyType> k2,
			BinaryNode<AnyType> parent, String side) {
		BinaryNode<AnyType> k1 = k2.left;
		k2.left = k1.right;
		k2.size = 1 + ((k2.right != null) ? k2.right.size : 0)
				+ ((k2.left != null) ? k2.left.size : 0);
		k1.right = k2;
		k1.size = 1 + ((k1.right != null) ? k1.right.size : 0)
				+ ((k1.left != null) ? k1.left.size : 0);
		if (side.equals("left"))
			parent.left = k1;
		else if (side.equals("right"))
			parent.right = k1;
		else
			root = k1;
	}

	private void rotateWithRight(BinaryNode<AnyType> k2,
			BinaryNode<AnyType> parent, String side) {
		BinaryNode<AnyType> k1 = k2.right;
		k2.right = k1.left;
		k2.size = 1 + ((k2.right != null) ? k2.right.size : 0)
				+ ((k2.left != null) ? k2.left.size : 0);
		k1.left = k2;
		k1.size = 1 + ((k1.right != null) ? k1.right.size : 0)
				+ ((k1.left != null) ? k1.left.size : 0);
		if (side.equals("left"))
			parent.left = k1;
		else if (side.equals("right"))
			parent.right = k1;
		else
			root = k1;
	}

	private void rotateElement(BinaryNode<AnyType> x, BinaryNode<AnyType> t) {
		int n = height(t) - height(x);
		AnyType value = x.element;
		for (int i = 0; i < n; i++) {
			rotateElementHelper(root, null, value, "root");
		}
	}

	private void rotateElementHelper(BinaryNode<AnyType> t,
			BinaryNode<AnyType> parent, AnyType value, String side) {
		if (t.left != null)
			if (t.left.element == value)
				rotateWithLeft(t, parent, side);
			else
				rotateElementHelper(t.left, t, value, "left");
		if (t.right != null)
			if (t.right.element == value)
				rotateWithRight(t, parent, side);
			else
				rotateElementHelper(t.right, t, value, "right");
	}

	// Basic node stored in unbalanced binary search trees
	private static class BinaryNode<AnyType> {
		// Constructors
		BinaryNode(AnyType theElement) {
			this(theElement, null, null);
		}

		BinaryNode(AnyType theElement, BinaryNode<AnyType> lt,
				BinaryNode<AnyType> rt) {
			element = theElement;
			left = lt;
			right = rt;
			size = (lt != null ? lt.size : 0) + (rt != null ? rt.size : 0) + 1;
		}

		AnyType element; // The data in the node
		BinaryNode<AnyType> left; // Left child
		BinaryNode<AnyType> right; // Right child
		int size;// size of the subtree
	}

	/** The tree root. */
	private BinaryNode<AnyType> root;

	// Test program
	public static void main(String[] args)throws Exception{
		try{
			BinarySearchTree<Integer> BST = new BinarySearchTree<Integer>();
		
		BinarySearchTree<Integer> RBST = new BinarySearchTree<Integer>();
		String arg0=args[0];
		System.out.println(arg0);
		int L = Integer.parseInt(arg0);
		String fileName = args[1];
		Scanner file = new Scanner(new File(fileName));
		while (file.hasNext()) {
			int x = file.nextInt();
			BST.insert(x);
			RBST.randomizeinsert(x);
		}
		file.close();
		System.out.println("\nHeight of the normal BST: " + (BST.height() - 1));
		System.out.println("Height of the randomized BST: "
				+ (RBST.height() - 1));
		System.out.println("\nLevel order print of the normal BST");
		BST.orderPrintTree(L);
		System.out.println("\nLevel order print of the randomized BST");
		RBST.orderPrintTree(L);
		System.out.print("\n");
		}
		catch(Exception e){
			System.out.println("Please enter valid arguments");		
		}
	}
}