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.13 to 0.0.14

325

lib/list.js

@@ -16,2 +16,8 @@ import { TernaryTreeKind } from "./types";

let emptyBranch = null;
let isEmptyBranch = (x) => {
if (x == null) {
return true;
}
return x.size == 0;
};
function decideParentDepth(...xs) {

@@ -37,10 +43,10 @@ let depth = 0;

let left = xs[offset];
let right = xs[offset + 1];
let middle = xs[offset + 1];
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: listLen(left) + listLen(right),
size: listLen(left) + listLen(middle),
left: left,
middle: emptyBranch,
right: right,
depth: decideParentDepth(left, right),
middle: middle,
right: emptyBranch,
depth: decideParentDepth(left, middle),
};

@@ -380,11 +386,3 @@ return result;

if (listLen(tree) === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 0,
depth: 1,
left: emptyBranch,
middle: emptyBranch,
right: emptyBranch,
};
return result;
return emptyBranch;
}

@@ -398,3 +396,3 @@ if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {

if (leftSize + middleSize + rightSize !== tree.size) {
throw new Error("tree.size does not match sum case branch sizes");
throw new Error("tree.size does not match sum from branch sizes");
}

@@ -404,31 +402,49 @@ let result = emptyBranch;

let changedBranch = dissocList(tree.left, idx);
if (changedBranch.size === 0) {
changedBranch = emptyBranch;
if (changedBranch == null || changedBranch.size === 0) {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.middle, tree.right),
left: tree.middle,
middle: tree.right,
right: emptyBranch,
};
}
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(changedBranch, tree.middle, tree.right),
left: changedBranch,
middle: tree.middle,
right: tree.right,
};
else {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(changedBranch, tree.middle, tree.right),
left: changedBranch,
middle: tree.middle,
right: tree.right,
};
}
}
else if (idx <= leftSize + middleSize - 1) {
let changedBranch = dissocList(tree.middle, idx - leftSize);
if (changedBranch.size === 0) {
changedBranch = emptyBranch;
if (changedBranch == null || changedBranch.size === 0) {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: tree.right,
right: emptyBranch,
};
}
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: changedBranch,
right: tree.right,
};
else {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: changedBranch,
right: tree.right,
};
}
}
else {
let changedBranch = dissocList(tree.right, idx - leftSize - middleSize);
if (changedBranch.size === 0) {
if (changedBranch == null || changedBranch.size === 0) {
changedBranch = emptyBranch;

@@ -445,9 +461,4 @@ }

}
// TODO
if (listLen(result) === 1) {
result = {
kind: TernaryTreeKind.ternaryTreeLeaf,
size: 1,
value: listGet(result, 0),
};
if (result.middle == null) {
return result.left;
}

@@ -498,28 +509,53 @@ return result;

size: 2,
left: emptyBranch,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree,
right: emptyBranch,
};
return result;
}
}
if (listLen(tree) === 1) {
if (after) {
// in compact mode, values placed at left
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree,
right: emptyBranch,
};
return result;
}
else {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.left,
right: emptyBranch,
};
return result;
}
}
if (listLen(tree) === 1) {
if (after)
if (tree.left != null) {
if (listLen(tree) === 2 && tree.middle != null) {
if (after) {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: emptyBranch,
right: tree.middle,
};
return result;
}
else if (tree.middle != null) {
if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: emptyBranch,
left: tree.left,
middle: tree.middle,

@@ -531,183 +567,32 @@ right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },

else {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: 2,
left: tree.right,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: emptyBranch,
};
return result;
throw new Error("cannot insert after position 2 since only 2 elements here");
}
}
else {
if (tree.right != null) {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.right,
};
return result;
}
else if (tree.middle != null) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.middle,
right: emptyBranch,
middle: tree.left,
right: tree.middle,
};
return result;
}
else {
else if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.left,
};
return result;
}
}
}
if (listLen(tree) === 2) {
if (after) {
if (tree.right == null) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: tree.middle,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.middle,
};
return result;
}
else if (tree.middle == null) {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.right,
};
return result;
}
else if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: tree.right,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
};
return result;
}
else {
throw new Error(`Unexpected idx: ${idx}`);
}
}
else {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.middle,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.right,
};
return result;
}
else if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.middle,
middle: tree.right,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
};
return result;
}
else {
throw new Error("Unexpected idx: {idx}");
}
throw new Error("cannot insert before position 2 since only 2 elements here");
}
}
else {
if (tree.left == null) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.middle,
right: tree.right,
};
return result;
}
else if (tree.middle == null) {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.left,
right: tree.right,
};
return result;
}
else if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.right,
};
return result;
}
else {
throw new Error(`Unexpected idx: ${idx}`);
}
}
else {
if (idx === 0) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.left,
right: tree.middle,
};
return result;
}
else if (idx === 1) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree.middle,
};
return result;
}
else {
throw new Error(`Unexpected idx: ${idx}`);
}
}
}
}

@@ -727,5 +612,5 @@ let leftSize = listLen(tree.left);

depth: tree.depth + 1,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
right: tree,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree,
right: emptyBranch,
};

@@ -759,3 +644,3 @@ return result;

}
if (!after && idx === 0 && leftSize === 0 && middleSize >= rightSize) {
if (!after && idx === 0 && rightSize === 0 && middleSize >= rightSize) {
let result = {

@@ -766,4 +651,4 @@ kind: TernaryTreeKind.ternaryTreeBranch,

left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item },
middle: tree.middle,
right: tree.right,
middle: tree.left,
right: tree.middle,
};

@@ -770,0 +655,0 @@ return result;

3

lib/map.d.ts

@@ -8,7 +8,8 @@ import { TernaryTreeMap, TernaryTreeMapHashEntry } from "./types";

export declare function mapLen<K, V>(tree: TernaryTreeMap<K, V>): number;
export declare function mapLenBound<K, V>(tree: TernaryTreeMap<K, V>, bound: number): number;
export declare function formatMapInline<K, V>(tree: TernaryTreeMap<K, V>, withHash?: boolean): string;
export declare function isMapEmpty<K, V>(tree: TernaryTreeMap<K, V>): boolean;
export declare function isMapOfOne<K, V>(tree: TernaryTreeMap<K, V>, counted?: number): boolean;
export declare function toHashSortedPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]>;
export declare function contains<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): boolean;
export declare function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): T;
export declare function mapGetDefault<K, T>(originalTree: TernaryTreeMap<K, T>, item: K, v0: T): T;

@@ -15,0 +16,0 @@ export declare function checkMapStructure<K, V>(tree: TernaryTreeMap<K, V>): boolean;

549

lib/map.js

@@ -78,12 +78,4 @@ import { TernaryTreeKind, hashGenerator } from "./types";

case 1: {
let middlePair = xs[offset];
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: middlePair.hash,
minHash: middlePair.hash,
left: emptyBranch,
right: emptyBranch,
middle: createLeafFromHashEntry(middlePair),
depth: 1,
};
let leftPair = xs[offset];
let result = createLeafFromHashEntry(leftPair);
return result;

@@ -93,10 +85,10 @@ }

let leftPair = xs[offset];
let rightPair = xs[offset + 1];
let middlePair = xs[offset + 1];
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: rightPair.hash,
maxHash: middlePair.hash,
minHash: leftPair.hash,
middle: emptyBranch,
left: createLeafFromHashEntry(leftPair),
right: createLeafFromHashEntry(rightPair),
middle: createLeafFromHashEntry(middlePair),
right: emptyBranch,
depth: 1,

@@ -199,3 +191,3 @@ };

case TernaryTreeKind.ternaryTreeLeaf:
return 1;
return tree.elements.length;
case TernaryTreeKind.ternaryTreeBranch:

@@ -207,2 +199,25 @@ return mapLen(tree.left) + mapLen(tree.middle) + mapLen(tree.right); // TODO

}
// when size succeeds bound, no longer counting, faster than traversing whole tree
export function mapLenBound(tree, bound) {
if (tree == null) {
return 0;
}
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf:
return tree.elements.length;
case TernaryTreeKind.ternaryTreeBranch:
let ret = mapLenBound(tree.left, bound);
if (ret > bound) {
return ret;
}
ret = ret + mapLenBound(tree.middle, bound);
if (ret > bound) {
return ret;
}
ret = ret + mapLenBound(tree.right, bound);
return ret;
default:
throw new Error("Unknown");
}
}
export function formatMapInline(tree, withHash = false) {

@@ -240,2 +255,15 @@ if (tree == null) {

}
export function isMapOfOne(tree, counted = 0) {
if (tree == null) {
return true;
}
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf:
return false;
case TernaryTreeKind.ternaryTreeBranch:
return tree.left == null && tree.middle == null && tree.right == null;
default:
throw new Error("Unknown");
}
}
function collectHashSortedArray(tree, acc, idx) {

@@ -307,2 +335,3 @@ if (tree == null || isMapEmpty(tree)) {

}
// TODO
// reduce redundant computation by reusing hash result

@@ -325,10 +354,10 @@ 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) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
if (tree.left == null) {
return false;
}
if (tree.left.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.left.hash) {
return false;
}
else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
if (tree.left.hash === hx) {
tree = tree.left;

@@ -338,77 +367,49 @@ continue whileLoop; // notice, it jumps to while loop

}
if (tree.middle != null) {
if (tree.middle.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
else {
if (hx < tree.left.minHash) {
return false;
}
else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
tree = tree.middle;
if (hx <= tree.left.maxHash) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.right != null) {
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
if (tree.middle == null) {
return false;
}
if (tree.middle.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.middle.hash) {
return false;
}
else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
tree = tree.right;
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
}
return false;
}
return false;
}
export function mapGet(originalTree, item) {
let hx = hashGenerator(item);
let tree = originalTree;
whileLoop: while (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
let size = tree.elements.length;
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (dataEqual(pair[0], item)) {
return pair[1];
}
else {
if (hx < tree.middle.minHash) {
return false;
}
throw new Error(`Cannot find target for ${item}`);
}
// echo "looking for: ", hx, " ", item, " in ", tree.formatInline
if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
}
else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
tree = tree.left;
if (hx <= tree.middle.maxHash) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
if (tree.right == null) {
return false;
}
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.right.hash) {
return false;
}
else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
tree = tree.middle;
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
else {
if (hx < tree.right.minHash) {
return false;
}
else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
if (hx <= tree.right.maxHash) {
tree = tree.right;

@@ -418,5 +419,5 @@ continue whileLoop; // notice, it jumps to while loop

}
throw new Error(`Cannot find target for ${item}`);
return false;
}
throw new Error(`Cannot find target for ${item}`);
return false;
}

@@ -438,10 +439,10 @@ export function mapGetDefault(originalTree, item, v0) {

// echo "looking for: ", hx, " ", item, " in ", tree.formatInline
if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
if (tree.left == null) {
return v0;
}
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.left.hash) {
return v0;
}
else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
if (tree.left.hash === hx) {
tree = tree.left;

@@ -451,10 +452,19 @@ continue whileLoop; // notice, it jumps to while loop

}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
else {
if (hx < tree.left.minHash) {
return v0;
}
else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
if (hx <= tree.left.maxHash) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.middle == null) {
return v0;
}
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.middle.hash) {
return v0;
}
if (tree.middle.hash === hx) {
tree = tree.middle;

@@ -464,10 +474,19 @@ continue whileLoop; // notice, it jumps to while loop

}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
else {
if (hx < tree.middle.minHash) {
return v0;
}
else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
if (hx <= tree.middle.maxHash) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.right == null) {
return v0;
}
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.right.hash) {
return v0;
}
if (tree.right.hash === hx) {
tree = tree.right;

@@ -477,2 +496,11 @@ continue whileLoop; // notice, it jumps to while loop

}
else {
if (hx < tree.right.minHash) {
return v0;
}
if (hx <= tree.right.maxHash) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
}
return v0;

@@ -495,3 +523,3 @@ }

}
if (mapLen(tree) !== 1) {
if (mapLenBound(tree, 2) !== 1) {
throw new Error(`Bad len at leaf node ${tree}`);

@@ -501,2 +529,15 @@ }

else {
if (tree.left == null) {
if (tree.middle != null) {
throw new Error("Layout is not compact");
}
if (tree.middle != null) {
throw new Error("Layout is not compact");
}
}
if (tree.middle == null) {
if (tree.right != null) {
throw new Error("Layout is not compact");
}
}
if (tree.left != null && tree.middle != null) {

@@ -575,46 +616,48 @@ if (getMax(tree.left) >= getMin(tree.middle)) {

throw new Error("Unexpected missing hash in assoc, hash too large");
if (tree.left != null)
if (rangeContainsHash(tree.left, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: assocExisted(tree.left, key, item, thisHash),
middle: tree.middle,
right: tree.right,
depth: 0,
};
return result;
}
if (tree.middle != null)
if (rangeContainsHash(tree.middle, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: assocExisted(tree.middle, key, item, thisHash),
right: tree.right,
depth: 0,
};
return result;
}
if (tree.right != null) {
if (rangeContainsHash(tree.right, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: assocExisted(tree.right, key, item, thisHash),
depth: 0,
};
return result;
}
if (tree.left == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
else {
if (rangeContainsHash(tree.left, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: assocExisted(tree.left, key, item, thisHash),
middle: tree.middle,
right: tree.right,
depth: 0,
};
return result;
}
if (tree.middle == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
return emptyBranch;
if (rangeContainsHash(tree.middle, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: assocExisted(tree.middle, key, item, thisHash),
right: tree.right,
depth: 0,
};
return result;
}
if (tree.right == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
if (rangeContainsHash(tree.right, thisHash)) {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: assocExisted(tree.right, key, item, thisHash),
depth: 0,
};
return result;
}
throw new Error("Unexpected missing hash in assoc, found not branch");
}

@@ -682,39 +725,3 @@ function assocNew(tree, key, item, thisHash = null) {

if (thisHash < tree.minHash) {
if (tree.left == null) {
if (tree.middle == null) {
let childBranch = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: thisHash,
left: emptyBranch,
middle: childBranch,
right: tree.right,
depth: 0,
};
return result;
}
else {
let childBranch = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: thisHash,
left: childBranch,
middle: tree.middle,
right: tree.right,
depth: 0,
};
return result;
}
}
else if (tree.right == null) {
if (tree.right == null) {
let childBranch = {

@@ -730,4 +737,4 @@ kind: TernaryTreeKind.ternaryTreeLeaf,

left: childBranch,
middle: tree.left,
right: tree.middle,
middle: tree,
right: emptyBranch,
depth: 0,

@@ -748,4 +755,4 @@ };

left: childBranch,
middle: tree,
right: emptyBranch,
middle: tree.left,
right: tree.middle,
depth: 0,

@@ -757,39 +764,21 @@ };

if (thisHash > tree.maxHash) {
if (tree.right == null) {
if (tree.middle == null) {
let childBranch = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: childBranch,
right: emptyBranch,
depth: 0,
};
return result;
}
else {
let childBranch = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: childBranch,
depth: 0,
};
return result;
}
// in compact layout, left arm must be existed
if (tree.middle == null) {
let childBranch = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: childBranch,
right: emptyBranch,
depth: 0,
};
return result;
}
else if (tree.left == null) {
else if (tree.right == null) {
let childBranch = {

@@ -804,4 +793,4 @@ kind: TernaryTreeKind.ternaryTreeLeaf,

minHash: tree.minHash,
left: tree.middle,
middle: tree.right,
left: tree.left,
middle: tree.middle,
right: childBranch,

@@ -822,5 +811,5 @@ depth: 0,

minHash: tree.minHash,
left: emptyBranch,
middle: tree,
right: childBranch,
left: tree,
middle: childBranch,
right: emptyBranch,
depth: 0,

@@ -924,17 +913,17 @@ };

if (tree.hash === hashGenerator(key)) {
let newPairs = [];
let size = tree.elements.length;
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (!dataEqual(pair[0], key)) {
newPairs.push(pair);
if (size === 1 && dataEqual(key, tree.elements[0][0])) {
return emptyBranch;
}
else {
let newPairs = [];
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (!dataEqual(pair[0], key)) {
newPairs.push(pair);
}
}
}
if (newPairs.length > 0) {
let result = { kind: TernaryTreeKind.ternaryTreeLeaf, hash: tree.hash, elements: newPairs };
return result;
}
else {
return emptyBranch;
}
}

@@ -945,3 +934,3 @@ else {

}
if (mapLen(tree) === 1) {
if (mapLenBound(tree, 2) === 1) {
if (!contains(tree, key)) {

@@ -965,25 +954,59 @@ throw new Error("Unexpected missing key in dissoc single branch");

}
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: changedBranch,
middle: tree.middle,
right: tree.right,
depth: 0,
};
return result;
if (isMapEmpty(changedBranch)) {
if (isMapEmpty(tree.right)) {
return tree.middle;
}
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: tree.middle,
middle: tree.right,
right: emptyBranch,
depth: 0,
};
return result;
}
else {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: changedBranch,
middle: tree.middle,
right: tree.right,
depth: 0,
};
return result;
}
}
if (rangeContainsHash(tree.middle, thisHash)) {
let changedBranch = dissocExisted(tree.middle, key);
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: changedBranch,
right: tree.right,
depth: 0,
};
return result;
if (isMapEmpty(changedBranch)) {
if (isMapEmpty(tree.right)) {
return tree.left;
}
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: tree.right,
right: emptyBranch,
depth: 0,
};
return result;
}
else {
let result = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: changedBranch,
right: tree.right,
depth: 0,
};
return result;
}
}

@@ -1140,5 +1163,9 @@ if (rangeContainsHash(tree.right, thisHash)) {

}
for (let key of toKeys(xs)) {
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
for (let pair of toPairsArray(xs)) {
let key = pair[0];
let vx = pair[1];
if (!contains(ys, key)) {
return false;
}
let vy = mapGetDefault(ys, key, null);
// TODO compare deep structures

@@ -1145,0 +1172,0 @@ if (!dataEqual(vx, vy)) {

78

lib/test-list.js
import { listToString, initTernaryTreeList, indexOf, findIndex, reverse, checkListStructure, slice, listToPairs, listToItems, formatListInline, sameListShape, assocBefore, concat, assocAfter, prepend, append, rest, butlast, first, assocList, dissocList, listGet, insert, initEmptyTernaryTreeList, last, listLen, forceListInplaceBalancing, listEqual, indexToItems, listMapValues, } from "./list";
import { test, check, arrayEqual } from "./utils";
import { test, check, arrayEqual, checkEqual } from "./utils";
export let runListTests = () => {

@@ -9,3 +9,3 @@ test("init list", () => {

check(checkListStructure(data11));
check(formatListInline(data11) === "((1 (2 _ 3) 4) (5 6 7) (8 (9 _ 10) 11))");
checkEqual(formatListInline(data11), "((1 (2 3 _) 4) (5 6 7) (8 (9 10 _) 11))");
check(arrayEqual(origin11, [...listToItems(data11)]));

@@ -36,18 +36,18 @@ check(arrayEqual([...listToItems(data11)], [...indexToItems(data11)]));

}
check(formatListInline(data5) === "((1 _ 2) 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 0)) === "(2 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 1)) === "(1 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 2)) === "((1 _ 2) _ (4 _ 5))");
check(formatListInline(dissocList(data5, 3)) === "((1 _ 2) 3 5)");
check(formatListInline(dissocList(data5, 4)) === "((1 _ 2) 3 4)");
check(formatListInline(rest(initTernaryTreeList([1]))) === "(_ _ _)");
check(formatListInline(rest(initTernaryTreeList([1, 2]))) === "2");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3]))) === "(_ 2 3)");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4]))) === "(_ (2 _ 3) 4)");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4, 5]))) === "(2 3 (4 _ 5))");
check(formatListInline(butlast(initTernaryTreeList([1]))) === "(_ _ _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2]))) === "1");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3]))) === "(1 2 _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4]))) === "(1 (2 _ 3) _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4, 5]))) === "((1 _ 2) 3 4)");
checkEqual(formatListInline(data5), "((1 2 _) 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 0)), "(2 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 1)), "(1 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 2)), "((1 2 _) (4 5 _) _)");
checkEqual(formatListInline(dissocList(data5, 3)), "((1 2 _) 3 5)");
checkEqual(formatListInline(dissocList(data5, 4)), "((1 2 _) 3 4)");
checkEqual(formatListInline(rest(initTernaryTreeList([1]))), "_");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2]))), "2");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3]))), "(2 3 _)");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4]))), "((2 3 _) 4 _)");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4, 5]))), "(2 3 (4 5 _))");
checkEqual(formatListInline(butlast(initTernaryTreeList([1]))), "_");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2]))), "1");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3]))), "(1 2 _)");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4]))), "(1 (2 3 _) _)");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4, 5]))), "((1 2 _) 3 4)");
});

@@ -57,19 +57,19 @@ test("list insertions", () => {

let data5 = initTernaryTreeList(origin5);
check(formatListInline(data5) === "((1 _ 2) 3 (4 _ 5))");
check(formatListInline(insert(data5, 0, 10, false)) === "(_ 10 ((1 _ 2) 3 (4 _ 5)))");
check(formatListInline(insert(data5, 0, 10, true)) === "((1 10 2) 3 (4 _ 5))");
check(formatListInline(insert(data5, 1, 10, false)) === "((1 10 2) 3 (4 _ 5))");
check(formatListInline(insert(data5, 1, 10, true)) === "((1 2 10) 3 (4 _ 5))");
check(formatListInline(insert(data5, 2, 10, false)) === "((1 _ 2) (_ 10 3) (4 _ 5))");
check(formatListInline(insert(data5, 2, 10, true)) === "((1 _ 2) (3 10 _) (4 _ 5))");
check(formatListInline(insert(data5, 3, 10, false)) === "((1 _ 2) 3 (10 4 5))");
check(formatListInline(insert(data5, 3, 10, true)) === "((1 _ 2) 3 (4 10 5))");
check(formatListInline(insert(data5, 4, 10, false)) === "((1 _ 2) 3 (4 10 5))");
check(formatListInline(insert(data5, 4, 10, true)) === "(((1 _ 2) 3 (4 _ 5)) 10 _)");
checkEqual(formatListInline(data5), "((1 2 _) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 0, 10, false)), "(10 ((1 2 _) 3 (4 5 _)) _)");
checkEqual(formatListInline(insert(data5, 0, 10, true)), "((1 10 2) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 1, 10, false)), "((1 10 2) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 1, 10, true)), "((1 2 10) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 2, 10, false)), "((1 2 _) (10 3 _) (4 5 _))");
checkEqual(formatListInline(insert(data5, 2, 10, true)), "((1 2 _) (3 10 _) (4 5 _))");
checkEqual(formatListInline(insert(data5, 3, 10, false)), "((1 2 _) 3 (10 4 5))");
checkEqual(formatListInline(insert(data5, 3, 10, true)), "((1 2 _) 3 (4 10 5))");
checkEqual(formatListInline(insert(data5, 4, 10, false)), "((1 2 _) 3 (4 10 5))");
checkEqual(formatListInline(insert(data5, 4, 10, true)), "(((1 2 _) 3 (4 5 _)) 10 _)");
let origin4 = [1, 2, 3, 4];
let data4 = initTernaryTreeList(origin4);
check(formatListInline(assocBefore(data4, 3, 10)) === "(1 (2 _ 3) (_ 10 4))");
check(formatListInline(assocAfter(data4, 3, 10)) === "(1 (2 _ 3) (4 10 _))");
check(formatListInline(prepend(data4, 10)) === "((_ 10 1) (2 _ 3) 4)");
check(formatListInline(append(data4, 10)) === "(1 (2 _ 3) (4 10 _))");
checkEqual(formatListInline(assocBefore(data4, 3, 10)), "(1 (2 3 _) (10 4 _))");
checkEqual(formatListInline(assocAfter(data4, 3, 10)), "(1 (2 3 _) (4 10 _))");
checkEqual(formatListInline(prepend(data4, 10)), "((10 1 _) (2 3 _) 4)");
checkEqual(formatListInline(append(data4, 10)), "(1 (2 3 _) (4 10 _))");
});

@@ -81,6 +81,6 @@ test("concat", () => {

let data4 = initTernaryTreeList([7, 8]);
check(formatListInline(concat(data1, data2)) === "((1 _ 2) _ (3 _ 4))");
check(formatListInline(concat(initTernaryTreeList([]), data1)) === "(1 _ 2)");
check(formatListInline(concat(data1, data2, data3)) === "((1 _ 2) (3 _ 4) (5 _ 6))");
check(formatListInline(concat(data1, data2, data3, data4)) === "((1 _ 2) ((3 _ 4) _ (5 _ 6)) (7 _ 8))");
check(formatListInline(concat(data1, data2)) === "((1 2 _) (3 4 _) _)");
check(formatListInline(concat(initTernaryTreeList([]), data1)) === "(1 2 _)");
check(formatListInline(concat(data1, data2, data3)) === "((1 2 _) (3 4 _) (5 6 _))");
check(formatListInline(concat(data1, data2, data3, data4)) === "((1 2 _) ((3 4 _) (5 6 _) _) (7 8 _))");
checkListStructure(concat(data1, data2));

@@ -112,3 +112,3 @@ checkListStructure(concat(data1, data2, data3));

forceListInplaceBalancing(data);
check(formatListInline(data) === "(((0 _ 1) (2 3 4) (5 _ 6)) ((7 _ 8) (9 _ 10) (11 _ 12)) ((13 _ 14) (15 16 17) (18 _ 19)))");
check(formatListInline(data) === "(((0 1 _) (2 3 4) (5 6 _)) ((7 8 _) (9 10 _) (11 12 _)) ((13 14 _) (15 16 17) (18 19 _)))");
// echo data.formatInline

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

});
test("check(structure)", () => {
test("check structure", () => {
var data = initTernaryTreeList([]);

@@ -133,0 +133,0 @@ for (let idx = 0; idx < 20; idx++) {

35

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, mapGet, toPairs, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEqual, toKeys, toPairsArray, mapMapValues, mapGetDefault, } from "./map";
import { initTernaryTreeMap, toHashSortedPairs, merge, mergeSkip, formatMapInline, assocMap, dissocMap, contains, toPairs, initEmptyTernaryTreeMap, sameMapShape, checkMapStructure, mapLen, mapEqual, toKeys, toPairsArray, mapMapValues, mapGetDefault, } from "./map";
export let runMapTests = () => {

@@ -20,4 +20,6 @@ test("init map", () => {

let data11 = initTernaryTreeMap(inList);
checkMapStructure(data10);
checkMapStructure(data11);
// echo data10
justDisplay(formatMapInline(data10), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (_ 1:11 _)) (8:18 0:10 4:14))");
justDisplay(formatMapInline(data10, true), " ((0:10 1:11 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19))");
check(deepEqual(toHashSortedPairs(data10), inList));

@@ -27,9 +29,9 @@ check(deepEqual(toHashSortedPairs(data11), inList));

check(contains(data10, "11") == false);
check(deepEqual(mapGet(data10, "1"), 11));
check(deepEqual(mapGetDefault(data10, "1", null), 11));
check(deepEqual(mapGetDefault(data10, "111", 0), 0));
// check(deepEqual(mapGet(data10, "11"), null)); // should throws error
// check(deepEqual(mapGetDefault(data10, "11", {} as any), null)); // should throws error
let emptyData = new Map();
check(mapEqual(initEmptyTernaryTreeMap(), initTernaryTreeMap(emptyData)));
});
test("check(structure", () => {
test("check structure", () => {
var dict = new Map();

@@ -51,4 +53,5 @@ for (let idx = 0; idx < 100; idx++) {

check(contains(data, "12") == false);
justDisplay(formatMapInline(assocMap(data, "1", 2222), false), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (_ 1:2222 _)) (8:18 0:10 4:14))");
justDisplay(formatMapInline(assocMap(data, "23", 2222), false), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (23:2222 1:11 _)) (8:18 0:10 4:14))");
checkMapStructure(data);
justDisplay(formatMapInline(assocMap(data, "1", 2222), true), "((0:10 1:2222 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19))");
justDisplay(formatMapInline(assocMap(data, "23", 2222), true), "(((0:10 1:11 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19)) 23:2222 _)");
});

@@ -61,2 +64,3 @@ test("dissoc", () => {

let data = initTernaryTreeMap(dict);
checkMapStructure(data);
// echo data.formatInline

@@ -81,2 +85,3 @@ for (let idx = 0; idx < 10; idx++) {

let data = initTernaryTreeMap(dict);
checkMapStructure(data);
// TODO

@@ -94,2 +99,4 @@ // justDisplay((mapToString(toPairs(data))) , "@[2:12, 3:13, 7:17, 9:19, 6:16, 5:15, 1:11, 8:18, 0:10, 4:14]")

let b = dissocMap(data, "3");
checkMapStructure(data);
checkMapStructure(b);
check(mapEqual(data, data));

@@ -113,2 +120,3 @@ check(!mapEqual(data, b));

let data = initTernaryTreeMap(dict);
checkMapStructure(data);
var dictB = new Map();

@@ -130,2 +138,3 @@ for (let idx = 10; idx < 14; idx++) {

let a = initTernaryTreeMap(dict);
checkMapStructure(a);
var dict2 = new Map();

@@ -136,7 +145,8 @@ for (let idx = 0; idx < 4; idx++) {

let b = initTernaryTreeMap(dict2);
checkMapStructure(b);
let c = mergeSkip(a, b, 11);
check(deepEqual(mapGet(c, "0"), 10));
check(deepEqual(mapGet(c, "1"), 12));
check(deepEqual(mapGet(c, "2"), 13));
check(deepEqual(mapGet(c, "3"), 14));
check(deepEqual(mapGetDefault(c, "0", null), 10));
check(deepEqual(mapGetDefault(c, "1", null), 12));
check(deepEqual(mapGetDefault(c, "2", null), 13));
check(deepEqual(mapGetDefault(c, "3", null), 14));
});

@@ -151,2 +161,3 @@ test("iterator", () => {

let data = initTernaryTreeMap(dict);
checkMapStructure(data);
var i = 0;

@@ -169,2 +180,3 @@ for (let [k, v] of toPairs(data)) {

let data = initTernaryTreeMap(dict);
checkMapStructure(data);
var i = 0;

@@ -190,2 +202,3 @@ for (let [k, v] of toPairs(data)) {

checkMapStructure(data3);
checkMapStructure(data3);
check(mapEqual(data2, data3));

@@ -192,0 +205,0 @@ check(formatMapInline(data2) === formatMapInline(data3));

2

lib/utils.d.ts

@@ -15,2 +15,4 @@ /** by default, it compares by reference

export declare let check: (x: boolean) => void;
/** compare by reference */
export declare let checkEqual: (x: any, y: any) => void;
export declare let justDisplay: (x: any, y: any) => void;

@@ -17,0 +19,0 @@ export declare let cmp: (x: any, y: any) => 1 | 0 | -1;

8

lib/utils.js

@@ -60,2 +60,10 @@ /** by default, it compares by reference

};
/** compare by reference */
export let checkEqual = (x, y) => {
if (x !== y) {
console.log("Left: ", x);
console.log("Right: ", y);
throw new Error("Test failed");
}
};
export let justDisplay = (x, y) => {

@@ -62,0 +70,0 @@ console.group("Compare:");

2

package.json
{
"name": "@calcit/ternary-tree",
"version": "0.0.13",
"version": "0.0.14",
"main": "./lib/index.js",

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

1

README.md

@@ -20,3 +20,2 @@ ## ternary-tree in TypeScript

function mapEqual<K, V>(xs: TernaryTreeMap<K, V>, ys: TernaryTreeMap<K, V>): boolean;
function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): T;

@@ -23,0 +22,0 @@ function* toPairs<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]>;

314

src/list.ts

@@ -18,2 +18,9 @@ import { RefInt, TernaryTreeKind, TernaryTreeList, TernaryTreeListTheBranch } from "./types";

let isEmptyBranch = (x: TernaryTreeList<any>) => {
if (x == null) {
return true;
}
return x.size == 0;
};
function decideParentDepth<T>(...xs: Array<TernaryTreeList<T>>): number {

@@ -40,10 +47,10 @@ let depth = 0;

let left = xs[offset];
let right = xs[offset + 1];
let middle = xs[offset + 1];
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: listLen(left) + listLen(right),
size: listLen(left) + listLen(middle),
left: left,
middle: emptyBranch,
right: right,
depth: decideParentDepth(left, right),
middle: middle,
right: emptyBranch,
depth: decideParentDepth(left, middle),
};

@@ -405,11 +412,3 @@ return result;

if (listLen(tree) === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 0,
depth: 1,
left: emptyBranch,
middle: emptyBranch,
right: emptyBranch,
};
return result;
return emptyBranch;
}

@@ -426,3 +425,3 @@

if (leftSize + middleSize + rightSize !== tree.size) {
throw new Error("tree.size does not match sum case branch sizes");
throw new Error("tree.size does not match sum from branch sizes");
}

@@ -434,29 +433,45 @@

let changedBranch = dissocList(tree.left, idx);
if (changedBranch.size === 0) {
changedBranch = emptyBranch;
if (changedBranch == null || changedBranch.size === 0) {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.middle, tree.right),
left: tree.middle,
middle: tree.right,
right: emptyBranch,
};
} else {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(changedBranch, tree.middle, tree.right),
left: changedBranch,
middle: tree.middle,
right: tree.right,
};
}
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(changedBranch, tree.middle, tree.right),
left: changedBranch,
middle: tree.middle,
right: tree.right,
};
} else if (idx <= leftSize + middleSize - 1) {
let changedBranch = dissocList(tree.middle, idx - leftSize);
if (changedBranch.size === 0) {
changedBranch = emptyBranch;
if (changedBranch == null || changedBranch.size === 0) {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: tree.right,
right: emptyBranch,
};
} else {
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: changedBranch,
right: tree.right,
};
}
result = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: tree.size - 1,
depth: decideParentDepth(tree.left, changedBranch, tree.right),
left: tree.left,
middle: changedBranch,
right: tree.right,
};
} else {
let changedBranch = dissocList(tree.right, idx - leftSize - middleSize);
if (changedBranch.size === 0) {
if (changedBranch == null || changedBranch.size === 0) {
changedBranch = emptyBranch;

@@ -473,9 +488,4 @@ }

}
// TODO
if (listLen(result) === 1) {
result = {
kind: TernaryTreeKind.ternaryTreeLeaf,
size: 1,
value: listGet(result, 0),
};
if (result.middle == null) {
return result.left;
}

@@ -531,28 +541,54 @@ return result;

size: 2,
left: emptyBranch,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree,
right: emptyBranch,
};
return result;
}
}
if (listLen(tree) === 1) {
if (after) {
// in compact mode, values placed at left
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree,
right: emptyBranch,
};
return result;
} else {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.left,
right: emptyBranch,
};
return result;
}
}
if (listLen(tree) === 1) {
if (after)
if (tree.left != null) {
if (listLen(tree) === 2 && tree.middle != null) {
if (after) {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: emptyBranch,
right: tree.middle,
};
return result;
} else if (tree.middle != null) {
}
if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: emptyBranch,
left: tree.left,
middle: tree.middle,

@@ -563,168 +599,28 @@ right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,

} else {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: 2,
left: tree.right,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: emptyBranch,
};
return result;
throw new Error("cannot insert after position 2 since only 2 elements here");
}
else {
if (tree.right != null) {
} else {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
size: 3,
depth: 2,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.right,
};
return result;
} else if (tree.middle != null) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.middle,
right: emptyBranch,
middle: tree.left,
right: tree.middle,
};
return result;
} else {
} else if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 2,
depth: getDepth(tree.middle) + 1,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.left,
};
return result;
}
}
}
if (listLen(tree) === 2) {
if (after) {
if (tree.right == null) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: tree.middle,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.middle,
};
return result;
} else if (tree.middle == null) {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.right,
};
return result;
} else if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: tree.right,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
};
return result;
} else {
throw new Error(`Unexpected idx: ${idx}`);
}
} else {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.middle,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.right,
};
return result;
} else if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.middle,
middle: tree.right,
right: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
};
return result;
} else {
throw new Error("Unexpected idx: {idx}");
}
throw new Error("cannot insert before position 2 since only 2 elements here");
}
} else {
if (tree.left == null) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.middle,
right: tree.right,
};
return result;
} else if (tree.middle == null) {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.left,
right: tree.right,
};
return result;
} else if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.right,
};
return result;
} else {
throw new Error(`Unexpected idx: ${idx}`);
}
} else {
if (idx === 0) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.left,
right: tree.middle,
};
return result;
} else if (idx === 1) {
let result: TernaryTreeList<T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
size: 3,
depth: 2,
left: tree.left,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree.middle,
};
return result;
} else {
throw new Error(`Unexpected idx: ${idx}`);
}
}
}

@@ -749,5 +645,5 @@ }

depth: tree.depth + 1,
left: emptyBranch,
middle: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
right: tree,
left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree,
right: emptyBranch,
};

@@ -784,3 +680,3 @@ return result;

if (!after && idx === 0 && leftSize === 0 && middleSize >= rightSize) {
if (!after && idx === 0 && rightSize === 0 && middleSize >= rightSize) {
let result: TernaryTreeList<T> = {

@@ -791,4 +687,4 @@ kind: TernaryTreeKind.ternaryTreeBranch,

left: { kind: TernaryTreeKind.ternaryTreeLeaf, size: 1, value: item } as TernaryTreeList<T>,
middle: tree.middle,
right: tree.right,
middle: tree.left,
right: tree.middle,
};

@@ -795,0 +691,0 @@ return result;

561

src/map.ts

@@ -85,12 +85,4 @@ import { TernaryTreeMap, TernaryTreeKind, TernaryTreeMapTheLeaf, TernaryTreeMapTheBranch, RefInt, Hash, hashGenerator, TernaryTreeMapHashEntry } from "./types";

case 1: {
let middlePair = xs[offset];
let result: TernaryTreeMap<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: middlePair.hash,
minHash: middlePair.hash,
left: emptyBranch,
right: emptyBranch,
middle: createLeafFromHashEntry(middlePair),
depth: 1,
};
let leftPair = xs[offset];
let result: TernaryTreeMap<K, T> = createLeafFromHashEntry(leftPair);
return result;

@@ -100,10 +92,10 @@ }

let leftPair = xs[offset];
let rightPair = xs[offset + 1];
let middlePair = xs[offset + 1];
let result: TernaryTreeMap<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: rightPair.hash,
maxHash: middlePair.hash,
minHash: leftPair.hash,
middle: emptyBranch,
left: createLeafFromHashEntry(leftPair),
right: createLeafFromHashEntry(rightPair),
middle: createLeafFromHashEntry(middlePair),
right: emptyBranch,
depth: 1,

@@ -213,3 +205,3 @@ };

case TernaryTreeKind.ternaryTreeLeaf:
return 1;
return tree.elements.length;
case TernaryTreeKind.ternaryTreeBranch:

@@ -222,2 +214,26 @@ return mapLen(tree.left) + mapLen(tree.middle) + mapLen(tree.right); // TODO

// when size succeeds bound, no longer counting, faster than traversing whole tree
export function mapLenBound<K, V>(tree: TernaryTreeMap<K, V>, bound: number): number {
if (tree == null) {
return 0;
}
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf:
return tree.elements.length;
case TernaryTreeKind.ternaryTreeBranch:
let ret = mapLenBound(tree.left, bound);
if (ret > bound) {
return ret;
}
ret = ret + mapLenBound(tree.middle, bound);
if (ret > bound) {
return ret;
}
ret = ret + mapLenBound(tree.right, bound);
return ret;
default:
throw new Error("Unknown");
}
}
export function formatMapInline<K, V>(tree: TernaryTreeMap<K, V>, withHash: boolean = false): string {

@@ -257,2 +273,16 @@ if (tree == null) {

export function isMapOfOne<K, V>(tree: TernaryTreeMap<K, V>, counted: number = 0): boolean {
if (tree == null) {
return true;
}
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf:
return false;
case TernaryTreeKind.ternaryTreeBranch:
return tree.left == null && tree.middle == null && tree.right == null;
default:
throw new Error("Unknown");
}
}
function collectHashSortedArray<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<[K, T]>, idx: RefInt): void {

@@ -327,2 +357,4 @@ if (tree == null || isMapEmpty(tree)) {

// TODO
// reduce redundant computation by reusing hash result

@@ -348,34 +380,63 @@ 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) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
if (tree.left == null) {
return false;
}
if (tree.left.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.left.hash) {
return false;
}
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
} else {
if (hx < tree.left.minHash) {
return false;
}
if (hx <= tree.left.maxHash) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.middle != null) {
if (tree.middle.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
if (tree.middle == null) {
return false;
}
if (tree.middle.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.middle.hash) {
return false;
}
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
} else {
if (hx < tree.middle.minHash) {
return false;
}
if (hx <= tree.middle.maxHash) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.right != null) {
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
if (tree.right == null) {
return false;
}
if (tree.right.kind === TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.right.hash) {
return false;
}
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
} else {
if (hx < tree.right.minHash) {
return false;
}
if (hx <= tree.right.maxHash) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
}

@@ -388,3 +449,3 @@ return false;

export function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): T {
export function mapGetDefault<K, T>(originalTree: TernaryTreeMap<K, T>, item: K, v0: T): T {
let hx = hashGenerator(item);

@@ -403,3 +464,3 @@

}
throw new Error(`Cannot find target for ${item}`);
return v0;
}

@@ -409,32 +470,19 @@

if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
if (tree.left == null) {
return v0;
}
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.left.hash) {
return v0;
}
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
} else {
if (hx < tree.left.minHash) {
return v0;
}
}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
tree = tree.right;
if (hx <= tree.left.maxHash) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop

@@ -444,44 +492,18 @@ }

throw new Error(`Cannot find target for ${item}`);
}
throw new Error(`Cannot find target for ${item}`);
}
export function mapGetDefault<K, T>(originalTree: TernaryTreeMap<K, T>, item: K, v0: T): T {
let hx = hashGenerator(item);
let tree = originalTree;
whileLoop: while (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
let size = tree.elements.length;
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (dataEqual(pair[0], item)) {
return pair[1];
}
}
if (tree.middle == null) {
return v0;
}
// echo "looking for: ", hx, " ", item, " in ", tree.formatInline
if (tree.left != null) {
if (tree.left.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.left.hash === hx) {
tree = tree.left;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.left.minHash && hx <= tree.left.maxHash) {
tree = tree.left;
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.middle.hash) {
return v0;
}
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
}
if (tree.middle != null) {
if (tree.middle.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.middle.hash === hx) {
tree = tree.middle;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.middle.minHash && hx <= tree.middle.maxHash) {
} else {
if (hx < tree.middle.minHash) {
return v0;
}
if (hx <= tree.middle.maxHash) {
tree = tree.middle;

@@ -491,12 +513,22 @@ continue whileLoop; // notice, it jumps to while loop

}
if (tree.right != null) {
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
} else if (hx >= tree.right.minHash && hx <= tree.right.maxHash) {
if (tree.right == null) {
return v0;
}
if (tree.right.kind == TernaryTreeKind.ternaryTreeLeaf) {
if (hx < tree.right.hash) {
return v0;
}
if (tree.right.hash === hx) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
} else {
if (hx < tree.right.minHash) {
return v0;
}
if (hx <= tree.right.maxHash) {
tree = tree.right;
continue whileLoop; // notice, it jumps to while loop
}
}

@@ -524,6 +556,19 @@

if (mapLen(tree) !== 1) {
if (mapLenBound(tree, 2) !== 1) {
throw new Error(`Bad len at leaf node ${tree}`);
}
} else {
if (tree.left == null) {
if (tree.middle != null) {
throw new Error("Layout is not compact");
}
if (tree.middle != null) {
throw new Error("Layout is not compact");
}
}
if (tree.middle == null) {
if (tree.right != null) {
throw new Error("Layout is not compact");
}
}
if (tree.left != null && tree.middle != null) {

@@ -605,47 +650,50 @@ if (getMax(tree.left) >= getMin(tree.middle)) {

if (tree.left != null)
if (rangeContainsHash(tree.left, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: assocExisted(tree.left, key, item, thisHash),
middle: tree.middle,
right: tree.right,
depth: 0, // TODO
};
return result;
}
if (tree.left == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
if (rangeContainsHash(tree.left, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: assocExisted(tree.left, key, item, thisHash),
middle: tree.middle,
right: tree.right,
depth: 0, // TODO
};
return result;
}
if (tree.middle != null)
if (rangeContainsHash(tree.middle, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: assocExisted(tree.middle, key, item, thisHash),
right: tree.right,
depth: 0, // TODO
};
return result;
}
if (tree.middle == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
if (rangeContainsHash(tree.middle, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: assocExisted(tree.middle, key, item, thisHash),
right: tree.right,
depth: 0, // TODO
};
return result;
}
if (tree.right != null) {
if (rangeContainsHash(tree.right, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: assocExisted(tree.right, key, item, thisHash),
depth: 0, // TODO
};
return result;
}
} else {
if (tree.right == null) {
throw new Error("Unexpected missing hash in assoc, found not branch");
}
return emptyBranch;
if (rangeContainsHash(tree.right, thisHash)) {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: assocExisted(tree.right, key, item, thisHash),
depth: 0, // TODO
};
return result;
}
throw new Error("Unexpected missing hash in assoc, found not branch");
}

@@ -713,37 +761,3 @@

if (thisHash < tree.minHash) {
if (tree.left == null) {
if (tree.middle == null) {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: thisHash,
left: emptyBranch,
middle: childBranch,
right: tree.right,
depth: 0, // TODO
};
return result;
} else {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: thisHash,
left: childBranch,
middle: tree.middle,
right: tree.right,
depth: 0, // TODO
};
return result;
}
} else if (tree.right == null) {
if (tree.right == null) {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {

@@ -759,4 +773,4 @@ kind: TernaryTreeKind.ternaryTreeLeaf,

left: childBranch,
middle: tree.left,
right: tree.middle,
middle: tree,
right: emptyBranch,
depth: 0, // TODO

@@ -776,4 +790,4 @@ };

left: childBranch,
middle: tree,
right: emptyBranch,
middle: tree.left,
right: tree.middle,
depth: 0, // TODO

@@ -786,37 +800,4 @@ };

if (thisHash > tree.maxHash) {
if (tree.right == null) {
if (tree.middle == null) {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: childBranch,
right: emptyBranch,
depth: 0, // TODO
};
return result;
} else {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: childBranch,
depth: 0, // TODO
};
return result;
}
} else if (tree.left == null) {
// in compact layout, left arm must be existed
if (tree.middle == null) {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {

@@ -831,8 +812,23 @@ kind: TernaryTreeKind.ternaryTreeLeaf,

minHash: tree.minHash,
left: tree.middle,
middle: tree.right,
left: tree.left,
middle: childBranch,
right: emptyBranch,
depth: 0, // TODO
};
return result;
} else if (tree.right == null) {
let childBranch: TernaryTreeMapTheLeaf<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: thisHash,
elements: [[key, item]],
};
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: thisHash,
minHash: tree.minHash,
left: tree.left,
middle: tree.middle,
right: childBranch,
depth: 0, // TODO
};
return result;

@@ -849,5 +845,5 @@ } else {

minHash: tree.minHash,
left: emptyBranch,
middle: tree,
right: childBranch,
left: tree,
middle: childBranch,
right: emptyBranch,
depth: 0, // TODO

@@ -958,15 +954,15 @@ };

if (tree.hash === hashGenerator(key)) {
let newPairs: Array<[K, T]> = [];
let size = tree.elements.length;
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (!dataEqual(pair[0], key)) {
newPairs.push(pair);
if (size === 1 && dataEqual(key, tree.elements[0][0])) {
return emptyBranch;
} else {
let newPairs: Array<[K, T]> = [];
for (let i = 0; i < size; i++) {
let pair = tree.elements[i];
if (!dataEqual(pair[0], key)) {
newPairs.push(pair);
}
}
}
if (newPairs.length > 0) {
let result: TernaryTreeMapTheLeaf<K, T> = { kind: TernaryTreeKind.ternaryTreeLeaf, hash: tree.hash, elements: newPairs };
return result;
} else {
return emptyBranch;
}

@@ -978,3 +974,3 @@ } else {

if (mapLen(tree) === 1) {
if (mapLenBound(tree, 2) === 1) {
if (!contains(tree, key)) {

@@ -999,12 +995,28 @@ throw new Error("Unexpected missing key in dissoc single branch");

let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: changedBranch,
middle: tree.middle,
right: tree.right,
depth: 0, // TODO
};
return result;
if (isMapEmpty(changedBranch)) {
if (isMapEmpty(tree.right)) {
return tree.middle;
}
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: tree.middle,
middle: tree.right,
right: emptyBranch,
depth: 0, // TODO
};
return result;
} else {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: tree.maxHash,
minHash: minHash,
left: changedBranch,
middle: tree.middle,
right: tree.right,
depth: 0, // TODO
};
return result;
}
}

@@ -1015,12 +1027,28 @@

let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: changedBranch,
right: tree.right,
depth: 0, // TODO
};
return result;
if (isMapEmpty(changedBranch)) {
if (isMapEmpty(tree.right)) {
return tree.left;
}
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: tree.right,
right: emptyBranch,
depth: 0, // TODO
};
return result;
} else {
let result: TernaryTreeMapTheBranch<K, T> = {
kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: getMax(tree),
minHash: tree.minHash,
left: tree.left,
middle: changedBranch,
right: tree.right,
depth: 0, // TODO
};
return result;
}
}

@@ -1183,6 +1211,11 @@

for (let key of toKeys(xs)) {
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
for (let pair of toPairsArray(xs)) {
let key = pair[0];
let vx = pair[1];
if (!contains(ys, key)) {
return false;
}
let vy = mapGetDefault(ys, key, null);
// TODO compare deep structures

@@ -1189,0 +1222,0 @@ if (!dataEqual(vx, vy)) {

78

src/test-list.ts

@@ -34,3 +34,3 @@ import {

import { test, check, arrayEqual } from "./utils";
import { test, check, arrayEqual, checkEqual } from "./utils";

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

check(formatListInline(data11) === "((1 (2 _ 3) 4) (5 6 7) (8 (9 _ 10) 11))");
checkEqual(formatListInline(data11), "((1 (2 3 _) 4) (5 6 7) (8 (9 10 _) 11))");
check(

@@ -87,20 +87,20 @@ arrayEqual<number>(origin11, [...listToItems(data11)])

check(formatListInline(data5) === "((1 _ 2) 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 0)) === "(2 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 1)) === "(1 3 (4 _ 5))");
check(formatListInline(dissocList(data5, 2)) === "((1 _ 2) _ (4 _ 5))");
check(formatListInline(dissocList(data5, 3)) === "((1 _ 2) 3 5)");
check(formatListInline(dissocList(data5, 4)) === "((1 _ 2) 3 4)");
checkEqual(formatListInline(data5), "((1 2 _) 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 0)), "(2 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 1)), "(1 3 (4 5 _))");
checkEqual(formatListInline(dissocList(data5, 2)), "((1 2 _) (4 5 _) _)");
checkEqual(formatListInline(dissocList(data5, 3)), "((1 2 _) 3 5)");
checkEqual(formatListInline(dissocList(data5, 4)), "((1 2 _) 3 4)");
check(formatListInline(rest(initTernaryTreeList([1]))) === "(_ _ _)");
check(formatListInline(rest(initTernaryTreeList([1, 2]))) === "2");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3]))) === "(_ 2 3)");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4]))) === "(_ (2 _ 3) 4)");
check(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4, 5]))) === "(2 3 (4 _ 5))");
checkEqual(formatListInline(rest(initTernaryTreeList([1]))), "_");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2]))), "2");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3]))), "(2 3 _)");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4]))), "((2 3 _) 4 _)");
checkEqual(formatListInline(rest(initTernaryTreeList([1, 2, 3, 4, 5]))), "(2 3 (4 5 _))");
check(formatListInline(butlast(initTernaryTreeList([1]))) === "(_ _ _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2]))) === "1");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3]))) === "(1 2 _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4]))) === "(1 (2 _ 3) _)");
check(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4, 5]))) === "((1 _ 2) 3 4)");
checkEqual(formatListInline(butlast(initTernaryTreeList([1]))), "_");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2]))), "1");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3]))), "(1 2 _)");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4]))), "(1 (2 3 _) _)");
checkEqual(formatListInline(butlast(initTernaryTreeList([1, 2, 3, 4, 5]))), "((1 2 _) 3 4)");
});

@@ -112,14 +112,14 @@

check(formatListInline(data5) === "((1 _ 2) 3 (4 _ 5))");
checkEqual(formatListInline(data5), "((1 2 _) 3 (4 5 _))");
check(formatListInline(insert(data5, 0, 10, false)) === "(_ 10 ((1 _ 2) 3 (4 _ 5)))");
check(formatListInline(insert(data5, 0, 10, true)) === "((1 10 2) 3 (4 _ 5))");
check(formatListInline(insert(data5, 1, 10, false)) === "((1 10 2) 3 (4 _ 5))");
check(formatListInline(insert(data5, 1, 10, true)) === "((1 2 10) 3 (4 _ 5))");
check(formatListInline(insert(data5, 2, 10, false)) === "((1 _ 2) (_ 10 3) (4 _ 5))");
check(formatListInline(insert(data5, 2, 10, true)) === "((1 _ 2) (3 10 _) (4 _ 5))");
check(formatListInline(insert(data5, 3, 10, false)) === "((1 _ 2) 3 (10 4 5))");
check(formatListInline(insert(data5, 3, 10, true)) === "((1 _ 2) 3 (4 10 5))");
check(formatListInline(insert(data5, 4, 10, false)) === "((1 _ 2) 3 (4 10 5))");
check(formatListInline(insert(data5, 4, 10, true)) === "(((1 _ 2) 3 (4 _ 5)) 10 _)");
checkEqual(formatListInline(insert(data5, 0, 10, false)), "(10 ((1 2 _) 3 (4 5 _)) _)");
checkEqual(formatListInline(insert(data5, 0, 10, true)), "((1 10 2) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 1, 10, false)), "((1 10 2) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 1, 10, true)), "((1 2 10) 3 (4 5 _))");
checkEqual(formatListInline(insert(data5, 2, 10, false)), "((1 2 _) (10 3 _) (4 5 _))");
checkEqual(formatListInline(insert(data5, 2, 10, true)), "((1 2 _) (3 10 _) (4 5 _))");
checkEqual(formatListInline(insert(data5, 3, 10, false)), "((1 2 _) 3 (10 4 5))");
checkEqual(formatListInline(insert(data5, 3, 10, true)), "((1 2 _) 3 (4 10 5))");
checkEqual(formatListInline(insert(data5, 4, 10, false)), "((1 2 _) 3 (4 10 5))");
checkEqual(formatListInline(insert(data5, 4, 10, true)), "(((1 2 _) 3 (4 5 _)) 10 _)");

@@ -129,7 +129,7 @@ let origin4 = [1, 2, 3, 4];

check(formatListInline(assocBefore(data4, 3, 10)) === "(1 (2 _ 3) (_ 10 4))");
check(formatListInline(assocAfter(data4, 3, 10)) === "(1 (2 _ 3) (4 10 _))");
checkEqual(formatListInline(assocBefore(data4, 3, 10)), "(1 (2 3 _) (10 4 _))");
checkEqual(formatListInline(assocAfter(data4, 3, 10)), "(1 (2 3 _) (4 10 _))");
check(formatListInline(prepend(data4, 10)) === "((_ 10 1) (2 _ 3) 4)");
check(formatListInline(append(data4, 10)) === "(1 (2 _ 3) (4 10 _))");
checkEqual(formatListInline(prepend(data4, 10)), "((10 1 _) (2 3 _) 4)");
checkEqual(formatListInline(append(data4, 10)), "(1 (2 3 _) (4 10 _))");
});

@@ -144,6 +144,6 @@

check(formatListInline(concat(data1, data2)) === "((1 _ 2) _ (3 _ 4))");
check(formatListInline(concat(initTernaryTreeList<number>([]), data1)) === "(1 _ 2)");
check(formatListInline(concat(data1, data2, data3)) === "((1 _ 2) (3 _ 4) (5 _ 6))");
check(formatListInline(concat(data1, data2, data3, data4)) === "((1 _ 2) ((3 _ 4) _ (5 _ 6)) (7 _ 8))");
check(formatListInline(concat(data1, data2)) === "((1 2 _) (3 4 _) _)");
check(formatListInline(concat(initTernaryTreeList<number>([]), data1)) === "(1 2 _)");
check(formatListInline(concat(data1, data2, data3)) === "((1 2 _) (3 4 _) (5 6 _))");
check(formatListInline(concat(data1, data2, data3, data4)) === "((1 2 _) ((3 4 _) (5 6 _) _) (7 8 _))");

@@ -181,3 +181,3 @@ checkListStructure(concat(data1, data2));

forceListInplaceBalancing(data);
check(formatListInline(data) === "(((0 _ 1) (2 3 4) (5 _ 6)) ((7 _ 8) (9 _ 10) (11 _ 12)) ((13 _ 14) (15 16 17) (18 _ 19)))");
check(formatListInline(data) === "(((0 1 _) (2 3 4) (5 6 _)) ((7 8 _) (9 10 _) (11 12 _)) ((13 14 _) (15 16 17) (18 19 _)))");
// echo data.formatInline

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

test("check(structure)", () => {
test("check structure", () => {
var data = initTernaryTreeList<number>([]);

@@ -208,0 +208,0 @@ for (let idx = 0; idx < 20; idx++) {

34

src/test-map.ts

@@ -13,3 +13,2 @@ import { hashGenerator } from "./types";

contains,
mapGet,
toPairs,

@@ -46,5 +45,7 @@ initEmptyTernaryTreeMap,

let data11 = initTernaryTreeMap<string, number>(inList);
checkMapStructure(data10);
checkMapStructure(data11);
// echo data10
justDisplay(formatMapInline(data10), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (_ 1:11 _)) (8:18 0:10 4:14))");
justDisplay(formatMapInline(data10, true), " ((0:10 1:11 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19))");

@@ -57,5 +58,5 @@ check(deepEqual(toHashSortedPairs(data10), inList));

check(deepEqual(mapGet(data10, "1"), 11));
check(deepEqual(mapGetDefault(data10, "1", null), 11));
check(deepEqual(mapGetDefault(data10, "111", 0), 0));
// check(deepEqual(mapGet(data10, "11"), null)); // should throws error
// check(deepEqual(mapGetDefault(data10, "11", {} as any), null)); // should throws error

@@ -66,3 +67,3 @@ let emptyData: Map<string, number> = new Map();

test("check(structure", () => {
test("check structure", () => {
var dict: Map<string, number> = new Map();

@@ -90,5 +91,6 @@ for (let idx = 0; idx < 100; idx++) {

check(contains(data, "12") == false);
checkMapStructure(data);
justDisplay(formatMapInline(assocMap(data, "1", 2222), false), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (_ 1:2222 _)) (8:18 0:10 4:14))");
justDisplay(formatMapInline(assocMap(data, "23", 2222), false), "((2:12 3:13 7:17) ((_ 9:19 _) (6:16 _ 5:15) (23:2222 1:11 _)) (8:18 0:10 4:14))");
justDisplay(formatMapInline(assocMap(data, "1", 2222), true), "((0:10 1:2222 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19))");
justDisplay(formatMapInline(assocMap(data, "23", 2222), true), "(((0:10 1:11 2:12) (3:13 (4:14 5:15 _) 6:16) (7:17 8:18 9:19)) 23:2222 _)");
});

@@ -103,2 +105,3 @@

let data = initTernaryTreeMap(dict);
checkMapStructure(data);

@@ -128,2 +131,3 @@ // echo data.formatInline

let data = initTernaryTreeMap(dict);
checkMapStructure(data);

@@ -145,2 +149,4 @@ // TODO

let b = dissocMap(data, "3");
checkMapStructure(data);
checkMapStructure(b);

@@ -169,2 +175,3 @@ check(mapEqual(data, data));

let data = initTernaryTreeMap(dict);
checkMapStructure(data);

@@ -190,2 +197,3 @@ var dictB: Map<string, number> = new Map();

let a = initTernaryTreeMap(dict);
checkMapStructure(a);

@@ -197,8 +205,9 @@ var dict2: Map<string, number> = new Map();

let b = initTernaryTreeMap(dict2);
checkMapStructure(b);
let c = mergeSkip(a, b, 11);
check(deepEqual(mapGet(c, "0"), 10));
check(deepEqual(mapGet(c, "1"), 12));
check(deepEqual(mapGet(c, "2"), 13));
check(deepEqual(mapGet(c, "3"), 14));
check(deepEqual(mapGetDefault(c, "0", null), 10));
check(deepEqual(mapGetDefault(c, "1", null), 12));
check(deepEqual(mapGetDefault(c, "2", null), 13));
check(deepEqual(mapGetDefault(c, "3", null), 14));
});

@@ -215,2 +224,3 @@

let data = initTernaryTreeMap(dict);
checkMapStructure(data);

@@ -238,2 +248,3 @@ var i = 0;

let data = initTernaryTreeMap(dict);
checkMapStructure(data);

@@ -262,2 +273,3 @@ var i = 0;

let data3 = mapMapValues(data, (x) => x + 10);
checkMapStructure(data3);

@@ -264,0 +276,0 @@ checkMapStructure(data3);

10

src/utils.ts

@@ -70,2 +70,12 @@ /** by default, it compares by reference

};
/** compare by reference */
export let checkEqual = (x: any, y: any): void => {
if (x !== y) {
console.log("Left: ", x);
console.log("Right: ", y);
throw new Error("Test failed");
}
};
export let justDisplay = (x: any, y: any): void => {

@@ -72,0 +82,0 @@ console.group("Compare:");

lib/bundle.js

Sorry, the diff of this file is too big to display

lib/bundle.js.map

Sorry, the diff of this file is not supported yet

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