Set

Set is a heap-owned hash set (an NSMutableSet) of unique elements, each any Hashable + Comparable Object*. Membership is by value, and every stored element is held with a strong reference.

#import "Set.xc"           // or the Foundation umbrella

Overview

A Set stores its elements in a single power-of-two slot table (one cell per slot) using open addressing with linear probing, and keeps a parallel dense _order array so enumAt is O(1) and iteration is deterministic. It inherits from Object and needs a real heap (-falloc=heap, the default on the xt 6502 layout and every native backend).

Set is a generic container only at compile time: the element type parameter is a check the compiler erases, and the slots are type-erased pointer cells at runtime.

Elements must conform to both Hashable (for slot selection) and Comparable (for collision-chain equality). Foundation’s Number, String and Data conform to both. A user element type adds <Hashable, Comparable> to its class line and supplies the two methods.

Uniqueness by value. add uses the element’s equals on the probe chain, so re-adding a value-equal element is a no-op (no duplicate, no extra retain). contains is value membership, not identity.

Ownership (ARC). The Set holds a strong reference on every element. add retains a fresh element; remove / removeAll release what they drop; dealloc releases every element and frees the table. The set-algebra methods and copy return new sets that hold their own strong reference to every element. These are shallow: the elements are shared.

Load factor. The table grows (doubling) when it would pass α > 0.75, so membership stays close to O(1). Removed entries leave a tombstone rather than clearing, so later entries’ probe chains still resolve.

Availability

This is the 32-bit Set (support/generic/lib) for arm64, arm9, m68k and x86_64: counts/indices are u32 and the hash is a u32. The 6502 build (support/xt6502/lib) has the same API with narrower types: u16 counts/indices and a u8 hash. Heap-capable targets only.

Conforms to

• Enumerable: enumLength / enumAt, so for (Object* e in s) walks the elements.
• Copying: copy returns an independent (shallow) duplicate.

Every Set* is also an Object* and fits anywhere one is expected.

Topics

Creating · withCapacity · withArray · init

Accessing · add · contains · count · isEmpty

Removing · remove · removeAll

Set algebra · unionWith · intersect · subtract · symmetricDifference

Relations · isSubsetOf · isSupersetOf · intersects · isDisjointFrom · equalsSet

Conversion · allObjects

Iterating · enumLength · enumAt

Lifecycle · copy · dealloc

---

Creating

withCapacity

static Set* withCapacity(u32 cap)

Pre-allocates the slot table rounded up to a power of two (minimum 16), skipping a future resize copy when the rough upper bound is known. A bare new Set() allocates lazily on the first add.

withArray

static Set* withArray(Array* items)

A new Set of the distinct elements of items (null and duplicate entries are dropped). A null argument yields an empty Set.

init

void init(void)

The default initializer: an empty Set with no allocation. Prefer new Set() or the with… constructors; you rarely call init directly.

↑ Topics

Accessing

add

void add(Hashable* elem)

Adds elem if no value-equal element is already present, retaining it and appending it to the insertion order. Re-adding an existing value is a no-op. Triggers a resize first if the table would pass α > 0.75.

contains

bool contains(Hashable* elem)

true if a value-equal element is a member. O(1) average.

count

u32 count(void)

Number of live elements (excludes tombstones). O(1).

isEmpty

bool isEmpty(void)

true when count is zero.

↑ Topics

Removing

remove

void remove(Hashable* elem)

Removes the value-equal element (plants a tombstone, closes the gap in the insertion order, releases the element). A missing element is a no-op.

removeAll

void removeAll(void)

Releases every element and empties the table.

↑ Topics

Set algebra

Each returns a new Set; the receiver and the argument are untouched. The result holds its own strong reference to every element it contains.

unionWith

Set* unionWith(Set* other)

Everything in either set.

intersect

Set* intersect(Set* other)

Only what is in both sets.

subtract

Set* subtract(Set* other)

What is in the receiver but not in other.

symmetricDifference

Set* symmetricDifference(Set* other)

What is in one set or the other, but not both.

↑ Topics

Relations

Predicates over two sets; none of them allocate a result set.

isSubsetOf

bool isSubsetOf(Set* other)

true if every element of the receiver is in other. The empty set is a subset of anything (including a null other).

isSupersetOf

bool isSupersetOf(Set* other)

true if the receiver contains every element of other (other.isSubsetOf(self)).

intersects

bool intersects(Set* other)

true if the two sets share at least one element.

isDisjointFrom

bool isDisjointFrom(Set* other)

true if the two sets share no element (!intersects(other)).

equalsSet

bool equalsSet(Set* other)

true if the two sets have the same members, in any order (same count, and the receiver is a subset of other).

↑ Topics

Conversion

allObjects

Array* allObjects(void)

The members as a new Array, in iteration order (a Set has no meaningful order of its own).

↑ Topics

Iterating

The Enumerable hooks; you normally use for (Object* e in s) rather than calling these directly.

enumLength

u32 enumLength(void)

Number of elements the for-in driver will visit (== count).

enumAt

Object* enumAt(u32 i)

The i-th element for the for-in driver. A plain O(1) index, because _order is dense.

↑ Topics

Lifecycle

copy

Set* copy(void)

A new Set holding the same elements. The copy is shallow: the elements are shared, each retained by the new Set. This is the Copying method.

dealloc

void dealloc(void)

Releases every element, then frees the slot and order buffers. ARC calls it when the last reference goes away; you do not call it directly.

↑ Topics

Worked example

#import "Stdio.xc"
#import "Foundation.xc"

i32 main(void)
{
    Set* a = new Set();
    a.add(Number.with((i32)1));
    a.add(Number.with((i32)2));
    a.add(Number.with((i32)2));     // duplicate value — ignored

    Set* b = new Set();
    b.add(Number.with((i32)2));
    b.add(Number.with((i32)3));

    Set* both = a.intersect(b);     // { 2 }
    Stdio.printf("count(a)=%d  shared=%d\n",
                 (i16)a.count(), (i16)both.count());
    return 0;
}

count(a)=2  shared=1