I need to create three classes to demonstrate LRU Cache and LFU Cache based on the attached UML diagram and the following logic:

ALGORITHMS

Items in the cache can be searched for (getIndexOfItem) or return -1 if they are not found.

As the name suggests, when the cache becomes full, a replacement algorithm must be used to determine what item is removed from the cache so that the newest item can enter the cache. The

item that was used least-recently or least-frequently must be removed from the cache (array), and all the other items move over to make room for this new item.

Note that this is not as simple as it might appear, because when an item is accessed (added) you must first check to see if the item already exists in the cache. If it does, then you move it to the front of the cache, because it was the most recently/frequently used item. That requires you to make room for it, which means moving all the items down the list up to the item that will be moved to the front.

You must code the Cache constructor such that it takes a size, sets it and allocates memory for

that particular sized array dynamically.

ADDING A BRAND NEW ITEM TO THE CACHE

Lets assume there is a size 5 array containing 5 items (i.e., numItems = 5), as follows:

1, 2, 3, 4, 5

Now, we want to add a brand new item, 6 to the cache, but there is no more room. The

replacement algorithm goes through, and 5 will ultimately be what is discarded. So, all the other

items are moved down the cache, and 5 is replaced entirely, making room for the new (most

recent), item 6, thusly:

6, 1, 2, 3, 4

ADDING AN ALREADY EXISTING ITEM TO THE CACHE

Now, lets say someone requests 3. This already exists in the cache, so all the items in front of it

must be moved down, yielding the following:

3, 6, 1, 2, 4

WHAT MUST YOU TURN IN?

You must utilize separate compilation for the classes, and provide a main function that uses polymorphic references to test the LRUCache using a Cache pointer variable.

In other words:

Cache* myLRUCache = new LRUCache(cacheSize);

Then, call the functions on this reference to test it.

Your class may be tested with a completely different main file / function than you provide, so you must ensure that your classes are not tightly coupled with the main function.

You must have the following:

Cache.h (specification file)

Cache.cpp (implementation file)

LRUCache.h

LRUCache.cpp

LFUCache.h

LFUCache.cpp

main.cpp (the client file / driver file to test your LRU cache)

Thank you!

Cache #size: int #numite mint #dataCache: int[] #setsize(someSize :int):void +addItem(item: int):void +getIndexOfltem(item: int):int +getItemAtFront):int LRUCache LFUCache LRUCache (size: int) +addItem (item: int):void +getIndexofItem (item: int):int LFUCache (size: int) +addItem (item: int):void +getIndexofitem(item: int):int