2
\$\begingroup\$

Implementation is based on the MVC design pattern, with callbacks to allow model and view to communicate with controller.

Concerns:

It's not ideal to have async code inside the model, i.e the model should be as close to a basic hashtable implementation as possible. However since we need to set a chain of calls to the view to animate things while in the middle of the model methods, I couldn't see another way.

In the middle of animations the user trying to insert new keys would cause problems, so I temporarily disable the ability to click on the buttons. This works well from the clients point of view, but in terms of code I'm wondering if there's a cleaner way to do it.

hashtable.ts

const enum ModelMessages {
  Searching,
  Found,
  UpdateVal,
  ExpandArray,
  NotFound,
}

// implementation of a hashtable with linear probing
class HashTable {
  private readonly notifyController: (message: ModelMessages, arg: any) => void;
  private readonly LOAD_FACTOR: number;
  private keys: (number | null)[];
  private entryCount: number;
  private arrayLength: number;

  constructor(
    initialCapacity: number,
    notify: (message: ModelMessages, arg: any) => void
  ) {
    this.notifyController = notify;
    this.LOAD_FACTOR = 0.75;
    this.keys = [];
    this.entryCount = 0;
    this.arrayLength = initialCapacity;
  }

  public async add(key: number): Promise<void> {
    let index;
    let offset = 0;

    do {
      index = this.hashFunction(key + offset);
      offset++;
      await this.notifyController(ModelMessages.Searching, index);
    } while (this.keys[index] !== undefined && this.keys[index] !== key);

    await this.notifyController(ModelMessages.Found, index);
    await this.notifyController(ModelMessages.UpdateVal, [index, key]);

    this.entryCount += this.keys[index] === undefined ? 1 : 0;
    this.keys[index] = key;
    this.handleArrayResize();
  }

  public async contains(key: number): Promise<boolean> {
    return (await this.getIndexOfKey(key)) !== -1;
  }

  public clear(): void {
    this.keys = [];
    this.entryCount = 0;
  }

  public async delete(key: number): Promise<boolean> {
    const index = await this.getIndexOfKey(key);

    if (index === -1) {
      return false;
    }

    this.keys[index] = null;

    await this.notifyController(ModelMessages.UpdateVal, [index, null]);

    return true;
  }

  private handleArrayResize(): void {
    if (this.arrayLength * this.LOAD_FACTOR < this.entryCount) {
      this.expandArray();
    }
  }

  private hashFunction(arg: number): number {
    return Math.abs(arg) % this.arrayLength;
  }

  private async expandArray(): Promise<void> {
    const oldKeyArray = this.keys;

    this.clear();
    this.arrayLength *= 2;
    await this.notifyController(ModelMessages.ExpandArray, this.arrayLength);

    for (let i = 0; i < this.arrayLength / 2; i++) {
      if (oldKeyArray[i] !== undefined && oldKeyArray[i] !== null) {
        await this.add(<number>oldKeyArray[i]);
      }
    }
  }

  private async getIndexOfKey(key: number): Promise<number> {
    let index;
    let offset = 0;

    do {
      index = this.hashFunction(key + offset);
      await this.notifyController(ModelMessages.Searching, index);

      if (this.keys[index] === undefined) {
        await this.notifyController(ModelMessages.NotFound, index);
        return -1;
      }

      offset++;
    } while (this.keys[index] !== key);

    await this.notifyController(ModelMessages.Found, index);

    return index;
  }
}

controller.ts

const hashtable = new HashTable(8, readMessageFromModel);
const view = new View(8, readMessageFromView);

async function readMessageFromView(
  message: ViewMessages,
  arg: any
): Promise<void> {
  switch (message) {
    case ViewMessages.Search:
      await hashtable.contains(<number>arg);
      break;
    case ViewMessages.Insert:
      await hashtable.add(<number>arg);
      break;
    case ViewMessages.Delete:
      await hashtable.delete(<number>arg);
      break;
    case ViewMessages.Clear:
      hashtable.clear();
      view.resetArray();
      break;
    default:
      throw "View has notified controller with unsupported type";
  }
}

async function readMessageFromModel(
  message: ModelMessages,
  arg: any
): Promise<void> {
  switch (message) {
    case ModelMessages.Searching:
      await view.highlightSearching(<number>arg);
      break;
    case ModelMessages.Found:
      await view.highlightFound(<number>arg);
      break;
    case ModelMessages.NotFound:
      await view.highlightNotFound(<number>arg);
      break;
    case ModelMessages.UpdateVal:
      view.updateCellValueAt.apply(view, <[number, number | null]>arg);
      break;
    case ModelMessages.ExpandArray:
      view.expandArray(<number>arg);
      break;
    default:
      throw "Model has notified controller with unsupported type";
  }
}

view.ts

const enum ViewMessages {
  Insert,
  Search,
  Delete,
  Clear,
}

class View {
  private arrayLength: number;
  private readonly notifyController: (message: ViewMessages, arg: any) => void;
  private readonly ARRAY_WIDTH: number = 1500;

  constructor(
    defaultLength: number,
    notify: (message: ViewMessages, arg: any) => void
  ) {
    this.arrayLength = defaultLength;
    this.notifyController = notify;
    this.initialiseView();
  }

  public async highlightFound(index: number): Promise<void> {
    await this.highlightGeneric(index, "#32CD32");
  }

  public async highlightSearching(index: number): Promise<void> {
    await this.highlightGeneric(index, "#33D5FF");
  }

  public async highlightNotFound(index: number): Promise<void> {
    await this.highlightGeneric(index, "red");
  }

  public updateCellValueAt(index: number, val: number | null): void {
    if (val !== null) {
      this.getCellInDOM(index).innerHTML = `${val}`;
    } else {
      this.getCellInDOM(index).innerHTML = "⚰️";
    }
  }

  public expandArray(newSize: number): void {
    this.arrayLength = newSize;
    this.resetArray();
  }

  public resetArray(): void {
    this.clearArray();
    this.createArrayInDOM();
  }

  private async highlightGeneric(index: number, color: string): Promise<void> {
    this.getCellInDOM(index).style.backgroundColor = color;

    await this.delay();

    this.getCellInDOM(index).style.backgroundColor = "white";
  }

  private clearArray(): void {
    const array = this.getArrayinDOM(document.querySelector("#array"));

    array.innerHTML = "";
  }

  private initialiseView(): void {
    this.createArrayInDOM();
    this.addMenuClickListeners();
  }

  private addMenuClickListeners(): void {
    document
      .querySelector("#search")
      ?.addEventListener("click", () => this.searchForKey());
    document
      .querySelector("#insert")
      ?.addEventListener("click", () => this.insertKey());
    document
      .querySelector("#delete")
      ?.addEventListener("click", () => this.deleteKey());
    document
      .querySelector("#clear")
      ?.addEventListener("click", () => this.clear());
  }

  private clear(): void {
    this.notifyController(ViewMessages.Clear, null);
  }

  private async notifyControllerWithInputValue(
    inputField: HTMLInputElement | null,
    message: ViewMessages
  ): Promise<void> {
    this.blockMenuButtons();

    if (inputField !== null) {
      const input = <HTMLInputElement>inputField;

      if (!isNaN(parseInt(input.value))) {
        await this.notifyController(message, parseInt(input.value));
      }
    } else {
      throw "Input field argument was null";
    }

    this.enableMenuButtons();
  }

  private searchForKey(): void {
    this.notifyControllerWithInputValue(
      document.querySelector("#search-input"),
      ViewMessages.Search
    );
  }

  private insertKey(): void {
    this.notifyControllerWithInputValue(
      document.querySelector("#insert-input"),
      ViewMessages.Insert
    );
  }

  private deleteKey(): void {
    this.notifyControllerWithInputValue(
      document.querySelector("#delete-input"),
      ViewMessages.Delete
    );
  }

  private blockMenuButtons(): void {
    this.getButtonInDOM(document.querySelector("#search")).style.pointerEvents =
      "none";
    this.getButtonInDOM(document.querySelector("#insert")).style.pointerEvents =
      "none";
    this.getButtonInDOM(document.querySelector("#delete")).style.pointerEvents =
      "none";
    this.getButtonInDOM(document.querySelector("#clear")).style.pointerEvents =
      "none";
  }

  private enableMenuButtons(): void {
    this.getButtonInDOM(document.querySelector("#search")).style.pointerEvents =
      "auto";
    this.getButtonInDOM(document.querySelector("#insert")).style.pointerEvents =
      "auto";
    this.getButtonInDOM(document.querySelector("#delete")).style.pointerEvents =
      "auto";
    this.getButtonInDOM(document.querySelector("#clear")).style.pointerEvents =
      "auto";
  }

  private getButtonInDOM(button: HTMLButtonElement | null): HTMLButtonElement {
    if (button === null) {
      throw "Button supplied is null";
    } else {
      return <HTMLButtonElement>button;
    }
  }

  private createArrayInDOM(): void {
    const array = this.getArrayinDOM(document.querySelector("#array"));
    const row = document.createElement("tr");

    array.style.width = `${this.ARRAY_WIDTH}px`;
    array.append(row);

    for (let i = 0; i < this.arrayLength; i++) {
      row.append(this.createCellInDOM(i));
    }
  }

  private createCellInDOM(index: number): HTMLTableCellElement {
    const newCell = document.createElement("td");

    newCell.style.width = `${this.ARRAY_WIDTH / this.arrayLength}px`;
    newCell.style.height = `${this.ARRAY_WIDTH / this.arrayLength}px`;
    newCell.style.fontSize = `${(this.ARRAY_WIDTH / this.arrayLength) * 4}%`;
    newCell.className = "cell";

    return newCell;
  }

  private getCellInDOM(index: number): HTMLTableCellElement {
    const arrayDOM = this.getArrayinDOM(document.querySelector("#array"));
    const rowDOM = arrayDOM.rows[0];
    const cellDOM = rowDOM.cells[index];

    return cellDOM;
  }

  private getArrayinDOM(array: HTMLTableElement | null): HTMLTableElement {
    if (array === null) {
      throw "Element supplied is null";
    } else {
      return <HTMLTableElement>array;
    }
  }

  private delay(): Promise<string> {
    const delayTimeInMilliseconds = 300;

    return new Promise((resolve) => {
      setTimeout(resolve, delayTimeInMilliseconds);
    });
  }
}
```
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.