CMPSC 132: Programming and Computation II Homework XXXXXXXXXXpoints) Due date: November 19, 2021, 11:59 PM Goal: In Modules 5 and 6 video-lectures, we discussed the linked list and hash table data...

Keep in Same format as the Starter code (NO Plagiarism and Comment)


CMPSC 132: Programming and Computation II Homework 5 (100 points) Due date: November 19, 2021, 11:59 PM Goal: In Modules 5 and 6 video-lectures, we discussed the linked list and hash table data structure. This homework assignment will combine both concepts to create a (heavily) modified Cache class. General instructions: • The work in this assignment must be your own original work and be completed alone. • The instructor and course assistants are available on Teams and with office hours to answer any questions you may have. You may also share testing code on Teams. • A doctest is provided to ensure basic functionality and may not be representative of the full range of test cases we will be checking. Further testing is your responsibility. • Debugging code is also your responsibility. • You may submit more than once before the deadline; only the latest submission will be graded. • Remove all testing code, code that produces syntax errors and any input() calls before you submit your file Assignment-specific instructions: • Download the starter code file from Canvas. Do not change the function names or given starter code in your script. • Each class has different requirements, read them carefully and ask questions if you need clarification. No credit is given for code that does not follow directions. • This assignment includes multiple methods interacting with each other over the course of execution. You will need to use the tools described in module 2 for debugging. • Value-returning methods must return the output, not print it. Code will not receive credit if you use print to display the output • Do not change the string formats given or use the output of __str__/__repr__ in any of the operations you were asked to complete. • The doctest contains in several lines. This line does not need to show up in your code, it simply represents the use of \n in the legible representations of the objects. In your output. it should show just a blank line • Execute the entire doctest only when ready to test out all your code. For debugging, it is best to perform each call in the Python shell. • If you are unable to complete a method, use the pass statement to avoid syntax errors Submission format: • Submit your code in a file named HW5.py to Gradescope before the due date. Section 1: What is a Cache? What are we making? A computer cache is a part of your computer that holds data. It can be accessed very quickly but cannot hold as much information as your main memory. Most caches on a computer are split into different levels. Your computer will typically look for data starting at the top level (L1) and work its way down the different levels. The most frequently used information is kept in L1 cache because it’s the fastest and the first level it will check. The implementation of the cache for this project will be very simplified and would ignore some of the features of a cache you might find online – so make sure to read this assignment document carefully. In our implementation, we will have three different levels of cache (L1, L2, L3). The overall cache structure will be implemented as a hash table using separate chaining for collision resolution, with each individual level implemented as a linked list. Content is put into different levels based on one of the content’s attributes. Visualization of the Cache, CacheLists, and ContentItems: Cache Hash Table 0 1 2 Level L1 Level L2 Level L3 CacheList CacheList CacheList Section 2: The ContentItem and Node classes The ContentItem class holds a piece of content and is described below. All methods have been implemented for you except __hash__. Do not modify the given code. Attributes Type Name Description int cid Stores the content id. int size Stores the size of the content as a nonnegative integer. str header Information stored by the ContentItem (used for hash function later) str content Information stored by the ContentItem Special methods Type Name Description None __init__(self, cid, size, header, content) Creates a ContentItem from parameters int __hash__(self) Returns the hash value for this ContentItem str __str__(self), __repr__(self) String representation of this object bool __eq__(self, other) Checks for equality with another object __hash__(self) (5 pts) Returns the hash value for this ContentItem (used by the Cache class). For this assignment, let the hash value be equal to the sum of every ASCII value in the header, modulo 3. This is the special method for the built-in method hash(object). Hint: the ord(c) method could be helpful here. Output int An integer between 0 and 2 (inclusive), based on the hash function described above The Node class has been implemented for you and is described below. Do not modify the given code. Attributes Type Name Description ContentItem value Stores the value of this Node (always a ContentItem in this case) Node next Points to the next Node in the linked list (defaults to None) Special methods Type Name Description None __init__(self, content) Creates a new Node that holds the given ContentItem str __str__(self), __repr__(self) String representation of this object https://docs.python.org/3/library/functions.html#ord Section 3: The CacheList class The CacheList class describes a single cache level in our hierarchy, implemented as a singly linked list with a reference to the head node. Items are moved to the head every time they are added or used, creating an order in the list from most recently used to least recently used. Attributes Type Name Description Node head Points to the first node in the linked list (defaults to None) int maxSize Maximum size that the CacheList can store int remainingSpace Remaining size that the CacheList can store int numItems The number of items currently in the CacheList Methods Type Name Description str put(self, content, evictionPolicy) Adds Nodes at the beginning of the list str update(self, cid, content) Updates the content in the list None mruEvict(self), lruEvict(self) Removes the first/last item of the list str clear(self) Removes all items from the list Special methods Type Name Description None __init__(self, size) Creates a new CacheList with a given maximum size str __str__(self), __repr__(self) String representation of this object int __len__(self) The number of items in the CacheList bool __contains__(self, cid) Determines if a content with cid is in the list put(self, content, evictionPolicy) (15 pts) 5 pts for addition at the beginning of the list, 10 pts for complete functionality from the HashTable class Adds nodes at the beginning of the list and evicts items as necessary to free up space. If the content is larger than the maximum size, do not evict anything. Otherwise, if there is currently not enough space for the content, evict items according to the eviction policy. If the content id exists in the list prior the insertion, new content is not added into the list, but the existing content is moved to the beginning of the list. Input ContentItem content The content item to add to the list str evictionPolicy The desired eviction policy (either ‘lru’ or ‘mru’) Output str ‘INSERTED: contentItem’ if insertion was successful str ‘Insertion not allowed’ if content size > maximum size str ‘Content {id} already in cache, insertion not allowed’ if id is already present in the list __contains__(self, cid) (15 pts) Finds a ContentItem from the list by id, moving the ContentItem to the front of the list if found. This is the special method for the in operator to allow the syntax cid in object. Input int cid The id to search for in the CacheList Output bool True if the matching ContentItem is in the list, False otherwise update(self, cid, content) (10 pts) Updates a ContentItem with a given id in the list. If a match is found, it is moved to the beginning of the list and the old ContentItem is entirely replaced with the new ContentItem. You cannot assume the size of the new content will be the same as the content in the list, thus, you must check that there is enough remaingSpace to perform the update. The update is not completed if the change results on exceeding the maxSize of the list, but the match is moved at the beginning