All O`one Data Structures

class AllOne {
    struct Bucket { int cnt; unordered_set<string> keys; };
    list<Bucket> buckets; // ascending by cnt; head = min, tail = max
    unordered_map<string, list<Bucket>::iterator> mp;
public:
    void inc(string key) {
        if (!mp.count(key)) {
            if (buckets.empty() || buckets.front().cnt != 1)
                buckets.push_front({1, {}});
            buckets.front().keys.insert(key);
            mp[key] = buckets.begin();
        } else {
            auto it = mp[key];
            auto nxt = next(it);
            if (nxt == buckets.end() || nxt->cnt != it->cnt + 1)
                nxt = buckets.insert(nxt, {it->cnt + 1, {}});
            nxt->keys.insert(key);
            mp[key] = nxt;
            it->keys.erase(key);
            if (it->keys.empty()) buckets.erase(it);
        }
    }
    void dec(string key) {
        auto it = mp[key];
        if (it->cnt == 1) {
            mp.erase(key);
        } else {
            auto pr = (it == buckets.begin()) ? buckets.end() : prev(it);
            if (pr == buckets.end() || pr->cnt != it->cnt - 1)
                pr = buckets.insert(it, {it->cnt - 1, {}});
            pr->keys.insert(key);
            mp[key] = pr;
        }
        it->keys.erase(key);
        if (it->keys.empty()) buckets.erase(it);
    }
    string getMaxKey() { return buckets.empty() ? "" : *buckets.back().keys.begin(); }
    string getMinKey() { return buckets.empty() ? "" : *buckets.front().keys.begin(); }
};

type bucket struct {
    cnt  int
    keys map[string]bool
    prev *bucket
    next *bucket
}

type AllOne struct {
    head *bucket // sentinel; head.next = min bucket
    tail *bucket // sentinel; tail.prev = max bucket
    mp   map[string]*bucket
}

func Constructor() AllOne {
    h, t := &bucket{}, &bucket{}
    h.next = t
    t.prev = h
    return AllOne{head: h, tail: t, mp: make(map[string]*bucket)}
}

func (a *AllOne) insertAfter(prev *bucket, cnt int) *bucket {
    b := &bucket{cnt: cnt, keys: make(map[string]bool), prev: prev, next: prev.next}
    prev.next.prev = b
    prev.next = b
    return b
}

func (a *AllOne) removeBucket(b *bucket) {
    b.prev.next = b.next
    b.next.prev = b.prev
}

func (a *AllOne) Inc(key string) {
    if b, ok := a.mp[key]; !ok {
        first := a.head.next
        if first == a.tail || first.cnt != 1 {
            first = a.insertAfter(a.head, 1)
        }
        first.keys[key] = true
        a.mp[key] = first
    } else {
        nxt := b.next
        if nxt == a.tail || nxt.cnt != b.cnt+1 {
            nxt = a.insertAfter(b, b.cnt+1)
        }
        nxt.keys[key] = true
        a.mp[key] = nxt
        delete(b.keys, key)
        if len(b.keys) == 0 {
            a.removeBucket(b)
        }
    }
}

func (a *AllOne) Dec(key string) {
    b := a.mp[key]
    if b.cnt == 1 {
        delete(a.mp, key)
    } else {
        pr := b.prev
        if pr == a.head || pr.cnt != b.cnt-1 {
            pr = a.insertAfter(b.prev, b.cnt-1)
        }
        pr.keys[key] = true
        a.mp[key] = pr
    }
    delete(b.keys, key)
    if len(b.keys) == 0 {
        a.removeBucket(b)
    }
}

func (a *AllOne) GetMaxKey() string {
    if a.tail.prev == a.head {
        return ""
    }
    for k := range a.tail.prev.keys {
        return k
    }
    return ""
}

func (a *AllOne) GetMinKey() string {
    if a.head.next == a.tail {
        return ""
    }
    for k := range a.head.next.keys {
        return k
    }
    return ""
}

class _Bucket:
    __slots__ = ('cnt', 'keys', 'prev', 'next')

    def __init__(self, cnt: int = 0):
        self.cnt = cnt
        self.keys: set[str] = set()
        self.prev: '_Bucket | None' = None
        self.next: '_Bucket | None' = None

class AllOne:
    def __init__(self):
        self.head = _Bucket()  # sentinel; head.next = min
        self.tail = _Bucket()  # sentinel; tail.prev = max
        self.head.next = self.tail
        self.tail.prev = self.head
        self.mp: dict[str, _Bucket] = {}

    def _insert_after(self, prev: _Bucket, cnt: int) -> _Bucket:
        b = _Bucket(cnt)
        b.prev = prev
        b.next = prev.next
        prev.next.prev = b
        prev.next = b
        return b

    def _remove(self, b: _Bucket) -> None:
        b.prev.next = b.next
        b.next.prev = b.prev

    def inc(self, key: str) -> None:
        if key not in self.mp:
            first = self.head.next
            if first is self.tail or first.cnt != 1:
                first = self._insert_after(self.head, 1)
            first.keys.add(key)
            self.mp[key] = first
        else:
            b = self.mp[key]
            nxt = b.next
            if nxt is self.tail or nxt.cnt != b.cnt + 1:
                nxt = self._insert_after(b, b.cnt + 1)
            nxt.keys.add(key)
            self.mp[key] = nxt
            b.keys.discard(key)
            if not b.keys:
                self._remove(b)

    def dec(self, key: str) -> None:
        b = self.mp[key]
        if b.cnt == 1:
            del self.mp[key]
        else:
            pr = b.prev
            if pr is self.head or pr.cnt != b.cnt - 1:
                pr = self._insert_after(b.prev, b.cnt - 1)
            pr.keys.add(key)
            self.mp[key] = pr
        b.keys.discard(key)
        if not b.keys:
            self._remove(b)

    def getMaxKey(self) -> str:
        if self.tail.prev is self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next is self.tail:
            return ""
        return next(iter(self.head.next.keys))

class _Bucket {
    constructor(cnt = 0) {
        this.cnt = cnt;
        this.keys = new Set();
        this.prev = null;
        this.next = null;
    }
}

var AllOne = function() {
    this.head = new _Bucket();
    this.tail = new _Bucket();
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.mp = new Map();
};

AllOne.prototype._insertAfter = function(prev, cnt) {
    const b = new _Bucket(cnt);
    b.prev = prev;
    b.next = prev.next;
    prev.next.prev = b;
    prev.next = b;
    return b;
};

AllOne.prototype._remove = function(b) {
    b.prev.next = b.next;
    b.next.prev = b.prev;
};

AllOne.prototype.inc = function(key) {
    if (!this.mp.has(key)) {
        let first = this.head.next;
        if (first === this.tail || first.cnt !== 1) {
            first = this._insertAfter(this.head, 1);
        }
        first.keys.add(key);
        this.mp.set(key, first);
    } else {
        const b = this.mp.get(key);
        let nxt = b.next;
        if (nxt === this.tail || nxt.cnt !== b.cnt + 1) {
            nxt = this._insertAfter(b, b.cnt + 1);
        }
        nxt.keys.add(key);
        this.mp.set(key, nxt);
        b.keys.delete(key);
        if (b.keys.size === 0) this._remove(b);
    }
};

AllOne.prototype.dec = function(key) {
    const b = this.mp.get(key);
    if (b.cnt === 1) {
        this.mp.delete(key);
    } else {
        let pr = b.prev;
        if (pr === this.head || pr.cnt !== b.cnt - 1) {
            pr = this._insertAfter(b.prev, b.cnt - 1);
        }
        pr.keys.add(key);
        this.mp.set(key, pr);
    }
    b.keys.delete(key);
    if (b.keys.size === 0) this._remove(b);
};

AllOne.prototype.getMaxKey = function() {
    if (this.tail.prev === this.head) return "";
    return this.tail.prev.keys.values().next().value;
};

AllOne.prototype.getMinKey = function() {
    if (this.head.next === this.tail) return "";
    return this.head.next.keys.values().next().value;
};

class AllOne {
    private static class Bucket {
        int cnt;
        Set<String> keys = new HashSet<>();
        Bucket prev, next;
        Bucket(int cnt) { this.cnt = cnt; }
    }

    private final Bucket head = new Bucket(0); // sentinel; head.next = min
    private final Bucket tail = new Bucket(0); // sentinel; tail.prev = max
    private final Map<String, Bucket> mp = new HashMap<>();

    public AllOne() {
        head.next = tail;
        tail.prev = head;
    }

    private Bucket insertAfter(Bucket prev, int cnt) {
        Bucket b = new Bucket(cnt);
        b.prev = prev;
        b.next = prev.next;
        prev.next.prev = b;
        prev.next = b;
        return b;
    }

    private void removeBucket(Bucket b) {
        b.prev.next = b.next;
        b.next.prev = b.prev;
    }

    public void inc(String key) {
        Bucket b = mp.get(key);
        if (b == null) {
            Bucket first = head.next;
            if (first == tail || first.cnt != 1) {
                first = insertAfter(head, 1);
            }
            first.keys.add(key);
            mp.put(key, first);
        } else {
            Bucket nxt = b.next;
            if (nxt == tail || nxt.cnt != b.cnt + 1) {
                nxt = insertAfter(b, b.cnt + 1);
            }
            nxt.keys.add(key);
            mp.put(key, nxt);
            b.keys.remove(key);
            if (b.keys.isEmpty()) removeBucket(b);
        }
    }

    public void dec(String key) {
        Bucket b = mp.get(key);
        if (b.cnt == 1) {
            mp.remove(key);
        } else {
            Bucket pr = b.prev;
            if (pr == head || pr.cnt != b.cnt - 1) {
                pr = insertAfter(b.prev, b.cnt - 1);
            }
            pr.keys.add(key);
            mp.put(key, pr);
        }
        b.keys.remove(key);
        if (b.keys.isEmpty()) removeBucket(b);
    }

    public String getMaxKey() {
        if (tail.prev == head) return "";
        return tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        if (head.next == tail) return "";
        return head.next.keys.iterator().next();
    }
}

class _Bucket {
    cnt: number;
    keys: Set<string>;
    prev: _Bucket | null;
    next: _Bucket | null;
    constructor(cnt: number = 0) {
        this.cnt = cnt;
        this.keys = new Set<string>();
        this.prev = null;
        this.next = null;
    }
}

class AllOne {
    private head: _Bucket;
    private tail: _Bucket;
    private mp: Map<string, _Bucket>;

    constructor() {
        this.head = new _Bucket();
        this.tail = new _Bucket();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.mp = new Map();
    }

    private insertAfter(prev: _Bucket, cnt: number): _Bucket {
        const b = new _Bucket(cnt);
        b.prev = prev;
        b.next = prev.next;
        prev.next!.prev = b;
        prev.next = b;
        return b;
    }

    private removeBucket(b: _Bucket): void {
        b.prev!.next = b.next;
        b.next!.prev = b.prev;
    }

    inc(key: string): void {
        if (!this.mp.has(key)) {
            let first = this.head.next!;
            if (first === this.tail || first.cnt !== 1) {
                first = this.insertAfter(this.head, 1);
            }
            first.keys.add(key);
            this.mp.set(key, first);
        } else {
            const b = this.mp.get(key)!;
            let nxt = b.next!;
            if (nxt === this.tail || nxt.cnt !== b.cnt + 1) {
                nxt = this.insertAfter(b, b.cnt + 1);
            }
            nxt.keys.add(key);
            this.mp.set(key, nxt);
            b.keys.delete(key);
            if (b.keys.size === 0) this.removeBucket(b);
        }
    }

    dec(key: string): void {
        const b = this.mp.get(key)!;
        if (b.cnt === 1) {
            this.mp.delete(key);
        } else {
            let pr = b.prev!;
            if (pr === this.head || pr.cnt !== b.cnt - 1) {
                pr = this.insertAfter(b.prev!, b.cnt - 1);
            }
            pr.keys.add(key);
            this.mp.set(key, pr);
        }
        b.keys.delete(key);
        if (b.keys.size === 0) this.removeBucket(b);
    }

    getMaxKey(): string {
        if (this.tail.prev === this.head) return "";
        return this.tail.prev!.keys.values().next().value ?? "";
    }

    getMinKey(): string {
        if (this.head.next === this.tail) return "";
        return this.head.next!.keys.values().next().value ?? "";
    }
}