New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@calcit/ternary-tree

Package Overview
Dependencies
Maintainers
1
Versions
33
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@calcit/ternary-tree - npm Package Compare versions

Comparing version 0.0.2-a4 to 0.0.3-a1

4

lib/list.d.ts
import { RefInt, TernaryTreeList } from "./types";
export declare function getDepth<T>(tree: TernaryTreeList<T>): number;
export declare function decideParentDepth<T>(...xs: Array<TernaryTreeList<T>>): number;
export declare function initTernaryTreeListIter<T>(size: number, offset: number, xs: Array<TernaryTreeList<T>>): TernaryTreeList<T>;
export declare function makeTernaryTreeList<T>(size: number, offset: number, xs: Array<TernaryTreeList<T>>): TernaryTreeList<T>;
export declare function initTernaryTreeList<T>(xs: Array<T>): TernaryTreeList<T>;

@@ -20,3 +20,3 @@ export declare function initEmptyTernaryTreeList<T>(): TernaryTreeList<T>;

export declare function listPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]>;
export declare function loopGetList<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T;
export declare function listGet<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T;
export declare function first<T>(tree: TernaryTreeList<T>): T;

@@ -23,0 +23,0 @@ export declare function last<T>(tree: TernaryTreeList<T>): T;

65

lib/list.js

@@ -17,3 +17,3 @@ import { TernaryTreeKind } from "./types";

export function decideParentDepth(...xs) {
var depth = 0;
let depth = 0;
for (let x of xs) {

@@ -27,3 +27,3 @@ let y = getDepth(x);

}
export function initTernaryTreeListIter(size, offset, xs) {
export function makeTernaryTreeList(size, offset, xs) {
switch (size) {

@@ -64,5 +64,5 @@ case 0: {

let divided = divideTernarySizes(size);
let left = initTernaryTreeListIter(divided.left, offset, xs);
let middle = initTernaryTreeListIter(divided.middle, offset + divided.left, xs);
let right = initTernaryTreeListIter(divided.right, offset + divided.left + divided.middle, xs);
let left = makeTernaryTreeList(divided.left, offset, xs);
let middle = makeTernaryTreeList(divided.middle, offset + divided.left, xs);
let right = makeTernaryTreeList(divided.right, offset + divided.left + divided.middle, xs);
let result = {

@@ -81,3 +81,3 @@ kind: TernaryTreeKind.ternaryTreeBranch,

export function initTernaryTreeList(xs) {
var ys = new Array(xs.length);
let ys = new Array(xs.length);
for (let idx in xs) {

@@ -87,3 +87,3 @@ let x = xs[idx];

}
return initTernaryTreeListIter(xs.length, 0, ys);
return makeTernaryTreeList(xs.length, 0, ys);
}

@@ -149,4 +149,4 @@ export function initEmptyTernaryTreeList() {

export function listToSeq(tree) {
var acc = new Array(listLen(tree));
var counter = { value: 0 };
let acc = new Array(listLen(tree));
let counter = { value: 0 };
counter.value = 0;

@@ -270,4 +270,4 @@ writeSeq(tree, acc, counter);

export function toLeavesSeq(tree) {
var acc = new Array(listLen(tree));
var counter = { value: 0 };
let acc = new Array(listLen(tree));
let counter = { value: 0 };
writeLeavesSeq(tree, acc, counter);

@@ -282,3 +282,3 @@ return acc;

for (let idx = 0; idx < listLen(tree); idx++) {
yield loopGetList(tree, idx);
yield listGet(tree, idx);
}

@@ -293,5 +293,5 @@ }

}
export function loopGetList(originalTree, originalIdx) {
var tree = originalTree;
var idx = originalIdx;
export function listGet(originalTree, originalIdx) {
let tree = originalTree;
let idx = originalIdx;
while (tree != null) {

@@ -306,3 +306,3 @@ if (idx < 0) {

else {
throw new Error("Cannot get from leaf with index {idx}");
throw new Error(`Cannot get from leaf with index ${idx}`);
}

@@ -331,7 +331,7 @@ }

}
throw new Error("Failed to get {idx}");
throw new Error(`Failed to get ${idx}`);
}
export function first(tree) {
if (listLen(tree) > 0) {
return loopGetList(tree, 0);
return listGet(tree, 0);
}

@@ -344,3 +344,3 @@ else {

if (listLen(tree) > 0) {
return loopGetList(tree, listLen(tree) - 1);
return listGet(tree, listLen(tree) - 1);
}

@@ -363,3 +363,3 @@ else {

else {
throw new Error("Cannot get from leaf with index {idx}");
throw new Error(`Cannot get from leaf with index ${idx}`);
}

@@ -414,3 +414,3 @@ }

if (idx < 0) {
throw new Error("Index is negative {idx}");
throw new Error(`Index is negative ${idx}`);
}

@@ -421,3 +421,3 @@ if (listLen(tree) === 0) {

if (idx > listLen(tree) - 1) {
throw new Error("Index too large {idx}");
throw new Error(`Index too large ${idx}`);
}

@@ -492,3 +492,3 @@ if (listLen(tree) === 1) {

size: 1,
value: loopGetList(result, 0),
value: listGet(result, 0),
};

@@ -722,3 +722,3 @@ }

else {
throw new Error("Unexpected idx: {idx}");
throw new Error(`Unexpected idx: ${idx}`);
}

@@ -750,3 +750,3 @@ }

else {
throw new Error("Unexpected idx: {idx}");
throw new Error(`Unexpected idx: ${idx}`);
}

@@ -858,4 +858,4 @@ }

// echo "Force inplace balancing case list: ", tree.size
var ys = toLeavesSeq(tree);
let newTree = initTernaryTreeListIter(ys.length, 0, ys);
let ys = toLeavesSeq(tree);
let newTree = makeTernaryTreeList(ys.length, 0, ys);
// let newTree = initTernaryTreeList(ys)

@@ -961,3 +961,3 @@ tree.left = newTree.left;

for (let idx = 0; idx < listLen(xs); idx++) {
if (!dataEqual(loopGetList(xs, idx), loopGetList(ys, idx))) {
if (!dataEqual(listGet(xs, idx), listGet(ys, idx))) {
return false;

@@ -1025,7 +1025,9 @@ }

// echo "sizes: {leftSize} {middleSize} {rightSize}"
if (startIdx >= leftSize + middleSize)
if (startIdx >= leftSize + middleSize) {
return slice(tree.right, startIdx - leftSize - middleSize, endIdx - leftSize - middleSize);
}
if (startIdx >= leftSize)
if (endIdx <= leftSize + middleSize)
if (endIdx <= leftSize + middleSize) {
return slice(tree.middle, startIdx - leftSize, endIdx - leftSize);
}
else {

@@ -1036,4 +1038,5 @@ let middleCut = slice(tree.middle, startIdx - leftSize, middleSize);

}
if (endIdx <= leftSize)
if (endIdx <= leftSize) {
return slice(tree.left, startIdx, endIdx);
}
if (endIdx <= leftSize + middleSize) {

@@ -1040,0 +1043,0 @@ let leftCut = slice(tree.left, startIdx, leftSize);

4

lib/main.js

@@ -8,3 +8,3 @@ import { deepEqual, overwriteComparator } from "./utils";

overwriteComparator((x, y) => {
console.log("comparing", x, y);
// console.log("comparing", x, y);
return deepEqual(x, y);

@@ -14,3 +14,3 @@ });

let ret = mergeValueHash(10, valueHash(x));
console.log("hashing", x, ret);
// console.log("hashing", x, ret);
return ret;

@@ -17,0 +17,0 @@ });

7

lib/map.d.ts

@@ -1,2 +0,2 @@

import { TernaryTreeMap, TernaryTreeMapKeyValuePair, RefInt, Option } from "./types";
import { TernaryTreeMap, TernaryTreeMapKeyValuePair, Option } from "./types";
export declare type TernaryTreeMapKeyValuePairOfLeaf<K, V> = {

@@ -13,6 +13,5 @@ k: K;

export declare function isMapEmpty<K, V>(tree: TernaryTreeMap<K, V>): boolean;
export declare function toHashSortedSeq<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]>;
export declare function collectHashSortedSeqOfLeaf<K, T>(tree: TernaryTreeMap<K, T>, acc: Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>, idx: RefInt): void;
export declare function toHashSortedPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]>;
export declare function contains<K, T>(tree: TernaryTreeMap<K, T>, item: K): boolean;
export declare function mapLoopGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T>;
export declare function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T>;
export declare function checkMapStructure<K, V>(tree: TernaryTreeMap<K, V>): boolean;

@@ -19,0 +18,0 @@ export declare function assocExisted<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T): TernaryTreeMap<K, T>;

185

lib/map.js

@@ -62,3 +62,3 @@ import { TernaryTreeKind, some, none, hashGenerator, } from "./types";

// pairs must be sorted before passing to proc.
function initTernaryTreeMapIterator(size, offset, xs) {
function makeTernaryTreeMap(size, offset, xs) {
switch (size) {

@@ -122,5 +122,5 @@ case 0: {

let divided = divideTernarySizes(size);
let left = initTernaryTreeMapIterator(divided.left, offset, xs);
let middle = initTernaryTreeMapIterator(divided.middle, offset + divided.left, xs);
let right = initTernaryTreeMapIterator(divided.right, offset + divided.left + divided.middle, xs);
let left = makeTernaryTreeMap(divided.left, offset, xs);
let middle = makeTernaryTreeMap(divided.middle, offset + divided.left, xs);
let right = makeTernaryTreeMap(divided.right, offset + divided.left + divided.middle, xs);
let result = {

@@ -143,7 +143,7 @@ kind: TernaryTreeKind.ternaryTreeBranch,

});
return initTernaryTreeMapIterator(leavesList.length, 0, leavesList);
return makeTernaryTreeMap(leavesList.length, 0, leavesList);
}
export function initTernaryTreeMap(t) {
var xs = new Array(t.size);
var idx = 0;
let xs = new Array(t.size);
let idx = 0;
for (let [k, v] of t) {

@@ -248,9 +248,9 @@ xs[idx] = { k, v };

// sorted by hash(tree.key)
export function toHashSortedSeq(tree) {
var acc = new Array(mapLen(tree));
var idx = { value: 0 };
export function toHashSortedPairs(tree) {
let acc = new Array(mapLen(tree));
let idx = { value: 0 };
collectHashSortedSeq(tree, acc, idx);
return acc;
}
export function collectHashSortedSeqOfLeaf(tree, acc, idx) {
function collectHashSortedSeqOfLeaf(tree, acc, idx) {
if (tree == null || isMapEmpty(tree)) {

@@ -285,5 +285,6 @@ // discard

}
// TODO index items with hash, rather than only key/value's
// for reusing leaves during rebalancing
function toHashSortedSeqOfLeaves(tree) {
var acc = new Array(mapLen(tree));
let acc = new Array(mapLen(tree));
let idx = { value: 0 };

@@ -297,4 +298,9 @@ collectHashSortedSeqOfLeaf(tree, acc, idx);

}
let hx = hashGenerator(item);
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
if (hx !== tree.hash) {
throw new Error("Expected hashes to be identical");
}
for (let idx in tree.elements) {
let pair = tree.elements[idx];
if (dataEqual(pair.k, item)) {

@@ -306,41 +312,21 @@ return true;

}
let hx = hashGenerator(item);
// echo "looking for: ", hx, " ", item, " in ", tree.formatInline(true)
if (tree.left != null) {
if (tree.left.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
return true;
for (let branch of [tree.left, tree.middle, tree.right]) {
if (branch != null) {
if (branch.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (branch.hash === hx) {
return true;
}
}
}
else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
return contains(tree.left, item); // TODO
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
return true;
else if (hx >= branch.minHash && hx <= branch.maxHash) {
return contains(branch, item); // TODO
}
}
else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
return contains(tree.middle, item);
}
}
if (tree.right != null) {
// echo "right..."
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
return true;
}
}
else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
return contains(tree.right, item); // TODO
}
}
return false;
}
export function mapLoopGet(originalTree, item) {
export function mapGet(originalTree, item) {
let hx = hashGenerator(item);
var tree = originalTree;
while (tree != null) {
let tree = originalTree;
whileLoop: while (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {

@@ -355,50 +341,20 @@ for (let pair of tree.elements) {

// echo "looking for: ", hx, " ", item, " in ", tree.formatInline
if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
for (let pair of tree.left.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
for (let branch of [tree.left, tree.middle, tree.right]) {
if (branch != null) {
if (branch.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (branch.hash === hx) {
for (let pair of branch.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
}
return none();
}
}
else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
tree = tree.left;
continue;
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
for (let pair of tree.middle.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
else if (hx >= branch.minHash && hx <= branch.maxHash) {
tree = branch;
continue whileLoop; // notice, it jumps to while loop
}
}
else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
tree = tree.middle;
continue;
}
}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
for (let pair of tree.right.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
}
}
else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
tree = tree.right;
continue;
}
}
return none();

@@ -467,4 +423,7 @@ }

if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
var newPairs = new Array(tree.elements.length);
var replaced = false;
if (tree.hash !== thisHash) {
throw new Error("Expected hashes to be identical");
}
let newPairs = new Array(tree.elements.length);
let replaced = false;
for (let idx in tree.elements) {

@@ -550,3 +509,3 @@ let pair = tree.elements[idx];

}
var newPairs = new Array(tree.elements.length + 1);
let newPairs = new Array(tree.elements.length + 1);
for (let idx in tree.elements) {

@@ -833,3 +792,3 @@ let pair = tree.elements[idx];

if (tree.hash === hashGenerator(key)) {
var newPairs = [];
let newPairs = [];
for (let pair of tree.elements) {

@@ -861,3 +820,3 @@ if (!dataEqual(pair.k, key)) {

let changedBranch = dissocExisted(tree.left, key);
var minHash;
let minHash;
if (changedBranch != null) {

@@ -898,3 +857,3 @@ minHash = getMin(changedBranch);

let changedBranch = dissocExisted(tree.right, key);
var maxHash;
let maxHash;
if (changedBranch != null) {

@@ -956,11 +915,7 @@ maxHash = getMax(changedBranch);

else {
for (let item of toPairs(tree.left)) {
result.push(item);
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
result.push(item);
}
}
for (let item of toPairs(tree.middle)) {
result.push(item);
}
for (let item of toPairs(tree.right)) {
result.push(item);
}
}

@@ -970,3 +925,3 @@ return result;

export function* toPairsIterator(tree) {
let seqItems = toHashSortedSeq(tree);
let seqItems = toHashSortedPairs(tree);
for (let item of seqItems) {

@@ -987,11 +942,7 @@ yield item;

else {
for (let item of mapKeys(tree.left)) {
result.push(item);
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of mapKeys(branch)) {
result.push(item);
}
}
for (let item of mapKeys(tree.middle)) {
result.push(item);
}
for (let item of mapKeys(tree.right)) {
result.push(item);
}
}

@@ -1021,4 +972,4 @@ return result;

for (let key of keys) {
let vx = mapLoopGet(xs, key);
let vy = mapLoopGet(ys, key);
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
if (vx.existed !== vy.existed) {

@@ -1035,4 +986,4 @@ return false;

export function merge(xs, ys) {
var ret = xs;
var counted = 0;
let ret = xs;
let counted = 0;
mapEach(ys, (key, item) => {

@@ -1053,4 +1004,4 @@ ret = assocMap(ret, key, item);

export function mergeSkip(xs, ys, skipped) {
var ret = xs;
var counted = 0;
let ret = xs;
let counted = 0;
mapEach(ys, (key, item) => {

@@ -1076,4 +1027,4 @@ if (dataEqual(item, skipped)) {

if (tree.kind === TernaryTreeKind.ternaryTreeBranch) {
var xs = toHashSortedSeqOfLeaves(tree);
let newTree = initTernaryTreeMapIterator(xs.length, 0, xs);
let xs = toHashSortedSeqOfLeaves(tree);
let newTree = makeTernaryTreeMap(xs.length, 0, xs);
tree.left = newTree.left;

@@ -1080,0 +1031,0 @@ tree.middle = newTree.middle;

8

lib/test-list.js

@@ -1,2 +0,2 @@

import { listToString, initTernaryTreeList, listEach, indexOf, findIndex, reverse, checkListStructure, listToSeq, slice, listPairs, listItems, formatListInline, sameListShape, assocBefore, concat, assocAfter, prepend, append, rest, butlast, first, assocList, dissocList, loopGetList, insert, initEmptyTernaryTreeList, last, listLen, forceListInplaceBalancing, listEqual, } from "./list";
import { listToString, initTernaryTreeList, listEach, indexOf, findIndex, reverse, checkListStructure, listToSeq, slice, listPairs, listItems, formatListInline, sameListShape, assocBefore, concat, assocAfter, prepend, append, rest, butlast, first, assocList, dissocList, listGet, insert, initEmptyTernaryTreeList, last, listLen, forceListInplaceBalancing, listEqual, } from "./list";
import { test, check, arrayEqual } from "./utils";

@@ -19,3 +19,3 @@ export let runListTests = () => {

for (let idx = 0; idx < origin11.length; idx++) {
check(origin11[idx] == loopGetList(data11, idx));
check(origin11[idx] == listGet(data11, idx));
}

@@ -28,4 +28,4 @@ check(first(data11) == 1);

let updated = assocList(data5, 3, 10);
check(loopGetList(updated, 3) == 10);
check(loopGetList(data5, 3) == 4);
check(listGet(updated, 3) == 10);
check(listGet(data5, 3) == 4);
check(listLen(updated) == listLen(data5));

@@ -32,0 +32,0 @@ for (let idx = 0; idx < listLen(data5); idx++) {

16

lib/test-map.js
import { some, none, hashGenerator } from "./types";
import { test, check, cmp, deepEqual, justDisplay } from "./utils";
import { initTernaryTreeMap, mapKeys, toHashSortedSeq, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, mapLoopGet, toPairsIterator, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEach, mapEqual, } from "./map";
import { initTernaryTreeMap, mapKeys, toHashSortedPairs, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, mapGet, toPairsIterator, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEach, mapEqual, } from "./map";
export let runMapTests = () => {

@@ -21,7 +21,7 @@ test("init map", () => {

justDisplay(formatMapInline(data10), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (_ 1:11 _)) (8:18 0:10 4:14))");
check(deepEqual(toHashSortedSeq(data10), inList));
check(deepEqual(toHashSortedPairs(data10), inList));
check(contains(data10, "1") == true);
check(contains(data10, "11") == false);
check(deepEqual(mapLoopGet(data10, "1"), some(11)));
check(deepEqual(mapLoopGet(data10, "11"), none()));
check(deepEqual(mapGet(data10, "1"), some(11)));
check(deepEqual(mapGet(data10, "11"), none()));
let emptyData = new Map();

@@ -126,6 +126,6 @@ check(mapEqual(initEmptyTernaryTreeMap(), initTernaryTreeMap(emptyData)));

let c = mergeSkip(a, b, 11);
check(deepEqual(mapLoopGet(c, "0"), some(10)));
check(deepEqual(mapLoopGet(c, "1"), some(12)));
check(deepEqual(mapLoopGet(c, "2"), some(13)));
check(deepEqual(mapLoopGet(c, "3"), some(14)));
check(deepEqual(mapGet(c, "0"), some(10)));
check(deepEqual(mapGet(c, "1"), some(12)));
check(deepEqual(mapGet(c, "2"), some(13)));
check(deepEqual(mapGet(c, "3"), some(14)));
});

@@ -132,0 +132,0 @@ test("iterator", () => {

2

package.json
{
"name": "@calcit/ternary-tree",
"version": "0.0.2-a4",
"version": "0.0.3-a1",
"main": "./lib/index.js",

@@ -5,0 +5,0 @@ "devDependencies": {

69

src/list.ts

@@ -19,3 +19,3 @@ import { RefInt, TernaryTreeKind, TernaryTreeList, TernaryTreeListTheBranch } from "./types";

export function decideParentDepth<T>(...xs: Array<TernaryTreeList<T>>): number {
var depth = 0;
let depth = 0;
for (let x of xs) {

@@ -30,3 +30,3 @@ let y = getDepth(x);

export function initTernaryTreeListIter<T>(size: number, offset: number, xs: /* var */ Array<TernaryTreeList<T>>): TernaryTreeList<T> {
export function makeTernaryTreeList<T>(size: number, offset: number, xs: /* var */ Array<TernaryTreeList<T>>): TernaryTreeList<T> {
switch (size) {

@@ -68,5 +68,5 @@ case 0: {

let left = initTernaryTreeListIter(divided.left, offset, xs);
let middle = initTernaryTreeListIter(divided.middle, offset + divided.left, xs);
let right = initTernaryTreeListIter(divided.right, offset + divided.left + divided.middle, xs);
let left = makeTernaryTreeList(divided.left, offset, xs);
let middle = makeTernaryTreeList(divided.middle, offset + divided.left, xs);
let right = makeTernaryTreeList(divided.right, offset + divided.left + divided.middle, xs);
let result: TernaryTreeList<T> = {

@@ -86,3 +86,3 @@ kind: TernaryTreeKind.ternaryTreeBranch,

export function initTernaryTreeList<T>(xs: Array<T>): TernaryTreeList<T> {
var ys = new Array<TernaryTreeList<T>>(xs.length);
let ys = new Array<TernaryTreeList<T>>(xs.length);
for (let idx in xs) {

@@ -92,3 +92,3 @@ let x = xs[idx];

}
return initTernaryTreeListIter(xs.length, 0, ys);
return makeTernaryTreeList(xs.length, 0, ys);
}

@@ -160,4 +160,4 @@

export function listToSeq<T>(tree: TernaryTreeList<T>): Array<T> {
var acc = new Array<T>(listLen(tree));
var counter: RefInt = { value: 0 };
let acc = new Array<T>(listLen(tree));
let counter: RefInt = { value: 0 };
counter.value = 0;

@@ -283,4 +283,4 @@ writeSeq(tree, acc, counter);

export function toLeavesSeq<T>(tree: TernaryTreeList<T>): Array<TernaryTreeList<T>> {
var acc = new Array<TernaryTreeList<T>>(listLen(tree));
var counter: RefInt = { value: 0 };
let acc = new Array<TernaryTreeList<T>>(listLen(tree));
let counter: RefInt = { value: 0 };
writeLeavesSeq(tree, acc, counter);

@@ -298,3 +298,3 @@ return acc;

for (let idx = 0; idx < listLen(tree); idx++) {
yield loopGetList(tree, idx);
yield listGet(tree, idx);
}

@@ -312,5 +312,5 @@ }

export function loopGetList<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T {
var tree = originalTree;
var idx = originalIdx;
export function listGet<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T {
let tree = originalTree;
let idx = originalIdx;
while (tree != null) {

@@ -325,3 +325,3 @@ if (idx < 0) {

} else {
throw new Error("Cannot get from leaf with index {idx}");
throw new Error(`Cannot get from leaf with index ${idx}`);
}

@@ -353,3 +353,3 @@ }

throw new Error("Failed to get {idx}");
throw new Error(`Failed to get ${idx}`);
}

@@ -359,3 +359,3 @@

if (listLen(tree) > 0) {
return loopGetList(tree, 0);
return listGet(tree, 0);
} else {

@@ -368,3 +368,3 @@ throw new Error("Cannot get from empty list");

if (listLen(tree) > 0) {
return loopGetList(tree, listLen(tree) - 1);
return listGet(tree, listLen(tree) - 1);
} else {

@@ -387,3 +387,3 @@ throw new Error("Cannot get from empty list");

} else {
throw new Error("Cannot get from leaf with index {idx}");
throw new Error(`Cannot get from leaf with index ${idx}`);
}

@@ -440,3 +440,3 @@ }

if (idx < 0) {
throw new Error("Index is negative {idx}");
throw new Error(`Index is negative ${idx}`);
}

@@ -449,3 +449,3 @@

if (idx > listLen(tree) - 1) {
throw new Error("Index too large {idx}");
throw new Error(`Index too large ${idx}`);
}

@@ -524,3 +524,3 @@

size: 1,
value: loopGetList(result, 0),
value: listGet(result, 0),
};

@@ -747,3 +747,3 @@ }

} else {
throw new Error("Unexpected idx: {idx}");
throw new Error(`Unexpected idx: ${idx}`);
}

@@ -772,3 +772,3 @@ } else {

} else {
throw new Error("Unexpected idx: {idx}");
throw new Error(`Unexpected idx: ${idx}`);
}

@@ -893,4 +893,4 @@ }

// echo "Force inplace balancing case list: ", tree.size
var ys = toLeavesSeq(tree);
let newTree = initTernaryTreeListIter(ys.length, 0, ys) as TernaryTreeListTheBranch<T>;
let ys = toLeavesSeq(tree);
let newTree = makeTernaryTreeList(ys.length, 0, ys) as TernaryTreeListTheBranch<T>;
// let newTree = initTernaryTreeList(ys)

@@ -1004,3 +1004,3 @@ tree.left = newTree.left;

for (let idx = 0; idx < listLen(xs); idx++) {
if (!dataEqual(loopGetList(xs, idx), loopGetList(ys, idx))) {
if (!dataEqual(listGet(xs, idx), listGet(ys, idx))) {
return false;

@@ -1077,6 +1077,9 @@ }

if (startIdx >= leftSize + middleSize) return slice(tree.right, startIdx - leftSize - middleSize, endIdx - leftSize - middleSize);
if (startIdx >= leftSize + middleSize) {
return slice(tree.right, startIdx - leftSize - middleSize, endIdx - leftSize - middleSize);
}
if (startIdx >= leftSize)
if (endIdx <= leftSize + middleSize) return slice(tree.middle, startIdx - leftSize, endIdx - leftSize);
else {
if (endIdx <= leftSize + middleSize) {
return slice(tree.middle, startIdx - leftSize, endIdx - leftSize);
} else {
let middleCut = slice(tree.middle, startIdx - leftSize, middleSize);

@@ -1087,3 +1090,5 @@ let rightCut = slice(tree.right, 0, endIdx - leftSize - middleSize);

if (endIdx <= leftSize) return slice(tree.left, startIdx, endIdx);
if (endIdx <= leftSize) {
return slice(tree.left, startIdx, endIdx);
}

@@ -1090,0 +1095,0 @@ if (endIdx <= leftSize + middleSize) {

4

src/main.ts

@@ -9,3 +9,3 @@ import { deepEqual, overwriteComparator } from "./utils";

overwriteComparator((x, y) => {
console.log("comparing", x, y);
// console.log("comparing", x, y);
return deepEqual(x, y);

@@ -16,3 +16,3 @@ });

let ret = mergeValueHash(10, valueHash(x));
console.log("hashing", x, ret);
// console.log("hashing", x, ret);
return ret;

@@ -19,0 +19,0 @@ });

190

src/map.ts

@@ -23,3 +23,3 @@ import {

function getMax<K, V>(tree: TernaryTreeMap<K, V>): number {
function getMax<K, V>(tree: TernaryTreeMap<K, V>): Hash {
if (tree == null) {

@@ -38,3 +38,3 @@ throw new Error("Cannot find max hash of nil");

function getMin<K, V>(tree: TernaryTreeMap<K, V>): number {
function getMin<K, V>(tree: TernaryTreeMap<K, V>): Hash {
if (tree == null) {

@@ -88,3 +88,3 @@ throw new Error("Cannot find min hash of nil");

// pairs must be sorted before passing to proc.
function initTernaryTreeMapIterator<K, T>(size: number, offset: number, xs: /* var */ Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>): TernaryTreeMap<K, T> {
function makeTernaryTreeMap<K, T>(size: number, offset: number, xs: /* var */ Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>): TernaryTreeMap<K, T> {
switch (size) {

@@ -149,5 +149,5 @@ case 0: {

let left = initTernaryTreeMapIterator(divided.left, offset, xs);
let middle = initTernaryTreeMapIterator(divided.middle, offset + divided.left, xs);
let right = initTernaryTreeMapIterator(divided.right, offset + divided.left + divided.middle, xs);
let left = makeTernaryTreeMap(divided.left, offset, xs);
let middle = makeTernaryTreeMap(divided.middle, offset + divided.left, xs);
let right = makeTernaryTreeMap(divided.right, offset + divided.left + divided.middle, xs);

@@ -174,9 +174,9 @@ let result: TernaryTreeMap<K, T> = {

);
return initTernaryTreeMapIterator(leavesList.length, 0, leavesList);
return makeTernaryTreeMap(leavesList.length, 0, leavesList);
}
export function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T> {
var xs = new Array<TernaryTreeMapKeyValuePair<K, T>>(t.size);
let xs = new Array<TernaryTreeMapKeyValuePair<K, T>>(t.size);
var idx = 0;
let idx = 0;
for (let [k, v] of t) {

@@ -289,5 +289,5 @@ xs[idx] = { k, v };

// sorted by hash(tree.key)
export function toHashSortedSeq<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]> {
var acc = new Array<[K, T]>(mapLen(tree));
var idx: RefInt = { value: 0 };
export function toHashSortedPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]> {
let acc = new Array<[K, T]>(mapLen(tree));
let idx: RefInt = { value: 0 };
collectHashSortedSeq(tree, acc, idx);

@@ -297,3 +297,3 @@ return acc;

export function collectHashSortedSeqOfLeaf<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>, idx: RefInt): void {
function collectHashSortedSeqOfLeaf<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>, idx: RefInt): void {
if (tree == null || isMapEmpty(tree)) {

@@ -328,5 +328,6 @@ // discard

// TODO index items with hash, rather than only key/value's
// for reusing leaves during rebalancing
function toHashSortedSeqOfLeaves<K, T>(tree: TernaryTreeMap<K, T>): Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>> {
var acc = new Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>(mapLen(tree));
let acc = new Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>(mapLen(tree));
let idx: RefInt = { value: 0 };

@@ -342,4 +343,10 @@ collectHashSortedSeqOfLeaf(tree, acc, idx);

let hx = hashGenerator(item);
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
if (hx !== tree.hash) {
throw new Error("Expected hashes to be identical");
}
for (let idx in tree.elements) {
let pair = tree.elements[idx];
if (dataEqual(pair.k, item)) {

@@ -352,44 +359,24 @@ return true;

let hx = hashGenerator(item);
// echo "looking for: ", hx, " ", item, " in ", tree.formatInline(true)
if (tree.left != null) {
if (tree.left.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
return true;
for (let branch of [tree.left, tree.middle, tree.right]) {
if (branch != null) {
if (branch.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (branch.hash === hx) {
return true;
}
} else if (hx >= branch.minHash && hx <= branch.maxHash) {
return contains(branch, item); // TODO
}
} else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
return contains(tree.left, item); // TODO
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
return true;
}
} else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
return contains(tree.middle, item);
}
}
if (tree.right != null) {
// echo "right..."
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
return true;
}
} else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
return contains(tree.right, item); // TODO
}
}
return false;
}
export function mapLoopGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T> {
export function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T> {
let hx = hashGenerator(item);
var tree = originalTree;
let tree = originalTree;
while (tree != null) {
whileLoop: while (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {

@@ -406,50 +393,20 @@ for (let pair of tree.elements) {

if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
for (let pair of tree.left.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
for (let branch of [tree.left, tree.middle, tree.right]) {
if (branch != null) {
if (branch.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (branch.hash === hx) {
for (let pair of branch.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
}
return none();
} else if (hx >= branch.minHash && hx <= branch.maxHash) {
tree = branch;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
tree = tree.left;
continue;
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
for (let pair of tree.middle.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
}
} else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
tree = tree.middle;
continue;
}
}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
for (let pair of tree.right.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
}
}
return none();
}
} else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
tree = tree.right;
continue;
}
}
return none();

@@ -525,4 +482,7 @@ }

if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
var newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length);
var replaced = false;
if (tree.hash !== thisHash) {
throw new Error("Expected hashes to be identical");
}
let newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length);
let replaced = false;
for (let idx in tree.elements) {

@@ -610,3 +570,3 @@ let pair = tree.elements[idx];

}
var newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length + 1);
let newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length + 1);
for (let idx in tree.elements) {

@@ -893,3 +853,3 @@ let pair = tree.elements[idx];

if (tree.hash === hashGenerator(key)) {
var newPairs: Array<TernaryTreeMapKeyValuePair<K, T>> = [];
let newPairs: Array<TernaryTreeMapKeyValuePair<K, T>> = [];
for (let pair of tree.elements) {

@@ -922,3 +882,3 @@ if (!dataEqual(pair.k, key)) {

let changedBranch = dissocExisted(tree.left, key);
var minHash: number;
let minHash: number;
if (changedBranch != null) {

@@ -962,3 +922,3 @@ minHash = getMin(changedBranch);

var maxHash: number;
let maxHash: number;
if (changedBranch != null) {

@@ -1020,11 +980,7 @@ maxHash = getMax(changedBranch);

} else {
for (let item of toPairs(tree.left)) {
result.push(item);
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
result.push(item);
}
}
for (let item of toPairs(tree.middle)) {
result.push(item);
}
for (let item of toPairs(tree.right)) {
result.push(item);
}
}

@@ -1036,3 +992,3 @@

export function* toPairsIterator<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]> {
let seqItems = toHashSortedSeq(tree);
let seqItems = toHashSortedPairs(tree);

@@ -1055,11 +1011,7 @@ for (let item of seqItems) {

} else {
for (let item of mapKeys(tree.left)) {
result.push(item);
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of mapKeys(branch)) {
result.push(item);
}
}
for (let item of mapKeys(tree.middle)) {
result.push(item);
}
for (let item of mapKeys(tree.right)) {
result.push(item);
}
}

@@ -1095,4 +1047,4 @@ return result;

for (let key of keys) {
let vx = mapLoopGet(xs, key);
let vy = mapLoopGet(ys, key);
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
if (vx.existed !== vy.existed) {

@@ -1111,4 +1063,4 @@ return false;

export function merge<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>): TernaryTreeMap<K, T> {
var ret = xs;
var counted = 0;
let ret = xs;
let counted = 0;
mapEach(ys, (key: K, item: T): void => {

@@ -1129,4 +1081,4 @@ ret = assocMap(ret, key, item);

export function mergeSkip<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>, skipped: T): TernaryTreeMap<K, T> {
var ret = xs;
var counted = 0;
let ret = xs;
let counted = 0;
mapEach(ys, (key: K, item: T): void => {

@@ -1152,4 +1104,4 @@ if (dataEqual(item, skipped)) {

if (tree.kind === TernaryTreeKind.ternaryTreeBranch) {
var xs = toHashSortedSeqOfLeaves(tree);
let newTree = initTernaryTreeMapIterator(xs.length, 0, xs) as TernaryTreeMapTheBranch<K, T>;
let xs = toHashSortedSeqOfLeaves(tree);
let newTree = makeTernaryTreeMap(xs.length, 0, xs) as TernaryTreeMapTheBranch<K, T>;
tree.left = newTree.left;

@@ -1156,0 +1108,0 @@ tree.middle = newTree.middle;

8

src/test-list.ts

@@ -25,3 +25,3 @@ import {

dissocList,
loopGetList,
listGet,
insert,

@@ -63,3 +63,3 @@ initEmptyTernaryTreeList,

for (let idx = 0; idx < origin11.length; idx++) {
check(origin11[idx] == loopGetList(data11, idx));
check(origin11[idx] == listGet(data11, idx));
}

@@ -74,4 +74,4 @@

let updated = assocList(data5, 3, 10);
check(loopGetList(updated, 3) == 10);
check(loopGetList(data5, 3) == 4);
check(listGet(updated, 3) == 10);
check(listGet(data5, 3) == 4);
check(listLen(updated) == listLen(data5));

@@ -78,0 +78,0 @@

18

src/test-map.ts

@@ -6,3 +6,3 @@ import { some, none, hashGenerator } from "./types";

mapKeys,
toHashSortedSeq,
toHashSortedPairs,
merge,

@@ -15,3 +15,3 @@ mergeSkip,

contains,
mapLoopGet,
mapGet,
toPairs,

@@ -49,3 +49,3 @@ toPairsIterator,

check(deepEqual(toHashSortedSeq(data10), inList));
check(deepEqual(toHashSortedPairs(data10), inList));

@@ -55,4 +55,4 @@ check(contains(data10, "1") == true);

check(deepEqual(mapLoopGet(data10, "1"), some(11)));
check(deepEqual(mapLoopGet(data10, "11"), none()));
check(deepEqual(mapGet(data10, "1"), some(11)));
check(deepEqual(mapGet(data10, "11"), none()));

@@ -187,6 +187,6 @@ let emptyData: Map<string, number> = new Map();

let c = mergeSkip(a, b, 11);
check(deepEqual(mapLoopGet(c, "0"), some(10)));
check(deepEqual(mapLoopGet(c, "1"), some(12)));
check(deepEqual(mapLoopGet(c, "2"), some(13)));
check(deepEqual(mapLoopGet(c, "3"), some(14)));
check(deepEqual(mapGet(c, "0"), some(10)));
check(deepEqual(mapGet(c, "1"), some(12)));
check(deepEqual(mapGet(c, "2"), some(13)));
check(deepEqual(mapGet(c, "3"), some(14)));
});

@@ -193,0 +193,0 @@

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc