LRUCache Leetcode (Medium, #146)

LRUCache.Clean.php

<?php

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 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;
        }
    }

}

class DoublyLinkedListNode
{

    /**
     * @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 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;
    }

}

class LRUCache
{

    private $capacity;
    private $count = 0;

    /**
     * @var DoublyLinkedList
     */
    private $linkedList;

    /**
     * @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
    {
        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);
            }

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

        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
         */

        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);
            }

            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--;
        }

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

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

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);
}