@calcit/ternary-tree - npm Package Compare versions

Comparing version 0.0.2-a3 to 0.0.2-a4

lib/main.js

@@ -6,2 +6,3 @@ import { deepEqual, overwriteComparator } from "./utils";
 import { runMapTests } from "./test-map";
+import { mergeValueHash, overwriteHashGenerator, valueHash } from "./types";
 overwriteComparator((x, y) => {
@@ -11,3 +12,8 @@ console.log("comparing", x, y);
 });
+overwriteHashGenerator((x) => {
+    let ret = mergeValueHash(10, valueHash(x));
+    console.log("hashing", x, ret);
+    return ret;
+});
 runListTests();
 runMapTests();

lib/map.js

@@ -1,2 +0,2 @@
-import { TernaryTreeKind, some, none, valueHash, } from "./types";
+import { TernaryTreeKind, some, none, hashGenerator, } from "./types";
 import { divideTernarySizes, cmp, dataEqual } from "./utils";
@@ -47,3 +47,3 @@ let emptyBranch = null;
         kind: TernaryTreeKind.ternaryTreeLeaf,
-        hash: valueHash(k),
+        hash: hashGenerator(k),
         elements: [{ k: k, v: v }],
@@ -56,3 +56,3 @@ };
         kind: TernaryTreeKind.ternaryTreeLeaf,
-        hash: valueHash(item.k),
+        hash: hashGenerator(item.k),
         elements: [item],
@@ -80,3 +80,3 @@ };
             let middlePair = xs[offset];
-            let hashVal = valueHash(middlePair.k);
+            let hashVal = hashGenerator(middlePair.k);
             let result = {
@@ -98,4 +98,4 @@ kind: TernaryTreeKind.ternaryTreeBranch,
                 kind: TernaryTreeKind.ternaryTreeBranch,
-                maxHash: valueHash(rightPair.k),
-                minHash: valueHash(leftPair.k),
+                maxHash: hashGenerator(rightPair.k),
+                minHash: hashGenerator(leftPair.k),
                 middle: emptyBranch,
@@ -114,4 +114,4 @@ left: leftPair.v,
                 kind: TernaryTreeKind.ternaryTreeBranch,
-                maxHash: valueHash(rightPair.k),
-                minHash: valueHash(leftPair.k),
+                maxHash: hashGenerator(rightPair.k),
+                minHash: hashGenerator(leftPair.k),
                 left: leftPair.v,
@@ -156,4 +156,4 @@ middle: middlePair.v,
     let ys = xs.sort((x, y) => {
-        let hx = valueHash(x.k);
-        let hy = valueHash(y.k);
+        let hx = hashGenerator(x.k);
+        let hy = hashGenerator(y.k);
         return cmp(hx, hy);
@@ -306,3 +306,3 @@ });
     }
-    let hx = valueHash(item);
+    let hx = hashGenerator(item);
     // echo "looking for: ", hx, " ", item, " in ", tree.formatInline(true)
@@ -343,3 +343,3 @@ if (tree.left != null) {
 export function mapLoopGet(originalTree, item) {
-    let hx = valueHash(item);
+    let hx = hashGenerator(item);
     var tree = originalTree;
@@ -413,3 +413,3 @@ while (tree != null) {
         for (let pair of tree.elements) {
-            if (tree.hash !== valueHash(pair.k)) {
+            if (tree.hash !== hashGenerator(pair.k)) {
                 throw new Error(`Bad hash at leaf node ${tree}`);
@@ -466,3 +466,3 @@ }
     }
-    let thisHash = valueHash(key);
+    let thisHash = hashGenerator(key);
     if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
@@ -543,3 +543,3 @@ var newPairs = new Array(tree.elements.length);
     }
-    let thisHash = valueHash(key);
+    let thisHash = hashGenerator(key);
     if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
@@ -833,3 +833,3 @@ if (thisHash === tree.hash) {
     if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
-        if (tree.hash === valueHash(key)) {
+        if (tree.hash === hashGenerator(key)) {
             var newPairs = [];
@@ -859,3 +859,3 @@ for (let pair of tree.elements) {
     }
-    let thisHash = valueHash(key);
+    let thisHash = hashGenerator(key);
     if (rangeContainsHash(tree.left, thisHash)) {
@@ -862,0 +862,0 @@ let changedBranch = dissocExisted(tree.left, key);

lib/test-map.js

@@ -1,2 +0,2 @@
-import { some, none, valueHash } from "./types";
+import { some, none, hashGenerator } from "./types";
 import { test, check, cmp, deepEqual, justDisplay } from "./utils";
@@ -14,4 +14,4 @@ import { initTernaryTreeMap, mapKeys, toHashSortedSeq, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, mapLoopGet, toPairsIterator, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEach, mapEqual, } from "./map";
         inList.sort((x, y) => {
-            let hx = valueHash(x[0]);
-            let hy = valueHash(y[0]);
+            let hx = hashGenerator(x[0]);
+            let hy = hashGenerator(y[0]);
             return cmp(hx, hy);
@@ -18,0 +18,0 @@ });

lib/types.d.ts

@@ -48,2 +48,7 @@ export declare enum TernaryTreeKind {
 export declare type Hash = number;
-export declare let valueHash: (x: any) => number;
+export declare let valueHash: (x: any) => Hash;
+/** default hash function only handles number and string, need customization */
+export declare let hashGenerator: typeof valueHash;
+/** allow customizing hash function from outside */
+export declare let overwriteHashGenerator: (f: typeof hashGenerator) => void;
+export declare let mergeValueHash: (base: Hash, x: number | string) => Hash;

lib/types.js

@@ -21,5 +21,5 @@ export var TernaryTreeKind;
 export let valueHash = (x) => {
-    let result = 0;
     if (typeof x === "number") {
-        result = x;
+        // console.log("hash for x:", x, "\t", result);
+        return x;
     }
@@ -32,9 +32,26 @@ else if (typeof x === "string") {
         }
-        result = h;
+        // console.log("hash for x:", x, "\t", result);
+        return h;
     }
-    else {
-        throw new Error("Hash solution not provided for this type(other than number and string)");
+    throw new Error("Hash solution not provided for this type(other than number and string)");
+};
+/** default hash function only handles number and string, need customization */
+export let hashGenerator = valueHash;
+/** allow customizing hash function from outside */
+export let overwriteHashGenerator = (f) => {
+    hashGenerator = f;
+};
+export let mergeValueHash = (base, x) => {
+    if (typeof x === "number") {
+        return Math.imul(31, base) + x;
     }
-    // console.log("hash for x:", x, "\t", result);
-    return result;
+    else if (typeof x === "string") {
+        let h = base;
+        // https://gist.github.com/hyamamoto/fd435505d29ebfa3d9716fd2be8d42f0#gistcomment-2775538
+        for (var i = 0; i < x.length; i++) {
+            h = Math.imul(31, h) + (x[i].charCodeAt(0) | 0);
+        }
+        return h;
+    }
+    throw new Error("Hash solution not provided for this type(other than number and string)");
 };

package.json

 {
   "name": "@calcit/ternary-tree",
-  "version": "0.0.2-a3",
+  "version": "0.0.2-a4",
   "main": "./lib/index.js",
@@ -5,0 +5,0 @@ "devDependencies": {

src/main.ts

@@ -6,2 +6,3 @@ import { deepEqual, overwriteComparator } from "./utils";
 import { runMapTests } from "./test-map";
+import { mergeValueHash, overwriteHashGenerator, valueHash } from "./types";
 
@@ -13,3 +14,9 @@ overwriteComparator((x, y) => {
 
+overwriteHashGenerator((x) => {
+  let ret = mergeValueHash(10, valueHash(x));
+  console.log("hashing", x, ret);
+  return ret;
+});
+
 runListTests();
 runMapTests();

src/map.ts

@@ -12,3 +12,3 @@ import {
   Hash,
-  valueHash,
+  hashGenerator,
 } from "./types";
@@ -70,3 +70,3 @@ import { divideTernarySizes, roughIntPow, cmp, dataEqual } from "./utils";
     kind: TernaryTreeKind.ternaryTreeLeaf,
-    hash: valueHash(k),
+    hash: hashGenerator(k),
     elements: [{ k: k, v: v }],
@@ -80,3 +80,3 @@ };
     kind: TernaryTreeKind.ternaryTreeLeaf,
-    hash: valueHash(item.k),
+    hash: hashGenerator(item.k),
     elements: [item],
@@ -105,3 +105,3 @@ };
       let middlePair = xs[offset];
-      let hashVal = valueHash(middlePair.k);
+      let hashVal = hashGenerator(middlePair.k);
       let result: TernaryTreeMap<K, T> = {
@@ -123,4 +123,4 @@ kind: TernaryTreeKind.ternaryTreeBranch,
         kind: TernaryTreeKind.ternaryTreeBranch,
-        maxHash: valueHash(rightPair.k),
-        minHash: valueHash(leftPair.k),
+        maxHash: hashGenerator(rightPair.k),
+        minHash: hashGenerator(leftPair.k),
         middle: emptyBranch,
@@ -139,4 +139,4 @@ left: leftPair.v,
         kind: TernaryTreeKind.ternaryTreeBranch,
-        maxHash: valueHash(rightPair.k),
-        minHash: valueHash(leftPair.k),
+        maxHash: hashGenerator(rightPair.k),
+        minHash: hashGenerator(leftPair.k),
         left: leftPair.v,
@@ -189,4 +189,4 @@ middle: middlePair.v,
   let ys = xs.sort((x, y: TernaryTreeMapKeyValuePair<K, T>): number => {
-    let hx = valueHash(x.k);
-    let hy = valueHash(y.k);
+    let hx = hashGenerator(x.k);
+    let hy = hashGenerator(y.k);
     return cmp(hx, hy);
@@ -350,3 +350,3 @@ });
 
-  let hx = valueHash(item);
+  let hx = hashGenerator(item);
   // echo "looking for: ", hx, " ", item, " in ", tree.formatInline(true)
@@ -388,3 +388,3 @@ if (tree.left != null) {
 export function mapLoopGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T> {
-  let hx = valueHash(item);
+  let hx = hashGenerator(item);
 
@@ -464,3 +464,3 @@ var tree = originalTree;
     for (let pair of tree.elements) {
-      if (tree.hash !== valueHash(pair.k)) {
+      if (tree.hash !== hashGenerator(pair.k)) {
         throw new Error(`Bad hash at leaf node ${tree}`);
@@ -521,3 +521,3 @@ }
 
-  let thisHash = valueHash(key);
+  let thisHash = hashGenerator(key);
 
@@ -600,3 +600,3 @@ if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
 
-  let thisHash = valueHash(key);
+  let thisHash = hashGenerator(key);
 
@@ -891,3 +891,3 @@ if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
   if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
-    if (tree.hash === valueHash(key)) {
+    if (tree.hash === hashGenerator(key)) {
       var newPairs: Array<TernaryTreeMapKeyValuePair<K, T>> = [];
@@ -917,3 +917,3 @@ for (let pair of tree.elements) {
 
-  let thisHash = valueHash(key);
+  let thisHash = hashGenerator(key);
 
@@ -920,0 +920,0 @@ if (rangeContainsHash(tree.left, thisHash)) {

src/test-map.ts

@@ -1,2 +0,2 @@
-import { some, none, valueHash } from "./types";
+import { some, none, hashGenerator } from "./types";
 import { test, check, cmp, deepEqual, justDisplay } from "./utils";
@@ -37,4 +37,4 @@ import {
     inList.sort((x, y: [string, number]): number => {
-      let hx = valueHash(x[0]);
-      let hy = valueHash(y[0]);
+      let hx = hashGenerator(x[0]);
+      let hy = hashGenerator(y[0]);
       return cmp(hx, hy);
@@ -41,0 +41,0 @@ });

src/types.ts

@@ -72,6 +72,6 @@ export enum TernaryTreeKind {
 
-export let valueHash = (x: any): number => {
-  let result: number = 0;
+export let valueHash = (x: any): Hash => {
   if (typeof x === "number") {
-    result = x;
+    // console.log("hash for x:", x, "\t", result);
+    return x;
   } else if (typeof x === "string") {
@@ -83,8 +83,28 @@ let h = 0;
     }
-    result = h;
-  } else {
-    throw new Error("Hash solution not provided for this type(other than number and string)");
+    // console.log("hash for x:", x, "\t", result);
+    return h;
   }
-  // console.log("hash for x:", x, "\t", result);
-  return result;
+  throw new Error("Hash solution not provided for this type(other than number and string)");
 };
+
+/** default hash function only handles number and string, need customization */
+export let hashGenerator: typeof valueHash = valueHash;
+
+/** allow customizing hash function from outside */
+export let overwriteHashGenerator = (f: typeof hashGenerator) => {
+  hashGenerator = f;
+};
+
+export let mergeValueHash = (base: Hash, x: number | string): Hash => {
+  if (typeof x === "number") {
+    return Math.imul(31, base) + x;
+  } else if (typeof x === "string") {
+    let h = base;
+    // https://gist.github.com/hyamamoto/fd435505d29ebfa3d9716fd2be8d42f0#gistcomment-2775538
+    for (var i = 0; i < x.length; i++) {
+      h = Math.imul(31, h) + (x[i].charCodeAt(0) | 0);
+    }
+    return h;
+  }
+  throw new Error("Hash solution not provided for this type(other than number and string)");
+};

No alert changes

Improved metrics

Total package byte prevSize

193010

1.29%

Lines of code

5630

0.91%

No dependency changes