123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
import type {  AdjacencyStructure,  AdjacencyStructureConstructor,  IndexedCollection,  TypedArrayConstructors,} from "./utility-types.ts";
/** * Creates an Adjacency List class extending a given TypedArray class. * * @param Base a TypedArray class to extend */export function AdjacencyListMixin<U extends TypedArrayConstructors>(  Base: U,): AdjacencyStructureConstructor<U> {  // deno-lint-ignore no-empty-interface  interface AdjacencyList extends IndexedCollection {}
  /**   * Implements the Adjacency List data structure for weighted directed graphs.   */  class AdjacencyList extends Base implements AdjacencyStructure {    static directed = true;    static weighted = true;    vertices = 2;    edges = 4;    empty = undefined;
    // deno-lint-ignore no-explicit-any    constructor(...args: any[]) {      super(...args);      [this.vertices, this.edges] = AdjacencyList.getDimensions(this);    }
    static get [Symbol.species](): U {      return Base;    }
    static create(vertices: number, edges: number) {      const length = this.getLength(vertices, edges);      const list = new this(length);      list.vertices = vertices;      list.edges = edges;      list.setOffsets();      return list as unknown as AdjacencyList & InstanceType<U>;    }
    /*    * Returns the dimensions, vertices and maximum edge count, of an existing AdjacencyList    */    static getDimensions(      list: IndexedCollection,    ): [vertices: number, edges: number] {      let vertices = 0;      while (list[vertices] <= list[vertices + 1]) {        vertices++;      }      const edges = (list.length - vertices - 1) >> 1;      return [vertices, edges];    }
    static getLength(vertices: number, edges: number): number {      return vertices + (edges << 1) + 1;    }
    // TODO document RangeError    addEdge(x: number, y: number, weight: number): this {      if (this.hasEdge(x, y)) return this;      // the list is full      if (this.isFull()) throw new RangeError("The list is full.");      const { vertices } = this;
      // shift values      for (let i = this[vertices]; i > this[x]; i -= 2) {        [this[i], this[i + 1], this[i - 1], this[i - 2]] = [          this[i - 2],          this[i - 1],          this[i],          this[i + 1],        ];      }      // set edge      this[this[x]] = y;      this[this[x] + 1] = weight;
      // update offsets      for (let i = x + 1; i <= vertices; i++) {        this[i] += 2;      }      return this;    }
    getEdge(x: number, y: number): number {      const offset = this[x];      const nextOffset = this[x + 1];      // no out edges from x      if (offset === nextOffset) return NaN;      for (let i = offset; i < nextOffset; i += 2) {        if (this[i] === y) return this[i + 1];      }      return NaN;    }
    hasEdge(x: number, y: number): boolean {      return !Number.isNaN(this.getEdge(x, y));    }
    *inEdges(vertex: number) {      const { vertices } = this;      let edge = 0;      let nextVertex = 1;      for (let i = vertices + 1; i < this[vertices]; i += 2) {        while (i >= this[nextVertex]) {          edge++;          nextVertex++;        }        if (this[i] === vertex) yield edge;      }    }
    isFull(): boolean {      return this[this.vertices] >= this.length;    }
    *outEdges(vertex: number) {      const offset = this[vertex];      const nextOffset = this[vertex + 1];      if (offset !== nextOffset) {        for (let i = nextOffset - 2; i >= offset; i -= 2) {          yield this[i];        }      }    }
    removeEdge(x: number, y: number): this {      const offset = this[x];      const nextOffset = this[x + 1];      // no out edges from x      if (offset === nextOffset) return this;      let edgeIndex = 0;      for (let i = offset; i < nextOffset; i += 2) {        if (this[i] === y) {          edgeIndex = i;          break;        }      }      // there is no such edge      if (!edgeIndex) return this;      // shift value      for (let i = edgeIndex; i < this[this.vertices]; i += 2) {        this[i] = this[i + 2];        this[i + 1] = this[i + 3];      }
      // update offsets      for (let i = x + 1; i <= this.vertices; i++) {        this[i] -= 2;      }
      return this;    }
    setOffsets(): void {      const lastElement = this.vertices + 1;      for (let i = 0; i < lastElement; i++) {        this[i] = lastElement;      }    }  }
  return AdjacencyList;}