class LRUCacheNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}


class LRUCache {
  constructor(capacity = 500) {
    this.capacity = capacity;
    this.cacheMap = new Map(); // 使用哈希表存儲(chǔ)鍵值對
    this.doubleLinkedList = new DoublyLinkedList(); // 雙向鏈表維護(hù)緩存順序
  }

  get(key) {
    if (this.cacheMap.has(key)) {
      const node = this.cacheMap.get(key);
      this.doubleLinkedList.moveToTail(node); // 將節(jié)點(diǎn)移動(dòng)到鏈表尾部，表示最新訪問
      return node.value;
    }
    return -1; // 或者返回null，表示key不存在于緩存中
  }

  put(key, value) {
    if (this.cacheMap.has(key)) {
      const node = this.cacheMap.get(key);
      node.value = value;
      this.doubleLinkedList.moveToTail(node);
    } else {
      if (this.cacheMap.size >= this.capacity) {
        const headNode = this.doubleLinkedList.deleteHead();
        this.cacheMap.delete(headNode.key); // 移除最舊的緩存項(xiàng)
      }
      const newNode = new Node(key, value);
      this.cacheMap.set(key, newNode);
      this.doubleLinkedList.addToTail(newNode);
    }
  }
}

// 雙向鏈表類和節(jié)點(diǎn)類的實(shí)現(xiàn)略（根據(jù)實(shí)際需求實(shí)現(xiàn)）
class Node {
  constructor(key, value) {
    this.key = key; // 節(jié)點(diǎn)鍵值
    this.value = value; // 節(jié)點(diǎn)數(shù)據(jù)值
    this.prev = null; // 前驅(qū)節(jié)點(diǎn)引用
    this.next = null; // 后繼節(jié)點(diǎn)引用
  }
}
class DoublyLinkedList {
  constructor() {
    this.head = null; // 頭節(jié)點(diǎn)
    this.tail = null; // 尾節(jié)點(diǎn)
  }

  /**
   * 添加節(jié)點(diǎn)到鏈表尾部
   * @param {Node} newNode 新節(jié)點(diǎn)
   */
  addToTail(newNode) {
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  /**
   * 移除頭節(jié)點(diǎn)并返回
   * @returns {Node | null} 刪除的頭節(jié)點(diǎn)或null（如果鏈表為空）
   */
  deleteHead() {
    if (!this.head) return null;

    const deletedNode = this.head;
    this.head = this.head.next;

    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null;
    }

    return deletedNode;
  }

  /**
   * 將指定節(jié)點(diǎn)移動(dòng)到鏈表尾部
   * @param {Node} node 需要移動(dòng)的節(jié)點(diǎn)
   */
  moveToTail(node) {
    if (node === this.tail) return; // 如果已經(jīng)是尾節(jié)點(diǎn)，則無需移動(dòng)

    // 斷開當(dāng)前節(jié)點(diǎn)與前后節(jié)點(diǎn)的連接
    node.prev.next = node.next;
    if (node.next) node.next.prev = node.prev;

    // 將節(jié)點(diǎn)添加至鏈表尾部
    this.addToTail(node);
  }
  
  // 其他可能的方法，如查找節(jié)點(diǎn)、在指定位置插入節(jié)點(diǎn)等...
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (this.cache.has(key)) {
            const value = this.cache.get(key);
            // 刪除舊數(shù)據(jù)再重新插入，以更新最近訪問的順序
            this.cache.delete(key);
            this.cache.set(key, value);
            return value;
        }
        return null;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // 超出容量時(shí)刪除最久未訪問的數(shù)據(jù)（即最近使用頻率最低的數(shù)據(jù)）
            const keys = this.cache.keys();
            this.cache.delete(keys.next().value);
        }
        this.cache.set(key, value);
    }

    displayHistory() {
        console.log("Browser History:");
        for (let [key, value] of this.cache) {
            console.log(key + " -> " + value);
        }
    }
}

// 使用示例
const historyCache = new LRUCache(5); // 設(shè)置緩存容量為5

historyCache.put("Page 1", "www.page1.com");
historyCache.put("Page 2", "www.page2.com");
historyCache.put("Page 3", "www.page3.com");
historyCache.get("Page 1");

// 輸出瀏覽歷史記錄
historyCache.displayHistory();