<?php
interface LRUCache{
/**
•@param string $key
•@param string $value
•@return bool $result
•
•Stores value against the key in the cache */
public function insertIntoCache($key,$value);
/**
•@param string $key
•@return string $value
•Gets the value of a key from the cache */
public function getFromCache($key);
/** Purge the entire cache */
public function purgeCache();
/**
•@return int $count
•Gets the number of successful cache hits so far */
public function allCacheHits();
/**
•@return int $count
•Gets the number of unsuccessful cache hits so far
**/
public function allCacheMissed();
}
class Cache implements LRUCache{
// int the max number of elements the cache supports
private $capacity;
// Array representing a naive hashmap (TODO needs to pass the key through a hash function)
private $hashmap = array();
// object Node representing the head of the list
private $head;
// object Node representing the tail of the list
private $tail;
// Cachehit
private $cacheHit;
//Cache missed
private $cacheMissed;
/**
•@param string $key
•@param string $value
•@return bool $result
**/
public function __construct($capacity) {
$this->capacity = $capacity;
$this->hashmap = array();
$this->head = new Node(null, null);
$this->tail = new Node(null, null);
$this->head->setNext($this->tail);
$this->tail->setPrevious($this->head);
$this->cacheHit = 0;
$this->cacheMissed = 0;
}
/*Stores value against the key in the cache */
public function insertIntoCache($key,$value){
if ($this->capacity <= 0) { return false; }
if (isset($this->hashmap[$key]) && !empty($this->hashmap[$key])) {
$node = $this->hashmap[$key];
// update data
$this->detach($node);
$this->attach($this->head, $node);
$node->setData($value);
}
else {
$node = new Node($key, $value);
$this->hashmap[$key] = $node;
$this->attach($this->head, $node);
// check if cache is full
if (count($this->hashmap) > $this->capacity) {
// we're full, remove the tail
$nodeToRemove = $this->tail->getPrevious();
$this->detach($nodeToRemove);
unset($this->hashmap[$nodeToRemove->getKey()]);
}
}
return true;
}
/**
•@param string $key
•@return string $value
•Gets the value of a key from the cache */
public function getFromCache($key){
if (!isset($this->hashmap[$key])) { $this->cacheMissed++; return null; }
$node = $this->hashmap[$key];
if($node->getData())
$this->cacheHit++;
if (count($this->hashmap) == 1) { return $node->getData(); }
// refresh the access
$this->detach($node);
$this->attach($this->head, $node);
return $node->getData();
}
/** Purge the entire cache */
public function purgeCache(){
$this->hashmap = array();
}
/**
•@return int $count
•Gets the number of successful cache hits so far */
public function allCacheHits(){
return $this->cacheHit;
}
/**
•@return int $count
•Gets the number of unsuccessful cache hits so far
**/
public function allCacheMissed(){
return $this->cacheMissed;
}
/**
* Removes a key from the cache
* @param string $key key to remove
* @return bool true if removed, false if not found
*/
public function remove($key) {
if (!isset($this->hashmap[$key])) { return false; }
$nodeToRemove = $this->hashmap[$key];
$this->detach($nodeToRemove);
unset($this->hashmap[$nodeToRemove->getKey()]);
return true;
}
/**
* Adds a node to the head of the list
* @param Node $head the node object that represents the head of the list
* @param Node $node the node to move to the head of the list
**/
private function attach($head, $node) {
$node->setPrevious($head);
$node->setNext($head->getNext());
$node->getNext()->setPrevious($node);
$node->getPrevious()->setNext($node);
}
/**
* Removes a node from the list
* @param Node $node the node to remove from the list
*/
private function detach($node) {
$node->getPrevious()->setNext($node->getNext());
$node->getNext()->setPrevious($node->getPrevious());
}
}
class Node {
/**
* the key of the node, this might seem reduntant,
* but without this duplication, we don't have a fast way
* to retrieve the key of a node when we wan't to remove it
* from the hashmap.
*/
private $key;
// the content of the node
private $data;
// the next node
private $next;
// the previous node
private $previous;
/**
* @param string $key the key of the node
* @param string $data the content of the node
*/
public function __construct($key, $data) {
$this->key = $key;
$this->data = $data;
}
/**
* Sets a new value for the node data
* @param string the new content of the node
*/
public function setData($data) {
$this->data = $data;
}
/**
* Sets a node as the next node
* @param Node $next the next node
*/
public function setNext($next) {
$this->next = $next;
}
/**
* Sets a node as the previous node
* @param Node $previous the previous node
*/
public function setPrevious($previous) {
$this->previous = $previous;
}
/**
* Returns the node key
* @return string the key of the node
*/
public function getKey() {
return $this->key;
}
/**
* Returns the node data
* @return mixed the content of the node
*/
public function getData() {
return $this->data;
}
/**
* Returns the next node
* @return Node the next node of the node
*/
public function getNext() {
return $this->next;
}
/**
* Returns the previous node
* @return Node the previous node of the node
*/
public function getPrevious() {
return $this->previous;
}
}
$lru = new Cache(5);
$db = array(
"This is item 0",
"This is item 1",
"This is item 2",
"This is item 3",
"This is item 4",
"This is item 5"
);
$testPattern = "0,2,4,1,0,5,3,1,5,3,0,1,5,2,5,1,4";
// Implement test pattern.
foreach (explode(",", $testPattern) as $index) {
$item = $lru->getFromCache($index);
if ($item){
printf ("Cache hit. - %s\n", $index);
echo ('</br>');
} else {
printf("Cache miss for key %s.", $index);
echo ('</br>');
$lru->insertIntoCache($index, $db[$index]);
}
}
echo '<br>';
$item2 = $lru->allCacheHits();
printf("Total Cache Hit : ".$item2);
echo '<br>';
$item3 = $lru->allCacheMissed();
printf("Total Cache Missed : ".$item3);
Comments
Post a Comment