COMP 1006 - Assignment 6

Bonus (20%) Due Date : Friday March 8, 2013 at noon

NEW Due Date : Monday March 11, 2013 at 9pm

Submit a single zip file called userID.assignment6.zip to cuLearn with all of your solutions to the following problems. Submit early and submit often. Here, userID is your Carleton userID number.

Node Class: You will extend the following class for (some of) the questions below.

   public class Node<T>{
       protected      T  data;
       protected Node<T> next; 
   }

Implement the QUEUE (FIFO) abstract data type. For this, you will create a class called Queue that extends Node<T>. Your class should have the following methods:

public void enqueue(T item)
// Purpose: adds item to the queue
// Preconditions:  item should exists (not be null)
// Postconditions: item is added to the end of the queue
//                 the size of the queue is increased by 1

public T dequeue()
// Purpose: removes an element from the queue
// Preconditions: the queue is non-empty
// Postconditions: returns the element at the front of the queue
//                 the size of the queue is decreased by 1

public int size()
// Purpose: gives the size of the queue
// Preconditions: the queue exists (and is not null)
// Postconditions: returns the size of the queue
//                 this method does not change anything
//                 in the queue

public boolean isEmpty()
// Purpose: asks if the queue is empty or not
// Preconditions: the queue exists (and is not null)
// Postconditions: returns true if the size of the queue is zero
//                 returns false if size > 0

public Queue()
// Purpose: creates an empty queue
// Preconditions: none
// Postconditions: the created queue is not null
//                 size of the queue is zero

Do not add a main method to your Queue class.

Submit your Queue.java file for this problem (in your zip file).

Create a class called QueueStuff that extends the Queue class. QueueStuff is a queue. Your class should have the following methods:

public void printQueue()
// Purpose: display the contents of the queue
// Preconditions: the queue exists (and is not null)
// Postconditions: displays the contents of the queue
//                 to the terminal (screen) in the format below
//                 The method does not change the calling queue
// Examples: 
// q has size zero:
//   q.printQueue() ==prints==> "< >"
// q has size 1:
//   q.printQueue() ==prints==> "< first >"
// typical non-empty queue q
//   q.printQueue() ==pritns==> "< first | second | ... | last >"
// Here, first, second, ..., last, are the items in the queue.
// Use println() to print

public Queue reverse()
// Purpose: creates a new queue that is the opposit order
// Preconditions: the queue exists (and is not null)
// Postconditions: returns a new Queue that has items in reverse
//                 order of the calling queue
//                 The method does no change the calling queue

public void reverseMe()
// Purpose: reverses the queue items order
// Preconditions: the queue exists (is not null)
// Postconditions: Reverses the order of the items in the queue

Do not add a main method to this class.

Submit your QueueStuff.java file for this problem (in your zip file).

Create a class called TestQueue. This class will have a main method that tests your Queue and QueueStuff classes. Be sure to diplay your testing results.
You should have a good test suite for at least one (non-trivial) method in one of Queue or QueueStuff.b
Submit your TestQueue.java file for this problem (in your zip file).

[Read Problem 4 and 5 together before starting Problem 4]
Create a class called QueueString. This class will implement the Queue (FIFO) abstract data type (for Strings) using an array of Strings.
Your class must have the following methods: (purpose, preconditions, and postconditions from Question 1 apply here)
```
public void enqueue(String item)
// Purpose: adds item to the queue
// Preconditions:  item should exists (not be null)
// Postconditions: item is added to the end of the queue
//                 the size of the queue is increased by 1

public String dequeue()
// Purpose: removes an element from the queue

public int size()
// Purpose: gives the size of the queue

public boolean isEmpty()
// Purpose: asks if the queue is empty or not

public Queue()
// Purpose: creates an empty queue
```
For your implementation, you will use an array of Strings to store the data in the queue. Your array will be
1. Circular: (I will post some notes about this soon.)
2. Dynamic: (We have already seen this in the Stack example.)
  - Only increase the size of the array when you need to (when the size has reached the capacity) not just when data reaches the end of the array.
  - As soon as the size of the queue is less than 25% of the capacity, you should decrease the size of the array by one half.
Do not include a main method in this class.
Submit your QueueString.java file for this problem (in your zip file).
In problem 4 you need to use a dynamic array. In this problem, you will investigate the efficiency of your dynamic array and try to partially optimize your implmentation.
You will generate some data to show how the performance of your QueueString class when you vary the condition for increasing the size of your array. Your experiments should consider at the very least
1. Increasing the array by 1 element at a time
2. Increasing the array by 2 elements at a time
3. Increasing the array size by 10% each time
4. Increasing the array size by 25% each time
5. Increasing the array size by 50% each time
6. Increasing the array size by 100% each time
In order to generate your data, you can use something like
```
long startTime = System.currentTimeMillis();

// do your queue operations here...

long endTime = System.currentTimeMillis();

System.out.println("That took " + (endTime - startTime) + " millise
conds");
```
Make sure that you do enough operations on the queue so that the runtime is big enough to measure. For each time determination, you may work with several queues do many operations on each. For each version of your code you should the exact same experiments.
Summarize your results in a PDF file called QueueStringSummary.pdf. This should include
1. A graph/plot/chart/something visual to show your collected data
2. A conclusion about what is the best way to increase your array
3. Any shortcoming about this method of optimizing your code
Do all your testing in a class called QueueStringPerformace.
Submit your QueueStringPerformance.java and your QueueStringSummary.pdf files for this problem (in your zip file).

You are asked to write some software to deal with student records on campus.
Describe an Abstract Data Type to handle this in a PDF file called Students.pdf
Submit your Students.pdf file for this problem (in your zip file).