Create a version of the ChainHashMap that uses a linked positional list for each bucket.

Note that the ChainHashMap implementation in Lab $8$ used an UnsortedTableMap as a bucket, so the

implementation here would be different.

$1.$ Implement the LinkedPositionalList class based on the class notes. The Iterable

PositionalList interface is provided.

$2.$ Implement the Map interface using the interfaces and abstract classes from Part A$.$ Name your class

LinkedPositionalChainHashMap.

$-$ Use a linked positional list as the auxiliary data structure that holds entries of colliding keys.

You must use your own implementation of the LinkedPositionalList based on the

class notes.

$-$ Add a method named getCollisions that returns an integer representing the number

of collisions that occurred in your hashmap. Think of an efficient way to do this.

$-$ Modify the AbstractHashMap class so that the resize method uses an instance of your

LinkedPositionalList instead of an ArrayList. There should be no import of

ArrayList in any of your classes.

$3.$ Create a class named PostalCode that stores:

$-$ Strings for the code, area, and province

$-$ double for latitude and longitude

$-$ include a natural ordering of postal codes in alphabetical order of the code

$4.$ Create an OrderByLongitude comparator that orders postal codes from west to east. See here

for more information about longitude.

$5.$ Create a class named QuickSort that uses the quicksort algorithm $($from class$)$ and a comparator

to sort elements of a collection $($stored as a queue or an array$).$ Overload your sorting algorithm to

work both with a default comparator and with a specified comparator. Make sure to reuse code.

$6.$ In a PartB$\_$Driver class, create a hash map of Postal Codes.

$-$ read in the PartB.txt file

$-$ set each line as an instance of PostalCode

$-$ store each instance in your map, using the code $($stored in the first column of the given data$)$

as the key and PostalCode instance as the value

$7.$ In your output, display

$-$ The total number of postal codes

$-$ The number of collisions that occurred in the hashmap

$-$ An option for the user to sort by code or longitude

$4$

$8.$ After displaying the output, include $2$ lines of code to do the following. You may use any of the postal

codes in the sample data for this.

$-$ Show the output of inserting an entry where the same key previously exists in the map.

$-$ Show the output of removing an entry where the key exists in the map.

Sample Output

Total Number of entries: $1649$

Number of collisions: $218$

Display by code $($C$)$ or Longitude $($L$)($any other key to quit$)$

$...$

$[$display the value associated with each postal code or quit accordingly$]$

Notes:

$-$ Your table $($array$)$ will hold a linked list of map entries e$.$g$.,$ declare

private LinkedPositionalList$>[]$ table;

$-$ Use the for$-$each loop, since elements are internal map entries you can make any updates

directly

$-$ Declare your hashmap as a LinkedPositionalChainHashMap in the driver $($i$.$e$.$ not Map$)$

and understand why this is necessary

$-$ Use the nextLine$()$ method of Scanner and split$(",")$ of String to parse the input data

$-$ The number of collisions should be ~$150$ to ~$450$ but may vary. Run several times to check. Think

about why the number of collisions may differ at each run.

$-$ The marker will be testing all methods, be sure to also test remove$()$ and put$()$ where an entry

with key k exists

$-$ You may choose to use either quickSort or quickSortInPlace

$-$ You will have to convert the Iterable of all values to a queue or an array $($iterate through and add

each element$).$ If you are using a queue, you must use the LinkedQueue implementation based

on the lecture notes. The Queue interface is provided.

$-$ Before our lecture on Sorting is comp, you can temporarily sort using Arrays.sort

$-$ Overload your sorting algorithm to work both with a default comparator and with a specified

comparator. Make sure to reuse code as necessary.