LRU Cache in ECMAScript

Question

I wrote this for a CodeWars challenge while trying to learn ECMAScript and would really like to have some advice on how it could be improved.

What I don't like about this code myself, but am unsure on how to improve:

• I didn't yet found a way to have a class in ECMAScript that mixes public and private methods in a way, where the public methods (and only them) can still access private methods and vars.
• (Partly caused by the point above) I think the code is way too verbose and bloated. Too much of it is wasted on language specific implementation details. There must be a smarter way to do this - I feel like I could write the same functionality in PHP using 10% of the lines I needed now.

function LRUCache(capacity, init) {

  this._capacity = capacity;
  this._size = 0;
  this._accessMap = [];
  this._items = [];
  this._frozenMethods = ['cache', 'delete'];  
  this._functionalProps = ['size', 'capacity'];

  this.cache = function(key, value) {

    if( this._accessMap.indexOf(key) == -1 ) {
      this._addNewItem(key);
    }

    this._items[key] = this[key] = value;
    this._updateAccessMap(key);

    return this;
  },
  this.delete = function(key) {

    if(this._frozenMethods.indexOf(key) !== -1 ||
    this._functionalProps.indexOf(key) !== -1) {
      return false;
    }

    if( this._accessMap.indexOf(key) === -1 ) {
      return true;
    }

    delete this[key];
    delete this._items[key];
    this._size--;

    this._updateAccessMap(key, true);

    return true;
  },
  this._removeOldest = function() {
    var key = this._accessMap[0];

    this.delete(key);
  },
  this._updateAccessMap = function(key, remove) {

    index = this._accessMap.indexOf(key);

    if( index !== -1) {
      this._accessMap.splice(index, 1);
    }

    if(!remove) {
      this._accessMap.push(key);
    }
  },
  this._addNewItem = function(key) {

    this._size++;

    if(this._size > this._capacity) {
      this._removeOldest();
    }

    Object.defineProperty(this, key, {
      get: function() {
        this._updateAccessMap(key);

        return this._items[key];
      },
      set: function(v) {
        this._items[key] = v;
        this._updateAccessMap(key);
        return this;
      },
      enumerable: true,
      configurable: true
    });
  };

  var obj = this;

  this._frozenMethods.map( function(v) {
    Object.defineProperty(obj, v, {
      enumerable: false,
      writable: false,
      configurable: false
    });
  });

  ['_items', '_capacity', '_accessMap', '_frozenMethods','_size', '_functionalProps',
  '_removeOldest','_updateAccessMap','_addNewItem'].map( function(v) {
    Object.defineProperty(obj, v, {
      enumerable: false,
      configurable: true
    });
  });

  Object.defineProperty(this, 'capacity', {
    set: function(v) {

      while(this.size > v) {
        this._removeOldest();
      }

      this._capacity = v;
    },
    get: function() {
      return this._capacity;
    },
    configurable: false
  });


  Object.defineProperty(this, 'size', {
    set: function(v) {
      return false;
    },
    get: function() {
      return this._size;
    },
    configurable: false
  });

  if(init) {
    for(var attr in init) {
      if( !init.hasOwnProperty(attr) ) {
        continue;
      }
      this.cache(attr, init[attr]);
    }
  }
}

Answer 1

I didn't yet found a way to have a class in ECMAScript that mixes public and private methods in a way, where the public methods (and only them) can still access private methods and vars.

JavaScript ain't classical OOP. Don't force it to be like one. The default inheritance pattern in JS is prototypal, and everything is public and methods are shared across instances.

You could emulate private by defining your data not as properties but as vars in the constructor. However, this requires that your methods be defined in the constructor to have access to them. This means that your methods are created on a per-instance basis, rather than shared via the prototype.

Anyways, off to a review of your code:

this._items = [];

I'm pretty sure you wanted a hash {} instead of an array.

this._items[key] = this[key] = value;

I'm not sure why you want to add the key-value pair as a property of the cache object. I'm pretty sure this is why you have to guard against overriding your methods. I suggest you don't. Make your object just an interface. Don't put your data on it. Just put it in _items.

this._frozenMethods.map( function(v) {
  Object.defineProperty(obj, v, {
    enumerable: false,
    writable: false,
    configurable: false
  });
});

['_items', '_capacity', '_accessMap', '_frozenMethods','_size', '_functionalProps',
'_removeOldest','_updateAccessMap','_addNewItem'].map( function(v) {
  Object.defineProperty(obj, v, {
    enumerable: false,
    configurable: true
  });
});

map is a special iterator method. It runs on each array item and expects a return value for each item to form the new array it creates. If you just end us using it to loop through, then forEach is a better choice. Less confusing.

Additionally, naming variables properly is a must. Explicit is better than implicit, and naming your variables explicitly is better for readability than having to guess what they're for. It takes 5 seconds for a developer to know a purpose of a variable if named properly, rather than 5 mins because the developer has to read through the implementation.

this.delete = function(key) {

IIRC, IE8 and some other browsers have issues when using some keywords as property/function names. Best use alternative names like remove.

Anyways, here's a simplified implementation. Should be straightforward:

function LruCache(capacity){
  this._capacity = capacity || 1;
  this._accessMap = [];
  this._items = {};
}

LruCache.prototype.addItem = function(key, value){
  if(this._accessMap.length >= this._capacity) this.removeOldest();
  this._accessMap.push(key);
  this._items[key] = value;
};

LruCache.prototype.remove = function(key){
  this._accessMap.splice(this._accessMap.indexOf(key), 1);
  delete this._items[key];
};

LruCache.prototype.removeOldest = function(){
  var oldestKey = this._accessMap.shift();
  delete this._items[oldestKey];
};

LruCache.prototype.getCapacity = function(){
  return this._capacity;
};

LruCache.prototype.getSize = function(){
  return this._accessMap.length;
};

LruCache.prototype.getItems = function(){
  var instance = this;
  return Object.keys(this._items).reduce(function(carry, key){
    carry[key] = instance._items[key];
    return carry;
  }, {});
};

If you really want privates by way of closures and throw away the entire concept of shared methods, you can do this:

function LruCache(capacity){
  var _capacity = capacity || 1;
  var _accessMap = [];
  var _items = {};

  function removeOldest(){
    var oldestKey = _accessMap.shift();
    delete _items[oldestKey];
  };

  this.addItem = function(key, value){
    if(_accessMap.length >= _capacity) removeOldest();
    _accessMap.push(key);
    _items[key] = value;
  };

  this.remove = function(key){
    _accessMap.splice(_accessMap.indexOf(key), 1);
    delete _items[key];
  };

  this.getCapacity = function(){
    return _capacity;
  };

  this.getSize = function(){
    return _accessMap.length;
  };

  this.getItems = function(){
    return Object.keys(_items).reduce(function(carry, key){
      carry[key] = _items[key];
      return carry;
    }, {});
  };

}