Lab 3: Putting Classes Together
Lab 4: Inheritance and Interfaces
Project 2: ADTs: Arrays, Linked Lists and Trees
Project2: Sample Solution
This page contains Java code for performing the experiments asked for in Project 2 and some plots of the output for comparisons.
Experimental Results. All data points are the average of 500 operations.
Getting Data |
 |
 |
 |
Adding Data |
 |
 |
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A very simple class that acts as a wrapper for the unsorted array to be used in the experiments.
public class UnsortedArray
{
private Student[] contents;
private int data_size = 0;
UnsortedArray( int size )
{
contents = new Student[size];
}
// Adds a student to the array in constant time since it is just appended to the end of the array.
public void addData( int k, Student data )
{
contents[data_size++] = data;
}
// Search through all the elements in the array to see if any of them match the key we are looking for.
// This takes linear time in the size of the array.
public Student getData( int k )
{
// Dummy student to wrap the key so we can use the comparitor and keep track of the number of comparisons.
Student key = new Student();
key.setID(k);
for( int i = 0; i < data_size; i++ )
{
if ( key.compareTo( contents[i] ) == 0 )
{
return contents[i];
}
}
return null;
}
// Display the array for debugging purposes.
public void displayArray()
{
for ( int i = 0; i < data_size; i++ )
System.out.print(" "+contents[i]);
}
}
SortedArray.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A class to hold the sorted array we will be using in the experiments.
// Uses binarySearch to find and retrieve a Student in the array.
public class SortedArray
{
private Student[] contents;
private int data_size = 0;
SortedArray( int size )
{
contents = new Student[size];
}
// Add a student to the array by iterating over the array until a student is found with an ID greater
// than the ID of the student to be added. Move all the data elements from that point to the end of the array
// up by one to make room to insert the new Student. Then add the student to the correct position. This
// maintains the sorted property of the array. This method takes linear time in the size of the array.
public void addData( int k, Student data )
{
Student key = new Student();
key.setID(k);
int i = 0;
while( i < data_size && key.compareTo(contents[i]) > 0 )
{
i++;
}
for( int j = data_size+1; j > i; j-- )
{
contents[j] = contents[j-1];
}
contents[i] = data;
data_size++;
}
// Display the array for debugging
public void displayArray()
{
for ( int i = 0; i < data_size; i++ )
System.out.print(" "+contents[i].getID() );
System.out.println();
}
// Wrapper method that calls binarySearch to retrieve a student matching the key "k" or returns null
// if there is no such student.
public Student getData( int k )
{
// Wrap the key in a dummy student object so we can use the student comparitor
Student key = new Student();
key.setID(k);
return binarySearch( key, 0, data_size );
}
// Binary search return the student in logarithmic time in the size of the array.
public Student binarySearch(Student key, int lowerbound, int upperbound )
{
// Choose a Student in the middle of the array
int position = ( lowerbound + upperbound) / 2;
// Check if the ID of the student is greater than, smaller than, or equal to the ID being sought.
// If greater or equal then only consider the left side of the array and repeat.
// If lesser then only consider the right side of the array and repeat.
// If the upperbound is less than the lowerbound, i.e. the subarray we are left with is empty
// then return null since no students in the array had the ID we were looking for. Otherwise return the
// single element that's left since that is the element we are looking for.
while( key.compareTo( contents[position] ) != 0 && lowerbound <= upperbound )
{
if (key.compareTo(contents[position]) < 0 )
{
upperbound = position - 1;
}
else
{
lowerbound = position + 1;
}
position = (lowerbound + upperbound)/2;
}
if (lowerbound <= upperbound)
{
return contents[position];
}
else
{
return null;
}
}
}
SortedLinkedList.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// Description: A singly-linked list that maintains the sorted property on the
// addData and getData operations.
// This list is just for Project 2 so it only requires an addData method
// and a getData method.
public class SortedLinkedList
{
private Node head = null;
// Display the List for debugging.
public void displayList()
{
Node current = head;
while( current != null )
{
System.out.print( " " + current.getData().getID() );
current = current.getNext();
}
System.out.println();
}
// Add a Student to the linked list.
// Precondition: The Students in the list are in sorted order with the
// Student at the head of the list having the least ID, or the list is empty.
// Precondtion: The list is null terminated.
// Postcondition: The Student is added to the list. The list is still
// in sorted order and is still null terminated.
public void addData( int k, Student data )
{
// Create a dummy student with the ID set to k so that
// we can use the Student.compareTo( Student ) method which
// makes it easy to count the number of comparisons.
Student key = new Student();
key.setID(k);
// Handle the case where this is the first element in the list
if ( head == null )
{
head = new Node( data );
return;
}
// If this Student has ID less than the Student at the head of the list
// then add the Student to the head of the list.
if ( key.compareTo( head.getData() ) < 0 )
{
Node temp = head;
head = new Node( data );
head.setNext(temp);
return;
}
// Iterate through the list until a Student is found with ID greater
// than the new Student's ID. Insert the new Student into the list
// just before the Student with the larger ID.
Node current = head.getNext();
Node predecessor = head;
while ( current != null )
{
if ( key.compareTo( current.getData() ) < 0 )
{
predecessor.setNext( new Node( data ) );
predecessor.getNext().setNext( current );
return;
}
predecessor = current;
current = current.getNext();
}
predecessor.setNext( new Node( data ) );
}
// Return the Student that matches the key k. If no Student matches
// the key then return null.
public Student getData( int k )
{
// Create a dummy student so that the Student's comparator method
// can be used. The comparator can keep track of how many comparisons
// occur for the experiments.
Student key = new Student();
key.setID(k);
// Start at the head and iterate through the list until either:
// 1) A student is found with an ID equal to the search key. Return that
// student.
// 2) A student is found with an ID greater than the search key.
// Since the list is sorted the search key cannot match any students
// further down the list. So return.
// 3) The end of the list of the list. Then no student in the list
// had matched the search key.
Node current = head;
while( current != null )
{
if ( key.compareTo( current.getData() ) == 0 )
{
return current.getData();
}
else if ( key.compareTo( current.getData() ) < 0 )
{
return null;
}
current = current.getNext();
}
return null;
}
// The list nodes that contain the Students
private class Node
{
private Node next = null;
private Student data = null;
Node( Student d )
{
data = d;
}
public Student getData()
{
return data;
}
public void setData( Student d )
{
data = d;
}
public Node getNext()
{
return next;
}
public void setNext( Node node )
{
next = node;
}
}
}
SortedBinaryTree.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Description: A binary tree that maintains the recursive sorted property that
// all data elements in the right subtree have keys that are greater than the root's key
// and all data elements in the left subtree have keys less than the root's key.
// Assume that Student IDs which are used as the keys are unique.
class SortedBinaryTree
{
private Node root = null;
// This code taken from Prof Kelley's website so I can see what is going on when I build the tree
// Begin Prof Kelley's code
public void displayTreeSide()
{
displayTreeSide( root, "", "", "" );
}
private void displayTreeSide( Node n, String leftPre, String rootPre, String rightPre ) {
if(n == null) return;
String label = String.valueOf(n.getData().getLastName()) + "(" + n.getData().getID() + ")";
String rootSpaces = String.format("%" + label.length() + "s", "");
leftPre += rootSpaces;
rightPre += rootSpaces;
displayTreeSide( n.left, leftPre + " ", leftPre + " ,-- ", leftPre + " | " );
System.out.println( rootPre + label );
displayTreeSide( n.right, rightPre + " | ", rightPre + " `-- ", rightPre + " ");
}
// End Prof Kelley's code
// Wrapper function to getData that specifies to start at the root of the tree
// Return the Student with ID equal to the key or null if no such student is found
// Input: An integer key corresponding to the ID of the student to be returned
// Output: A student object with ID equal to "key" or null if no such student exists in the tree
public Student getData( int key )
{
// Create a dummy student with ID equal to the key being sought so that the Student comparitor
// can be used. The comparitor keeps track of the number of comparisons for the experiments.
Student s = new Student();
s.setID( key );
return getData( s, root );
}
// Recursive method used to retrieve the student object from the tree that matched the ID of the
// student passed in as an argument. Returns null if there is no such student in the tree. Assumes
// that Student IDs are unique so that at most one Student will match.
public Student getData( Student key, Node parent )
{
Student parent_data = parent.getData();
if (Global.debug) System.out.println("Considering " + parent_data.getID() );
int compare = key.compareTo( parent_data );
// Return the student in the parent node if the ID matches otherwise call getData()
// recursively on the right or left subtree depending on whether the ID being sought is
// less than or greater than the ID of the parent's student.
if ( compare == 0 )
{
if (Global.debug) System.out.println( "Found Key" );
return parent_data;
}
else if ( parent.getLeftChild()!=null & compare < 0 )
{
return getData( key, parent.getLeftChild() );
}
else if ( parent.getRightChild()!=null & compare > 0 )
{
return getData( key, parent.getRightChild() );
}
// Should not reach this code since the if statement above ought to cover all cases.
if (Global.debug) System.out.println("Error " + parent_data.getID() );
return null;
}
// Wrapper to the recursive addData() method. Handles the case where this student is the first student
// to be added to the tree.
public boolean addData( int key, Student data )
{
// Dummy student to wrap the key so we can use the student class's comparitor method and keep
// track of how many comparisons have been performed
Student student_key = new Student();
student_key.setID(key);
if ( root == null )
{
root = new Node( data );
}
else
{
addNode( root, student_key, data );
}
return true;
}
// Recursive method that adds a student to the sorted binary tree in the correct location.
// Input: The parent node that is the root of this subtree. The key of the data element to add.
// The Student to be added.
// Output: A boolean value indicating success or failure.
public boolean addNode( Node parent, Student key, Student data )
{
// There are four cases. Either the key of the student to be added is greater than the key of the root
// or less.
// If less then look at the left subtree, if greater look at the right subtree.
// If the subtree being looked at is null then add the student there, else call getData recursively on
// the root of the subtree. Since Student IDs are unique there will always be a location to which the
// Student can be added.
if ( key.compareTo( parent.getData() ) < 0 )
{
if ( parent.getLeftChild() == null )
{
parent.setLeftChild( new Node( data ) );
}
else
{
addNode( parent.getLeftChild(), key, data );
}
}
else
{
if ( parent.getRightChild() == null )
{
parent.setRightChild( new Node( data ) );
}
else
{
addNode( parent.getRightChild(), key, data );
}
}
// Always return true. Makes it possible to add error checks if the tree is someday extended to handle
// non-unique IDs.
return true;
}
// The node class that is used as building blocks to make the binary tree
// and which holds the student data elements.
private class Node
{
public Student data = null;
public Node left = null;
public Node right = null;
Node( Student d )
{
data = d;
}
public Student getData()
{
return data;
}
public boolean setData( Student d )
{
data = d;
return true;
}
public Node getLeftChild()
{
return left;
}
public Node getRightChild()
{
return right;
}
public boolean setLeftChild( Node n )
{
if ( left == null )
{
left = n;
return true;
}
return false;
}
public boolean setRightChild( Node n )
{
if ( right == null )
{
right = n;
return true;
}
return false;
}
}
}
driver.java
// CS251 Project 2 Solution
// Author: Matthew Fricke
// Date: Fall 2012
// Email: mfricke@unm.edu. Please send bug reports to this email address.
// This driver creates a sorted array, an unsorted array, a sorted list, and a sorted binary tree to hold Student objects, and performs some efficiency experiments on the datastructures.
import java.util.Arrays; // For sorting arrays
import java.util.Collections; // For shuffling arrays
import java.text.DecimalFormat; // For formating the output to some precision
class driver
{
// Print correct usage and exit
public static void usage()
{
System.out.println("Usage: driver [(un)sorted array|list|tree] [number of data items to insert] [number of gets to perform]");
System.exit(1);
}
// main() expects three arguments
public static void main( String[] args )
{
// Do some input checks
// Check that the user passed the correct number of arguments
if ( args.length != 3 ) usage();
// Get the datastructure argument and make sure it is a valid choice
String datastructure = args[0];
if ( !Arrays.asList("unsorted array", "sorted_array", "list", "tree").contains(datastructure) ) usage();
// Set the number of items to add to the datastructure
// and the number of gets to perform in the experiments
int num_adds = 0;
int num_gets = 0;
// Check the arguments passed in by the user to make sure they are integers
try
{
num_adds = Integer.parseInt(args[1]);
num_gets = Integer.parseInt(args[2]);
}
// Catch the exception if arguments are not integers and exit
catch ( Exception e )
{
usage();
}
double total_time_taken = 0;
// Create an unsorted and sorted array twice the size of the number
// of items we want to add so we have room to pay with adding more items
UnsortedArray ua = new UnsortedArray( 2*num_adds );
SortedArray sa = new SortedArray( 2*num_adds );
// Create a sorted linked list and a sorted binary tree
SortedBinaryTree bst = new SortedBinaryTree();
SortedLinkedList sl = new SortedLinkedList();
// create the data items to add and give them some silly names
Student[] students = new Student[num_adds];
for ( int i = 0; i < num_adds; i++ )
{
String suffix = "";
switch ( i % 10 )
{
case 1: suffix = "st"; break;
case 2: suffix = "nd"; break;
case 3: suffix = "rd"; break;
default: suffix = "th";
}
String first_name = "Bill";
String last_name = "Frankenfurter the " + i + suffix;
students[i] = new Student( i*2, first_name, last_name );
}
// Randomly reorder the students just created so our tree
// doesn't turn into a linked list and so adding items to the sorted list
// doesn't always add items to the end or to the front.
Collections.shuffle(Arrays.asList(students));
// Add the students one by one to the datastructure specified by the user.
// Time how long each addition takes and count how many comparisons occur.
for ( int i = 0; i < num_adds; i++ )
{
if (Global.debug) System.out.println("Adding: " + students[i].getID() );
double start = System.nanoTime();
int key = students[i].getID();
if ( datastructure.equals("tree") ) bst.addData(key, students[i]);
else if ( datastructure.equals("list") ) sl.addData(key, students[i]);
else if (datastructure.equals("sorted_array")) sa.addData( key, students[i] );
else if (datastructure.equals("unsorted_array")) ua.addData( key, students[i] );
total_time_taken += System.nanoTime() - start;
}
double comparison_average_for_add = Student.getComparisonCount()/num_adds;
double time_average_for_add = total_time_taken/num_adds;
// Reshuffle the students and perform some specified number of get operations.
Collections.shuffle(Arrays.asList(students));
// Do one get on the tree to prime the cache. The first get takes much
// longer than the others. This could be because of prefetching? Mystery.
if (datastructure.equals("tree")) bst.getData( students[0].getID() );
// Initialize the time and counter variables
Student.resetComparisonCount();
total_time_taken = 0;
for ( int i = 0; i < num_gets; i++ )
{
if (Global.debug) System.out.println("Getting: " + students[i%num_adds].getID() );
int key = students[i%num_adds].getID();
double start_time = System.nanoTime();
Student s = null;
if (datastructure.equals("tree")) s = bst.getData( key );
else if (datastructure.equals("list")) s = sl.getData( key );
else if (datastructure.equals("array")) s = sa.getData( key );
else if (datastructure.equals("sorted_array")) s = sa.getData( key );
else if (datastructure.equals("unsorted_array")) s = ua.getData( key );
total_time_taken += System.nanoTime() - start_time;
if (Global.debug)
{
if ( s == null ) System.out.println( key + " not found");
else System.out.println( s.getLastName() );
}
}
// If the debug flag is set print out the datastructures
if (Global.debug) bst.displayTreeSide();
if (Global.debug) sl.displayList();
if (Global.debug) sa.displayArray();
if (Global.debug) ua.displayArray();
// Format the output values to one decimal place
DecimalFormat df = new DecimalFormat("#.#");
// Compute the averages
double comparison_average_for_get = Student.getComparisonCount()/num_gets;
double time_average_for_get = total_time_taken/num_gets;
// Print the results to standard out
System.out.println( df.format( comparison_average_for_add ) + " "
+ df.format( time_average_for_add ) + " "
+ df.format( comparison_average_for_get ) + " "
+ df.format( time_average_for_get ) );
}
}