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 TimeStepOne step in a TimeTree DFS traversal:
Apply(id): apply eventtt.event(id)on entry to a segment-tree node.Query(t): answer time slottat a leaf.Undo: revert the most recently applied event in LIFO order on exit.
TimeStep.Apply
Apply(id: Int)TimeStep.Query
Query(t: Int)TimeStep.Undo
UndoTimeTree
pub struct TimeTree<E>Offline segment tree over time [0, q) holding events of type E active on half-open
intervals [lo, hi).
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
TimeTree.link
fn link(mut self, u: Int, ev: E)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 < 0orhi > qon a non-empty interval
Examples:
var tt = TimeTree<Str>(2); tt.add_interval(0, 2, "e"); tt.steps().len == 4
TimeTree.event
fn event(self, id: Int) -> EThe 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
idis not an id that someApplystep carries
Examples:
var tt = TimeTree<Str>(2); tt.add_interval(0, 2, "e"); tt.event(0) == "e"
TimeTree.emit_dfs
fn emit_dfs(self, u: Int, nl: Int, nr: Int, mut out: List<TimeStep>)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
mscheduled intervals - empty:
[]whenq == 0 - order: DFS order;
Query(t)appears once pert, in increasingt - 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]
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>, )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
mscheduled intervals, O(log q) extra stack - empty:
[]whenq == 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]
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
rreaches outside0..q
Examples:
var tt = TimeTree<Str>(3); tt.add_range(1..3, "e"); tt.steps().len == 7
TimeTree.walk
fn walk(self) -> yields TimeStepThe 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)]