Page MenuHomePhabricator
Files F3349008

D9626.diff
No OneTemporary
Actions

D9626.diff
View Options

diff --git a/lib/shared/radix-tree.js b/lib/shared/radix-tree.js
new file mode 100644
--- /dev/null
+++ b/lib/shared/radix-tree.js
@@ -0,0 +1,150 @@
+// @flow
+
+import invariant from 'invariant';
+
+type RadixTreeLeafNode<V> = {
+ leaf: true,
+ part: string,
+ values: Set<V>,
+};
+type RadixTreeBranchNode<V> = {
+ part: string,
+ children: Map<string, RadixTreeNode<V>>,
+};
+type RadixTreeNode<V> = RadixTreeLeafNode<V> | RadixTreeBranchNode<V>;
+
+class RadixTree<V> {
+ root: RadixTreeBranchNode<V> = {
+ part: '',
+ children: new Map(),
+ };
+
+ add(key: string, value: V) {
+ let node = this.root;
+ let partLeft = key;
+ while (true) {
+ partLeft = partLeft.substring(node.part.length);
+ if (node.leaf) {
+ // If we recurse into a leaf, that means we have an exact match
+ invariant(
+ partLeft.length === 0,
+ 'RadixTree should have exact match when adding to a leaf',
+ );
+ node.values.add(value);
+ return;
+ }
+ // If there is a node that is a substring, we recurse into it
+ // Otherwise we look for a node with the same first char
+ const firstChar = partLeft[0] ?? '';
+ const firstCharMatch = node.children.get(firstChar);
+ if (!firstCharMatch) {
+ node.children.set(firstChar, {
+ leaf: true,
+ part: partLeft,
+ values: new Set([value]),
+ });
+ return;
+ } else if (firstCharMatch.leaf && partLeft === firstCharMatch.part) {
+ node = firstCharMatch;
+ continue;
+ } else if (
+ !firstCharMatch.leaf &&
+ partLeft.startsWith(firstCharMatch.part)
+ ) {
+ node = firstCharMatch;
+ continue;
+ }
+
+ let sharedStart = '';
+ const minLength = Math.min(partLeft.length, firstCharMatch.part.length);
+ for (let i = 0; i < minLength; i++) {
+ if (partLeft[i] !== firstCharMatch.part[i]) {
+ break;
+ }
+ sharedStart += partLeft[i];
+ }
+ invariant(sharedStart, 'firstCharMatch should share at least one char');
+
+ firstCharMatch.part = firstCharMatch.part.substring(sharedStart.length);
+ const newBranchFirstChar = firstCharMatch.part[0] ?? '';
+
+ const newLeafPart = partLeft.substring(sharedStart.length);
+ const newLeafFirstChar = newLeafPart[0] ?? '';
+
+ const newBranch = {
+ part: sharedStart,
+ children: new Map([
+ [newBranchFirstChar, firstCharMatch],
+ [
+ newLeafFirstChar,
+ {
+ leaf: true,
+ part: newLeafPart,
+ values: new Set([value]),
+ },
+ ],
+ ]),
+ };
+ node.children.set(firstChar, newBranch);
+ break;
+ }
+ }
+
+ getAllMatchingPrefix(prefix: string): V[] {
+ const result = new Set();
+ const stack = [{ node: this.root, partLeft: prefix }];
+ while (stack.length > 0) {
+ const { node, partLeft: prevPartLeft } = stack.pop();
+ if (node.leaf) {
+ for (const value of node.values) {
+ result.add(value);
+ }
+ continue;
+ }
+
+ const partLeft = prevPartLeft.substring(node.part.length);
+ const firstChar = partLeft[0];
+ if (!firstChar) {
+ for (const child of node.children.values()) {
+ stack.push({ node: child, partLeft });
+ }
+ continue;
+ }
+
+ const firstCharMatch = node.children.get(firstChar);
+ if (!firstCharMatch) {
+ continue;
+ }
+
+ const leafMatch = firstCharMatch.part.startsWith(partLeft);
+ if (leafMatch) {
+ stack.push({ node: firstCharMatch, partLeft });
+ continue;
+ }
+
+ const branchMatch =
+ !firstCharMatch.leaf && partLeft.startsWith(firstCharMatch.part);
+ if (branchMatch) {
+ stack.push({ node: firstCharMatch, partLeft });
+ }
+ }
+
+ return [...result];
+ }
+
+ getAllMatchingExactly(key: string): V[] {
+ let node = this.root;
+ let partLeft = key;
+ while (node && partLeft.startsWith(node.part)) {
+ if (node.leaf) {
+ return [...new Set(node.values)];
+ }
+ partLeft = partLeft.substring(node.part.length);
+ const firstChar = partLeft[0] ?? '';
+ node = node.children.get(firstChar);
+ }
+ return [];
+ }
+}
+
+export default RadixTree;
diff --git a/lib/shared/radix-tree.test.js b/lib/shared/radix-tree.test.js
new file mode 100644
--- /dev/null
+++ b/lib/shared/radix-tree.test.js
@@ -0,0 +1,199 @@
+// @flow
+
+import RadixTree from './radix-tree.js';
+
+type TestValue = {
+ +id: number,
+};
+
+const radixTree = new RadixTree<TestValue>();
+
+describe('RadixTree.add', () => {
+ it('should add "test", "slow", and "water"', () => {
+ radixTree.add('test', { id: 1 });
+ radixTree.add('slow', { id: 2 });
+ radixTree.add('water', { id: 3 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ expect(childNodes[0].part).toBe('test');
+ expect(childNodes[0].leaf).toBe(true);
+ expect(childNodes[1].part).toBe('slow');
+ expect(childNodes[1].leaf).toBe(true);
+ expect(childNodes[2].part).toBe('water');
+ expect(childNodes[2].leaf).toBe(true);
+ });
+ it('should group "slow" and "slower"', () => {
+ radixTree.add('slower', { id: 4 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ const slowNode = childNodes[1];
+ expect(slowNode.part).toBe('slow');
+ expect(!!slowNode.leaf).toBe(false);
+ if (slowNode.leaf) {
+ return;
+ }
+ const slowChildren = slowNode.children;
+ const slowChildrenNodes = [...slowChildren.values()];
+ expect(slowChildrenNodes.length).toBe(2);
+ expect(slowChildrenNodes[0].part).toBe('');
+ expect(slowChildrenNodes[0].leaf).toBe(true);
+ expect(slowChildrenNodes[1].part).toBe('er');
+ expect(slowChildrenNodes[1].leaf).toBe(true);
+ });
+ it('should group "water" and "wat"', () => {
+ radixTree.add('wat', { id: 5 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ const watNode = childNodes[2];
+ expect(watNode.part).toBe('wat');
+ expect(!!watNode.leaf).toBe(false);
+ if (watNode.leaf) {
+ return;
+ }
+ const watChildren = watNode.children;
+ const watChildrenNodes = [...watChildren.values()];
+ expect(watChildrenNodes.length).toBe(2);
+ expect(watChildrenNodes[0].part).toBe('er');
+ expect(watChildrenNodes[0].leaf).toBe(true);
+ expect(watChildrenNodes[1].part).toBe('');
+ expect(watChildrenNodes[1].leaf).toBe(true);
+ });
+ it('should group "test" and "team"', () => {
+ radixTree.add('team', { id: 6 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ const teNode = childNodes[0];
+ expect(teNode.part).toBe('te');
+ expect(!!teNode.leaf).toBe(false);
+ if (teNode.leaf) {
+ return;
+ }
+ const teChildren = teNode.children;
+ const teChildrenNodes = [...teChildren.values()];
+ expect(teChildrenNodes.length).toBe(2);
+ expect(teChildrenNodes[0].part).toBe('st');
+ expect(teChildrenNodes[0].leaf).toBe(true);
+ expect(teChildrenNodes[1].part).toBe('am');
+ expect(teChildrenNodes[1].leaf).toBe(true);
+ });
+ it('should group "toast" and "te" (parent of "test" and "team")', () => {
+ radixTree.add('toast', { id: 7 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ const tNode = childNodes[0];
+ expect(tNode.part).toBe('t');
+ expect(!!tNode.leaf).toBe(false);
+ if (tNode.leaf) {
+ return;
+ }
+ const tChildren = tNode.children;
+ const tChildrenNodes = [...tChildren.values()];
+ expect(tChildrenNodes.length).toBe(2);
+ expect(tChildrenNodes[1].part).toBe('oast');
+ expect(tChildrenNodes[1].leaf).toBe(true);
+ const teNode = tChildrenNodes[0];
+ expect(teNode.part).toBe('e');
+ expect(!!teNode.leaf).toBe(false);
+ if (teNode.leaf) {
+ return;
+ }
+ const teChildren = teNode.children;
+ const teChildrenNodes = [...teChildren.values()];
+ expect(teChildrenNodes[0].part).toBe('st');
+ expect(teChildrenNodes[0].leaf).toBe(true);
+ expect(teChildrenNodes[1].part).toBe('am');
+ expect(teChildrenNodes[1].leaf).toBe(true);
+ });
+ it('should combine "slow" and "slow" into a single leaf', () => {
+ radixTree.add('slow', { id: 8 });
+ const childNodes = [...radixTree.root.children.values()];
+ expect(childNodes.length).toBe(3);
+ const slowNode = childNodes[1];
+ expect(slowNode.part).toBe('slow');
+ expect(!!slowNode.leaf).toBe(false);
+ if (slowNode.leaf) {
+ return;
+ }
+ const slowChildren = slowNode.children;
+ const slowChildrenNodes = [...slowChildren.values()];
+ expect(slowChildrenNodes.length).toBe(2);
+ const slowLeafNode = slowChildrenNodes[0];
+ expect(slowLeafNode.part).toBe('');
+ expect(slowLeafNode.leaf).toBe(true);
+ if (!slowLeafNode.leaf) {
+ return;
+ }
+ expect(slowLeafNode.values.size).toBe(2);
+ expect(slowChildrenNodes[1].part).toBe('er');
+ expect(slowChildrenNodes[1].leaf).toBe(true);
+ });
+});
+
+describe('RadixTree.getAllMatchingPrefix', () => {
+ it('should match "t" to "toast", "test", and "team"', () => {
+ const results = radixTree.getAllMatchingPrefix('t');
+ expect(results.length).toBe(3);
+ expect(results[0].id).toBe(7);
+ expect(results[1].id).toBe(6);
+ expect(results[2].id).toBe(1);
+ });
+ it('should match "slow" to "slow", "slow", and "slower"', () => {
+ const results = radixTree.getAllMatchingPrefix('slow');
+ expect(results.length).toBe(3);
+ expect(results[0].id).toBe(4);
+ expect(results[1].id).toBe(2);
+ expect(results[2].id).toBe(8);
+ });
+ it('should match "slowe" to "slower"', () => {
+ const results = radixTree.getAllMatchingPrefix('slowe');
+ expect(results.length).toBe(1);
+ expect(results[0].id).toBe(4);
+ });
+ it('should match "wa" to "wat" and "water"', () => {
+ const results = radixTree.getAllMatchingPrefix('wa');
+ expect(results.length).toBe(2);
+ expect(results[0].id).toBe(5);
+ expect(results[1].id).toBe(3);
+ });
+ it('should match "water" to "water"', () => {
+ const results = radixTree.getAllMatchingPrefix('water');
+ expect(results.length).toBe(1);
+ expect(results[0].id).toBe(3);
+ });
+ it('should match "" to all results', () => {
+ const results = radixTree.getAllMatchingPrefix('');
+ expect(results.length).toBe(8);
+ });
+});
+
+describe('RadixTree.getAllMatchingExactly', () => {
+ it('should not match "t"', () => {
+ const results = radixTree.getAllMatchingExactly('t');
+ expect(results.length).toBe(0);
+ });
+ it('should match "slow" to "slow" and "slow"', () => {
+ const results = radixTree.getAllMatchingExactly('slow');
+ expect(results.length).toBe(2);
+ expect(results[0].id).toBe(2);
+ expect(results[1].id).toBe(8);
+ });
+ it('should not match "slowe"', () => {
+ const results = radixTree.getAllMatchingExactly('slowe');
+ expect(results.length).toBe(0);
+ });
+ it('should match "slower" to "slower"', () => {
+ const results = radixTree.getAllMatchingExactly('slower');
+ expect(results.length).toBe(1);
+ expect(results[0].id).toBe(4);
+ });
+ it('should match "wat" to "wat"', () => {
+ const results = radixTree.getAllMatchingExactly('wat');
+ expect(results.length).toBe(1);
+ expect(results[0].id).toBe(5);
+ });
+ it('should match "water" to "water"', () => {
+ const results = radixTree.getAllMatchingExactly('water');
+ expect(results.length).toBe(1);
+ expect(results[0].id).toBe(3);
+ });
+});

File Metadata

Mime Type
text/plain
Expires
Sat, Nov 23, 4:47 PM (19 h, 51 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
2571615
Default Alt Text
D9626.diff (11 KB)

Event Timeline