Use of LRU algorithm in Vue built-in component keep-alive

export default {
  name: "keep-alive",
  // Abstract component properties, which will be ignored when the component instance establishes a parent-child relationship, which occurs during the initLifecycle process abstract: true, 
  props: {
    // Cache components include: patternTypes, 
    // Exclude components from being cached: patternTypes,
    // Specify cache size max: [String, Number] 
  },
  created() {
    // Initialize the cache object used to store cache this.cache = Object.create(null);
    // Initialize the keys array used to store VNode key values ​​this.keys = []; 
  },
  destroyed() {
    for (const key in this.cache) {
      // Delete all caches pruneCacheEntry(this.cache, key, this.keys);
    }
  },
  mounted() {
    // Listen for changes in cache (include)/exclude components // Re-adjust the cache when changes occur
    // pruneCache: traverse the cache, if the cached node name does not match the passed in rule, remove the node from the cache this.$watch("include", val => {
      pruneCache(this, name => matches(val, name));
    });
    this.$watch("exclude", val => {
      pruneCache(this, name => !matches(val, name));
    });
  },
  render() {
    // Get the vnode of the first child element
    const slot = this.$slots.default;
    const vnode: VNode = getFirstComponentChild(slot);
    const componentOptions: ?VNodeComponentOptions =
      vnode && vnode.componentOptions;
    if (componentOptions) {
      // If name is not in include or in exclude, return vnode directly, otherwise proceed to the next step // check pattern
      const name: ?string = getComponentName(componentOptions);
      const { include, exclude } = this;
      if (
        // not included
        (include && (!name || !matches(include, name))) ||
        // excluded
        (exclude && name && matches(exclude, name))
      ) {
        return vnode;
      }
      
      const { cache, keys } = this;
      // Get the key, first get the name field of the component, otherwise it is the tag of the component
      const key: ?string =
        vnode.key == null
          ? // same constructor may get registered as different local components
            // so cid alone is not enough (#3269)
            componentOptions.Ctor.cid +
            (componentOptions.tag ? `::${componentOptions.tag}` : "")
          : vnode.key;
        
      // --------------------------------------------------
      // The following is the LRU algorithm,
      // If it is in the cache, adjust it.
      // If not, put it in (if the length exceeds max, eliminate those that have not been accessed recently)
      // --------------------------------------------------
      // If the cache is hit, get the component instance of vnode from the cache and adjust the order of the keys to the end of the keys array if (cache[key]) {
        vnode.componentInstance = cache[key].componentInstance;
        // make current key freshest
        remove(keys, key);
        keys.push(key);
      }
      // If the cache is not hit, put the vnode into the cache else {
        cache[key] = vnode;
        keys.push(key);
        // prune oldest entry
        // If max is configured and the cache length exceeds this.max, delete the first one from the cache if (this.max && keys.length > parseInt(this.max)) {
          pruneCacheEntry(cache, keys[0], keys, this._vnode);
        }
      }
      
      // keepAlive flag vnode.data.keepAlive = true;
    }
    return vnode || (slot && slot[0]);
  }
};

// Remove key cache function pruneCacheEntry (
  cache: VNodeCache,
  key: string,
  keys: Array<string>,
  current?: VNode
) {
  const cached = cache[key]
  if (cached && (!current || cached.tag !== current.tag)) {
    cached.componentInstance.$destroy()
  }
  cache[key] = null
  remove(keys, key)
}

// remove method (shared/util.js)
/**
 * Remove an item from an array.
 */
export function remove (arr: Array<any>, item: any): Array<any> | void {
  if (arr.length) {
    const index = arr.indexOf(item)
    if (index > -1) {
      return arr.splice(index, 1)
    }
  }
}

class LRU {
  constructor(size) {
    this.cache = new Map()
    this.size = size
  }
  put (key, val) {
    //Existsif (this.cache.has(key)) {
      //delete this.cache.delete(key)
    } else {
      // Does not exist, is the capacity full if (this.size === this.cache.size) {
        //Delete the last one this.cache.delete(this.cache.keys().next().value) //Get the element at the end of the queue}
    }
    //Insert at the head of the queue this.cache.set(key, val)
  }
  get (key) {
    let val = this.cache.get(key)
    if (!val) {
      return -1
    }
    //After access, it needs to be put at the head of the queue this.put(key, val)
    return val
  }
}

//Define the node class class Node {
    constructor(pre, next, value, key){
        this.pre = pre;
        this.next = next;
        this.value = value;
        this.key = key;
    }
}

//Define a bidirectional linked list class DoubleList {
    constructor(head, tail){
        this.head = head;
        this.tail = tail;
    }
}


class LRUCache {
    //Constructor, pass in cache capacity constructor(max){
        this.max = max;
        this.map = new Map();
        let node = new Node(null, null, null, null);
        this.doubleList = new DoubleList(node, node);
    }
    
    /**
     * Get the cache value * If it does not exist, return -1; if it does exist, return the corresponding value and move this node to the tail * @param {*} key key value */
    get(key){
        let node = this.map.get(key)
        if(!node){
            return -1;
        }else{
            this.moveNode2Tail(key, node);
            return node.value;
        }
    }

    /**
     * Insert cache * 1. If the corresponding key value does not exist, add it to the tail * 2. If the corresponding key value exists, update the value corresponding to this key value and mention it to the tail * 3. If the capacity is exceeded, remove the header data * @param {*} key key value * @param {*} value value
     */
    put(key, value) {
        let node = this.map.get(key);
        if(node){
            if(!node.next){
                node.value = value;
                return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        let newNode = new Node(null, null, value, key);
        newNode.pre = this.doubleList.tail;
        this.doubleList.tail.next = newNode;
        this.doubleList.tail = newNode;
        this.map.set(key, newNode);
        if(this.map.size > this.max){
            this.map.delete(this.doubleList.head.next.key);
            this.doubleList.head.next = this.doubleList.head.next.next;
            this.doubleList.head.next.pre = this.doubleList.head;          
        }
    }
    
    //Move the node to the tail moveNode2Tail(key,node){   
        if(!node.next){
            return;
        }
        //Delete node node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.delete(key)
        //Add a new tail node let newNode = new Node(null, null, node.value, key);
        newNode.pre = this.doubleList.tail;
        this.doubleList.tail.next = newNode;
        this.doubleList.tail = newNode;
        this.map.set(key, newNode);
    }
}