Test two lru-queue solutions

index.js

'use strict';

var LruQueue      = require('lru-queue')
  , SnowyuLruQueue = require('./snowyu-lru-queue')

  , now = Date.now;

var getMemoize = function (LruQueue) {
	return function (fn) {
		var cache = {}, queue = new LruQueue(1000);
		return function (x) {
			var result = cache[x], cleared;
			if (result !== undefined) {
				queue.hit(x);
				return result;
			}
			result = cache[x] = fn(x);
			cleared = queue.hit(x);
			if (cleared !== undefined) delete cache[cleared];
			return result;
		};
	};
};

var getMemoizedFibonacci = function (memoize) {
	var fib = memoize(function (x) {
		return (x < 2) ? 1 : fib(x - 1) + fib(x - 2);
	});
	return fib;
};

var repeatCount = 1000, base = 4000, memo, total, i, time;

total = 0;
i = repeatCount;
while (i--) {
	// Replace below LruQueue with SnowyuLruQueue to test it
	memo = getMemoizedFibonacci(getMemoize(LruQueue));
	time = now();
	memo(base);
	total += now() - time;
}
console.log(total);

snowyu-lru-queue.js

"use strict";

var LRUQueue, create, hasOwnProperty;

create = Object.create;

hasOwnProperty = Object.prototype.hasOwnProperty;

module.exports = LRUQueue = (function() {
	var QueueItem;

	QueueItem = (function() {
		function QueueItem(value) {
			this.value = value;
		}

		return QueueItem;

	})();

	function LRUQueue(capacity) {
		if (!(this instanceof LRUQueue)) {
			return new LRUQueue(capacity);
		}
		this.maxCapacity = capacity > 0 ? capacity : 0;
		this.clear();
	}

	LRUQueue.prototype.add = function(id) {
		var result;
		id.lu = this._mru;
		this.queue[this._mru] = id;
		++this.length;
		++this._mru;
		if (this.length > this.maxCapacity) {
			result = this.pop();
		}
		return result;
	};

	LRUQueue.prototype.push = LRUQueue.prototype.add;

	LRUQueue.prototype.pop = function() {
		var result;
		this.shiftLU();
		result = this.queue[this._lru];
		delete this.queue[this._lru];
		--this.length;
		return result;
	};

	LRUQueue.prototype.use = function(id) {
		delete this.queue[id.lu];
		id.lu = this._mru;
		this.queue[this._mru] = id;
		++this._mru;
	};

	LRUQueue.prototype.hit = function(id) {
		var result, s;
		if (typeof id === 'string' || typeof id === 'number' || typeof id === 'boolean') {
			s = id;
			if (this._map) {
				id = this._map[s];
				if (id === void 0) {
					id = new QueueItem(s);
				}
			} else {
				this._map = create(null);
				id = new QueueItem(s);
			}
			this._map[s] = id;
		}
		if (id.lu === void 0) {
			result = this.add(id);
			if (result instanceof QueueItem) {
				result = result.value;
				delete this._map[result];
			}
			return result;
		} else {
			return this.use(id);
		}
	};

	LRUQueue.prototype["delete"] = function(id) {
		if (this.queue[id.lu]) {
			delete this.queue[id.lu];
			--this.length;
			if (this.length) {
				this.shiftLU();
			} else {
				this._mru = 0;
				this._lru = 0;
			}
		}
	};

	LRUQueue.prototype.del = LRUQueue.prototype["delete"];

	LRUQueue.prototype.forEach = function(callback, thisArg) {
		var i, item, k;
		thisArg || (thisArg = this);
		k = this._mru;
		i = 0;
		while (--k >= 0 && i < this.length) {
			item = this.queue[k];
			if (item) {
				++i;
				callback.call(thisArg, item, this);
			}
		}
	};

	LRUQueue.prototype.clear = function() {
		this.length = 0;
		this._lru = 0;
		this._mru = 0;
		this.queue = create(null);
		delete this._map;
	};

	LRUQueue.prototype.shiftLU = function() {
		while (this._lru < this._mru && !this.queue[this._lru]) {
			this._lru++;
		}
	};

	return LRUQueue;

})();