LRU.v1

class LRUElement {
  constructor (data, master, index) {
    this.data = data;
    this.master = master;
    this.index = index;
    this.lastAccess = new Date();
  }

  get value () {
    return this.data;
  }

  get isDeleted () {
    return this.data === undefined;
  }

  access () {
    this.lastAccess = new Date();
    this.master.update(this.index);
  }
}

class LRU {
  constructor (maxSize, type) {
    this.maxSize = maxSize;
    this.size = 0;
    this.container = [];
    this.type = type;
  }

  get isFull () {
    return this.maxSize === this.size;
  }

  insert (data) {
    if (!(data instanceof this.type))
      throw new TypeError('LRU insert: should be '
                          + this.type.name
                          + '. Given value is a '
                          + typeof data);

    var array = this.container;
    var holder = null;
    if (this.isFull) {
      delete array[0].data;
      holder = array[0] = new LRUElement(data, this, 0);
      this.update(0);
    } else {
      holder = array[this.size] = new LRUElement(data, this, this.size);
      this.size ++;
    }
    return holder;
  }

  update (index) {
    var array = this.container;

    var left = x => (x + 1) * 2 - 1;
    var right = x => (x + 1) * 2;
    var swap = (i1, i2) => {
      var t = array[i1];
      array[i1] = array[i2];
      array[i2] = t;

      array[i1].index = i1;
      array[i2].index = i2;
    }

    var leftIndex = left(index);
    var rightIndex = right(index);

    var leftable = leftIndex < this.size;
    var rightable = rightIndex < this.size;
    if (leftable && rightable) {
      var isLeftLess = array[leftIndex].lastAccess < array[rightIndex].lastAccess
      if (isLeftLess) {
        swap(index, leftIndex);
        this.update(leftIndex);
      }
      else {
        swap(index, rightIndex);
        this.update(rightIndex);
      }
    } else if (leftable) {
      swap(index, leftIndex);
    }
  }
}