LFUCache Leetcode (Hard, #460)

LFUCache.php

<?php

/*
 * Least Frequently Used (LFU) is a caching algorithm in which the least frequently used cache block is removed whenever the cache is overflowed.
 * In LFU we check the old page as well as the frequency of that page and if the frequency of the page is larger than the old page we cannot remove it
 * and if all the old pages are having same frequency then take last i.e FIFO method for that and remove that page.
 */

include_once '../../runner.php';

class DoublyLinkedList
{

    /**
     * @var DoublyLinkedListNode|null
     */
    private $head;

    /**
     * @var DoublyLinkedListNode|null
     */
    private $tail;

    /**
     * @var int
     */
    private $count = 0;

    public function unshift(DoublyLinkedListNode $node): void
    {
        if (null === $this->head) {

            $this->head = $this->tail = $node;

        } else {

            $formerHead = $this->head;

            $node->setNext($formerHead);
            $formerHead->setPrev($node);

            $this->head = $node;
        }

        $this->count++;
    }

    public function shift(): ?DoublyLinkedListNode
    {
        if (null === $this->head) {
            return null;
        }

        $node = $this->head;

        $this->head = $node->getNext();

        if (null !== $this->head) {
            $this->head->setPrev(null);
        } else {
            $this->tail = null;
        }

        $this->count--;

        return $node;
    }

    public function push(DoublyLinkedListNode $node): void
    {
        if (null === $this->tail) {

            $this->head = $this->tail = $node;

        } else {

            $formerTail = $this->tail;
            $node->setPrev($formerTail);
            $formerTail->setNext($node);

            $this->tail = $node;
        }

        $this->count++;
    }

    public function pop(): ?DoublyLinkedListNode
    {
        if (null === $this->tail) {
            return null;
        }

        $node = $this->tail;

        $this->tail = $node->getPrev();

        if (null !== $this->tail) {
            $this->tail->setNext(null);
        } else {
            $this->head = null;
        }

        $this->count--;

        return $node;
    }

    /**
     * @return DoublyLinkedListNode|null
     */
    public function getHead(): ?DoublyLinkedListNode
    {
        return $this->head;
    }

    /**
     * @return DoublyLinkedListNode|null
     */
    public function getTail(): ?DoublyLinkedListNode
    {
        return $this->tail;
    }

    /**
     * @return int
     */
    public function getCount(): int
    {
        return $this->count;
    }

    public function deleteNode(DoublyLinkedListNode $node): void
    {
        if ($this->head === $node) {
            $this->head = $node->getNext();
        }

        if ($this->tail === $node) {
            $this->tail = $node->getPrev();
        }

        $node->removeMeFromChain();

        $this->count--;

        if (0 === $this->count) {
            $this->head = $this->tail = null;
        }
    }

    public function test(): array
    {
        return [
            null === $this->head,
            null === $this->tail,
            $this->count,
            $this->head,
            $this->tail
        ];
    }
}

class DoublyLinkedListNode implements JsonSerializable
{

    /**
     * @var DoublyLinkedListNode|null
     */
    private $prev;

    /**
     * @var DoublyLinkedListNode|null
     */
    private $next;

    /**
     * @var mixed
     */
    private $value;

    public function __construct($value)
    {
        $this->value = $value;
    }

    public function getValue()
    {
        return $this->value;
    }

    /**
     * @param mixed $value
     */
    public function setValue($value): void
    {
        $this->value = $value;
    }

    /**
     * @param DoublyLinkedListNode|null $prev
     */
    public function setPrev(?DoublyLinkedListNode $prev): void
    {
        $this->prev = $prev;
    }

    /**
     * @param DoublyLinkedListNode|null $next
     */
    public function setNext(?DoublyLinkedListNode $next): void
    {
        $this->next = $next;
    }

    /**
     * @return DoublyLinkedListNode|null
     */
    public function getPrev(): ?DoublyLinkedListNode
    {
        return $this->prev;
    }

    /**
     * @return DoublyLinkedListNode|null
     */
    public function getNext(): ?DoublyLinkedListNode
    {
        return $this->next;
    }

    public function removeMeFromChain(): void
    {
        // connect prev and next nodes

        if (null !== $this->next) {
            $this->next->setPrev($this->prev);
        }

        if (null !== $this->prev) {
            $this->prev->setNext($this->next);
        }

        $this->next = $this->prev = null;
    }

    /**
     * @inheritDoc
     */
    public function jsonSerialize()
    {
        $valuePrev = null === $this->prev ? null : $this->prev->getValue();
        $valueNext = null === $this->next ? null : $this->next->getValue();

        return [$this->value, $valuePrev, $valueNext];
    }
}

class LRUCache
{

    private $capacity;
    private $count = 0;

    private $logEnabled = true;
    private $opCount = 0;

    /**
     * @var SplMinHeap
     */
    private $blocks;

    /**
     * @var DoublyLinkedListNode[]
     */
    private $hashMap = [];

    /**
     * @param Integer $capacity
     */
    public function __construct($capacity)
    {
        $this->capacity = $capacity;
        $this->linkedList = new DoublyLinkedList;
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    public function get($key): int
    {
        $this->opCount++;
        $this->log(sprintf('#%d GET %s', $this->opCount, str_repeat('-', 30)));

        if (array_key_exists($key, $this->hashMap)) {

            $node = $this->hashMap[$key];

            // mark the key as recently used
            if ($this->linkedList->getHead() !== $node) {

                // Remove the node from chain
                $this->linkedList->deleteNode($node);

                // Add same node to top of the chain
                $this->linkedList->unshift($node);

                $this->log('Node bubbled to top');
            }

            $this->log(sprintf(
                'Requested value for key %d. Returns %d; Current count: %d; LC: %d; LTK: %d, LHK: %d',
                $key, $node->getValue()->value, $this->count, $this->linkedList->getCount(),
                $this->linkedList->getTail()->getValue()->key,
                $this->linkedList->getHead()->getValue()->key
            ));

            return $node->getValue()->value;
        }

        $this->log(sprintf('Requested value for key %d. Returns -1 (not found)', $key));

        return -1;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return void
     */
    public function put($key, $value): void
    {
        /**
         * CASES:
         *
         * 1) if amount of items < the cache capacity
         *      - Create new node and put it in head of linked list
         *      - Add element in hash table with provided key and reference to the linked list node
         *      - Increase counter
         * 2) if amount of items == the cache capacity
         *      - Remove LRU element from tail of the linked list and the hash table (in LL we need to have the key also)
         *      - Decrease counter
         *      - See Case 1
         */

        $this->opCount++;
        $this->log(sprintf('#%d PUT %s', $this->opCount, str_repeat('-', 30)));

        if (array_key_exists($key, $this->hashMap)) {

            // we need just to update the value
            // and put the node on top of the list?

            $node = $this->hashMap[$key];

            $node->getValue()->value = $value;

            // mark the key as recently used
            if ($this->linkedList->getHead() !== $node) {

                // Remove the node from chain
                $this->linkedList->deleteNode($node);

                // Add same node to top of the chain
                $this->linkedList->unshift($node);

                $this->log('Node bubbled to top');
            }

            $this->log(sprintf(
                'Updated value for key %d with value %d; Current count: %d; LC: %d; LTK: %d, LHK: %d',
                $key, $value, $this->count, $this->linkedList->getCount(),
                $this->linkedList->getTail()->getValue()->key,
                $this->linkedList->getHead()->getValue()->key
            ));
            return;
        }

        if ($this->count === $this->capacity) {

            // we already fulfilled the cache
            // we need to evict the LRU element

            /** @var DoublyLinkedListNode $lru */
            $lru = $this->linkedList->pop();
            unset($this->hashMap[$lru->getValue()->key]);

            $this->count--;

            $this->log(sprintf(
                'Evicted key %d with value %d; Current count: %d; LC: %d; LTK: %d, LHK: %d',
                $lru->getValue()->key, $lru->getValue()->value, $this->count, $this->linkedList->getCount(),
                $this->linkedList->getTail()->getValue()->key,
                $this->linkedList->getHead()->getValue()->key
            ));
        }

        $node = new DoublyLinkedListNode(new LRUCacheNode($key, $value));

        // put in top of the list
        $this->linkedList->unshift($node);
        $this->hashMap[$key] = $node;
        $this->count++;

        $this->log(sprintf(
            'Added key %d with value %d; Current count: %d; LC: %d; LTK: %d, LHK: %d',
            $key, $value, $this->count, $this->linkedList->getCount(),
            $this->linkedList->getTail()->getValue()->key,
            $this->linkedList->getHead()->getValue()->key
        ));
    }

    private function log($message): void
    {
        if (!$this->logEnabled) {
            return;
        }

        $node = $this->linkedList->getHead();
        $stack = [];

        while (null !== $node) {
            $stack[] = $node->getValue()->key;
            $node = $node->getNext();
        }

        $stack = implode('->', $stack);

        printf("[log][%d/%d] %s\t\t%s\n", $this->count, $this->capacity, $message, $stack);
    }
}

class LRUCacheNode
{
    public $value;
    public $key;

    public function __construct($key, $value)
    {
        $this->key = $key;
        $this->value = $value;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);
 */

//$cache = new LRUCache(2);
//
//$cache->put(1, 1);
//$cache->put(2, 2);
//$cache->get(1);       // returns 1
//$cache->put(3, 3);    // evicts key 2
//$cache->get(2);       // returns -1 (not found)
//$cache->put(4, 4);    // evicts key 1
//$cache->get(1);       // returns -1 (not found)
//$cache->get(3);       // returns 3
//$cache->get(4);       // returns 4

$input = <<<STDIN
["LRUCache","put","put","put","put","put","get","put","get","get","put","get","put","put","put","get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put","get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put","get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put","get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"]
[[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]
STDIN;

$expected = <<<STDOUT
[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,-1,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,-1,null,null,null,null,29,null,null,null,null,17,22,18,null,null,null,-1,null,null,null,20,null,null,null,-1,18,18,null,null,null,null,20,null,null,null,null,null,null,null]
STDOUT;

runner($input, $expected);

runner.php

<?php

function runner($input, $expected)
{

    $lines = explode(PHP_EOL, $input, 2);
    $operations = json_decode($lines[0], true, 512, JSON_THROW_ON_ERROR);
    $values = json_decode($lines[1], true, 512, JSON_THROW_ON_ERROR);

    $expected = json_decode($expected, true, 512, JSON_THROW_ON_ERROR);


    // key 0 in operations is create an object
    // key 0 in operations are arguments for the object above

    $model = new $operations[0](...$values[0]);

    $opIndex = 1;
    $output = [null];

    echo 'Total operations will be performed: ' . count($operations) . "\n";

    foreach ($operations as $key => $value) {

        if ($key === 0) {

            continue;
        }

        $opIndex++;
        $output[] = call_user_func_array([$model, $operations[$key]], $values[$key]);

        if (($expectedSlice = array_slice($expected, 0, $opIndex)) !== $output) {

            echo "\n\n[Step $opIndex] Operation STOPPED due errors:\n";
            echo 'Expected: ' . json_encode($expectedSlice, JSON_THROW_ON_ERROR, 512) . "\n";
            echo 'Got:      ' . json_encode($output, JSON_THROW_ON_ERROR, 512) . "\n";

            break;
        }

    }

    return json_encode($output, JSON_THROW_ON_ERROR, 512);
}