Module: collections.set

Source: ./collections/set.reef

Overview

collections/set — Set[T], hashed, elements bounded by Hash.

Collections 0.9.2 / D8. This replaces the LINEAR set that lived here (O(n) contains) and the string-only HashSet in collections/hashset. One set type, one module path: collections.set.

Open addressing with linear probing, same 70% load rule and the same slot-index discipline as collections.hashmap.

Usage: import collections.set let seen = set.create:string seen.add("ada") if seen.contains("ada") println("yes") end if

ELEMENTS ARE COMPARED WITH ==, WHICH IS NOT VALUE EQUALITY FOR STRUCTS. For int, string and bool it compares values. For a struct or object it is REFERENCE IDENTITY (D3), so two separately constructed structs with identical fields are two distinct elements. Prefer an int or string element type; see examples/test_struct_eq_identity.reef.

Factories: createT -> Set[T] 32 slots create_with_capacityT -> Set[T] cap < 1 clamps to 1

Methods: add(value) -> bool true if newly inserted try_add(value) -> Result[bool, Error] Ok(true) = inserted, Ok(false) = already present, Err = hard failure contains(value) -> bool remove(value) -> bool true if it existed len() / capacity() / is_empty() / clear() elements() -> [T] occupied elements, probe order union(other) / intersection(other) / difference(other) -> Set[T] is_subset(other) / is_superset(other) -> bool

The set algebra is GENERIC. The linear version only offered it for int and string (set_union_int, set_union_string, ...), which is why the typed factories existed at all.

Performance: O(1) average add/contains/remove; O(n) elements(), the algebra, and rehash.

Types

Set

Slot states: 0=empty, 1=occupied, 2=deleted (tombstone)

Fields:

Functions

fn create(): Set[T]

fn create_with_capacity(cap: int): Set[T]

cap < 1 clamps to 1 (BUG-062): a zero-capacity table would divide by zero in slot_of.

Generated by reefc doc