432. All O`one Data Structure

class Node{
    var keys = Set<String>()
    var pre: Node?
    var next: Node?
    var count: Int
    init(_ count: Int){
        self.count = count
    }
}


class AllOne {
    var keyMap = [String: Int]()
    var nodeMap = [Int: Node]()
    var head : Node
    var tail : Node
    var nodeCount = 0
    /** Initialize your data structure here. */
    init() {
        head = Node(-1)
        tail = Node(-1)
        tail.pre = head
        head.next = tail
    }
    func addNodeAfter(_ preNode: Node, _ node: Node){
         // print(" addd \(node.count)" )
        let nextNode = preNode.next!
        nextNode.pre = node
        node.next = nextNode

        preNode.next = node
        node.pre = preNode
        nodeCount += 1
    }
    func removeNode(_ node: Node){
        // print(" remove \(node.count)" )
        let pre = node.pre!
        let next = node.next!
        pre.next = next
        next.pre = pre
        node.pre = nil
        node.next = nil
        nodeCount -= 1
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    func inc(_ key: String) {
        if let count = keyMap[key]{
            //remove this key from previous Node
            let node = nodeMap[count]!
            node.keys.remove(key)

            //add to new node
            if let node_next = nodeMap[count + 1]{
                node_next.keys.insert(key)
            }else{
                let node_next = Node(count + 1)
                node_next.keys.insert(key)

                addNodeAfter(node, node_next)
                nodeMap[count + 1] = node_next
            }
            keyMap[key] = count + 1


            if node.keys.count == 0 {
                removeNode(node)
                nodeMap[count] = nil
            }

        }else{
            if let node_next = nodeMap[1]{
                node_next.keys.insert(key)
            }else{
                let node_next = Node(1)
                addNodeAfter(head, node_next)
                node_next.keys.insert(key)

                nodeMap[1] = node_next
            }
            keyMap[key] = 1
        }


    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    func dec(_ key: String) {
        if let count = keyMap[key], let node = nodeMap[count]{
            node.keys.remove(key)

            //add to new node
            if count > 1 {
                if let node_next = nodeMap[count - 1]{
                    node_next.keys.insert(key)
                }else{
                    let node_next = Node(count - 1)
                    node_next.keys.insert(key)

                    addNodeAfter(node.pre!, node_next)
                    nodeMap[count - 1] = node_next
                }
                keyMap[key] = count - 1
            }

            if node.keys.count == 0 {
                removeNode(node)
                nodeMap[count] = nil
            }
        }

    }

    /** Returns one of the keys with maximal value. */
    func getMaxKey() -> String {
        if nodeCount == 0 {return ""}
        // print(tail.pre!.count)
        for key in tail.pre!.keys{
            return key
        }
                           return ""
        // return Array(tail.pre!.keys)[0]
    }

    /** Returns one of the keys with Minimal value. */
    func getMinKey() -> String {
        if nodeCount == 0 {return ""}
        // print(head.next!.count)
        for key in head.next!.keys{
            return key
        }
        return ""
    }

    func printLink(){
        var node = head
        while node !== tail{
            print(node.count)
            node = node.next!
        }
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * let obj = AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * let ret_3: String = obj.getMaxKey()
 * let ret_4: String = obj.getMinKey()
 */