Goal of this homework: More practice with abstract data types. You will implement both stacks and queues, and use both.
Collaboration policy for this homework: You must follow the CS Department Academic Integrity Code and this time may not collaborate with another student (in contrast to the previous homework). Of course, you may get help from the course staff.
How to hand in your work: instructions, upload page
What to hand in (all packaged up in a zip or tar file):
JavaStack.java (mostly written for you)
EditableString.java (outlined for you)
QueueFullException.java (easy)
QueueEmptyException.java (easy)
ArrayQueue.java (discussed in textbook)
ArrayQueueStack.java
As usual, you should write clear, readable code (see section 1.9.2 of the textbook). Avoid duplicated code. Make the code as simple and direct as possible. It should lay out a natural way of thinking about the problem.
A doc subdirectory containing HTML documentation
that you have generated with the command javadoc -private
-linksource -d doc *.java. The graders will look at this
documentation, so you should provide javadoc comments for all of
your methods, including private ones.
A Readme file that contains your
answers to miscellaneous questions on the homework (i.e., answers that
don't go in any other file). Usually these are English paragraphs or small
fragments of code.
Acknowledgments: Many thanks to Yuan Chen (one of your CAs) for her great work writing the GUI class, test-driving the assignment, and providing some of these instructions.
You use a word processor or text editor every day. Those programs add new features every year. But at their core, they simply let a user modify a sequence of characters. How is this sequence represented?
Since the user can insert or delete characters in the middle of the string, you might wish to use a List data structure as in chapter 5. In particular, a doubly linked list of characters would support efficient insertion and deletion into the middle of the sequence.
But suppose the user were only adding and deleting characters from the end of the string, by typing and backspacing. Then you could get away with using a Stack, which is simpler and cheaper.
But in fact, the user doesn't do so much more than that! The user
only adds and deletes characters next to the cursor. You can
therefore get away with using two stacks. One stack holds the
characters to the left of the cursor. The other stack holds the
characters to the right of the cursor. This diagram shows how to
represent the word elephantine with the cursor between
the letters p and h:
LEFT STACK RIGHT STACK
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
|_e_|_l_|_e_|_p_| |_h_|_a_|_n_|_t_|_i_|_n_|_e_|
bottom top top bottom
To move the cursor right, you would just pop the h
from the right stack and push it onto the left stack:
LEFT STACK RIGHT STACK
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
|_e_|_l_|_e_|_p_|_h_| |_a_|_n_|_t_|_i_|_n_|_e_|
bottom top top bottom
In this assignment, you'll build EditableString - a
small word-processor class that uses this 2-stack representation. The
class will include methods for inserting and deleting characters, and
for moving the cursor. To test your class, we've provided a cute
EditableStringWindow class that puts a window on the
screen. Whenever the user presses a key, the window calls the
appropriate one of your EditableString methods, such as
backspace.
Your initial version of EditableString will just use
the stack class that is built into Java. In the second half of the
assignment, you will switch from using data structures to
implementing them. In particular, you will implement your own
stack class. The word processor should then work just as well with
your stack class as it does with Java's!
Stack and Queue are the interfaces
given in the textbook. Similarly, StackFullException
and StackEmptyException
are from the textbook.
JavaStack
implements Stack. It uses the methods of the standard
java.util.Stack to do most of the actual work, but it
provides a different interface to those methods, namely the one
specified by Stack. Such a class is called a
wrapper class (or adapter class), because it takes an
existing implementation (the java.util.Stack class) and
wraps it in some pretty wrapping paper (the Stack
interface) so that it has a different appearance from the outside.
The central class EditableString is
provided in skeleton form for your convenience. The methods
are there but they don't do anything yet except maybe return a
value. Such placeholder methods are called stubs. You will
replace them with real methods.
EditableStringWindow
is the GUI interface that will call your code.
JavaStack and EditableStringYou should be able to compile and run
EditableStringWindow right away. You can see what the
interface will look like, but it won't do much, since all the methods
it calls are still stubs!
Your first job is to read through JavaStack.java and
fill in the JavaStack.pop method, which is a stub. Make
sure you know exactly what that method is supposed to do (by looking
at the documentation of the Stack interface). To
understand how to implement it in terms of
java.util.Stack, look at the online java.util.Stack
documentation. (Note: This is found at the standard source of Java
platform documentation, java.sun.com.)
Your second job is to fill in all the methods of
EditableString.java, replacing the stubs. Test your
methods directly, and by using java EditableStringWindow.
Just for fun, you could also try java EditableStringWindow
2, which creates two EditableStringWindows on the
very same EditableString; thus edits in one window also
affect the other window.
Important notes:
As usual, keep things simple and obvious. Each method's body should do as little work as possible, and pass the rest on to a friend.
As much as possible, avoid calling the methods of the two
underlying stacks! Several of the EditableString
methods (e.g., moveToStart) can be implemented just
by calling other EditableString methods. This
strategy will also make your method bodies higher-level and easier
to read, and will make your class easier to modify. It will also
help you avoid duplicating low-level code.
For example, to implement toString, your program will
have to iterate through all the characters on both stacks, and that
means moving characters back and forth between the stacks. But don't
write it that way explicitly. Help yourself by using the higher-level
methods that you have already written, like moveToStart
and moveRight.
Along the same lines, when you are implementing
toStringCursor, remember the puzzle in lecture about how
a mathematician boils water. Don't duplicate code - instead, figure
out how to reduce to a problem that has previously been solved!
Note: In the previous assignment, you represented
numbers by Russian dolls. Here, you are representing a string by
a pair of stacks (thus making it efficiently editable). So in the
same spirit as the last assignment, you should not use the
String class in your implementation -- except inasmuch
as a method's signature requires it to take or return a
String.
In particular, you will need to manipulate Strings
on the character level when converting between
EditableString and String. Such
conversions are to be carried out by the method
toString() and the constructor
EditableString(String left, String right).
Implementing the method search(String s) will also
require you to look at the individual characters of
s.
For those cases, you may be interested in the String
class's documentation, particularly the constructor String(char[]
value) and the method charAt(int
index).
Hint: It may help to simplify your code and organize your thinking if you write a few private methods, such as these:
/** @return The character immediately after the cursor.
* @throws StackEmptyException if there is no such character. */
private char charNext() {
...
}
/** Is the string s immediately after the cursor?
* If so, move the cursor past it and return true.
* Else, leave the cursor where it is and return false.
*/
private boolean followsCursor(String s) {
...
}
|
Hint: Here are some potentially tricky cases for search.
Make sure that a search for abc works correctly if the
text is xxxababcde. Also, note that even if the cursor
is already at the end of the string, the search method
could still return true (if you are searching for the empty string),
so make sure it does so. (The GUI reports the true/false result of the
search method in the status bar at the bottom of the window.)
The next part of the assignment is to implement a queue using a portion of an array. This is discussed extensively in chapter 4 of your textbook, so we won't give you many more instructions here.
Specifically, you should write an ArrayQueue
class that implements the Queue interface that was
provided to you. Your ArrayQueue class should also
have 2 constructors:
new ArrayQueue(50) should create
a queue that can hold up to 50 elements
new ArrayQueue() should create
a queue of some default size
Make sure that you throw QueueEmptyException and
QueueFullException as appropriate; see the
Queue interface for details. These are unchecked
exceptions (because they are subclasses of
RuntimeException), so they do not have to be mentioned in
the method signatures.
As always, test your class carefully.
Finally, you'll implement a stack. The book already gives you code for implementing stacks in terms of arrays and in terms of linked lists. So what other ways are left for you to try?
Well, a stack can theoretically be implemented in terms of a queue! That's because you can get to any element on a queue by repeatedly dequeuing the front element and enqueuing it again at the back. So if you want to remove ("pop") the element that you've just enqueued ("pushed"), you can get to it it by "cycling once around the queue."
Of course this is a silly way to implement a stack, just like doing arithmetic with Russian dolls is theoretically possible but silly. However, it gives you a chance to try out your queue code on a real problem.
Write a class ArrayQueueStack that implements
Stack. It should contain a protected ArrayQueue
q. All the stack methods should be implemented just by calling
queue methods. You should take care to throw
StackFullException and StackEmptyException
rather than the corresponding queue exceptions, even though the stack
exceptions are "morally equivalent" to the queue exceptions.
Now for the punchline. Change the constructor of
EditableString so that it initializes left
and right by calling new ArrayQueueStack()
rather than new JavaStack(). Recompile everything.
EditableStringWindow should work just as before!
To check that your exceptions work, you should change new
ArrayQueueStack() to new ArrayQueueStack(30).
Then if you type a line or two into the window, your methods should
throw a StackFullException. The GUI explicitly catches
this exception, and should display a message about it in the status
bar at the bottom of the GUI window.
Readme:
moveLeft method (a) when the stacks are implemented
with JavaStack? (b) when the stacks are implemented
with ArrayQueueStack?
moveToStart method.
Jason Eisner - jason@cs.jhu.edu - $Date: 2004/02/12 10:10:54 $