Read this whole handout!!! Yes, this is important. While you're at it, do the readings that go along with the assignment. If you understand Queues and Iterators before you start, you will be much better off. We tell you what sections to read, so read them! Java Docs and NDS4 Docs also might be helpful, so take a look at those.

Introduction

In this assignment, you will be writing an implementation of the Queue ADT and an Iterator. As was discussed in class, a queue is a simple data structure based on the first-in-first-out principle. You will be responsible for writing a class which models a queue by implementing the enqueue and dequeue methods.

In order to allow for greater efficiency in performing dequeue and enqueue operations, your queue will utilize a circular array. As far as the queue is concerned, the first space in the array immediately follows the last space in the array. New data should be enqueued by storing it in the array immediately after the last element in the queue. Data should be dequeued by removing the first element in the queue (at whatever array index it may reside).

You're also required to implement an iterator. An iterator is simply a design pattern that allows you to step through each element of your data structure. In this project, an iterator is represented by the MyQueueIterator class whose methods enable you to look at each element of the queue from start to end without modifying the actual data. The particular type of iterator you are going to be implementing is called a "snapshot iterator." More details in the Iterators section of this handout!

Installing, Compiling, Handing In, Demo

Type 'cs016_install queue' to install the project.

Type 'make' in the queue directory to compile your code.*

Type 'make run' in the queue directory to run your code.*

Type 'cs016_runDemo queue' to run the demo.


*These are DIFFERENT FROM CS15! Simply using javac or java won't work.


Reading

Extendable Arrays
See the "Array Lists and Extendable Arrays" section at the end of this handout for information on implementing extendable arrays.

Queues
Intro to Queues provides a queue ADT and information on extendable array based queues.

Iterators
See the iterators section at the end of this handout for a brief explanation of iterators and how they are used.

Specification

Purpose

• learn how to read an interface and design an implementation that meets its requirements.
• understand the Queue<E> interface and develop a class that implements it.
• understand the java.util.Iterator<E>interface and develop a class that implements it.
• learn about exceptions as an error handling mechanism in Java.
• learn how to throw and catch exceptions.

Requirements

• Fill in the MyQueue and MyQueueIterator classes. Write Java code to implement the support.queue.Queue<E> and java.util.Iterator<E> interfaces.
• Throw the exceptions that are specified in the Queue<E> and Iterator<E> interfaces when appropriate.
• Meet the specified time complexity requirements for your queue's and iterator's methods.  (This will require you to use a circular array to represent your queue.)
• Your queue's initial array size should be eight (8).
• Ensure that the queue can hold an arbitrary number of elements. When the underlying array, upon which the queue is based, becomes full you should expand it by doubling its size rather than increasing it by a constant amount.

The Visualizer

In order to run the visualizer on your queue, you will have to successfully implement two methods of the Queue<E>: size() and getData(). See the method list below for a detailed description of what is expected for each of these methods. Once these are completed your GUI will show up. The other testing capabilities of the interface will become functional as you implement more of the Queue<E> and Iterator<E> methods.

You will notice that we have provided you with a MyQueueDataObject<E> class. This allows an outside source to access some of the Queue<E>'s private variables which are needed for the visualizer to work. This breaks encapsulation and, though generally poor design, is necessary to see your queue.  (A typical Queue<E> would not have a getData() method.)

The MyQueueDataObject<E> class has already been written for you. All you need to do is return an instance of it in your Queue<E>'s getData() method. Don't be confused by it. The MyQueueDataObject<E> class exists solely for the visualizer.
 

Read Me

For each CS16 project you must also hand in a README to explain your design decisions. Answer the following questions in a text file entitled "README" and save it in the same directory as your project; that way it will automatically be included when you run the handin script. (You can create a new text file in kate or xemacs or any other editor.) Each of the questions should be answered in about 2-4 lines, unless otherwise stated.
• Give an overview of your design for Queue.
• How did you implement a snapshot iterator?
• If you have anything else noteworthy about your program you haven't mentioned yet, talk about it (write as much or as little as you like).

Note that we still expect you to comment your code where appropriate.

Important: The CS16 TA staff has automated testing utilities that help us assess the functionality of a program. If there is a bug in your code, we will find it. Promise. However, if you notice a bug that you just can't seem to fix (or don't have the time to fix), let us know in your README and you shall be rewarded! Just tell us what goes wrong, what functionality is affected, and roughly where you think the problem is, and we'll give you some points back. It won't be much, but you'll lose fewer than if you pretended it wasn't there and forced us to find it ourselves. It's easier on us and shows that you put some effort into testing rather than just being sloppy.

Installation

Run the install script, cs016_install queue

Handing In

Run the handin script, cs016_handin queue. Make sure to save your README in the same place as your code, so the handin script can find it.
 

Additional Information

The Queue<E> Interface

Below is the list of methods in the Queue<E> interface. You will need to implement this interface and define these methods in your queue class. Be sure to throw the proper exceptions, return the proper values, and satisfy all running time requirements. Note that only getData() comes directly from the Queue<E> interface you are implementing. The majority of the methods for your class come from the interfaces net.datastructures.Queue<E> and java.lang.Iterable<E>, which support.queue.Queue<E> extends off of. We list all the methods below to clarify the running time constraints.
• int size()
• Returns the number of elements in the queue.
• Must run in O(1) time.
• boolean isEmpty()
• Returns true if the queue is empty, false otherwise.
• Must run in O(1) time.
• void enqueue(E)
• Adds an elemnt to the rear of the queue.
• Must run in O(1) time.
• E dequeue() throws EmptyQueueException
• Removes and returns the object at the front of the queue.
• Throws EmptyQueueException if the queue is empty.
• Must run in O(1) time.
• E front() throws EmptyQueueException
• Returns, but does not remove, the object at the front of the queue.
• Throws EmptyQueueException if the queue is empty.
• Must run in O(1) time.
• Iterator<E> iterator() throws EmptyQueueException
• Returns an iterator over the elements in the queue, from front to rear. See below for more details.
• Must run in O(n) time.
• MyQueueDataObject<E> getData() throws ArrayIndexOutOfBoundsException
• Returns an instance of MyQueueDataObject<E> which you create. This method provides the visualizer access to your private members, shattering encapsulation, but allowing it to visualize your queue. Note that, while it is possible that the construction of the MyQueueDataObject<E> could throw the ArrayIndexOutOfBoundsException, proper implementation of this method will not require that you throw it yourself. Leave the throws statement in your method signature to avoid problems.
• Must run in O(1) time

MyQueueDataObject<E>

• MyQueueDataObject(E[] array, int firstIndex, int lastIndex)
  • Used by the visualizer to display each element in the queue.
  • The array must be that on top of which the queue is built.
  • The firstIndex must be the first element of the queue and the lastIndex must be the last element of the queue (Note that the first index is not necessarily 0, and the last index is not necessarily arraysize-1. Remember, you're implementing a circular array).

The java.util.Iterator<E> Interface

Below is the list of methods included in the Iterator<E>  interface. You will need to implement this interface and define these methods in your iterator class. Be sure to throw the proper exceptions, return the proper values, and satisfy all run time requirements.
 
• boolean hasNext()
• Returns true if there is another element to view, false otherwise.
• Must run in O(1) time.
• E next() throws NoSuchElementException
• Returns the next element to view.
• Throws NoSuchElementException if there are no more elements to view (i.e. the iterator has reached the end of the queue).
• Must run in O(1) time.
• The java.util.Iterator<E> interface defines an optional method remove(). We will not be implementing this method and you should leave it as it is in the stencil code. (The only thing it should do is throw an UnsupportedOperationException.)
In addition to the java.util.Iterator<E> interface methods, we would like you to implement two additional methods that are useful for iterators to have. These methods will allow you to examine the current element without advancing the iterator and reset the iterator to its initial state.
• E object() throws NoSuchElementException
• Returns the object that was returned by the last call to nextObject() (i.e., repeated calls to object() should return the same object, without moving the iterator)
• Throws NoSuchElementException if the iterator is in its initial state (i.e. nextObject() has not been called and so the iterator is positioned before the start of the queue).
• Must run in O(1) time.
• void reset()
• Puts the iterator back in its initial state, before the start of the queue.
• Must run in O(1) time.

 

Exceptions

There are two exceptions that you need to worry about for this program. Keep in mind that it is vital for the rest of the course (and for your successful programming career) that you understand how exceptions work in a general context. If you do not understand exceptions or interfaces (or anything else for that matter), be sure to visit your knowledgeable and friendly TAs on hours.
• EmptyQueueException

This exception should occur whenever an empty container is told to do something that only a non-empty container can do (such as return an element). For instance, if you try to dequeue from an empty queue, this exception should be thrown.
 
• NoSuchElementException

This exception should occur when an iterator is told to iterate onto an element which does not exist in the underlying data structure. The primary example of this is when an iterator is told to iterate beyond the end of the underlying data structure.




Design

CS 16 does not weigh design heavily as a separate category from correctness and efficiency. We do reserve the right to take off points for particularly heinous design errors, but chances are that you will not make these. On the other hand, we do reward good design indirectly because the data structures you will build often have special cases that you will get wrong on your first try. Only good design will allow you to make your data structure fully correct without having to untangle your own spaghetti code. Furthermore, only good design will allow you to meet the efficiency requirements that each assignment imposes.

A suggested design process:

1. The first step in designing a data structure for CS 16 is to understand what the data structure has to do. Look over the methods we require you to support, and make sure you understand the parameters, return, and meaning of each one. Speculate briefly about ways you could fulfill these requirements correctly, but don't commit to anything until you've completed the next step.
2. Next, you should look over the efficiency specifications for the assignment. Considerations of asymptotic efficiency often determine important design decisions. For instance, in this assignment, the requirement that enqueue and dequeue run in O(1) time suggests that you implement the queue with an array used in a circular fashion.
3. Now that you have chosen a representation for your data structure, go through the required methods again, making sure that your design will support both the general case and the special cases for each method.
4. Only now should you settle on a careful design of the code that you will need to write. To complete your design, you can draw pictures, write pseudocode, or whatever makes Java programming easier for you.
Your design must include classes that implement the Queue<E> and Iterator<E> interfaces, of course, and your Queue<E> has to use an array.
Now you can start writing pseudocode for the Queue<E> and Iterator<E> methods. (And you can start making adjustments to your design, as you discover details you hadn't thought about before.) A few tips to set you on your way:
• Start early! This program is more difficult than it first appears. You're probably familiar with the idea of queues and arrays, but iterators are a new concept. How it all fits together is not trivial.
• Learn about exceptions. Exceptions are an important part of error handling in Java and many other object-oriented languages, and they will be used extensively in this course.
• Finally, when you do start writing code, you're probably best off writing the Queue first. Only start on the Iterator once you've tested and are pretty confident of your Queue implementation.

Modular Arithmetic

This assignment requires modular arithmetic in order to correctly use your array in a circular fashion. Modular arithmetic is the math of remainders. Given nonnegative integers a and b, a mod b is the remainder of the division of a by b. In Java, this operation can be performed using the % operator. For example: 5 % 3 = 2, 7 % 4 = 3, 4 % 2 = 0. One key feature of modulo arithmetic is the fact that congruences exist. A number a is congruent modulo b to another number c if (a mod b) = (c mod b). For example, all even numbers are congruent with each other modulo 2 since any even number leaves a remainder 0 when divided by 2. Example: 4 % 2 = 0, 6 % 2 = 0, ...

In this assignment, you will be able to use the fact that modular arithmetic wraps around (much like a clock, which can be thought of modulo 12) by using it to index your arrays. For instance, in an array of size 16, if you want to access the element after the 15th element, you can simply say, (15 + 1) % 16 which would put the index back at 0. Note: % has the same precedence as * and /, which is greater than that of + and -. Modular arithmetic can also be used to move backwards in the array, but the % operator does not work the same for negative numbers. Therefore, you will always want to work with nonnegative numbers. Luckily, thanks to the congruence, you can always add the size of the modulo without affecting the result (e.g. 1 mod 7 = (1+7) mod 7 = 1). Thus, you can say (-1 + 16) mod 16 = 15, which is what one would expect to do if you moved back from 0. This explanation has been fairly brief, so if you have any questions, please come to the help session or visit a TA on hours.

Iterators

A Little Bit of Elaboration...

For most of you, the iterator is probably a new concept. An iterator is a design pattern that allows you to easily march through a data structure one element at a time. In its simplest form, an iterator may just provide a method to "access the next element". But it always makes the useful guarantee that if you repeatedly "access the next element", it will eventually indicate that "there are no elements remaining", and when that happens you can be assured that you have visited every element in the data structure.

So, what you're going to be doing is implementing a "snapshot iterator." A snapshot iterator, rather than iterating through the data structure itself, gets a copy, or "snapshot," of the data in the data structure. What this means is that, once the iterator has been created, it will access the data in the queue as it was when the iterator was created. If the queue is changed, the iterator will not reflect these changes. This is in contrast to what is known as a dynamic iterator, which iterates through the data reflecting any changes made to the data structure.

Your iterator's main methods are the next() method, which will return the next piece of data in the structure when it is called, and the hasNext() method, which returns a boolean indicating if the end of the queue has been reached. So your Iterator is going to need to be able to determine the next element in the sequence as well as the end of the queue. Think about what this means regarding your particular implementation, and how the Iterator will get this data.

The tough part will be designing your iterator. Once you get that squared away, the code should just fall into place. You should think about what information your iterator needs to know. How does it know which elements to iterate through and in what order? How does it know where to start and where to end? If you can answer these questions, you're almost there. (Hint: Look at how your Queue is implemented...)

Array Lists and Extendable Arrays

Overview:

One major weakness of traditional arrays is that they require a fixed capacity to be specified ahead of time. If the number of elements stored in the array is much smaller than the fixed capacity, space is wasted, but if the number of elements exceeds the capacity, the program will crash.

Thus, instead of using traditional fixed-capacity arrays, the java.util.ArrayList class uses extendable arrays, which have a mechanism for handling overflow. When an overflow occurs (ie. the number of elements is equal to the capacity of the array and an add method is called), a new array with twice the capacity of the old array is created, the elements of the old array are copied into it and then the old array pointer is updated to indicate the new array. Then the new element is inserted into the new array.

Some Pseudocode:

Let's say we have an ArrayList S and an array A with capacity N storing the elements of S. Then... an overflow:

1. Allocate an array B of capacity 2N
2. Let B[i] ← A[i], for i=0,...,N-1
3. Let A ← B
4. Insert the new element into A

ArrayList ADT:

A Java implementation of an array list ADT using an extendable array. Note that this is not quite the same as the implementation you will be doing.

public class ArrayIndexList implements IndexList {
	private E[] A;					//array storing elements of indexed list
	private int capacity = 4;	    		//initial length
	private int size = 0;		     		//number of elements stored in list

	public ArrayIndexList(){
		A = (E[]) new Object[capacity];
	}
	
	/* inserts an element at a given index */
	public void add(int r, E e) throws IndexOutOfBoundsException {
		checkIndex(r, size()+1);
		if (size == capacity) {			//overflow!
			capacity *= 2;
			E[] B = (E[]) new Object[capacity];
			for (int i=0; i<size; i++)
				B[i] = A[i];
			A = B;
		}
		for (int i=size-1; i>=r; i--)		//code to shift elements up
			A[i+1] = A[i];
		A[r] = e;
		size ++;
	}

	/* removes element at a given index */
	public E remove(int r) throws IndexOutOfBoundsException {
		checkIndex(r, size());
		E temp = A[r];
		for (int i=r; i<size-1; i++)		//code to shift elements down
			A[i] = A[i+1];
		size--;
		return temp;
	}
}