marks
The marks module.
Generated from spec/std/marks.cp by cpl doc --format json.
Marks
pub struct Marks<D>A visited/mark set over a domain D with O(1) add, remove, contains (v in m),
and O(1) clear(). Memory is one [D]0..=2_000_000_000 array (4 bytes per element).
Marks.new
fn new() -> Marks<D>An empty mark set over D, with its stamp array allocated once.
- cost: O(|D|)
- empty: an empty
Dgives a set that can never hold a mark - traps: never
Examples:
Marks<0..5>().is_empty
Marks.add
fn add(mut self, v: D) -> BoolMark v. Returns true when v was unmarked, false when it was already marked (and
nothing changes).
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = Marks<0..5>(); m.add(2) and not m.add(2)
Marks.remove
fn remove(mut self, v: D) -> BoolUnmark v. Returns true when v was marked, false when it was not (and nothing changes).
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = Marks<0..5>(); m.add(2); m.remove(2) and not m.remove(2)
Marks.contains
fn contains(self, v: D) -> BoolWhether v is marked; also spelled v in m.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = Marks<0..5>(); m.add(1); m.contains(1) and not m.contains(0)
Marks.clear
fn clear(mut self)Unmark everything by moving to a new generation, without touching the stamp array. Once the
generation counter reaches 2_000_000_000 the array is reset to zero, so the cost stays O(1)
amortized over the calls.
- cost: O(1) amortized; O(|D|) on the call that wraps the counter
- traps: never
Examples:
var m = Marks<0..5>(); m.add(1); m.add(3); m.clear(); m.is_empty and not (1 in m)
Marks.len
fn len(self) -> IntThe number of marked positions.
- cost: O(1)
- traps: never
Examples:
var m = Marks<0..5>(); m.add(1); m.add(3); m.add(1); m.len == 2
Marks.is_empty
fn is_empty(self) -> BoolWhether no position is marked; len == 0.
- cost: O(1)
- traps: never
Examples:
var m = Marks<0..5>(); m.add(0); m.remove(0); m.is_empty
MarkMap
pub struct MarkMap<D, T>Epoch-stamped map over domain D with O(1) get, set, contains, remove, and clear().
MarkMap.new
fn new(default_val: T) -> MarkMap<D, T>An empty map over D. default_val fills the value array and is never returned: an absent
key reads as None.
- cost: O(|D|)
- empty: an empty
Dgives a map that can never hold an entry - traps: never
Examples:
MarkMap<0..5, Int>(0).is_empty
MarkMap.len
fn len(self) -> IntThe number of keys present.
- cost: O(1)
- traps: never
Examples:
var m = MarkMap<0..5, Int>(0); m.set(1, 7); m.set(1, 8); m.set(4, 0); m.len == 2
MarkMap.is_empty
fn is_empty(self) -> BoolWhether no key is present; len == 0.
- cost: O(1)
- traps: never
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 1); m.remove(2); m.is_empty
MarkMap.contains
fn contains(self, v: D) -> BoolWhether v has a value. A key set to default_val is present.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 0); m.contains(2) and not m.contains(3)
MarkMap.get
fn get(self, v: D) -> ?TThe value at v, or None when v is absent.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.get(2) == Some(9) and m.get(3) == None
MarkMap.set
fn set(mut self, v: D, val: T)Give v the value val, adding v when it is absent and overwriting it otherwise.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.set(2, 4); m.get(2) == Some(4)
MarkMap.remove
fn remove(mut self, v: D) -> ?TRemove v and return the value it had, or None (and change nothing) when it was absent.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.remove(2) == Some(9) and m.remove(2) == None
MarkMap.clear
fn clear(mut self)Remove every key by moving to a new generation, without touching the value array; the
arrays are reset when the counter reaches 2_000_000_000, as for Marks.clear.
- cost: O(1) amortized; O(|D|) on the call that wraps the counter
- traps: never
Examples:
var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.clear(); m.get(2) == None and m.is_empty
Interner
pub struct Interner<K>Online value-to-id interner assigning contiguous 0..len IDs to distinct keys K.
id, get, and key are O(1) expected; len, is_empty, clear are O(1).
Interner.new
fn new() -> Interner<K>An empty interner.
- cost: O(1)
- traps: never
Examples:
Interner<Str>().is_empty
Interner.len
fn len(self) -> IntThe number of distinct keys interned so far; ids are exactly 0..len.
- cost: O(1)
- traps: never
Examples:
var t = Interner<Str>(); t.id("a"); t.id("b"); t.id("a"); t.len == 2
Interner.is_empty
fn is_empty(self) -> BoolWhether no key has been interned; len == 0.
- cost: O(1)
- traps: never
Examples:
var t = Interner<Str>(); t.id("a"); t.clear(); t.is_empty
Interner.clear
fn clear(mut self)Forget every key, so the next new key gets id 0 again.
- cost: O(1)
- traps: never
Examples:
var t = Interner<Str>(); t.id("a"); t.id("b"); t.clear(); t.id("b") == 0
Interner.id
fn id(mut self, k: K) -> IntThe id of k. A new key gets the next id, len, so ids follow first-seen order.
- cost: O(1) expected
- traps: never
Examples:
var t = Interner<Str>(); t.id("x") == 0 and t.id("y") == 1 and t.id("x") == 0
Interner.get
fn get(self, k: K) -> ?IntThe id of k, or None when k has not been interned; never adds a key.
- cost: O(1) expected
- traps: never
Examples:
var t = Interner<Str>(); t.id("x"); t.get("x") == Some(0) and t.get("y") == None and t.len == 1
Interner.key
fn key(self, i: Int) -> KThe key whose id is i; the inverse of id.
- cost: O(1)
- traps: when
iis outside0..len
Examples:
var t = Interner<Str>(); t.id("x"); t.id("y"); t.key(1) == "y"
Interner.contains
fn contains(self, k: K) -> BoolWhether k has been interned; get(k) != None.
- cost: O(1) expected
- traps: never
Examples:
var t = Interner<Int>(); t.id(40); t.contains(40) and not t.contains(41)
Interner.reserve
fn reserve(mut self, cap: Int)Allocate room for at least cap distinct keys, so the next cap - len new keys do not
reallocate. Changes no ids.
- cost: O(cap)
- traps: when
cap < 0
Examples:
var t = Interner<Int>(); t.reserve(100); t.id(5); t.len == 1
SparseSet
pub struct SparseSet<D>Briggs-Torczon sparse set over domain D.
O(1) add, remove, contains, clear AND O(len) iteration over active elements.
SparseSet.new
fn new() -> SparseSet<D>An empty sparse set over D.
- cost: O(|D|)
- empty: an empty
Dgives a set that can never hold an element - traps: never
Examples:
SparseSet<0..5>().is_empty
SparseSet.len
fn len(self) -> IntThe number of elements.
- cost: O(1)
- traps: never
Examples:
var s = SparseSet<0..5>(); s.add(1); s.add(4); s.add(1); s.len == 2
SparseSet.is_empty
fn is_empty(self) -> BoolWhether the set has no elements; len == 0.
- cost: O(1)
- traps: never
Examples:
var s = SparseSet<0..5>(); s.add(1); s.remove(1); s.is_empty
SparseSet.contains
fn contains(self, v: D) -> BoolWhether v is in the set.
- cost: O(1)
- traps: when
vis outsideD
Examples:
var s = SparseSet<0..5>(); s.add(3); s.contains(3) and not s.contains(2)
SparseSet.add
fn add(mut self, v: D) -> BoolAdd v at the end of the dense order. Returns true when v was absent, false when it
was present (and nothing changes).
- cost: O(1)
- traps: when
vis outsideD
Examples:
var s = SparseSet<0..5>(); s.add(3) and not s.add(3)
SparseSet.remove
fn remove(mut self, v: D) -> BoolRemove v, moving the last element of the dense order into its slot. Returns true when v
was present, false when it was absent (and nothing changes).
- cost: O(1)
- traps: when
vis outsideD
Examples:
var s = SparseSet<0..5>(); s.add(3); s.add(1); s.add(4); s.remove(3); s.each().collect() == [4, 1]
SparseSet.clear
fn clear(mut self)Remove every element by resetting the length; the sparse table is not touched.
- cost: O(1)
- traps: never
Examples:
var s = SparseSet<0..5>(); s.add(3); s.clear(); s.is_empty and not s.contains(3)
SparseSet.each
fn each(self) -> yields DEvery element, in dense order: insertion order, except that each remove moved the then-last
element into the removed one's slot.
- cost: O(len)
- empty: yields nothing for an empty set
- order: dense order (insertion order adjusted by removals, as above)
- traps: never
Examples:
var s = SparseSet<0..5>(); s.add(2); s.add(0); s.add(4); s.each().collect() == [2, 0, 4]
Id
pub struct Id<T>(rawCompact 4-byte typed handle into an Arena<T>.
Arena
pub struct Arena<T>Contiguous pool allocator returning compact 4-byte Id<T> handles (for user trees, tries, and persistent nodes).
Arena.new
fn new(cap: Int = 0) -> Arena<T>An empty arena with room for cap nodes before it reallocates.
- cost: O(cap)
- traps: when
cap < 0
Examples:
Arena<Int>(cap: 8).is_empty
Arena.len
fn len(self) -> IntThe number of nodes allocated since creation or the last clear; valid handles have raw
values 0..len.
- cost: O(1)
- traps: never
Examples:
var a = Arena<Int>(); a.alloc(5); a.alloc(6); a.len == 2
Arena.is_empty
fn is_empty(self) -> BoolWhether no node is allocated; len == 0.
- cost: O(1)
- traps: never
Examples:
var a = Arena<Int>(); a.alloc(5); a.clear(); a.is_empty
Arena.alloc
fn alloc(mut self, x: T) -> Id<T>Store x as a new node and return its handle; handles are issued in order 0, 1, 2, ....
- cost: O(1) amortized
- traps: when the arena already holds
2_000_000_001nodes
Examples:
var a = Arena<Str>(); a.alloc("p"); a.alloc("q") == Id<Str>(1)
Arena.get
fn get(self, id: Id<T>) -> TThe node behind id; also arena[id].
it is below len; it reads whatever node now holds that slot
- cost: O(1)
- traps: when
idis not belowlen. A handle issued before aclearis not detected while
Examples:
var a = Arena<Int>(); let i = a.alloc(5); a.alloc(6); a.get(i) == 5
Arena.set
fn set(mut self, id: Id<T>, x: T)Overwrite the node behind id with x; also arena[id] = x.
- cost: O(1)
- traps: when
idis not belowlen(stale handles as inget)
Examples:
var a = Arena<Int>(); let i = a.alloc(5); a.set(i, 9); a[i] == 9
Arena.reserve
fn reserve(mut self, cap: Int)Allocate room for at least cap nodes in total; changes no handle or node.
- cost: O(cap)
- traps: when
cap < 0
Examples:
var a = Arena<Int>(); a.reserve(100); a.alloc(1); a.len == 1
Arena.clear
fn clear(mut self)Drop every node, so the next alloc returns handle 0 again. Every handle issued before is
invalidated.
- cost: O(1)
- traps: never
Examples:
var a = Arena<Int>(); a.alloc(5); a.clear(); a.alloc(7) == Id<Int>(0)