All O`one Data Structure

Implement a data structure supporting the following operations:

1. Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.

2. Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.

3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".

4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

有bug

class AllOne {
    
    private Map<String,Node> map;
    private DoubleLinkedList ddl;
    /** Initialize your data structure here. */
    public AllOne() {
        map = new HashMap<>();
        ddl = new DoubleLinkedList();
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        System.out.println("inc");
        
        if(key == null || key.length() == 0)
            return;
        Node node = null;
        if(!map.containsKey(key)){
            //check ddl 中是否包含key
            if(ddl.head.next.val == 1){
                node = ddl.head.next;
                node.addString(key);
            }else{
                node = new Node(1);
                ddl.addAfterHead(node);
                node.addString(key);
            }
            map.put(key,node);
        }
        
        else{
            node = map.get(key);
            map.put(key,ddl.update(node,key));
        }
        
        //ddl.dump();
        ddl.printNode();
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        System.out.println("dec");
        if(key == null || key.length() == 0)
            return;
        if(map.containsKey(key)){
            Node node = map.get(key);
            int val = node.val;
            Node newNode = ddl.decUpdate(node,key);
            
            if(val == 1){
                map.remove(key);
            }
            
            else{
                map.put(key,newNode);
            }
        }
        
        //ddl.dump();
        ddl.printNode();
        
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return ddl.getMax();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey(){
        return ddl.getMin();
    }
    
    
    
    class DoubleLinkedList{
        private Node head;
        private Node tail;
        
        public DoubleLinkedList(){
            this.head = new Node(-1);
            this.tail = new Node(-1);
            
            head.next = tail;
            head.prev = null;
            tail.next = null;
            tail.prev = head;
        }
        
        public void dump(){
            Node tmp = head.next;
            
            while(tmp != tail && tmp != null){
                System.out.print(tmp.val+" : ");
                
                for(String s : tmp.getList()){
                    System.out.print(s + "  ");
                }
                
                System.out.println();
                
                tmp = tmp.next;
            }
        }
        
        public void printNode(){
            Node tmp = head;
            
            while(tmp != null){
                System.out.print(tmp.val+" -> ");
                tmp = tmp.next;
            }
        }
        public Node decUpdate(Node node, String s){
            int curVal = node.val;
            
            if(curVal == 1){
                node.removeString(s);
                if(node.isEmpty()){
                    
                    remove(node);
                    return head;
                }
                return node;
                
            }
            else{
                if(node.prev.val == curVal - 1){
                    Node prevNode = node.prev;
                    
                    prevNode.addString(s);
                    node.removeString(s);
                    if(node.isEmpty()){
                        System.out.println("this node is empty, ready to remove");
                        remove(node);
                    }
                    
                    return prevNode;
                }
                    Node newNode = new Node(curVal - 1);
                    
                    newNode.next = node;
                    newNode.prev = node.prev;
                    
                    node.prev.next = newNode;
                    node.prev = newNode;
                    newNode.addString(s);
                    node.removeString(s);
                    if(node.isEmpty()){
                        remove(node);
                    }
                
                
                return newNode;
            }
        }
        
        
        public void addAfterHead(Node node){
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            
            
        }
        
        public void remove(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
        }
        
        public Node update(Node node,String s){
            int curVal = node.val;

            if(node.next.val == curVal + 1){
                node.removeString(s);
                node.next.addString(s);
                if(node.isEmpty()){
                    remove(node);
                    return null;
                }
                
            }else{
                Node newNode = new Node(curVal+1);
                
                newNode.addString(s);
                node.removeString(s);
                
                newNode.next = node.next;
                newNode.prev = node;
                node.next.prev = newNode;
                node.next = newNode;
                if(node.isEmpty()){
                    remove(node);
                    return newNode;
                }
                
            }
            
            return node.next;
        }
        
        
        public String getMax(){
            if(tail.prev == head){
                return "";
            }
            
            List<String> list = tail.prev.getList();
            
            
            int size = tail.prev.listSize();
            
            
            return list.isEmpty() ? "": list.get(size -1);
        }
        
        public String getMin(){
            if(head.next == tail){
                return "";
            }
            
            List<String> list = head.next.getList();
            int size = head.next.listSize();
            return list.isEmpty() ? "": list.get(size -1);
        }
        
    }
    
    class Node{
        public int val;
        // store keys with same value
        public List<String> list;
        //store keys and it's index mapping
        public Map<String, Integer> map;
            
        //connect next and previous node 
        public Node next;
        public Node prev;
        
        public Node(int val){
            this.val = val;
            list = new ArrayList<>();
            map = new HashMap<>();
            next = null;
            prev = null;
        }
        
        public void addString(String s){
            list.add(s);
            map.put(s,list.size()-1);
        }
        
        public boolean removeString(String s){
            if(!map.containsKey(s)){
                return false;
            }
            
            int indexOfS = map.get(s);
            
            if(indexOfS != list.size()-1){
                
                String last = list.get(list.size()-1);
                
                list.set(indexOfS,last);
                map.put(last,indexOfS);
            }
            
            map.remove(s);
            list.remove(list.size()-1);
            
            return true;
        } 
        
        public boolean isEmpty(){
            return list.isEmpty();
        }
        
        public int listSize(){
            return list.size();
        }
        
        public List<String> getList(){
            return list;
        }
        
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */