Data Structures and Algorithms Project

Data Structure and Algorithm Design

CSCI 3000

Name: Date:

Programming Final Credit – HashMap (Lyric Analyzer)

Since the lyrics of most pop music contains words that repeat a number of times, a simple way to compress

a lyric file is to create a map that stores each word once along with the positions of each word in the file.

For example, suppose the lyric consists of the lines:

What have I

1 2 3 <-- word position in lyrics

What have I

4 5 6 <-- word position in lyrics

What have I done to deserve this

7 8 9 10 11 12 13 <-- word position in lyrics

We would form a map that maps each unique word to a list of word positions in the lyric. NOTE: The

word position for a word at the end of a line is stored as a negative integer rather than a positive integer so

you can recreate the lyrics later when you iterate through the words in the map.

Sample map for the lyric above (order of words may vary):

Word Word Position(s)

===========================

WHAT 1, 4, 7

HAVE 2, 5, 8

I -3, -6, 9

DONE 10

TO 11

DESERVE 12

THIS -13

This project currently contains only one class that models the analyzer using a HashMap that maps a lyric

word to a list of integers representing the locations of the word in the lyrics.

1. Complete the class for the lyric analyzer by adding the following methods listed below. a. Write an add method with the following signature:

public void add(HashMap<String,ArrayList<Integer>> map)

This method will determine if the given lyric word is in the map. If the word is not in the map, then a mapping is added that maps that word to a list containing the position of the word in the lyric. If the word is already in the map, then its word position is added to the list of word positions for this word. Do not create a new mapping if the lyric word is already in the map. Use the one that is already there and just update its list. Remember to negate the word position if the word is at the end of a line in the lyrics.

b. Write a displayWords method with the following signature:

public void displayWords(HashMap<String,ArrayList<Integer>> map)

This method should display the words of the song along with the word positions of the

word, one word per line, in alphabetical order. You should do this without creating

another map. Instead, get a set of all the words stored in the map. Sort this set using one of

the sort methods from the Java API. Then iterate over this sorted set and print out each

word along with the word positions associated with each word. You may leave the negative

integers in the word position list. (see sample output below) Iterate through the array of

words using the enhanced for loop.

c. Write a displayLyrics method with the following signature:

public void displayLyrics(HashMap<String,ArrayList<Integer>> map)

This method will display the lyrics for the song (in uppercase) stored in the map. Start with

an empty array of strings whose size is the number of words in the lyric plus 1 (don't use

cell 0). Initialize this array with empty strings (not null). Then, get a set of all of the words

stored in the map. For each word, store the word in the array cells corresponding to its word

position(s). If a word position is negative, add on an extra newline character to the word

when you store the word in the array. Once you finish processing all words that are in the

map, iterate through the array and print out each string, and you should see the lyrics

appear, line by line. Note that if the original lyrics had blank lines, you won't have these in

the reconstructed lyrics. Iterate through the array of words using the enhanced for loop.

d. Write a method with the following signature:

public int count(HashMap<String,ArrayList<Integer>> map)

This method will return the total number of unique words in the lyric by analyzing the map.

e. Write a method with the following signature:

public String mostFrequentWord(HashMap<String,ArrayList<Integer>> map)

This method will return the word that occurs most frequently in the lyric. Do this by getting

a set of all the words in the map and then for each word, find the one that has the largest set

of word positions. Use the enhanced for loop in your solution. Do not create any

additional data structures to solve this problem. If there is a tie for the most frequent word,

print out the most frequent word that comes first alphabetically.

2. Complete the main method that reads the file Minimal.txt. The text file contains the lyrics for a pop song. You may assume that the files have all punctuation filtered out (except for apostrophes), but

there may be uppercase and lowercase letters mixed together. For example, the string "Don't" is

considered one word. Some lines of the file may also be empty. If the file is not found, exit the

program with a warning message.

Once you open the text file, read each word from the file one at a time, convert the word to

uppercase, and insert the word into the map along with its word position using your add method.

After you add all words to the map, display the word/position list using your displayWords

method.

Next, reconstruct and display the lyrics using your displayLyrics method.

Then, display the total number of unique words in the lyrics by using your count method.

Finally, output the word that occurs most frequently using your mostFrequentWord method.