| Lab | Assigned | Design Due (Mondays 2 PM) |
Lab Due (Fridays 2 PM) |
|||
|---|---|---|---|---|---|---|
| 2 | Apr | 5 | Apr | 9 | Apr | |
The design will be discussed Monday in class. In Lab, your graded design will be returned. No other handouts or code will be issued. So, think carefully about your design!
Zip includes:
Remember to type the following lines at the top of any files that use the terminal or canvas classes.
import cs101.terminal.*; import cs101.canvas.*;
You should think of a "mapping" ADT as a relation between a domain and a range. For example, a telephone directory is a mapping from names to telephone numbers. The domain is all possible names, and the range is all possible phone numbers. Each entry in the mapping is a pair of elements, one from the domain and one from the range. Usually, the domain and range are different, but that is not a requirement.
In this lab, your mapping will be from item names (represented as String objects) to Objects (which can represent any reference type).
Implementation note:
To compare String values, you will need to use the provided
compareTo method of the String class.
The compareTo method takes as its parameter another String,
and returns an integer whose value is:
WARNING: Do not use the == operator to compare String values.
When == is used on objects, it evaluates to true if both
sides of the comparison refer to the same exact memory location (i.e.,
it's the exact same object). Therefore, even if two String objects
contain the same text, the == test for equality on the
two objects would return false because they are not
the same object.
Mapping.java
and study the provided
code in that file. Notice that the file contains an abstract
class that declares the methods that a Mapping should provide.
Because it is abstract, the Mapping class cannot
be instantiated.
Startup.java and look at the
test procedure. Notice that the parameter to this procedure has type
Mapping. This means that this procedure accepts a parameter
of type Mapping or any of its subclasses.
In this program, three
different types of objects will be created and passed to the test procedure.
All
three are instantiations of different classes, but each extends (directly or
indirectly)
the Mapping interface. Therefore, Java's support for
abstract classes provides
the power to define the interface of an ADT and write programs in
terms of that interface. Then, you can implement the ADT in different
ways and use them in the program, provided that you conform to the
defined superclass's definition.
Mapping.java,
paying attention to the documentation for each method.
StringObjPair
that can store a pair, consisting of
a String (the domain) and an Object (the range).
You may choose to pattern this class after the
DomainRange
class (which contains
Domain and
Range)
in the notes. Or you might think about extending these classes to
obtain StringObjPair.
UnorderedMapping.
You will have to create a new file and add it to your project.
Your implementation will probably
be similar to the Relation
class seen in lecture.
For your internal representation, use an unordered list of StringObjPairs.
For the unordered list,
you may choose to subclass the
List.java class seen in lecture.
In the file Startup.java, create an instance of an UnorderedMapping,
and pass it to the test procedure. Verify that the output is correct.
Notice that the test procedure just knows it's getting a Mapping.
It doesn't care whether it's an UnorderedMapping, or any other kind of
Mapping, so long as the class extends the Mapping class.
OrderedMapping.java.
One of your representation invariants should be that the list is kept in
sorted order, according to the values of the String in each pair.
Make use of this invariant
to improve the efficiency of the map and
lookup methods.
In the file Startup.java, create an instance of an OrderedMapping,
and pass it to the test procedure. Again, notice that the test
procedure only cares that the object's type implements the mapping
interface. Verify that the output is correct.
Look at the printed values of the mapping to be sure that your list
is being kept in sorted order.
ArrayMapping.java.
For your internal representation, create an array of references to
StringObjPair objects.
Create the array to allow enough space for 100 pairs.
One of your representation invariants should be that the array is kept in
sorted order according to the values of the String in each pair.
By maintaining this invariant, you can use binary search on the array
as discussed in class to improve the efficiency of the
lookup method.
Note that when you insert an item that belongs somewhere in the middle
of the array, you'll have to bump all the items after it down by one to
make room for it in the array.
In the file Startup.java, create an instance of an ArrayMapping,
and pass it to the test procedure. Again, notice that the test
procedure only cares that the object's type implements the mapping
interface. Verify that the output is correct.
Look at the printed values of the mapping to be sure that your array
is being kept in sorted order.
Mapping,
UnorderedMapping,
OrderedMapping,
and
ArrayMapping.
You may find it helpful to review the class notes on
Set,
ListBasedSet, and extensions of ListBasedSet.
Explain why you subclass where you do. State which methods are inherited without change and which are redefined in the subclasses.
Think about a representation-specific locate method. For
example, the list-based mappings might use locate to return
the list element that contains a desired StringObject pair.
The array-based mapping might require a different locate, because
the internal representation is different.
Strive to make lookup as general as possible (i.e., as high up
in the hierarchy asyou can), possibly by making it use a subclass's
locate method.
StringObjPair and give
the API for that class.
Implementation the class TreeMapping as a concrete
extension of Mapping.
For your internal representation, use a binary search tree
of StringObjParis.
Additionally,
each node in the tree will have a (possibly null) left subtree and
a (possibly null) right subtree.
Your implementation should satisfy the representation invariant that
all strings in the left subtree of a given node have values that are
less than the string in the node itself.
Make use of this invariant
to improve the efficiency of the map and
lookup method.
The toString method is tricky. Create a string
that is a readable representation of the tree.
Display the tree sideways, with the root of
the tree at the left edge of the page.
Your return String should have one node
per line, something like this:
(quack,4)
(oink,5)
(moo,7)
(meow,2)
()
(bow wow,8)
(baa,5)
This is called an in-order traversal of the tree, since
one subtree is traversed first, then the node itself, and then
the other subtree.
You can use the special
character '\n' in a String to cause the terminal to advance
to a new line as it prints the string.
Hint:
The depth of the node in the tree determines how much to indent.
So, use a helper procedure with a String parameter
that keeps track of the leading spaces
for each line of output. Start it out with the value ""
and then concatenate a String of spaces to create
the indentation String parameter for the recursive calls on both subtrees.
In the file Startup.java, create an instance of a TreeMapping,
and pass it to the test procedure. Verify that the output is correct.
Look at the printed values of the mapping to be sure that the
representation invariant is being preserved by your implementation.