Assignment 06a

Task

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; interfaces; stacks.

Steps

In this A06 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 A06b.

Step 1: PyramidStack

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. (This is not a standard or common data structure, by the way. It will be useful for A06b, 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, and 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 countLessThan that returns the number of items in the stack that are smaller than the given item. 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 countLessThan(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: Strings, Integers, Doubles, etc.

Step 2: UsernameA06a

Write a main method that prompts the user to enter Strings. For each String, save it if it is "less than or equal to" all the other strings the user has entered so far. Use the normal compareTo behavior to determine String ordering. This is by character-encoding order, which is basically alphabetically with capitals before lowercase. (In other words, just use your PyramidStack to store all of the entered strings that the stack will accept.)

Let the user know whether you saved each input or not. You may explain the rules behind saving a String to the user or not, as you choose. If you explain the rules, you might call countLessThan when you refuse to a save a string in order to explain how many of the saved Strings are smaller than the given value.

If the user enters nothing (that is, just hits enter), end the program and print all the Strings you saved on one line in the order that you saved them.

Sample Output

This program will save some of the strings you enter.
Enter a string: hi there
String saved.
Enter a string: thanks
String NOT saved.
Enter a string: save all my strings!
String NOT saved.
Enter a string: Lousy program
String saved.
Enter a string: I'm leaving
String saved.
Enter a string: quit
String NOT saved.
Enter a string: Bye
String saved.
Enter a string: 

Saved 4 strings: hi there, Lousy program, I'm leaving, Bye

What to Submit

Create a .jar file named UsernameA06a.jar. This should include:

Upload your UsernameA06a.jar to Tamarin.

Remember to follow the course coding standards on all assignments.

Grading [45 points]

5 - Compiles
35 - PyramidStack
Takes only Comparable items (5). Accepts only new items that are <= current top, else throws an IllegalArgumentException (10). toString() returns a single-line String listing the current stack elements from bottom to top (10). countLessThan(E item) returns the number of items currently in the stack that compareTo says are smaller than the given item (10). Other methods, such as size(), should still work correctly.
5 - UsernameA06a
Continues to read in user input until the user enters nothing, storing each entered line into a PyramidStack, if possible. Prints the final stack on one line.

Discussion

This assignment involves the following concepts.

Inheritance and Reuse
When you extend Stack, you will inherit all the members defined in the provided Stack class. You will automatically be able to refer to 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.
Overriding

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.

Polymorphism

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.)

Sorted data structures
Note how the restrictions on what you can push on to a PyramidStack means that its contents will always be sorted from smallest-to-largest as you move down the stack. Encapsulation guarantees this invariant since there is no other way to get an item into the stack except through the push method.

FAQs

PyramidStack<E extends Comparable<E>>? Why is there an extends in the generics part?
This is an example of an upper bound on the type parameter E. It says that E can be any class that extends (which, with type parameters, is the same thing as implements) the Comparable interface.

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

The description of PyramidStack says to push values onto the stack only if they are "smaller or equal to" the current top. Do you mean smaller in terms of length or something?
No. I meant "smaller" according to the compareTo method and that type's natural ordering:
  left.compareTo(right) <= 0
means left is less than or equal to (smaller or same size as) right.

So, with Integers, this would be by value, with 5 being smaller than 8. Strings are sorted alphabetically... sort of. They actually go by character position in the character encoding, so usually capitals come before lowercase letters. So "catastrophe" would be "smaller" ("less than", "come before") than "dog". (I guess that is a little confusing to user "smaller" with Strings, rather than "less than".)

When writing your PyramidStack, just use the compareTo method of whatever item is pushed onto the stack and you'll be fine.

How do I write PyramidStack's toString() method?
The toString() method is a little tricky because you have a linked list of nodes with one-way pointers. The pointers/links between nodes go from the top of the stack towards the bottom, but you need to print the stack in bottom-to-top order. So just looping through the nodes in order and building a String won't work.

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 to 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 rather 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.

I get a compiler error when I try to call the countLessThan method in main.
If you declared your stack variable like this:
  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. countLessThan 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>();