jackrusher · March 29, 2021 09:23 · Mar 29, 2021
diff --git a/trinity.js b/trinity.js
@@ -0,0 +1,114 @@
+// three indices to efficiently support all lookups
+function createDB() {
+    return {eav: new Map(),
+            ave: new Map(),
+            vea: new Map()};
+}
+
+function addToIndex(xs, x, y, z, triple) {
+    let ys = xs.get(x);
+    if(ys == undefined) {
+        ys = new Map();
+        xs.set(x, ys);
+    }
+    let zs = ys.get(y);
+    if(zs == undefined) {
+        zs = new Map();
+        ys.set(y, zs);
+    }
+    zs.set(z, triple);
+}
+
+function removeFromIndex(table, x, y, z) {
+    table.get(x)?.get(y)?.delete(z);
+}
+
+// always called with at least x
+function lookupInIndex(index, x, y, z) {
+    let triples = new Set();
+    if (y == undefined) {
+        index.get(x)?.forEach(function(y) {
+            y.forEach((z) => triples.add(z));
+        });
+    } else if (z == undefined ) {
+        index.get(x)?.get(y)?.forEach((z) => triples.add(z));
+    } else {
+        let triple = index.get(x)?.get(y)?.get(z);
+        if (triple) {
+            triples.add(triple);
+        }
+    }
+    return triples;
+}
+
+// N.B. upsert semantics!
+function add(db, e, a, v) {
+    // index payloads are all pointers to a single frozen array, thus we
+    // are able to return an immutable value and JS's questionable equality
+    // semantics actually work properly for triples (Sets work, &c). 
+    let triple = Object.freeze([e, a, v]);
+    addToIndex(db.eav, e, a, v, triple);
+    addToIndex(db.ave, a, v, e, triple);
+    addToIndex(db.vea, v, e, a, triple);
+}
+
+function remove(db, e, a, v) {
+    removeFromIndex(db.eav, e, a, v);
+    removeFromIndex(db.ave, a, v, e);
+    removeFromIndex(db.vea, v, e, a);
+}
+
+function get(db, e, a, v) {
+    if(e != undefined) {
+        if(a == undefined && v != undefined) {
+            return lookupInIndex(db.vea, v, e); // e, null, v
+        }
+        return lookupInIndex(db.eav, e, a, v); // e, null, null / e, a, null / e, a, v
+    } else if(a != undefined) {
+        return lookupInIndex(db.ave, a, v); // null, a, null / null, a, v
+    } else if (v != undefined) {
+        return lookupInIndex(db.vea, v); // null, null, v
+    }
+    throw 'get() requires at least one of {e,a,v}!';
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// testing
+
+test_data = [[1, ":username", "arslonga"],
+             [1, ":firstname", "Alvin"],
+             [1, ":lastname", "Pencilpoint"],
+             [1, ":role", "designer"],
+             [1, ":group", 47],
+             [2, ":username", "l33t"],
+             [2, ":firstname", "Edward"],
+             [2, ":lastname", "Bughands"],
+             [2, ":role", "developer"],
+             [2, ":workgroup", 47],
+             [3, ":username", "baker"],
+             [3, ":firstname", "Pippin"],
+             [3, ":lastname", "Apfelbrot"],
+             [3, ":role", "designer"],
+             [3, ":role", "developer"],
+             [3, ":workgroup", 23]];
+
+function addTestData(db) {
+    test_data.forEach((triple) => add(db, triple[0], triple[1], triple[2]));
+}
+
+test_db = createDB();
+addTestData(test_db);
+
+console.log(
+    JSON.stringify(
+        Array.from(
+            get(test_db, 1,null,null)
+            // get(null,":lastname",null)
+            // get(null,null,"Bughands")
+            // get(null,":firstname","Alvin")
+            // get(3,":role",null)
+            // get(3,null,"Pippin")
+            // get(2, ":workgroup", 47)
+            // get(null,null,null)
+        )
+    ));