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), for example hash('hello'). 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	previous	Points to the preceding Node in the linked list (defaults to None)
Node	next	Points to the following 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

Section 3: The CacheList class

The CacheList class describes a single cache level in our hierarchy, implemented as a doubly linked list with references to the first and last node in the list (head and tail). Items are moved to the front every time they are added or used, creating an order in the list from most recently used to least recently used. READ the outline for all the methods in this class first, the put method should be the last one to be implemented in this class since it relies on the correctness of the other methods. A portion of your grade in this class comes from your ability to reuse code by calling other methods.

Attributes

Type	Name	Description
Node	head	Points to the first node in the linked list (defaults to None)
Node	tail	Points to the last 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 and evictions

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 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. If there is currently not enough space for the content, evict items according to the eviction policy.

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 available space 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 of the list.

Input
int	cid	The id to search for in the CacheList
ContentItem	content	The values to update the existing ContentItem with

Output
str	'UPDATED: contentItem' if update was successful
str	'Cache miss!' is returned if no match is found or the update exceeds the maxSize

lruEvict(self) / mruEvict(self) (10 pts each)Removes the last (least recently used) or the first (most recently used) item of the list

Output
None	This function returns nothing.

clear(self) (5 pts)

Removes all items from the list. This method must unlink all nodes from the list

Output
str	'Cleared cache!'

Section 4: The Cache class

The Cache class describes the overall cache, implemented as a hash table. It contains three CacheLists which actually store the ContentItems. Hash values of 0 correspond with the first CacheList (L1), 1 with L2, and 2 with L3.

0	1	2
Level L1	Level L2	Level L3
CacheList(size)	CacheList(size)	CacheList(size)

All methods in the Cache class will call a corresponding method in the CacheList class. For example, the insert method calls the put method from the CacheList class.

Do not change the initialization of the CacheList objects in the starter code. You are not allowed to add any other methods in this class. Your code will not receive credit if you add other methods.

Attributes

Type	Name	Description
list	hierarchy	List with 3 CacheList objects of size (lst_capacity)
int	size	Number of levels in our hierarchy (always set to 3)

Methods

Type	Name	Description
str	insert(self, content, evictionPolicy)	Adds an item into the proper cache list
str	clear(self)	Clears all CacheLists in the hierarchy.

Special methods

Type	Name	Description
None	__init__(self, lst_capacity)	Creates a new Cache with (3) CacheLists of size lst_capacity
str	__str__(self), __repr__(self)	String representation of this object
(various)	__getitem__(self, content)	Gets a Node from the proper cache list
None	__setitem__(self, cid, content)	Updates an item from the proper cache list

30 pts for correct status of the Hash Table after mixed calls do insert, getitem and setitem (no partial credit for this set of points)

insert(self, content, evictionPolicy)

Inserts a ContentItem into the proper CacheList. After using the hash function to determine which CacheList the content should go into, call that CacheList's put method to add the content.

Input
ContentItem	content	The content item to add to the list
str	evictionPolicy	The desired eviction policy (either 'lru' or 'mru')

Output
str	(Return the output from the put method call)

__getitem__(self, content)

Returns a reference to a Node that stores a ContentItem in a CacheList. After using the hash function to determine which CacheList the content should exist in, you may use the CacheList's in operator to find the proper node. This is the special method to support the syntax object[content]

Input
ContentItem	content	The content item to retrieve

Output
Node	Reference to Node object with value that matches the ContentItem (item was found)
str	'Cache miss!' is returned if it's a cache miss (item was not found)

setitem(self, cid, content)

Updates a ContentItem. After using the hash function to determine which CacheList the content would be in, call that CacheList's update method to update the content.

Input
ContentItem	content	The content item to update

clear(self)

Clears all the lists in the hierarchy. This method is already implemented for you.

Output
str	'Cache cleared!'

class Node:

def __init__(self, content):

self.value = content

self.next = None

self.previous = None

def __str__(self):

return ('CONTENT:{} '.format(self.value))

__repr__=__str__

class ContentItem:

'''

>>> content1 = ContentItem(1000, 10, "Content-Type: 0", "0xA")

>>> content2 = ContentItem(1004, 50, "Content-Type: 1", "110010")

>>> content3 = ContentItem(1005, 18, "Content-Type: 2", "

'CMPSC132'

")

>>> content4 = ContentItem(1005, 18, "another header", "111110")

>>> hash(content1)

0

>>> hash(content2)

1

>>> hash(content3)

2

>>> hash(content4)

1

'''

def __init__(self, cid, size, header, content):

self.cid = cid

self.size = size

self.header = header

self.content = content

def __str__(self):

return f'CONTENT ID: {self.cid} SIZE: {self.size} HEADER: {self.header} CONTENT: {self.content}'

__repr__=__str__

def __eq__(self, other):

if isinstance(other, ContentItem):

return self.cid == other.cid and self.size == other.size and self.header == other.header and self.content == other.content

return False

def __hash__(self):

# YOUR CODE STARTS HERE

pass

class CacheList:

'''

>>> content1 = ContentItem(1000, 10, "Content-Type: 0", "0xA")

>>> content2 = ContentItem(1004, 50, "Content-Type: 1", "110010")

>>> content3 = ContentItem(1005, 180, "Content-Type: 2", "

'CMPSC132'

")

>>> content4 = ContentItem(1006, 18, "another header", "111110")

>>> content5 = ContentItem(1008, 2, "items", "11x1110")

>>> lst=CacheList(200)

>>> lst

REMAINING SPACE:200

ITEMS:0

LIST:

>>> lst.put(content1, 'mru')

'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'

>>> lst.put(content2, 'lru')

'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'

>>> lst.put(content4, 'mru')

'INSERTED: CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110'

>>> lst.put(content5, 'mru')

'INSERTED: CONTENT ID: 1008 SIZE: 2 HEADER: items CONTENT: 11x1110'

>>> lst.put(content3, 'lru')

"INSERTED: CONTENT ID: 1005 SIZE: 180 HEADER: Content-Type: 2 CONTENT:

'CMPSC132'

"

>>> lst.put(content1, 'mru')

'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'

>>> 1006 in lst

True

>>> contentExtra = ContentItem(1034, 2, "items", "other content")

>>> lst.update(1008, contentExtra)

'UPDATED: CONTENT ID: 1034 SIZE: 2 HEADER: items CONTENT: other content'

>>> lst

REMAINING SPACE:170

ITEMS:3

LIST:

[CONTENT ID: 1034 SIZE: 2 HEADER: items CONTENT: other content]

[CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110]

[CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]

>>> lst.tail.value

CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA

>>> lst.tail.previous.value

CONTENT ID: 1006 SIZE: 18 HEADER: another header CONTENT: 111110

>>> lst.tail.previous.previous.value

CONTENT ID: 1034 SIZE: 2 HEADER: items CONTENT: other content

>>> lst.tail.previous.previous is lst.head

True

>>> lst.tail.previous.previous.previous is None

True

>>> lst.clear()

'Cleared cache!'

>>> lst

REMAINING SPACE:200

ITEMS:0

LIST:

'''

def __init__(self, size):

self.head = None

self.tail = None

self.maxSize = size

self.remainingSpace = size

self.numItems = 0

def __str__(self):

listString = ""

current = self.head

while current is not None:

listString += "[" + str(current.value) + "] "

current = current.next

return 'REMAINING SPACE:{} ITEMS:{} LIST: {}'.format(self.remainingSpace, self.numItems, listString)

__repr__=__str__

def __len__(self):

return self.numItems

def put(self, content, evictionPolicy):

# YOUR CODE STARTS HERE

if self.numItems == 0:

self.head = self.tail = Node(content)

self.remainingSpace -= content.size

self.numItems += 1

return f'INSERTED: {content}'

if content.cid in self:

return f'CONTENT ID {content.cid} ALREADY EXISTS'

if self.remainingSpace < content.size:

if evictionPolicy == 'mru':

evicted_content = self.mruEvict()

else:

evicted_content = self.lruEvict()

self.remainingSpace += evicted_content.size

new_node = Node(content)

new_node.next = self.head

self.head.previous = new_node

self.head = new_node

self.remainingSpace -= content.size

self.numItems += 1

return f'INSERTED: {content}'

new_node = Node(content)

new_node.next = self.head

self.head.previous = new_node

self.head = new_node

self.remainingSpace -= content.size

self.numItems += 1

return f'INSERTED: {content}'

def __contains__(self, cid):

# YOUR CODE STARTS HERE

current = self.head

while current is not None:

if current.value.cid == cid:

return True

current = current.next

return False

pass

def update(self, cid, content):

# YOUR CODE STARTS HERE

current = self.head

while current is not None:

if current.value.cid == cid:

self.remainingSpace += current.value.size

current.value = content

self.remainingSpace -= content.size

return f'UPDATED: {content}'

current = current.next

return f'CONTENT ID {cid} NOT FOUND'

pass

def mruEvict(self):

# YOUR CODE STARTS HERE

evicted_content = self.tail.value

if self.numItems == 1:

self.head = self.tail = None

else:

self.tail = self.tail.previous

self.tail.next = None

self.remainingSpace += evicted_content.size

self.numItems -= 1

return evicted_content

pass

def lruEvict(self):

# YOUR CODE STARTS HERE

evicted_content = self.head.value

if self.numItems == 1:

self.head = self.tail = None

else:

self.head = self.head.next

self.head.previous = None

self.remainingSpace += evicted_content.size

self.numItems -= 1

return evicted_content

pass

def clear(self):

# YOUR CODE STARTS HERE

self.head = self.tail = None

self.remainingSpace = self.maxSize

self.numItems = 0

return 'Cleared cache!'

pass

class Cache:

"""

>>> cache = Cache(205)

>>> content1 = ContentItem(1000, 10, "Content-Type: 0", "0xA")

>>> content2 = ContentItem(1003, 13, "Content-Type: 0", "0xD")

>>> content3 = ContentItem(1008, 242, "Content-Type: 0", "0xF2")

>>> content4 = ContentItem(1004, 50, "Content-Type: 1", "110010")

>>> content5 = ContentItem(1001, 51, "Content-Type: 1", "110011")

>>> content6 = ContentItem(1007, 155, "Content-Type: 1", "10011011")

>>> content7 = ContentItem(1005, 23, "Content-Type: 2", "

'CMPSC132'

")

>>> content8 = ContentItem(1002, 14, "Content-Type: 2", "

'PSU'

")

>>> content9 = ContentItem(1006, 170, "Content-Type: 2", "")

>>> cache.insert(content1, 'lru')

'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'

>>> cache.insert(content2, 'lru')

'INSERTED: CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD'

>>> cache.insert(content3, 'lru')

'Insertion not allowed'

>>> cache.insert(content4, 'lru')

'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'

>>> cache.insert(content5, 'lru')

'INSERTED: CONTENT ID: 1001 SIZE: 51 HEADER: Content-Type: 1 CONTENT: 110011'

>>> cache.insert(content6, 'lru')

'INSERTED: CONTENT ID: 1007 SIZE: 155 HEADER: Content-Type: 1 CONTENT: 10011011'

>>> cache.insert(content7, 'lru')

"INSERTED: CONTENT ID: 1005 SIZE: 23 HEADER: Content-Type: 2 CONTENT:

'CMPSC132'

"

>>> cache.insert(content8, 'lru')

"INSERTED: CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT:

'PSU'

"

>>> cache.insert(content9, 'lru')

"INSERTED: CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: "

>>> cache

L1 CACHE:

REMAINING SPACE:182

ITEMS:2

LIST:

[CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD]

[CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]

L2 CACHE:

REMAINING SPACE:50

ITEMS:1

LIST:

[CONTENT ID: 1007 SIZE: 155 HEADER: Content-Type: 1 CONTENT: 10011011]

L3 CACHE:

REMAINING SPACE:21

ITEMS:2

LIST:

[CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: ]

[CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT:

'PSU'

]

>>> cache.hierarchy[0].clear()

'Cleared cache!'

>>> cache.hierarchy[1].clear()

'Cleared cache!'

>>> cache.hierarchy[2].clear()

'Cleared cache!'

>>> cache

L1 CACHE:

REMAINING SPACE:205

ITEMS:0

LIST:

L2 CACHE:

REMAINING SPACE:205

ITEMS:0

LIST:

L3 CACHE:

REMAINING SPACE:205

ITEMS:0

LIST:

>>> cache.insert(content1, 'mru')

'INSERTED: CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA'

>>> cache.insert(content2, 'mru')

'INSERTED: CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD'

>>> cache[content1].value

CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA

>>> cache[content2].value

CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD

>>> cache[content3]

'Cache miss!'

>>> cache.insert(content5, 'lru')

'INSERTED: CONTENT ID: 1001 SIZE: 51 HEADER: Content-Type: 1 CONTENT: 110011'

>>> content6 = ContentItem(1007, 160, "Content-Type: 1", "10011011")

>>> cache.insert(content6, 'lru')

'INSERTED: CONTENT ID: 1007 SIZE: 160 HEADER: Content-Type: 1 CONTENT: 10011011'

>>> cache.insert(content4, 'lru')

'INSERTED: CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010'

>>> cache.insert(content7, 'mru')

"INSERTED: CONTENT ID: 1005 SIZE: 23 HEADER: Content-Type: 2 CONTENT:

'CMPSC132'

"

>>> cache.insert(content8, 'mru')

"INSERTED: CONTENT ID: 1002 SIZE: 14 HEADER: Content-Type: 2 CONTENT:

'PSU'

"

>>> cache.insert(content9, 'mru')

"INSERTED: CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: "

>>> cache

L1 CACHE:

REMAINING SPACE:182

ITEMS:2

LIST:

[CONTENT ID: 1003 SIZE: 13 HEADER: Content-Type: 0 CONTENT: 0xD]

[CONTENT ID: 1000 SIZE: 10 HEADER: Content-Type: 0 CONTENT: 0xA]

L2 CACHE:

REMAINING SPACE:155

ITEMS:1

LIST:

[CONTENT ID: 1004 SIZE: 50 HEADER: Content-Type: 1 CONTENT: 110010]

L3 CACHE:

REMAINING SPACE:12

ITEMS:2

LIST:

[CONTENT ID: 1006 SIZE: 170 HEADER: Content-Type: 2 CONTENT: ]

[CONTENT ID: 1005 SIZE: 23 HEADER: Content-Type: 2 CONTENT:

'CMPSC132'

]

>>> cache.clear()

'Cache cleared!'

>>> contentA = ContentItem(2000, 52, "Content-Type: 2", "GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1")

>>> contentB = ContentItem(2001, 76, "Content-Type: 2", "GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1")

>>> contentC = ContentItem(2002, 11, "Content-Type: 2", "GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1")

>>> cache.insert(contentA, 'lru')

'INSERTED: CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1'

>>> cache.insert(contentB, 'lru')

'INSERTED: CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1'

>>> cache.insert(contentC, 'lru')

'INSERTED: CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1'

>>> cache.hierarchy[2]

REMAINING SPACE:66

ITEMS:3

LIST:

[CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]

[CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]

[CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]

>>> cache[contentC].value

CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1

>>> cache.hierarchy[2]

REMAINING SPACE:66

ITEMS:3

LIST:

[CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]

[CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]

[CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]

>>> cache[contentA].next.previous.value

CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1

>>> cache.hierarchy[2]

REMAINING SPACE:66

ITEMS:3

LIST:

[CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]

[CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]

[CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]

>>> cache[contentC].next.previous.value

CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1

>>> cache.hierarchy[2]

REMAINING SPACE:66

ITEMS:3

LIST:

[CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]

[CONTENT ID: 2000 SIZE: 52 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201802040nwe.htm HTTP/1.1]

[CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]

>>> contentD = ContentItem(2002, 11, "Content-Type: 2", "GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1")

>>> cache.insert(contentD, 'lru')

'Content 2002 already in cache, insertion not allowed'

>>> contentE = ContentItem(2000, 103, "Content-Type: 2", "GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1")

>>> cache[2000] = contentE

>>> cache.hierarchy[2]

REMAINING SPACE:15

ITEMS:3

LIST:

[CONTENT ID: 2000 SIZE: 103 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1]

[CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1]

[CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1]

>>> cache.hierarchy[2].tail.value

CONTENT ID: 2001 SIZE: 76 HEADER: Content-Type: 2 CONTENT: GET https://giphy.com/gifs/93lCI4D0murAszeyA6/html5 HTTP/1.1

>>> cache.hierarchy[2].tail.previous.value

CONTENT ID: 2002 SIZE: 11 HEADER: Content-Type: 2 CONTENT: GET https://media.giphy.com/media/YN7akkfUNQvT1zEBhO/giphy-downsized.gif HTTP/1.1

>>> cache.hierarchy[2].tail.previous.previous.value

CONTENT ID: 2000 SIZE: 103 HEADER: Content-Type: 2 CONTENT: GET https://www.pro-football-reference.com/boxscores/201801210phi.htm HTTP/1.1

>>> cache.hierarchy[2].tail.previous.previous is cache.hierarchy[2].head

True

>>> cache.hierarchy[2].tail.previous.previous.previous is None

True

"""

def __init__(self, lst_capacity):

self.hierarchy = [CacheList(lst_capacity), CacheList(lst_capacity), CacheList(lst_capacity)]

self.size = 3

def __str__(self):

return ('L1 CACHE: {} L2 CACHE: {} L3 CACHE: {} '.format(self.hierarchy[0], self.hierarchy[1], self.hierarchy[2]))

__repr__=__str__

def clear(self):

for item in self.hierarchy:

item.clear()

return 'Cache cleared!'

def insert(self, content, evictionPolicy):

# YOUR CODE STARTS HERE

res = self.hierarchy[self.hashFunc(content.header)].put(content, evictionPolicy)

return res or f'INSERTED: {content}'

pass

def __getitem__(self, content):

# YOUR CODE STARTS HERE

pass

def __setitem__(self, cid, content):

# YOUR CODE STARTS HERE

pass