Make sure you read the sections in the above on how to interpret CodeLab string comparison feedback
Overview
In this lab, you will be introduced to those containers of the Java Collection Framework (JCF) that correspond to the ones presented in
Lecture 5.
the purpose of this lab is to acquaint you with the basic operations of the containers we presented in Lecture 5
later on we will use those containers when we code some 'classic' applications
some of the containers
are directly implemented by containers in the JCF
for example List is implemented by LinkedList and ArrayList
are indirectly implemented by containers in the JCF
FIFO Queue is indirectly implemented by ArrayDeque
not implemented at all by containers in the JCF
Bag has no direct or indirect implementation in the JCF
some of the methods used do not match those in the interfaces presented in Lecture 5
in some cases, it's simply the method name that changes
in others, the JCF method to be used has a different signature. You can still leverage the JCF method, but you may have to supply
arguments or otherwise massage things.
we will not be delving into internal implementation issues until later
The Java APa is your source for information about the JCF and its containers.
This lab asks you to code the demo apps of Lecture 5. It is purposely meant to be as straightforward as possible, to 'warm you up' for subsequent
labs. The work consists of two relatively minor modifications to those apps:
change of container
change of elements type
Change of Container
What you will be doing in this lab is taking the demo apps from Lecture 5 and modifying them so they run against Java's containers.
the apps in Lecture 5 ran against containers that I wrote (and which you in turn will be writing in a future lab).
it's not much work to modify the demo code to work with the Java containers.
as mentioned above, some of the containers have no real representation in Java's framework; others will be implemented
by containers with similar behavior.
we will skip the former entirely for the moment
I will elaborate on the latter implementations; several of them have direct representations; some have several
reasonable but indirect representations … you will be exploring them all
Change of Element Type
Instead of an element type of Integer, you will be demoing containers whose element type is String.`
I want to make sure you actually think about the code and become a bit familiar with it (for later labs). Changing the element type from Integer to String
will hopefully do just that.
Once again, this is not meant to be a challenging lab; rather one that gets you comfortable with:
the containers as expressed in JCF, in particular their operations
working with the containers, i.e., using their interface
Two Other Important Items
When you are first developing your code in your IDE), you will notice output that does not match the output of the lectures (aside from the change from Integer to String). This is due to the fact that
up until now we were running again my (and your) classes, and the output was from the behavior of those containers. In this lab you are now using the JCF containers whose behavior is slightly different:
The lectures (including 5) have been printing the containers using {}'s as the delimiters. However, JCF uses []'s. (This is out of your control,
you are writing the app, but using the JCF containers, i.e., it is THEIR toString not yours).
The priority queue in JCF removes the smallest element, not the largest as presented in Lecture 5.
The CodeLab solutions have taken the above changes into account (so, for example, the output that you will be matched against in CodeLab will have []'s rather than {}'s.), so you shouldn't have an problem.
Just be aware when you are developing your code in your IDE that the output will be slightly different than the demo output in Lecture 5 (the []'s and the order of removal from the priority queue).
And this is in addition to the fact that your output will be of the Str10, Str20 form rather than 10, 20.
Details: The Containers
As it turns out, Sequence, Bag, and Associative have no direct representation in the language.
actually, as we pointed out in Lecture 5, Sequence is really just List, which is what Java calls that container, so there's no point
in implementing that. Similarly Bag and Associative are the same container type, and in this case there is no such container in the framework,
so you will not be transforming their demos.
The Freebie: Stack
To put you on the right track, I am providing the solution for Stack. This is not all that generous of me … of all the
containers, Stack is the closest in terms of its transformation to Java. However, what I am providing is useful in two ways:
it will give you an idea of what one of these apps look like
it will serve as an example of changing the element type from Integer to String
import java.util.Stack;
public class StackDemo {
public static void main(String [] args) {
System.out.println("========== Stack ==========");
Stack<String> stack = new Stack<>();
System.out.println(stack + " (" + stack.empty() + ")");
System.out.println();
System.out.println("Pushing");
System.out.println("-------");
for (int i = 0; i < 10; i++) {
System.out.print("Str" + (i * 10) + " -> ");
stack.push("Str" + (i * 10));
System.out.println(stack + " (" + stack.empty() + ")");
}
System.out.println();
System.out.println("Popping");
System.out.println("-------");
while (!stack.empty()) {
System.out.print(stack + " (" + stack.empty() + ")");
System.out.println(" -> " + stack.pop());
}
System.out.println(stack + " (" + stack.empty() + ")");
}
}
Notes
(import jaba.util.Stack;) Since we're running against Java's containers, we import them
Please avoid using the '*' format of the import statement, i.e., only import those classes your demo code is
actually using
(Stack) There is a Stack class in Java; however, it is actually not part of the Framework — we'll explain
why much later when we cover the structure of that Framework.
("Str" + (i * 10)) Using an int element type in previous demos made it easy to generate sample data for the containers by using a for loop;
generating pattern-based String data is not as simple. One could set up arrays of sample String data, but a simpler way is to stick with the int values and convert them to
String. To keep things from getting too boring (i.e., the output of the int 3 and the String "3" are both 3), we'll add the prefix Str to
our values emphasizing their 'String'ness.
The traditional operation names for a stack are push, pop, and empty, and the
Java Stack class conforms to that convention. The Stack I presented in Lecture 5 used isEmpty and thus
the demo code for Java had to make that change.
Once the code has been transformed to run against the Java container, it's merely a matter of compiling and running it. No code is needed from me; all that is required
is the app and the Java class. Here is the output:
You should first code up your demos in IntelliJ … as I said above, all you need is your demo code, no additional classes from me; you are running again predefined Java containers.
Unlike most other labs you will eventually submit to Codelab, you are basically given the logic (and test cases) for this (albeit indirectly via the demo output), so odds are once you get an execution, you will be able to
successfully submit it to Codelab.
Codelab Notes
Codelab will be checking the correctness of your code by comparing your output against my 'correct' output, and there you should know what your output should look like.
The Stack example above illustrates the differences between the Lecture 5 output and that of the this Lab … the storage/retrieval patterns are the same, the main difference is the values themselves; i.e.,
Stri vs i (e.g. Str10 vs 10). The other difference is when order comes into play, for example for priority queue, and the associatives (set, and map),
where the order of integers and our String values may differ (e.g. 2 < 10, but Str2 > Str10).
Your Turn
Now it's your turn to create the demo apps for the containers specified below. I will guide you as to which Java containers to use; for several of the containers there is more than one choice,
and you will be asked to implement the container using each of them.
for some of those choices, the reason will be immediately clear; for others, we will have to wait until we get 'under the hood' of the containers internals before the
reason for different implementations becomes clear
in several cases, it is not obvious, nor even clear why the classes are named the way they are; again, all will eventually become clear.
Some Suggestions for Helping you Expedite Your Coding
Cut and paste as much as you can:
from one demo to the next, especially if they are demos of the same container (i.e., different implementations)
I've tried to present the various implementations in an order that simplify things for you. If you are feeling unsure about how to do this lab, try to follow the order
and read the notes for each demo; they are meant to help guide you.
Lab 5.1 Priority Queue Demo (using PriorityQueue)
This is basically a freebie as well — except you are the one coding it. The class name and the operations are the same in the JCF as they were in the priority queue presented in Lecture 5, just as they are
for the Stack class above. Add the import, the String generic element type, and the Str prefix to the values, and you should be done. It's a good warm-up for the ones after this.
Important: Our presentation of the priority queue has been that of a max-priority queue, i.e., one in which the largest element is removed. This is in contrast to a min-priority queue
where the smallest item is removed. The priority queue in the JCF is a min-priority queue.
Lab 5.2 Deque Demo (using ArrayDeque)
This is the first class that requires some modification to the class/methods. The class name here is slightly different (ArrayDeque in JCF vs the Deque class of Lecture 5), however, the operations (i.e. methods) are the same.
For each of the following demo implementations, the parenthesized item is the Java class you are to use for your container. In our case, this means that the Deque container demo of Lecture 5 should
be run again the ArrayDeque class of the Java Framework.
Here is the relevant fragment of code for this implementation:
import java,util.ArrayDeque;
public class DequeDemo {
public static void main(String [] args) {
System.out.println("========== Deque ==========");
ArrayDeque<String> deque = new ArrayDeque<>();
System.out.println(deque + " (" + deque.isEmpty() + ")");
System.out.println();
…
…
i.e., create an object of the specified Java type (I kept the 'abstract' class name for the variable, i.e., deque, rather than arrayDeque (this minimizes the code I have to modify);
feel free to do otherwise.
Although I have told you the class you should run each demo against, I have not specified which operations you should use; you should go to the API to figure out which operations
correspond to the set of operations of the desired container. In many cases, the Lecture 5 container and its Java correspondent's operation (method) names are the same; sometimes the
names are different and sometime, their prototypes (and thus behavior) are different as well. This is a good opportunity for you to become acquainted with the method names of some of these Java containers.
Lab 5.3 Deque Demo (using LinkedList)
Same idea as Deque/ArrayDeque. If you haven't started copying/pasting yet, this is a good time to start doing so (from the previous lab). (you should be able to open both projects in separate windows of your IDE, maybe even in the same window, or at worst
copy from one then close it and open the second).
Lab 5.4 Deque Demo (using ArrayList)
The operations (methods) of ArrayList that give you the behavior of a deque require a little bit of thought. Remember, you need to be able to insert and remove from each end. If necessary, skip this one and come back to it.
Lab 5.5 Stack Demo (using ArrayDeque)
Should be fairly straightforward, aside from the change in class name.
Lab 5.6 Stack Demo (using LinkedList)
Should be fairly straightforward, aside from the change in class name.
Lab 5.7 Stack Demo (using ArrayList)
The same approach as Deque using ArrayList, but slightly simpler; you only need to be able insert and remove from the same end
Lab 5.8 FIFO Queue Demo (using ArrayDeque)
Should be fairly straightforward, aside from the change in class name.
Lab 5.9 FIFO Queue Demo (using LinkedList)
Should be fairly straightforward, aside from the change in class name.
Lab 5.10 FIFO Queue Demo (using ArrayList)
Similar to the ArrayList implementations of Deque and Stack.
Lab 5.11 List Demo (using LinkedList)
Should be straightforward, aside from the change in class name. You also need to change the comparison to a String comparison, and remove elements less than "Str1000"
Lab 5.12 List Demo (using ArrayList)
Should be straightforward, aside from the change in class name. You also need to change the comparison to a String comparison, and remove elements less than "Str1000"
Lab 5.13 Set Demo (using HashSet)
Nearly straightforward, though pay attention to the order of the elements when printed, and compare it to the TreeSet implementation.
The only issue is the removal of the elements of the set. … if you think about it, you'll see that it's not that simple. What I did was to generate random
numbers in the range of the index variables of the 'add' loop (i.e., 0 … 9), multiplied them by 10 (to get the actual #'s i wanted to add: 0, 10, 20 …)
then checked if they were in the set and if they were, I removed them, continuing this until the set was empty.
Lab 5.14 Set Demo (using TreeSet)
Again, nearly straightforward, though pay attention to the order of the elements when printed, and compare it to the HashSet implementation
The only issue is the removal of the elements of the set. … if you think about it, you'll see that it's not that simple. What I did was to generate random
numbers in the range of the index variables of the 'add' loop (i.e., 0 … 9), multiplied them by 10 (to get the actual #'s i wanted to add: 0, 10, 20 …)
then checked if they were in the set and if they were, I removed them, continuing this until the set was empty.
Lab 5.15 Map Demo (using HashMap)
Same comments as HashSet, i.e., contrast the order of the keys to those of TreeMap
I should have played the same game with removal as I did with Set, but for some reason I simply used the knowledge of the Map's key and removed them 'directly'
Lab 5.16 Map Demo (using TreeMap)
Same comments as TreeSet, i.e., contrast the order of the keys to those of HashMap
I should have played the same game with removal as I did with Set, but for some reason I simply used the knowledge of the Map's key and removed them 'directly'