# implement the hash-table using Linear Probing # you may add further functions if required class HashTable: # return the hash value for 'v' # See page #121 of Open Data Structure book # for implementation of a hash function # OR see https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html def __hashed(self, k): pass # returns value for the key 'k' # returns none if it doesn't exist # should run in O(1) def Get(self, k): pass # store value 'v' for the key 'k' # if 'k' already in the table then overwrite # returns: old value of 'k' # should run in O(1) def Put(self, k, v): pass # remove 'k' from the table if exists # returns: current value for the key 'k' # should run in O(1) def Remove(self, k): pass # returns all keys as a list def Keys(self): pass # returns all values as a list def Values(self): pass # returns a list containing key value pairs as # tuples i.e. [(k,v)] def Entries(self): pass # returns the number of elements def Size(self): pass # returns True if the table is empty # otherwise returns false def IsEmpty(self): pass # resize the array when the array def ReSize(self): pass # A wrapper for HashTable class to implement # logic for frequency # you may add further functions if required class FrequencyTable: # constructor def __init__(self): self.hashtable = HashTable() # add e in the table and set counter to 1 # if already exists then add the counter # returns the value of counter after adding # should run in O(1) def Add(self, e): pass # if the counter of e is greater # then 1 then reduce by 1 # otherwise remove the element # returns the current value of counter # should run in O(1) def Remove(self, e): pass # returns the total number of elements/locations def Count(self): pass # returns a list of tuples where first value # shows the element and second value shows frequency # [(1,2),(3,4)] shows two elements 1 and 3 with # frequency 2 and 4, respectivelly def Frequency(self): pass # Driving code to load data from files and process # ******************************************** # YOU ARE NOT REQUIRED TO CHANGE THIS CLASS ** # ******************************************** class FrequencyUtility: # constructor def __init__(self, entrancefile, exitfile): self.entrance = entrancefile self.exit = exitfile # table to store data self.freqTable = FrequencyTable() # process the data and returns freuence table def Process(self): self.__ProcessEntrance() self.__ProcessExit() return self.freqTable.Frequency() # private method to process enterance data def __ProcessEntrance(self): f = open(self.entrance, "r") allLines = f.read().split(' ') f.close() for aLine in allLines: if len(aLine)>0: self.freqTable.Add(int(aLine)) # private method to process exit data def __ProcessExit(self): f = open(self.exit, "r") allLines = f.read().split(' ') f.close() for aLine in allLines: if len(aLine)>0: self.freqTable.Remove(int(aLine)) def Test(): d = FrequencyUtility("entrance.txt","exit.txt") print(d.Process())

Frequencies and Hash-Table

We are processing for a logistic company handling a huge number of parcels every day. The handling a huge number of deliveries required a planning as well. The company has divided the city into different block of locations such as Gulshan Block 4 is considered one location - each location is identified by a number.

At the end of each day, we have to find the number of parcels remaining for each location and a file is maintained for the entrance and exist locations. This information is critical to strategically plan the next day. Whenever a new parcel passes through entrance, its location ID is stored in a file and a similar file is also maintained at the exit location for any parcel going outside the warehouse. Presently, it is taking too much time therefore it is decided to automate this process by writing a small utility.

We are provided two text files in which each line contains a number representing the Location ID for the parcel. As discussed above, the entrance file contains the Location IDs for parcels received whereas the exit file contains the Location IDs for parcel going for delivery. Our goal is to generate the list of Location IDs with remaining number of parcels.

Implementation

HashTable:

You have to implement the Hash-Table with linear probing. This file will store each location as a key and its frequency as value. The signature and details of required functions are given in the provided code template. You may add other functions if required.

FrequencyTable:

This call is a kind of wrapper for the HashTable class in order to implement the logic of frequency. The signature and details of required functions are given in the provided code template. You may add other functions if required.

FrequencyUtility:

This class is responsible to read the data from the file and store in to FrequencyTable in order to generate frequency for each location.

Code: See the provided code template

CS221: Data Structures and Algorithms Example: Consider the following files:	Fall 2020	Usman Institute of Technology
For entrance: 121345 675839 563719 982756 12364 14653 12364 121345 121345 563719	For exit: 982756 12364 14653 12364 121345

The testing code must print the following output (order can vary):

[(121345,2), (675839,1), (563719,2)]

python data structures