module.exports = LRUCache

// This will be a proper iterable 'Map' in engines that support it,
// or a fakey-fake PseudoMap in older versions.
var Map = require('pseudomap')
var util = require('util')

// A linked list to keep track of recently-used-ness
var Yallist = require('yallist')

// use symbols if possible, otherwise just _props
var symbols = {}
var hasSymbol = typeof Symbol === 'function'
var makeSymbol
/* istanbul ignore if */
if (hasSymbol) {
  makeSymbol = function (key) {
    return Symbol.for(key)
  }
} else {
  makeSymbol = function (key) {
    return '_' + key
  }
}

function priv (obj, key, val) {
  var sym
  if (symbols[key]) {
    sym = symbols[key]
  } else {
    sym = makeSymbol(key)
    symbols[key] = sym
  }
  if (arguments.length === 2) {
    return obj[sym]
  } else {
    obj[sym] = val
    return val
  }
}

function naiveLength () { return 1 }

// lruList is a yallist where the head is the youngest
// item, and the tail is the oldest.  the list contains the Hit
// objects as the entries.
// Each Hit object has a reference to its Yallist.Node.  This
// never changes.
//
// cache is a Map (or PseudoMap) that matches the keys to
// the Yallist.Node object.
function LRUCache (options) {
  if (!(this instanceof LRUCache)) {
    return new LRUCache(options)
  }

  if (typeof options === 'number') {
    options = { max: options }
  }

  if (!options) {
    options = {}
  }

  var max = priv(this, 'max', options.max)
  // Kind of weird to have a default max of Infinity, but oh well.
  if (!max ||
      !(typeof max === 'number') ||
      max <= 0) {
    priv(this, 'max', Infinity)
  }

  var lc = options.length || naiveLength
  if (typeof lc !== 'function') {
    lc = naiveLength
  }
  priv(this, 'lengthCalculator', lc)

  priv(this, 'allowStale', options.stale || false)
  priv(this, 'maxAge', options.maxAge || 0)
  priv(this, 'dispose', options.dispose)
  this.reset()
}

// resize the cache when the max changes.
Object.defineProperty(LRUCache.prototype, 'max', {
  set: function (mL) {
    if (!mL || !(typeof mL === 'number') || mL <= 0) {
      mL = Infinity
    }
    priv(this, 'max', mL)
    trim(this)
  },
  get: function () {
    return priv(this, 'max')
  },
  enumerable: true
})

Object.defineProperty(LRUCache.prototype, 'allowStale', {
  set: function (allowStale) {
    priv(this, 'allowStale', !!allowStale)
  },
  get: function () {
    return priv(this, 'allowStale')
  },
  enumerable: true
})

Object.defineProperty(LRUCache.prototype, 'maxAge', {
  set: function (mA) {
    if (!mA || !(typeof mA === 'number') || mA < 0) {
      mA = 0
    }
    priv(this, 'maxAge', mA)
    trim(this)
  },
  get: function () {
    return priv(this, 'maxAge')
  },
  enumerable: true
})

// resize the cache when the lengthCalculator changes.
Object.defineProperty(LRUCache.prototype, 'lengthCalculator', {
  set: function (lC) {
    if (typeof lC !== 'function') {
      lC = naiveLength
    }
    if (lC !== priv(this, 'lengthCalculator')) {
      priv(this, 'lengthCalculator', lC)
      priv(this, 'length', 0)
      priv(this, 'lruList').forEach(function (hit) {
        hit.length = priv(this, 'lengthCalculator').call(this, hit.value, hit.key)
        priv(this, 'length', priv(this, 'length') + hit.length)
      }, this)
    }
    trim(this)
  },
  get: function () { return priv(this, 'lengthCalculator') },
  enumerable: true
})

Object.defineProperty(LRUCache.prototype, 'length', {
  get: function () { return priv(this, 'length') },
  enumerable: true
})

Object.defineProperty(LRUCache.prototype, 'itemCount', {
  get: function () { return priv(this, 'lruList').length },
  enumerable: true
})

LRUCache.prototype.rforEach = function (fn, thisp) {
  thisp = thisp || this
  for (var walker = priv(this, 'lruList').tail; walker !== null;) {
    var prev = walker.prev
    forEachStep(this, fn, walker, thisp)
    walker = prev
  }
}

function forEachStep (self, fn, node, thisp) {
  var hit = node.value
  if (isStale(self, hit)) {
    del(self, node)
    if (!priv(self, 'allowStale')) {
      hit = undefined
    }
  }
  if (hit) {
    fn.call(thisp, hit.value, hit.key, self)
  }
}

LRUCache.prototype.forEach = function (fn, thisp) {
  thisp = thisp || this
  for (var walker = priv(this, 'lruList').head; walker !== null;) {
    var next = walker.next
    forEachStep(this, fn, walker, thisp)
    walker = next
  }
}

LRUCache.prototype.keys = function () {
  return priv(this, 'lruList').toArray().map(function (k) {
    return k.key
  }, this)
}

LRUCache.prototype.values = function () {
  return priv(this, 'lruList').toArray().map(function (k) {
    return k.value
  }, this)
}

LRUCache.prototype.reset = function () {
  if (priv(this, 'dispose') &&
      priv(this, 'lruList') &&
      priv(this, 'lruList').length) {
    priv(this, 'lruList').forEach(function (hit) {
      priv(this, 'dispose').call(this, hit.key, hit.value)
    }, this)
  }

  priv(this, 'cache', new Map()) // hash of items by key
  priv(this, 'lruList', new Yallist()) // list of items in order of use recency
  priv(this, 'length', 0) // length of items in the list
}

LRUCache.prototype.dump = function () {
  return priv(this, 'lruList').map(function (hit) {
    if (!isStale(this, hit)) {
      return {
        k: hit.key,
        v: hit.value,
        e: hit.now + (hit.maxAge || 0)
      }
    }
  }, this).toArray().filter(function (h) {
    return h
  })
}

LRUCache.prototype.dumpLru = function () {
  return priv(this, 'lruList')
}

LRUCache.prototype.inspect = function (n, opts) {
  var str = 'LRUCache {'
  var extras = false

  var as = priv(this, 'allowStale')
  if (as) {
    str += '\n  allowStale: true'
    extras = true
  }

  var max = priv(this, 'max')
  if (max && max !== Infinity) {
    if (extras) {
      str += ','
    }
    str += '\n  max: ' + util.inspect(max, opts)
    extras = true
  }

  var maxAge = priv(this, 'maxAge')
  if (maxAge) {
    if (extras) {
      str += ','
    }
    str += '\n  maxAge: ' + util.inspect(maxAge, opts)
    extras = true
  }

  var lc = priv(this, 'lengthCalculator')
  if (lc && lc !== naiveLength) {
    if (extras) {
      str += ','
    }
    str += '\n  length: ' + util.inspect(priv(this, 'length'), opts)
    extras = true
  }

  var didFirst = false
  priv(this, 'lruList').forEach(function (item) {
    if (didFirst) {
      str += ',\n  '
    } else {
      if (extras) {
        str += ',\n'
      }
      didFirst = true
      str += '\n  '
    }
    var key = util.inspect(item.key).split('\n').join('\n  ')
    var val = { value: item.value }
    if (item.maxAge !== maxAge) {
      val.maxAge = item.maxAge
    }
    if (lc !== naiveLength) {
      val.length = item.length
    }
    if (isStale(this, item)) {
      val.stale = true
    }

    val = util.inspect(val, opts).split('\n').join('\n  ')
    str += key + ' => ' + val
  })

  if (didFirst || extras) {
    str += '\n'
  }
  str += '}'

  return str
}

LRUCache.prototype.set = function (key, value, maxAge) {
  maxAge = maxAge || priv(this, 'maxAge')

  var now = maxAge ? Date.now() : 0
  var len = priv(this, 'lengthCalculator').call(this, value, key)

  if (priv(this, 'cache').has(key)) {
    if (len > priv(this, 'max')) {
      del(this, priv(this, 'cache').get(key))
      return false
    }

    var node = priv(this, 'cache').get(key)
    var item = node.value

    // dispose of the old one before overwriting
    if (priv(this, 'dispose')) {
      priv(this, 'dispose').call(this, key, item.value)
    }

    item.now = now
    item.maxAge = maxAge
    item.value = value
    priv(this, 'length', priv(this, 'length') + (len - item.length))
    item.length = len
    this.get(key)
    trim(this)
    return true
  }

  var hit = new Entry(key, value, len, now, maxAge)

  // oversized objects fall out of cache automatically.
  if (hit.length > priv(this, 'max')) {
    if (priv(this, 'dispose')) {
      priv(this, 'dispose').call(this, key, value)
    }
    return false
  }

  priv(this, 'length', priv(this, 'length') + hit.length)
  priv(this, 'lruList').unshift(hit)
  priv(this, 'cache').set(key, priv(this, 'lruList').head)
  trim(this)
  return true
}

LRUCache.prototype.has = function (key) {
  if (!priv(this, 'cache').has(key)) return false
  var hit = priv(this, 'cache').get(key).value
  if (isStale(this, hit)) {
    return false
  }
  return true
}

LRUCache.prototype.get = function (key) {
  return get(this, key, true)
}

LRUCache.prototype.peek = function (key) {
  return get(this, key, false)
}

LRUCache.prototype.pop = function () {
  var node = priv(this, 'lruList').tail
  if (!node) return null
  del(this, node)
  return node.value
}

LRUCache.prototype.del = function (key) {
  del(this, priv(this, 'cache').get(key))
}

LRUCache.prototype.load = function (arr) {
  // reset the cache
  this.reset()

  var now = Date.now()
  // A previous serialized cache has the most recent items first
  for (var l = arr.length - 1; l >= 0; l--) {
    var hit = arr[l]
    var expiresAt = hit.e || 0
    if (expiresAt === 0) {
      // the item was created without expiration in a non aged cache
      this.set(hit.k, hit.v)
    } else {
      var maxAge = expiresAt - now
      // dont add already expired items
      if (maxAge > 0) {
        this.set(hit.k, hit.v, maxAge)
      }
    }
  }
}

LRUCache.prototype.prune = function () {
  var self = this
  priv(this, 'cache').forEach(function (value, key) {
    get(self, key, false)
  })
}

function get (self, key, doUse) {
  var node = priv(self, 'cache').get(key)
  if (node) {
    var hit = node.value
    if (isStale(self, hit)) {
      del(self, node)
      if (!priv(self, 'allowStale')) hit = undefined
    } else {
      if (doUse) {
        priv(self, 'lruList').unshiftNode(node)
      }
    }
    if (hit) hit = hit.value
  }
  return hit
}

function isStale (self, hit) {
  if (!hit || (!hit.maxAge && !priv(self, 'maxAge'))) {
    return false
  }
  var stale = false
  var diff = Date.now() - hit.now
  if (hit.maxAge) {
    stale = diff > hit.maxAge
  } else {
    stale = priv(self, 'maxAge') && (diff > priv(self, 'maxAge'))
  }
  return stale
}

function trim (self) {
  if (priv(self, 'length') > priv(self, 'max')) {
    for (var walker = priv(self, 'lruList').tail;
         priv(self, 'length') > priv(self, 'max') && walker !== null;) {
      // We know that we're about to delete this one, and also
      // what the next least recently used key will be, so just
      // go ahead and set it now.
      var prev = walker.prev
      del(self, walker)
      walker = prev
    }
  }
}

function del (self, node) {
  if (node) {
    var hit = node.value
    if (priv(self, 'dispose')) {
      priv(self, 'dispose').call(this, hit.key, hit.value)
    }
    priv(self, 'length', priv(self, 'length') - hit.length)
    priv(self, 'cache').delete(hit.key)
    priv(self, 'lruList').removeNode(node)
  }
}

// classy, since V8 prefers predictable objects.
function Entry (key, value, length, now, maxAge) {
  this.key = key
  this.value = value
  this.length = length
  this.now = now
  this.maxAge = maxAge || 0
}