Adaptive replacement cache, implemented in JavaScript, extending Montage Collections, using CommonJS packaging suitable for NodeJS for servers and Montage or Mr for browsers.

arc-map.js

"use strict";

var Shim = require("collections/shim");
var ArcSet = require("./arc-set");
var GenericCollection = require("collections/generic-collection");
var GenericMap = require("collections/generic-map");
var PropertyChanges = require("collections/listen/property-changes");

module.exports = ArcMap;

function ArcMap(values, maxLength, equals, hash, getDefault) {
    if (!(this instanceof ArcMap)) {
        return new ArcMap(values, maxLength, equals, hash);
    }
    equals = equals || Object.equals;
    hash = hash || Object.hash;
    getDefault = getDefault || Function.noop;
    this.contentEquals = equals;
    this.contentHash = hash;
    this.getDefault = getDefault;
    this.store = new ArcSet(
        undefined,
        maxLength,
        function keysEqual(a, b) {
            return equals(a.key, b.key);
        },
        function keyHash(item) {
            return hash(item.key);
        }
    );
    this.length = 0;
    this.addEach(values);
}

Object.addEach(ArcMap.prototype, GenericCollection.prototype);
Object.addEach(ArcMap.prototype, GenericMap.prototype);
Object.addEach(ArcMap.prototype, PropertyChanges.prototype);

ArcMap.prototype.constructClone = function (values) {
    return new this.constructor(
        values,
        this.maxLength,
        this.contentEquals,
        this.contentHash,
        this.getDefault
    );
};

arc-set.js

// Adaptive Replacement Cache
// Patented in the USA by IBM in 2006
// Derrived from http://code.activestate.com/recipes/576532/
// And made to extend Montage Collections https://github.com/montagejs/collections
// Copyright 2012 Kris Kowal.  MIT License

"use strict";

var Set = require("collections/set");
var GenericCollection = require("collections/generic-collection");
var GenericSet = require("collections/generic-set");
var PropertyChanges = require("collections/listen/property-changes");

module.exports = ArcSet;

function ArcSet(values, maxLength, equals, hash, getDefault) {
    if (!(this instanceof ArcSet)) {
        return new ArcSet(values, maxLength, equals, hash, getDefault);
    }
    equals = equals || Object.equals;
    hash = hash || Object.hash;
    getDefault = getDefault || Function.noop;
    this.contentEquals = equals;
    this.contentHash = hash;
    this.getDefault = getDefault;
    this.maxLength = maxLength;
    this.store = Set(null, equals, hash);

    // arc strategy data
    this.p = 0;
    this.t1 = Set(null, equals, hash);
    this.t2 = Set(null, equals, hash);
    this.b1 = Set(null, equals, hash);
    this.b2 = Set(null, equals, hash);

    this.length = 0;
    this.addEach(values);
}

Object.addEach(ArcSet.prototype, GenericCollection.prototype);
Object.addEach(ArcSet.prototype, GenericSet.prototype);
Object.addEach(ArcSet.prototype, PropertyChanges.prototype);

ArcSet.prototype.get = function (value) {
    if (this.store.has(value)) {
        this.add(value);
        return value;
    }
};

ArcSet.prototype.add = function (value) {
    if (this.t1.has(value)) {
        this.t1["delete"](value);
        this.t2.add(value);
        return;
    }
    if (this.t2.has(value)) {
        this.t2["delete"](value);
        this.t2.add(value);
        return;
    }
    this.store.add(value);
    if (this.b1.has(value)) {
        this.p = Math.min(
            this.maxLength,
            this.p + Math.max(
                this.b2.length / this.b1.length,
                1
            )
        );
        this.replace(value);
        this.b1["delete"](value);
        this.t2.add(value);
        return;
    }
    if (this.b2.has(value)) {
        this.p = Math.max(
            0,
            this.p - Math.max(
                this.b1.length / this.b2.length,
                1
            )
        );
        this.replace(value);
        this.b2["delete"](value);
        this.t2.add(value);
        return;
    }
    if (this.t1.length + this.b1.length === this.maxLength) {
        if (this.t1.length < this.maxLength) {
            this.b1.shift();
            this.replace(value);
        } else {
            this.store["delete"](this.t1.shift())
        }
    } else {
        var total = this.t1.length + this.b1.length + this.t2.length + this.b2.length;
        if (total >= this.maxLength) {
            if (total === this.maxLength * 2) {
                this.b2.shift();
            }
            this.replace(value);
        }
    }
    this.t1.add(value);
};

ArcSet.prototype.replace = function (value) {
    var old;
    if (this.t1.length && (
        (this.b2.has(value) && this.t1.length === this.p) ||
        (this.t1.length > this.p)
    )) {
        old = this.t1.shift();
        this.b1.add(old);
    } else {
        old = this.t2.shift();
        this.b2.add(old);
    }
    this.store["delete"](old);
};

ArcSet.prototype.reduce = function (callback, basis /*, thisp*/) {
    var thisp = arguments[2];
    return this.store.reduce(callback, basis, thisp);
};

ArcSet.prototype.reduceRight = function (callback, basis /*, thisp*/) {
    var thisp = arguments[2];
    return this.store.reduce(callback, basis, thisp);
};

ArcSet.prototype.log = function () {
    this.report(console.log, console);
};

ArcSet.prototype.report = function (write, thisp) {
    write.call(thisp, "t1: " + this.t1.toArray());
    write.call(thisp, "t2: " + this.t2.toArray());
    write.call(thisp, "b1: " + this.b1.toArray());
    write.call(thisp, "b2: " + this.b2.toArray());
};

package.json

{
    "name": "arc",
    "version": "0.0.0",
    "dependencies": {
        "collections": "0.1.5 - 0.2"
    }
}