CS310 Data Structures Programming Assignment 5: Hashing with Sets and Maps Solved

40.00 $

Category:

Description

Problem Scenario

The brokerage office was very impressed with your work from Assn 3. Nevertheless, the IT director at the office just received the latest “Java Geek Weekly”, and read all about hashing. Now, the IT director wants to replace the linked lists in your project with hash sets and maps.

In addition, the brokerage office would like help their FundManagers identify specific stocks as either taxable or not taxable. Therefore, they would like to replace your prior reports with a report on this.

Program Requirements

You will replace your FundManagerImpl and StockTradeLogImpl classes from Assn 3 to work with hash tables, instead of linked lists.

The FundManagerImpl will use a Hash Set to store FundManager objects. The hash table will be implemented as an array of FundManager objects (initialized to null when the table is created). The hash table will use the open addressing method via linear probing to resolve collisions. The array size for this implementation will be 19 (a prime number).

The StockTradeLogImpl will use a hashmap to store StockTrade objects. You will need to create a MapEntry class to implement the hashmap. Each MapEntry will be comprised of a key and a StockTrade node. The hashmap will be an array of MapEntry objects (initialized to null when the table is created).

Since the MapEntry value is a StockTradeNode, it can be used as a reference to a linked list. So, if there are multiple entries that map to the same index, the collisions will be resolved by using the chaining method, adding each entry to the top of the linked list at that index. This means that each StockTrade object that maps to the same index (via the hashcode) will be stored in a linked list at that index. The array size for this implementation will be 17 (another prime number).

See the last page of this requirements document for diagrams of the hash tables.

You will create your own hashing algorithms for this assignment. Remember the hashcode method that was generated for you in week 1? Modify this method for each of your domain classes.

Create a hashcode for a FundManager object in the FundManagerImpl hash table by extracting the last 5 digit characters from the FundManager license number, converting them to an integer, and then using the modulus operator, so that the value will map correctly to array indexes. For example, the license number of CCC12233, will hash to:

12233 mod 19 = 16 (maps to index 16)

Create a hashcode for a StockTrade object in the StockTradeLogImpl hash table by adding the ASCII/Unicode values of each character in the stockSymbol. After adding them, use the modulus operator, so that the value will map correctly to an array index. For example, the StockSymbol of CCDD will hash to:

67 + 67 + 68 + 68 = 270 mod 17 = 15 (maps to index 15)

The input file of FundManagers and StockTrade listings will remain the same as used in the previous assignments, except that you can now assume all data will be valid. So there will no longer be any need to validate and remove incorrect data.

You also will not need to worry about removing StockTrades or FundManagers. Concentrate on adding the objects to the respective HashSet/HashMap. You will need to remove the code in your main that removes the objects.

Read the input file and use the correct hashCode to place each FundManager/StockTrade object into the correct location in one of the hash tables. Then display the contents of each hash table as follows:

Add a displayHash() method to both FundManagerImpl and StockTradeLogImpl.

These methods will first display a header:

FundManager Hash Table: OR StockTrade Hash Table:

and will then display where each FundManager/StockTrade object is stored in the hash table. An example is shown at the end of the assignment

NOTE: The input in the example will provide collisions on both the FundManager and StockTrades HashSet/HashMap. You may use it to test your code. However, you are expected to provide your own data input files with a minimum of five FundManagers, each with at least two StockTrades. Your data needs to be as such to cause some collisions.

Note that your FundManagerImpl and StockTradeLogImpl will no longer use remove methods (because no data will be removed from the hash tables). Instead, they will use addand find methods.

The add methods will be used to place the FundManager and StockTrade objects into their hash tables.

The find method in the FundManagerImpl class will search for a FundManager based on the FundManager license number. It will return a reference to the found FundManager object, or will return null if the FundManager is not in the hash table.

The find method in the StockTradeLogImpl class will search for a StockTrade based on the stockSymbol. It will return a reference to the found StockTrade object, or will return nullif the StockTrade is not in the hash table.

You will not need to create any of the reports that you created in the past assignments. So you can remove the calls that created those reports from your main method.

Instead, the brokerage office wants you use the hash tables to create a new report of taxable/not taxable stocks by FundManager for them. The office will provide a simple flat file of FundManager license numbers and StockTrade stockSymbols, for all of the FundManagers in the office who requested a report on their taxable/not taxable stocks.

Each line of the file will contain a FundManager license number and a list of one or more StockTrade stockSymbols that the FundManager would like to check taxable/not taxable status on.

For example (this is using the sample data at the end of the assignment):

LMN11111 LMN XXXX

MMM11111 MMM

ABC11111 ABC

This file, called FundManagerRequests.txt, will be located in the input folder

When reading the data in this file:

Use a hash code to find the FundManager license number in your FundManagerImpl hash table

Use a hash code find each StockTrade stockSymbol your StockTradeLogImpl hash table

and for each, determine if the StockTrade is taxable/not taxable.

Replace the old create report method in PrintImpl with a method that will generate a new report to be written to an output file named assn5salesReport.txt, which will be located in the output folder of the project.

Sample report output:

FundManager LMN11111, George Harrison

StockTrade LMN is NOT TAXABLE

StockTrade XXXX is NOT TAXABLE

FundManager MMM11111, Ringo Starr

StockTrade MMM is TAXABLE

FundManager ABC11111 does not exist

Note that when the FundManager does not exist, you should not search for any of the StockTrade listings on that line.

The program must follow all CS310 Coding Standards from Content section 1.9.

Additional Requirements

 Create Javadoc headers, and generate Javadoc files for each of your new implementation classes and for all new static methods in the main class. You are responsible for completing the comment headers created.

 Your original input data file (containing FundManager and StockTrade data to build the hash tables from) will still be read from the input folder in your project.

Place all test data files that you create to test your program in the input folder of your project, and name them as follows:

assn5input1.txt

assn5input2.txt

(i.e. number each data file after the filename of assn5input.txt)

 Your new input data file will also be read from the input folder in your project.

Place all test data files that you create to test your program in the input folder of your project, and name them as follows:

FundManagerRequests1.txt

FundManagerRequests2.txt

(i.e. number each data file after the filename of FundManagerRequests.txt)

As a group, all of your test data files should demonstrate that you have tested every possible execution path within your code, including erroneous data which causes errors or exceptions.

 Add screen shots of clean compile of your classes to the documentation folder.

WARNING: Submittals without the clean compile screenshots will not be accepted.

(This means that programs that do not compile will not be accepted)

StockTrade

NEXT

KEY

StockTrade

NEXT

Program Submission

Programming assignment is due by midnight of the date listed on Course Assignments by Week page.

 Export your project from NetBeans using the same method as you did for previous assns.

o Name your export file in the following format: CS310<lastname>Assn<x>.zip

For example:

CS310SmithAssn5.zip

 Submit your .zip file to the Prog Assn 5 Submission Folder (located under Assignments tab in online course). Only NetBeans export files will be accepted.

Grading

This program will be graded using the rubric that is linked under the online Student Resources page.

WARNING: Programs submitted more than 5 days past the due date will not be accepted, and will receive a grade of 0.

HashSet Diagram for FundManagers

Each index of the array represents the hashcode.

HashMap Diagrams for StockTrades

StockTradeNode

MapEntry

(the key is used to determine the hashcode,

and the value is a StockTradeNode object)

The hash map is an array of MapEntry objects:

EXAMPLE AUDIT TRAIL

For the following data input:

BROKER,ADD,MMM11111,Ringo,Starr,321-111,0.02

TRADE,BUY,MMM,999.999,99999,MMM11111,Y

BROKER,ADD,LMN11111,George,Harrison,123-222,0.025

TRADE,BUY,LMN,9,1022,LMN11111,N

TRADE,BUY,ABC,555,555,LMN11111,Y

TRADE,BUY,XXXX,100,877,LMN11111,N

and sample request file on page 2, the following audit trail is generated:

Reading data from file input/assn5input.txt

ADDED: FundManager with license MMM11111

ADDED: StockTrade with stock symbol MMM listed by fundManager MMM11111

ADDED: FundManager with license LMN11111

ADDED: StockTrade with stock symbol LMN listed by fundManager LMN11111

ADDED: StockTrade with stock symbol ABC listed by fundManager LMN11111

ADDED: StockTrade with stock symbol XXXX listed by fundManager LMN11111

Done reading file. 6 lines read

FundManager Hash Table:

Index 0 is empty

Index 1 is empty

Index 2 is empty

Index 3 is empty

Index 4 is empty

Index 5 is empty

Index 6 is empty

Index 7 is empty

Index 8 is empty

Index 9 is empty

Index 10 is empty

Index 11 is empty

Index 12 is empty

Index 13 is empty

Index 14 is empty

Index 15 contains FundManager MMM11111, Ringo Starr

Index 16 contains FundManager LMN11111, George Harrison

Index 17 is empty

Index 18 is empty

StockTrade Hash Table:

Index 0 is empty

Index 1 is empty

Index 2 is empty

Index 3 is empty

Index 4 is empty

Index 5 is empty

Index 6 is empty

Index 7 is empty

Index 8 is empty

Index 9 is empty

Index 10 contains StockTrades: LMN MMM

Index 11 contains StockTrades: ABC

Index 12 contains StockTrades: XXXX

Index 13 is empty

Index 14 is empty

Index 15 is empty

Index 16 is empty

Creating initial report…

Creating sales report using requests from file input/FundManagerRequests.txt

Sales report is complete — located in file: output/assn5taxReport.txtort.txt