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.3-a4 to 0.0.4-a1

8

lib/list.d.ts

@@ -9,9 +9,7 @@ import { TernaryTreeList } from "./types";

export declare function formatListInline<T>(tree: TernaryTreeList<T>): string;
export declare function listToSeq<T>(tree: TernaryTreeList<T>): Array<T>;
export declare function listEach<T>(tree: TernaryTreeList<T>, f: (x: T) => void): void;
export declare function listToItems<T>(tree: TernaryTreeList<T>): Generator<T>;
export declare function findIndex<T>(tree: TernaryTreeList<T>, f: (x: T) => boolean): number;
export declare function indexOf<T>(tree: TernaryTreeList<T>, item: T): number;
export declare function toLeavesSeq<T>(tree: TernaryTreeList<T>): Array<TernaryTreeList<T>>;
export declare function listItems<T>(tree: TernaryTreeList<T>): Generator<T>;
export declare function listPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]>;
export declare function indexToItems<T>(tree: TernaryTreeList<T>): Generator<T>;
export declare function listToPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]>;
export declare function listGet<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T;

@@ -18,0 +16,0 @@ export declare function first<T>(tree: TernaryTreeList<T>): T;

84

lib/list.js

@@ -117,11 +117,7 @@ import { TernaryTreeKind } from "./types";

}
function writeSeq(tree, acc, idx) {
if (tree == null) {
// discard
}
else {
export function* listToItems(tree) {
if (tree != null) {
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf: {
acc[idx.value] = tree.value;
idx.value = idx.value + 1;
yield tree.value;
break;

@@ -131,9 +127,15 @@ }

if (tree.left != null) {
writeSeq(tree.left, acc, idx);
for (let x of listToItems(tree.left)) {
yield x;
}
}
if (tree.middle != null) {
writeSeq(tree.middle, acc, idx);
for (let x of listToItems(tree.middle)) {
yield x;
}
}
if (tree.right != null) {
writeSeq(tree.right, acc, idx);
for (let x of listToItems(tree.right)) {
yield x;
}
}

@@ -145,34 +147,2 @@ break;

}
export function listToSeq(tree) {
let acc = new Array(listLen(tree));
let counter = { value: 0 };
counter.value = 0;
writeSeq(tree, acc, counter);
return acc;
}
export function listEach(tree, f) {
if (tree == null) {
//
}
else {
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf: {
f(tree.value);
break;
}
case TernaryTreeKind.ternaryTreeBranch: {
if (tree.left != null) {
listEach(tree.left, f);
}
if (tree.middle != null) {
listEach(tree.middle, f);
}
if (tree.right != null) {
listEach(tree.right, f);
}
break;
}
}
}
}
// returns -1 if (not foun)

@@ -237,3 +207,3 @@ export function findIndex(tree, f) {

}
function writeLeavesSeq(tree, acc, idx) {
function writeLeavesArray(tree, acc, idx) {
if (tree == null) {

@@ -251,9 +221,9 @@ //

if (tree.left != null) {
writeLeavesSeq(tree.left, acc, idx);
writeLeavesArray(tree.left, acc, idx);
}
if (tree.middle != null) {
writeLeavesSeq(tree.middle, acc, idx);
writeLeavesArray(tree.middle, acc, idx);
}
if (tree.right != null) {
writeLeavesSeq(tree.right, acc, idx);
writeLeavesArray(tree.right, acc, idx);
}

@@ -268,13 +238,9 @@ break;

}
export function toLeavesSeq(tree) {
function toLeavesArray(tree) {
let acc = new Array(listLen(tree));
let counter = { value: 0 };
writeLeavesSeq(tree, acc, counter);
writeLeavesArray(tree, acc, counter);
return acc;
}
// https://forum.nim-lang.org/t/5697
export function* listItems(tree) {
// let seqItems = tree.toSeq()
// for x in seqItems:
// yield x
export function* indexToItems(tree) {
for (let idx = 0; idx < listLen(tree); idx++) {

@@ -284,7 +250,7 @@ yield listGet(tree, idx);

}
export function* listPairs(tree) {
let seqItems = listToSeq(tree);
for (let idx in seqItems) {
let x = seqItems[idx];
yield [parseInt(idx), x];
export function* listToPairs(tree) {
let idx = 0;
for (let x of listToItems(tree)) {
yield [idx, x];
idx = idx + 1;
}

@@ -847,3 +813,3 @@ }

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

@@ -850,0 +816,0 @@ // let newTree = initTernaryTreeList(ys)

18

lib/map.d.ts

@@ -1,7 +0,4 @@

import { TernaryTreeMap, TernaryTreeMapKeyValuePair, Option, Hash } from "./types";
export declare type TernaryTreeMapKeyValuePairOfLeaf<K, V> = {
k: K;
v: TernaryTreeMap<K, V>;
};
import { TernaryTreeMap, Hash, TernaryTreeMapHashEntry } from "./types";
export declare function getMapDepth<K, V>(tree: TernaryTreeMap<K, V>): number;
export declare function initTernaryTreeMapFromHashEntries<K, T>(xs: Array<TernaryTreeMapHashEntry<K, T>>): TernaryTreeMap<K, T>;
export declare function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T>;

@@ -15,12 +12,9 @@ export declare function initEmptyTernaryTreeMap<K, T>(): TernaryTreeMap<K, T>;

export declare function contains<K, T>(tree: TernaryTreeMap<K, T>, item: K, hx?: Hash): boolean;
export declare function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): Option<T>;
export declare function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): T;
export declare function checkMapStructure<K, V>(tree: TernaryTreeMap<K, V>): boolean;
export declare function assocExisted<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T, thisHash?: Hash): TernaryTreeMap<K, T>;
export declare function assocMap<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T, disableBalancing?: boolean): TernaryTreeMap<K, T>;
export declare function dissocMap<K, T>(tree: TernaryTreeMap<K, T>, key: K): TernaryTreeMap<K, T>;
export declare function mapEach<K, T>(tree: TernaryTreeMap<K, T>, f: (k: K, v: T) => void): void;
export declare function toPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<TernaryTreeMapKeyValuePair<K, T>>;
export declare function toPairsIterator<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]>;
export declare function mapKeys<K, T>(tree: TernaryTreeMap<K, T>): Array<K>;
export declare function mapItems<K, T>(tree: TernaryTreeMap<K, T>): Generator<K>;
export declare function toPairs<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]>;
export declare function toKeys<K, V>(tree: TernaryTreeMap<K, V>): Generator<K>;
export declare function toValues<K, V>(tree: TernaryTreeMap<K, V>): Generator<V>;
export declare function mapEqual<K, V>(xs: TernaryTreeMap<K, V>, ys: TernaryTreeMap<K, V>): boolean;

@@ -27,0 +21,0 @@ export declare function merge<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>): TernaryTreeMap<K, T>;

266

lib/map.js

@@ -1,4 +0,5 @@

import { TernaryTreeKind, some, none, hashGenerator, } from "./types";
import { TernaryTreeKind, hashGenerator } from "./types";
import { divideTernarySizes, cmp, dataEqual } from "./utils";
let emptyBranch = null;
let nilResult = null;
function getMax(tree) {

@@ -48,11 +49,11 @@ if (tree == null) {

hash: hashGenerator(k),
elements: [{ k: k, v: v }],
elements: [[k, v]],
};
return result;
}
function createLeafFromPair(item) {
function createLeafFromHashEntry(item) {
let result = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: hashGenerator(item.k),
elements: [item],
hash: item.hash,
elements: item.pairs,
};

@@ -79,10 +80,9 @@ return result;

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

@@ -97,7 +97,7 @@ };

kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: hashGenerator(rightPair.k),
minHash: hashGenerator(leftPair.k),
maxHash: rightPair.hash,
minHash: leftPair.hash,
middle: emptyBranch,
left: leftPair.v,
right: rightPair.v,
left: createLeafFromHashEntry(leftPair),
right: createLeafFromHashEntry(rightPair),
depth: 1,

@@ -113,7 +113,7 @@ };

kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: hashGenerator(rightPair.k),
minHash: hashGenerator(leftPair.k),
left: leftPair.v,
middle: middlePair.v,
right: rightPair.v,
maxHash: rightPair.hash,
minHash: leftPair.hash,
left: createLeafFromHashEntry(leftPair),
middle: createLeafFromHashEntry(middlePair),
right: createLeafFromHashEntry(rightPair),
depth: 1,

@@ -141,21 +141,32 @@ };

}
function initTernaryTreeMapFromPairs(xs) {
let leavesList = xs.map((pair) => {
return { k: pair.k, v: createLeafFromPair(pair) };
});
return makeTernaryTreeMap(leavesList.length, 0, leavesList);
export function initTernaryTreeMapFromHashEntries(xs) {
return makeTernaryTreeMap(xs.length, 0, xs);
}
export function initTernaryTreeMap(t) {
let xs = new Array(t.size);
let idx = 0;
let groupBuffers = new Map();
for (let [k, v] of t) {
xs[idx] = { k, v };
idx = idx + 1;
let h = hashGenerator(k);
if (groupBuffers.has(h)) {
let branch = groupBuffers.get(h);
if (branch != null) {
branch.push([k, v]);
}
else {
throw new Error("Expected referece to pairs");
}
}
else {
groupBuffers.set(h, [[k, v]]);
}
}
let ys = xs.sort((x, y) => {
let hx = hashGenerator(x.k);
let hy = hashGenerator(y.k);
return cmp(hx, hy);
let xs = [...groupBuffers.keys()].sort(cmp).map((h) => {
let pairs = groupBuffers.get(h);
if (pairs != null) {
return { hash: h, pairs: pairs };
}
else {
throw new Error("Expected reference to paris");
}
});
let result = initTernaryTreeMapFromPairs(ys);
let result = initTernaryTreeMapFromHashEntries(xs);
// checkMapStructure(result);

@@ -200,6 +211,6 @@ return result;

if (withHash) {
return `${tree.hash}->${tree.elements[0].k}:${tree.elements[0].v}`; // TODO show whole list
return `${tree.hash}->${tree.elements[0][0]}:${tree.elements[0][1]}`; // TODO show whole list
}
else {
return `${tree.elements[0].k}:${tree.elements[0].v}`;
return `${tree.elements[0][0]}:${tree.elements[0][1]}`;
}

@@ -226,3 +237,3 @@ case TernaryTreeKind.ternaryTreeBranch: {

}
function collectHashSortedSeq(tree, acc, idx) {
function collectHashSortedArray(tree, acc, idx) {
if (tree == null || isMapEmpty(tree)) {

@@ -235,3 +246,3 @@ // discard

for (let item of tree.elements) {
acc[idx.value] = [item.k, item.v];
acc[idx.value] = item;
idx.value = idx.value + 1;

@@ -242,5 +253,5 @@ }

case TernaryTreeKind.ternaryTreeBranch: {
collectHashSortedSeq(tree.left, acc, idx);
collectHashSortedSeq(tree.middle, acc, idx);
collectHashSortedSeq(tree.right, acc, idx);
collectHashSortedArray(tree.left, acc, idx);
collectHashSortedArray(tree.middle, acc, idx);
collectHashSortedArray(tree.right, acc, idx);
break;

@@ -257,6 +268,6 @@ }

let idx = { value: 0 };
collectHashSortedSeq(tree, acc, idx);
collectHashSortedArray(tree, acc, idx);
return acc;
}
function collectHashSortedSeqOfLeaf(tree, acc, idx) {
function collectOrderedHashEntries(tree, acc, idx) {
if (tree == null || isMapEmpty(tree)) {

@@ -268,17 +279,10 @@ // discard

case TernaryTreeKind.ternaryTreeLeaf: {
for (let pair of tree.elements) {
let item = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: tree.hash,
elements: [pair],
};
acc[idx.value] = { k: pair.k, v: item };
idx.value = idx.value + 1;
}
acc[idx.value] = { hash: tree.hash, pairs: tree.elements };
idx.value = idx.value + 1;
break;
}
case TernaryTreeKind.ternaryTreeBranch: {
collectHashSortedSeqOfLeaf(tree.left, acc, idx);
collectHashSortedSeqOfLeaf(tree.middle, acc, idx);
collectHashSortedSeqOfLeaf(tree.right, acc, idx);
collectOrderedHashEntries(tree.left, acc, idx);
collectOrderedHashEntries(tree.middle, acc, idx);
collectOrderedHashEntries(tree.right, acc, idx);
break;

@@ -292,8 +296,7 @@ }

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

@@ -311,3 +314,3 @@ }

let pair = tree.elements[idx];
if (dataEqual(pair.k, item)) {
if (dataEqual(pair[0], item)) {
return true;

@@ -340,7 +343,7 @@ }

for (let pair of tree.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
if (dataEqual(pair[0], item)) {
return pair[1];
}
}
return none();
return nilResult;
}

@@ -353,7 +356,7 @@ // echo "looking for: ", hx, " ", item, " in ", tree.formatInline

for (let pair of branch.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
if (dataEqual(pair[0], item)) {
return pair[1];
}
}
return none();
return nilResult;
}

@@ -367,5 +370,5 @@ }

}
return none();
return nilResult;
}
return none();
return nilResult;
}

@@ -377,3 +380,6 @@ // leaves on the left has smaller hashes

for (let pair of tree.elements) {
if (tree.hash !== hashGenerator(pair.k)) {
if (pair.length !== 2) {
throw new Error("Expected pair to br [k,v] :" + pair);
}
if (tree.hash !== hashGenerator(pair[0])) {
throw new Error(`Bad hash at leaf node ${tree}`);

@@ -426,3 +432,3 @@ }

}
export function assocExisted(tree, key, item, thisHash = null) {
function assocExisted(tree, key, item, thisHash = null) {
if (tree == null || isMapEmpty(tree)) {

@@ -440,4 +446,4 @@ throw new Error("Cannot call assoc on nil");

let pair = tree.elements[idx];
if (dataEqual(pair.k, key)) {
newPairs[idx] = { k: key, v: item };
if (dataEqual(pair[0], key)) {
newPairs[idx] = [key, item];
replaced = true;

@@ -515,3 +521,3 @@ }

for (let pair of tree.elements) {
if (dataEqual(pair.k, key)) {
if (dataEqual(pair[0], key)) {
throw new Error("Unexpected existed key in assoc");

@@ -525,3 +531,3 @@ }

}
newPairs[tree.elements.length] = { k: key, v: item };
newPairs[tree.elements.length] = [key, item];
}

@@ -533,3 +539,3 @@ else {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -551,3 +557,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -574,3 +580,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -592,3 +598,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -611,3 +617,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -629,3 +635,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -650,3 +656,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -668,3 +674,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -687,3 +693,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -705,3 +711,3 @@ let result = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -815,3 +821,3 @@ let result = {

for (let pair of tree.elements) {
if (!dataEqual(pair.k, key)) {
if (!dataEqual(pair[0], key)) {
newPairs.push(pair);

@@ -908,70 +914,28 @@ }

}
export function mapEach(tree, f) {
if (tree == null) {
return;
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
f(pair.k, pair.v);
export function* toPairs(tree) {
if (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
yield pair;
}
}
}
else {
mapEach(tree.left, f);
mapEach(tree.middle, f);
mapEach(tree.right, f);
}
}
export function toPairs(tree) {
let result = [];
if (tree == null) {
return [];
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
result.push(pair);
}
}
else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
result.push(item);
else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
yield item;
}
}
}
}
return result;
}
export function* toPairsIterator(tree) {
let seqItems = toHashSortedPairs(tree);
for (let item of seqItems) {
yield item;
export function* toKeys(tree) {
for (let item of toPairs(tree)) {
yield item[0];
}
}
export function mapKeys(tree) {
let result = [];
if (tree == null) {
return [];
export function* toValues(tree) {
for (let item of toPairs(tree)) {
yield item[1];
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
result.push(pair.k);
}
}
else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of mapKeys(branch)) {
result.push(item);
}
}
}
return result;
}
export function* mapItems(tree) {
let seqItems = mapKeys(tree);
for (let x of seqItems) {
yield x;
}
}
function pairToString(p) {
return `${p.k}:${p.v}`;
}
export function mapEqual(xs, ys) {

@@ -987,11 +951,7 @@ if (xs === ys) {

}
let keys = mapKeys(xs);
for (let key of keys) {
for (let key of toKeys(xs)) {
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
if (vx.existed !== vy.existed) {
return false;
}
// TODO compare deep structures
if (!dataEqual(vx.value, vy.value)) {
if (!dataEqual(vx, vy)) {
return false;

@@ -1005,3 +965,3 @@ }

let counted = 0;
mapEach(ys, (key, item) => {
for (let [key, item] of toPairs(ys)) {
ret = assocMap(ret, key, item);

@@ -1016,3 +976,3 @@ // # TODO pickd loop by experience

}
});
}
return ret;

@@ -1024,5 +984,5 @@ }

let counted = 0;
mapEach(ys, (key, item) => {
for (let [key, item] of toPairs(ys)) {
if (dataEqual(item, skipped)) {
return;
continue;
}

@@ -1038,3 +998,3 @@ ret = assocMap(ret, key, item);

}
});
}
return ret;

@@ -1046,3 +1006,3 @@ }

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

@@ -1049,0 +1009,0 @@ tree.left = newTree.left;

19

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, listGet, insert, initEmptyTernaryTreeList, last, listLen, forceListInplaceBalancing, listEqual, } from "./list";
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, } from "./list";
import { test, check, arrayEqual } from "./utils";

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

check(formatListInline(data11) == "((1 (2 _ 3) 4) (5 6 7) (8 (9 _ 10) 11))");
check(arrayEqual(origin11, listToSeq(data11)));
check(arrayEqual(origin11, [...listToItems(data11)]));
check(arrayEqual([...listToItems(data11)], [...indexToItems(data11)]));
let emptyXs = new Array(0);

@@ -105,3 +106,3 @@ check(listEqual(initEmptyTernaryTreeList(), initTernaryTreeList(emptyXs)));

var i = 0;
for (let item of listItems(data4)) {
for (let item of listToItems(data4)) {
i = i + 1;

@@ -111,3 +112,3 @@ }

i = 0;
for (let [idx, item] of listPairs(data4)) {
for (let [idx, item] of listToPairs(data4)) {
i = i + idx;

@@ -138,3 +139,3 @@ }

for (let j = i; j < 40; j++) {
check(arrayEqual(listToSeq(slice(data, i, j)), list40.slice(i, j)));
check(arrayEqual([...listToItems(slice(data, i, j))], list40.slice(i, j)));
}

@@ -146,11 +147,11 @@ }

let reversedData = reverse(data);
check(arrayEqual(listToSeq(data).reverse(), listToSeq(reversedData)));
check(arrayEqual([...listToItems(data)].reverse(), [...listToItems(reversedData)]));
check(checkListStructure(reversedData));
});
test("list each", () => {
test("list traverse", () => {
var i = 0;
let data = initTernaryTreeList([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
listEach(data, (x) => {
for (let x of listToItems(data)) {
i = i + 1;
});
}
check(i == 10);

@@ -157,0 +158,0 @@ });

26

lib/test-map.js

@@ -1,4 +0,4 @@

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

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

check(contains(data10, "11") == false);
check(deepEqual(mapGet(data10, "1"), some(11)));
check(deepEqual(mapGet(data10, "11"), none()));
check(deepEqual(mapGet(data10, "1"), 11));
check(deepEqual(mapGet(data10, "11"), null));
let emptyData = new Map();

@@ -77,3 +77,3 @@ check(mapEqual(initEmptyTernaryTreeMap(), initTernaryTreeMap(emptyData)));

// justDisplay((mapToString(toPairs(data))) , "@[2:12, 3:13, 7:17, 9:19, 6:16, 5:15, 1:11, 8:18, 0:10, 4:14]")
justDisplay(mapKeys(data), ["2", "3", "7", "9", "6", "5", "1", "8", "0", "4"]);
justDisplay([...toKeys(data)], ["2", "3", "7", "9", "6", "5", "1", "8", "0", "4"]);
});

@@ -127,6 +127,6 @@ test("Equality", () => {

let c = mergeSkip(a, b, 11);
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)));
check(deepEqual(mapGet(c, "0"), 10));
check(deepEqual(mapGet(c, "1"), 12));
check(deepEqual(mapGet(c, "2"), 13));
check(deepEqual(mapGet(c, "3"), 14));
});

@@ -142,3 +142,3 @@ test("iterator", () => {

var i = 0;
for (let [k, v] of toPairsIterator(data)) {
for (let [k, v] of toPairs(data)) {
i = i + 1;

@@ -148,3 +148,3 @@ }

i = 0;
for (let key of toPairsIterator(data)) {
for (let key of toPairs(data)) {
i = i + 1;

@@ -161,8 +161,8 @@ }

var i = 0;
mapEach(data, (k, v) => {
for (let [k, v] of toPairs(data)) {
// echo "..{k}-{v}.."
i = i + 1;
});
}
check(i == 100);
});
};

14

lib/types.d.ts

@@ -19,5 +19,5 @@ export declare enum TernaryTreeKind {

export declare type TernaryTreeList<T> = TernaryTreeListTheBranch<T> | TernaryTreeListTheLeaf<T>;
export declare type TernaryTreeMapKeyValuePair<K, V> = {
k: K;
v: V;
export declare type TernaryTreeMapHashEntry<K, V> = {
hash: Hash;
pairs: Array<[K, V]>;
};

@@ -36,3 +36,3 @@ export declare type TernaryTreeMapTheBranch<K, T> = {

hash: number;
elements: Array<TernaryTreeMapKeyValuePair<K, T>>;
elements: Array<[K, T]>;
};

@@ -43,8 +43,2 @@ export declare type TernaryTreeMap<K, T> = TernaryTreeMapTheBranch<K, T> | TernaryTreeMapTheLeaf<K, T>;

};
export declare type Option<T> = {
existed: boolean;
value: T;
};
export declare function none<T>(): Option<T>;
export declare function some<T>(v: T): Option<T>;
export declare type Hash = number;

@@ -51,0 +45,0 @@ export declare let valueHash: (x: any) => Hash;

14

lib/types.js

@@ -6,16 +6,2 @@ export var TernaryTreeKind;

})(TernaryTreeKind || (TernaryTreeKind = {}));
export function none() {
let result = {
existed: false,
value: null,
};
return result;
}
export function some(v) {
let result = {
existed: true,
value: v,
};
return result;
}
export let valueHash = (x) => {

@@ -22,0 +8,0 @@ if (typeof x === "number") {

2

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

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

85

README.md
## ternary-tree in TypeScript
_TODO_
> ported from [ternary-tree](https://github.com/calcit-lang/ternary-tree), providing a ternary tree based persistent data structure.
### APIs
![npm](https://img.shields.io/npm/v/@calcit/ternary-tree?style=flat-square)
Map functions:
```ts
export function initTernaryTreeMapFromHashEntries<K, T>(xs: Array<TernaryTreeMapHashEntry<K, T>>): TernaryTreeMap<K, T>;
export function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T>;
export function initEmptyTernaryTreeMap<K, T>(): TernaryTreeMap<K, T>;
export function mapLen<K, V>(tree: TernaryTreeMap<K, V>): number;
export function isMapEmpty<K, V>(tree: TernaryTreeMap<K, V>): boolean;
export function contains<K, T>(tree: TernaryTreeMap<K, T>, item: K, hx: Hash = null as any): boolean;
export function mapEqual<K, V>(xs: TernaryTreeMap<K, V>, ys: TernaryTreeMap<K, V>): boolean;
export function mapGet<K, T>(originalTree: TernaryTreeMap<K, T>, item: K): T;
export function* toPairs<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]>;
export function* toKeys<K, V>(tree: TernaryTreeMap<K, V>): Generator<K>;
export function* toValues<K, V>(tree: TernaryTreeMap<K, V>): Generator<V>;
export function assocMap<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T, disableBalancing: boolean = false): TernaryTreeMap<K, T>;
export function dissocMap<K, T>(tree: TernaryTreeMap<K, T>, key: K): TernaryTreeMap<K, T>;
export function merge<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>): TernaryTreeMap<K, T>;
export function mergeSkip<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>, skipped: T): TernaryTreeMap<K, T>;
export function toHashSortedPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<[K, T]>;
export function mapToString<K, V>(tree: TernaryTreeMap<K, V>): string;
export function formatMapInline<K, V>(tree: TernaryTreeMap<K, V>, withHash: boolean = false): string;
export function checkMapStructure<K, V>(tree: TernaryTreeMap<K, V>): boolean;
export function getMapDepth<K, V>(tree: TernaryTreeMap<K, V>): number;
export function forceMapInplaceBalancing<K, T>(tree: TernaryTreeMap<K, T>): void;
export function sameMapShape<K, T>(xs: TernaryTreeMap<K, T>, ys: TernaryTreeMap<K, T>): boolean;
```
List functions:
```ts
function makeTernaryTreeList<T>(size: number, offset: number, xs: /* var */ Array<TernaryTreeList<T>>): TernaryTreeList<T>;
function initTernaryTreeList<T>(xs: Array<T>): TernaryTreeList<T>;
function initEmptyTernaryTreeList<T>(): TernaryTreeList<T>;
function* listToItems<T>(tree: TernaryTreeList<T>): Generator<T>;
function* indexToItems<T>(tree: TernaryTreeList<T>): Generator<T>;
function* listToPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]>;
function listLen<T>(tree: TernaryTreeList<T>): number;
function listEqual<T>(xs: TernaryTreeList<T>, ys: TernaryTreeList<T>): boolean;
function listGet<T>(originalTree: TernaryTreeList<T>, originalIdx: number): T;
function first<T>(tree: TernaryTreeList<T>): T;
function last<T>(tree: TernaryTreeList<T>): T;
function slice<T>(tree: TernaryTreeList<T>, startIdx: number, endIdx: number): TernaryTreeList<T>;
function findIndex<T>(tree: TernaryTreeList<T>, f: (x: T) => boolean): number;
function indexOf<T>(tree: TernaryTreeList<T>, item: T): number;
function assocList<T>(tree: TernaryTreeList<T>, idx: number, item: T): TernaryTreeList<T>;
function dissocList<T>(tree: TernaryTreeList<T>, idx: number): TernaryTreeList<T>;
function rest<T>(tree: TernaryTreeList<T>): TernaryTreeList<T>;
function butlast<T>(tree: TernaryTreeList<T>): TernaryTreeList<T>;
function insert<T>(tree: TernaryTreeList<T>, idx: number, item: T, after: boolean = false): TernaryTreeList<T>;
function assocBefore<T>(tree: TernaryTreeList<T>, idx: number, item: T, after: boolean = false): TernaryTreeList<T>;
function assocAfter<T>(tree: TernaryTreeList<T>, idx: number, item: T, after: boolean = false): TernaryTreeList<T>;
function prepend<T>(tree: TernaryTreeList<T>, item: T, disableBalancing: boolean = false): TernaryTreeList<T>;
function append<T>(tree: TernaryTreeList<T>, item: T, disableBalancing: boolean = false): TernaryTreeList<T>;
function concat<T>(xs: TernaryTreeList<T>, ys: TernaryTreeList<T>): TernaryTreeList<T>;
function reverse<T>(tree: TernaryTreeList<T>): TernaryTreeList<T>;
function sameListShape<T>(xs: TernaryTreeList<T>, ys: TernaryTreeList<T>): boolean;
function getDepth<T>(tree: TernaryTreeList<T>): number;
function listToString<T>(tree: TernaryTreeList<T>): string;
function formatListInline<T>(tree: TernaryTreeList<T>): string;
function checkListStructure<T>(tree: TernaryTreeList<T>): boolean;
function forceListInplaceBalancing<T>(tree: TernaryTreeList<T>): void;
```
To overwrite internals behaviors:
```ts
overwriteHashGenerator(f);
overwriteComparator(f);
```
### License
MIT

87

src/list.ts

@@ -128,10 +128,7 @@ import { RefInt, TernaryTreeKind, TernaryTreeList, TernaryTreeListTheBranch } from "./types";

function writeSeq<T>(tree: TernaryTreeList<T>, acc: /* var */ Array<T>, idx: RefInt): void {
if (tree == null) {
// discard
} else {
export function* listToItems<T>(tree: TernaryTreeList<T>): Generator<T> {
if (tree != null) {
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf: {
acc[idx.value] = tree.value;
idx.value = idx.value + 1;
yield tree.value;
break;

@@ -141,9 +138,15 @@ }

if (tree.left != null) {
writeSeq(tree.left, acc, idx);
for (let x of listToItems(tree.left)) {
yield x;
}
}
if (tree.middle != null) {
writeSeq(tree.middle, acc, idx);
for (let x of listToItems(tree.middle)) {
yield x;
}
}
if (tree.right != null) {
writeSeq(tree.right, acc, idx);
for (let x of listToItems(tree.right)) {
yield x;
}
}

@@ -156,35 +159,2 @@ break;

export function listToSeq<T>(tree: TernaryTreeList<T>): Array<T> {
let acc = new Array<T>(listLen(tree));
let counter: RefInt = { value: 0 };
counter.value = 0;
writeSeq(tree, acc, counter);
return acc;
}
export function listEach<T>(tree: TernaryTreeList<T>, f: (x: T) => void): void {
if (tree == null) {
//
} else {
switch (tree.kind) {
case TernaryTreeKind.ternaryTreeLeaf: {
f(tree.value);
break;
}
case TernaryTreeKind.ternaryTreeBranch: {
if (tree.left != null) {
listEach(tree.left, f);
}
if (tree.middle != null) {
listEach(tree.middle, f);
}
if (tree.right != null) {
listEach(tree.right, f);
}
break;
}
}
}
}
// returns -1 if (not foun)

@@ -250,3 +220,3 @@ export function findIndex<T>(tree: TernaryTreeList<T>, f: (x: T) => boolean): number {

function writeLeavesSeq<T>(tree: TernaryTreeList<T>, acc: /* var */ Array<TernaryTreeList<T>>, idx: RefInt): void {
function writeLeavesArray<T>(tree: TernaryTreeList<T>, acc: /* var */ Array<TernaryTreeList<T>>, idx: RefInt): void {
if (tree == null) {

@@ -263,9 +233,9 @@ //

if (tree.left != null) {
writeLeavesSeq(tree.left, acc, idx);
writeLeavesArray(tree.left, acc, idx);
}
if (tree.middle != null) {
writeLeavesSeq(tree.middle, acc, idx);
writeLeavesArray(tree.middle, acc, idx);
}
if (tree.right != null) {
writeLeavesSeq(tree.right, acc, idx);
writeLeavesArray(tree.right, acc, idx);
}

@@ -281,16 +251,10 @@ break;

export function toLeavesSeq<T>(tree: TernaryTreeList<T>): Array<TernaryTreeList<T>> {
function toLeavesArray<T>(tree: TernaryTreeList<T>): Array<TernaryTreeList<T>> {
let acc = new Array<TernaryTreeList<T>>(listLen(tree));
let counter: RefInt = { value: 0 };
writeLeavesSeq(tree, acc, counter);
writeLeavesArray(tree, acc, counter);
return acc;
}
// https://forum.nim-lang.org/t/5697
export function* listItems<T>(tree: TernaryTreeList<T>): Generator<T> {
// let seqItems = tree.toSeq()
// for x in seqItems:
// yield x
export function* indexToItems<T>(tree: TernaryTreeList<T>): Generator<T> {
for (let idx = 0; idx < listLen(tree); idx++) {

@@ -301,8 +265,7 @@ yield listGet(tree, idx);

export function* listPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]> {
let seqItems = listToSeq(tree);
for (let idx in seqItems) {
let x = seqItems[idx];
yield [parseInt(idx), x];
export function* listToPairs<T>(tree: TernaryTreeList<T>): Generator<[number, T]> {
let idx = 0;
for (let x of listToItems(tree)) {
yield [idx, x];
idx = idx + 1;
}

@@ -881,3 +844,3 @@ }

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

@@ -884,0 +847,0 @@ // let newTree = initTernaryTreeList(ys)

302

src/map.ts

@@ -1,22 +0,6 @@

import {
TernaryTreeMap,
TernaryTreeKind,
TernaryTreeMapTheLeaf,
TernaryTreeMapTheBranch,
TernaryTreeMapKeyValuePair,
RefInt,
Option,
some,
none,
Hash,
hashGenerator,
} from "./types";
import { TernaryTreeMap, TernaryTreeKind, TernaryTreeMapTheLeaf, TernaryTreeMapTheBranch, RefInt, Hash, hashGenerator, TernaryTreeMapHashEntry } from "./types";
import { divideTernarySizes, roughIntPow, cmp, dataEqual } from "./utils";
export type TernaryTreeMapKeyValuePairOfLeaf<K, V> = {
k: K;
v: TernaryTreeMap<K, V>;
};
let emptyBranch: TernaryTreeMap<any, any> = null as any;
let nilResult = null as any;

@@ -70,3 +54,3 @@ function getMax<K, V>(tree: TernaryTreeMap<K, V>): Hash {

hash: hashGenerator(k),
elements: [{ k: k, v: v }],
elements: [[k, v]],
};

@@ -76,7 +60,7 @@ return result;

function createLeafFromPair<K, T>(item: TernaryTreeMapKeyValuePair<K, T>): TernaryTreeMap<K, T> {
function createLeafFromHashEntry<K, T>(item: TernaryTreeMapHashEntry<K, T>): TernaryTreeMap<K, T> {
let result: TernaryTreeMap<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: hashGenerator(item.k),
elements: [item],
hash: item.hash,
elements: item.pairs,
};

@@ -88,3 +72,3 @@ return result;

// pairs must be sorted before passing to proc.
function makeTernaryTreeMap<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<TernaryTreeMapHashEntry<K, T>>): TernaryTreeMap<K, T> {
switch (size) {

@@ -105,10 +89,9 @@ case 0: {

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

@@ -123,7 +106,7 @@ };

kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: hashGenerator(rightPair.k),
minHash: hashGenerator(leftPair.k),
maxHash: rightPair.hash,
minHash: leftPair.hash,
middle: emptyBranch,
left: leftPair.v,
right: rightPair.v,
left: createLeafFromHashEntry(leftPair),
right: createLeafFromHashEntry(rightPair),
depth: 1,

@@ -139,7 +122,7 @@ };

kind: TernaryTreeKind.ternaryTreeBranch,
maxHash: hashGenerator(rightPair.k),
minHash: hashGenerator(leftPair.k),
left: leftPair.v,
middle: middlePair.v,
right: rightPair.v,
maxHash: rightPair.hash,
minHash: leftPair.hash,
left: createLeafFromHashEntry(leftPair),
middle: createLeafFromHashEntry(middlePair),
right: createLeafFromHashEntry(rightPair),
depth: 1,

@@ -170,27 +153,32 @@ };

function initTernaryTreeMapFromPairs<K, T>(xs: Array<TernaryTreeMapKeyValuePair<K, T>>): TernaryTreeMap<K, T> {
let leavesList = xs.map(
(pair: TernaryTreeMapKeyValuePair<K, T>): TernaryTreeMapKeyValuePairOfLeaf<K, T> => {
return { k: pair.k, v: createLeafFromPair<K, T>(pair) };
}
);
return makeTernaryTreeMap(leavesList.length, 0, leavesList);
export function initTernaryTreeMapFromHashEntries<K, T>(xs: Array<TernaryTreeMapHashEntry<K, T>>): TernaryTreeMap<K, T> {
return makeTernaryTreeMap(xs.length, 0, xs);
}
export function initTernaryTreeMap<K, T>(t: Map<K, T>): TernaryTreeMap<K, T> {
let xs = new Array<TernaryTreeMapKeyValuePair<K, T>>(t.size);
let idx = 0;
let groupBuffers: Map<number, Array<[K, T]>> = new Map();
for (let [k, v] of t) {
xs[idx] = { k, v };
idx = idx + 1;
let h = hashGenerator(k);
if (groupBuffers.has(h)) {
let branch = groupBuffers.get(h);
if (branch != null) {
branch.push([k, v]);
} else {
throw new Error("Expected referece to pairs");
}
} else {
groupBuffers.set(h, [[k, v]]);
}
}
let ys = xs.sort((x, y: TernaryTreeMapKeyValuePair<K, T>): number => {
let hx = hashGenerator(x.k);
let hy = hashGenerator(y.k);
return cmp(hx, hy);
let xs: Array<TernaryTreeMapHashEntry<K, T>> = [...groupBuffers.keys()].sort(cmp).map((h) => {
let pairs = groupBuffers.get(h);
if (pairs != null) {
return { hash: h, pairs: pairs };
} else {
throw new Error("Expected reference to paris");
}
});
let result = initTernaryTreeMapFromPairs(ys);
let result = initTernaryTreeMapFromHashEntries(xs);
// checkMapStructure(result);

@@ -239,5 +227,5 @@ return result;

if (withHash) {
return `${tree.hash}->${tree.elements[0].k}:${tree.elements[0].v}`; // TODO show whole list
return `${tree.hash}->${tree.elements[0][0]}:${tree.elements[0][1]}`; // TODO show whole list
} else {
return `${tree.elements[0].k}:${tree.elements[0].v}`;
return `${tree.elements[0][0]}:${tree.elements[0][1]}`;
}

@@ -267,3 +255,3 @@ case TernaryTreeKind.ternaryTreeBranch: {

function collectHashSortedSeq<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<[K, T]>, idx: RefInt): void {
function collectHashSortedArray<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<[K, T]>, idx: RefInt): void {
if (tree == null || isMapEmpty(tree)) {

@@ -275,3 +263,3 @@ // discard

for (let item of tree.elements) {
acc[idx.value] = [item.k, item.v];
acc[idx.value] = item;
idx.value = idx.value + 1;

@@ -282,5 +270,5 @@ }

case TernaryTreeKind.ternaryTreeBranch: {
collectHashSortedSeq(tree.left, acc, idx);
collectHashSortedSeq(tree.middle, acc, idx);
collectHashSortedSeq(tree.right, acc, idx);
collectHashSortedArray(tree.left, acc, idx);
collectHashSortedArray(tree.middle, acc, idx);
collectHashSortedArray(tree.right, acc, idx);
break;

@@ -298,7 +286,7 @@ }

let idx: RefInt = { value: 0 };
collectHashSortedSeq(tree, acc, idx);
collectHashSortedArray(tree, acc, idx);
return acc;
}
function collectHashSortedSeqOfLeaf<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>, idx: RefInt): void {
function collectOrderedHashEntries<K, T>(tree: TernaryTreeMap<K, T>, acc: /* var */ Array<TernaryTreeMapHashEntry<K, T>>, idx: RefInt): void {
if (tree == null || isMapEmpty(tree)) {

@@ -309,17 +297,10 @@ // discard

case TernaryTreeKind.ternaryTreeLeaf: {
for (let pair of tree.elements) {
let item: TernaryTreeMap<K, T> = {
kind: TernaryTreeKind.ternaryTreeLeaf,
hash: tree.hash, // TODO
elements: [pair],
};
acc[idx.value] = { k: pair.k, v: item };
idx.value = idx.value + 1;
}
acc[idx.value] = { hash: tree.hash, pairs: tree.elements };
idx.value = idx.value + 1;
break;
}
case TernaryTreeKind.ternaryTreeBranch: {
collectHashSortedSeqOfLeaf(tree.left, acc, idx);
collectHashSortedSeqOfLeaf(tree.middle, acc, idx);
collectHashSortedSeqOfLeaf(tree.right, acc, idx);
collectOrderedHashEntries(tree.left, acc, idx);
collectOrderedHashEntries(tree.middle, acc, idx);
collectOrderedHashEntries(tree.right, acc, idx);
break;

@@ -334,8 +315,7 @@ }

// 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>> {
let acc = new Array<TernaryTreeMapKeyValuePairOfLeaf<K, T>>(mapLen(tree));
function toOrderedHashEntries<K, T>(tree: TernaryTreeMap<K, T>): Array<TernaryTreeMapHashEntry<K, T>> {
let acc = new Array<TernaryTreeMapHashEntry<K, T>>(mapLen(tree));
let idx: RefInt = { value: 0 };
collectHashSortedSeqOfLeaf(tree, acc, idx);
collectOrderedHashEntries(tree, acc, idx);
return acc;

@@ -356,3 +336,3 @@ }

let pair = tree.elements[idx];
if (dataEqual(pair.k, item)) {
if (dataEqual(pair[0], item)) {
return true;

@@ -381,3 +361,3 @@ }

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

@@ -390,7 +370,7 @@

for (let pair of tree.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
if (dataEqual(pair[0], item)) {
return pair[1];
}
}
return none();
return nilResult;
}

@@ -405,7 +385,7 @@

for (let pair of branch.elements) {
if (dataEqual(pair.k, item)) {
return some(pair.v);
if (dataEqual(pair[0], item)) {
return pair[1];
}
}
return none();
return nilResult;
}

@@ -419,6 +399,6 @@ } else if (hx >= branch.minHash && hx <= branch.maxHash) {

return none();
return nilResult;
}
return none();
return nilResult;
}

@@ -431,3 +411,6 @@

for (let pair of tree.elements) {
if (tree.hash !== hashGenerator(pair.k)) {
if (pair.length !== 2) {
throw new Error("Expected pair to br [k,v] :" + pair);
}
if (tree.hash !== hashGenerator(pair[0])) {
throw new Error(`Bad hash at leaf node ${tree}`);

@@ -483,3 +466,3 @@ }

export function assocExisted<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T, thisHash: Hash = null as any): TernaryTreeMap<K, T> {
function assocExisted<K, T>(tree: TernaryTreeMap<K, T>, key: K, item: T, thisHash: Hash = null as any): TernaryTreeMap<K, T> {
if (tree == null || isMapEmpty(tree)) {

@@ -495,8 +478,8 @@ throw new Error("Cannot call assoc on nil");

}
let newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length);
let newPairs = new Array<[K, T]>(tree.elements.length);
let replaced = false;
for (let idx in tree.elements) {
let pair = tree.elements[idx];
if (dataEqual(pair.k, key)) {
newPairs[idx] = { k: key, v: item };
if (dataEqual(pair[0], key)) {
newPairs[idx] = [key, item];
replaced = true;

@@ -576,7 +559,7 @@ } else {

for (let pair of tree.elements) {
if (dataEqual(pair.k, key)) {
if (dataEqual(pair[0], key)) {
throw new Error("Unexpected existed key in assoc");
}
}
let newPairs = new Array<TernaryTreeMapKeyValuePair<K, T>>(tree.elements.length + 1);
let newPairs = new Array<[K, T]>(tree.elements.length + 1);
for (let idx in tree.elements) {

@@ -586,3 +569,3 @@ let pair = tree.elements[idx];

}
newPairs[tree.elements.length] = { k: key, v: item };
newPairs[tree.elements.length] = [key, item];
} else {

@@ -593,3 +576,3 @@ if (thisHash > tree.hash) {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -610,3 +593,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -632,3 +615,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -649,3 +632,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -667,3 +650,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -684,3 +667,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -706,3 +689,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -723,3 +706,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -741,3 +724,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -759,3 +742,3 @@ let result: TernaryTreeMapTheBranch<K, T> = {

hash: thisHash,
elements: [{ k: key, v: item }],
elements: [[key, item]],
};

@@ -874,5 +857,5 @@ let result: TernaryTreeMapTheBranch<K, T> = {

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

@@ -974,77 +957,29 @@ }

export function mapEach<K, T>(tree: TernaryTreeMap<K, T>, f: (k: K, v: T) => void): void {
if (tree == null) {
return;
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
f(pair.k, pair.v);
}
} else {
mapEach(tree.left, f);
mapEach(tree.middle, f);
mapEach(tree.right, f);
}
}
export function toPairs<K, T>(tree: TernaryTreeMap<K, T>): Array<TernaryTreeMapKeyValuePair<K, T>> {
let result: Array<TernaryTreeMapKeyValuePair<K, T>> = [];
if (tree == null) {
return [];
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
result.push(pair);
}
} else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
result.push(item);
export function* toPairs<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]> {
if (tree != null) {
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
yield pair;
}
} else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of toPairs(branch)) {
yield item;
}
}
}
}
return result;
}
export function* toPairsIterator<K, T>(tree: TernaryTreeMap<K, T>): Generator<[K, T]> {
let seqItems = toHashSortedPairs(tree);
for (let item of seqItems) {
yield item;
export function* toKeys<K, V>(tree: TernaryTreeMap<K, V>): Generator<K> {
for (let item of toPairs(tree)) {
yield item[0];
}
}
export function mapKeys<K, T>(tree: TernaryTreeMap<K, T>): Array<K> {
let result: Array<K> = [];
if (tree == null) {
return [];
export function* toValues<K, V>(tree: TernaryTreeMap<K, V>): Generator<V> {
for (let item of toPairs(tree)) {
yield item[1];
}
if (tree.kind === TernaryTreeKind.ternaryTreeLeaf) {
for (let pair of tree.elements) {
result.push(pair.k);
}
} else {
for (let branch of [tree.left, tree.middle, tree.right]) {
for (let item of mapKeys(branch)) {
result.push(item);
}
}
}
return result;
}
export function* mapItems<K, T>(tree: TernaryTreeMap<K, T>): Generator<K> {
let seqItems = mapKeys(tree);
for (let x of seqItems) {
yield x;
}
}
function pairToString<K, V>(p: TernaryTreeMapKeyValuePair<K, V>): string {
return `${p.k}:${p.v}`;
}
export function mapEqual<K, V>(xs: TernaryTreeMap<K, V>, ys: TernaryTreeMap<K, V>): boolean {

@@ -1062,11 +997,8 @@ if (xs === ys) {

let keys = mapKeys(xs);
for (let key of keys) {
for (let key of toKeys(xs)) {
let vx = mapGet(xs, key);
let vy = mapGet(ys, key);
if (vx.existed !== vy.existed) {
return false;
}
// TODO compare deep structures
if (!dataEqual(vx.value, vy.value)) {
if (!dataEqual(vx, vy)) {
return false;

@@ -1082,3 +1014,3 @@ }

let counted = 0;
mapEach(ys, (key: K, item: T): void => {
for (let [key, item] of toPairs(ys)) {
ret = assocMap(ret, key, item);

@@ -1092,3 +1024,3 @@ // # TODO pickd loop by experience

}
});
}
return ret;

@@ -1101,5 +1033,5 @@ }

let counted = 0;
mapEach(ys, (key: K, item: T): void => {
for (let [key, item] of toPairs(ys)) {
if (dataEqual(item, skipped)) {
return;
continue;
}

@@ -1114,3 +1046,3 @@ ret = assocMap(ret, key, item);

}
});
}
return ret;

@@ -1123,3 +1055,3 @@ }

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

@@ -1126,0 +1058,0 @@ tree.left = newTree.left;

28

src/test-list.ts
import {
listToString,
initTernaryTreeList,
listEach,
indexOf,

@@ -9,6 +8,5 @@ findIndex,

checkListStructure,
listToSeq,
slice,
listPairs,
listItems,
listToPairs,
listToItems,
formatListInline,

@@ -33,2 +31,3 @@ sameListShape,

listEqual,
indexToItems,
} from "./list";

@@ -52,4 +51,8 @@

check(formatListInline(data11) == "((1 (2 _ 3) 4) (5 6 7) (8 (9 _ 10) 11))");
check(arrayEqual<number>(origin11, listToSeq(data11)));
check(
arrayEqual<number>(origin11, [...listToItems(data11)])
);
check(arrayEqual<number>([...listToItems(data11)], [...indexToItems(data11)]));
let emptyXs = new Array<number>(0);

@@ -170,3 +173,3 @@ check(listEqual(initEmptyTernaryTreeList<number>(), initTernaryTreeList(emptyXs)));

var i = 0;
for (let item of listItems(data4)) {
for (let item of listToItems(data4)) {
i = i + 1;

@@ -178,3 +181,3 @@ }

i = 0;
for (let [idx, item] of listPairs(data4)) {
for (let [idx, item] of listToPairs(data4)) {
i = i + idx;

@@ -213,3 +216,3 @@ }

for (let j = i; j < 40; j++) {
check(arrayEqual<number>(listToSeq(slice(data, i, j)), list40.slice(i, j)));
check(arrayEqual<number>([...listToItems(slice(data, i, j))], list40.slice(i, j)));
}

@@ -222,12 +225,13 @@ }

let reversedData = reverse(data);
check(arrayEqual(listToSeq(data).reverse(), listToSeq(reversedData)));
check(arrayEqual([...listToItems(data)].reverse(), [...listToItems(reversedData)]));
check(checkListStructure(reversedData));
});
test("list each", () => {
test("list traverse", () => {
var i = 0;
let data = initTernaryTreeList<number>([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
listEach(data, (x: number) => {
for (let x of listToItems(data)) {
i = i + 1;
});
}
check(i == 10);

@@ -234,0 +238,0 @@ });

28

src/test-map.ts

@@ -1,6 +0,5 @@

import { some, none, hashGenerator } from "./types";
import { hashGenerator } from "./types";
import { test, check, cmp, deepEqual, justDisplay } from "./utils";
import {
initTernaryTreeMap,
mapKeys,
toHashSortedPairs,

@@ -16,3 +15,2 @@ merge,

toPairs,
toPairsIterator,
initEmptyTernaryTreeMap,

@@ -23,4 +21,4 @@ sameMapShape,

mapToString,
mapEach,
mapEqual,
toKeys,
} from "./map";

@@ -54,4 +52,4 @@

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

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

// justDisplay((mapToString(toPairs(data))) , "@[2:12, 3:13, 7:17, 9:19, 6:16, 5:15, 1:11, 8:18, 0:10, 4:14]")
justDisplay(mapKeys(data), ["2", "3", "7", "9", "6", "5", "1", "8", "0", "4"]);
justDisplay([...toKeys(data)], ["2", "3", "7", "9", "6", "5", "1", "8", "0", "4"]);
});

@@ -187,6 +185,6 @@

let c = mergeSkip(a, b, 11);
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)));
check(deepEqual(mapGet(c, "0"), 10));
check(deepEqual(mapGet(c, "1"), 12));
check(deepEqual(mapGet(c, "2"), 13));
check(deepEqual(mapGet(c, "3"), 14));
});

@@ -205,3 +203,3 @@

var i = 0;
for (let [k, v] of toPairsIterator(data)) {
for (let [k, v] of toPairs(data)) {
i = i + 1;

@@ -213,3 +211,3 @@ }

i = 0;
for (let key of toPairsIterator(data)) {
for (let key of toPairs(data)) {
i = i + 1;

@@ -229,8 +227,8 @@ }

var i = 0;
mapEach(data, (k: string, v: number): void => {
for (let [k, v] of toPairs(data)) {
// echo "..{k}-{v}.."
i = i + 1;
});
}
check(i == 100);
});
};

29

src/types.ts

@@ -23,5 +23,5 @@ export enum TernaryTreeKind {

export type TernaryTreeMapKeyValuePair<K, V> = {
k: K;
v: V;
export type TernaryTreeMapHashEntry<K, V> = {
hash: Hash;
pairs: Array<[K, V]>;
};

@@ -41,3 +41,3 @@

hash: number;
elements: Array<TernaryTreeMapKeyValuePair<K, T>>; // handle hash collapsing
elements: Array<[K, T]>; // handle hash collapsing
};

@@ -51,23 +51,2 @@

export type Option<T> = {
existed: boolean;
value: T;
};
export function none<T>(): Option<T> {
let result: Option<T> = {
existed: false,
value: null as any,
};
return result;
}
export function some<T>(v: T): Option<T> {
let result: Option<T> = {
existed: true,
value: v,
};
return result;
}
export type Hash = number; // TODO

@@ -74,0 +53,0 @@ 

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