Trie implementation

trie.test.ts

// tests/trie.test.ts
import Trie from "../src/Trie";

describe("Testing Trie.ts:", () => {
  let instance: Trie<string>;
  beforeEach(() => {
    instance = new Trie<string>();
  });
  describe("Empty Trie nodes have required properties:", () => {
    test("Node should have property `children`", () => {
      expect(instance).toHaveProperty("children");
    });
    test("Node should have property `isTerminal`", () => {
      expect(instance).toHaveProperty("isTerminal", false);
    });
    test("Node should have property `value`", () => {
      expect(instance).toHaveProperty("value", null);
    });
  });

  test("Insertion into a Trie", () => {
    expect(instance).toHaveProperty("insert");
    const [key, value] = ["foo", "bar"];
    instance.insert(key, value);
    expect(instance.lookup(key)).toBe(value);
    expect(Object.keys(instance.children).length).toBe(1);
  });
  test("Deletion from a Trie", () => {
    const pairs = {
      cat: "tankerous",
      category: "crocodile",
      categorical: "shoulder",
    };
    for (const [key, value] of Object.entries(pairs)) {
      instance.insert(key, value);
    }
    // delete each one, and make sure the others are still accessible

    // delete categorical; cat and category available
    instance.delete("categorical");
    expect(instance.lookup("cat")).toBe(pairs["cat"]);
    expect(instance.lookup("category")).toBe(pairs["category"]);
    expect(instance.lookup("categorical")).toBe(null);

    // delete cat; category available
    instance.delete("cat");
    expect(instance.lookup("cat")).toBe(null);
    expect(instance.lookup("category")).toBe(pairs["category"]);
    expect(instance.lookup("categorical")).toBe(null);

    // delete category; none available
    instance.delete("category");
    expect(instance.lookup("cat")).toBe(null);
    expect(instance.lookup("category")).toBe(null);
    expect(instance.lookup("categorical")).toBe(null);
  });

  test("Lookup of string keys in a Trie", () => {
    const pairs = {
      cat: "dog",
      alligator: "crocodile",
      elbow: "shoulder",
    };
    for (const [key, value] of Object.entries(pairs)) {
      instance.insert(key, value);
    }

    for (const [key, value] of Object.entries(pairs)) {
      expect(instance.lookup(key)).toBe(value);
    }
    return;
  });
});

Trie.ts

// src/Trie.ts
// pronounced "try"
/**
 * Bespoke implementation of the Trie data structure.
 * Used to do prefix search on shell builtins and, in the future,
 * nodes in the virtual filesystem.
 */
export default class Trie<T> {
  children: Trie<T>[];
  value: T | null;
  isTerminal: boolean;

  constructor() {
    this.children = [];
    this.value = null;
    this.isTerminal = false;
  }

  public lookup(key: string): T | null {
    let node: Trie<T> = this;
    for (let i = 0; i < key.length; i++) {
      const ordinal = key.charCodeAt(i);
      if (node.children[ordinal] === undefined) {
        // if at any point down it’s nil, no result
        return null;
      }
      node = node.children[ordinal];
    }
    return node.value;
  }

  public insert(key: string, value: T) {
    // make a new node for each char in the key, if it doesn’t exist
    let node: Trie<T> = this;
    for (let i = 0; i < key.length; i++) {
      const ordinal = key.charCodeAt(i);
      if (node.children[ordinal] === undefined) {
        node.children[ordinal] = new Trie<T>();
      }
      node = node.children[ordinal];
    }
    node.value = value;
    node.isTerminal = true;
  }

  // deletion, recursive impl.
  public delete(key: string): null | Trie<T> {
    // base case, calling with an empty string means 'delete yourself' since
    // there is no prefix.
    if (key == "") {
      if (this.isTerminal) {
        this.isTerminal = false;
        this.value = null;
      }
      for (const _ of this.children) {
        return this;
      }
      return null;
    }
    const ordinal = key.charCodeAt(0);
    if (!this.children[ordinal].delete(key.slice(1))) {
      delete this.children[ordinal];
    }
    return this;
  }
}