craigpatten · February 10, 2014 05:06 · Dec 29, 2012
diff --git a/arc-map.js b/arc-map.js
@@ -0,0 +1,47 @@
+"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
+    );
+};
diff --git a/arc-set.js b/arc-set.js
@@ -0,0 +1,144 @@
+
+// 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());
+};
+
diff --git a/package.json b/package.json
@@ -0,0 +1,7 @@
+{
+    "name": "arc",
+    "version": "0.0.0",
+    "dependencies": {
+        "collections": "0.1.5 - 0.2"
+    }
+}
No results found