Useful Data Structures

graph.ts

import { uniqueBy } from "remeda";
import { SuperMap } from "./SuperMap.ts";

export class Graph<T> {
  adjacencyList: SuperMap<T, T[]>;
  private serialize: (input: T) => string;
  private deserialize: (input: string) => T;
  private printVal: (input: T) => any;

  constructor(
    { serialize, deserialize, print = (n) => n }:
      {
        serialize: (input: T) => string;
        deserialize: (input: string) => T;
        print?: (input: T) => any;
      },
  ) {
    this.adjacencyList = new SuperMap<T, T[]>({
      serialize,
      deserialize,
    });
    this.serialize = serialize;
    this.deserialize = deserialize;
    this.printVal = print;
  }

  addVertex(vertex: T): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1: T, vertex2: T): void {
    if (!this.adjacencyList.has(vertex1)) {
      this.addVertex(vertex1);
    }
    if (!this.adjacencyList.has(vertex2)) {
      this.addVertex(vertex2);
    }

    this.adjacencyList.get(vertex1)?.push(
      vertex2,
    );
    this.adjacencyList.get(vertex2)?.push(
      vertex1,
    ); // For undirected graph
  }

  allIsolatedLines() {
    const allVals = this.adjacencyList.keys();
    const touchedVals = new SuperMap<T, number>({
      serialize: this.serialize,
      deserialize: this.deserialize,
    });
    const groups: T[][] = [];

    for (const val of allVals) {
      if (touchedVals.has(val)) continue;
      touchedVals.set(val, 1);
      const newVals = this.followToEnd(val);
      newVals.forEach((v) => {
        touchedVals.set(v, 1);
      });
      groups.push(newVals);
    }

    return groups.map((n) =>
      uniqueBy(n, (item) => this.serialize(item))
    );
  }

  followToEnd(
    vertex: T,
    prevChecked = new Map<T, number>(),
  ): T[] {
    prevChecked.set(vertex, 1);
    for (
      let neighbor
        of this.getNeighbors(vertex)?.filter((
          n,
        ) => !prevChecked.has(n)) ??
          []
    ) {
      prevChecked.set(neighbor, 1);
      this.followToEnd(neighbor, prevChecked);
    }
    return [...prevChecked.keys()];
  }

  getNeighbors(vertex: T): T[] | undefined {
    return this.adjacencyList.get(vertex);
  }

  hasVertex(vertex: T): boolean {
    return this.adjacencyList.has(vertex);
  }

  printGraph(): void {
    for (
      const [vertex, neighbors] of this
        .adjacencyList.entries()
    ) {
      console.log(
        `${this.printVal(vertex)}: ${
          neighbors.map(this.printVal).join(", ")
        }`,
      );
    }
  }
}

supermap.ts

import { pipe } from "@core/pipe/pipe";
import { map } from "@core/iterutil/pipe/map";

export class SuperMap<K, T> {
  private regMap: Map<string, T> = new Map();

  serialize: (input: K) => string;
  deserialize: (input: string) => K;

  constructor({ serialize, deserialize }: {
    serialize: (input: K) => string;
    deserialize: (input: string) => K;
  }) {
    this.serialize = serialize;
    this.deserialize = deserialize;
  }

  set = (key: K, val: T) => {
    return this.regMap.set(
      this.serialize(key),
      val,
    );
  };

  get = (
    key: K,
  ) => {
    return this.regMap.get(this.serialize(key));
  };

  has = (key: K) => {
    return this.regMap.has(this.serialize(key));
  };

  entries = () =>
    pipe(
      this.regMap.entries(),
      map((
        [key, value],
      ) =>
        [this.deserialize(key), value] as [K, T]
      ),
    );

  keys = () =>
    pipe(
      this.regMap.keys(),
      map(this.deserialize),
    );
}