/**
 * LRU 缓存算法
 * 前置指针 NEWER
 * 后置指针 OLDER
 * @class LRUCache
 * TODO: LRU 算法错误
 */

const NEWER = Symbol('newer')
const OLDER = Symbol('older')

// 链表元素设置
class Entry {
  constructor (key, value) {
    this.key = key
    this.value = value
    this[NEWER] = undefined
    this[OLDER] = undefined
  }
}

class LRUCache {
  constructor (limit) {
    this.size = 0
    this.limit = limit
    this.newest = this.oldest = undefined
    this.keyMap = new Map()
  }

  // 内部函数，处理 entry 的链表位置
  markEntryAsUsed (entry) {
    // 链表头部元素，无需更新
    if (entry === this.newest) {
      return
    }
    // 处理链表元素前置指向
    if (entry[NEWER]) {
      // 边界条件：尾部元素
      if (entry === this.oldest) {
        this.oldest = entry[NEWER]
      }
      entry[NEWER][OLDER] = entry[OLDER]
    }

    // 处理链表元素后置指向
    if (entry[OLDER]) {
      entry[OLDER][NEWER] = entry[NEWER]
    }
    entry[NEWER] = undefined
    entry[OLDER] = this.newest

    if (this.newest) {
      this.newest[NEWER] = entry
    }

    this.newest = entry
  }

  // 移除最后一个元素
  shift () {
    const entry = this.oldest
    if (entry) {
      if (this.oldest[NEWER]) {
        this.oldest = this.oldest[NEWER]
        this.oldest[OLDER] = undefined
      } else {
        this.oldest = undefined
        this.newest = undefined
      }
    }

    entry[NEWER] = undefined
    entry[OLDER] = undefined

    this.keyMap.delete(entry.key)
    this.size--
  }

  /** 将缓存数据加入到链表中 */
  put (key, value) {
    let entry = this.keyMap.get(key)

    // 处理 key 值已在链表中存在
    if (entry) {
      entry.value = value
      this.markEntryAsUsed(entry)
      return
    }

    this.keyMap.set(key, (entry = new Entry(key, value)))
    if (this.newest) {
      this.newest[NEWER] = entry
      entry[OLDER] = this.newest
    } else {
      this.oldest = entry
    }

    this.newest = entry
    this.size++
    if (this.size > this.limit) {
      this.shift()
    }
  }
  
  /** 获取数据在缓存中是否存在，存在则提到链表头部 */
  get (key) {
    const entry = this.keyMap.get(key)
    if (entry === undefined) return -1
    this.markEntryAsUsed(entry)
    return entry.value
  }
}

module.exports = LRUCache
// export default LRUCache
@@ -62,28 +62,23 @@
 e%0A *
- TODO: LRU %E7%AE%97%E6%B3%95%E9%94%99%E8%AF%AF%0A */%0A
+/%0A%0A // %E5%AE%9A%E4%B9%89%E9%93%BE%E8%A1%A8%E5%89%8D%E5%90%8E%E6%8C%87%E9%92%88
 %0Acon
@@ -142,14 +142,15 @@
 %0A// 
+%E5%88%9D%E5%A7%8B%E5%8C%96
 %E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0
-%E8%AE%BE%E7%BD%AE
 %0Acla
@@ -1540,24 +1540,58 @@
 lue = value%0A
+      // markEntryAsUsed%EF%BC%9A%E9%87%8D%E6%96%B0%E6%8E%92%E5%88%97%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0%0A
       this.m
@@ -1865,16 +1865,40 @@
 .size++%0A
+    // %E8%B6%85%E5%87%BA%E9%93%BE%E8%A1%A8%E9%95%BF%E5%BA%A6%EF%BC%8C%E5%88%99%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E5%B0%BE%E9%83%A8%E5%85%83%E7%B4%A0%0A
     if (

remove todo & add comments