@calcit/ternary-tree - npm Package Compare versions

Comparing version 0.0.17 to 0.0.18

lib/map.d.ts

 import { TernaryTreeMap, TernaryTreeMapHashEntry } from "./types";
 export declare function getMapDepth<K, V>(tree: TernaryTreeMap<K, V>): number;
 export declare function initTernaryTreeMapFromHashEntries<K, T>(xs: Array<TernaryTreeMapHashEntry<K, T>>): TernaryTreeMap<K, T>;
-export declare function initTernaryTreeMap<K, T>(t: Map<K, T> | Array<[K, T]>): TernaryTreeMap<K, T>;
+export declare function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T>;
+export declare function initTernaryTreeMapFromArray<K, T>(t: Array<[K, T]>): TernaryTreeMap<K, T>;
 export declare function initEmptyTernaryTreeMap<K, T>(): TernaryTreeMap<K, T>;
@@ -6,0 +7,0 @@ export declare function mapToString<K, V>(tree: TernaryTreeMap<K, V>): string;

lib/map.js

@@ -126,2 +126,3 @@ import { TernaryTreeKind, hashGenerator } from "./types";
     let groupBuffers = new Map();
+    let xs = [];
     for (let [k, v] of t) {
@@ -139,12 +140,12 @@ let h = hashGenerator(k);
         else {
-            groupBuffers.set(h, [[k, v]]);
+            let pairs = [[k, v]];
+            groupBuffers.set(h, pairs);
+            xs.push({
+                hash: h,
+                pairs,
+            });
         }
     }
-    let xs = [];
     for (let [k, v] of groupBuffers) {
         if (v != null) {
-            xs.push({
-                hash: k,
-                pairs: v,
-            });
         }
@@ -161,2 +162,34 @@ else {
 }
+// use for..in for performance
+export function initTernaryTreeMapFromArray(t) {
+    let groupBuffers = {};
+    let xs = [];
+    for (let idx = 0; idx < t.length; idx++) {
+        let k = t[idx][0];
+        let v = t[idx][1];
+        let h = hashGenerator(k);
+        if (groupBuffers[h] != null) {
+            let branch = groupBuffers[h];
+            if (branch != null) {
+                branch.push([k, v]);
+            }
+            else {
+                throw new Error("Expected referece to pairs");
+            }
+        }
+        else {
+            let pairs = [[k, v]];
+            groupBuffers[h] = pairs;
+            xs.push({
+                hash: h,
+                pairs: pairs,
+            });
+        }
+    }
+    // MUTABLE in-place sort
+    xs.sort((a, b) => cmp(a.hash, b.hash));
+    let result = initTernaryTreeMapFromHashEntries(xs);
+    // checkMapStructure(result);
+    return result;
+}
 // for empty map
@@ -163,0 +196,0 @@ export function initEmptyTernaryTreeMap() {

lib/test-map.js

 import { hashGenerator } from "./types";
 import { test, check, cmp, deepEqual, justDisplay } from "./utils";
-import { initTernaryTreeMap, toHashSortedPairs, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, toPairs, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEqual, toKeys, toPairsArray, mapMapValues, mapGetDefault, } from "./map";
+import { initTernaryTreeMap, initTernaryTreeMapFromArray, toHashSortedPairs, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, toPairs, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEqual, toKeys, toPairsArray, mapMapValues, mapGetDefault, } from "./map";
 export let runMapTests = () => {
@@ -19,3 +19,3 @@ test("init map", () => {
         let data10 = initTernaryTreeMap(dict);
-        let data11 = initTernaryTreeMap(inList);
+        let data11 = initTernaryTreeMapFromArray(inList);
         checkMapStructure(data10);
@@ -22,0 +22,0 @@ checkMapStructure(data11);

package.json

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

src/map.ts

@@ -135,4 +135,5 @@ import { TernaryTreeMap, TernaryTreeKind, TernaryTreeMapTheLeaf, TernaryTreeMapTheBranch, RefInt, Hash, hashGenerator, TernaryTreeMapHashEntry } from "./types";
 
-export function initTernaryTreeMap<K, T>(t: Map<K, T> | Array<[K, T]>): TernaryTreeMap<K, T> {
+export function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T> {
   let groupBuffers: Map<number, Array<[K, T]>> = new Map();
+  let xs: Array<TernaryTreeMapHashEntry<K, T>> = [];
   for (let [k, v] of t) {
@@ -148,13 +149,13 @@ let h = hashGenerator(k);
     } else {
-      groupBuffers.set(h, [[k, v]]);
+      let pairs: [K, T][] = [[k, v]];
+      groupBuffers.set(h, pairs);
+      xs.push({
+        hash: h,
+        pairs,
+      });
     }
   }
 
-  let xs: Array<TernaryTreeMapHashEntry<K, T>> = [];
   for (let [k, v] of groupBuffers) {
     if (v != null) {
-      xs.push({
-        hash: k,
-        pairs: v,
-      });
     } else {
@@ -173,2 +174,35 @@ throw new Error("Expected reference to paris");
 
+// use for..in for performance
+export function initTernaryTreeMapFromArray<K, T>(t: Array<[K, T]>): TernaryTreeMap<K, T> {
+  let groupBuffers: Record<number, Array<[K, T]>> = {};
+  let xs: Array<TernaryTreeMapHashEntry<K, T>> = [];
+  for (let idx = 0; idx < t.length; idx++) {
+    let k = t[idx][0];
+    let v = t[idx][1];
+    let h = hashGenerator(k);
+    if (groupBuffers[h] != null) {
+      let branch = groupBuffers[h];
+      if (branch != null) {
+        branch.push([k, v]);
+      } else {
+        throw new Error("Expected referece to pairs");
+      }
+    } else {
+      let pairs: [K, T][] = [[k, v]];
+      groupBuffers[h] = pairs;
+      xs.push({
+        hash: h,
+        pairs: pairs,
+      });
+    }
+  }
+
+  // MUTABLE in-place sort
+  xs.sort((a, b) => cmp(a.hash, b.hash));
+
+  let result = initTernaryTreeMapFromHashEntries(xs);
+  // checkMapStructure(result);
+  return result;
+}
+
 // for empty map
@@ -175,0 +209,0 @@ export function initEmptyTernaryTreeMap<K, T>(): TernaryTreeMap<K, T> {

src/test-map.ts

@@ -5,2 +5,3 @@ import { hashGenerator } from "./types";
   initTernaryTreeMap,
+  initTernaryTreeMapFromArray,
   toHashSortedPairs,
@@ -44,3 +45,3 @@ merge,
     let data10 = initTernaryTreeMap<string, number>(dict);
-    let data11 = initTernaryTreeMap<string, number>(inList);
+    let data11 = initTernaryTreeMapFromArray<string, number>(inList);
     checkMapStructure(data10);
@@ -47,0 +48,0 @@ checkMapStructure(data11);

No alert changes

Improved metrics

Total package byte prevSize

459692

increased by0.96%

Lines of code

8838

increased by1.16%

No dependency changes