Pre-existing Java packages start with "java.", but you have also been creating your own packages. Until now, we have only used them in the lab in which we are currently working. However, now that we are writing and implementing ADTs, but you are 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:
package cs170utils;The combination of having this line and residing in the cs170utils directory tells Java that these classes are in the cs170utils package.
import cs170utils.and wait. You should see eclipse suggest all of the classes that you have included in that package. You can either select an individual class or type "*" to import all of them.
In class we discussed the Queue data structure. Save the following files to your directory:
Now proceed as follows:
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 front and back, 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.
How do you know when your queue is at capacity? When you try to enqueue you need to check this. If you need more space, you need to call increaseSize() - this method is one of the trickiest parts of the array implementation. (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.
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.