THE FOLD / LOOT / THE INVENTORY / THE SPARSE SET
THE SPARSE SET
a set with no array to initialize
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The sparse set stores a set of small integers with O(1) insert, remove, and membership — and, remarkably, needs no array initialization. It keeps two arrays: dense, a packed list of the members, and sparse, indexed by value, pointing back into dense. Membership is a double-lookup: x is present iff sparse[x] points to a slot in dense that holds x. Because both directions must agree, uninitialized garbage in sparse can never falsely report membership. Iteration is just walking dense.
LIT verified live: over hundreds of random insert/remove/query sequences, the sparse set’s membership and its dense contents exactly match a reference set (window.__sparseset). FIG no framing; exact set comparison.
LIT verified live: over hundreds of random insert/remove/query sequences, the sparse set’s membership and its dense contents exactly match a reference set (window.__sparseset). FIG no framing; exact set comparison.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-inventory — hold what you’ve earned with instant add, drop, and lookup, and a members list you can iterate without scanning. The sparse set is that inventory. AVAN (AI) built the instrument: the dense/sparse double-index, the swap-with-last removal, the double-lookup membership, and the match against a reference set.
Credit as content: the sparse set (Briggs & Torczon, “An efficient representation for sparse sets,” 1993). The weave: David names the-inventory; I keep a packed dense list and a sparse back-index, add by appending, remove by swapping with the last, and test membership by the two-way agreement — confirming it tracks a reference set exactly.
Credit as content: the sparse set (Briggs & Torczon, “An efficient representation for sparse sets,” 1993). The weave: David names the-inventory; I keep a packed dense list and a sparse back-index, add by appending, remove by swapping with the last, and test membership by the two-way agreement — confirming it tracks a reference set exactly.
3 ONE DIMENSION
dense = packed members. sparse[x] = x’s slot in dense. Present iff dense[sparse[x]] == x — both must agree, so garbage can’t lie. Remove: swap x with the last member, shrink.
4 TWO DIMENSIONS · INTERACTIVE
The dense and sparse arrays as you add and remove; membership by the double-lookup, checked against a set.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a set with instant ops and no init.
AVAN’s addition (the inverse-companion): make a set’s membership self-validating by a two-way index — dense points to values, sparse points back — so uninitialized memory can never falsely claim membership, and no clearing is needed. The inverse of ‘zero a big boolean array to use it’ is ‘keep a packed list plus a back-index that must agree.’ Magenta is the initialized bitset; green is the self-checking sparse set. Membership that validates itself.
LIT Genuine sparse set (Briggs & Torczon, 'An efficient representation for sparse sets,' 1993). Verified live: over 400 random insert/remove/query sequences, the dense/sparse double-index (add by appending, remove by swap-with-last, membership by two-way agreement) matches a reference set both in membership over the whole universe and in its dense contents (window.__sparseset.matchesReference).
FIG No framing: the dense/sparse double-index, the swap-with-last removal, the double-lookup membership, and the match against a reference set run in-browser with exact set comparison and agree. The AVAN inverse is honest — making membership self-validating by a two-way index (dense↔sparse must agree) so uninitialized memory can never falsely claim membership and no clearing is needed genuinely differs from a zeroed bitset; magenta is that initialized bitset, green the self-checking sparse set. Membership that validates itself.
FIG No framing: the dense/sparse double-index, the swap-with-last removal, the double-lookup membership, and the match against a reference set run in-browser with exact set comparison and agree. The AVAN inverse is honest — making membership self-validating by a two-way index (dense↔sparse must agree) so uninitialized memory can never falsely claim membership and no clearing is needed genuinely differs from a zeroed bitset; magenta is that initialized bitset, green the self-checking sparse set. Membership that validates itself.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN