MkSTSequence functorfunctor MkSTSequence (structure Seq :
SEQUENCE) :>
ST_SEQUENCE
where Seq = Seq
Implements single-threated sequences via a state ref and
history. If the state is CUR a, then the single-threaded
sequence is current and a can be accessed immediately. Otherwise, if the
state is MOD, the single-threaded sequence needs to be
reconstructed from history — that is, by sequentially applying every
update to the original sequence from which the single-threaded sequence was
created.
ST_SEQUENCE Cost Specifications| Work | Span | |
nth S iupdate (S,(i,x))
|
O(1) | O(1) |
inject (S,U) |
O(|U|) | O(1) |
The following assumes Seq =
ArraySequence. For another choice
of Seq, refer directly to the implementations of
fromSeq and toSeq.
| Work | Span | |
fromSeq StoSeq S
|
O(|S|) | O(1) |