CPSC 170 Lab 11: Packages and Queues

Packages

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:

1. 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).
   
   
2. 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.
   
   
3. Now you have to tell Java where to find this package, which means modifying your classpath.  You can do this by entering the following command at the command prompt:
   

   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 type:

   export CLASSPATH=$CLASSPATH:~/cpsc170
   
   Note that you DO NOT include cs170utils as part of the path.

4. The command you just issued works for your current session; when you logout, the classpath will revert to its previous state.   Clearly, this is not something that you want to do this every time you log in.   Fortunately,  whenever you login, the system looks for a special file called ".bashrc" to find a list of personal settings and commands to execute.  This is called a logon script.   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 export command from above.  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.   Now whenver you start a new shell (i.e. login) your classpath should be set properly to find your cs170utils


5. 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:

1. Complete the method definitions in LinkedQueue.java. Remember:
• In enqueue and dequeue you have to maintain both the front and back pointers -- this takes a little extra thought. 
  
• Initially, we want to return null if  dequeue is called on an empty structure - we will "fix" this later in the lab.
2. Study the code in TestQueue so you know what it is doing, then compile and run it. Correct any problems in your LinkedQueue class.
3. 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 is increaseSize(). (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. 

4. 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.
   
   
5. Finally - exceptions. Generally, methods throw exceptions if they can't carry out their tasks in a meaningful way. If there is nothing in the queue, a dequeue operation should throw 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. One of the design decisions you have to make is determining if  this new exception should be "checked" or "unchecked" (does it extend Exception or RuntimeException)   I will leave this decision up to you, but you must justify your decision in the comments of  EmptyCollectionException.java.   If you aren't sure, or don't have a good rationale, try it both ways to figure out what the ramifations are.

HAND IN: