Class AllOne

AllOoneDataStructure.java:13–100

    }
}
class AllOne {
    HashMap<String, Node> map;
    Node head;
    Node tail;
    public AllOne() {
        head = new Node(0);
        tail = new Node(0);
        map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
    }
    
    public void inc(String key) {
        Node cur = head;
        int newFreq = 1;
        if(map.containsKey(key)){
            cur = map.get(key);
            newFreq = cur.freq + 1;
            cur.keys.remove(key);
        }
        if(cur.next.freq == newFreq){
            cur.next.keys.add(key);
        }else{ // insert a node with newFreq
            Node node = new Node(newFreq);
            node.keys.add(key);
            Node nextNode = cur.next;
            node.next = nextNode;
            nextNode.prev = node;
            cur.next = node;
            node.prev = cur;
        }
        map.put(key, cur.next);
        if(cur.keys.size()==0 && cur!=head){
            removeNode(cur);
        }
    }
    
    public void dec(String key) {
        Node cur = map.get(key);
        int newFreq = cur.freq - 1;
        cur.keys.remove(key);
        if(newFreq == 0){
            if(cur.keys.size()==0){
                removeNode(cur);
            }
            map.remove(key);
            return;
        }
    
        if(cur.prev.freq == newFreq){
            cur.prev.keys.add(key);
        }else{ // insert a node with newFreq
            Node node = new Node(newFreq);
            node.keys.add(key);
            Node prevNode = cur.prev;
            node.prev = prevNode;
            prevNode.next = node;
            node.next = cur;