23. 文件缓存系统

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
class fileCacheSys() {
    constructor(maxCacheSize) {
        this.maxCacheSize = maxCacheSize;
        this.currentCacheSize = 0;
        this.cache = {};
        this.minHeap= [];
        this.time = 0;
    }
    compare(a, b) {
        if (a.accessCount === b.accessCount) {
            return a.lastAccessTime - b.lastAccessTime;
        }
        return a.accessCount - b.accessCount;
    }
    minHeapify(index) {
        let smallest = index;
        const leftChild = 2*index+1;
        const rightChild = 2*index+2;
        if(leftChild < this.minHeap.length && this.compare(this.minHeap[leftChild], this.minHeap[smallest]) < 0) {
            smallest = leftChild;
        }
        if (rightChild < this.minHeap.length && this.compare(this.minHeap[rightChild], this.minHeap[smallest]) < 0) {
            smallest = rightChild;
        }
        if (smallest !== index) {
            [this.minHeap[smallest], this.minHeap[index]] = [this.minHeap[index], this.minHeap[smallest]]
            this.minHeapify(smallest);
        }
    }
    minHeapInsert(file) {
        this.minHeap.push(file);
        let index = this.minHeap.length - 1;
        let parentIndex = Math.floor((index - 1)/2);
        while(index >0 && this.compare(this.minHeap[index], this.minHeap[parentIndex]) < 0) {
            [this.minHeap[parentIndex], this.minHeap[index]] = [this.minHeap[index], this.minHeap[parentIndex]]
            index = parentIndex;
            parentIndex = Math.floor((index - 1)/2);
        }
    }
    minHeapPop() {
        if (this.minHeap.length === 0) return null;
        const minItem = this.minHeap[0];
        this.minHeap[0] = this.minHeap[this.minHeap.length - 1];
        this.minHeap.pop();
        this.minHeapify(0);
        return minItem;
    }
    minHeapRemove(file) {
        const index = this.minHeap.findIndex(f => f.name === file.name)
        if (index === -1) return;
        this.minHeap[index] = this.minHeap[this.minHeap.length-1];
        this.minHeap.pop();
        this.minHeapify(index);
    }
    put(fileName, fileSize) {
        if (fileSize > this.maxCacheSize) return;
        const currentTime = Date.now();
        if (this.cache[fileName]) {
            this.get(fileName);
            return;
        }
        while(this.currentCacheSize + fileSize > this.maxCacheSiz) {
            const toRemove = this.minHeapPop();
            if (toRemove) {
                delete this.cache[toRemove.name];
                this.currentCacheSize -= toRemove.size;
            }
        }
        const file = {name: fileName, size: fileSize, accessCount: 1, lastAccessTime: currentTime};
        this.cache[fileName] = file;
        this.minHeapInsert(file);
        this.currentCacheSize += fileSize;
    }
    get(fileName) {
        if (!this.cache[fileName]) return;
        const file = this.cache[fileName];
        this.minHeapRemove(file);
        file.accessCount++;
        file.lastAccessTime = Date.now();
        this.minHeapInsert(file);
    }
    getCurrentCache() {
        const files = Object.keys(this.cache);
        files.sort();
        return files;
    }
}

const lines = [];
rl.on('line', (line) => {
    lines.push(line);
});
rl.on('close', () => {
    const maxCacheSize = parseInt(lines[0]);
    const opCount = parseInt(lines[1]);
    const cacheSystem = new FileCacheSystem(maxCacheSize);

    for(let i=2; i<opCount+2; i++) {
        const input= lines[i].split(' ');
        const op = input[0];
        const fileName = input[1];

        if (op === 'put') {
            const fileSize = parseInt(input[2]);
            cacheSystem.put(fileName, fileSize);
        } else if (op === 'get') {
            cacheSystem.get(fileName);
        }
    }
    const currentCache = cacheSystem.getCurrentCache();
    if (currentCache.length === 0) {
        console.log('NONE');
    } else {
        console.log(currentCache.join(','));
    }
})