Skip to Content
ReferenceLibrary

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).

Source

Marks.new

fn new() -> Marks<D>

An empty mark set over D, with its stamp array allocated once.

  • cost: O(|D|)
  • empty: an empty D gives a set that can never hold a mark
  • traps: never

Examples:

  • Marks<0..5>().is_empty

Source

Marks.add

fn add(mut self, v: D) -> Bool

Mark v. Returns true when v was unmarked, false when it was already marked (and nothing changes).

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = Marks<0..5>(); m.add(2) and not m.add(2)

Source

Marks.remove

fn remove(mut self, v: D) -> Bool

Unmark v. Returns true when v was marked, false when it was not (and nothing changes).

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = Marks<0..5>(); m.add(2); m.remove(2) and not m.remove(2)

Source

Marks.contains

fn contains(self, v: D) -> Bool

Whether v is marked; also spelled v in m.

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = Marks<0..5>(); m.add(1); m.contains(1) and not m.contains(0)

Source

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)

Source

Marks.len

fn len(self) -> Int

The 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

Source

Marks.is_empty

fn is_empty(self) -> Bool

Whether 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

Source

MarkMap

pub struct MarkMap<D, T>

Epoch-stamped map over domain D with O(1) get, set, contains, remove, and clear().

Source

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 D gives a map that can never hold an entry
  • traps: never

Examples:

  • MarkMap<0..5, Int>(0).is_empty

Source

MarkMap.len

fn len(self) -> Int

The 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

Source

MarkMap.is_empty

fn is_empty(self) -> Bool

Whether 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

Source

MarkMap.contains

fn contains(self, v: D) -> Bool

Whether v has a value. A key set to default_val is present.

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = MarkMap<0..5, Int>(0); m.set(2, 0); m.contains(2) and not m.contains(3)

Source

MarkMap.get

fn get(self, v: D) -> ?T

The value at v, or None when v is absent.

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.get(2) == Some(9) and m.get(3) == None

Source

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 v is outside D

Examples:

  • var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.set(2, 4); m.get(2) == Some(4)

Source

MarkMap.remove

fn remove(mut self, v: D) -> ?T

Remove v and return the value it had, or None (and change nothing) when it was absent.

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var m = MarkMap<0..5, Int>(0); m.set(2, 9); m.remove(2) == Some(9) and m.remove(2) == None

Source

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

Source

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).

Source

Interner.new

fn new() -> Interner<K>

An empty interner.

  • cost: O(1)
  • traps: never

Examples:

  • Interner<Str>().is_empty

Source

Interner.len

fn len(self) -> Int

The 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

Source

Interner.is_empty

fn is_empty(self) -> Bool

Whether 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

Source

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

Source

Interner.id

fn id(mut self, k: K) -> Int

The 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

Source

Interner.get

fn get(self, k: K) -> ?Int

The 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

Source

Interner.key

fn key(self, i: Int) -> K

The key whose id is i; the inverse of id.

  • cost: O(1)
  • traps: when i is outside 0..len

Examples:

  • var t = Interner<Str>(); t.id("x"); t.id("y"); t.key(1) == "y"

Source

Interner.contains

fn contains(self, k: K) -> Bool

Whether 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)

Source

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

Source

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.

Source

SparseSet.new

fn new() -> SparseSet<D>

An empty sparse set over D.

  • cost: O(|D|)
  • empty: an empty D gives a set that can never hold an element
  • traps: never

Examples:

  • SparseSet<0..5>().is_empty

Source

SparseSet.len

fn len(self) -> Int

The 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

Source

SparseSet.is_empty

fn is_empty(self) -> Bool

Whether 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

Source

SparseSet.contains

fn contains(self, v: D) -> Bool

Whether v is in the set.

  • cost: O(1)
  • traps: when v is outside D

Examples:

  • var s = SparseSet<0..5>(); s.add(3); s.contains(3) and not s.contains(2)

Source

SparseSet.add

fn add(mut self, v: D) -> Bool

Add 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 v is outside D

Examples:

  • var s = SparseSet<0..5>(); s.add(3) and not s.add(3)

Source

SparseSet.remove

fn remove(mut self, v: D) -> Bool

Remove 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 v is outside D

Examples:

  • var s = SparseSet<0..5>(); s.add(3); s.add(1); s.add(4); s.remove(3); s.each().collect() == [4, 1]

Source

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)

Source

SparseSet.each

fn each(self) -> yields D

Every 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]

Source

Id

pub struct Id<T>(raw

Compact 4-byte typed handle into an Arena<T>.

Source

Arena

pub struct Arena<T>

Contiguous pool allocator returning compact 4-byte Id<T> handles (for user trees, tries, and persistent nodes).

Source

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

Source

Arena.len

fn len(self) -> Int

The 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

Source

Arena.is_empty

fn is_empty(self) -> Bool

Whether no node is allocated; len == 0.

  • cost: O(1)
  • traps: never

Examples:

  • var a = Arena<Int>(); a.alloc(5); a.clear(); a.is_empty

Source

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_001 nodes

Examples:

  • var a = Arena<Str>(); a.alloc("p"); a.alloc("q") == Id<Str>(1)

Source

Arena.get

fn get(self, id: Id<T>) -> T

The node behind id; also arena[id].

it is below len; it reads whatever node now holds that slot

  • cost: O(1)
  • traps: when id is not below len. A handle issued before a clear is not detected while

Examples:

  • var a = Arena<Int>(); let i = a.alloc(5); a.alloc(6); a.get(i) == 5

Source

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 id is not below len (stale handles as in get)

Examples:

  • var a = Arena<Int>(); let i = a.alloc(5); a.set(i, 9); a[i] == 9

Source

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

Source

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)

Source

On this page