Skip to content

Instantly share code, notes, and snippets.

@w8r w8r/heapset.js

Created Sep 19, 2018
Embed
What would you like to do?
HeapSet - unordered heap with random access and pop() and unshift()
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]];
}
}
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));
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.