LRUMemoryCache.ts

module LRUMemoryCache {
    export class Cache {
        private leastRecentlyUsed: Node;
        private mostRecentlyUsed: Node;
        private map: Map<string, Node>;
        private usage: number = 0;

        constructor(public size: number) {
            if (size <= 0) {
                throw new Error('Cache size should be larger than 0');
            }
        }

        set(key: string, value: CacheValue) {
            if (this.size < value.length) {
                return; // XXX: should throw error?
            }
            
            var node = new Node(key, value);

            if (this.mostRecentlyUsed) {
                this.mostRecentlyUsed.next = node;
                node.prev = this.mostRecentlyUsed;
            }
            this.mostRecentlyUsed = node;

            if (this.leastRecentlyUsed == null) {
                this.leastRecentlyUsed = node;
            }

            this.map[key] = node;
            this.usage += value.length;

            this.trim();
        }

        get(key: string): CacheValue {
            var node = this.map[key];
            this.use(node);
            
            return node.value;
        }

        private use(node: Node) {
            if (node.next) node.next.prev = node.prev;
            if (node.prev) node.prev.next = node.next;

            node.next = null;
            node.prev = this.mostRecentlyUsed;
            this.mostRecentlyUsed.next = node;
            this.mostRecentlyUsed = node;
        }

        private trim() {
            while (this.isOverflow()) this.removeLeastRecentlyUsed();
        }

        private isOverflow() {
            return this.size < this.usage;
        }

        private removeLeastRecentlyUsed() {
            if (this.leastRecentlyUsed == null) {
                return;
            }

            var node = this.leastRecentlyUsed;
            this.leastRecentlyUsed = node.next;
            node.next.prev = null;
            node.free();
            this.usage -= node.value.length;

            delete this.map[node.key];
        }
    }

    class Node {
        prev: Node;
        next: Node;

        constructor(public key: string, public value: CacheValue) {
        }

        free() {
            delete this.value;
        }
    }

    export interface CacheValue {
        length: number;
    }
}