Skip to Content
ReferenceLibrary

segtree

The segtree module.

Generated from spec/std/segtree.cp by cpl doc --format json.

SegTree

pub struct SegTree<D, T, F = Int>(m: Monoid<T>)

Point update and range fold. The operation is a bare operator (+, *, ^, &, |, min, max, gcd) or your own Monoid(id, op): SegTree<V, Int>(max, a), SegTree<V, Int>(+), SegTree<V, Run>(Monoid(Run.empty, Run.join), a). set and fold are O(log n), and so are right_while and left_while; memory is 2 * bit_ceil(n) values. The fold keeps the order of the positions, so non-commutative operations work.

Source

SegTree.source

source: ?(D -> T)

What each position holds, for a tree built with of.

Source

SegTree.new

fn new<M, A>(op: ?M = None, a: ?[D]T = None, fill: ?T = None, act: A = NoAction(), over: ?Range<Int> = None) -> SegTree<D, T, F>

A tree over D folding with op: built from a, filled with fill, or holding the identity everywhere when neither is given. op is a bare operator (+, *, ^, &, |, min, max, gcd) or a Monoid(id, op).

act: adds range tags (apply, apply_all); with act: and no op the tree applies tags and reads points only. When the tag monoid is Commutative the tree skips push-down, which changes speed, never answers. over: lo..hi covers a huge Int range instead, making nodes on first touch; positions outside the touched ones hold fill or the identity.

  • cost: O(|D|); O(1) with over:
  • empty: an empty D gives a tree whose every fold is the identity
  • order: positions keep the domain D of a
  • traps: when both a and fill are given, or over: is given together with a

Examples:

  • SegTree(+, [1, 2, 3]).all == 6
  • SegTree<0..4, Int>(max, fill: 5).fold(1..3) == 5
  • SegTree<0..4, Int>(+).all == 0
  • var s = SegTree<Int, Int>(+, over: 0..1_000_000_000); s.set(999_999_999, 4); s.all == 4

Source

SegTree.build

fn build(m: Monoid<T>, a: ?[D]T, fill: ?T) -> SegTree<D, T, F>

Source

SegTree.build_lazy

fn build_lazy(m: Monoid<T>, a: ?[D]T, fill: ?T, resolved: Action<T, F>) -> SegTree<D, T, F>

Source

SegTree.put

fn put(self, p: Int, f: F)

Source

SegTree.push

fn push(self, p: Int)

Source

SegTree.open

fn open(self, l: Int, h: Int)

Source

SegTree.pull_node

fn pull_node(self, p: Int)

Source

SegTree.apply

fn apply(mut self, r: Range<D>, f: F)

Apply tag f to every position of r: each fold over r then sees the values with f applied, through the action given to act:.

  • cost: O(log |D|)
  • empty: changes nothing
  • traps: when a non-empty r reaches outside D

Examples:

  • var s = SegTree(+, [1, 2, 3], act: add); s.apply(0..2, 10); s.all == 26
  • var s = SegTree(max, [1, 2, 3], act: add); s.apply(0..1, 5); s.all == 6

Source

SegTree.apply_all

fn apply_all(mut self, f: F)

Apply tag f to every position; apply(D.all, f).

  • cost: O(1) amortized when the tags commute, else O(|D|)
  • empty: changes nothing for an empty D
  • traps: never

Examples:

  • var s = SegTree(+, [1, 2, 3], act: add); s.apply_all(1); s.all == 9

Source

SegTree.fold

fn fold(self, r: Range<D>) -> T

The fold of the values in r, left to right: op(op(a[l], a[l + 1]), ...).

  • cost: O(log |D|)
  • empty: the identity
  • traps: when a non-empty r reaches outside D

Examples:

  • var s = SegTree(+, [1, 2, 3], act: add); s.apply(1..3, 1); s.fold(1..3) == 7

Source

SegTree.right_while

fn right_while(self, from: Cut<D>, ok: T -> Bool) -> Cut<D>

The last cut d at or right of from such that ok(fold(from..d)) holds. ok must be monotone (once false it stays false as d moves right) and true on the identity, so from itself always qualifies. Replaces max_right.

  • cost: O(log |D|)
  • ties: the rightmost qualifying cut
  • traps: when ok(identity) is false

Examples:

  • SegTree(+, [1, 2, 3, 4]).right_while((0..0).r, s => s <= 3) == (0..2).r
  • SegTree(+, [1, 2, 3, 4]).right_while((0..1).r, s => s <= 5) == (0..3).r
  • SegTree(+, [1, 2, 3, 4]).right_while((0..0).r, s => s <= 100) == (0..4).r

Source

SegTree.left_while

fn left_while(self, to: Cut<D>, ok: T -> Bool) -> Cut<D>

The first cut d at or left of to such that ok(fold(d..to)) holds. ok must be monotone (once false it stays false as d moves left) and true on the identity, so to itself always qualifies. Replaces min_left.

  • cost: O(log |D|)
  • ties: the leftmost qualifying cut
  • traps: when ok(identity) is false

Examples:

  • SegTree(+, [1, 2, 3, 4]).left_while((0..4).r, s => s <= 7) == (0..2).r
  • SegTree(+, [1, 2, 3, 4]).left_while((0..4).r, s => s <= 3) == (0..4).r

Source

SegTree.of

fn of<M>(op: M, f: D -> T) -> SegTree<D, T>

A tree whose position i holds f(i). f is kept: when something it reads changes, refresh(i) recomputes position i, so the formula is written once instead of at every update site.

  • cost: O(|D|), calling f once per position in key order
  • empty: an empty D gives a tree whose every fold is the identity
  • order: position i holds f(i)
  • traps: never

Examples:

  • let w = [1, 2, 3]; SegTree<0..3, Int>.of(+, i => w[i] * 2).all == 12

Source

SegTree.refresh

fn refresh(mut self, i: D)

Recompute position i as f(i) with the formula given to of, and update its ancestors.

  • cost: O(log |D|) plus one call of f
  • traps: when i is outside D, or the tree was not built with of

Examples:

  • var w = [1, 2, 3]; var s = SegTree<0..3, Int>.of(+, i => w[i]); w[1] = 10; s.refresh(1); s.all == 14

Source

SegTree.get

fn get(self, i: D) -> T

The value at position i, with every tag applied.

  • cost: O(1); O(log |D|) on a tree with act:
  • traps: when i is outside D

Examples:

  • SegTree(+, [4, 5, 6]).get(1) == 5
  • var s = SegTree(act: assign, [1, 2, 3]); s.apply(0..2, Some(9)); s.get(1) == 9

Source

SegTree.set

fn set(mut self, i: D, x: T)

Make position i hold x, replacing any tags applied to it, and update its ancestors.

  • cost: O(log |D|)
  • traps: when i is outside D

Examples:

  • var s = SegTree(+, [1, 2, 3]); s.set(0, 10); s.all == 15

Source

SegTree.at

fn at(mut self, i: D) -> lends mut T

Position i as a writable place: st.at(i) += x, st.at(i) max= x. The ancestors are updated when the write ends, so each use is one set; read with get instead.

  • cost: O(log |D|) per write
  • traps: when i is outside D

Examples:

  • var s = SegTree(+, [1, 2, 3]); s.at(0) += 5; s.all == 11

Source

SegTree.pull

fn pull(mut self, i: D)

Source

SegTree.update

fn update(mut self, i: D, f: T -> T)

Replace the value v at i with f(v); set(i, f(get(i))) in one walk.

  • cost: O(log |D|) plus one call of f
  • traps: when i is outside D

Examples:

  • var s = SegTree(+, [1, 2, 3]); s.update(2, x => x * 10); s.all == 33

Source

SegTree.all

fn all(self) -> T

The fold of every position, left to right.

  • cost: O(1)
  • empty: the identity for an empty D
  • traps: never

Examples:

  • SegTree(max, [3, 9, 4]).all == 9

Source

SegTree.monoid

fn monoid(self) -> Monoid<T>

The operation the tree folds with, as its (id, op) pair.

  • cost: O(1)
  • traps: never

Examples:

  • SegTree(+, [1]).monoid.id == 0

Source

SegTree.try_fold

fn try_fold(self, r: Range<D>) -> ?T

The fold of r, or None when r is empty; for operations whose identity is only a sentinel.

  • cost: O(log |D|)
  • empty: None
  • traps: when a non-empty r reaches outside D

Examples:

  • SegTree(+, [1, 2]).try_fold(0..2) == Some(3)
  • SegTree(+, [1, 2]).try_fold(1..1) == None

Source

SegTree.clear

fn clear(mut self, fill: ?T = None)

Make every position hold fill, or the identity when fill is None, dropping all pending tags; the storage is reused. A tree built with of keeps its formula.

  • cost: O(|D|)
  • empty: nothing to reset for an empty D
  • traps: never

Examples:

  • var s = SegTree(+, [1, 2, 3]); s.clear(); s.all == 0
  • var s = SegTree(+, [1, 2, 3]); s.clear(fill: 2); s.all == 6

Source

SegTree.walk

fn walk(self, r: Range<D>) -> yields T

The values of the canonical nodes that exactly cover r: the maximal aligned blocks of the tree's bit_ceil(|D|) leaves inside r. Their fold, left to right, is fold(r).

  • cost: O(log |D|)
  • empty: yields nothing
  • order: left to right; at most 2 * log2(bit_ceil(|D|)) values
  • traps: when a non-empty r reaches outside D

Examples:

  • SegTree(+, [1, 2, 3, 4]).walk(0..3).collect() == [3, 3]
  • SegTree(+, [1, 2, 3, 4]).walk(1..4).collect() == [2, 7]

Source

MergeSortTree

pub struct MergeSortTree<D, T>

Static merge-sort tree for orthogonal 2D range counting over [D]T. Build in O(n log n) time and memory; answer value-range counts over any Range<D> in O(log^2 n).

Source

MergeSortTree.new

fn new(a: [D]T) -> MergeSortTree<D, T>

A static tree over a whose nodes hold their values sorted, for counting values in a range.

  • cost: O(|D| log |D|) time and memory
  • empty: an empty a gives a tree where every count is 0
  • order: positions keep the domain D of a
  • traps: never

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_lt(0..5, 3) == 2

Source

MergeSortTree.lower_idx

fn lower_idx(self, u: Int, x: T) -> Int

Source

MergeSortTree.upper_idx

fn upper_idx(self, u: Int, x: T) -> Int

Source

MergeSortTree.count_lt

fn count_lt(self, r: Range<D>, x: T) -> Int

The number of positions in r whose value is < x.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_lt(0..5, 3) == 2

Source

MergeSortTree.count_le

fn count_le(self, r: Range<D>, x: T) -> Int

The number of positions in r whose value is <= x.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_le(0..5, 3) == 3

Source

MergeSortTree.count_in

fn count_in(self, r: Range<D>, lo_v: T, hi_v: T) -> Int

The number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_in(1..4, 1, 4) == 3
  • MergeSortTree([3, 1, 4, 1, 5]).count_in(0..5, 4, 3) == 0

Source

MergeSortTree.count_gt

fn count_gt(self, r: Range<D>, x: T) -> Int

The number of positions in r whose value is > x.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_gt(0..5, 3) == 2

Source

MergeSortTree.count_ge

fn count_ge(self, r: Range<D>, x: T) -> Int

The number of positions in r whose value is >= x.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).count_ge(0..5, 4) == 2

Source

MergeSortTree.first_ge

fn first_ge(self, r: Range<D>, x: T) -> ?T

The smallest value in r that is >= x, or None.

  • cost: O(log^2 |D|)
  • empty: None
  • ties: equal values are interchangeable; the value is returned, not a position
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).first_ge(0..3, 2) == Some(3)
  • MergeSortTree([3, 1, 4, 1, 5]).first_ge(0..3, 5) == None

Source

MergeSortTree.last_le

fn last_le(self, r: Range<D>, x: T) -> ?T

The largest value in r that is <= x, or None.

  • cost: O(log^2 |D|)
  • empty: None
  • ties: equal values are interchangeable; the value is returned, not a position
  • traps: when a non-empty r reaches outside D

Examples:

  • MergeSortTree([3, 1, 4, 1, 5]).last_le(2..5, 3) == Some(1)
  • MergeSortTree([3, 1, 4, 1, 5]).last_le(2..5, 0) == None

Source

SegTree2D

pub struct SegTree2D<R, C, T>(m: Monoid<T>)

O(|R| * |C|) space. Iterative 2D segment tree: point update and rectangle fold in O(log |R| * log |C|).

Source

SegTree2D.fold_row

fn fold_row(self, i: Int, cl: Int, ch: Int) -> T

Source

SegTree2D.new

fn new<M>(op: M, a: ?[R, C]T = None, fill: ?T = None) -> SegTree2D<R, C, T>

A grid tree over (R, C) folding with op: built from a, filled with fill, or holding the identity everywhere. op must be Commutative, since a rectangle is folded in row-blocks and column-blocks rather than in one order.

  • cost: O(|R| * |C|)
  • empty: an empty R or C gives a tree whose every fold is the identity
  • order: cells keep the domains R and C of a
  • traps: when both a and fill are given

Examples:

  • SegTree2D<0..3, 0..3, Int>(+, fill: 1).all == 9

Source

SegTree2D.get

fn get(self, r: R, c: C) -> T

The value of cell (r, c).

  • cost: O(1)
  • traps: when r is outside R or c is outside C

Examples:

  • var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.set(1, 2, 7); g.get(1, 2) == 7

Source

SegTree2D.set

fn set(mut self, r: R, c: C, x: T)

Make cell (r, c) hold x.

  • cost: O(log |R| * log |C|)
  • traps: when r is outside R or c is outside C

Examples:

  • var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.set(0, 0, 5); g.all == 13

Source

SegTree2D.update

fn update(mut self, r: R, c: C, f: T -> T)

Replace the value v of cell (r, c) with f(v).

  • cost: O(log |R| * log |C|) plus one call of f
  • traps: when r is outside R or c is outside C

Examples:

  • var g = SegTree2D<0..3, 0..3, Int>(+, fill: 1); g.update(2, 2, x => x + 1); g.all == 10

Source

SegTree2D.fold

fn fold(self, rows: Range<R>, cols: Range<C>) -> T

The fold of every cell in rows rows and columns cols.

  • cost: O(log |R| * log |C|)
  • empty: the identity when rows or cols is empty
  • traps: when a non-empty range reaches outside its domain

Examples:

  • SegTree2D<0..3, 0..3, Int>(+, fill: 1).fold(0..2, 1..3) == 4
  • SegTree2D<0..3, 0..3, Int>(+, fill: 1).fold(0..2, 1..1) == 0

Source

SegTree2D.all

fn all(self) -> T

The fold of every cell.

  • cost: O(1)
  • empty: the identity for an empty grid
  • traps: never

Examples:

  • var g = SegTree2D<0..2, 0..2, Int>(max, fill: 0); g.set(1, 0, 8); g.all == 8

Source

WaveletMatrix

pub struct WaveletMatrix<D>

O(|D| log V) build and memory. Wavelet matrix over non-negative integer values: O(log V) range k-th smallest, frequency, value-range count, predecessor/successor, and quantile sum.

Source

WaveletMatrix.ones

fn ones(self, l: Int, i: Int) -> Int

Source

WaveletMatrix.below

fn below(self, lo0: Int, hi0: Int, x: Int) -> Int

Source

WaveletMatrix.new

fn new(a: [D]Int) -> WaveletMatrix<D>

A wavelet matrix over the non-negative values of a, with one bit level per bit of the largest value (V below is that value plus one).

  • cost: O(|D| log V) time and memory
  • empty: an empty a gives a matrix where every count is 0
  • order: positions keep the domain D of a
  • traps: when some value is negative

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 2) == Some(3)

Source

WaveletMatrix.kth

fn kth(self, r: Range<D>, k: Int) -> ?Int

The k-th smallest value in r, counting from 0 and with repeats, or None when k >= r.len.

  • cost: O(log V)
  • empty: None
  • ties: equal values are counted once each
  • traps: when k < 0, or a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 0) == Some(1)
  • WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 2) == Some(3)
  • WaveletMatrix([3, 1, 4, 1, 5]).kth(0..5, 5) == None

Source

WaveletMatrix.rank

fn rank(self, r: Range<D>, x: Int) -> Int

The number of positions in r holding exactly x; 0 for any x outside 0..V.

  • cost: O(log V)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).rank(0..5, 1) == 2

Source

WaveletMatrix.count_lt

fn count_lt(self, r: Range<D>, x: Int) -> Int

The number of positions in r whose value is < x.

  • cost: O(log V)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).count_lt(0..5, 4) == 3

Source

WaveletMatrix.count_in

fn count_in(self, r: Range<D>, lo_v: Int, hi_v: Int) -> Int

The number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.

  • cost: O(log V)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).count_in(0..5, 1, 3) == 3

Source

WaveletMatrix.prev_val

fn prev_val(self, r: Range<D>, x: Int) -> ?Int

The largest value in r that is < x, or None.

  • cost: O(log V)
  • empty: None
  • ties: equal values are interchangeable; the value is returned, not a position
  • traps: when a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).prev_val(0..5, 3) == Some(1)
  • WaveletMatrix([3, 1, 4, 1, 5]).prev_val(0..5, 1) == None

Source

WaveletMatrix.next_val

fn next_val(self, r: Range<D>, x: Int) -> ?Int

The smallest value in r that is > x, or None.

  • cost: O(log V)
  • empty: None
  • ties: equal values are interchangeable; the value is returned, not a position
  • traps: when a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).next_val(0..5, 3) == Some(4)
  • WaveletMatrix([3, 1, 4, 1, 5]).next_val(0..5, 5) == None

Source

WaveletMatrix.quantile_sum

fn quantile_sum(self, r: Range<D>, k: Int) -> Int

The sum of the k smallest values in r, with repeats.

  • cost: O(log V)
  • empty: 0 (only k == 0 is allowed)
  • ties: equal values are counted once each
  • traps: when k is outside 0..=r.len, or a non-empty r reaches outside D

Examples:

  • WaveletMatrix([3, 1, 4, 1, 5]).quantile_sum(0..5, 3) == 5
  • WaveletMatrix([3, 1, 4, 1, 5]).quantile_sum(1..3, 0) == 0

Source

DynamicOrderTree

pub struct DynamicOrderTree<D, T>

O(|D| log^2 |D|) space. Dynamic point-update + 2D range value-count and k-th structure (Fenwick of order trees) over [D]T.

Source

DynamicOrderTree.bump

fn bump(mut self, i: Int, x: T, put: Bool)

Source

DynamicOrderTree.below

fn below(self, end: Int, x: T, le: Bool) -> Int

Source

DynamicOrderTree.span_count

fn span_count(self, r: Range<D>, x: T, le: Bool) -> Int

Source

DynamicOrderTree.new

fn new(a: [D]T) -> DynamicOrderTree<D, T>

A structure over a answering value counts and order statistics on ranges while positions are reassigned.

  • cost: O(|D| log^2 |D|) time and memory
  • empty: an empty a gives a tree where every count is 0
  • order: positions keep the domain D of a
  • traps: never

Examples:

  • DynamicOrderTree([3, 1, 4]).count_lt(0..3, 4) == 2

Source

DynamicOrderTree.set

fn set(mut self, i: D, x: T)

Make position i hold x.

  • cost: O(log^2 |D|)
  • traps: when i is outside D

Examples:

  • var t = DynamicOrderTree([3, 1, 4]); t.set(0, 0); t.kth(0..3, 0) == Some(0)

Source

DynamicOrderTree.get

fn get(self, i: D) -> T

The value at position i.

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

Examples:

  • var t = DynamicOrderTree([3, 1, 4]); t.set(2, 9); t.get(2) == 9

Source

DynamicOrderTree.count_lt

fn count_lt(self, r: Range<D>, x: T) -> Int

The number of positions in r whose value is < x.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • DynamicOrderTree([3, 1, 4]).count_lt(1..3, 4) == 1

Source

DynamicOrderTree.count_in

fn count_in(self, r: Range<D>, lo_v: T, hi_v: T) -> Int

The number of positions in r whose value lies in lo_v..=hi_v; 0 when lo_v > hi_v.

  • cost: O(log^2 |D|)
  • empty: 0
  • traps: when a non-empty r reaches outside D

Examples:

  • DynamicOrderTree([3, 1, 4]).count_in(0..3, 1, 3) == 2

Source

DynamicOrderTree.kth

fn kth(self, r: Range<D>, k: Int) -> ?T

The k-th smallest value in r, counting from 0 and with repeats, or None when k >= r.len.

  • cost: O(log^2 |D|)
  • empty: None
  • ties: equal values are counted once each
  • traps: when k < 0, or a non-empty r reaches outside D

Examples:

  • DynamicOrderTree([3, 1, 4]).kth(0..3, 1) == Some(3)
  • DynamicOrderTree([3, 1, 4]).kth(0..3, 3) == None

Source

MergeSeg

pub struct MergeSeg<D>

O(q log |D|) space. Mergeable min-ordered set over domain D for lazily pruned minimum-alive queries (MergeSeg.singleton, merge, first_alive).

Source

MergeSeg.push_raw

fn push_raw(mut self, x: D)

Source

MergeSeg.pop_min

fn pop_min(mut self)

Source

MergeSeg.singleton

fn singleton(x: D) -> MergeSeg<D>

A set of positions of D holding only x, stored as a sparse binary tree over D.

  • cost: O(log |D|)
  • traps: when x is outside D

Examples:

  • MergeSeg<0..10>.singleton(3).first_alive(x => true) == Some(3)

Source

MergeSeg.merge

fn merge(self, other: MergeSeg<D>) -> MergeSeg<D>

The union of self and other. The result reuses the nodes of both, so neither input may be used afterwards.

  • cost: O(log |D|) amortized per node absorbed
  • traps: never

Examples:

  • var m = MergeSeg<0..10>.singleton(7).merge(MergeSeg<0..10>.singleton(3)); m.first_alive(x => true) == Some(3)

Source

MergeSeg.first_alive

fn first_alive(mut self, alive: D -> Bool) -> ?D

The smallest position x in the set with alive(x), or None. Every position found dead on the way is removed for good, so alive must be monotone over time: a position never comes back to life.

  • cost: O(log |D|) amortized
  • ties: the smallest position in key order
  • traps: never

Examples:

  • var m = MergeSeg<0..10>.singleton(3).merge(MergeSeg<0..10>.singleton(7)); m.first_alive(x => x > 5) == Some(7)
  • var m = MergeSeg<0..10>.singleton(3).merge(MergeSeg<0..10>.singleton(7)); m.first_alive(x => x > 5); m.first_alive(x => true) == Some(7)

Source

On this page