Labs 13-14
Data Structures – Maps and Sets
A map is like a function, unique first value (key) associated with second
value that can belong to several pairs. Map is an interface
A set is an unordered collection of unique objects, with no duplicate entries.
Set is an interface.
A tree has nodes that hold information and references to other nodes.
In a binary tree, each node has at least two references or links.
A binary search tree has the property that each node has no more than
two children, the left child is smaller and the right child is larger. BST’s can be searched in O(log
n), if the tree is balanced.
A hash table holds objects in an array like structure, but the index is calculated
by a formula for fast access. Some indices have no object. Searching/retrieval is done in O(1), adding is O(1) unless there are collisions.
Java has two classes that implement the Set interface, TreeSet and HashSet.
You choose a Set when it is important to have unique elements.
Use TreeSet when it is important that the iterator returns elements
in ascending order. The objects stored
in a TreeSet must implement the Comparable interface. Use HashSet when addition and removal are the
common operations. The objects stored
in a HashSet must override the hashCode() method
from Object.
Maps are similar to Sets, but have keys and values, rather than single elements.
TreeMap and HashMap are chosen in the same way and have the same restrictions
with respect to compareTo and hashCode(). You can call the keySet()
method to have a Set returned of all the key objects in order to iterate over
the map.
Lab 13 -- Maps
COPY and rename your Lab 10-12
folder to Lab 13.
In planning programs or locating requests, a common operation necessary is
to find the CD that holds a given song. A possible design for retrieval of CD that contains
a given song would be as follows:
Create a Map with the keys being the song title (String) and the associated
values being the CD that holds that song. To keep it simple we will ignore the possibility
for now that the same song could be on different CD’s or recorded by different
artists.
Write a class, RadioStationInventory, that has a HashMap and a CDReader as
private instance variables. The CDReader
should store all the CD’s in an additional instance variable, allCDs.
The class should also have a method, buildMap()
that iterates through allCDs, creating the HashMap.
Finally, write a method, findSong(String songTitle),
that returns the first CD that contains that song or null if the station does
not own a CD containing that song.
Write an application program, Lab 13 that creates a RadioStationInventory
object and calls its findSong method to find three songs that exist on different
CD’s and one that is not in the inventory.
Note: Since the String class already
has compareTo() and hashCode() methods, no overriding
is necessary.
Lab 14 -- Sets
Copy the folder for Lab 13 and rename it Lab 14. You will be adding to the RadioStationInventory
class and revising the CDReader and CD classes.
Consider the following related problems: In putting together a radio program, one may
wish to find all the recordings by a particular artist or all the recordings
of a particular song by different artists.
An efficient way to solve this problem is to use a set. Since a set holds only unique objects, if a
CD had several songs by the same artist, a set of all artists for that CD
could be quickly checked using the contains(Object o) method.
Revise the CDReader to require each song be followed by the artist when read
in from the file. The format of the
file is
CD title
number of tracks
song1
artist
song2
artist
...
Revise the CD class to have another private instance variable, TreeSet itsArtists and a method buildArtistSet(). buildArtistSet() should iterate through the contents and add the artist of each song to the set. It should be called in the CD’s constructor. If the artist is already in the set, nothing will happen. If the CD has only one artist, the set will have only one element. If the CD has several artists, each name will appear only once in the set. Write the trivial boolean method, containsArtist(String artist) for the CD class and a songsBy(String artist) that returns an ArrayList of the songs on that CD by the artist. If an artist is in the itsArtists list, then the songs list will be searched for those by that artist.
Finally, write the method, allSongsBy(String artist),
for the RadioStationInventroy class, that returns an TreeSet of song titles.
Do this by iterating through the list of CD’s
(allCDs) and if a CD contains an artist, call its songsBy method. Add all
the arrayLists to the TreeSet to be returned.
In the application program, Lab 14, use the revised CDReader to read the data,
ChristmasSongs.txt, and create the CDs. Search for all the songs by Garth Brooks and
print them out. The TreeSet maintains
the strings in alphabetical order.
Extra Credit
Write a method for RadioStationInventory class that will return a list of all CD’s that contain a given song. Use the ChristmasSongs list and print out all the CD’s that have Winter Wonderland and Silent Night.