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]];
  }
}