5 files changed, 172 insertions, 0 deletions
diff --git a/llparse-frontend/src/trie/empty.ts b/llparse-frontend/src/trie/empty.ts
new file mode 100644
index 0000000..aba52ea
--- /dev/null
+++ b/llparse-frontend/src/trie/empty.ts
@@ -0,0 +1,9 @@
+import { node as api } from 'llparse-builder';
+import { TrieNode } from './node';
+
+export class TrieEmpty extends TrieNode {
+  constructor(public readonly node: api.Node,
+              public readonly value: number | undefined) {
+    super();
+  }
+}
diff --git a/llparse-frontend/src/trie/index.ts b/llparse-frontend/src/trie/index.ts
new file mode 100644
index 0000000..391c6a3
--- /dev/null
+++ b/llparse-frontend/src/trie/index.ts
@@ -0,0 +1,136 @@
+import * as assert from 'assert';
+import { Buffer } from 'buffer';
+import { Edge, node as api } from 'llparse-builder';
+
+import { TrieEmpty } from './empty';
+import { TrieNode } from './node';
+import { TrieSequence } from './sequence';
+import { ITrieSingleChild, TrieSingle } from './single';
+
+export { TrieEmpty, TrieNode, TrieSequence, TrieSingle };
+
+interface IEdge {
+  readonly key: Buffer;
+  readonly node: api.Node;
+  readonly noAdvance: boolean;
+  readonly value: number | undefined;
+}
+
+type Path = ReadonlyArray<Buffer>;
+type EdgeArray = ReadonlyArray<IEdge>;
+
+export class Trie {
+  constructor(private readonly name: string) {
+  }
+
+  public build(edges: ReadonlyArray<Edge>): undefined | TrieNode {
+    if (edges.length === 0) {
+      return undefined;
+    }
+
+    const internalEdges: IEdge[] = [];
+    for (const edge of edges) {
+      internalEdges.push({
+        key: edge.key as Buffer,
+        noAdvance: edge.noAdvance,
+        node: edge.node,
+        value: edge.value,
+      });
+    }
+
+    return this.level(internalEdges, []);
+  }
+
+  private level(edges: EdgeArray, path: Path): TrieNode {
+    const first = edges[0].key;
+    const last = edges[edges.length - 1].key;
+
+    // Leaf
+    if (edges.length === 1 && edges[0].key.length === 0) {
+      return new TrieEmpty(edges[0].node, edges[0].value);
+    }
+
+    // Find the longest common sub-string
+    let common = 0;
+    for (; common < first.length; common++) {
+      if (first[common] !== last[common]) {
+        break;
+      }
+    }
+
+    // Sequence
+    if (common > 1) {
+      return this.sequence(edges, first.slice(0, common), path);
+    }
+
+    // Single
+    return this.single(edges, path);
+  }
+
+  private slice(edges: EdgeArray, off: number): EdgeArray {
+    return edges.map((edge) => {
+      return {
+        key: edge.key.slice(off),
+        noAdvance: edge.noAdvance,
+        node: edge.node,
+        value: edge.value,
+      };
+    }).sort((a, b) => {
+      return a.key.compare(b.key);
+    });
+  }
+
+  private sequence(edges: EdgeArray, prefix: Buffer, path: Path): TrieNode {
+    const sliced = this.slice(edges, prefix.length);
+    const noAdvance = sliced.some((edge) => edge.noAdvance);
+    assert(!noAdvance);
+    const child = this.level(sliced, path.concat(prefix));
+
+    return new TrieSequence(prefix, child);
+  }
+
+  private single(edges: EdgeArray, path: Path): TrieNode {
+    // Check for duplicates
+    if (edges[0].key.length === 0) {
+      assert(path.length !== 0, `Empty root entry at "${this.name}"`);
+      assert(edges.length === 1 || edges[1].key.length !== 0,
+        `Duplicate entries in "${this.name}" at [ ${path.join(', ')} ]`);
+    }
+
+    let otherwise: TrieEmpty | undefined;
+    const keys: Map<number, IEdge[]> = new Map();
+    for (const edge of edges) {
+      if (edge.key.length === 0) {
+        otherwise = new TrieEmpty(edge.node, edge.value);
+        continue;
+      }
+      const key = edge.key[0];
+
+      if (keys.has(key)) {
+        keys.get(key)!.push(edge);
+      } else {
+        keys.set(key, [ edge ]);
+      }
+    }
+
+    const children: ITrieSingleChild[] = [];
+    keys.forEach((subEdges, key) => {
+      const sliced = this.slice(subEdges, 1);
+      const subpath = path.concat(Buffer.from([ key ]));
+
+      const noAdvance = subEdges.some((edge) => edge.noAdvance);
+      const allSame = subEdges.every((edge) => edge.noAdvance === noAdvance);
+
+      assert(allSame || subEdges.length === 0,
+        'Conflicting `.peek()` and `.match()` entries in ' +
+          `"${this.name}" at [ ${subpath.join(', ')} ]`);
+
+      children.push({
+        key,
+        noAdvance,
+        node: this.level(sliced, subpath),
+      });
+    });
+    return new TrieSingle(children, otherwise);
+  }
+}
diff --git a/llparse-frontend/src/trie/node.ts b/llparse-frontend/src/trie/node.ts
new file mode 100644
index 0000000..31f327c
--- /dev/null
+++ b/llparse-frontend/src/trie/node.ts
@@ -0,0 +1,2 @@
+export abstract class TrieNode {
+}
diff --git a/llparse-frontend/src/trie/sequence.ts b/llparse-frontend/src/trie/sequence.ts
new file mode 100644
index 0000000..6b17e02
--- /dev/null
+++ b/llparse-frontend/src/trie/sequence.ts
@@ -0,0 +1,9 @@
+import { node as api } from 'llparse-builder';
+import { TrieNode } from './node';
+
+export class TrieSequence extends TrieNode {
+  constructor(public readonly select: Buffer,
+              public readonly child: TrieNode) {
+    super();
+  }
+}
diff --git a/llparse-frontend/src/trie/single.ts b/llparse-frontend/src/trie/single.ts
new file mode 100644
index 0000000..c984af0
--- /dev/null
+++ b/llparse-frontend/src/trie/single.ts
@@ -0,0 +1,16 @@
+import { node as api } from 'llparse-builder';
+import { TrieEmpty } from './empty';
+import { TrieNode } from './node';
+
+export interface ITrieSingleChild {
+  readonly key: number;
+  readonly noAdvance: boolean;
+  readonly node: TrieNode;
+}
+
+export class TrieSingle extends TrieNode {
+  constructor(public readonly children: ReadonlyArray<ITrieSingleChild>,
+              public readonly otherwise: TrieEmpty | undefined) {
+    super();
+  }
+}