Doubly Linked ID List

doublylinkedidlist.ts

export type DoubleLinkedIDListNode<T> = {
  data: T | false;
  prev: string | false;
  next: string | false;
};

export type DoubleLinkedIDListNodes<T> = Record<
  string,
  DoubleLinkedIDListNode<T>
>;
export type DoubleLinkedIDConstructor<T> = new ()=>DoubleLinkedIDListInterface<T>;
/**# Double Linked ID List 
 * ---
 * A doubly linked list mixed with a map. 
 * 
 * 
 */
export interface DoubleLinkedIDListInterface<T> {
  size : number;
  nodes: DoubleLinkedIDListNodes<T>;

 
  keys() : string[];
  /**# Move Node Before Other
   * ---
   * Move a node to be the previous node of the static node.
   * @param staticNodeId
   * @param nodeMovingId
   */
  moveNodeBeforeOther(staticNodeId: string, nodeMovingId: string): void;
  /**# Move Node After Other
   * ---
   * Move a node to be the next node of the static node.
   * @param staticNodeId
   * @param nodeMovingId
   */
  moveNodeAfterOther(staticNodeId: string, nodeMovingId: string): void;
  /**# Append
   * ---
   * Move node to the bottom of the list.
   * @param id
   */
  append(id: string): void;
  /**# Prepend
   * ---
   * Move node to the top of the list.
   * @param id
   */
  prepend(id: string): void;
  /**# Insert Before
   * ---
   * Create a new node and insert it before the given node.
   * @param insertAtId
   * @param id
   * @param Data
   */
  insertBefore(insertAtId: string, id: string, Data: T): void;
  /**# Insert After
   * ---
   * Create a new node and insert it after the given node.
   * @param insertAtId
   * @param id
   * @param Data
   */
  insertAfter(insertAtId: string, id: string, Data: T): void;
  /**# Append New
   * ---
   * Create a new node and insert at the end of the list.
   * @param id
   * @param Data
   */
  appendNew(id: string, Data: T): void;
  /**# Prepend New
   * ---
   * Create a new node and insert at the start of the list.
   * @param id
   * @param Data
   */
  prependNew(id: string, Data: T): void;
  /**# Pop
   * ---
   * Take a node out from the list and reconfigure it's prev and next nodes to point to each other.
   * @param id
   */
  pop(id: string): DoubleLinkedIDListNode<T>;
  /**# Remove
   * ---
   * Deletes a node from it's list and updates it's previous and next nodes.
   * @param id
   */
  remove(id: string): void;
  removeAll() : void;

  getValue(id: string): T | false;
  setValue(id: string, data: T): void;

  traverseWithFuncForward(func : (key:string,data:T)=>any) : void;
  traverseWithFuncBackward( func : (key:string,data:T)=>any) : void;
  traverseIDsForward(): IteratorResult<string>;
  traverseValuesForward(): IteratorResult<T | false>;
  traverseKeyValuesForward(): IteratorResult<{key : string, value : T | false}>;
  traverseIDsBackward(): IteratorResult<string>;
  traverseValuesBackward(): IteratorResult<T | false>;
  traverseKeyValuesBackward(): IteratorResult<{key : string, value : T | false}>;

  getNextKVP(id : string) : {key : string, value : T | false} | false ;
  getPrevKVP(id : string) : {key : string, value : T | false} | false;
  getNextID(id : string) : string | false;
  getPrevID(id : string) : string | false;

  resetTraverse() : void;
  exists(id : string) : boolean;
  getKVP(id : string) : {key : string, value : T | false} | false;
  getFirstID() : string;
  getLastID() : string;

  isBefore(startId: string, idLookingFor: string) : boolean;
  isAfter(startId: string, idLookingFor: string) : boolean;
  
}

export class DounleLinkedIDList<T> implements DoubleLinkedIDListInterface<T> {
  size: number = 0;
  head: DoubleLinkedIDListNode<T>;
  tail: DoubleLinkedIDListNode<T>;
  nodes: DoubleLinkedIDListNodes<T> = {};

  currentNodeID: string;
  _currentIteratorFowardData: T | false;
  _currentIteratorBackwardData: T | false;
  _currentIteratorForwardId = "head";
  _currentIteratorBackwardId = "tail";

  constructor() {
    this.head = {
      data: false,
      next: "tail",
      prev: false,
    };
    this.tail = {
      data: false,
      next: false,
      prev: "head",
    };
    this.nodes["head"] = this.head;
    this.nodes["tail"] = this.tail;
  }

  keys() {
    const keys = Object.keys(this.nodes);
    const headIndex = keys.indexOf("head");
    keys.splice(headIndex,1);
    const tailIndex = keys.indexOf("tail");
    keys.splice(tailIndex,1);
    return keys;
  }

  getFirstID() {
    if (this.head.next == "tail") return "";
    return <string>this.head.next;
  }

  getLastID() {
    if (this.tail.prev == "head") return "";
    return <string>this.tail.prev;
  }

  insertBefore(insertAtId: string, id: string, Data: T) {
    if (!this.exists(insertAtId)) {
      throw new Error(`${insertAtId} does not exist.`);
    }
    if (this.exists(id)) {
      throw new Error(`${id} already exist.`);
    }
    const insertBeforerNode = this.nodes[insertAtId];
    if (!insertBeforerNode.prev) return;
    const beforeNodeID = insertBeforerNode.prev;
    const beforeNode = this.nodes[beforeNodeID];
    const newNode: DoubleLinkedIDListNode<T> = {
      data: Data,
      prev: beforeNodeID,
      next: insertAtId,
    };
    beforeNode.next = id;
    insertBeforerNode.prev = id;
    this.nodes[id] = newNode;
    this.size++;
  }
  insertAfter(insertAtId: string, id: string, Data: T) {
    if (!this.exists(insertAtId)) {
      throw new Error(`${insertAtId} does not exist.`);
    }
    if (this.exists(id)) {
      throw new Error(`${id} already exist.`);
    }
    const insertAfterNode = this.nodes[insertAtId];
    if (!insertAfterNode.next) return;
    const nextNodeID = insertAfterNode.next;
    const nextNode = this.nodes[nextNodeID];
    const newNode: DoubleLinkedIDListNode<T> = {
      data: Data,
      prev: insertAtId,
      next: nextNodeID,
    };
    nextNode.prev = id;
    insertAfterNode.next = id;
    this.nodes[id] = newNode;
    this.size++;
    return this.nodes[id];
  }

  moveNodeBeforeOther(staticNodeId: string, nodeMovingId: string) {
    if (!this.exists(staticNodeId)) {
      throw new Error(`${staticNodeId} does not exist.`);
    }
    if (!this.exists(nodeMovingId)) {
      throw new Error(`${nodeMovingId} does not exist.`);
    }
    const insertBeforerNode = this.nodes[staticNodeId];
    if (!insertBeforerNode.prev) return;
    const beforeNodeID = insertBeforerNode.prev;
    const beforeNode = this.nodes[beforeNodeID];

    const nodeMoving = this.pop(nodeMovingId);

    beforeNode.next = nodeMovingId;

    nodeMoving.prev = beforeNodeID;
    nodeMoving.next = staticNodeId;

    insertBeforerNode.prev = nodeMovingId;
  }
  moveNodeAfterOther(staticNodeId: string, nodeMovingId: string) {
    if (!this.exists(staticNodeId)) {
      throw new Error(`${staticNodeId} does not exist.`);
    }
    if (!this.exists(nodeMovingId)) {
      throw new Error(`${nodeMovingId} does not exist.`);
    }
    const insertAfterNode = this.nodes[staticNodeId];
    if (!insertAfterNode.next) return;
    const afterNodeID = insertAfterNode.next;
    const afterNode = this.nodes[afterNodeID];

    const nodeMoving = this.pop(nodeMovingId);
    insertAfterNode.next = nodeMovingId;
    nodeMoving.prev = staticNodeId;
    nodeMoving.next = afterNodeID;
    afterNode.prev = nodeMovingId;
  }
  pop(id: string): DoubleLinkedIDListNode<T> {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    const nodeMoving = this.nodes[id];
    const nodeMovingBeforeId = nodeMoving.prev;
    const nodeMovingAfterId = nodeMoving.next;
    if (!nodeMovingBeforeId && !nodeMovingAfterId) {
      return nodeMoving;
    }
    const nodeMovingBefore = this.nodes[<string>nodeMovingBeforeId];
    const nodeMovingAfter = this.nodes[<string>nodeMovingAfterId];
    nodeMovingBefore.next = nodeMovingAfterId;
    nodeMovingAfter.prev = nodeMovingBeforeId;
    return nodeMoving;
  }
  remove(id: string): void {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    this.pop(id);
    //@ts-ignore
    this.nodes[id] = undefined;
    delete this.nodes[id];
    this.size--;
  }
  removeAll() {
    //@ts-ignore
    this.nodes = undefined;
    this.nodes = {};
    this.size = 0;
    this.head.next = "tail";
    this.tail.prev = "head";
    this._currentIteratorBackwardData = false;
    this._currentIteratorFowardData = false;
    this._currentIteratorForwardId = "head";
    this._currentIteratorBackwardId = "tail";
  }

  append(id: string) {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    if (!this.tail.prev) return;
    if (this.tail.prev == "head") {
      this.head.next = id;
    }
    const prevNodeId = this.tail.prev;
    const prevNode = this.nodes[prevNodeId];
    prevNode.next = id;
    this.tail.prev = id;
    const movingNode = this.pop(id);
    movingNode.prev = prevNodeId;
    movingNode.next = "tail";
  }
  prepend(id: string) {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    if (!this.head.next) return;
    if (this.head.next == "tail") {
      this.tail.prev = id;
    }
    const nextNodeId = this.head.next;
    const nextNode = this.nodes[nextNodeId];
    nextNode.prev = id;
    this.head.next = id;
    const movingNode = this.pop(id);
    movingNode.prev = "head";
    movingNode.next = nextNodeId;
  }

  appendNew(id: string, Data: T) {
    if (this.exists(id)) {
      throw new Error(`${id} already exist.`);
    }
    if (!this.tail.prev) return;
    if (this.tail.prev == "head") {
      this.head.next = id;
    }

    const bottomNodeId = this.tail.prev;
    const newNode: DoubleLinkedIDListNode<T> = {
      data: Data,
      prev: bottomNodeId,
      next: "tail",
    };
    this.nodes[id] = newNode;
    this.nodes[bottomNodeId].next = id;
    this.tail.prev = id;
    this.size++;
  }
  prependNew(id: string, Data: T) {
    if (this.exists(id)) {
      throw new Error(`${id} already exist.`);
    }
    if (!this.head.next) return;
    if (this.head.next == "tail") {
      this.tail.prev = id;
    }
    const topNodeId = this.head.next;
    const newNode: DoubleLinkedIDListNode<T> = {
      data: Data,
      prev: "head",
      next: topNodeId,
    };
    this.nodes[id] = newNode;
    this.nodes[topNodeId].prev = id;
    this.head.next = id;
    this.size++;
  }

  getValue(id: string) {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    return this.nodes[id].data;
  }
  setValue(id: string, data: T) {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    this.nodes[id].data = data;
  }

  traverseWithFuncForward(func: (key: string, data: T) => any) {
    let data: IteratorResult<{ key: string; value: T | false }>;
    data = this.traverseKeyValuesForward();
    while (!data.done) {
      func(data.value.key, <T>data.value.value);

      data = this.traverseKeyValuesForward();
    }
  }

  traverseWithFuncBackward(func: (key: string, data: T) => any) {
    let data: IteratorResult<{ key: string; value: T | false }>;
    data = this.traverseKeyValuesBackward();
    while (!data.done) {
      func(data.value.key, <T>data.value.value);

      data = this.traverseKeyValuesForward();
    }
  }

  resetTraverse() {
    this._currentIteratorForwardId = "head";
    this._currentIteratorBackwardId = "tail";
  }

  traverseIDsForward(): IteratorResult<string> {
    let done = false;
    if (this.nodes[this._currentIteratorForwardId].next == "tail") {
      done = true;
      this._currentIteratorForwardId = "head";
    } else {
      this._currentIteratorForwardId = <string>(
        this.nodes[this._currentIteratorForwardId].next
      );
      this._currentIteratorFowardData =
        this.nodes[this._currentIteratorForwardId].data;
    }
    return {
      done: done,
      value: this._currentIteratorForwardId,
    };
  }
  traverseValuesForward(): IteratorResult<T | false> {
    let done = false;
    if (this.nodes[this._currentIteratorForwardId].next == "tail") {
      done = true;
      this._currentIteratorForwardId = "head";
    } else {
      this._currentIteratorForwardId = <string>(
        this.nodes[this._currentIteratorForwardId].next
      );
      this._currentIteratorFowardData =
        this.nodes[this._currentIteratorForwardId].data;
    }
    return {
      done: done,
      value: this._currentIteratorFowardData,
    };
  }
  traverseKeyValuesForward(): IteratorResult<{
    key: string;
    value: T | false;
  }> {
    let done = false;
    if (this.nodes[this._currentIteratorForwardId].next == "tail") {
      done = true;
      this._currentIteratorForwardId = "head";
    } else {
      this._currentIteratorForwardId = <string>(
        this.nodes[this._currentIteratorForwardId].next
      );
      this._currentIteratorFowardData =
        this.nodes[this._currentIteratorForwardId].data;
    }
    return {
      done: done,
      value: {
        key: this._currentIteratorForwardId,
        value: this._currentIteratorFowardData,
      },
    };
  }

  traverseIDsBackward(): IteratorResult<string> {
    let done = false;
    if (this.nodes[this._currentIteratorBackwardId].prev == "head") {
      done = true;
      this._currentIteratorBackwardId = "tail";
    } else {
      this._currentIteratorBackwardId = <string>(
        this.nodes[this._currentIteratorBackwardId].prev
      );
    }
    return {
      done: done,
      value: this._currentIteratorBackwardId,
    };
  }
  traverseValuesBackward(): IteratorResult<T | false> {
    let done = false;
    if (this.nodes[this._currentIteratorBackwardId].prev == "head") {
      done = true;
      this._currentIteratorBackwardId = "tail";
    } else {
      this._currentIteratorBackwardId = <string>(
        this.nodes[this._currentIteratorBackwardId].prev
      );
      this._currentIteratorBackwardData =
        this.nodes[this._currentIteratorBackwardId].data;
    }
    return {
      done: done,
      value: this._currentIteratorBackwardData,
    };
  }
  traverseKeyValuesBackward(): IteratorResult<{
    key: string;
    value: T | false;
  }> {
    let done = false;
    if (this.nodes[this._currentIteratorBackwardId].prev == "head") {
      done = true;
      this._currentIteratorBackwardId = "tail";
    } else {
      this._currentIteratorBackwardId = <string>(
        this.nodes[this._currentIteratorBackwardId].prev
      );
      this._currentIteratorBackwardData =
        this.nodes[this._currentIteratorBackwardId].data;
    }
    return {
      done: done,
      value: {
        key: this._currentIteratorBackwardId,
        value: this._currentIteratorBackwardData,
      },
    };
  }

  exists(id: string) {
    if (this.nodes[id] === undefined) {
      return false;
    } else {
      return true;
    }
  }

  getKVP(id: string): { key: string; value: T | false } | false {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    const node = this.nodes[id];
    if (!node) {
      return false;
    }
    return { key: id, value: node.data };
  }

  getNextKVP(id: string): { key: string; value: T | false } | false {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    if (!this.nodes[id]) {
      throw new Error(`${id} does not exist`);
    }
    const node = this.nodes[id];
    if (!node.next || node.next == "tail") return false;
    const nextNode = this.nodes[node.next];
    return { key: node.next, value: nextNode.data };
  }

  getPrevKVP(id: string): { key: string; value: T | false } | false {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    const node = this.nodes[id];
    if (!node.prev || node.prev == "head") return false;
    const nextNode = this.nodes[node.prev];
    return { key: node.prev, value: nextNode.data };
  }

  getNextID(id: string): string | false {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    const node = this.nodes[id];
    if (!node.next || node.next == "tail") return false;
    return node.next;
  }
  getPrevID(id: string): string | false {
    if (!this.exists(id)) {
      throw new Error(`${id} does not exist.`);
    }
    const node = this.nodes[id];
    if (!node.prev || node.prev == "head") return false;
    return node.prev;
  }

  isBefore(startId: string, idLookingFor: string) {
    if (!this.exists(startId)) {
      throw new Error(`${startId} does not exist.`);
    }
    if (!this.exists(idLookingFor)) {
      throw new Error(`${idLookingFor} does not exist.`);
    }
    if (startId == idLookingFor) return true;
    const startNode = this.nodes[startId];
    if (startNode.prev == idLookingFor) return true;
    let prev = startNode.prev;
    while (prev) {
      if (prev == idLookingFor) {
        prev = false;
        return true;
      }
      const newNode = this.nodes[prev];
      prev = newNode.prev;
      if (prev == "head") break;
    }
    return false;
  }
  isAfter(startId: string, idLookingFor: string) {
    if (!this.exists(startId)) {
      throw new Error(`${startId} does not exist.`);
    }
    if (!this.exists(idLookingFor)) {
      throw new Error(`${idLookingFor} does not exist.`);
    }
    if (startId == idLookingFor) return true;
    const startNode = this.nodes[startId];
    if (startNode.next == idLookingFor) return true;
    let next = startNode.next;
    while (next) {
      if (next == idLookingFor) {
        next = false;
        return true;
      }
      const newNode = this.nodes[next];
      next = newNode.prev;
      if (next == "tail") break;
    }
    return false;
  }
}