Skip to Content
ReferenceLibrary

timetree

One step in a TimeTree DFS traversal: - Apply(id): apply event tt.event(id) on entry to a segment-tree node.

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

TimeStep

pub enum TimeStep

One step in a TimeTree DFS traversal:

  • Apply(id): apply event tt.event(id) on entry to a segment-tree node.
  • Query(t): answer time slot t at a leaf.
  • Undo: revert the most recently applied event in LIFO order on exit.

Source

TimeStep.Apply

Apply(id: Int)

Source

TimeStep.Query

Query(t: Int)

Source

TimeStep.Undo

Undo

Source

TimeTree

pub struct TimeTree<E>

Offline segment tree over time [0, q) holding events of type E active on half-open intervals [lo, hi).

Source

TimeTree.new

fn new(q: Int) -> TimeTree<E>

An empty timeline of q time slots 0..q, with no events scheduled yet.

  • cost: O(q) time and memory
  • traps: when q < 0

Examples:

  • TimeTree<Int>(2).steps().len == 2

Source

fn link(mut self, u: Int, ev: E)

Source

TimeTree.add_interval

fn add_interval(mut self, lo: Int, hi: Int, ev: E)

Schedule ev to be active at every time slot in lo..hi (half-open). The interval is stored on the O(log q) segment-tree nodes that cover it, one copy of ev on each. An empty interval (lo >= hi) schedules nothing.

  • cost: O(log q)
  • traps: when lo < 0 or hi > q on a non-empty interval

Examples:

  • var tt = TimeTree<Str>(2); tt.add_interval(0, 2, "e"); tt.steps().len == 4

Source

TimeTree.event

fn event(self, id: Int) -> E

The event carried by TimeStep.Apply(id). Ids are 0, 1, 2, ... in the order the node copies were stored by add_interval / add_range; read them from the steps, never compute them.

  • cost: O(1)
  • traps: when id is not an id that some Apply step carries

Examples:

  • var tt = TimeTree<Str>(2); tt.add_interval(0, 2, "e"); tt.event(0) == "e"

Source

TimeTree.emit_dfs

fn emit_dfs(self, u: Int, nl: Int, nr: Int, mut out: List<TimeStep>)

Source

TimeTree.steps

fn steps(self) -> List<TimeStep>

The whole depth-first walk over 0..q as a list. Entering a node emits one Apply(id) per event stored there, in scheduling order; a leaf t then emits Query(t); leaving the node emits one Undo per Apply it emitted, so undos match applies in LIFO order. Children are visited left (earlier times) before right.

see: run, which walks the same order without building the list

  • cost: O(q + m log q) time and memory for m scheduled intervals
  • empty: [] when q == 0
  • order: DFS order; Query(t) appears once per t, in increasing t
  • traps: never

Examples:

  • TimeTree<Int>(2).steps() == [TimeStep.Query(0), TimeStep.Query(1)]
  • var tt = TimeTree<Str>(2); tt.add_interval(0, 2, "e"); tt.steps() == [TimeStep.Apply(0), TimeStep.Query(0), TimeStep.Query(1), TimeStep.Undo]

Source

TimeTree.run_node

fn run_node<M, R>( self, u: Int, nl: Int, nr: Int, mark: () -> M, apply: E -> (), answer: Int -> R, undo: M -> (), mut out: List<R>, )

Source

TimeTree.run

fn run<M, R>( self, mark: () -> M, apply: E -> (), answer: Int -> R, undo: M -> (), ) -> List<R>

Walk the same order as steps with callbacks instead of a list. On entering a node that holds at least one event it calls mark() once, then apply(ev) for each event there in scheduling order; at each leaf t it calls answer(t); on leaving such a node it calls undo(m) once with the value its mark() returned. Nodes with no events call neither.

  • cost: O(q + m log q) callback calls for m scheduled intervals, O(log q) extra stack
  • empty: [] when q == 0
  • order: [answer(0), ..., answer(q - 1)], indexed by time
  • traps: never (callbacks may trap)

Examples:

  • TimeTree<Int>(2).run(mark: () => 0, apply: e => (), answer: t => t * 10, undo: m => ()) == [0, 10]

Source

TimeTree.add_range

fn add_range(mut self, r: Range<Int>, ev: E)

Schedule ev to be active at every time slot in r; add_interval with the range form. An empty r schedules nothing.

  • cost: O(log q)
  • empty: schedules nothing
  • traps: when a non-empty r reaches outside 0..q

Examples:

  • var tt = TimeTree<Str>(3); tt.add_range(1..3, "e"); tt.steps().len == 7

Source

TimeTree.walk

fn walk(self) -> yields TimeStep

The steps of steps, yielded one at a time without building the list.

  • cost: O(1) amortized per step, O(log q) extra stack
  • order: the same DFS order as steps
  • traps: never

Examples:

  • TimeTree<Int>(2).walk().collect() == [TimeStep.Query(0), TimeStep.Query(1)]

Source

On this page