Successor disjoint sets: skip permanently retired slots

Last updated: 4 Oct 20269 min read

tutorial

A successor disjoint set tracks the first available integer slot at or after a requested index when slots can be retired permanently. Parent entries initially point to themselves. Retiring slot s redirects its parent to the first available slot after s; a find follows and compresses those forward links. A sentinel at capacity marks exhaustion. The representative has a required meaning—the next unretired slot—so an ordinary union-by-rank choice would be wrong unless an additional successor field preserved that meaning. A claim looks up the next slot and retires it in one operation. This is a monotone allocation structure: it cannot reopen a retired slot, release a claimed bay, or serve a growing domain without rebuilding.

Operational case

Nine loading bays are numbered zero through eight. Reserve bays two, three, and six. Two claims starting at bay two return four and five; the next available bay from six is seven. Retiring three again returns false because it is already absent. A claim starting at eight returns eight, then the sentinel causes the next claim to return no bay. The index includes an addressable sentinel at nine, but that sentinel is never a usable bay. Path compression can make a repeated search cheap after traversing a long retired chain, yet it never restores a retired bay.

Working Python program

class AvailableSlotIndex:
    def __init__(self, capacity):
        if capacity < 0:
            raise ValueError("capacity cannot be negative")
        self.capacity = capacity
        self.parent = list(range(capacity + 1))

    def _find(self, slot):
        trail = []
        while self.parent[slot] != slot:
            trail.append(slot)
            slot = self.parent[slot]
        for visited in trail:
            self.parent[visited] = slot
        return slot

    def next_available(self, start):
        if not 0 <= start <= self.capacity:
            raise IndexError(start)
        slot = self._find(start)
        return None if slot == self.capacity else slot

    def retire(self, slot):
        if not 0 <= slot < self.capacity:
            raise IndexError(slot)
        if self._find(slot) != slot:
            return False
        self.parent[slot] = self._find(slot + 1)
        return True

    def claim_next(self, start):
        slot = self.next_available(start)
        if slot is not None:
            self.retire(slot)
        return slot


loading_bays = AvailableSlotIndex(9)
for reserved_bay in (2, 3, 6):
    loading_bays.retire(reserved_bay)
print(loading_bays.claim_next(2), loading_bays.claim_next(2))
print(loading_bays.next_available(6), loading_bays.retire(3))
print(loading_bays.claim_next(8), loading_bays.claim_next(8))

Output

4 5
7 False
8 None

Time, space, and tradeoff

Initialization writes N+1 parent entries in O(N) time and space. A single find or claim can follow O(N) forward links before compression, so this implementation does not promise worst-case constant time or the usual union-by-rank inverse-Ackermann bound. Compression shortens later traversals of those same chains. Retire performs one successor find plus a redirect and is idempotent here. A sorted set supports both retirement and reopening but pays logarithmic ordered operations; a fixed bitset can be simpler for a small dense universe. Choose this one-way index only when permanent disappearance is the actual contract.

Common Mistakes

Do not apply union by rank without preserving which representative is the successor.
Do not return the capacity sentinel as an available slot.
Do not advertise reopening when parents only move forward.
Do not claim a worst-case constant-time find before compression.

Connected lessons

Compare this operation boundary with Persistent range-distinct counts: keep only the latest position active, Editable substring fingerprints: join hashes in a segment tree, Sliding medians: expire heap entries by event identity, Ball trees: prune exact nearest-depot search with radius bounds, then complete the audit project and decision quiz.

data structures

graphs-and-disjoint-sets