GARBAGE COLLECTION

In this assignment, you will simulate the Mark-Sweep garbage collection algorithm. The reference variables and values will be read in from an input file. All variables on the stack will have a string name (ex. vPtr) and the heap blocks will be integers. Operations You must create the following function in the file hw3.py. setMemory Parameters: Name of the input file (string) Returns: A tuple that consists of a dictionary and a list, in that order. Description: Reads and parses the input file. Creates and returns a dictionary and a list. The first line in the file represents the number of heap blocks (n). Each heap block will be numbered between 0 and n-1. Each subsequent line represents a single block on the heap with an integer and all variables that are pointing to that block. All the values are comma separated. Sample input file: 4 3,a,2,b Named variables a and b are pointing to heap block 3 AND Heap block 2 is pointing to heap block 3 Store the named variables in a dictionary where the key is the name of the variable and the value is a heap block its pointing to. You can assume that a named variable points to exactly one heap block. Ex. {'a': 3, 'b': 3} for the graph above Store the heap blocks in a list where the index is the number of the heap block and the value is a list of all the heap blocks its pointing to. The result should be a nested list. The inner lists should be in ascending order. Ex. [[], [], [3], []] for the graph above You may assume that named variables and heap blocks only point to heap blocks.

Main program The program has the following top-level functionality: 1. Get the name of an input file from the command line (using sys.argv). WARNING: Do not prompt the user for a file name. 2. Call setMemory in the input filename and store the result in varDict and heapList. 3. The input file may not exist or may be empty. Create appropriate exception handlers. If an error occurs, print an error message specific to the type of exception and exit the program. 4. Print the varDict. 5. Print the heapList. 6. Perform marking by using DFS (depth first search) traversal from each variable in the varDict. Start from the variable that comes first alphabetically. If a heap block points to multiple heap blocks, a lower numbered heap block has higher priority and gets marked first. 7. Print the marked heap blocks in the order that they are marked. Begin with marked: followed by each number separated with a single space. 8. Print the swept (reclaimed) heap blocks in ascending. Begin with swept: followed by each number separated with a single space. Notes: You may assume the input is valid and properly formatted. A valid variable name consists of letters, digits, and underscores but cannot begin with a digit. (Remember that the program will only be tested with valid variable names.) You may assume the variable names are unique. For non-empty files, you may assume there is at least one heap block the number on the first line will be greater than or equal to one. Your algorithm must run in polynomial time but does not need to optimal. You may NOT import any module or library for this assignment except for the import specified in the instruction. You may create other functions and variables beyond what is listed here.