Cache #Size: int #numitem: int #dataCache: int[] #setsize(someSize :int ) :void
ID: 3708783 • Letter: C
Question
Cache #Size: int #numitem: int #dataCache: int[] #setsize(someSize :int ) :void +addItem(item: int):void +getIndexOfItem(item: int)int +getitemAtFrontO: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 Note that in UML,-means private, + means public, and # means protected. Protected members are accessible to the derived (child) class, but are not accessible outside the inheritance hierarchy. In other words, to the "outside world", it is the same as if they are private. The italics of the Cache class name and two of its member functions: addltem and getlndexOfltem is on purpose. These are pure virtual functions, meaning that the derived classes must implement them. There are no implementations in the abstract base class, Cache. ALGORITHMS Items in the cache can be searched for (getIndexOftem) or return- 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. TheExplanation / Answer
Note: Create each of the files *.H and *.CPP mentioned below and then compile.
CACHE.H
#include "conio.h"
#include <iostream>
using namespace std;
class Cache
{
public:
Cache(void);
~Cache(void);
protected:
int size; //assuming this is size of bytes of array
int numItem; //assuming this is Number of elements in array
int *dataCache;
protected:
void setSize(int someSize);
public:
int getItemAtFront();
virtual void addItem(int item) =0;
virtual int getIndexOfItem(int item)=0;
public:
void display();
};
LRUCache.H
#include "cache.h"
class LRUCache :
public Cache
{
public:
LRUCache(void);
~LRUCache(void);
LRUCache(int size);
public:
void addItem(int item);
int getIndexOfItem(int item);
};
LFUCache.H
#include "cache.h"
class LFUCache :
public Cache
{
public:
LFUCache(void);
~LFUCache(void);
LFUCache(int size);
public:
void addItem(int item);
int getIndexOfItem(int item);
};
CACHE.CPP
#include "Cache.h"
Cache::Cache(void)
{
}
Cache::~Cache(void)
{
delete [] dataCache; // When done, free memory pointed to by Cache.
dataCache = NULL; // Clear dataCache to prevent using invalid memory reference.
}
void Cache::setSize(int someSize)
{
dataCache = new int[someSize];
size = someSize*sizeof(int);
numItem = someSize;
//cout << sizeof(dataCache) << " " << sizeof(*(dataCache));
int arrSize = someSize; //length(dataCache);
for(int i=0;i<arrSize;i++)
{
dataCache[i] = -1;
}
}
int Cache::getItemAtFront()
{
return dataCache[0];
}
void Cache::display()
{
int arrSize = numItem;
cout << " Displaying all elements " << endl;
cout << " ----------------------- " << endl;
for(int i=0;i<arrSize;i++)
{
cout << " " << dataCache[i];
}
}
LRUCache.CPP
#include "LRUCache.h"
LRUCache::LRUCache(void)
{
}
LRUCache::~LRUCache(void)
{
}
LRUCache::LRUCache(int size)
{
setSize(size);
}
void LRUCache::addItem(int item)
{
cout << " ***********************************" << endl;
cout << " press any key to continue..."; getch();
cout << " Add " << item << endl;
/*Before adding item check if item exists*/
int indexItem = getIndexOfItem(item);
/* 12345 12344 12334 12234 61234 */
int arrSize ;
if (indexItem == -1)
arrSize = numItem;
else
arrSize = indexItem;
for(int next=arrSize;next>=0;next--)
{
if (next==arrSize)
; //ignore the last element
else if(next==0)
{
dataCache[next+1] = dataCache[next];
dataCache[next] = item;
}
else
dataCache[next+1] = dataCache[next];
}
display(); // display every time an element is added
}
int LRUCache::getIndexOfItem(int item)
{
int arrSize = numItem ;
for(int i=0;i<arrSize;i++)
{
if (dataCache[i] == item)
return i;
}
return -1;
}
LFUCache.CPP
#include "LFUCache.h"
LFUCache::LFUCache(void)
{
}
LFUCache::~LFUCache(void)
{
}
LFUCache::LFUCache(int size)
{
setSize(size);
}
void LFUCache::addItem(int item)
{
;
}
int LFUCache::getIndexOfItem(int item)
{
return -1;
}
MAIN.CPP
#include "LRUCache.h"
int main ()
{
Cache *myLRUCache = new LRUCache(5);
myLRUCache->display();
/* add first 5 elements */
myLRUCache->addItem(5);
myLRUCache->addItem(4);
myLRUCache->addItem(3);
myLRUCache->addItem(2);
myLRUCache->addItem(1);
/* the array is full. add a brand new element*/
myLRUCache->addItem(6);
/* the array is full. add an existing element*/
myLRUCache->addItem(3);
/* the array is full. add an existing element*/
myLRUCache->addItem(2);
/* the array is full. add an existing element that exists at first spot*/
myLRUCache->addItem(2);
/* the array is full. add an existing element that exists at last spot*/
myLRUCache->addItem(4);
cout << " press any key to exit..."; getch();
return 0;
}
OUTPUT
Displaying all elements
-----------------------
-1 -1 -1 -1 -1
***********************************
press any key to continue...
Add 5
Displaying all elements
-----------------------
5 -1 -1 -1 -1
***********************************
press any key to continue...
Add 4
Displaying all elements
-----------------------
4 5 -1 -1 -1
***********************************
press any key to continue...
Add 3
Displaying all elements
-----------------------
3 4 5 -1 -1
***********************************
press any key to continue...
Add 2
Displaying all elements
-----------------------
2 3 4 5 -1
***********************************
press any key to continue...
Add 1
Displaying all elements
-----------------------
1 2 3 4 5
***********************************
press any key to continue...
Add 6
Displaying all elements
-----------------------
6 1 2 3 4
***********************************
press any key to continue...
Add 3
Displaying all elements
-----------------------
3 6 1 2 4
***********************************
press any key to continue...
Add 2
Displaying all elements
-----------------------
2 3 6 1 4
***********************************
press any key to continue...
Add 2
Displaying all elements
-----------------------
2 3 6 1 4
***********************************
press any key to continue...
Add 4
Displaying all elements
-----------------------
4 2 3 6 1
press any key to exit...