hash-table-separate-chaining.spec.ts

import 'mocha';
import { expect } from 'chai';
import { HashTableSeparateChaining } from '../../../src/ts/index';
import MyObj from './my-obj';

describe('HashTableSeparateChaining', () => {
  const A = 'Jonathan';
  const B = 'Jamie';
  const C = 'Sue';

  it('starts empty', () => {
    const hashTable = new HashTableSeparateChaining<number, number>();
    expect(hashTable.size()).to.equal(0);
    expect(hashTable.isEmpty()).to.equal(true);
  });

  it('generates hashcode', () => {
    // numbers
    let hashTable: any = new HashTableSeparateChaining<number, number>();
    expect(hashTable.hashCode(1)).to.equal(1);
    expect(hashTable.hashCode(10)).to.equal(10);
    expect(hashTable.hashCode(100)).to.equal(100);
    expect(hashTable.hashCode(1000)).to.equal(1000);

    // strings
    hashTable = new HashTableSeparateChaining<string, number>();
    expect(hashTable.hashCode('1')).to.equal(12);
    expect(hashTable.hashCode('10')).to.equal(23);
    expect(hashTable.hashCode('100')).to.equal(34);
    expect(hashTable.hashCode('1000')).to.equal(8);
    expect(hashTable.hashCode('a')).to.equal(23);
    expect(hashTable.hashCode('A')).to.equal(28);
    expect(hashTable.hashCode('Aba')).to.equal(1);

    // objects
    hashTable = new HashTableSeparateChaining<MyObj, MyObj>();
    const myObjList = [];
    for (let i = 1; i <= 5; i++) {
      myObjList.push(new MyObj(i, i + 1));
    }
    expect(hashTable.hashCode(myObjList[0])).to.equal(1);
    expect(hashTable.hashCode(myObjList[1])).to.equal(3);
    expect(hashTable.hashCode(myObjList[2])).to.equal(5);
    expect(hashTable.hashCode(myObjList[3])).to.equal(7);
    expect(hashTable.hashCode(myObjList[4])).to.equal(9);
  });

  it('puts undefined and null keys and values', () => {
    const hashTable = new HashTableSeparateChaining<string, number>();

    expect(hashTable.put('undefined', undefined)).to.equal(false);
    expect(hashTable.get('undefined')).to.equal(undefined);

    expect(hashTable.put('undefined', 1)).to.equal(true);
    expect(hashTable.get('undefined')).to.equal(1);

    expect(hashTable.put('null', null)).to.equal(false);
    expect(hashTable.get('null')).to.equal(undefined);

    expect(hashTable.put('null', 1)).to.equal(true);
    expect(hashTable.get('null')).to.equal(1);

    hashTable.clear();
    expect(hashTable.put(undefined, undefined)).to.equal(false);
    expect(hashTable.get(undefined)).to.equal(undefined);

    expect(hashTable.put(undefined, 1)).to.equal(false);
    expect(hashTable.get(undefined)).to.equal(undefined);

    expect(hashTable.put(null, null)).to.equal(false);
    expect(hashTable.get(null)).to.equal(undefined);

    expect(hashTable.put(null, 1)).to.equal(false);
    expect(hashTable.get(null)).to.equal(undefined);
  });

  it('puts values with number key without collisions', () => {
    const min = 1;
    const max = 5;
    const size = max - min + 1;
    const hashTable = new HashTableSeparateChaining<number, number>();

    for (let i = min; i <= max; i++) {
      expect(hashTable.put(i, i)).to.equal(true);
    }
    expect(hashTable.size()).to.equal(size);

    const table = hashTable.getTable();
    for (let i = min; i <= max; i++) {
      const linkedList = table[i];
      expect(linkedList.size()).to.equal(1);
      const valuePair = linkedList.getHead();
      expect(valuePair.element.key).to.equal(i);
      expect(valuePair.element.value).to.equal(i);
    }
  });

  it('puts values with string key without collisions', () => {
    const hashTable = new HashTableSeparateChaining<string, number>();

    expect(hashTable.put('1', 1)).to.equal(true);
    expect(hashTable.put('10', 10)).to.equal(true);
    expect(hashTable.put('100', 100)).to.equal(true);
    expect(hashTable.put('1000', 1000)).to.equal(true);

    const table = hashTable.getTable();

    let linkedList = table[12];
    expect(linkedList.size()).to.equal(1);
    let valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal('1');
    expect(valuePair.element.value).to.equal(1);

    linkedList = table[23];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal('10');
    expect(valuePair.element.value).to.equal(10);

    linkedList = table[34];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal('100');
    expect(valuePair.element.value).to.equal(100);

    linkedList = table[8];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal('1000');
    expect(valuePair.element.value).to.equal(1000);
  });

  it('puts values with object key without collisions', () => {
    const hashTable = new HashTableSeparateChaining<MyObj, MyObj>();

    const myObjList = [];
    for (let i = 1; i <= 5; i++) {
      myObjList.push(new MyObj(i, i + 1));
      expect(hashTable.put(myObjList[i - 1], myObjList[i - 1])).to.equal(true);
    }

    const table = hashTable.getTable();

    let linkedList = table[1];
    expect(linkedList.size()).to.equal(1);
    let valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal(myObjList[0]);
    expect(valuePair.element.value).to.equal(myObjList[0]);

    linkedList = table[3];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal(myObjList[1]);
    expect(valuePair.element.value).to.equal(myObjList[1]);

    linkedList = table[5];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal(myObjList[2]);
    expect(valuePair.element.value).to.equal(myObjList[2]);

    linkedList = table[7];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal(myObjList[3]);
    expect(valuePair.element.value).to.equal(myObjList[3]);

    linkedList = table[9];
    expect(linkedList.size()).to.equal(1);
    valuePair = linkedList.getHead();
    expect(valuePair.element.key).to.equal(myObjList[4]);
    expect(valuePair.element.value).to.equal(myObjList[4]);
  });

  it('puts values with collisions', () => {
    const min = 1;
    const max = 5;
    const size = max - min + 1;
    const hashTable = new HashTableSeparateChaining<number, number>();

    for (let i = min; i <= max; i++) {
      expect(hashTable.put(i, i)).to.equal(true);
    }
    expect(hashTable.size()).to.equal(size);

    for (let i = min; i <= max; i++) {
      expect(hashTable.put(i, i + 10)).to.equal(true);
    }
    expect(hashTable.size()).to.equal(size * 2);

    for (let i = min; i <= max; i++) {
      expect(hashTable.put(i, i + 100)).to.equal(true);
    }
    expect(hashTable.size()).to.equal(size * 3);

    const table = hashTable.getTable();
    for (let i = min; i <= max; i++) {
      const linkedList = table[i];
      expect(linkedList.size()).to.equal(3);

      let valuePair = linkedList.getHead();
      expect(valuePair.element.key).to.equal(i);
      expect(valuePair.element.value).to.equal(i);

      valuePair = valuePair.next;
      expect(valuePair.element.key).to.equal(i);
      expect(valuePair.element.value).to.equal(i + 10);

      valuePair = valuePair.next;
      expect(valuePair.element.key).to.equal(i);
      expect(valuePair.element.value).to.equal(i + 100);
    }
  });

  it('removes elements without collisions', () => {
    const min = 1;
    const max = 5;
    const size = max - min + 1;
    const hashTable = new HashTableSeparateChaining<number, number>();

    for (let i = min; i <= max; i++) {
      expect(hashTable.put(i, i)).to.equal(true);
    }
    expect(hashTable.size()).to.equal(size);

    for (let i = min; i <= max; i++) {
      expect(hashTable.remove(i)).to.equal(true);
    }

    // elements do not exist
    for (let i = min; i <= max; i++) {
      expect(hashTable.remove(i)).to.equal(false);
    }

    expect(hashTable.isEmpty()).to.equal(true);
  });

  function addValuesCollision() {
    const hashTable = new HashTableSeparateChaining<string, string>();

    expect(hashTable.put(A, `${A}@email.com`)).to.equal(true);
    expect(hashTable.put(B, `${B}@email.com`)).to.equal(true);
    expect(hashTable.put(C, `${C}@email.com`)).to.equal(true);
    expect(hashTable.size()).to.equal(3);

    const expectedHash = 5;
    expect(hashTable.hashCode(A)).to.equal(expectedHash);
    expect(hashTable.hashCode(B)).to.equal(expectedHash);
    expect(hashTable.hashCode(C)).to.equal(expectedHash);

    expect(hashTable.getTable()[expectedHash].size()).to.equal(3);

    return hashTable;
  }

  function removeWithCollision(a: string, b: string, c: string) {
    const hashTable = addValuesCollision();

    expect(hashTable.remove(a)).to.equal(true);
    expect(hashTable.get(a)).to.equal(undefined);
    expect(hashTable.get(b)).to.not.equal(undefined);
    expect(hashTable.get(c)).to.not.equal(undefined);

    expect(hashTable.remove(b)).to.equal(true);
    expect(hashTable.get(a)).to.equal(undefined);
    expect(hashTable.get(b)).to.equal(undefined);
    expect(hashTable.get(c)).to.not.equal(undefined);

    expect(hashTable.remove(c)).to.equal(true);
    expect(hashTable.get(a)).to.equal(undefined);
    expect(hashTable.get(b)).to.equal(undefined);
    expect(hashTable.get(c)).to.equal(undefined);

    expect(hashTable.isEmpty()).to.equal(true);
  }

  it('removes elements with collisions', () => {
    // test all possibilities for removal
    removeWithCollision(A, B, C);
    removeWithCollision(A, C, B);
    removeWithCollision(B, A, C);
    removeWithCollision(B, C, A);
    removeWithCollision(C, A, B);
    removeWithCollision(C, B, A);
  });

  it('returns toString primitive types without collisions', () => {
    const hashTable = new HashTableSeparateChaining<number, number>();

    expect(hashTable.toString()).to.equal('');

    hashTable.put(1, 1);
    expect(hashTable.toString()).to.equal('{1 => [#1: 1]}');

    hashTable.put(2, 2);
    expect(hashTable.toString()).to.equal('{1 => [#1: 1]},{2 => [#2: 2]}');

    hashTable.clear();
    expect(hashTable.toString()).to.equal('');
  });

  it('returns toString primitive types without collisions', () => {
    const hashTable = new HashTableSeparateChaining<string, number>();

    hashTable.put('el1', 1);
    expect(hashTable.toString()).to.equal('{36 => [#el1: 1]}');

    hashTable.put('el2', 2);
    expect(hashTable.toString()).to.equal('{0 => [#el2: 2]},{36 => [#el1: 1]}');
  });

  it('returns toString objects without collisions', () => {
    const hashTable = new HashTableSeparateChaining<MyObj, MyObj>();

    let myObj = new MyObj(1, 2);
    hashTable.put(myObj, myObj);
    expect(hashTable.toString()).to.equal('{1 => [#1|2: 1|2]}');

    myObj = new MyObj(3, 4);
    hashTable.put(myObj, myObj);
    expect(hashTable.toString()).to.equal(
      '{1 => [#1|2: 1|2]},{5 => [#3|4: 3|4]}'
    );
  });

  it('returns toString with collisions', () => {
    const hashTable = new HashTableSeparateChaining<number, number>();

    expect(hashTable.toString()).to.equal('');

    hashTable.put(1, 1);
    expect(hashTable.toString()).to.equal('{1 => [#1: 1]}');

    hashTable.put(2, 2);
    expect(hashTable.toString()).to.equal('{1 => [#1: 1]},{2 => [#2: 2]}');

    hashTable.put(1, 10);
    expect(hashTable.toString()).to.equal('{1 => [#1: 1],[#1: 10]},{2 => [#2: 2]}');

    hashTable.clear();
    expect(hashTable.toString()).to.equal('');
  });
});