Skip to content

@kriskowal /arc-map.js
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Adaptive replacement cache, implemented in JavaScript, extending Montage Collections, using CommonJS packaging suitable for NodeJS for servers and Montage or Mr for browsers.
"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
);
};
// 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());
};
{
"name": "arc",
"version": "0.0.0",
"dependencies": {
"collections": "0.1.5 - 0.2"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.