-
Notifications
You must be signed in to change notification settings - Fork 0
/
radix_tree_test.ts
113 lines (99 loc) · 2.89 KB
/
radix_tree_test.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import {
assert,
assertEquals,
} from "https://deno.land/std@0.89.0/testing/asserts.ts";
import { Edge, Node, RadixTree } from "./radix_tree.ts";
class DataNode<T> extends Node {
static bind<T>(data: T) {
return () => new this(data);
}
constructor(public data: T, edges: Edge[] = [], isLeaf = true) {
super(edges, isLeaf);
}
}
Deno.test("distinct insertions", () => {
const trie = new RadixTree();
trie.insert("test", DataNode.bind("test"));
trie.insert("slow", DataNode.bind("slow"));
trie.insert("water", DataNode.bind("water"));
assertEquals<Node>(
trie.rootNode,
new Node([
{ label: "test", targetNode: new DataNode("test") },
{ label: "slow", targetNode: new DataNode("slow") },
{ label: "water", targetNode: new DataNode("water") },
], false),
);
assertEquals(trie.lookup("test"), {
closestNode: new DataNode("test"),
success: true,
elementsFound: 4,
});
});
Deno.test("suffix insertion split", () => {
const trie = new RadixTree();
trie.insert("test", DataNode.bind("test"));
trie.insert("slow", DataNode.bind("slow"));
trie.insert("water", DataNode.bind("water"));
trie.insert("slower", DataNode.bind("slower"));
assertEquals<Node>(
trie.rootNode,
new Node([
{ label: "test", targetNode: new DataNode("test") },
{
label: "slow",
targetNode: new DataNode("slow", [{
label: "er",
targetNode: new DataNode("slower"),
}]),
},
{ label: "water", targetNode: new DataNode("water") },
], false),
);
assertEquals(trie.lookup("slow"), {
closestNode: trie.rootNode.edges[1].targetNode,
success: true,
elementsFound: 4,
});
});
Deno.test("prefix insertion split", () => {
const trie = new RadixTree();
trie.insert("slower", DataNode.bind("slower"));
trie.insert("water", DataNode.bind("water"));
trie.insert("test", DataNode.bind("test"));
trie.insert("slow", DataNode.bind("slow"));
assertEquals<Node>(
trie.rootNode,
new Node([
{
label: "slow",
targetNode: new DataNode("slow", [{
label: "er",
targetNode: new DataNode("slower"),
}]),
},
{ label: "water", targetNode: new DataNode("water") },
{ label: "test", targetNode: new DataNode("test") },
], false),
);
assertEquals(trie.lookup("slow"), {
closestNode: trie.rootNode.edges[0].targetNode,
success: true,
elementsFound: 4,
});
assertEquals(trie.lookup("slowe"), {
closestNode: trie.rootNode.edges[0].targetNode,
success: false,
elementsFound: 4,
});
assertEquals(trie.lookup("slower"), {
closestNode: trie.rootNode.edges[0].targetNode.edges[0].targetNode,
success: true,
elementsFound: 6,
});
assertEquals(trie.lookup("slowere"), {
closestNode: trie.rootNode.edges[0].targetNode.edges[0].targetNode,
success: false,
elementsFound: 6,
});
});