Java Small Problems and Programs.

A Hello World! Java program.
/* 
 * @author Usman Mughal
 */

public class HelloWorld
{
	public static void main(String[] args) {
		System.out.println("Hello World!");
	}
}


Calling Methods. A sample of how to call methods in the same class.
/* 
 * @author Usman Mughal
 * illustrates how to call static methods a class
 * from a method in the same class
 */

public class CallingMethodsInSameClass
{
	public static void main(String[] args) {
		printOne();
		printOne();
		printTwo();
	}

	public static void printOne() {
		System.out.println("Hello World");
	}

	public static void printTwo() {
		printOne();
		printOne();
	}
}


For loop.
/* 
 * @author Usman Mughal
 */

public class Factorial
{
	public static void main(String[] args)
	{	final int NUM_FACTS = 100;
		for(int i = 0; i < NUM_FACTS; i++)
			System.out.println( i + "! is " + factorial(i));
	}
	
	public static int factorial(int n)
	{	int result = 1;
		for(int i = 2; i <= n; i++)
			result *= i;
		return result;
	}
}


Enhanced for loop.
/* 
 * @author Usman Mughal
 */
public class EnhancedFor
{
	public static void main(String[] args)
	{	int[] list ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int sum = sumListEnhanced(list);
		System.out.println("Sum of elements in list: " + sum);

		System.out.println("Original List");
		printList(list);
		System.out.println("Calling addOne");
		addOne(list);
		System.out.println("List after call to addOne");
		printList(list);
		System.out.println("Calling addOneError");
		addOneError(list);
		System.out.println("List after call to addOneError. Note elements of list did not change.");
		printList(list);
	}

	// pre: list != null
	// post: return sum of elements
	// uses enhanced for loop
	public static int sumListEnhanced(int[] list)
	{	int total = 0;
		for(int val : list)
		{	total += val;
		}
		return total;
	}

	// pre: list != null
	// post: return sum of elements
	// use traditional for loop
	public static int sumListOld(int[] list)
	{	int total = 0;
		for(int i = 0; i < list.length; i++)
		{	total += list[i];
			System.out.println( list[i] );
		}
		return total;
	}

	// pre: list != null
	// post: none.
	// The code appears to add one to every element in the list, but does not
	public static void addOneError(int[] list)
	{	for(int val : list)
		{	val = val + 1;
		}
	}

	// pre: list != null
	// post: adds one to every element of list
	public static void addOne(int[] list)
	{	for(int i = 0; i < list.length; i++)
		{	list[i]++;
		}
	}

	public static void printList(int[] list)
	{	System.out.println("index, value");
		for(int i = 0; i < list.length; i++)
		{	System.out.println(i + ", " + list[i]);
		}
	}
}


Value Parameters.
/* 
 * @author Usman Mughal
 */
public class PrimitiveParameters
{	
	public static void main(String[] args)
	{	go();
	}
	
	public static void go()
	{	int x = 3;
		int y = 2;
		System.out.println("In method go. x: " + x + " y: " + y);
		falseSwap(x,y);
		System.out.println("in method go. x: " + x + " y: " + y);
		moreParameters(x,y);
		System.out.println("in method go. x: " + x + " y: " + y);
	}
	
	public static void falseSwap(int x, int y)
	{	System.out.println("in method falseSwap. x: " + x + " y: " + y);
		int temp = x;
		x = y;
		y = temp;
		System.out.println("in method falseSwap. x: " + x + " y: " + y);
	}
	
	public static void moreParameters(int a, int b)
	{	System.out.println("in method moreParameters. a: " + a + " b: " + b);
		a = a * b;
		b = 12;
		System.out.println("in method moreParameters. a: " + a + " b: " + b);
		falseSwap(b,a);
		System.out.println("in method moreParameters. a: " + a + " b: " + b);	
	}
}


String Example.
/* 
 * @author Usman Mughal
 */
public class StringExample
{	public static void main(String[] args)
	{	String s1 = "Computer Science";
		int x = 307;
		String s2 = s1 + " " + x;
		String s3 = s2.substring(10,17);
		String s4 = "is fun";
		String s5 = s2 + s4;
		
		System.out.println("s1: " + s1);
		System.out.println("s2: " + s2);
		System.out.println("s3: " + s3);
		System.out.println("s4: " + s4);
		System.out.println("s5: " + s5);
		
		//showing effect of precedence
		
		x = 3;
		int y = 5;
		String s6 = x + y + "total";
		String s7 = "total " + x + y;
		String s8 = " " + x + y + "total";
		System.out.println("s6: " + s6);
		System.out.println("s7: " + s7);
		System.out.println("s8: " + s8);
	}
}


BinaryConverter.
/* 
 * @author Usman Mughal
 */

public class BinaryConverter {
    
    public static void main(String[] args){
        for(int i = -5; i < 33; i++){
            System.out.println(i + ": " + toBinary(i));
            System.out.println(i);
            //always another way
            System.out.println(i + ": " + Integer.toBinaryString(i));
        }
    }
    
    /*
     * pre: none
     * post: returns a String with base10Num in base 2
     */
    public static String toBinary(int base10Num){
        boolean isNeg = base10Num < 0;
        base10Num = Math.abs(base10Num);        
        String result = "";
        
        while(base10Num > 1){
            result = (base10Num % 2) + result;
            base10Num /= 2;
        }
        assert base10Num == 0 || base10Num == 1 : "value is not <= 1: " + base10Num;
        
        result = base10Num + result;
        assert all0sAnd1s(result);
        
        if( isNeg )
            result = "-" + result;
        return result;
    }
    
    /*
     * pre: cal != null
     * post: return true if val consists only of characters 1 and 0, false otherwise
     */
    public static boolean all0sAnd1s(String val){
        assert val != null : "Failed precondition all0sAnd1s. parameter cannot be null";
        boolean all = true;
        int i = 0;
        char c;
        
        while(all && i < val.length()){
            c = val.charAt(i);
            all = c == '0' || c == '1';
            i++;
        }
        return all;
    }
}


PrimeEx.
/* 
 * @author Usman Mughal
 */
import java.math.BigInteger;
import java.util.Random;

public class PrimeEx {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		printTest(10, 4);
		printTest(2, 2);
		printTest(54161329, 4);
		printTest(1882341361, 2);
		printTest(36, 9);

		System.out.println(isPrime(54161329) + " expect false");
		System.out.println(isPrime(1882341361) + " expect true");
		System.out.println(isPrime(2) + " expect true");
		int numPrimes = 0;
		Stopwatch s = new Stopwatch();
		s.start();
		for(int i = 2; i < 10000000; i++) {
			if(isPrime(i)) {
				numPrimes++;
			}
		}
		s.stop();
		System.out.println(numPrimes + " " + s);
		s.start();
		boolean[] primes = getPrimes(10000000);
		int np = 0;
		for(boolean b : primes)
			if(b)
				np++;
		s.stop();
		System.out.println(np + " " + s);

		System.out.println(new BigInteger(1024, 10, new Random()));
	}

	public static boolean[] getPrimes(int max) {
		boolean[] result = new boolean[max + 1];
		for(int i = 2; i < result.length; i++)
			result[i] = true;
		final double LIMIT = Math.sqrt(max);
		for(int i = 2; i <= LIMIT; i++) {
			if(result[i]) {
				// cross out all multiples;
				int index = 2 * i;
				while(index < result.length){
					result[index] = false;
					 index += i;
				}
			}
		}
		return result;
	}


	public static void printTest(int num, int expectedFactors) {
		Stopwatch st = new Stopwatch();
		st.start();
		int actualFactors = numFactors(num);
		st.stop();
		System.out.println("Testing " + num + " expect " + expectedFactors + ", " +
				"actual " + actualFactors);
		if(actualFactors == expectedFactors)
			System.out.println("PASSED");
		else
			System.out.println("FAILED");
		System.out.println(st.time());
	}

	// pre: num >= 2
	public static boolean isPrime(int num) {
		assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
		final double LIMIT = Math.sqrt(num);
		boolean isPrime = (num == 2) ? true : num % 2 != 0;
		int div = 3;
		while(div <= LIMIT && isPrime) {
			isPrime = num % div != 0;
			div += 2;
		}
		return isPrime;
	}

	// pre: num >= 2
	public static int numFactors(int num) {
		assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
		int result = 0;
		final double SQRT = Math.sqrt(num);
		for(int i = 1; i < SQRT; i++) {
			if(num % i == 0) {
				result += 2;
			}
		}
		if(num % SQRT == 0)
			result++;
		return result;
	}

}


Pointers as Value parameters.
/* 
 * @author Usman Mughal
 */
import java.awt.Rectangle;

public class ObjectVarsAsParameters
{	public static void main(String[] args)
	{	go();
	}
	
	public static void go()
	{	Rectangle r1 = new Rectangle(0,0,5,5);
		System.out.println("In method go. r1 " + r1 + "\n");
		// could have been 
		//System.out.prinltn("r1" + r1.toString());
		r1.setSize(10, 15);
		System.out.println("In method go. r1 " + r1 + "\n");
		alterPointee(r1);
		System.out.println("In method go. r1 " + r1 + "\n");
		
		alterPointer(r1);
		System.out.println("In method go. r1 " + r1 + "\n");
	}
	
	public static void alterPointee(Rectangle r)
	{	System.out.println("In method alterPointee. r " + r + "\n");
		r.setSize(20, 30);
		System.out.println("In method alterPointee. r " + r + "\n");
	}
	
	public static void alterPointer(Rectangle r)
	{	System.out.println("In method alterPointer. r " + r + "\n");
		r = new Rectangle(5, 10, 30, 35);
		System.out.println("In method alterPointer. r " + r + "\n");
	}
}


Array Examples.
/* 
 * @author Usman Mughal
 */
//Mike Scott
//examples of array manipulations

public class ArrayExamples
{	public static void main(String[] args)
	{	int[] list = {1, 2, 3, 4, 1, 2, 3};
		findAndPrintPairs(list, 5);
		bubblesort(list);
		showList(list);

		list = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
		bubblesort(list);
		showList(list);

		list = new int[]{11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2};
		bubblesort(list);
		showList(list);

		list = new int[]{1};
		bubblesort(list);
		showList(list);
	}


	// pre: list != null, list.length > 0
	// post: return index of minimum element of array
	public static int findMin(int[] list)
	{	assert list != null && list.length > 0 : "failed precondition";

		int indexOfMin = 0;
		for(int i = 1; i < list.length; i++)
		{	if(list[i] < list[indexOfMin])
			{	indexOfMin = i;
			}
		}

		return indexOfMin;
	}


	/*
	 *pre: list != null, newSize >= 0
	 *post: nothing. the method does not succeed it resizing the
	 * argument
	 */
	public static void badResize(int[] list, int newSize)
	{	assert list != null && newSize >= 0 : "failed precondition";

		int[] temp = new int[newSize];
		int limit = Math.min(list.length, newSize);

		for(int i = 0; i < limit; i++)
		{	temp[i] = list[i];
		}

		// uh oh!! Changing pointer, not pointee. This breaks the
		// relationship between the parameter and argument
		list = temp;
	}


	/*
	 *pre: list != null, newSize >= 0
	 *post: returns an array of size newSize. Elements from 0 to newSize - 1
	 *	will be copied into the new array
	 */
	public static int[] goodResize(int[] list, int newSize)
	{	assert list != null && newSize >= 0 : "failed precondition";

		int[] result = new int[newSize];
		int limit = Math.min(list.length, newSize);

		for(int i = 0; i < limit; i++)
		{	result[i] = list[i];
		}

		return result;
	}


	/*
	 *pre: list != null
	 *post: prints out the indices and values of all pairs of numbers
	 *in list such that list[a] + list[b] = target
	 */
	public static void findAndPrintPairs(int[] list, int target)
	{	assert list != null : "failed precondition";

		for(int i = 0; i < list.length; i++)
		{	for(int j = i + 1; j < list.length; j++)
			{	if(list[i] + list[j] == target)
				{	System.out.println("The two elements at indices " + i + " and " + j
						+ " are " + list[i] + " and " + list[j] + " add up to " + target);
				}
			}
		}
	}


	/*
	 *pre: list != null;
	 *post: sort the elements of list so that they are in ascending order
	 */
	public static void bubblesort(int[] list)
	{
		assert list != null : "failed precondition";

		int temp;
		boolean changed = true;
		for(int i = 0; i < list.length && changed; i++)
		{	changed = false;
			for(int j = 0; j < list.length - i - 1; j++)
			{	assert (j > 0) && (j + 1 < list.length) : "loop counter j " + j +
					"is out of bounds.";
				if(list[j] > list[j+1])
				{	changed = true;
					temp = list[j + 1];
					list[j + 1] = list[j];
					list[j] = temp;
				}
			}
		}

		assert isAscending( list );
	}


	public static void showList(int[] list)
	{	for(int i = 0; i < list.length; i++)
			System.out.print( list[i] + " " );
		System.out.println();
	}

	/* 	pre: list != null
		post: return true if list is sorted in ascedning order, false otherwise
	*/
	public static boolean isAscending( int[] list )
	{	boolean ascending = true;
		int index = 1;
		while( ascending && index < list.length )
		{	assert index >= 0 && index < list.length;

			ascending = (list[index - 1] <= list[index]);
			index++;
		}

		return ascending;
	}
}


2D array Example.

A simplified version of filtering a picture represented by ints.

/* 
 * @author Usman Mughal
 */
import java.awt.Color;


public class FilterExample
{
	/*
	 *pre: image != null, image.length > 1, image[0].length > 1
	 *	image is a rectangular matrix, neighberhoodSize > 0
	 *post: return a smoothed version of image
	 */
	public Color[][] smooth(Color[][] image, int neighberhoodSize)
	{	//check precondition
		assert image != null && image.length > 1 && image[0].length > 1
				&& ( neighberhoodSize > 0 ) && rectangularMatrix( image )
				: "Violation of precondition: smooth";

		Color[][] result = new Color[image.length][image[0].length];

		for(int row = 0; row < image.length; row++)
		{	for(int col = 0; col < image[0].length; col++)
			{	result[row][col] = aveOfNeighbors(image, row, col, neighberhoodSize);
			}
		}

		return result;
	}


	// helper method that determines the average color of a neighberhood
	// around a particular cell.
	private Color aveOfNeighbors(Color[][] image, int row, int col, int neighberhoodSize)
	{	int numNeighbors = 0;
		int red = 0;
		int green = 0;
		int blue = 0;

		for(int r = row - neighberhoodSize; r <= row + neighberhoodSize; r++)
		{	for(int c = col - neighberhoodSize; c <= col + neighberhoodSize; c++)
			{	if( inBounds( image, r, c ) )
				{	numNeighbors++;
					red += image[r][c].getRed();
					green += image[r][c].getGreen();
					blue += image[r][c].getBlue();
				}
			}
		}

		assert numNeighbors > 0;
		return new Color( red / numNeighbors, green / numNeighbors, blue / numNeighbors );
	}

	//helper method to determine if given coordinates are in bounds
	private boolean inBounds(Color[][] image, int row, int col)
	{	return (row >= 0) && (row <= image.length) && (col >= 0)
				&& (col < image[0].length);
	}

	//private method to ensure mat is rectangular
	private boolean rectangularMatrix( Color[][] mat )
	{	boolean isRectangular = true;
		int row = 1;
		final int COLUMNS = mat[0].length;

		while( isRectangular && row < mat.length )
		{	isRectangular = ( mat[row].length == COLUMNS );
			row++;
		}

		return isRectangular;
	}
}


2D array example.

Very simple version of the Conway's Game of Life.

/* 
 * @author Usman Mughal
 */
import java.util.Scanner;

public class Life {
    public static void show(boolean[][] grid){
        String s = "";
        for(boolean[] row : grid){
            for(boolean val : row)
                if(val)
                    s += "*";
                else
                    s += ".";
            s += "\n";
        }
        System.out.println(s);
    }
    
    public static boolean[][] gen(){
        boolean[][] grid = new boolean[10][10];
        for(int r = 0; r < 10; r++)
            for(int c = 0; c < 10; c++)
                if( Math.random() > 0.7 )
                    grid[r][c] = true;
        return grid;
    }
    
    public static void main(String[] args){
        boolean[][] world = gen();
        show(world);
        System.out.println();
        world = nextGen(world);
        show(world);
        Scanner s = new Scanner(System.in);
        while(s.nextLine().length() == 0){
            System.out.println();
            world = nextGen(world);
            show(world);
            
        }
    }
    
    public static boolean[][] nextGen(boolean[][] world){
        boolean[][] newWorld 
            = new boolean[world.length][world[0].length];
        int num;
        for(int r = 0; r < world.length; r++){
            for(int c = 0; c < world[0].length; c++){
                num = numNeighbors(world, r, c);
                if( occupiedNext(num, world[r][c]) )
                    newWorld[r][c] = true;
            }
        }
        return newWorld;
    }
    
    public static boolean occupiedNext(int numNeighbors, boolean occupied){
        if( occupied && (numNeighbors == 2 || numNeighbors == 3))
            return true;
        else if (!occupied && numNeighbors == 3)
            return true;
        else
            return false;
    }

    private static int numNeighbors(boolean[][] world, int row, int col) {
        int num = world[row][col] ? -1 : 0;
        for(int r = row - 1; r <= row + 1; r++)
            for(int c = col - 1; c <= col + 1; c++)
                if( inbounds(world, r, c) && world[r][c] )
                    num++;

        return num;
    }

    private static boolean inbounds(boolean[][] world, int r, int c) {
        return r >= 0 && r < world.length && c >= 0 &&
        c < world[0].length;
    }
}


Getting input from Keyboard with Scanner class.
/* 
 * @author Usman Mughal
 */
import java.util.Scanner;

public class ScannerAndKeyboard
{
	public static void main(String[] args)
	{	Scanner s = new Scanner(System.in);
		System.out.print( "Enter your name: "  );
		String name = s.nextLine();
		System.out.println( "Hello " + name + "!" );
	}
}


Reading ints from file with Scanner class.
/* 
 * @author Usman Mughal
 */
import java.util.Scanner;
import java.io.File;
import java.io.IOException;

public class ReadAndPrintScores
{
    public static void main(String[] args)
    {	try
	{   Scanner s = new Scanner( new File("scores.dat") );
	    while( s.hasNextInt() )
	    {	System.out.println( s.nextInt() );
	    }
	}
	catch(IOException e)
	{	System.out.println( e );
	}
    }
}


Writing ints to file.
/* 
 * @author Usman Mughal
 */
//sample code to write 100 random ints to a file, 1 per line

import java.io.PrintStream;
import java.io.IOException;
import java.io.File;
import java.util.Random;

public class WriteToFile
{	public static void main(String[] args)
	{	try
		{	PrintStream writer = new PrintStream( new File("randInts.txt"));
			Random r = new Random();
			final int LIMIT = 100;

			for(int i = 0; i < LIMIT; i++)
			{	writer.println( r.nextInt() );
			}
			writer.close();
		}
		catch(IOException e)
		{	System.out.println("An error occured while trying to write to the file");
		}
	}
}


Connecting to and reading from a web page.
/* 
 * @author Usman Mughal
 */
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;
import java.util.Scanner;

public class URLExpSimple {
    public static void main(String[] args) {
        try {
            URL mySite = new URL("http://www.cs.utexas.edu/~scottm");
            URLConnection yc = mySite.openConnection();
            Scanner in = new Scanner(new InputStreamReader(yc.getInputStream()));
            int count = 0;
            while (in.hasNext()) {
                System.out.println(in.next());
                count++;
            }
            System.out.println("Number of tokens: " + count);
            in.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}


Program to create ASCII frequency table from file and url.

Demonstration of try / catch blocks.

/* 
 * @author Usman Mughal
 */
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.MalformedURLException;
import java.net.URL;

public class FreqTableExampleOriginal {

    public static final int NUM_ASCII_CHAR = 128;

    // program to create a frequency table.
    // Example of simple try catch blocks to deal with checked exceptions
    public static void main(String[] args)
        {

        int[] freqs = createFreqTableURL("http://www.utexas.edu/");

        if( freqs.length == 0)
            System.out.println("No frequency table created due to problems when reading from file");
        else{
            for(int i = 0; i < NUM_ASCII_CHAR; i++){
                System.out.println("charcater code: " + i + " ,character: " + (char)i + " ,frequency: " + freqs[i]);
            }
            System.out.println("Total characters in file: " + sum(freqs));
        }


        freqs = new int[]{};
        try{
            freqs = createTable("ciaFactBook2008.txt");
        }
        catch(FileNotFoundException e){
            System.out.println("File not found. Unable to create freq table" + e);
        }
        catch(IOException e){
            System.out.println("Problem while reading from file. Unable to create freq table" + e);
        }
        if( freqs.length == 0)
            System.out.println("No frequency table created due to problems when reading from file");
        else{
            for(int i = 0; i < freqs.length; i++){
                System.out.println("charcater code: " + i + " ,character: " + (char)i + " ,frequency: " + freqs[i]);
            }
            System.out.println("Total characters in file: " + sum(freqs));
        }

    }


    // return sum of ints in list
    // list may not be null
    private static int sum(int[] list) {
        assert list != null : "Failed precondition, sum: parameter list" +
            " may not be null.";
        int total = 0;
        for(int x : list){
            total += x;
        }
        return total;
    }


    // pre: url != null
    // Connect to the URL specified by the String url.
    // Map characters to index in array.
    // All non ASCII character dumped into one element of array
    // If IOException occurs message printed and array of
    // length 0 returned.
    public static int[] createFreqTableURL (String url){
        if(url == null)
            throw new IllegalArgumentException("Violation of precondition. parameter url must not be null.");

        int[] freqs = new int[NUM_ASCII_CHAR];
        try {
        URL inputURL = new URL(url);
        InputStreamReader in
            = new InputStreamReader(inputURL.openStream());

        while(in.ready()){
            int c = in.read();
            if(0 <= c && c < freqs.length)
                freqs[c]++;
            else
                System.out.println("Non ASCII char: " + c + " " + (char) c);
        }
        in.close();
        }
        catch(MalformedURLException e){
            System.out.println("Bad URL.");
            freqs = new int[0];
        }
        catch(IOException e){
            System.out.println("Unable to read from resource." + e);
            freqs = new int[0];
        }
        return freqs;
    }
    // Connect to the file specified by the String fileName.
    // Assumes it is in same directory as compiled code.
    // Map characters to index in array.
    public static int[] createTable(String fileName) throws FileNotFoundException, IOException{
        int[] freqs = new int[NUM_ASCII_CHAR];
        File f = new File(fileName);
        FileReader r = new FileReader(f);
        while( r.ready() ){
            int ch = r.read();
//            if( 0 <= ch && ch <= NUM_ASCII_CHAR)
//                freqs[ch]++;
//            else
//                freqs[INDEX_NON_ASCII]++;
            if(0 <= ch && ch < freqs.length)
                freqs[ch]++;
            else
                System.out.println((char) ch);
                
        }
        r.close();
        return freqs;
    }
}


IntListVer1.

First version of the IntList class developed in class. Developing class to illustrate various class design and implementation issues in Java.

/**
 * A class to provide a simple list of integers.
 * List resizes automatically. Used to illustrate 
 * various design and implementation details of 
 * a class in Java.
 * 
 * Version 1 only contains the instance variables and
 * the constructors
 * @author  Usman Mughal
 *
 */
public class IntListVer1 {
    // class constant for default size
    private static final int DEFAULT_CAP = 10;
    
    //instance variables
    private int[] iValues;
    private int iSize;
    
    /**
     * Default constructor. Creates an empty list.
     */
    public IntListVer1(){
        //redirect to single int constructor
        this(DEFAULT_CAP);
        //other statments could go here.
    }

    /**
     * Constructor to allow user of class to specify 
     * initial capacity in case they intend to add a lot
     * of elements to new list. Creates an empty list.
     * @param initialCap > 0
     */    
    public IntListVer1(int initialCap) {
        assert initialCap > 0 : "Violation of precondition. IntListVer1(int initialCap):"
            + "initialCap must be greater than 0. Value of initialCap: " + initialCap;
        iValues = new int[initialCap];
        iSize = 0;
    }
}


IntListTesterVer1
/* 
 * @author  Usman Mughal
 */
public class IntListTesterVer1 {
    public static void main(String[] args){
        IntListVer1 list1 = new IntListVer1();
        IntListVer1 list2 = new IntListVer1(100);
        
        //equal when empty?
        System.out.println("list1.equals(list2): " + list1.equals(list2));
        System.out.println("list1: " + list1);
        System.out.println("list2: " + list2);
    }
}


IntListVer2

Added default add method, equals method, and toString methods. Includes versions of toString using String concatenation and StringBuffer to illustarte performance differences.

/**
 * A class to provide a simple list of integers.
 * List resizes automatically. Used to illustrate 
 * various design and implementation details of 
 * a class in Java.
 * 
 * Version 1 only contains the instance variables and
 * the constructors
 * @author Usman Mughal
 *
 */
public class IntListVer2{
    // class constant for default size
    private static final int DEFAULT_CAP = 10;
    
    //instance variables
    // iValues store the elements of the list and 
    // may have extra capacity
    private int[] iValues;
    private int iSize;
    
    /**
     * Default add method. Add x to the end of this IntList.
     * Size of the list goes up by 1.
     * @param x The value to add to the end of this list.
     */
    public void add(int x){
        // is there extra capacity available?
        // if not, resize
        if(iSize == iValues.length)
            resize();
        assert 0 <= iSize && iSize < iValues.length;
        iValues[iSize] = x;
        iSize++;
    }
    
    // resize internal storage container by a factor of 2
    private void resize() {
        int[] temp = new int[iValues.length * 2];
        System.arraycopy(iValues, 0, temp, 0, iValues.length);
        iValues = temp;
    }
    
    /**
     * Return a String version of this list. Size and 
     * elements included.
     */
    public String toString(){
        // we could make this more effecient by using a StringBuffer.
        // See alternative version
        String result = "size: " + iSize + ", elements: [";
        for(int i = 0; i < iSize - 1; i++)
            result += iValues[i] + ", ";
        if(iSize > 0 )
            result += iValues[iSize - 1];
        result += "]";
        return result;
    }
    
    // Would not really have this and toString available
    // both included just for testing
    public String toStringUsingStringBuffer(){
        StringBuffer result = new StringBuffer();
        result.append( "size: " );
        result.append( iSize );
        result.append(", elements: [");
        for(int i = 0; i < iSize - 1; i++){
            result.append(iValues[i]);
            result.append(", ");
        }
        if( iSize > 0 )
            result.append(iValues[iSize - 1]);
        result.append("]");
        return result.toString();
    }

    /**
     * Default constructor. Creates an empty list.
     */
    public IntListVer2(){
        //redirect to single int constructor
        this(DEFAULT_CAP);
        //other statments could go here.
    }

    /**
     * Constructor to allow user of class to specify 
     * initial capacity in case they intend to add a lot
     * of elements to new list. Creates an empty list.
     * @param initialCap > 0
     */    
    public IntListVer2(int initialCap) {
        assert initialCap > 0 : "Violation of precondition. IntListVer1(int initialCap):"
            + "initialCap must be greater than 0. Value of initialCap: " + initialCap;
        iValues = new int[initialCap];
        iSize = 0;
    }
    
   /**
    * Return true if this IntList is equal to other.
* pre: none * @param other The object to comapre to this * @return true if other is a non null, IntList object * that is the same size as this IntList and has the * same elements in the same order, false otherwise. */ public boolean equals(Object other){ boolean result; if(other == null) // we know this is not null so can't be equal result = false; else if(this == other) // quick check if this and other refer to same IntList object result = true; else if( this.getClass() != other.getClass() ) // other is not an IntList they can't be equal result = false; else{ // other ris not null and refers to an IntList IntListVer2 otherIntList = (IntListVer2)other; result = this.iSize == otherIntList.iSize; int i = 0; while(i < iSize && result){ result = this.iValues[i] == otherIntList.iValues[i]; i++; } } return result; } }


IntListTesterVer2
/* 
 * @author Usman Mughal
 */

public class IntListTesterVer2 {
    public static void main(String[] args){
        IntListVer2 list1 = new IntListVer2();
        IntListVer2 list2 = new IntListVer2(100);
        
        //equal when empty?
        System.out.println("list1.equals(list2): " + list1.equals(list2));
        System.out.println("list1: " + list1);
        System.out.println("list2: " + list2);
        
        //add elements
        for(int i = 0; i < 100; i += 5){
            list1.add(i);
            list2.add(i);
        }
        
        System.out.println("list1.equals(list2): " + list1.equals(list2));
        System.out.println("list1: " + list1);
        System.out.println("list2: " + list2);
        
        list2.add(200);
        System.out.println("Added 200 to list2.");
        System.out.println("list1.equals(list2): " + list1.equals(list2));
        System.out.println("list1: " + list1);
        System.out.println("list2: " + list2);
        
        System.out.println("Testing efficieny of StringBuffer versus using String.");
        System.out.println("Increasing list1 size to 10000.");
        Stopwatch s = new Stopwatch();
        list1 = new IntListVer2();
        for(int i = 0; i < 10000; i++)
            list1.add(i);
        s.start();
        list1.toString();
        s.stop();
        System.out.println("Time to build String using String class: " + s.toString() );
        s.start();
        list1.toStringUsingStringBuffer();
        s.stop();
        System.out.println("Time to build String using StringBuffer class: " + s.toString() );

    }
}


IntListVer3.

Added insert and remove methods.

/**
 * A class to provide a simple list of integers.
 * List resizes automatically. Used to illustrate 
 * various design and implementation details of 
 * a class in Java.
 * 
 * Version 3 added the insert and remove methods. Changed the
 * add method to rely on insert.
 * @author Usman Mughal
 *
 */
public class IntListVer3{
    // class constant for default size
    private static final int DEFAULT_CAP = 10;
    
    //instance variables
    // iValues store the elements of the list and 
    // may have extra capacity
    private int[] iValues;
    private int iSize;
    
    /**
     * Default constructor. Creates an empty list.
     */
    public IntListVer3(){
        //redirect to single int constructor
        this(DEFAULT_CAP);
        //other statments could go here.
    }

    /**
     * Constructor to allow user of class to specify 
     * initial capacity in case they intend to add a lot
     * of elements to new list. Creates an empty list.
     * @param initialCap > 0
     */    
    public IntListVer3(int initialCap) {
        assert initialCap > 0 : "Violation of precondition. IntListVer1(int initialCap):"
            + "initialCap must be greater than 0. Value of initialCap: " + initialCap;
        iValues = new int[initialCap];
        iSize = 0;
    }
    
    /**
     * Default add method. Add x to the end of this IntList.
     * Size of the list goes up by 1.
     * @param x The value to add to the end of this list.
     */
    public void add(int x){
        //example of loose coupling
        insert(iSize, x);
    }
    
    /**
     * Retrieve an element from the list based on position.
     * @param pos 0 <= pos < size()
     * @return The element at the given position.
     */
    public int get(int pos){
        assert 0 <= pos && pos < size() : "Failed precondition get. " +
        		"pos it out of bounds. Value of pos: " + pos;
        return iValues[pos];
    }
    
    /**
     * Insert x at position pos. Elements with a position equal
     * to pos or more are shifted to the right. (One added to their
     * position.)
     * post: get(pos) = x, size() = old size() + 1
     * @param pos 0 <= pos <= size()
     * @param x
     */
    public void insert(int pos, int x){
        assert 0 <= pos && pos <= size() : "Failed precondition insert. " +
        "pos is invalid. Value of pos: " + pos;
        ensureCapcity();
        for(int i = iSize; i > pos; i--){
            iValues[i] = iValues[i - 1];
        }
        iValues[pos] = x;
        iSize++;
    }
    
    /**
     * Remove an element from the list based on position.
     * Elements with a position greater than pos
     * are shifted to the left. (One subtracted from their
     * position.)
     * @param pos 0 <= pos < size()
     * @return The element that is removed.
     */
    public int remove(int pos){
        assert 0 <= pos && pos < size() : "Failed precondition remove. " +
        "pos it out of bounds. Value of pos: " + pos;
        int removedValue = iValues[pos];
        for(int i = pos; i < iSize - 1; i++)
            iValues[i] = iValues[i + 1];
        iSize--;
        return removedValue;
    }
    
    private void ensureCapcity(){
        // is there extra capacity available?
        // if not, resize
        if(iSize == iValues.length)
            resize();
    }
    
    /**
     * Returns the size of the list.
     * @return The size of the list.
     */
    public int size(){
        return iSize;
    }
    
    // resize internal storage container by a factor of 2
    private void resize() {
        int[] temp = new int[iValues.length * 2];
        System.arraycopy(iValues, 0, temp, 0, iValues.length);
        iValues = temp;
    }
    
    /**
     * Return a String version of this list. Size and 
     * elements included.
     */
    public String toString(){
        // we could make this more effecient by using a StringBuffer.
        // See alternative version
        String result = "size: " + iSize + ", elements: [";
        for(int i = 0; i < iSize - 1; i++)
            result += iValues[i] + ", ";
        if(iSize > 0 )
            result += iValues[iSize - 1];
        result += "]";
        return result;
    }
    
    // Would not really have this and toString available
    // both included just for testing
    public String toStringUsingStringBuffer(){
        StringBuffer result = new StringBuffer();
        result.append( "size: " );
        result.append( iSize );
        result.append(", elements: [");
        for(int i = 0; i < iSize - 1; i++){
            result.append(iValues[i]);
            result.append(", ");
        }
        if( iSize > 0 )
            result.append(iValues[iSize - 1]);
        result.append("]");
        return result.toString();
    }
    
   /**
    * Return true if this IntList is equal to other.
* pre: none * @param other The object to comapre to this * @return true if other is a non null, IntList object * that is the same size as this IntList and has the * same elements in the same order, false otherwise. */ public boolean equals(Object other){ boolean result; if(other == null) // we know this is not null so can't be equal result = false; else if(this == other) // quick check if this and other refer to same IntList object result = true; else if( this.getClass() != other.getClass() ) // other is not an IntList they can't be equal result = false; else{ // other is not null and refers to an IntList IntListVer3 otherIntList = (IntListVer3)other; result = this.size() == otherIntList.size(); int i = 0; while(i < iSize && result){ result = this.iValues[i] == otherIntList.iValues[i]; i++; } } return result; } }


SortedIntList.

Inherits from InListVer3 to create a SortedIntList. Class is "broken" because random insertions still allowed.

/* 
 * @author Usman Mughal
 */
public class SortedIntList extends IntListVer3{
    
    public SortedIntList(int initialCap){
        //call IntList constructor
        super(initialCap);
    }
    
    public SortedIntList(){
        super();
    }
    
    //override add
    public void add(int value){
        //search for location to insert value
        int pos = 0;
        while( pos < size() && value > get(pos) ){
            pos++;
        }
        super.insert(pos, value);
    }
}


GenericList.

Altered the list to store anything, not just ints.


/**
 * A class to provide a simple list.
 * List resizes automatically. Used to illustrate 
 * various design and implementation details of 
 * a class in Java.
 * 
 * @author Usman Mughal
 *
 */
public class GenericList{
    // class constant for default size
    private static final int DEFAULT_CAP = 10;
    
    //instance variables
    // iValues store the elements of the list and 
    // may have extra capacity
    private Object[] iValues;
    private int iSize;
    
    /**
     * Default add method. Add x to the end of this IntList.
     * Size of the list goes up by 1.
     * @param x The value to add to the end of this list.
     */
    public void add(Object x){
        insert(iSize, x);
    }
    
    public Object get(int pos){
        return iValues[pos];
    }
    
    /**
     * Insert obj at position pos.
     * post: get(pos) = x, size() = old size() + 1
     * @param pos 0 <= pos <= size()
     * @param obj The element to add.
     */
    public void insert(int pos, Object obj){
        ensureCapcity();
        for(int i = iSize; i > pos; i--){
            iValues[i] = iValues[i - 1];
        }
        iValues[pos] = obj;
        iSize++;
    }
    
    public Object remove(int pos){
        Object removedValue = iValues[pos];
        for(int i = pos; i < iSize - 1; i++)
            iValues[i] = iValues[i + 1];
        iValues[iSize - 1] = null;
        iSize--;
        return removedValue;
    }
    
    private void ensureCapcity(){
        // is there extra capacity available?
        // if not, resize
        if(iSize == iValues.length)
            resize();
    }
    
    public int size(){
        return iSize;
    }
    
    // resize internal storage container by a factor of 2
    private void resize() {
        Object[] temp = new Object[iValues.length * 2];
        System.arraycopy(iValues, 0, temp, 0, iValues.length);
        iValues = temp;
    }
    
    /**
     * Return a String version of this list. Size and 
     * elements included.
     */
    public String toString(){
        // we could make this more effecient by using a StringBuffer.
        // See alternative version
        String result = "size: " + iSize + ", elements: [";
        for(int i = 0; i < iSize - 1; i++)
            result += iValues[i].toString() + ", ";
        if(iSize > 0 )
            result += iValues[iSize - 1];
        result += "]";
        return result;
    }
    
    // Would not really have this and toString available
    // both included just for testing
    public String toStringUsingStringBuffer(){
        StringBuffer result = new StringBuffer();
        result.append( "size: " );
        result.append( iSize );
        result.append(", elements: [");
        for(int i = 0; i < iSize - 1; i++){
            result.append(iValues[i]);
            result.append(", ");
        }
        if( iSize > 0 )
            result.append(iValues[iSize - 1]);
        result.append("]");
        return result.toString();
    }

    /**
     * Default constructor. Creates an empty list.
     */
    public GenericList(){
        //redirect to single int constructor
        this(DEFAULT_CAP);
        //other statments could go here.
    }

    /**
     * Constructor to allow user of class to specify 
     * initial capacity in case they intend to add a lot
     * of elements to new list. Creates an empty list.
     * @param initialCap > 0
     */    
    public GenericList(int initialCap) {
        assert initialCap > 0 : "Violation of precondition. IntListVer1(int initialCap):"
            + "initialCap must be greater than 0. Value of initialCap: " + initialCap;
        iValues = new Object[initialCap];
        iSize = 0;
    }
    
   /**
    * Return true if this IntList is equal to other.
* pre: none * @param other The object to comapre to this * @return true if other is a non null, IntList object * that is the same size as this IntList and has the * same elements in the same order, false otherwise. */ public boolean equals(Object other){ boolean result; if(other == null) // we know this is not null so can't be equal result = false; else if(this == other) // quick check if this and other refer to same IntList object result = true; else if( this.getClass() != other.getClass() ) // other is not an IntList they can't be equal result = false; else{ // other is not null and refers to an IntList GenericList otherList = (GenericList)other; result = this.size() == otherList.size(); int i = 0; while(i < iSize && result){ result = this.iValues[i].equals( otherList.iValues[i] ); i++; } } return result; } }


Die Class.

A class that models a playing die.

import java.util.Random;

/**
 * Models a playing die with sides numbered 1 to N.
 * All sides have uniform probablity of being rolled.
 *
 * @author Usman Mughal
 */
public class Die
{   public static final int DEFAULT_SIDES = 6;

    private static Random ourRandNumGen = new Random();

    private final int iMyNumSides;
    private int iMyResult;


    /**
     * Default constructor.

* pre: none
* post: getNumSides() = DEFAULT_SIDES, getResult() = 1 */ public Die() { this(DEFAULT_SIDES); } /** * Create a Die with numSides sides

* pre: numSides > 1
* post: getNumSides() = numSides, getResult() = 1
* An exception will be generated if the preconditions are not met */ public Die(int numSides) { assert numSides > 1 : "Violation of precondition: numSides = " + numSides + "numSides must be greater than 1"; iMyNumSides = numSides; iMyResult = 1; assert getResult() == 1 && getNumSides() == numSides; } /** * Create a Die with numSides and top side and result set to result

* pre: numSides > 1, 1 <= result <= numSides
* post: getNumSides() = numSides, getResult() = 1
* An exception will be generated if the preconditions are not met */ public Die(int numSides, int result) { assert numSides > 1 && 1 <= result && result <= numSides : "Violation of precondition"; iMyNumSides = numSides; iMyResult = result; } /** * roll this Die. Every side has an equal chance of being the new result

* pre: none
* post: 1 <= getResult() <= getNumSides() * @return the result of the Die after the roll */ public int roll() { iMyResult = ourRandNumGen.nextInt(iMyNumSides) + 1; assert ( 1 <= getResult() ) && ( getResult() <= getNumSides() ); return iMyResult; } /** * return how many sides this Die has

* pre: none
* post: return how many sides this Die has * @return the number of sides on this Die */ public int getNumSides() { return iMyNumSides; } /** * get the current result or top number of this Die

* pre: none
* post: return the number on top of this Die * @return the current result of this Die */ public int getResult() { return iMyResult; } /** * returns true if this Die and the parameter otherObj are equal

* pre: none
* post: return true if the parameter is a Die object with the same number of sides as this Die and currently has the same result. * @return true if the the two Dice are equal, false otherwise */ public boolean equals(Object otherObj) { boolean result = true; if(otherObj == null) result = false; else if(this == otherObj) result = true; else if(this.getClass() != otherObj.getClass()) result = false; else { Die otherDie = (Die)otherObj; result = this.iMyResult == otherDie.iMyResult && this.iMyNumSides == otherDie.iMyNumSides; } return result; } /** * returns a String containing information about this Die

* pre: none
* post: return a String with information about the current state of this Die * @return: A String with the number of sides and current result of this Die */ public String toString() { return "Num sides " + getNumSides() + " result " + getResult(); } }// end of Die class



DemoClass:

This illustrates some of the more confusing concepts in class syntax and mechanics such as constructors, static vs. instance methods, and method overloading.

/* 
 * @author Usman Mughal
 */
public class DemoClass
{
    private int x;

    public DemoClass()
    {
        // assign default value
        x = 0;
    }

    public DemoClass(int x)
    {
        // use this.x to refer to the instance variable x
        // use x to refer to a local variable x (more specifically,
        // method parameter x)
        this.x = x;
    }

    public DemoClass(DemoClass otherDemo)
    {
        // copy the value from the otherDemo
        this.x = otherDemo.x;
    }

    // static method (aka class method)
    public static void s1() {
        return;
    }
    // instance method
    public void i1() {
        return;
    }

    // static calling static OK
    // static calling instance is a compile-time error
    public static void s2() {
//        i1();     // compile-time error
        s1();       // DemoClass.s1
        return;
    }

    // instance calling static OK
    // instance calling instance OK
    public void i2() {
        s1();       // DemoClass.s1();
        i1();       // this.i1();
        return;
    }

    // call various versions of overload() based on their 
    // list of parameters (aka function signatures)
    public void overloadTester() {
        System.out.println("overloadTester:\n");

        overload((byte)1);
        overload((short)1);
        overload(1);
        overload(1L);
        overload(1.0f);
        overload(1.0);
        overload('1');
        overload(true);
    }
    
    public void overload(byte b) {
        System.out.println("byte");
    }    
    public void overload(short s) {
        System.out.println("short");
    }    
    public void overload(int i) {
        System.out.println("int");
    }
    public void overload(long l) {
        System.out.println("long");
    }
    public void overload(float f) {
        System.out.println("float");
    }
    public void overload(double d) {
        System.out.println("double");
    }    
    public void overload(char c) {
        System.out.println("char");
    }    
    public void overload(boolean b) {
        System.out.println("boolean");
    }    

    public static void main(String[] args) {
        DemoClass dc = new DemoClass();
        dc.overloadTester();
    }
}



Stopwatch class.

A class for measuring how long it takes for a program to run.

/* 
 * @author Usman Mughal
 */
/**
 A class to measure time elapsed.
*/

public class Stopwatch
{
    private long startTime;
    private long stopTime;

    public static final double NANOS_PER_SEC = 1000000000.0;

	/**
	 start the stop watch.
	*/
	public void start(){
		startTime = System.nanoTime();
	}

	/**
	 stop the stop watch.
	*/
	public void stop()
	{	stopTime = System.nanoTime();	}

	/**
	elapsed time in seconds.
	@return the time recorded on the stopwatch in seconds
	*/
	public double time()
	{	return (stopTime - startTime) / NANOS_PER_SEC;	}

	public String toString(){
	    return "elapsed time: " + time() + " seconds.";
	}

	/**
	elapsed time in nanoseconds.
	@return the time recorded on the stopwatch in nanoseconds
	*/
	public long timeInNanoseconds()
	{	return (stopTime - startTime);	}
}



Create a Set.

A method that using polymorphism to create a set from an array.

import java.util.Arrays;
import java.awt.Rectangle;

/**
 * A sample of a ploymorphic method.
 * @author Usman Mughal
 *
 */
public class CreateASet {
    
    public static void main(String[] args){
        String[] words = {"A", "B", "B", "D", "C", "A"};
        System.out.println( "original: " + Arrays.toString(words));
        System.out.println( "as a set: " + Arrays.toString(makeSet(words)));
        
        Rectangle[] rectList = {new Rectangle(), new Rectangle(), 
                    new Rectangle(0, 1, 2, 3), new Rectangle(0, 1, 2, 3)};
        System.out.println( "original: " + Arrays.toString(rectList));
        System.out.println( "as a set: " + Arrays.toString(makeSet(rectList)));     
        
        
        Object[] mixed = {"A", "C", "A", "B", new Rectangle(),
                new Rectangle(), "A", new Rectangle(0, 1, 2, 3), "D"};
        System.out.println( "original: " + Arrays.toString(mixed));
        System.out.println( "as a set: " + Arrays.toString(makeSet(mixed))); 
    }
    
    /**
     * An example of polymorphism in action. The method relies
     * on Java's inheritance requirement and polymorhphism to call
     * the correct equals method.
     * @param data != null, no elements of data are null
     * @return a Set (no duplicates) of the elements in data.
     */
    public static Object[] makeSet(Object[] data){
        assert data != null : "Failed precondition makeSet. parameter cannot be null";
        assert noNulls(data) : "Failed precondition makeSet. no elements of parameter can be null";
        Object[] result = new Object[data.length];
        int numUnique = 0;
        boolean found;
        int indexInResult;
        for(int i = 0; i < data.length; i++){
            // maybe should break this out into another method
            indexInResult = 0;
            found = false;
            while(!found && indexInResult < numUnique){
                found = data[i].equals(result[indexInResult]);
                indexInResult++;
            }
            if( ! found ){
                result[numUnique] = data[i];
                numUnique++;
            }
        }
        Object[] result2 = new Object[numUnique];
        System.arraycopy(result, 0, result2, 0, numUnique);
        return result2;
    }
    
    // pre: data != null
    // return true if all elements of data are non null,
    // false otherwise
    private static boolean noNulls(Object[] data){
        assert data != null : "Failed precondition makeSet. parameter cannot be null";
        boolean good = true;
        int i = 0;
        while( good && i < data.length ){
            good = data[i] != null;
            i++;
        }
        return good;        
    }
    
}



Recursion examples.

Includes examples on finding space taken up by files in a directory including all files in all subdirectories, recursive factorial, recursive power, recursive Fibonacci numbers, and a simple knapsack problem.

/* 
 * @author Usman Mughal
 */
public class RecursionExampleDirectory
{	
	public int getSize(Directory dir)
	{	int total = 0;
	
		//check files
		File[] files = dir.getFiles();
		for(int i = 0; i < files.length; i++)
			total += files[i].getSize();
			
		//get sub directories and check them
		Directory[] subs = dir.getSubs();
		for(int i = 0; i < subs.length; i++)
			total += getSize(subs[i]);
			
		return total;
	}
	
	public static void main(String[] args)
	{	RecursionExampleDirectory r = new RecursionExampleDirectory();
		Directory d = new Directory();
		System.out.println( r.getSize(d) );
	}
	
	//pre: n >= 0
	public static int fact(int n)
	{	int result = 0;
		if(n == 0)
			result = 1;
		else
			result = n * fact(n-1);
		return result;
	}
	
	//pre: exp >= 0
	public static int pow(int base, int exp)
	{	int result = 0;
		if(exp == 0)
			result = 1;
		else
			result = base * pow(base, exp - 1);
		return result;
	}
	
	//slow fib
	//pre: n >= 1
	public static int fib(int n)
	{	int result = 0;
		if(n == 1 || n == 2)
			result = 1;
		else
			result = fib(n-1) + fib(n-2);
		return result;
	}
	
	public static int minWasted(int[] items, int itemNum, int capLeft)
	{	int result = 0;
		if(itemNum >= items.length)
			result = capLeft;
		else if( capLeft == 0)
			result = 0;
		else
		{	int minWithout = minWasted(items, itemNum + 1, capLeft);
			if( capLeft <= items[itemNum])		
			{	int minWith = minWasted(items, itemNum + 1, capLeft - items[itemNum]);
				result = Math.min(minWith, minWithout);
			}
			else
				result = minWithout;
		}
		return result;	
	}
}

class Directory
{	private Directory[] mySubs;
	private File[] myFiles;
	
	public Directory()
	{	int numSubs = (int)(Math.random() * 3);
		mySubs = new Directory[numSubs];
		int numFiles = (int)(Math.random() * 10);
		myFiles = new File[numFiles];
		
		for(int i = 0; i < myFiles.length; i++)
			myFiles[i] = new File( (int)(Math.random() * 1000 ) );
		for(int i = 0; i < mySubs.length; i++)
			mySubs[i] = new Directory();
	}
	
	public Directory[] getSubs()
	{	return mySubs;
	}
	
	public File[] getFiles()
	{	return myFiles;
	}
}

class File
{	private int iMySize;

	public File(int size)
	{	iMySize = size;
	}
	
	public int getSize()
	{	return iMySize;
	}
}


Eight Queens example.

Code to find a a solution to an N queens problem. Note the queensAreSafe method has not been completed.

/* 
 * @author Usman Mughal
 */
import java.util.Arrays;
import java.util.ArrayList;

public class EightQueens {


	public static void main(String[] args) {
			solveNQueens(8);
			ArrayList solutions = getAllNQueens(8);
			System.out.println( solutions.size() );
			for( int i = 0; i < solutions.size(); i++){
				System.out.println("\n\nSolution " + (i+1));
				if( queensAreSafe(solutions.get(i)) )
					printBoard(solutions.get(i));
				else
					System.out.println("UH OH!!!!! BETTER FIX IT!!!!!");

	}

	/**
	 * determine if the chess board represented by board is a safe set up
	 * 

pre: board != null, board.length > 0, board is a square matrix. * (In other words all rows in board have board.length columns.), * all elements of board == 'q' or '.'. 'q's represent queens, '.'s * represent open spaces.
*

post: return true if the configuration of board is safe, * that is no queen can attack any other queen on the board. * false otherwise. * @param board the chessboard * @return true if the configuration of board is safe, * that is no queen can attack any other queen on the board. * false otherwise. */ public static boolean queensAreSafe(char[][] board) { char[] validChars = {'q', '.'}; assert (board != null) && (board.length > 0) && isSquare(board) && onlyContains(board, validChars) : "Violation of precondition: queensAreSafe"; return true; } public static ArrayList getAllNQueens(int size){ ArrayList solutions = new ArrayList(); char[][] board = blankBoard(size); solveAllNQueens(board, 0, solutions); return solutions; } public static void solveAllNQueens(char[][] board, int col, ArrayList solutions){ // am I done? if so, add this solution to the ArrayList of solutions if( col == board.length){ solutions.add( makeCopy(board)); // all done } else { for(int row = 0; row < board.length; row++){ // place queen board[row][col] = 'q'; if( queensAreSafe(board) ) // if safe go on to next column solveAllNQueens(board, col + 1, solutions); board[row][col] = '.'; } } } // pre: mat != null, mat is rectangular public static char[][] makeCopy(char[][] mat){ assert mat != null; char[][] copy = new char[mat.length][mat[0].length]; for(int r = 0; r < mat.length; r++) for(int c = 0; c < mat[0].length; c++) copy[r][c] = mat[r][c]; return copy; } public static void printBoard(char[][] board){ for(int r = 0; r < board.length; r++){ for(int c = 0; c < board[r].length; c++) System.out.print(board[r][c]); System.out.println(); } } public static void solveNQueens(int n){ char[][] board = blankBoard(n); //start in column 0 boolean solved = canSolve(board, 0); if( solved ){ System.out.println("Solved the " + n + " queen problem."); printBoard(board); } else System.out.println("Can't solve the " + n + " queen problem."); } public static boolean canSolve(char[][] board, int col){ //know when you are done! if( col == board.length) return true; // solved!!!!! // not done, try all the rows boolean solved = false; for(int row = 0; row < board.length && !solved; row++){ //System.out.println(row + " " + col); // place queen board[row][col] = 'q'; if( queensAreSafe(board) ) solved = canSolve(board, col + 1); if( !solved ) board[row][col] = '.'; } return solved; //could be true(solved) or false(not solved)!! } private static char[][] blankBoard(int size){ char[][] result = new char[size][size]; for(int r = 0; r < size; r++) Arrays.fill(result[r], '.'); return result; } private static boolean inbounds(int row, int col, char[][] mat){ return row >= 0 && row < mat.length && col >= 0 && col < mat[0].length; } /* pre: mat != null post: return true if mat is a square matrix, false otherwise */ private static boolean isSquare(char[][] mat) { assert mat != null : "Violation of precondition: isSquare"; final int numRows = mat.length; int row = 0; boolean square = true; while( square && row < numRows ) { square = ( mat[row] != null) && (mat[row].length == numRows); row++; } return square; } /* pre: mat != null, valid != null post: return true if all elements in mat are one of the characters in valid */ private static boolean onlyContains(char[][] mat, char[] valid) { assert mat != null && valid != null : "Violation of precondition: onlyContains"; int row = 0; int col; boolean correct = true; while( correct && row < mat.length) { col = 0; while(correct && col < mat[row].length) { correct = contains(valid, mat[row][col]); col++; } row++; } return correct; } /* pre: list != null post: return true if c is in list */ private static boolean contains(char[] list, char c) { assert ( list != null ) : "Violation of precondition: contains"; boolean found = false; int index = 0; while( !found && index < list.length) { found = list[index] == c; index++; } return found; } }



Airlines example.

Determine if airlines can be moved from airline to another based on network of airline partners. Here is a sample input file.

/* 
 * @author Usman Mughal
 */
import java.util.ArrayList;
import java.util.Scanner;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;

public class AirlineProblem {

    public static void main(String[] args){
        Scanner scannerToReadAirlines = null;
        try{
            scannerToReadAirlines = new Scanner(new File("airlines.txt"));
        }
        catch(IOException e){
            System.out.println("Could not connect to file airlines.txt.");
            System.exit(0);
        }
        if(scannerToReadAirlines != null){
            ArrayList airlinesPartnersNetwork = new ArrayList();
            Airline newAirline;
            String lineFromFile;
            String[] airlineNames;
            
            while( scannerToReadAirlines.hasNext() ){
                lineFromFile = scannerToReadAirlines.nextLine();
                airlineNames = lineFromFile.split(",");
                newAirline = new Airline(airlineNames);
                airlinesPartnersNetwork.add( newAirline );
            }
            System.out.println(airlinesPartnersNetwork);
            Scanner keyboard = new Scanner(System.in);
            System.out.print("Enter airline miles are on: ");
            String start = keyboard.nextLine();
            System.out.print("Enter goal airline: ");
            String goal = keyboard.nextLine();
            ArrayList pathForMiles = new ArrayList();
            ArrayList airlinesVisited = new ArrayList();
            if( canRedeem(start, goal, pathForMiles, airlinesVisited, airlinesPartnersNetwork))
                System.out.println("Path to redeem miles: " + pathForMiles);
            else
                System.out.println("Cannot convert miles from " + start + " to " + goal + ".");
        }
    }
    
    private static boolean canRedeem(String current, String goal,
            ArrayList pathForMiles, ArrayList airlinesVisited,
            ArrayList network){
        if(current.equals(goal)){
            //base case 1, I have found a path!
            pathForMiles.add(current);
            return true;
        }
        else if(airlinesVisited.contains(current))
            // base case 2, I have already been here
            // don't go into a cycle
            return false;
        else{
            // I have not been here and it isn't
            // the goal so check its partners
            // now I have been here
            airlinesVisited.add(current);
            
            // add this to the path
            pathForMiles.add(current);
            
            // find this airline in the network
            int pos = -1;
            int index = 0;
            while(pos == -1 && index < network.size()){
                if(network.get(index).getName().equals(current))
                    pos = index;
                index++;
            }
            //if not in the network, no partners
            if( pos == - 1)
                return false;
            
            // loop through partners
            index = 0;
            String[] partners = network.get(pos).getPartners();
            boolean foundPath = false;
            while( !foundPath && index < partners.length){
                foundPath = canRedeem(partners[index], goal, pathForMiles, airlinesVisited, network);
                index++;
            }
            if( !foundPath )
                pathForMiles.remove( pathForMiles.size() - 1);
            return foundPath;
        }
    }

    private static class Airline{
        private String name;
        private ArrayList partners;
        
        //pre: data != null, data.length > 0
        public Airline(String[] data){
            assert data != null && data.length > 0 : "Failed precondition";
            name = data[0];
            partners = new ArrayList();
            for(int i = 1; i < data.length; i++)
                partners.add( data[i] );
        }
        
        public String[] getPartners(){
            return partners.toArray(new String[partners.size()]);
        }
        
        public boolean isPartner(String name){
            return partners.contains(name);
        }
        
        public String getName(){
            return name;
        }
        
        public String toString(){
            return name + ", partners: " + partners;
        }
    }
}


Minesweeper.

Another example of recursion from the game minesweeper.

/* 
 * @author Usman Mughal
 */
public class MineSweeper
{	private int[][] myTruth;
	private boolean[][] myShow;
	
	public void cellPicked(int row, int col)
	{	if( inBounds(row, col) && !myShow[row][col] )
		{	myShow[row][col] = true;
		
			if( myTruth[row][col] == 0)
			{	for(int r = -1; r <= 1; r++)
					for(int c = -1; c <= 1; c++)
						cellPicked(row + r, col + c);
			}	
		}
	}
	
	public boolean inBounds(int row, int col)
	{	return 0 <= row && row < myTruth.length && 0 <= col && col < myTruth[0].length;
	}
}


GenericListVersion2.

Changed the GenericList class so that it implements the Iterable interface in order to demonstrate how to implement an iterator using an inner class.

import java.util.Collection;
import java.util.Iterator;

/**
 * A class to provide a simple list.
 * List resizes automatically. Used to illustrate 
 * various design and implementation details of 
 * a class in Java.
 * 
 * @author Usman Mughal
 *
 */
public class GenericListVersion2 implements Iterable{
    // class constant for default size
    private static final int DEFAULT_CAP = 10;
    
    //instance variables
    // iValues store the elements of the list and 
    // may have extra capacity
    private Object[] iValues;
    private int iSize;
    
    private class GenericListIterator implements Iterator{
        private int position;
        private boolean removeOK;
        
        private GenericListIterator(){
            position = 0;
            removeOK = false;
        }
        
        public boolean hasNext(){
            return position < iSize;
        }
        
        public Object next(){
            Object result = iValues[position];
            position++;
            removeOK = true;
            return result;
        }
        
        public void remove(){
            if( !removeOK )
                throw new IllegalStateException();
            // which element should be removed??
            removeOK = false;
            GenericListVersion2.this.remove(position - 1);
            position--;
        }
    }
    
    public Iterator iterator(){
        return new GenericListIterator();
    }
    
    public void addAll(Collection c){
       // for each loop
        for(Object obj : c){
            this.add(obj);
        }
    }
    
    /**
     * Default add method. Add x to the end of this IntList.
     * Size of the list goes up by 1.
     * @param x The value to add to the end of this list.
     */
    public void add(Object x){
        insert(iSize, x);
    }
    
    public Object get(int pos){
        return iValues[pos];
    }
    
    /**
     * Insert obj at position pos.
     * post: get(pos) = x, size() = old size() + 1
     * @param pos 0 <= pos <= size()
     * @param obj The element to add.
     */
    public void insert(int pos, Object obj){
        ensureCapcity();
        for(int i = iSize; i > pos; i--){
            iValues[i] = iValues[i - 1];
        }
        iValues[pos] = obj;
        iSize++;
    }
    
    public Object remove(int pos){
        Object removedValue = iValues[pos];
        for(int i = pos; i < iSize - 1; i++)
            iValues[i] = iValues[i + 1];
        iValues[iSize - 1] = null;
        iSize--;
        return removedValue;
    }
    
    private void ensureCapcity(){
        // is there extra capacity available?
        // if not, resize
        if(iSize == iValues.length)
            resize();
    }
    
    public int size(){
        return iSize;
    }
    
    // resize internal storage container by a factor of 2
    private void resize() {
        Object[] temp = new Object[iValues.length * 2];
        System.arraycopy(iValues, 0, temp, 0, iValues.length);
        iValues = temp;
    }
    
    /**
     * Return a String version of this list. Size and 
     * elements included.
     */
    public String toString(){
        // we could make this more effecient by using a StringBuffer.
        // See alternative version
        String result = "size: " + iSize + ", elements: [";
        for(int i = 0; i < iSize - 1; i++)
            result += iValues[i].toString() + ", ";
        if(iSize > 0 )
            result += iValues[iSize - 1];
        result += "]";
        return result;
    }
    
    // Would not really have this and toString available
    // both included just for testing
    public String toStringUsingStringBuffer(){
        StringBuffer result = new StringBuffer();
        result.append( "size: " );
        result.append( iSize );
        result.append(", elements: [");
        for(int i = 0; i < iSize - 1; i++){
            result.append(iValues[i]);
            result.append(", ");
        }
        if( iSize > 0 )
            result.append(iValues[iSize - 1]);
        result.append("]");
        return result.toString();
    }

    /**
     * Default constructor. Creates an empty list.
     */
    public GenericListVersion2(){
        //redirect to single int constructor
        this(DEFAULT_CAP);
        //other statments could go here.
    }

    /**
     * Constructor to allow user of class to specify 
     * initial capacity in case they intend to add a lot
     * of elements to new list. Creates an empty list.
     * @param initialCap > 0
     */    
    public GenericListVersion2(int initialCap) {
        assert initialCap > 0 : "Violation of precondition. IntListVer1(int initialCap):"
            + "initialCap must be greater than 0. Value of initialCap: " + initialCap;
        iValues = new Object[initialCap];
        iSize = 0;
    }
    
   /**
    * Return true if this IntList is equal to other.
* pre: none * @param other The object to comapre to this * @return true if other is a non null, IntList object * that is the same size as this IntList and has the * same elements in the same order, false otherwise. */ public boolean equals(Object other){ boolean result; if(other == null) // we know this is not null so can't be equal result = false; else if(this == other) // quick check if this and other refer to same IntList object result = true; else if( this.getClass() != other.getClass() ) // other is not an IntList they can't be equal result = false; else{ // other is not null and refers to an IntList GenericListVersion2 otherList = (GenericListVersion2)other; result = this.size() == otherList.size(); int i = 0; while(i < iSize && result){ result = this.iValues[i].equals( otherList.iValues[i] ); i++; } } return result; } }


GenericListVersion3.

Changed GenericList so it is generic based on Java generics syntax instead of relying on Object.

/* 
 * @author Usman Mughal
 */
import java.util.Iterator;

public class GenericList implements Iterable{
 // class constant
    private static final int DEFAULT_CAP = 10;
 
    // instance variables
    protected E[] container; // the array is NOT the list
    private int listSize;
    
    public Iterator iterator(){
        return new GenListIterator();
    }
    
    // inner class
    private class GenListIterator implements Iterator{
        private int indexOfNextElement;
        private boolean okToRemove;
        
        private GenListIterator(){
            indexOfNextElement = 0;
            okToRemove = false;
        }
        
        public boolean hasNext(){
            return indexOfNextElement < size();
        }
        
        public E next(){
            assert hasNext();
            okToRemove = true;
            indexOfNextElement++;
            return container[indexOfNextElement - 1];
        }
        
        public void remove(){
            assert okToRemove;
            okToRemove = false;
            indexOfNextElement--;
            GenericList.this.remove(indexOfNextElement);
        }
        
    }
    
    public boolean equals(Object obj){
        assert this != null;
        if(obj == null)
            return false;
        else if (this == obj)
            return true;
        else if( this.getClass() != obj.getClass() )
            return false;
        else{
            // obj is a non null GenericList
            GenericList list = (GenericList)obj;
            if( list.size() != size() )
                return false;
            for(int i = 0; i < size(); i++)
                if( (get(i) == null && list.get(i) != null) || !get(i).equals(list.get(i)) )
                    return false;
            return true;
        }
        
            
    }
    

    // creates an empty IntList
    public GenericList(){
        this(DEFAULT_CAP);
    }

    // pre: initialCap >= 0
    public GenericList(int initialCap){
        assert initialCap >= 0 : "failed precondition";
        container = (E[])(new Object[initialCap]);
        listSize = 0;        
    }
    
    public void insertAll(int pos, GenericList otherList){
        
        for(int i = 0; i < otherList.listSize; i++){
            this.insert(pos + i, otherList.container[i]);
        }
    }
    
    // pre: 0 <= pos < size()
    public E remove(int pos){
        E result = container[pos];
        listSize--;
        for(int index = pos; index < size(); index++){
            container[index] = container[index + 1];
        }
        container[listSize] = null;
        return result;
    }
    
    // pre: 0 <= pos <= size()
    public void insert(int pos, E element){
        assert 0 <= pos && pos <= size();
        if( size() == container.length )
            resize();
        for(int index = size(); index > pos; index--){
            assert index > 0;
            container[index] = container[index - 1];
        }
        container[pos] = element;
        listSize++;
    }
    
    // get size of list
    public int size(){
        return listSize;
    }
    
    // access elements
    // pre: 0 <= position < size()
    public E get(int position){
        assert 0 <= position && position < size();
        return container[position];
    }
    
    // pre: none
    public void add(E element){    
        insert(size(), element);
    }

    private void resize() {
        E[] temp = (E[])(new Object[container.length * 2 + 1]);
        System.arraycopy(container, 0, temp, 0, size());
        container = temp;
    }
    
    public String toString(){
        StringBuffer result = new StringBuffer("[");
        final int LIMIT = size() - 1;
        for(int i = 0; i < LIMIT; i++){
            if( this == this.get(i) )
                result.append("this list");
            else{
                result.append(get(i));
            }
            result.append(", ");
        }
        if( size() != 0)
            result.append(get(size() - 1));
        result.append("]");
        return result.toString();
    }
   
}



ListNode.

A singly linked node class used to build linked lists

/* 
 * @author Usman Mughal
 */
public class ListNode
 {
	 // instance variables

	// the data to store in this node
	private Object myData;

	// the link to the next node (presumably in a list)
	private ListNode myNext;

	/**
	 * default constructor
	 * pre: none
* post: getData() = null, getNext() = null */ public ListNode() { this(null, null); } /** * create a ListNode that holds the specified data and refers to the specified next element * pre: none
* post: getData() = item, getNext() = next * @param item the data this ListNode should hold * @param next the next node in the list */ public ListNode(Object data, ListNode next) { myData = data; myNext = next; } /** * return the data in this node * pre: none
* @return the data this ListNode holds */ public Object getData() { return myData; } /** * return the ListNode this ListNode refers to * pre: none
* @return the ListNode this ListNode refers to (normally the next one in a list) */ public ListNode getNext() { return myNext; } /** * set the data in this node * The old data is over written.
* pre: none
* @param data the new data for this ListNode to hold */ public void setData(Object data) { myData = data; } /** * set the next node this ListNode refers to * pre: none
* @param next the next node this ListNode should refer to */ public void setNext(ListNode next) { myNext = next; } }


IList

A simple list interface

/* 
 * @author Usman Mughal
 */
import java.util.Iterator;

/**
 * Interface for a simple List. Random access to all items in the list is provided. 
 * The numbering of elements in the list begins at 0.
 *
 */
public interface IList extends Iterable{

	/**
	 * Add an item to the end of this list.
	 * 
pre: none *
post: size() = old size() + 1, get(size() - 1) = item * @param item the data to be added to the end of this list */ void add(E item); /** * Insert an item at a specified position in the list. *
pre: 0 <= pos <= size() *
post: size() = old size() + 1, get(pos) = item, all elements in * the list with a positon >= pos have a position = old position + 1 * @param pos the position to insert the data at in the list * @param item the data to add to the list */ void insert(int pos, E item); /** * Change the data at the specified position in the list. * the old data at that position is returned. *
pre: 0 <= pos < size() *
post: get(pos) = item, return the * old get(pos) * @param pos the position in the list to overwrite * @param item the new item that will overwrite the old item * @return the old data at the specified position */ E set(int pos, E item); /** * Get an element from the list. *
pre: 0 <= pos < size() *
post: return the item at pos * @param pos specifies which element to get * @return the element at the specified position in the list */ E get(int pos); /** * Remove an element in the list based on position. *
pre: 0 <= pos < size() *
post: size() = old size() - 1, all elements of * list with a positon > pos have a position = old position - 1 * @param pos the position of the element to remove from the list * @return the data at position pos */ E remove(int pos); /** * Remove the first occurrence of obj in this list. * Return true if this list changed as a result of this call, false otherwise. *
pre: none *
post: if obj is in this list the first occurence has been removed and size() = old size() - 1. * If obj is not present the list is not altered in any way. * @param obj The item to remove from this list. * @return Return true if this list changed as a result of this call, false otherwise. */ boolean remove(E obj); /** * Return a sublist of elements in this list from start inclusive to stop exclusive. * This list is not changed as a result of this call. *
pre: 0 <= start < size(), start <= stop <= size() *
post: return a list whose size is stop - start and contains the elements at positions start through stop - 1 in this list. * @param start index of the first element of the sublist. * @param stop stop - 1 is the index of the last element of the sublist. * @return a list with stop - start elements, The elements are from positions start inclusive to * stop exclusive in this list. */ IList getSubList(int start, int stop); /** * Return the size of this list. In other words the number of elements in this list. *
pre: none *
post: return the number of items in this list * @return the number of items in this list */ int size(); /** * Find the position of an element in the list. *
pre: none *
post: return the index of the first element equal to item * or -1 if item is not present * @param item the element to search for in the list * @return return the index of the first element equal to item or a -1 if item is not present */ int indexOf(E item); /** * find the position of an element in the list starting at a specified position. *
pre: 0 <= pos < size() *
post: return the index of the first element equal to item starting at pos * or -1 if item is not present from position pos onward * @param item the element to search for in the list * @param pos the position in the list to start searching from * @return starting from the specified position return the index of the first element equal to item or a -1 if item is not present between pos and the end of the list */ int indexOf(E item, int pos); /** * return the list to an empty state. *
pre: none *
post: size() = 0 */ void makeEmpty(); /** * return an Iterator for this list. *
pre: none *
post: return an Iterator object for this List */ Iterator iterator(); /** * Remove all elements in this list from start inclusive to stop exclusive. *
pre: 0 <= start < size(), start <= stop <= size() *
post: size() = old size() - (stop - start) * @param start position at beginning of range of elements to be removed * @param stop stop - 1 is the position at the end of the range of elements to be removed */ void removeRange(int start, int stop); /** * Return a String version of this list enclosed in * square brackets, []. Elements are in * are in order based on position in the * list with the first element * first. Adjacent elements are seperated by comma's * @return a String representation of this IList */ public String toString(); /** * Determine if this IList is equal to other. Two * ILists are equal if they contain the same elements * in the same order. * @return true if this IList is equal to other, false otherwise */ public boolean equals(Object other); }


LinkedList.

Similar to the LinkedList developed in class. Does not contain all the methods you would expect of a LinkedList. Also implements the iterator remove method in O(N) time. An O(1) time remove method is possible.

/* 
 * @author Usman Mughal
 */


import java.util.Iterator;

import Summer08.Node;

public class LinkedList implements Iterable {
    private Node head;
    private Node tail;
    private int size;
    
    public Iterator iterator(){
        return new LLIterator();
    }
    
    private class LLIterator implements Iterator{
        private Node nextNode;
        private boolean removeOK;
        private int posToRemove;
        
        private LLIterator(){
            nextNode = head;
            removeOK = false;
            posToRemove = -1;
        }
        
        public boolean hasNext(){
            return nextNode != null;
        }
        
        public Object next(){
            assert hasNext();
            
            Object result = nextNode.getData();
            nextNode = nextNode.getNext();
            
            removeOK = true;
            posToRemove++;
            
            return result;
        }
        
        public void remove(){
            assert removeOK;
            removeOK = false;
            LinkedList.this.remove(posToRemove);
            posToRemove--;
        }
    }
    
    public void makeEmpty(){
        // let GC do its job!!!!!!!
        head = tail = null;
        size = 0;
    }
    
    public Object remove(int pos){
        assert pos >= 0 && pos < size;
        Object result;
        if( pos == 0 ){
            result = head.getData();
            head = head.getNext();
            if( size == 1 )
                tail = null;
        }
        else{    
            Node temp = head;
            for(int i = 1; i < pos; i++)
                temp = temp.getNext();
            result = temp.getNext().getData();
            temp.setNext( temp.getNext().getNext() );
            if( pos == size - 1)
                tail = temp;
        }
        size--;
        return result;
    }
    
    public Object get(int pos){
        assert pos >= 0 && pos < size;
        // array based list
        // return myCon[pos]
        Object result;
        if( pos == size - 1 )
            result = tail.getData(); //O(1)
        else{
            Node temp = head;
            for(int i = 0; i < pos; i++)
                temp = temp.getNext();
            result = temp.getData();
            // average case O(N) :((((
        }
        return result;
    }
    
    public void insert(int pos, Object obj){
        assert pos >= 0 && pos <= size;
        
        // addFirst?
        if(pos == 0)
            addFirst(obj); // O(1)
        // add last?
        else if( pos == size )
            add(obj); //at end O(1)
        else{
            // general case
            Node temp = head;
            for(int i = 1; i < pos; i++)
                temp = temp.getNext();
            // I know temp is pointing at the
            // node at position pos - 1
            Node newNode = new Node(obj, temp.getNext());
            temp.setNext( newNode );
            size++;
        }
    }
    
    public void add(Object obj){
        Node newNode = new Node(obj, null);
        if( size == 0 )
            head = newNode;
        else
            tail.setNext(newNode);
        tail = newNode;
        size++;
    }
    
    public void addFirst(Object obj){
        if(size == 0)
            add(obj);
        else{
            Node newNode = new Node(obj, head);
            head = newNode;
            size++;
        }
    }
    
    public String toString(){
        String result = "";
        Node temp = head;
        for(int i = 0; i < size; i++){
            result += temp.getData() + " ";
            temp = temp.getNext();
        }
        return result;
    }
}


UnsortedHashSet

An unsorted set that uses a hashtable with closed address hashing to store values. Currently only the add method is implemented.

/* 
 * @author Usman Mughal
 */


import java.util.LinkedList;
import java.lang.reflect.Array;

public class UnsortedHashSet {
   
    private static final double LOAD_FACTOR_LIMIT = 0.7;
    
    private int size;
    private LinkedList[] con;
    
    public UnsortedHashSet() {
        con  = (LinkedList[])(new LinkedList[10]);
    }
    
    public boolean add(E obj) {
        int oldSize = size;
        int index = Math.abs(obj.hashCode()) % con.length;
        if(con[index] == null)
            con[index] = new LinkedList();
        if(!con[index].contains(obj)) {
            con[index].add(obj);
            size++;
            
        }
        if(1.0 * size / con.length > LOAD_FACTOR_LIMIT)
            resize();
        return oldSize != size;
    }

    private void resize() {
        UnsortedHashSet temp = new UnsortedHashSet();
        temp.con = (LinkedList[])(new LinkedList[con.length * 2 + 1]);
        for(int i = 0; i < con.length; i++){
            if(con[i] != null)
                for(E e : con[i])
                    temp.add(e);
        }
        con = temp.con;
    }
    
    public int size() {
        return size;
    }
}


UnsortedSetTest

A method to compare Java's TreeSet and HashSet to the BianrySearchTree, UnsortedSet, and UnsortedHashSet classes developed in class. Note you need a lot of other files for this to work.

/* 
 * @author Usman Mughal
 */
package Solution;


import java.io.File;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class UnsortedSetTest {

    public static void main(String[] args) throws Exception {
        String[] allFileNames = {"hounds.txt", "huckfinn.txt", "oz.txt", "war.txt", "ciaFactBook2008.txt"};
        String[] noCIA = {"hounds.txt", "huckfinn.txt", "oz.txt", "war.txt"};
        countWords(new BinarySearchTree(), allFileNames[0]);
        for(String s : allFileNames) {
            System.out.println(s);
            countWordsOurUnsortedSet(s);
            countWordsOurBinarySearchTree(s);
            countWordsOurHash(s);
            countWordsCollection(new TreeSet(), s);
            int[] result = countWordsCollection(new HashSet(), s);
            System.out.println(result[0] + " total words.");
            System.out.println(result[1] + " distinct words.");
            System.out.println();
            
        }
    }
    
    // return total num words, and num distinct words
    public static int[] countWordsCollection(Collection c, String fileName) throws Exception{
        c.clear();
        Scanner fileScanner = new Scanner(new File(fileName));  
        Stopwatch st = new Stopwatch();
        st.start();
        int total = 0;
        while(fileScanner.hasNext()){
            c.add(fileScanner.next());
            total++;
        }
        st.stop();
        System.out.println("Time for " + c.getClass() + " : \n" + st);
//        System.out.println(c.size() + " distinct words");
//        System.out.println(total + " total words including duplicates: ");
        assert total >= c.size();
        System.out.println();
        return new int[]{total, c.size()};
    }
    
    
    // GACKY GACKY GACKY repition. Look into removing repetition with reflection
    // we assume there will be add and size methods
    public static int[] countWordsOurHash(String fileName) throws Exception {
        Scanner fileScanner = new Scanner(new File(fileName));  
        Stopwatch st = new Stopwatch();
        UnsortedHashSet c = new UnsortedHashSet();
        st.start();
        int total = 0;
        while(fileScanner.hasNext()) {
            c.add(fileScanner.next());
            total++;
        }
        st.stop();
        System.out.println("Time for our hashtable (closed address hashing): \n" + st);
//        System.out.println(c.size() + " distinct words");
//        System.out.println(total + " total words including duplicates: ");
        assert total >= c.size();
        System.out.println();
        return new int[]{total, c.size()};
    }
    
    public static int[] countWordsOurUnsortedSet(String fileName) throws Exception {
        Scanner fileScanner = new Scanner(new File(fileName));  
        Stopwatch st = new Stopwatch();
        UnsortedSet c = new UnsortedSet();
        st.start();
        int total = 0;
        while(fileScanner.hasNext()){
            c.add(fileScanner.next());
            total++;
        }
        st.stop();
        System.out.println("Time for our unsorted set based on ArrayList: \n" + st);
//        System.out.println(c.size() + " distinct words");
//        System.out.println(total + " total words including duplicates: ");
        assert total >= c.size();
        System.out.println();
        return new int[]{total, c.size()};
    }
    
    public static int[] countWordsOurBinarySearchTree(String fileName) throws Exception {
        Scanner fileScanner = new Scanner(new File(fileName));  
        Stopwatch st = new Stopwatch();
        BinarySearchTree c = new BinarySearchTree();
        st.start();
        int total = 0;
        while(fileScanner.hasNext()){
            c.add(fileScanner.next());
            total++;
        }
        st.stop();
        System.out.println("Time for our binary search tree: \n" + st);
//        System.out.println(c.size() + " distinct words");
//        System.out.println(total + " total words including duplicates: ");
        assert total >= c.size();
        System.out.println();
        return new int[]{total, c.size()};
    }
    
    
    // a try at reflection. Not working on Binary Search tree from class. 
    // Hunch. Due to add method taking in Comparable, not Object!
    // Alterantives: search list of methods for name?
    public static int[] countWords(Object c, String fileName) throws Exception {
        Scanner fileScanner = new Scanner(new File(fileName));  
        Stopwatch st = new Stopwatch();
        System.out.println(Arrays.toString(c.getClass().getMethods()));
        Method addMethod = c.getClass().getMethod("add", Object.class);
        st.start();
        int total = 0;
        while(fileScanner.hasNext()){
            addMethod.invoke(c, fileScanner.next());
            total++;
        }
        st.stop();
        System.out.println("Time for " + c.getClass() + ": "+ st);
        Method sizeMethod = c.getClass().getMethod("size");
        int distictWords = (Integer) sizeMethod.invoke(c);
//        System.out.println(distictWords + " distinct words");
//        System.out.println(total + " total words including duplicates: ");
        System.out.println();
        return new int[]{total, distictWords};
    }
}


SimpleWordCount

Program demonstrating use of a map to count the frequency of words in a file.

/* 
 * @author Usman Mughal
 */

import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class SimpleWordCounter {
    
    public static void main(String[] args) {
        try {
            File f = new File("ciaFactBook2008.txt");
            Scanner sc;
            sc = new Scanner(f);
            // sc.useDelimiter("[^a-zA-Z']+");
            Map wordCount = new TreeMap();
            while(sc.hasNext()) {
                String word = sc.next();
                if(!wordCount.containsKey(word))
                    wordCount.put(word, 1);
                else
                    wordCount.put(word, wordCount.get(word) + 1);
            }
            
            // show results
            for(String word : wordCount.keySet())
                System.out.println(word + " " + wordCount.get(word));
            System.out.println(wordCount.size());
        }
        catch(IOException e) {
            System.out.println("Unable to read from file.");
        }
    }
}


WordCount -

Program that compares counting words in files using an ArrayList and a Map.

/* 
 * @author Usman Mughal
 */
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

import javax.swing.JFileChooser;
import javax.swing.UIManager;


public class WordCount {

    public static void main(String[] args) {
        countWordsViaGUI();
    }


    // allow user to pick file to exam via GUI.
    // allow multiple picks
    public static void countWordsViaGUI() {
        setLookAndFeel();
        try {
            Scanner key = new Scanner(System.in);
            do {
                System.out.println("Opening GUI to choose file.");
                Scanner fileScanner = new Scanner(getFile());
                Stopwatch st = new Stopwatch();
                st.start();
                ArrayList words = countWordsWithArrayList(fileScanner);
                st.stop();
                System.out.println("time to count: " + st);
                System.out.print("Enter number of words to display: ");
                int numWordsToShow = Integer.parseInt(key.nextLine());
                showWords(words, numWordsToShow);
                fileScanner.close();
                System.out.print("Perform another count? ");
            } while(key.nextLine().toLowerCase().charAt(0) == 'y');
            key.close();
        }
        catch(FileNotFoundException e) {
            System.out.println("Problem reading the data file. Exiting the program." + e);
        }
    }


    // determine distinct words in a file using an array list
    private static ArrayList countWordsWithArrayList(Scanner fileScanner) {


        System.out.println("Total number of words: " + numWords);
        System.out.println("number of distincy words: " + result.size());
        return result;
    }


    // determine distinct words in a file and frequency of each word with a Map
    private static Map countWordsWithMap(Scanner fileScanner) {


        System.out.println("Total number of words: " + numWords);
        System.out.println("number of distincy words: " + result.size());
        return result;
    }


    private static void showWords(ArrayList words, int numWordsToShow) {
        for(int i = 0; i < words.size() && i < numWordsToShow; i++)
            System.out.println(words.get(i));
    }


    private static void showWords(Map words, int numWordsToShow) {



    }


    // perform a series of experiments on files. Determine average time to
    // count words in files of various sizes
    private static void performExp() {
        String[] smallerWorks = {"smallWords.txt", "2BR02B.txt", "Alice.txt", "SherlockHolmes.txt"};;
        String[] bigFile = {"ciaFactBook2008.txt"};
        timingExpWithArrayList(smallerWorks, 50);
        timingExpWithArrayList(bigFile, 3);
        timingExpWithMap(smallerWorks, 50);
        timingExpWithMap(bigFile, 3);
    }


    // pre: titles != null, elements of titles refer to files in the
    // same path as this program, numExp >= 0
    // read words from files and print average time to cound words.
    private static void timingExpWithMap(String[] titles, int numExp) {
        try {
            double[] times = new double[titles.length];
            final int NUM_EXP = 50;
            for(int i = 0; i < NUM_EXP; i++) {
                for(int j = 0; j < titles.length; j++) {
                    Scanner fileScanner = new Scanner(new File(titles[j]));
                    Stopwatch st = new Stopwatch();
                    st.start();
                    Map words = countWordsWithMap(fileScanner);
                    st.stop();
                    System.out.println(words.size());
                    times[j] += st.time();
                    fileScanner.close();
                }
            }
            for(double a : times)
                System.out.println(a / NUM_EXP);
        }
        catch(FileNotFoundException e) {
            System.out.println("Problem reading the data file. Exiting the program." + e);
        }
    }


    // pre: titles != null, elements of titles refer to files in the
    // same path as this program, numExp >= 0
    // read words from files and print average time to cound words.
    private static void timingExpWithArrayList(String[] titles, int numExp) {
        try {
            double[] times = new double[titles.length];
            for(int i = 0; i < numExp; i++) {
                for(int j = 0; j < titles.length; j++) {
                    Scanner fileScanner = new Scanner(new File(titles[j]));
                    Stopwatch st = new Stopwatch();
                    st.start();
                    ArrayList words = countWordsWithArrayList(fileScanner);
                    st.stop();
                    times[j] += st.time();
                    fileScanner.close();
                }
            }
            for(int i = 0; i < titles.length; i++)
                System.out.println("Average time for " + titles[i] + ": " + (times[i] / numExp));
        }
        catch(FileNotFoundException e) {
            System.out.println("Problem reading the data file. Exiting the program." + e);
        }
    }


    // try to set look and feel to same as system
    private static void setLookAndFeel() {
        try {
            UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
        }
        catch(Exception e) {
            System.out.println("Unable to set look at feel to local settings. " +
            "Continuing with default Java look and feel.");
        }
    }


    /** Method to choose a file using a window.
     * @return the file chosen by the user. Returns null if no file picked.
     */
    private static File getFile() {
        // create a GUI window to pick the text to evaluate
        JFileChooser chooser = new JFileChooser(".");
        chooser.setDialogTitle("Select File To Count Words:");
        int retval = chooser.showOpenDialog(null);
        File f =null;
        chooser.grabFocus();
        if (retval == JFileChooser.APPROVE_OPTION)
            f = chooser.getSelectedFile();
        return f;
    }
}