Gap labels: compare dispatch order across middle inserts

Last updated: 5 Oct 20269 min read

tutorial

An order-maintenance label maps every task ID to an increasing integer. Comparing two current labels answers which task comes first without scanning the list. Inserting after a known anchor chooses an unused integer between its label and the next task's label. When no integer remains, the model relabels the full sequence with fresh gaps before inserting. The ordered Python list is retained to find anchors and display the order. That list makes middle insertion and anchor search linear; this is a gap-label mechanics model, not a constant-time full order-maintenance implementation. Labels can change at relabel, so clients must compare through the current map rather than persist old labels as external IDs.

Operational case

Starting with tasks T-19 and T-83, repeated inserts immediately after T-19 consume progressively smaller gaps and eventually trigger a relabel. The final order is T-19, T-71, T-67, T-61, T-52, T-47, T-83. The current labels still put T-19 before T-83. A duplicate task ID is rejected, because one ID cannot have two positions in the map. If a user cached T-47's old label as a durable priority, a later relabel could silently invalidate that interpretation even though the task order itself remains correct.

Working Python program

class DispatchOrder:
    GAP = 16

    def __init__(self, task_ids):
        if len(set(task_ids)) != len(task_ids):
            raise ValueError("duplicate task")
        self.tasks = list(task_ids)
        self.labels = {task: (position + 1) * self.GAP for position, task in enumerate(self.tasks)}
        self.relabels = 0

    def before(self, first, second):
        return self.labels[first] < self.labels[second]

    def _relabel(self):
        self.labels = {task: (position + 1) * self.GAP for position, task in enumerate(self.tasks)}
        self.relabels += 1

    def insert_after(self, anchor, task):
        if task in self.labels:
            raise ValueError("duplicate task")
        position = self.tasks.index(anchor) + 1
        left = self.labels[anchor]
        right = self.labels[self.tasks[position]] if position < len(self.tasks) else left + self.GAP
        if right - left <= 1:
            self._relabel()
            left = self.labels[anchor]
            right = self.labels[self.tasks[position]] if position < len(self.tasks) else left + self.GAP
        self.tasks.insert(position, task)
        self.labels[task] = (left + right) // 2

    def remove(self, task):
        self.tasks.remove(task)
        del self.labels[task]


if __name__ == "__main__":
    queue = DispatchOrder(["T-19", "T-83"])
    for task in ["T-47", "T-52", "T-61", "T-67", "T-71"]:
        queue.insert_after("T-19", task)
    print(queue.tasks)
    print(queue.before("T-19", "T-83"), queue.relabels)

Output

['T-19', 'T-71', 'T-67', 'T-61', 'T-52', 'T-47', 'T-83']
True 1

Time, space, and tradeoff

A comparison of two present IDs is expected O(1) dictionary work. Insert-after takes O(N) to locate the anchor and shift the Python list, and a relabel adds O(N) work; removal also shifts O(N) entries. Memory is O(N). The arithmetic gap decision itself is constant-time, but it does not erase list costs or prove an amortized bound for arbitrary repeated inserts into one gap. A linked list with direct node handles would remove list shifting, while a full order-maintenance structure needs a stronger local relabel schedule.

Common Mistakes

Do not expose labels as permanent business identifiers.
Do not claim constant-time insertion while using list.index and list.insert.
Do not insert a second position for an existing task ID.
Do not leave equal labels after a gap is exhausted.

Connected lessons

Compare its input and update contract with CSR delta overlays: stage road edits before compaction, Reachability bitsets: precompute directed paths for a fixed graph, Skew heaps: meld priorities by swapping child paths, then complete the structure audit and decision quiz.

data structures

array-data-structure-guide