aa treesdold/dev/memidb

6 files changed, 485 insertions, 136 deletions

diff --git a/src/memidb/aatree-test.ts b/src/memidb/aatree-test.ts
new file mode 100644
index 000000000..21ae26173
--- /dev/null
+++ b/src/memidb/aatree-test.ts
@@ -0,0 +1,84 @@
+/*
+ This file is part of TALER
+ (C) 2017 Inria and GNUnet e.V.
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ TALER; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ */
+
+
+import {test} from "ava";
+
+import * as aat from "./aatree";
+
+
+function shuffleArray(array: any[]): any[] {
+  for (let i = array.length - 1; i > 0; i--) {
+    const j = Math.floor(Math.random() * (i + 1));
+    const temp = array[i];
+    array[i] = array[j];
+    array[j] = temp;
+  }
+  return array;
+}
+
+
+function myCmp(a: any, b: any): number {
+  if (a < b) {
+    return -1;
+  }
+  if (a > b) {
+    return 1;
+  }
+  return 0;
+}
+
+
+test("insertion", (t) => {
+  let vs = [];
+  for (let i = 0; i < 1000; i++) {
+    vs.push(Math.floor(Math.random() * 500));
+  }
+  
+  let tree = undefined;
+  t.true(aat.checkInvariants(tree));
+
+  for (let i = 0; i < 1000; i++) {
+    tree = aat.treeInsert(tree, vs[i], myCmp);
+    t.true(aat.checkInvariants(tree));
+    t.true(aat.treeFind(tree, vs[i], myCmp));
+  }
+
+  vs = Array.from(new Set(vs));
+
+  vs.sort((a, b) => a - b);
+  t.deepEqual(aat.treeToArray(tree), vs);
+});
+
+
+test("deletion", (t) => {
+  let vs = [];
+  let tree = undefined;
+  for (let i = 0; i < 1000; i++) {
+    vs.push(Math.floor(Math.random() * 500));
+    tree = aat.treeInsert(tree, vs[i], myCmp);
+    t.true(aat.checkInvariants(tree));
+    t.true(aat.treeFind(tree, vs[i], myCmp));
+  }
+
+  shuffleArray(vs);
+
+  for (let i = 0; i < 1000; i++) {
+    tree = aat.treeDelete(tree, vs[i], myCmp);
+    t.true(aat.checkInvariants(tree));
+    t.false(aat.treeFind(tree, vs[i], myCmp));
+  }
+});
diff --git a/src/memidb/aatree.ts b/src/memidb/aatree.ts
new file mode 100644
index 000000000..50c4f0aae
--- /dev/null
+++ b/src/memidb/aatree.ts
@@ -0,0 +1,388 @@
+/*
+ This file is part of TALER
+ (C) 2017 Inria and GNUnet e.V.
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ TALER; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
+ */
+
+
+/**
+ * Implementation of AA trees (Arne Andersson, 1993) as a persistent data
+ * structure (Prabhakar Ragde, 2014).
+ *
+ * AA trees were chosen since they balance efficiency and a simple
+ * implementation.
+ */
+
+
+/**
+ * An AA tree, either a node or 'undefined' as sentinel element.
+ */
+export type AATree = AATreeNode | undefined;
+
+
+interface AATreeNode {
+  left: AATree;
+  right: AATree;
+  level: number;
+  key: any;
+}
+
+
+/**
+ * Check AA tree invariants.  Useful for testing.
+ */
+export function checkInvariants(t: AATree): boolean {
+  // No invariants for the sentinel.
+  if (!t) {
+    return true;
+  }
+
+  // AA1: The left child of a node x has level one less than x.
+  if (level(t.left) != level(t) - 1) {
+    console.log("violated AA1");
+
+    console.log(JSON.stringify(t, undefined, 2));
+    return false;
+  }
+
+  // AA2: The right child of x has the same level (x is a "double" node) or one less (x is a "single" node).
+  if (!(level(t.right) === level(t) || level(t.right) === level(t) - 1)) {
+    console.log("violated AA2");
+    console.log("level(t.right)", level(t.right));
+    console.log("level(t)", level(t));
+    return false;
+  }
+
+  // AA3: The right child of the right child of x has level less than x.
+  if (t.right && t.right.right) {
+    if (level(t.right.right) >= level(t)) {
+      console.log("violated AA3");
+      console.log(JSON.stringify(t, undefined, 2));
+      return false;
+    }
+  }
+
+  // AA4: All internal nodes have two children.
+  // This invariant follows from how we defined "level"
+  return true;
+}
+
+
+/**
+ * Fix a violation of invariant AA1 by reversing a link.
+ *
+ * ```
+ *    y <--- t    =>     y ---> t
+ *   / \      \   =>    /      / \
+ *  a   b      c  =>   a      b   c
+ * ```
+ */
+function skew(t: AATreeNode) {
+  if (t.left && t.left.level === t.level) {
+    return { ...t.left, right: { ...t, left: t.left.right } };
+  }
+  return t;
+}
+
+
+/**
+ * Fix a violation of invariant AA3 by pulling up the middle node.
+ *
+ * ```
+ *                    =>      y
+ *                    =>     / \
+ *    t --> y --> z   =>    t   z
+ *   /     /          =>   / \
+ *  a     b           =>  a   b
+ * ```
+ */
+function split(t: AATreeNode) {
+  if (t.right && t.right.right && 
+      t.level === t.right.level &&
+      t.right.level === t.right.right.level) {
+    return {
+      level: t.level + 1,
+      key: t.right.key,
+      left: { ...t, right: t.right.left },
+      right: t.right.right,
+    }
+  }
+  return t;
+}
+
+
+/**
+ * Non-destructively insert a new key into an AA tree.
+ */
+export function treeInsert(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATreeNode {
+  if (!t) {
+    return {
+      level: 1,
+      key: k,
+      left: undefined,
+      right: undefined,
+    }
+  }
+  const cmp = cmpFn(k, t.key);
+  if (cmp === 0) {
+    return t;
+  } else if (cmp < 0) {
+    return split(skew({ ...t, left: treeInsert(t.left, k, cmpFn)}));
+  } else {
+    return split(skew({ ...t, right: treeInsert(t.right, k, cmpFn)}));
+  }
+}
+
+
+/**
+ * Level of an AA tree node, or zero if it's a sentinel.
+ */
+function level(t: AATree) {
+  if (!t) {
+    return 0;
+  }
+  return t.level;
+}
+
+
+/**
+ * Check if a node is single, i.e. doens't have a right child
+ * on the same level.
+ */
+function isSingle(t: AATree) {
+  if (t && t.right && t.right.level === t.level) {
+    return false;
+  }
+  return true;
+}
+
+
+/**
+ * Restore invariants that were broken by deleting a node.
+ *
+ * Assumes that invariants for t.left and t.right are already adjusted.
+ */
+function adjust(t: AATreeNode): AATreeNode {
+  // First check if left or right subtree are at the right level.  Note that
+  // they can't be both at the wrong level, since only one node is deleted
+  // before calling adjust.
+  const leftOkay = level(t.left) === level(t) - 1;
+  const rightOkay = (level(t.right) === level(t) || level(t.right) === level(t) - 1);
+  if (leftOkay && rightOkay) {
+    return t;
+  }
+  if (!rightOkay) {
+    if (isSingle(t.left)) {
+      return skew({ ...t, level: t.level - 1 });
+    }
+    /*
+     *      ( t )       =>      ( b )
+     *     /     \      =>     /     \
+     *    x -> b  \     =>    x       t
+     *   /    / \  \    =>   / \     / \
+     *  a    d   e  c   =>  a   d   e   c
+     */
+    const b = t.left!.right!;
+    return {
+      level: b.level + 1,
+      key: b.key,
+      left: { ...t.left, right: b.left },
+      right: { ...t, level: t.level - 1, left: b.right },
+    };
+  }
+  if (!leftOkay) {
+    if (isSingle(t)) {
+      return split({ ...t, level: t.level - 1 });
+    }
+    /*
+     *      t -> ( r )    =>       ( a ) -> r   
+     *     /    /     \   =>      /        / \  
+     *    /    a -> d  b  =>     t        d   b 
+     *   /    /           =>    / \            
+     *  x    c            =>   l   c           
+     *
+     *      t -> r    =>       ( a )
+     *     /    / \   =>      /     \
+     *    /    a   b  =>     t       r -> b
+     *   /    / \     =>    / \     /    
+     *  x    c   d    =>   l   c   d
+     *
+     *  Only Level of r differs, depending on whether a is single or double.
+     *  Node 'r' must be split, as node 'b' might be double.
+     */
+    const a = t.right!.left!;
+    const n = isSingle(a) ? a.level : a.level + 1;
+    return {
+      key: a.key,
+      left: { ...t, level: a.level, right: a.left },
+      level: a.level + 1,
+      right: split({
+        level: n,
+        left: a.right,
+        right: t.right!.right,
+        key: t.right!.key,
+      }),
+    };
+  }
+  throw Error("not reached");
+}
+
+
+function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } {
+  if (!t.right) {
+    return { key: t.key, tree: t.left };
+  }
+  const d = treeDeleteLargest(t.right);
+  return {
+    key: d.key,
+    tree: adjust({ ...t, right: d.tree}),
+  };
+}
+
+
+/**
+ * Count the number of elements stored in the tree.
+ */
+export function treeSize(t: AATree): number {
+  if (!t) {
+    return 0;
+  }
+  return treeSize(t.left) + treeSize(t.right) + 1;
+}
+
+
+/**
+ * Get an array of (sorted) keys from an AA tree.
+ */
+export function treeToArray(t: AATree, accum: any[] = []) {
+  if (!t) {
+    return accum;
+  }
+  treeToArray(t.left, accum);
+  accum.push(t.key);
+  treeToArray(t.right, accum);
+  return accum;
+}
+
+
+/**
+ * Check if a key can be found in a tree.
+ */
+export function treeFind(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): boolean {
+  if (!t) {
+    return false;
+  }
+  const cmp = cmpFn(k, t.key);
+  if (cmp < 0) {
+    return treeFind(t.left, k, cmpFn);
+  }
+  if (cmp > 0) {
+    return treeFind(t.right, k, cmpFn);
+  }
+  return true;
+}
+
+
+/**
+ * Get the largest key in the tree.
+ */
+export function treeBiggest(t: AATree): any {
+  if (!t) {
+    return undefined;
+  }
+  if (!t.right) {
+    return t.key;
+  }
+  return treeBiggest(t);
+}
+
+
+/**
+ * Get the smallest key in the tree.
+ */
+export function treeSmallest(t: AATree): any {
+  if (!t) {
+    return undefined;
+  }
+  if (!t.left) {
+    return t.key;
+  }
+  return treeSmallest(t);
+}
+
+
+/**
+ * Get the smallest key from the tree that is larger than the given key.
+ * Returns 'undefined' if the given key is the largest key.
+ */
+export function treeNextKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any {
+  if (!t) {
+    return undefined;
+  }
+  const cmp = cmpFn(k, t.key);
+  if (cmp === 0) {
+    return treeSmallest(t.right);
+  }
+  if (cmp < 0) {
+    const r = treeNextKey(t.left, k, cmpFn);
+    if (r) {
+      return r;
+    }
+    return t.key;
+  }
+  if (cmp < 0) {
+    return treeNextKey(t.right, k, cmpFn);
+  }
+}
+
+
+/**
+ * Get the largest tree from the tree that is smaller than the given key.
+ * Returns 'undefined' if the given key is the smallest key.
+ */
+export function treePreviousKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any {
+  return treeNextKey(t, k, (k1, k2) => -cmpFn(k1, k2));
+}
+
+
+/**
+ * Returns a new tree without the given key.
+ */
+export function treeDelete(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATree {
+  if (!t) {
+    return t;
+  }
+  const cmp = cmpFn(k, t.key);
+  if (cmp === 0) {
+    if (!t.left) {
+      return t.right;
+    }
+    if (!t.right) {
+      return t.left;
+    }
+    const d = treeDeleteLargest(t.left);
+    return adjust({
+      key: d.key,
+      left: d.tree,
+      right: t.right,
+      level: t.level,
+    });
+  }
+  if (cmp < 0) {
+    return adjust({ ...t, left: treeDelete(t.left, k, cmpFn) });
+  }
+  if (cmp > 0) {
+    return adjust({ ...t, right: treeDelete(t.right, k, cmpFn) });
+  }
+  throw Error("not reached");
+}
diff --git a/src/memidb-test.ts b/src/memidb/memidb-test.ts
index 8f8498a6e..8f8498a6e 100644
--- a/src/memidb-test.ts
+++ b/src/memidb/memidb-test.ts
diff --git a/src/memidb.ts b/src/memidb/memidb.ts
index 3348d97a7..4ad3a01b9 100644
--- a/src/memidb.ts
+++ b/src/memidb/memidb.ts
@@ -86,133 +86,6 @@ class MyDomStringList extends Array<string> implements DOMStringList {
 
 
 
-interface AATreeNode {
-  left?: AATreeNode;
-  right?: AATreeNode;
-  level: number;
-  key: any;
-}
-
-export type AATree = AATreeNode | undefined;
-
-
-function skew(t: AATreeNode) {
-  if (t.left && t.left.level == t.level) {
-    return {
-      left: t.left.left,
-      right: t,
-      key: t.left.key,
-      level: t.level,
-    };
-  }
-  return t;
-}
-
-
-function split(t: AATreeNode) {
-  if (t.right && t.right.right && 
-      t.level == t.right.level &&
-      t.right.level == t.right.right.level) {
-    return {
-      level: t.level + 1,
-      key: t.right.key,
-      left: {
-        level: t.level,
-        key: t.key,
-        left: t.left,
-        right: t.right.left,
-      },
-      right: {
-        key: t.right.right.key,
-        left: t.right.right.left,
-        level: t.level,
-        right: t.right.right.right,
-      },
-    }
-  }
-  return t;
-}
-
-/**
- * Non-destructively insert a new key into an AA tree.
- */
-export function treeInsert(t: AATree, k: any): AATreeNode {
-  if (!t) {
-    return {
-      level: 0,
-      key: k,
-    }
-  }
-  const cmp = compareKeys(k, t.key);
-  if (cmp == 0) {
-    return t;
-  }
-  let r = Object.assign({}, t);
-  if (cmp == -1) {
-    r.left = treeInsert(t.left, k);
-  } else {
-    r.right = treeInsert(t.right, k);
-  }
-  return split(skew(r));
-}
-
-
-/**
- * Check AA tree invariants.  Useful for testing.
- */
-export function checkInvariants(t: AATree): boolean {
-  if (!t) {
-    return true;
-  }
-  throw Error("not implemented");
-}
-
-
-function adjust(t: AATreeNode): AATreeNode {
-  throw Error("not implemented");
-}
-
-function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } {
-  if (!t.right) {
-    return { key: t.key, tree: t.left };
-  }
-  const d = treeDeleteLargest(t.right);
-  return {
-    key: d.key,
-    tree: adjust({
-      level: t.level,
-      key: t.key,
-      left: t.left,
-      right: d.tree,
-    }),
-  };
-}
-
-
-//function treeDelete(t: AATree, k: any): AATreeNode {
-//  if (!t) {
-//    return t;
-//  }
-//  const cmp = compareKeys(k, t.key);
-//  if (cmp == 0) {
-//    if (!t.left) {
-//      return t.right;
-//    }
-//    if (!t.right) {
-//      return t.left;
-//    }
-//    const d = treeDeleteLargest(t.left);
-//    return adjust({
-//      key: d.key,
-//      left: d.tree,
-//      right: t.right,
-//      level: t.level,
-//    });
-//  } else {
-//  }
-//}
-
-
 
 class MyKeyRange implements IDBKeyRange {
   static only(value: any): IDBKeyRange {
@@ -246,7 +119,7 @@ export function isKeyRange(obj: any): obj is IDBKeyRange {
 }
 
 
-function compareKeys(a: any, b: any): -1|0|1 {
+export function compareKeys(a: any, b: any): -1|0|1 {
   throw Error("not implemented")
 }
 
@@ -305,6 +178,8 @@ class MyRequest implements IDBRequest {
   done: boolean = false;
   _result: any;
 
+  _source: (IDBObjectStore | IDBIndex | IDBCursor | null) = null;
+
   constructor(public _transaction: Transaction, public runner: () => void) {
   }
 
@@ -329,7 +204,7 @@ class MyRequest implements IDBRequest {
   get source() {
     // buggy type definitions don't allow null even though it's in
     // the spec.
-    return (null as any) as (IDBObjectStore | IDBIndex | IDBCursor);
+    return this._source as (IDBObjectStore | IDBIndex | IDBCursor);
   }
 
   get transaction() {
@@ -536,7 +411,7 @@ class MyObjectStore implements IDBObjectStore  {
     }
 
     const req = new MyRequest(this.transaction, () => {
-      req.source = this;
+      req._source = this;
       store.objects[stringKey] = value;
     });
     return req;
@@ -563,8 +438,8 @@ class MyObjectStore implements IDBObjectStore  {
     const store = this.transaction.transactionDbData.stores[this.storeName];
     const stringKey = stringifyKey(key);
     const req = new MyRequest(this.transaction, () => {
-      req.source = this;
-      delete store.objects[stringifyKey];
+      req._source = this;
+      delete store.objects[stringKey];
     });
     return req;
   }
@@ -582,8 +457,8 @@ class MyObjectStore implements IDBObjectStore  {
     const store = this.transaction.transactionDbData.stores[this.storeName];
     const stringKey = stringifyKey(key);
     const req = new MyRequest(this.transaction, () => {
-      req.source = this;
-      req.result = store.objects[stringKey];
+      req._source = this;
+      req._result = store.objects[stringKey];
     });
     return req;
   }
diff --git a/tsconfig.json b/tsconfig.json
index 349b5969a..876cd1cfb 100644
--- a/tsconfig.json
+++ b/tsconfig.json
@@ -42,8 +42,10 @@
     "src/libtoolVersion-test.ts",
     "src/libtoolVersion.ts",
     "src/logging.ts",
-    "src/memidb-test.ts",
-    "src/memidb.ts",
+    "src/memidb/aatree-test.ts",
+    "src/memidb/aatree.ts",
+    "src/memidb/memidb-test.ts",
+    "src/memidb/memidb.ts",
     "src/query.ts",
     "src/timer.ts",
     "src/types-test.ts",
diff --git a/web-common b/web-common
-Subproject a8bff2e27b89feb3696cf0e3a49fc00155d92de
+Subproject ebf2b43fb00f057643d69abf34b54a1b6087dfc