Assignment 4 - Java File Submission and Map Implementation

Part A - Linear Probing

Submit your .java files (together in an As4.zip file) via Nexus - Include your name and student number in each file as a comment - Document the PostalCode class for Part B using Javadoc notation - Include comments as needed - Use appropriate exception handling where necessary Part A - Linear Probing Develop a program named HighestWordFrequency that determines the 10 most frequently used words found in PartA.txt . Note that your program must exclude all sentence 1 punctuation characters when parsing. 1. Using the Map and Entry interfaces and AbstractMap class from Lab 7, provide the ProbeHashMap implementation. Use the AbstractHashMap class from your notes/text as a base. - In a PartA_Driver class, use your ProbeHashMap to store each word and its count 2. Create a class named MergeSort that uses the merge-sort algorithm and a non-generic OrderByFrequency comparator to sort items in descending order - Sort your list of word frequencies, and display the top 10 most frequently occurring words Notes: - The ProbeHashMap implementation will be part of Lab 7 as well - To remove sentence punctuation, use: - the useDelimiter() method of Scanner e.g. f.useDelimiter("[^a-zA-Z']+"); - or replaceAll() method of String e.g. word = word.replaceAll("[^a-zA-Z']+", ""); - You will have to convert the Iterable to an array (iterate through and add each element) - Prior to our Sorting lecture, you can temporarily sort using Arrays.sort 1 Rowling, J.K. Harry Potter & the Sorcerer's Stone . Scholastic, 1998 PART B - Separate Chaining Create a version of the ChainHashMap that uses a linked list for each bucket. 1. Implement the Map interface using the interfaces and abstract classes from Part A. Name your class LinkedChainHashMap. - Use a linked list as the auxiliary data structure that holds entries of colliding keys - You may choose to use either the LinkedPositionalList (Lab 3) or Java’s LinkedList class. - Add a method named getCollisions that returns an integer representing the number of collisions that occurred in your hashmap. 2. Create a class named PostalCode that stores: - Strings for the code (first segment), area, and province - double for latitude and longitude - include a natural ordering alphabetically by code 3. Create a class named QuickSort that uses the quicksort algorithm and a non-generic OrderByLatitude comparator to sort postal codes from west to east. 4. In a driver class called PartB_Driver, create a hash map of Postal Codes. - read in the PartB.txt file - set each line as an instance of PostalCode - create a mapEntry of each order instance, using the code as key and PostalCode instance as value 6. In your output, display - The total number of postal codes - The number of collisions that occured in the hashmap - An option for the user to sort by code or latitude 7. Go back to ProbeHashMap and add a getCollisions() method. Test your driver code with an instance of ProbeHashMap. Sample output: Total: 1649 Number of collisions: 212 Display by code (C) or latitude (L) (any other key to quit) [display or quit accordingly] Notes: - Your table (array) will hold a linked list of map entries e.g. declare private LinkedList<MapEntry<K, V>>[] table; - Use the for-each loop, since elements are internal map entries you can make any updates directly - Declare your hashmap as a LinkedChainHashMap in the driver (i.e. not Map) - Use nextLine() of Scanner and split(",") of String to parse the csv input - The number of collisions should be ~150 to ~300 - Run several times to check. - Marker will be testing all methods, be sure to also test remove() and put() where an entry with k exists - You will have to convert the Iterable to an array (iterate through and add each element) - Prior to our Sorting lecture, you can temporarily sort using Arrays.sort Submit your As4.zip file that includes all assignment files (Map.java, Entry.java, AbstractMap.java, AbstractHashMap.java, ProbeHashMap.java, LinkedChainHashMap.java, PostalCode.java, MergeSort.java, QuickSort.java, OrderByFrequency.java, OrderByLatitude.java, PartA_Driver, PartB_Driver.java - and PositionalList files, if used) via Nexus