CPSC 170 Lab 10: Packages and Queues

As usual, create a lab10 subdirectory for today's lab, open this document in Mozilla, and start emacs.

Packages

Before we get into queues, it's time we talked about Java's package structure. Java allows classes to be grouped into packages; for example, the package java.util contains general java utilities such as the Scanner and Random classes, and the package java.awt contains graphics/windowing classes. We often import these packages when we want to use one or more of their classes; if we didn't, we would have to prefix the class name with the package name every time we used it (e.g., java.util.Scanner scan = new java.util.Scanner(System.in)).

Pre-existing Java packages start with "java.", but you can also create your own packages. We haven't had the need for this until we started writing and implementing ADTs, but now you're probably finding that there are classes such as LinearNode and LinkedIterator that you are copying from one directory to another so that you can use them for different implementations. This is a nuisance and a waste of space, and it paves the way for having numerous slightly different versions of common utilities -- usually not a good idea. The solution is to put these utilities in a single package, tell the Java system where to look for this package, and import it as needed. To do this you need to follow these steps:

Create a directory called cs170utils. I don't care where you put it (although it would probably make sense in your cpsc170 directory), but you must call it exactly this, including capitalization (or lack thereof).
Copy classes that you would like to share, such as LinearNode and the iterator classes, into this directory. Then modify each file (e.g., LinearNode.java) by adding the following line as the first line in the file:
```
   package cs170utils;
```
The combination of having this line and residing in the cs170utils directory tells Java that these classes are in the cs170utils package.
Now you have to tell Java where to find this package, which means modifying your classpath. Open file .bashrc (don't forget the leading .) in your home directory; if you don't have such a file, create a new one. Add the following line (anywhere; at the bottom is fine):
```
export CLASSPATH=$CLASSPATH:**directory**
```
where **directory** is the directory where you put the cs170utils package. So if you put it in your cpsc170 directory, and if your cpsc170 directory is directly under your home directory, you would add this line:
```
export CLASSPATH=$CLASSPATH:~/cpsc170
```
If there is already a line like this (export CLASSPATH=$CLASSPATH:...) in your .bashrc, just add :**directory** to the end of it, with **directory** interpreted as above. Note that you DO NOT include cs170utils as part of the path.
You have to either start a new shell (which executes .bashrc) or give the export command to the command line for the new classpath to take effect.
That's it! Now you just have to import cs170utils any time you want to use these classes.

Queues

In class we discussed the Queue data structure. Save the following files to your directory:

QueueADT.java -- The Queue ADT interface.
LinkedQueue.java -- A skeleton for a linked implementation of a queue.
ArrayQueue.java -- A skeleton for an array implementation of a queue.
TestQueue.java -- A simple program that creates and manipulates some queues.

Now proceed as follows:

Complete the method definitions in LinkedQueue.java. Remember that in enqueue and dequeue you have to maintain both the front and back pointers -- this takes a little extra thought.
Study the code in TestQueue so you know what it is doing, then compile and run it. Correct any problems in your LinkedQueue class.
Complete the method definitions in ArrayQueue.java. Be sure that you use a circular implementation of the queue -- don't move everything down when you enqueue or dequeue. This means that whenever you increment an index, you have to do it mod the arraysize (use the % operator). As for the linked case, remember to maintain both the front and back indices when you modify the queue. You also have to initialize them, which can take some thought. One possibility is to initialize front to 0 and back to -1. This may look odd, but it works nicely -- when you enqueue the first item, back will increase to 0, which is just what you want. Just be sure to use the number of elements, not the values of front and back, to determine whether the queue is empty.
The trickiest parts of the array implementation are increaseSize() and iterator(). (Remember that increaseSize is a private method that is called from enqueue when the array is already full. I did not put it in the skeleton, so you'll need to add it.) The front of the queue may not be at location 0 in the old array, but when you increase the size you may as well put it at location 0 in the new array (it's even more complicated if you don't). So your loop that copies needs to keep track of two sets of indices -- the index in the old array, which will need to wrap around, and the index in the new array, which will start at 0. You will need to do something similar in the iterator, since ArrayIterator assumes that the array elements start at location 0. Here you don't need to increase the size of the array, but you do need to create a new array and copy the elements to it starting at location 0 before passing the array to the ArrayIterator constructor. Do not modify the ArrayIterator class!.
Modify TestQueue.java so that it creates an ArrayQueue instead of a LinkedQueue. Don't change anything else in the file. Compile and run it, and be sure that it works as before.
One more thing: exceptions. You may have noticed that in the collection code in the text, methods throw exceptions if they can't carry out their tasks. For example, p. 234 gives code for the dequeue method in the LinkedQueue class. If there is nothing in the queue, it throws an EmptyCollectionException, passing the string "queue" to indicate what collection was empty. We have been returning null in this situation, perhaps a reasonable design decision but one that provides less information than throwing an exception.
Revisit your queue implementations and make dequeue and first throw an EmptyCollectionException if there is nothing in the queue. The catch (no pun intended!) is that the EmptyCollectionException is not defined in Java, so you'll have to define it yourself (as part of the cs170utils package, of course). Exception classes are typically very simple; they are just placeholders for a message. Here is a modified version of the OutOfRangeException class from Lewis and Loftus. The only change is that it extends RuntimeException instead of Exception (we'll talk about why in class). You should model your EmptyCollectionException class after it.