LD12: ArrayDictionary due Wed 10 Apr 10:00

Preparation for Lab Day

1. Make sure you have the most recent repository files and do your work in the provided hw12 directory.
2. Copy these files from hw11 to hw12: Word.java, LinkedDictionary.java, Driver.java.
3. Rename LinkedDictionary.java to ArrayDictionary.java. On lab day we'll make major modifications to this file. For now just do this:
   1. rename the class and constructor to match the new name of your file
   2. remove the head attribute
   3. comment out all the methods (including the constructor)
   4. the code should compile, but that's about it
4. In a previous homework assignment we explored the concept of Java's use of .compareTo() to define ordering relationships between two objects of the same type. Add a .compareTo() method to the the Word class that will be used to compare two Word objects. The method should return a negative value if “this” object's sorted string is less than the passed parameter's sorted string. Have it return a positive value if “this” object's sorted string is greater than the passed parameter's sorted string. And, of course, it should return 0 if they are deemed to be equal.
5. In your driver write code to demonstrate that the .compareTo() method is working properly.
6. When it works commit and push.

Lab Day

• We will use an array to hold the Word objects rather than a linked list.
• We will use quicksort to sort the array elements by the “anagram” word (sorted word) rather than the actual word.
• We will search for matching anagrams using a binary search.
• The functionality just described will be implemented by replacing the LinkedDictionary class with a similar ArrayDictionary class that will have this design:

  ArrayDictionary
  - Word[] data	array of Word objects
  - int n	number of elements in the array
  + ArrayDictionary(String f)	read words from file and insert into array
  + int countAnagrams(Word w)	look through array and return count of w's anagrams
  + void displayBigAnagramFamilies()	display each word with 6+ anagrams
  - void sort()	quicksort
  - int binSearch(Word w)	binary search to return position where w is found; -1 if not found

NOTE: The sort() and binSearch() methods are private because they will be used internally.

Keeping in mind the final destination, embark on these steps:

1. Show your pre-lab work to the instructor.

2. Begin by working on the ArrayDictionary constructor. Uncomment it and modify it to do the following:
   1. Reserve 500,000 slots in the data array.
   2. Use BufferedReader to read the provided input file into the data array. Close the file when done.
   3. By the end of the method the attribute n should reflect the number of values read from the file.

3. Once you are comfortable with the behavior of the constructor: document and commit.

4. Add a display method that will display the first 20 elements of the array.

5. Now begin working on the sort() method. The recursive quicksort we discussed in class needs to pass the index of the beginning and and of the current partition as parameters. When we are implementing a sort in a container such as this it is customary to provide a method that takes no parameters. To handle this we use a “helper” method (no parameters) whose only job is to call the recursive method with its initial values. So, add this method:

   public void sort() {
      qSort(0,n-1);
   }
   

6. Place a call to this method at the bottom of the constructor (after file has been read and n has been set).

7. Now all the remains is to create the referenced, recursive qSort() method. Use you notes to construct this method along with the accompanying parition() method.

8. Once quicksort is working document each method and commit/push your work.