HeapSet - unordered heap with random access and pop() and unshift()

heapset.js

export default class HeapSet {

  constructor (values) {
    this._values = values;
    this._list = new Array(values.length * 3);
    this._idToIndex = {};

    const list = this._list;
 
    for (let i = 0, prev = -1; i < values.length; i++) {
      this._idToIndex[values[i]] = i;
      list[i * 3]     = i;
      list[i * 3 + 1] = prev;
      list[i * 3 + 2] = i + 1;
      prev = i;
    }
    list[list.length - 1] = -1;

    this._end   = values.length - 1;
    this._begin = 0;
    this._size = values.length;
  }


  pop () {
    if (this._size === 0) {
      return undefined;
    }
    const list = this._list;
    const end = this._end * 3;
    const prev = list[end + 1];
    const val  = this._values[list[end]];

    list[end]     = -1;
    list[end + 1] = -1;
    list[end + 2] = -1;

    this._end = prev;
    this._size--;

    return val;
  }


  shift () {
    if (this._size === 0) {
      return undefined;
    }
    const list = this._list;
    const begin = this._begin * 3;
    const next = list[begin + 2];
    const val  = this._values[list[begin]];

    list[begin]     = -1;
    list[begin + 1] = -1;
    list[begin + 2] = -1;

    this._begin = next;
    this._size--;

    return val;
  }


  has (id) {
    const index = this._idToIndex[id];
    return (index !== undefined && this._list[index * 3] !== -1);
  }


  remove (id) {
    let pos = this._idToIndex[id];

    const index = pos * 3;
    const list = this._list;

    if (list[index] === -1) { // already removed;
      return undefined; 
    }
    const prev = list[index + 1];
    const next = list[index + 2];

    if (next !== -1) list[next * 3 + 1] = prev;
    if (prev !== -1) list[prev * 3 + 2] = next;

    if (pos === this._begin) {
      this._begin = next;
    }

    if (pos === this._end) {
      this._end = prev;
    }

    const val = this._values[list[index]];
    list[index] = list[index + 1] = list[index + 2] = -1;

    this._size--;

    return val;
  }

  get size () {
    return this._size;
  }


  begin () {
    return this._values[this._list[this._begin * 3]];
  }

  end () {
    return this._values[this._list[this._end * 3]];
  }
} 

heapset.test.js

const { assert } = require('chai');
const HeapSet    = require('./heapset');

describe ('HeapSet', () => {

  it ('constructs from an array of values', () => {
    const h = new HeapSet([12, -5, 6, 5]);
    assert.deepEqual(h._values, [12, -5, 6, 5]);
    assert.equal(h.size, 4);
  });

  
  it ('supports pop()', () => {
    const values = [12, -5, 6, 5];
    const h = new HeapSet(values.slice());

    while (values.length !== 0) {
      assert.equal(h.end(), values[values.length - 1]);
      assert.equal(h.pop(), values.pop());
      assert.equal(h.size, values.length);
    }
    assert.isUndefined(h.pop());

    assert.isUndefined(h.begin());
    assert.isUndefined(h.end());
  });


  it ('supports shift()', () => {
    const values = [12, -5, 6, 5];
    const h = new HeapSet(values.slice());

    while (values.length !== 0) {
      assert.equal(h.begin(), values[0]);
      assert.equal(h.shift(), values.shift());
      assert.equal(h.size, values.length);
    }

    assert.isUndefined(h.shift());

    assert.isUndefined(h.begin());
    assert.isUndefined(h.end());
  });


  it ('supports random remove', () => {
    const values = [12, -5, 6, 5];
    const h = new HeapSet(values.slice());

    while (values.length !== 0) {
      const v = values.shift();
      assert.equal(h.remove(v), v);
      assert.equal(h.size, values.length);
    }
  });


  it ('supports random access', () => {
    const h = new HeapSet([12, -5, 6, 5]);
    [12, -5, 6, 5].forEach(v => assert.isTrue(h.has(v)));

    assert.isFalse(h.has(115));

    h.remove(6);
    assert.isFalse(h.has(6));
  });
});