# 432 - All O`one Data Structure

解法一 - Hash Table + doubly linked list

這題是擴展眼界題，邊聽影片邊做，可以看：https://www.youtube.com/watch?v=wYqLisoH80w

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {}

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        auto it = m_.find(key);

        if(it == m_.end()) {
            if(l_.empty() or l_.front().value != 1) {
                l_.push_front({1, {key}});
            }
            else {
                l_.front().keys.insert(key);
            }

            m_[key] = l_.begin();
            return;
        }

        auto lit = it->second;
        auto nit = next(lit);

        if(nit->value != lit->value + 1 or nit == l_.end()) {
            nit = l_.insert(nit, {lit->value + 1, {}});    
        }
        nit->keys.insert(key);
        m_[key] = nit;

        lit->keys.erase(key);
        if(lit->keys.empty()) {
            l_.erase(lit);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        auto it = m_.find(key);

        if(it == m_.end()) {
            return;
        }

        auto lit = it->second;

        if(lit->value > 1) {
            auto pit = prev(lit);

            if(lit == l_.begin() or pit->value != lit->value - 1) {
                pit = l_.insert(lit, {lit->value - 1, {}});
            }
            pit->keys.insert(key);
            m_[key] = pit;
        }
        else{
            m_.erase(key);
        }

        lit->keys.erase(key);
        if(lit->keys.empty()) {
            l_.erase(lit);
        }
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return l_.empty() ? "" : *l_.back().keys.cbegin();
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return l_.empty() ? "" : *l_.front().keys.cbegin();
    }

private:
    struct Node {
        int value;
        unordered_set<string> keys;
    };

    list<Node> l_;
    unordered_map<string, list<Node>::iterator> m_;
};

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