//! Growable vectors, hash maps and hash sets.
//!
//! `Vec` is a list of values that grows as they are pushed, and `VecIter`
//! walks one in order. `Map` maps keys to values, and `Set` holds values
//! without repeats; both need a key or value type that implements `Hash` and
//! `Eq`. Every module sees these types without an import, and a module's own
//! definition of one of these names shadows the one here.
//!
//! The three collections are shared, not copied: assigning one to another
//! binding, or passing it to a function, gives a second name for the same
//! collection, and a change made through either is seen through both. A
//! method that changes a collection takes `mut self`, and needs a mutable
//! receiver, such as one held in a `mut` binding.
//!
//! A `Vec`, a `Map` and a `Set` in use:
//!
//! ```
//! let mut scores: Vec<Int> = Vec::new()
//! scores.push(90)
//! scores.push(75)
//! assert_eq(scores.len(), 2)
//! assert(scores.get(5).is_none(), "an index past the end gives None")
//!
//! let mut ages: Map<String, Int> = Map::new()
//! ages.insert("ada", 36)
//! assert_eq(ages.get("ada").unwrap(), 36)
//! assert(!ages.contains_key("alan"), "alan was never inserted")
//!
//! let mut seen: Set<String> = Set::new()
//! assert(seen.insert("nova"), "the first insert adds the value")
//! assert(!seen.insert("nova"), "a repeat is not added again")
//! assert_eq(seen.len(), 1)
//! ```
// Nova standard library — collections.
//
// Compiled as an implicit module and glob-imported into every user module, so
// these names need no `import`. A user definition of the same name shadows the
// one here (see docs/adr/0004-stdlib-compile-model.md).
//
// `Vec` grows by allocating a larger `[T]` and reassigning the field: the record
// object's address never changes and the array's only referent is that field, so
// the conservative non-moving collector needs no special handling.
/// A list of values of type `T`, indexed from 0, that grows as values are
/// pushed.
///
/// `get` returns `None` for an index out of range, where `set` panics.
/// Assigning a `Vec`, or passing it to a function, shares it rather than
/// copying it.
///
/// A `Vec` is shared, not copied, when it is assigned:
///
/// ```
/// let mut a: Vec<Int> = Vec::new()
/// a.push(1)
///
/// // Assigning a Vec shares it: `b` is a second name for the same vector.
/// let mut b = a
/// b.push(2)
/// assert_eq(a.len(), 2)
///
/// // For an independent copy, build a new Vec from the values.
/// let mut copy: Vec<Int> = Vec::new()
/// for x in a.iter() { copy.push(x) }
/// copy.push(3)
/// assert_eq(a.len(), 2)
/// assert_eq(copy.len(), 3)
/// ```
pub record Vec<T> { len: Int, data: [T] }
impl<T> Vec<T> {
// An empty vector. No storage is allocated until the first `push`.
/// Returns an empty vector.
pub fn new() -> Vec<T> { Vec { len: 0, data: [] } }
/// Returns the number of values in the vector.
pub fn len(self) -> Int { self.len }
/// Returns `true` if the vector holds no values.
pub fn is_empty(self) -> Bool { self.len == 0 }
// Append `x`, growing if full.
//
// Growth allocates `[x; newcap]` — using the pushed element as the filler,
// so no slot is ever uninitialized and no `Default` bound is needed — then
// copies the existing elements back. Slot `self.len` is then already `x`,
// so the append needs no further store on the growth path.
/// Appends `x` to the end of the vector, growing its storage when it is
/// full.
pub fn push(mut self, x: T) {
if self.len == self.data.len() {
let newcap = if self.len == 0 { 4 } else { self.len * 2 }
let mut grown = [x; newcap]
for i in 0..self.len { grown[i] = self.data[i] }
self.data = grown
} else {
self.data[self.len] = x
}
self.len = self.len + 1
}
/// Removes the last value and returns it, or returns `None` if the vector
/// is empty.
pub fn pop(mut self) -> Option<T> {
if self.len == 0 {
None
} else {
let last = self.data[self.len - 1]
self.len = self.len - 1
Some(last)
}
}
/// Returns the value at index `i`, or `None` if `i` is negative or not
/// less than `len()`.
pub fn get(self, i: Int) -> Option<T> {
if i < 0 { None } else { if i >= self.len { None } else { Some(self.data[i]) } }
}
/// Replaces the value at index `i` with `v`.
///
/// Panics if `i` is negative or not less than `len()`: `set` never adds a
/// value, as `push` does.
pub fn set(mut self, i: Int, v: T) {
if i < 0 { panic("Vec::set index out of range") }
if i >= self.len { panic("Vec::set index out of range") }
self.data[i] = v
}
/// Removes every value, leaving the vector empty. It keeps its storage for
/// the values pushed next.
pub fn clear(mut self) { self.len = 0 }
// A cursor over this vector's elements, starting at index 0. See `VecIter`
// below for what the cursor shares with this vector.
//
// Deliberately in this existing `impl<T> Vec<T>` block rather than a second
// inherent impl on `Vec<T>`: two inherent impls on one type is a
// configuration nothing in std or the test suite exercises, and `std/strings`
// avoided it for the same reason.
/// Returns an iterator over the vector's values, from index 0 up.
///
/// The iterator shares the vector rather than copying it, so it sees
/// changes made while it runs: a value pushed onto the vector is yielded
/// too, even one pushed after the iterator has returned `None`.
pub fn iter(self) -> VecIter<T> { VecIter { v: self, i: 0 } }
}
// A cursor over a `Vec<T>`: the vector, plus the next index to yield.
//
// The vector is held by value, but records are heap objects passed by pointer,
// so this **shares** the caller's storage rather than copying it — a `push`
// during iteration is visible to the iterator, and an element appended after
// the iterator has already answered `None` is still yielded by the next call.
// That is the same alias-visibility the whole module has (see the header); it is
// documented rather than prevented, because preventing it needs borrow tracking
// the language does not have. `an_exhausted_vec_iterator_does_not_advance_its_cursor`
// in `crates/nova-cli/tests/run_tests.rs` pins it, so it is a property and not
// an accident.
//
// As with `Map` and `Set` above, the `Iterator` contract lives on the `impl`
// below, not on this record's generic parameter. A bound in that position is no
// longer `E0900` — Phase 2.2d accepts it as a **resolution scope** so a field
// type may name a projection on the parameter (ADR 0007 §1) — but it would buy
// nothing here: `v: Vec<T>` and `i: Int` name no projection, so `T` needs no
// bound to be convertible, and a bound in that position is not enforced at
// construction. `std/core`'s `MapIter`/`FilterIter` are the records that do
// need one.
/// An iterator over a `Vec`'s values, in order.
///
/// `Vec::iter` returns one. It shares the vector rather than copying it, so a
/// value pushed onto the vector is yielded too, even after the iterator has
/// returned `None`.
pub record VecIter<T> { v: Vec<T>, i: Int }
impl<T> Iterator for VecIter<T> {
// Bound to the impl's **own** parameter, not to a primitive. That is what
// makes every projection through this impl go through `subst`, and so what
// makes `VecIter<Int>` and `VecIter<String>` resolve `Item` differently
// instead of sharing one cached answer.
type Item = T
// Written `Option<T>` rather than echoing the trait's `Option<Self::Item>`.
// Both spellings are accepted (conformance normalizes each side before
// comparing); the concrete one is chosen here because it reads as the
// answer to "what does this yield" rather than restating the question.
fn next(mut self) -> Option<T> {
// Not a bounds check — `Vec::get` already returns `None` out of range,
// so this guard is redundant for safety. What it buys is that `i` stops
// at `len` instead of running away past it, which is why relaxing `>=`
// to `>` is not the equivalent mutation it looks like.
if self.i >= self.v.len() { return None }
let x = self.v.get(self.i)
self.i = self.i + 1
x
}
}
// A hash map with open addressing and linear probing.
//
// Capacity is a power of two, so a bucket index is `hash & (cap - 1)` — never
// `hash % cap`. A hash may be negative (`mix64` spans the whole `Int` range and
// `str_hash` reinterprets an unsigned 64-bit result), and `%` inherits that
// sign while `&` with a positive mask does not. The high bits are not read at
// all: Nova's `>>` is arithmetic with no `>>>`, so a negative hash
// sign-extends. See the masking rule on `pub trait Hash` in std/core.
//
// A `String`, `Int`, `Bool` or `Char` key's hash is SEEDED ONCE PER PROCESS —
// `String` from `nova_rt_str_hash`'s draw and the other three from
// `nova_rt_int_hash_seed`'s, which is a separate draw — so which bucket a given
// key lands in is not a property of the program text: two runs of the same
// program, inserting the same keys in the same order, build different tables.
// Lookup and `len` do not change — every probe in a run uses the run's own
// seed, and `len` counts live entries whatever the layout — but what a caller
// can OBSERVE about layout can vary run to run. `keys()` order is the channel
// a caller is most likely to notice (see its own note below); the `keys`,
// `vals` and `state` fields are reachable directly and carry the same
// variation, which is what a fixture reading them is reading.
//
// GROWTH IS NOT ON THAT UNCHANGED LIST. The trigger in `insert` reads `used`,
// which counts tombstones as well as occupied slots, and an insert that reuses a
// tombstone leaves `used` where it was while one taking a fresh slot raises it
// (see "A reused tombstone was already counted in `used`" below). Which of the
// two happens depends on the probe path, so a map with a seeded key type that
// holds tombstones can reach a different capacity on different runs of the same
// program. Checked in `tests/runtime/collections.nova`, which a grep for
// `state.len()` across `tests/runtime/*.nova` matches and no sibling does: its
// `String`-keyed maps `sm` and `sb` never remove anything, so `sb`'s printed
// `cap=64` follows from its 30 insertions alone; every `.remove(` in that file
// passes an `Int` or a `Key`; and its `Key` impl is `self.id`, which reaches no
// seeded hash. Re-run that grep rather than trusting this sentence.
//
// The `Int` case there survives for a narrower reason than the `Key` one, and
// it is worth stating because the reason is not "`Int` is unseeded" any more.
// Its `Map<Int, Int>` removes one key and then reinserts that same key while
// printing a capacity. The table holds exactly one tombstone at that point —
// the removed key's own former slot, which lies on that key's own probe path —
// so `insert`'s `first_free` is that slot at every seed, the reinsert reuses
// it, and `used` and the capacity cannot move. A fixture that removed one key
// and then inserted a DIFFERENT one before printing a capacity would have no
// such argument.
//
// A key of a user type is stable only while its own `Hash` impl reaches no
// seeded hash: one `str_hash` call, or one `.hash()` on an `Int`, `Bool` or
// `Char` field, anywhere inside that impl carries a per-process seed into the
// result, and the layout varies with it. The seeding lives in the runtime at
// `nova_rt_str_hash` and `nova_rt_int_hash_seed`, which document what it buys
// and what it does not; neither hash is collision-resistant either way.
//
// The three arrays are allocated together on the first insert, using the
// inserted key and value as fillers, so no slot is ever uninitialized and no
// `Default` bound is needed. `state` is filled with 0, which is exactly the
// "empty" tag, so a fresh table is empty by construction. Slot states are
// `0` empty, `1` occupied, `2` tombstone.
//
// `len` counts live entries only. `used` counts occupied *plus* tombstones and
// is what the load threshold reads, so a remove-heavy workload cannot degrade
// into an all-tombstone scan.
//
// The `K: Hash + Eq` contract lives on the `impl` below, not on this record's
// own generic parameters. `record Map<K: Hash + Eq, V>` does compile as of
// Phase 2.2d — a bound on a *record*'s type parameter is accepted as a
// **resolution scope**, so that a field type may name a projection on the
// parameter (ADR 0007 §1). What it is not is a **constraint**: it is not
// checked when the record is built, because `nova-hir`'s `RecordType` keeps
// only a generic count and `nova-mir`'s `mono` checks bounds solely against a
// function's own `bounds`, so that position has no way to enforce anything.
// (That mechanism is exactly what ADR 0007's "why it is not enforced" cites.)
// Writing the bound here would therefore be decoration: no field of `Map`
// names a projection, so nothing needs resolving, and the bound would promise
// a check it does not perform. On the impl it is real: instantiating any
// method with a key that is not `Hash + Eq` is E0013 at monomorphization,
// which is pinned by `map_key_without_hash_reports_e0013` in nova-mir's
// lowering tests.
/// A hash map from keys of type `K` to values of type `V`.
///
/// Its methods need a key type that implements `Hash` and `Eq`, and keys
/// equal by `eq` must have the same hash. Assigning a `Map`, or passing it to
/// a function, shares it rather than copying it.
pub record Map<K, V> { len: Int, used: Int, keys: [K], vals: [V], state: [Int] }
impl<K: Hash + Eq, V> Map<K, V> {
// An empty map. No storage is allocated until the first `insert`.
/// Returns an empty map.
pub fn new() -> Map<K, V> { Map { len: 0, used: 0, keys: [], vals: [], state: [] } }
// Number of live entries; unaffected by tombstones.
/// Returns the number of entries in the map.
pub fn len(self) -> Int { self.len }
/// Returns `true` if the map holds no entries.
pub fn is_empty(self) -> Bool { self.len == 0 }
// Bucket for `k` in a table of capacity `cap` (a power of two). `cap` must
// be positive: at `cap == 0` the mask would be `-1` and the result the raw
// hash, so every caller checks for the unallocated table first.
fn slot_of(self, k: K, cap: Int) -> Int { k.hash() & (cap - 1) }
// Insert, returning the previous value for `k` if there was one.
//
// The probe never stops at a tombstone: it runs on to either `k` itself (a
// replacement) or an empty slot (a genuine absence), and only then stores
// into the *first* tombstone it passed. Stopping early would let a second
// copy of `k` appear behind the tombstone; not reusing the tombstone at all
// would let a churn workload grow without bound.
/// Maps `k` to `v`, and returns the value `k` mapped to before, or `None`
/// if `k` was not in the map.
///
/// If `k` was in the map, its entry keeps the key it had and takes `v`.
pub fn insert(mut self, k: K, v: V) -> Option<V> {
if self.state.len() == 0 {
self.keys = [k; 8]
self.vals = [v; 8]
self.state = [0; 8]
} else {
// Grow above 3/4 load, counting tombstones.
if (self.used + 1) * 4 > self.state.len() * 3 { self.grow(k, v) }
}
// After that check `used + 1 <= cap * 3 / 4 < cap`, so at least one slot
// is still empty and the scan below always terminates at `st == 0`
// before `probes` runs out. The `panic` is unreachable.
let cap = self.state.len()
let mut i = self.slot_of(k, cap)
let mut first_free = -1
let mut probes = 0
while probes < cap {
let st = self.state[i]
if st == 0 {
let at = if first_free >= 0 { first_free } else { i }
self.keys[at] = k
self.vals[at] = v
self.state[at] = 1
self.len = self.len + 1
// A reused tombstone was already counted in `used`.
if first_free < 0 { self.used = self.used + 1 }
return None
}
if st == 1 {
if self.keys[i].eq(k) {
let old = self.vals[i]
self.vals[i] = v
return Some(old)
}
} else {
if first_free < 0 { first_free = i }
}
i = (i + 1) & (cap - 1)
probes = probes + 1
}
panic("Map::insert found no free slot")
}
// The slot index of a live entry for `k`, or `-1` if there is none. Shared
// by `get` and `remove`, which differ only in what they do with the slot
// once found — `get` reads it, `remove` writes a tombstone into it — so
// this scan now lives in one place instead of the two separate copies
// `get` and `remove` used to carry. `insert` (above) cannot share it: it
// has to track the first tombstone it passes (`first_free`) so a fresh
// key reuses that slot, and must keep scanning past a tombstone to tell a
// replacement (the key turns up further on) from a genuine insertion (an
// empty slot reached with no match) — a plain lookup needs neither.
//
// Only an empty slot ends the chain; a tombstone is walked past, so a key
// inserted past a tombstone stays reachable — removing from the middle of
// a chain must not break the chain for keys further along it.
fn find(self, k: K) -> Int {
let cap = self.state.len()
// Not what keeps this safe from indexing anything bad — at `cap == 0`
// the loop below never executes regardless, since `probes < cap` is
// false from the start. What this guard keeps true is `slot_of`'s own
// precondition (see its comment above): every caller checks for the
// unallocated table first, and without this line `find` would call
// `slot_of(k, 0)` and break that contract, even though nothing
// downstream happens to depend on it today.
if cap == 0 { return -1 }
let mut i = self.slot_of(k, cap)
let mut probes = 0
while probes < cap {
let st = self.state[i]
if st == 0 { return -1 }
if st == 1 { if self.keys[i].eq(k) { return i } }
i = (i + 1) & (cap - 1)
probes = probes + 1
}
// Unreachable, for the same reason `insert`'s trailing `panic` is
// (see its comment above): the 3/4 load threshold caps `used` at 6 of
// 8 (or the equivalent fraction at any capacity), so at least two
// slots are always empty and the scan above always returns at
// `st == 0` before `probes` runs out. Kept as `return -1` rather than
// a `panic` — unlike `insert`, `find` has a safe fallback: an absent
// key is an ordinary result, not a corrupted table.
//
// Not a bare trailing `-1`: a line starting with `-` right after a
// `}`-closed block is absorbed as binary subtraction against the
// `while` above (which types `Unit`), not read as a fresh statement —
// the same trap `tests/runtime/collections.nova` binds `miss` to
// avoid. `return` makes this an unambiguous statement.
return -1
}
/// Returns the value `k` maps to, or `None` if `k` is not in the map.
///
/// Telling a missing key from a present one:
///
/// ```
/// let mut stock: Map<String, Int> = Map::new()
/// stock.insert("apples", 3)
///
/// // `get` returns an `Option`: `None` for a key that is not in the map.
/// let pears = match stock.get("pears") {
/// Some(n) => n
/// None => 0
/// }
/// assert_eq(pears, 0)
/// assert_eq(stock.get("apples").unwrap_or(0), 3)
///
/// // `insert` returns the value the key had before, if any.
/// assert_eq(stock.insert("apples", 5).unwrap(), 3)
/// assert(stock.insert("pears", 1).is_none(), "pears is new")
/// assert_eq(stock.len(), 2)
/// ```
pub fn get(self, k: K) -> Option<V> {
let i = self.find(k)
if i < 0 { None } else { Some(self.vals[i]) }
}
/// Returns `true` if `k` is in the map.
pub fn contains_key(self, k: K) -> Bool {
match self.get(k) {
Some(_) => true
None => false
}
}
// Remove `k`, leaving a tombstone so later probes still reach entries that
// were inserted past this slot. `len` drops; `used` does not, because the
// slot is still unusable to a probe walking through it.
/// Removes the entry for `k` and returns its value, or returns `None` if
/// `k` was not in the map.
pub fn remove(mut self, k: K) -> Option<V> {
let i = self.find(k)
if i < 0 {
None
} else {
let old = self.vals[i]
self.state[i] = 2
self.len = self.len - 1
Some(old)
}
}
// The live keys, in table order. `state[j]` is 1 for occupied, 2 for a
// tombstone and 0 for empty, so this is the same walk `grow` already does
// to find the entries worth reinserting.
//
// The `[fill; n]` FORM is forced rather than stylistic: the AST has
// exactly two array-construction nodes, and a length known only at run
// time needs the repeat form, which needs a value in hand -- Nova has no
// null. `Vec::push` grows by the same manoeuvre.
//
// The five-line SEARCH for a live slot below is NOT forced, and this
// comment used to read as if it were. No slot is ever uninitialized --
// the record's own header note and `grow` below both state that
// invariant -- so `self.keys[0]` would seed the array just as well, live
// or not, and the collecting walk overwrites all `self.len` slots either
// way. The search is removable with no behaviour any test can observe;
// it is kept so the seed is visibly a value this map actually holds.
//
// Table order is deliberately NOT insertion order, and no caller should
// assume it is. The strongest true statement is that KEYS() ORDER IS NOT A
// FUNCTION OF THE KEY SET ALONE. Hash order alone reverses insertion order
// with NO GROWTH AT ALL -- measured: inserting `"a"`, `"c"`, `"e"` into a
// fresh map returns `"e"`, `"c"`, `"a"`, three entries in a cap-8 table
// that never reaches the 3/4 threshold -- and a `grow` then reinserts every
// entry and can reorder them again on top of that. Naming only `grow`
// would let a reader infer that a map which never grows preserves
// insertion order, and that inference is false.
//
// FOR A SEEDED KEY TYPE THERE IS NOW A STRONGER STATEMENT, and it is a
// change in observable behaviour rather than a restatement of the above.
// The order used to be fixed by the key set and the insertion sequence
// together, so one unchanged binary run twice returned the same order both
// times; the per-process hash seed (see the record header above) means it
// CAN DIFFER BETWEEN RUNS of that same binary. Not must: a different seed
// may land on the same layout, and a one-key map has only one order to
// return. So a caller must not treat one observed order as reproducible,
// and a test or a golden that pins more than one key's order is pinning a
// seed it does not control -- sort, or assert per key. This covers `String`
// keys and, since `int_hash_seed` reached the primitive impls, `Int`, `Bool`
// and `Char` keys as well. What is left outside it is a user `Hash` impl
// that reaches no seeded hash, for which the paragraph above covers the
// whole of it.
//
// One consequence for the paragraph above: its `"e"`, `"c"`, `"a"` was
// measured when the hash was unseeded. What it demonstrates is intact and
// is the reason it is there -- no growth is needed to reorder, so a
// never-growing map does not preserve insertion order -- but that exact
// sequence is not reproducible now. Read it as an instance of the property,
// not as an order to expect from those three keys.
/// Returns the map's keys, as an array with one element per entry.
///
/// Their order is unspecified: it need not be the order the keys were
/// inserted in, and it can change from one run of a program to the next.
pub fn keys(self) -> [K] {
if self.len == 0 { return [] }
let cap = self.state.len()
let mut seed = 0
let mut i = 0
while i < cap {
if self.state[i] == 1 {
seed = i
i = cap
} else {
i = i + 1
}
}
let mut out = [self.keys[seed]; self.len]
let mut w = 0
let mut j = 0
while j < cap {
if self.state[j] == 1 {
out[w] = self.keys[j]
w = w + 1
}
j = j + 1
}
out
}
// Double the capacity and reinsert the live entries, which is also what
// clears the tombstones. `fk`/`fv` are fillers for the fresh arrays, so no
// slot is uninitialized; `state`'s 0 filler makes the new table empty.
//
// Reached only from `insert`'s pre-check, and the reinserts cannot re-enter
// it: `used` is reset to 0 and at most `oldcap` live entries go back in,
// while the new threshold needs `used + 1 > newcap * 3 / 4`, i.e. more than
// `1.5 * oldcap`. So the nesting is exactly one level deep.
//
// GC: this is *not* safe for the reason `Vec::push` is. `push` finishes the
// new array before reassigning the field, so the old one stays reachable
// through the record the whole time. Here `self.keys` is reassigned on the
// very next line, and from then on `oldkeys` is live only in this frame's
// locals while two more `[_; newcap]` allocations and one allocation per
// reinsert all run — every one of them a collection point. It is safe
// because the collector scans the stack from the allocating frame up to the
// thread base *plus* the callee-saved registers `gc_stack.c` spills
// there, and the ABI leaves anything live across a call in one of those two
// places; marking is range-based, so a derived element pointer counts too.
// That is a property of the calling convention, not of the record/buffer
// shape, which is why this window is what makes `NOVA_GC_STRESS=1`
// load-bearing on `tests/runtime/collections.nova` rather than
// belt-and-braces — a missed root here loses entries silently instead of
// crashing.
fn grow(mut self, fk: K, fv: V) {
let oldcap = self.state.len()
let newcap = oldcap * 2
let oldkeys = self.keys
let oldvals = self.vals
let oldstate = self.state
self.keys = [fk; newcap]
self.vals = [fv; newcap]
self.state = [0; newcap]
self.len = 0
self.used = 0
for j in 0..oldcap {
if oldstate[j] == 1 {
// Reinserting a key the fresh table cannot already hold always
// returns `None`, so the result is discarded.
let _ = self.insert(oldkeys[j], oldvals[j])
}
}
}
}
// A hash set, backed by a `Map` with a placeholder value. Reusing `Map` keeps
// the probing, tombstone and growth logic in exactly one place.
//
// As with `Map` (see the note above it), the `T: Hash + Eq` contract lives on
// the `impl`, not on this record's generic parameter. A bound there is legal as
// of Phase 2.2d but is a resolution scope rather than a constraint (ADR 0007
// §1), and `map: Map<T, Bool>` names no projection, so it would resolve nothing
// and enforce nothing.
/// A hash set of values of type `T`, each held once.
///
/// Its methods need a value type that implements `Hash` and `Eq`, and values
/// equal by `eq` must have the same hash. Assigning a `Set`, or passing it to
/// a function, shares it rather than copying it.
pub record Set<T> { map: Map<T, Bool> }
impl<T: Hash + Eq> Set<T> {
// An empty set. No storage is allocated until the first `insert`.
/// Returns an empty set.
pub fn new() -> Set<T> { Set { map: Map::new() } }
// Number of elements; unaffected by tombstones (see `Map::len`).
/// Returns the number of values in the set.
pub fn len(self) -> Int { self.map.len() }
/// Returns `true` if the set holds no values.
pub fn is_empty(self) -> Bool { self.map.is_empty() }
// Add `v`, returning whether it was newly added. `Map::insert` returns
// `Some(old)` when `v` was already a key, so "newly added" is exactly the
// `None` case — the inverse of what `Map::insert` reports.
/// Adds `v` to the set, and returns `true` if it was not there before.
///
/// If an equal value was there, the set keeps that one and returns
/// `false`.
pub fn insert(mut self, v: T) -> Bool {
match self.map.insert(v, true) {
Some(_) => false
None => true
}
}
/// Returns `true` if `v` is in the set.
pub fn contains(self, v: T) -> Bool { self.map.contains_key(v) }
// Remove `v`, returning whether it was present. `Map::remove` returns
// `Some(old)` when `v` was there, so "was present" is exactly the
// `Some` case — the inverse of what `Map::remove` reports.
/// Removes `v` from the set, and returns `true` if it was there.
pub fn remove(mut self, v: T) -> Bool {
match self.map.remove(v) {
Some(_) => true
None => false
}
}
}