Programming Lab #2:
Assigned: Thu 5 Mar 1998
Due: Thu 19 Mar 1998
For this project you will write a program which:
More specifically, you should implement a program which repeatedly reads
commands from a command line and performs input, output and structure
modifications as specified by the user. The specific command structure is
as follows:
Here is a sample run showing typical input/output (you should feel free to use
appropriate introductory text and prompts of your own design):
In order to successfully implement this assignment, you will need access to Weiss'
implementations of stacks, queues and priority queues; these can be found in the
data structures section of his on-line code library.
More specifically, you will need at least an interface and one implementation for
each of the three structures. For example, you could use the
QueueAr.java implementation
of the
the Queue.java interface
and the
BinaryHeap.java implementation
of the
PriorityQueue.java interface.
Ideally, you should not need to modify these interfaces or implementations at
all in order to use them. If you need to change the behavior of the implementation,
it should be done through sub-classing, that is to say, by extending
the class. You will at the very least need to extend these classes in order to
implement the abstract storage structure interface (see below). A good way to
enforce your own comliance with the "no modifications" rule would be to only
download the compiled .CLASS files for the implementations you need.
In order to implement the various commands for the storage structures efficiently,
you should use the abstract storage structure interface described in class. You
can find the relevant files in the directory:
~fruehr/public_html/dsa/code/StorageStructure.
The basic idea, as described in lecture, is that the StorageStructure
interface gives you a means to implement each of the relevant commands (load,
dump and transfer) in an abstract setting, divorced from any particular structure
or its implementations. For example, the load command cn be implemented using a
loop which repeatedly reads input values until a 0 is encountered, and which
uses the tossIn method to put the values into a structure one after another
as they are read in. Because you will supply a "glue code" class definition which
extends (for example) stacks and implements the StorageStructure
interface, if you declare your stack to be of this class, you will be able to
access the stack methods by way of the names supplied in the abstract interface.
This access by abstract methods means that you will not have to write
different chunks of code to implement the three commands for each kind of
structure: rather, you will need only write a single implementation of each
command, for the general case, and then invoke the method for different
specific structures as needed. Judicious use of typing and type-casting
will be necessary to make this all work. For an example of the interaction
between interface, implementation class and "glue code", see the DumbStruc
and
Your project will be assessed on the basis of both a "live" demonstration
and a hard copy description and print-out of the project code.
The printed version
should specify both members of your group and should specifically mention any free
late days used, remaining problems or bugs, special enhancements, etc. In addition
to "raw code", you should include a brief introduction describing anything that is
special in your approach to the problem (bugs, enhancements, etc., should also be
mentioned here).
Your grade will be determined in part by the correctness of your code, but also
by virtue of the techniques you use to implement it. In particular, you
should try to avoid revising any of Weiss' code, and you should avoid repetition
of code for different structures (i.e., you should use one general implementation
for each command, as described above). If you have trouble constructing the
classes and interfaces so that this is possible, see me for help.
I will be available in lab on Monday mornings from 10:00 - 11:30 for demonstrations.
You may also demonstrate at other times (Thursday morning office hours will likely
be popular), including by appointment, but you must demonstrate your project and hand
in your hard copy by the due date unless you receive a specific provision otherwise
(see also the information about free late days on the syllabus).
C 3 P
which creates a priority queue with reference number 3.
Welcome to Store-o-Rama, your storage structure service center.
Enter commands one per line, and input values where indicated:
> C 2 S
[stack in slot 2 created]
> C 4 Q
[queue in slot 4 created]
> L 4
[input values, stop with 0:]
10 3 6 7 8 5 2 0
[structure 4 loaded from input]
> T 2 4
[transferred 0 items from 2 to 4]
> T 4 2
[transferred 7 items from 4 to 2]
> D 2
[dumping structure 2 to output ...]
2 5 8 7 6 3 10
> D 2 -- check to make sure 2 is empty
[dumping structure 2 to output ...]
> Q -- OK, time to quit (end-of-line text is ignored)
Thanks for using Store-o-Rama, come again soon!
