432. All O`one Data Structure

432. 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.

----------------------------
用doubly linked list, value相同的string都放在一个node里面

class AllOne {

    class Node{
        public Node pre;
        public Node next;
        public int val;
        public boolean isDummy;
        public Set<String> set;
        public Node(int val) {
            this.val = val;
            set = new HashSet<>();
            isDummy = false;
        }
    }
    
    private Node min;
    private Node max;
    private Map<String, Integer> map;
    private Map<Integer, Node> iToN;
    
    /** Initialize your data structure here. */
    public AllOne() {
        min = new Node(0);
        max = new Node(0);
        min.next = max;
        max.pre = min;
        min.isDummy = true;
        max.isDummy = true;
        
        map = new HashMap<>();
        iToN = new HashMap<>();
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (!map.containsKey(key)) {
            addOne(key);
        }else {
            int val = map.get(key);
            map.put(key, val + 1);
            
            addToNewNode(key, val + 1);
            removeKey(key, val);
        }
    }
    
    private void addToNewNode(String key, int val) {
        if (iToN.containsKey(val)) {
            iToN.get(val).set.add(key);
        }else {
            Node node = new Node(val);
            node.set.add(key);
            iToN.put(val, node);
            
            Node pre = iToN.get(val - 1);
            insertAfter(pre, node);
        }
    }
    
    private void insertAfter(Node cur, Node node) {
        Node next = cur.next;
        cur.next = node;
        node.pre = cur;
        node.next = next;
        next.pre = node;
    }
    
    private void removeKey(String key, int val) {
        Node node = iToN.get(val);
        node.set.remove(key);
        if (node.set.isEmpty()) {
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            
            iToN.remove(val);
        }
    }
    
    private void addOne(String key) {
        map.put(key, 1);
        
        if (iToN.containsKey(1)) {
            iToN.get(1).set.add(key);
        }else {
            Node node = new Node(1);
            node.set.add(key);
            iToN.put(1, node);

            insertAfter(min, node);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (!map.containsKey(key)) return;
        
        int val = map.get(key);
        if (val == 1) {
            map.remove(key);
            removeKey(key, 1);
        }else {
            if (iToN.containsKey(val - 1)) {
                iToN.get(val - 1).set.add(key);
            }else {
                Node node = new Node(val - 1);
                node.set.add(key);
                iToN.put(val - 1, node);
                Node pre = iToN.get(val).pre;
                
                insertAfter(pre, node);
            }
            
            removeKey(key, val);
            map.put(key, val - 1);
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if (max.pre.isDummy) return "";
        Iterator<String> itr = max.pre.set.iterator();
        return itr.next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if (min.next.isDummy) return "";
        Iterator<String> itr = min.next.set.iterator();
        return itr.next();
    }
}

/**
 * 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();
 */