Write a subclass of Stack with slightly different behavior and use it in a simple program.
Text: 3.1, Java review.
Concepts: inheritance, overriding, polymorphism; stacks.
In this A05 assignment, you will practice a number of different Java concepts by building different reusable classes. You will use some of those classes here, and then you will reuse them in a simulation program in A05b.
In lecture, we discussed a generic Node and node-based Stack implementation:
You will need both of these files, but do not change them.
You will now author a special kind of stack called a PyramidStack. A pyramid stack requires that each item pushed onto the stack must be of the same size or "smaller" than the current top item. However, we will define "smaller" in terms of compareTo, which is to say "coming earlier in the natural order for that type". (A PyramidStack is not a standard or common data structure, by the way. It will be very useful for A05b, though.)
Since most of the behavior is otherwise the same as Stack, you will implement the PyramidStack by sub-classing Stack. You will inherit the peek, pop, and size methods, but you will override the push method. If someone tries to push an item that is "larger" than the current top element of the stack, the push method should throw an IllegalArgumentException. (This exception is in java.lang, so it does not need to be imported.) Since the pushed items will need to be comparable to each other, a PyramidStack should only take Comparable items.
Also, it would be handy to print out the contents of a stack. Write a toString() method in PyramidStack to return a representation of the stack's current contents. This String representation should be on one line, showing the stack elements from bottom-to-top as you read the line left-to-right. Additional formatting, such as commas between elements or [brackets] around the whole string, is up to you.
Write a method named countBefore that returns the number of items in the stack that come before (ie, are "smaller") than the given item in that item's natural ordering. This essentially tells you how many pop operations you would need to perform before you could safely push the given item. If the stack is empty, this method should return 0.
Therefore, create the following class:
public class PyramidStack<E extends Comparable<E>> extends Stack<E> {
@Override
public void push(E item) throws IllegalArgumentException { ... }
@Override
public String toString() { ... }
public int countBefore(E item) { ... }
}
You may write additional methods if you like.
You should now be able to create a PyramidStack and push and pop its contents. You should be able to create a new PyramidStack that handles any specific Comparable type: Strings, Integers, Doubles, etc.
Write a program that asks the user to enter strings. Save each string only if it comes before (in the natural order for strings) all the other strings the user has typed so far and if the string is shorter than any of the previous strings. (This can be easily done by using two PyramidStacks: one for the Strings and one for the lengths of the Strings.)
Let the user know whether you saved each input or not. You can explain the rules behind saving an input to the user, or you can make the program as a sort of a puzzle game for the player to figure out. It would probably be helpful to call countBefore when you refuse to a save a string in order to explain how many of the saved Strings come before or are shorter than the given input.
If the user enters nothing (that is, just hits enter), end the program and print all the strings that you saved on one line and all of their corresponding lengths on another line. (Other than these final two lines, the format/content of any other output is up to you.)
A05> java ZtomaszeA05a This program will save some of the strings you enter. Can you predict which ones will be saved? (Enter nothing to quit.) Enter a string: many many words String saved. Enter a string: even more words String saved. Enter a string: will it save anything then? String NOT saved: Already saved 2 strings that should come before this one. Enter a string: come before? You mean alphabetically? String NOT saved: Already saved 2 strings shorter than this one. Enter a string: shorter too? String NOT saved: Already saved 2 strings that should come before this one. Enter a string: a short string String saved. Enter a string: I got it! String saved. Enter a string: Capitalized String NOT saved: Already saved 1 strings shorter than this one. Enter a string: 9000! String saved. Enter a string: 2go String saved. Enter a string: Saved strings: many many words, even more words, a short string, I got it!, 9000!, 2go Corresponding lengths: 15, 15, 14, 9, 5, 3
Create a .jar file named UsernameA05a.jar. This should include:
Upload your UsernameA05a.jar to Tamarin.
Remember to follow the course coding standards on all assignments.
This assignment involves the following concepts.
this.top and the methods in PyramidStack as if they were defined in PyramidStack. This lets you reuse that Stack code in PyramidStack without rewriting it.
You will then change the normal push behavior of Stack by overriding that method. Remember that you can still call the original version of any of the superclass's methods from within PyramidStack, such as by using super.push(item);
The @Override annotations are optional. They just tell the compiler that you are trying to override a method in a superclass or implement a method specified by an interface. This annotation prevents common programmer errors, such as using the wrong signature or misspelling the method name.
In your main method, you can do this:
Stack<String> stack = new PyramidStack<String>();
Although you're using a Stack variable here, the object it contains will still have PyramidStack behavior thanks to polymorphism.
Note that you could easily and significantly change the behavior of your program simply by changing the right side of this line from new PyramidStack<String>(); to new Stack<String>();. The program would then store all entered lines. (It would also break the final output, though, because Stack doesn't provide a useful toString() method.)
PyramidStack<E extends Comparable<E>>? Why is there an extends in the generics part?
If we just used PyramidStack<E> here, a PyramidStack would take any kind of object (like the original Stack<E>). That won't work for us, though, since we need to be able to call compareTo on any pushed element.
If we just used PyramidStack<Comparable<E>>, it would fail to compile for a number of reasons. The main reason is that we have not declared E properly here. But even if this did compile, it means we'd only take Comparable objects. This is a problem for two reasons. First, while we might have Comparable variables, there are no "pure" Comparable objects in the heap. Comparable is an interface, so any implementation must be undertaken by a different specific class. Any instances of those implementing classes (such as String or Integer) would be something other than Comparable instances. Secondly, even if we could overcome that by creating Comparable instance directly, this signature means we would take only Comparable objects, but not any subclasses, such as Integers, Strings, etc.
So we use PyramidStack<E extends Comparable<E>>, which means we'll take any instance of class Comparable (if there were any) or any class that implements Comparable or any subclass of one of those implementing classes.
When a class implements Comparable and its compareTo method, that compareTo implementation defines an ordering for instances of that type. For example, suppose we call a.compareTo(b). If compareTo returns a negative value, it means a should come before b in the natural ordering. If it returns a positive value, b comes before a. If it returns 0, the two values are equivalent in terms of ordering.
Most of the time, a natural ordering is in terms of ascending/increasing values. This means that if a < b in the natural ordering, a has a smaller value than b. This is not always true, though, especially for more complicated types.
For example, consider this code which prints two values in their natural order:
Comparable<???> a = new ???
Comparable<???> b = new ???
if (a.compareTo(b) <= 0) {
System.out.println(a + " <= " + b);
}else {
System.out.println(b + " < " + a);
}
We have not yet specified the ??? datatypes of a and b. Suppose a and b are Integers or Doubles, such as a = -3 and b = 5. For numbers, the natural order is from smaller to larger values. Therefore, the smaller (closer to negative infinity) value will be printed first by this code. The first value printed will be "smaller", "less than", and "come before" the second.
The natural ordering for Strings is defined by String's compareTo method to be in alphabetical order... sort of. Component characters are actually sorted by character position in the character encoding, so usually capitals come before lowercase letters. So if a = "catastrophe" and b = "dog", a would be "less than" or "comes before" b. It starts getting a little confusing to say "catastrophe" is "smaller" then "dog", though.
Finally, suppose we write an HighScore object for use in an arcade game. This object has 3 fields: the player's initials, the score, and a timestamp of when they won the game. We could write a compareTo method for this class to sort two HighScore objects based on the score so that a higher score comes before a lower one. That would be their natural ordering. We could extend this comparison too, so that on a tied score, the HighScore with an older/earlier timestamp should come first. Now if a = [1012, WNR, 07/08/1987] and b = [845, LSR, 08/09/1988], the code above should print WNR's score as coming before LSR's score. "Smaller" and "less than" are certainly not as useful descriptors of this ordering, though.
Conceptually, your PyramidStack is something like this or this. So I just described this as "don't put something bigger on top of something smaller". But, because you're using compareTo for all comparisons, this really means "don't allow a new insertion onto the stack if the new value comes later in the natural ordering then the current top of the stack". That is a more accurate description, but it's a lot wordier and a bit harder to wrap your head around!
There are a number of different options you might consider here.
One is to use a temporary local data structure, such as ArrayList or a regular Stack. You could pop all the elements off into an extra Stack, then add them to a String as you pop them off the extra stack and push them back into the original stack again. So this is sort of like pouring tennis balls from one tube into another and then back into the original tube again. As they go back into the original tube, they'll go past you in the order you need. And when you're done, the original tube is in the same state you started with.
Or, rather than all that pushing and popping, you could work at a lower level by looping through the Nodes, adding the data elements to a separate array, ArrayList, or stack and then build the String from that other data structure.
That's all really heavy-handed though. A much more elegant solution would be to use recursion in a private helper method. If you process the linked list of nodes recursively, you could then append their data to a returned string as you return from the calls... which will give you the order you want with only a few lines of code and no extra data structures required.
Perhaps even better, you might consider prepending to your String rather than appending.
countBefore method in main.
Stack<String> st = new PyramidStack<String>();then, thanks to polymorphism, your
st looks like a Stack but it behaves like a PyramidStack. That can be very handy in certain situations.
However, the flip side of this is that you can only call Stack methods on st because it is a Stack variable. countBefore is not a Stack method. If you want to call PyramidStack methods (behaviors), then you need to use a PyramidStack variable:
PyramidStack<String> st = new PyramidStack<String>();
item.compareTo(this.top.getData()) > 0, you should throw new IllegalArgumentException("Item too big for this stack"); instead of storing the item. (You can customize that error message string or leave it out.)
The reason the Stack should only worry about this one thing and not print to the screen is so you can reuse it. If you make your PyramidStack worry about the length of the item given or if you print to the screen, you will probably have to revise it when you need to use the same class to silently store Meeps without caring about their lengths in A05b. One point of this assignment is to teach you how you have to design your classes if you want to be able to reuse them in different contexts like this.
As just mentioned, a PyramidStack should not enforce both of these rules. Instead, you will need to enforce them in main.
The best way to do this is to use a PyramidStack<String> to store the entered Strings and another PyramidStack<Integer> to store their lengths. (Actually, these bizarre rules were designed so that you would need to create some stacks that work with different data types. This way, you can see the polymorphism of the compareTo method based on the datatype stored in each stack.) Then, each time you get a new String from the user, compare it to the top of PyramidStack<String> and its length to the top of PyramidStack<Integer>.
For example, imagine you have the following stacks.
|coin | |4| |dirt | |4| |helmet | |6| |mountain| |8| ---------- ---
Notice how each item on the string and length stack is smaller than or equal to the item underneath it.
When writing the code in main, you have two options on how to do these checks. One option is to use an if to test that you can really push the new input onto both of the stacks before you push onto either one. If you know both pushes will be safe, you don't have worry about getting any exceptions at all and so you will need no try/catches.
The other option is to just push the items without testing first, using a try/catch to catch the IllegalArgumentException if one of the pushes fails. Here, you need no if tests, but you may need more than one try/catch, and you may need to call pop on the first stack if the first push succeeds but then the second push fails.