Project Assignment
Program Description
You will develop a C++ program that reads an input data set consisting of four parts: the first part is a hash table size requested by a user; the second part is a list of cities with its state, population, and geo-location. This part will end with the line "InsertionEnd"; the third part is a number of commands to follow; and the forth part is a list of commands.
1. After reading in a hash table size requested by a user, a hash table of the size (with open addressing, double-hashing) needs to be created. Each slot of your hash table should be a pointer of the class called City which you will be creating to store each city's name, state, population, and its geo-location (do not store double-quotes " used for geo- location), and a number of collisions. Initially each pointer should be NULL.
2. Then by reading each city information line by line, their information needs to be stored in the hash table using a hash function. You will need to design your hash function so that it reduces the number of collisions. You need to specify your hash functions that will be used, i.e., h(k,i), and h_1(k) and h_2(k) using each city name as its key value.
The following shows an example of such data for cities:
AL,Mobile,195111,"(30.67762486480, -88.1184482714)"
AK,Anchorage,291826,"(61.14986873100, -149.111113424)"
AZ,Phoenix,1445632,"(33.57241386950, -112.088995222)"
AZ,Scottsdale,217385,"(33.68724936510, -111.865085877)"
AR,Fayetteville,73580,"(36.07121173120, -94.1659600436)"
AR,Fort Smith,86209,"(35.34916926360, -94.3696317306)"
AR,Jonesboro,67263,"(35.82081215380, -90.6794991686)"
CA,Anaheim,336265,"(33.83890769960, -117.857613481)"
3. After the line "InsertionEnd", your program needs to print out the content of your hash table. Then a user will enter a number of commands.
4. Each command will be "hash_display", "hash_search", or "hash_max_population".
Hash_Display command:
With "hash_display" command, your program needs to display the content of your hash table by listing the content of each index in the following format, by specifying their number of collisions. If a slot if empty, print out "none" for strings and "--" for integers:
|
index
|
state
|
city name
|
collisions
|
population
|
geolocation
|
|
0
|
none
|
none
|
--
|
--
|
none
|
|
1
|
CO
|
Denver
|
0
|
600158
|
(39.76202837430, -104.876365322)
|
|
2
|
DC
|
Washington
|
0
|
601723
|
(38.90992414260, -77.0147205666)
|
|
3
|
none
|
none
|
--
|
--
|
none
|
|
4
|
AK
|
Anchorage
|
0
|
291826
|
(61.14986873100, -149.111113424)
|
|
5
|
none
|
none
|
--
|
--
|
none
|
|
6
|
IN
|
Bloomington
|
1
|
80405
|
(39.16374582210, -86.5257124351)
|
|
7
|
ID
|
Boise City
|
0
|
205671
|
(43.59843438970, -116.230885189)
|
|
8
|
CA
|
Burbank
|
0
|
103340
|
(34.18797996050, -118.323429032)
|
|
9
|
CO
|
Boulder
|
2
|
97385
|
(40.02755104940, -105.251517760)
|
Hash_Search command:
Hash_Search command will have the format of:
hash_search,CT,Hartford
where the word "hash_search" is followed by state and a city name, and they are separated by commas.
After the hash_search command is entered, the program should search for the city and its state that matches those data fields, and if it is found, display their information with their population and geolocation as:
The city Hartford of CT with its population of 124775 and its geolocation of (41.76607064190, -72.6834012389) was found
If not found, display a message using the following format: The city Topeka of KS was not found Hash_Max_Population command:
Hash_Max_Population command will have the format of:
hash_max_population
After the hash_max_population command is entered, the program should search for the city with the maximum population, and if it is found, the program needs to display a message using the following format using their information:
The city Chicago of IL has the highest population of 2695598
If the hash table is empty:
There is no city stored in the hash table
Design Requirements:
You should create a hash table with open addressing using double hashing. You also need to define hash_display, hash_insert, hash_search, and hash_max_population functions for the hash table.
Implementation/Documentation Requirements:
• You need implement this program using C++ and it has to read from the standard input (from a keyboard).
• Your program needs to compile and execute in general.asu.edu.
• You need to create a class or a struct City containing, state, city name, population, geolocation, and collisions.
• You need to define hash_display, hash_insert, hash_search, and hash_max_population functions (name them "hash_display", "hash_insert", "hash_search", "hash_max_population", for your hash table, and a hash function h, h1, and h2.
• Your code should be well documented and commented.
• At the top of your driver file, within a comment, write your hash analysis -- how did you come up with your hash function? Was the number of collisions what you expected? Did your hash function work well? If you had to change your function to reduce the number of collisions, how did you change it?
• You must use the provided data sets.
• Also you are not allowed to use any predefined data structures (such as ones in the library in C++, etc.) except arrays and strings, you need to build your own data structures and operations associated with them (such as insert or search).
• Copying any codes from other people's programs is considered to be cheating and will lead to a report to the Dean and you will be penalized. Also check the rules stated in the syllabus of the course regarding the academic integrity
What to turn in:
submit a zip file containing the following:
1. one or more files of your well documented C++ source code (with a file extension .cpp or .h) implementing the commands required, your hash table.
2. A Makefile that compiles your program to an executable named "cse310project1" on the Linux machine general.asu.edu. Our TA will write a script to compile and run all student submissions on general.asu.edu; therefore executing the make command must produce the executable file "cse310project1" in the same folder as your source code files. After such cse310project1 file is produced, then we should be able to execute your program using the command:
./cse310project1 < sampleinput.txt
where "sampleinput.txt" is a file name, but we should be able to use a file with a different name with a content in the format specified in the project statement.
Your program must read from a keyboard, not a file.
Error Handling
Your program will be tested with other input besides the sample input given, thus is expected to be robust.
Attachment:- Sample-Input-and-Output.rar