Project: test depot rollback, routes, and ordered deletion

Last updated: 5 Oct 202618 min read

project

A depot planner evaluates a temporary bridge before approving a maintenance release. It must answer whether depots are connected under the proposed bridge, calculate a route over currently active directed roads, remove expired scheduler deadlines, and remove a booked maintenance window. Treat those as four distinct data-structure contracts. Build an independent oracle for each: a small edge list, a distance relaxation model, a sorted set of deadlines, and a plain list of windows. The production question comes later: when do readers see all accepted changes together?

Temporary connectivity

Join D-19 with D-26, then record a rollback checkpoint. Temporarily join D-26 with D-47. D-19 and D-47 must be connected under the proposal, but not after rollback. D-19 and D-26 remain connected in both states. Check the parent and size history after repeated redundant joins. A rollback token belongs to the active in-memory branch; it is not a durable revision number, and it cannot remove one old edge while preserving arbitrary later unions.

Routes and ordered indexes

Use directed roads D-19 to D-26 at 7 minutes, D-19 to D-47 at 14, D-26 to D-47 at 3, D-26 to D-52 at 8, and D-47 to D-52 at 4. The shortest route from D-19 to D-52 takes 14 minutes through D-26 and D-47. The old 14-minute heap entry for D-47 must be skipped after its distance improves to 10. Remove deadlines 26, 47, and 83 from the red-black index holding 47, 52, 61, 19, 26, 58, and 83; check order and every color path. Remove exact window [19, 26) from an AVL interval index, then query [25, 30) and require no overlap. Audit height and maximum-end metadata after the deletion.

Acceptance trace

Temporary D-19 to D-47: connected
After rollback D-19 to D-47: disconnected
D-19 to D-52: 14 via D-26 and D-47
Remaining deadlines: 19, 52, 58, 61
After removal [25, 30): no overlap

Cost and state boundary

Union by size without path compression bounds rollback-DSU find and union by O(log n); reverting u successful unions takes O(u). Balanced tree removals take O(log n) per key and O(log n) stack space in these recursive models. The lazy shortest-path heap can hold O(E) entries for E roads; stale entries are discarded on pop. These facts do not establish a transaction. If a planner approves the proposal, specify a publication version or committed record that binds the new graph, route data, and ordered indexes. If it rejects the proposal, keep the old state visible. A process crash between separate writes needs a recovery rule; no example here supplies one.

Common Mistakes

Do not enable unrecorded path compression in a rollback DSU.
Do not process a stale heap distance as a current shortest route.
Do not trust sorted red-black output without color and black-height checks.
Do not leave AVL maximum-end metadata stale after deleting a window.
Do not call a temporary checkpoint a durable published revision.

Connected lessons

data structures

projects