package arithmetic;
import java.util.HashMap;
public class FaceTest82 {
//LFU缓存置换算法
//比较词频，词频相同看时间点
//置换之后，词频重新开始累计
public FaceTest82(int k) {
capacity = k;
size = 0;
records = new HashMap<Integer, FaceTest82.Node>();
heads = new HashMap<>();
headList = null;
}
private int capacity;//最大缓存大小
private int size;//目前的节点数
private HashMap<Integer, Node> records;//表示key（Integer）由哪个节点代表
private HashMap<Node,NodeList> heads;//表示节点（Node）在哪个桶（NodeList） 里面
private NodeList headList;//整个结构中位于最左的桶 头桶
//节点的数据结构
public static class Node{
public Integer key;
public Integer value;
public Integer times;//节点操作次数总和
public Node up; //节点之间是双向链表所以有上一个节点
public Node down; //节点之间是双向链表所以有下一个节点
public Node(int k,int v,int t) {
key = k;
value = v;
times = t;
}
}
//桶结构
public static class NodeList {
public Node head;//桶的头结点
public Node tail;//桶的尾结点
public NodeList last;//桶之间是双向链表所以有前一个
public NodeList next;//桶之间是双向链表所以有后一个
public NodeList(Node node) {
head = node;
tail = node;
}
//把一个新节点加入这个桶，新的节点都放在顶端变成新头结点
public void addNodeFromHead(Node newHead) {
newHead.down = head;
head.up = newHead;
head = newHead;
}
//判断这个桶是不是空的桶
public boolean isEmpty() {
return head == null;
}
//删除节点并保证node的上下文环境重新连接
public void deleteNode(Node node) {
if (head == tail) {
head = null;
tail = null;
} else {
//先保证上下节点重新连接
if (node == head) {
head = node.down;//移除顶端，下面的上来
head.up = null;
}else if (node == tail) {
tail = node.up;
tail.down = null;
}else {
node.up.down = node.down;
node.down.up = node.up;
}
}
//移除该节点
node.up = null;
node.down = null;
}
}
// removeNodeList刚刚减少一个节点的桶
// 判断这个桶是不是已经空了
// 如果已经空了，再根据removeNodeList他是不是最左边的桶
// 如果是让removeNodeList他下一个桶做头桶，如果不是删掉后保证左右相连
// 函数返回值表示这个桶减少一个节点后是不是空桶
public boolean modifyHeadList(NodeList removeNodeList) {
if (removeNodeList.isEmpty()) {
if (headList == removeNodeList) {
headList = removeNodeList.next;
if (headList != null) {
headList.last = null;// 新头桶左边指向空
}
} else {
removeNodeList.last.next = removeNodeList.next;
if (removeNodeList.next != null) {
removeNodeList.next.last = removeNodeList.last;
}
}
return true;
}
return false;
}
// 放入一个节点，
// 首先查看是否一个桶都没有,先创建
// 找桶放值，找不到创建
// 创建保证左右桶相连
// 找到桶，值满要删tail，遵循FIFO原则
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (records.containsKey(key)) {// 修改
Node node = records.get(key);
node.value = value;
node.times++;// 修改词频
NodeList curNodeList = heads.get(node);
move(node, curNodeList);
} else {
if (size == capacity) {// 桶满的情况
Node node = headList.tail;
// 删除节点并对桶判空
headList.deleteNode(node);
modifyHeadList(headList);
// 总map要删，heads标记桶的map也要删
records.remove(node.key);
heads.remove(node);
size--;
}
// 放节点
Node node = new Node(key, value, 1);
if (headList == null) {// 没有桶，新建一个放节点就行
headList = new NodeList(node);
} else {// 寻找旧桶
if (headList.head.times.equals(node.times)) {
headList.addNodeFromHead(node);// 替换旧头部
} else {// 找不到旧桶新建一个，左右连接一下，比如词频1的是空的，原来的都到别的桶上去了
NodeList newList = new NodeList(node);
newList.next = headList;
headList.last = newList;
headList = newList;// 新建并作为头桶
}
}
// 总map和桶标记map都放入节点，容量++
records.put(key, node);
heads.put(node, headList);
size++;
}
}
public int get(int key) {
if (!records.containsKey(key)) {
return -1;
}
Node node = records.get(key);
node.times++;
NodeList curNodeList = heads.get(node);
move(node, curNodeList);
return node.value;
}
// 词频变化，换桶
// 把这个节点从原来的同移除
// 过程要保证任然是双向链表
private void move(Node node, NodeList oldNodeList) {
oldNodeList.deleteNode(node);
// oldNodeList原来的可能拿走这个节点后是个空桶
// oldNodeList可能是中间的桶，所以还要保证空桶后要连接前后连个同
// preList表示+1的桶的前一个桶是谁
// 没有节点就用前一个桶
NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;
// nextList表示次数+1的桶的后一个桶是谁
NodeList nextList = oldNodeList.next;
if (nextList == null) {// 后面没有桶
NodeList newList = new NodeList(node);
if (preList != null) {
preList.next = newList;
}
newList.last = preList;
if (headList == null) {
headList = newList;
}
heads.put(node, newList);
} else { // +1后有桶
if (nextList.head.times.equals(node.times)) {// 找到同词频
nextList.addNodeFromHead(node);
heads.put(node, nextList);
} else {// 找不到同词频，就新建
NodeList newList = new NodeList(node);
if (preList != null) {
preList.next = newList;
}
newList.last = preList;
newList.next = nextList;
nextList.last = newList;
if (headList == nextList) {
headList = newList;
}
heads.put(node, newList);//重新标记桶
}
}
}
}