Module Sek.Ephemeral
The submodule Ephemeral
, also available under the name E
, offers an implementation of ephemeral (mutable) sequences. Please follow the link for details.
type 'a t
A sequence
s
of type'a t
is a mutable data structure which represents a mathematical sequence of elements of type'a
.
Construction
val create : 'a -> 'a t
create default
constructs and returns a new empty sequence. The default valuedefault
is used to fill empty array slots.Time complexity: O(K).
val make : 'a -> length -> 'a -> 'a t
make default n v
constructs and returns a fresh sequence whose length isn
and which consists ofn
copies of the valuev
. It is equivalent toof_array default (Array.make n v)
.Time complexity: O(n + K).
val init : 'a -> length -> (index -> 'a) -> 'a t
init default n f
constructs and returns a fresh sequence whose length isn
and whose elements are the values produced by the callsf 0
,f 1
, ...f (n-1)
, in this order. It is equivalent toof_array default (Array.init n f)
.Time complexity: O(n + K), not counting the cost of the function
f
.
Accessors
val default : 'a t -> 'a
default s
returns the value that is used to fill empty array slots in the sequences
.Time complexity: O(1).
val is_empty : 'a t -> bool
is_empty s
returnstrue
if the sequences
is empty andfalse
otherwise. It is equivalent tolength s = 0
.Time complexity: O(1).
Assignment and Copy
val clear : 'a t -> unit
clear s
empties the sequences
.Time complexity: O(K), unless the global parameter
overwrite_empty_slots
isfalse
, in which case the complexity is O(1).
val copy : ?mode:[ `Copy | `Share ] -> 'a t -> 'a t
copy ~mode s
constructs and returns a copys'
of the sequences
. The sequencess
ands'
initially have the same elements, and can thereafter be modified independently of one another. Several copying modes are available, which have the same observable behavior, but offer distinct performance characteristics:copy ~mode:`Copy s
creates a sequence that is physically disjoint froms
. All of the elements are copied one by one. It takes linear time, which is slow, but on the upside, it has no latent cost. The sequences
is unaffected, and the sequences'
has unique ownership of its chunks.
copy ~mode:`Share s
creates a sequence whose chunks are physically shared with those ofs
. The copying of individual chunks is delayed untils
ors'
is actually modified. This operation has complexity O(K), which is fast, but on the downside, there is a latent cost: subsequent update operations ons
ands'
are more costly.
The default mode is
`Copy
. That is,copy s
is a short-hand forcopy ~mode:`Copy s
.Time complexity: O(n + K) in
`Share
mode; O(K) in`Copy
mode.
val assign : 'a t -> 'a t -> unit
If
s1
ands2
are distinct sequences, thenassign s1 s2
movess2
's elements intos1
, overwritings1
's previous content, and clearss2
. Ifs1
ands2
are the same sequence, thenassign s1 s2
has no effect.Time complexity: O(1) in the special case where
s2
is never used afterwards; otherwise O(K).
Stack Operations
val push : side -> 'a t -> 'a -> unit
push side s x
pushes the elementx
onto the front or back end of the sequences
. The parameterside
determines which end of the sequence is acted upon.Time complexity: O(log n) in the worst case. That said, in practice, most
push
operations execute in O(1).
val pop : side -> 'a t -> 'a
If the sequence
s
is nonempty, thenpop side s
pops an elementx
off the front or back end of the sequences
and returnsx
. The parameterside
determines which end of the sequence is acted upon. If the sequences
is empty, the exceptionEmpty
is raised.Time complexity: same as
push
.
val pop_opt : side -> 'a t -> 'a option
If the sequence
s
is nonempty, thenpop_opt side s
pops an elementx
off the front or back end of the sequences
and returnsSome x
. The parameterside
determines which end of the sequence is acted upon. If the sequences
is empty,None
is returned.Time complexity: same as
pop
.
val peek : side -> 'a t -> 'a
If the sequence
s
is nonempty, thenpeek side s
reads the elementx
found at the front or back end of the sequences
and returnsx
. The parameterside
determines which end of the sequence is acted upon. If the sequences
is empty, the exceptionEmpty
is raised.Time complexity: O(1).
val peek_opt : side -> 'a t -> 'a option
If the sequence
s
is nonempty, thenpeek_opt side s
reads the elementx
found at the front or back end of the sequences
and returnsSome x
. The parameterside
determines which end of the sequence is acted upon. If the sequences
is empty,None
is returned.Time complexity: O(1).
Random Access
val get : 'a t -> index -> 'a
get s i
returns the elementx
located at indexi
in the sequences
. The indexi
must lie in the semi-open interval[0, length s)
.Time complexity: O(log n), or, more precisely, O(log (min (i, n - i))).
val set : 'a t -> index -> 'a -> unit
set s i x
replaces the element located at indexi
in the sequences
with the elementx
. The indexi
must lie in the semi-open interval[0, length s)
. The sequences
is updated in place.Time complexity: if the
set
operation hits a chunk that is marked as potentially shared with other sequences, then its complexity is O(K + log n), and this chunk is replaced in the process with one that is not shared with any other sequence. Otherwise, the complexity is O(log n), or, more precisely, O(log (min (i, n - i))).
Concatenation and Splitting
val concat : 'a t -> 'a t -> 'a t
concat s1 s2
creates and returns a new sequence whose content is the concatenation of the sequencess1
ands2
. The sequencess1
ands2
are cleared. The sequencess1
ands2
must be distinct.concat
is slightly less efficient thanappend
, whose use should be preferred.Time complexity: in pathological cases,
concat
can cost as much as O(K + log^2 n), where n is the length of the result of the concatenation. In most cases, however, we expectconcat
to cost O(K + log n). In the particular case of a concatenation that involves sequences whose chunks have never been shared, a more precise bound is O(K + log (min(n1, n2))), where n1 and n2 denote the lengths of the two sequences.
val append : side -> 'a t -> 'a t -> unit
append back s1 s2
is equivalent toassign s1 (concat s1 s2)
. Thus,s1
is assigned the concatenation of the sequencess1
ands2
, whiles2
is cleared. In other words,append back s1 s2
appends the sequences2
at the back end of the sequences1
.append front s1 s2
is equivalent toassign s1 (concat s2 s1)
. Thus,s1
is assigned the concatenation of the sequencess2
ands1
, whiles2
is cleared. In other words,append front s1 s2
prepends the sequences2
at the front end of the sequences1
.In either case, the sequences
s1
ands2
must be distinct.Time complexity: same as
concat
.
val split : 'a t -> index -> 'a t * 'a t
split s i
splits the sequences
at indexi
. It returns two new sequencess1
ands2
such that the length ofs1
isi
and the concatenation ofs1
ands2
iss
. The sequences
is cleared. The indexi
must lie in the closed interval[0, length s]
.split
is slightly less efficient thancarve
, whose use should be preferred.Time complexity: in pathological cases,
split
can cost as much as O(K + log^2 n), where n is the length of the result of the concatenation. In most cases, however, we expectsplit
to cost O(K + log n), or, more precisely, O(K + log (min (i, n - i))). The latter bound holds, in particular, when the operation involves a sequence whose chunks have never been shared.
val carve : side -> 'a t -> index -> 'a t
carve back s i
is equivalent tolet s1, s2 = split s i in assign s s1; s2
. Thus, it splits the sequences
at indexi
into two parts: the first part is written tos
, while the second part is returned.carve front s i
is equivalent tolet s1, s2 = split s i in assign s s2; s1
. Thus, it splits the sequences
at indexi
into two parts: the second part is written tos
, while the first part is returned.In either case, the index
i
must lie in the closed interval[0, length s]
.Time complexity: same as
split
.
val take : side -> 'a t -> index -> unit
take side s i
is equivalent to (and faster than)ignore (carve side s i)
. In other words,take front s i
truncates the sequences
at indexi
, and keeps only the front part;take back s i
truncates the sequences
at indexi
, and keeps only the back part. The indexi
must lie in the closed interval[0, length s]
.Time complexity: same as
split
.
Iteration
val iter : direction -> ('a -> unit) -> 'a t -> unit
iter direction f s
applies the functionf
in turn to every elementx
of the sequences
. The parameterdirection
determines in what order the elements are presented. The functionf
is not allowed to modify the sequences
while iteration is ongoing. If the flagcheck_iterator_validity
is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: O(n), not counting the cost of the function
f
.
val iteri : direction -> (index -> 'a -> unit) -> 'a t -> unit
iteri direction f s
applies the functionf
in turn to every indexi
and matching elementx
of the sequences
. The parameterdirection
determines in what order the elements are presented. The functionf
is not allowed to modify the sequences
while iteration is ongoing. If the flagcheck_iterator_validity
is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: O(n), not counting the cost of the function
f
.
val iter_segments : direction -> 'a t -> 'a segments
iter_segments direction s f
applies the functionf
to a series of nonempty array segments whose concatenation represents the sequences
. The functionf
is allowed to read these array segments. When iterating backward, each segment must be traversed in reverse order. The functionf
is not allowed to write these array segments. The functionf
is not allowed to modify the sequences
while iteration is ongoing. If the flagcheck_iterator_validity
is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: O(n/K), not counting the cost of the function
f
.
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
fold_left f a s
applies the functionf
in turn to each element of the sequences
, in the forward direction. An accumulator is threaded through the calls tof
. The functionf
is not allowed to modify the sequences
while iteration is ongoing. Subject to this condition,fold_left f a s
is equivalent toList.fold_left f a (to_list s)
. If the flagcheck_iterator_validity
is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: O(n), not counting the cost of the function
f
.
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
fold_right f a s
applies the functionf
in turn to each element of the sequences
, in the backward direction. An accumulator is threaded through the calls tof
. The functionf
is not allowed to modify the sequences
while iteration is ongoing. Subject to this condition,fold_right f s a
is equivalent toList.fold_right f (to_list s) a
. If the flagcheck_iterator_validity
is enabled (which it is, by default), then an illegal modification is detected at runtime.Time complexity: O(n), not counting the cost of the function
f
.
Conversion To
val to_list : 'a t -> 'a list
to_list s
returns a list whose elements are the elements of the sequences
.Time complexity: O(n).
val to_array : 'a t -> 'a array
to_array s
returns a fresh array whose elements are the elements of the sequences
.Time complexity: O(n).
val to_seq : direction -> 'a t -> 'a Stdlib.Seq.t
to_seq direction s
returns a fresh sequence whose elements are the elements of the sequences
, enumerated according todirection
. The sequenceto_seq direction s
is ephemeral: it can be consumed only once. This sequence occupies O(log n) space in memory: it is an iterator in disguise.Time complexity: the creation of a sequence costs O(1); then, demanding each element of the sequence has the same cost as a call to
Iter.get_and_move
. If k elements of the resulting sequence are demanded by the user, then the total cost of producing these elements is O(k).
Conversion From
val of_list_segment : 'a -> length -> 'a list -> 'a t
of_list_segment default n xs
creates a new sequence out of then
first elements of the listxs
. The listxs
must have at leastn
elements.Time complexity: O(n + K).
val of_list : 'a -> 'a list -> 'a t
of_list default xs
creates a new sequence out of the listxs
. If the length of the listxs
is known, then the use ofof_list_segment
should be preferred.Time complexity: O(n + K).
val of_array_segment : 'a -> 'a array -> index -> length -> 'a t
of_array_segment default a head size
creates a new sequence out of the array segment defined by the arraya
, the start indexhead
, and the sizesize
. The data is copied, so the arraya
can still be used afterwards.Time complexity: O(n + K), where n, the length of the result, is equal to
size
.
val of_array : 'a -> 'a array -> 'a t
of_array default a
creates a new sequence out of the arraya
. The data is copied, so the arraya
can still be used afterwards.Time complexity: O(n + K).
val of_seq_segment : 'a -> length -> 'a Stdlib.Seq.t -> 'a t
of_seq_segment default n xs
creates a new sequence out of then
first elements of the sequencexs
. The sequencexs
must have at leastn
elements. It is consumed once.Time complexity: O(n + K), not counting the cost of demanding elements from the sequence
xs
.
val of_seq : 'a -> 'a Stdlib.Seq.t -> 'a t
of_seq d xs
creates a new sequence out of the sequencexs
. The sequencexs
must be finite. It is consumed once. If the length of the sequencexs
is known, then the use ofof_seq_segment
should be preferred.Time complexity: O(n + K), not counting the cost of demanding elements from the sequence
xs
.
Searching
val find : direction -> ('a -> bool) -> 'a t -> 'a
find direction p s
finds and returns the first element of the sequences
, along the directiondirection
, that satisfies the predicatep
. If no element of the sequence satisfiesp
, the exceptionNot_found
is raised.Time complexity: O(i), where
i
is the index of the first element that satisfiesp
, or n if no element satisfiesp
. This does not count the cost of the functionp
.
val find_opt : direction -> ('a -> bool) -> 'a t -> 'a option
find_opt direction p s
finds and returns the first element of the sequences
, along the directiondirection
, that satisfies the predicatep
. If no element of the sequence satisfiesp
,None
is returned.Time complexity: same as
find
.
val find_map : direction -> ('a -> 'b option) -> 'a t -> 'b option
find_map direction f s
appliesf
to each element of the sequences
, along the directiondirection
, and returns the first result other thanNone
. If there is no such result, it returnsNone
. Iff
is pure, then it is equivalent tofind direction (fun o -> o <> None) (map f s)
.Time complexity: same as
find
, not counting the cost of the functionf
.
val for_all : ('a -> bool) -> 'a t -> bool
for_all p s
tests whether all elements of the sequences
satisfy the predicatep
.Time complexity: O(i), where
i
is the index of the first element that does not satisfyp
, or n if every element satisfiesp
. This does not count the cost of the functionp
.
val exists : ('a -> bool) -> 'a t -> bool
exists p s
tests whether some element of the sequences
satisfies the predicatep
.Time complexity: O(i), where
i
is the index of the first element that satisfiesp
, or n if no element satisfiesp
. This does not count the cost of the functionp
.
val mem : 'a -> 'a t -> bool
mem x s
is equivalent toexists (fun y -> x = y) s
.
val memq : 'a -> 'a t -> bool
memq x s
is equivalent toexists (fun y -> x == y) s
.
Transformation
val map : 'b -> ('a -> 'b) -> 'a t -> 'b t
map default f s
applies the functionf
in turn to each element of the sequences
, in the forward direction, and returns a sequence of the results. The sequences
is unaffected.Time complexity: O(n + K), not counting the cost of the function
f
.
val mapi : 'b -> (index -> 'a -> 'b) -> 'a t -> 'b t
mapi default f s
applies the functionf
in turn to each index-and-element pair in the sequences
, in the forward direction, and returns a sequence of the results. The sequences
is unaffected.Time complexity: O(n + K), not counting the cost of the function
f
.
val rev : 'a t -> 'a t
rev s
returns a sequence whose elements are the elements of the sequences
, in reverse order. The sequences
is unaffected.Time complexity: O(n + K).
val zip : 'a t -> 'b t -> ('a * 'b) t
zip s1 s2
is a sequence of the pairs(x1, x2)
, wherex1
andx2
are drawn synchronously from the sequencess1
ands2
. The lengths of the sequencess1
ands2
need not be equal: the length of the result is the minimum of the lengths ofs1
ands2
.Time complexity: O(n + K), where n denotes the length of the result sequence.
val unzip : ('a * 'b) t -> 'a t * 'b t
unzip s
is equivalent to(map _ fst s, map _ snd s)
.Time complexity: O(n + K).
val filter : ('a -> bool) -> 'a t -> 'a t
filter p s
returns a subsequence of the elements ofs
that satisfy the predicatep
. The sequences
is unaffected.Time complexity: O(n + K), not counting the cost of the function
p
.
val filter_map : 'b -> ('a -> 'b option) -> 'a t -> 'b t
filter_map default f s
returns the subsequence of the defined images of the elements ofs
through the partial functionf
.Time complexity: O(n + K), not counting the cost of the function
f
.
Iteration over Two Sequences
val iter2 : direction -> ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
iter2 direction f s1 s2
repeatedly invokesf x1 x2
as long as a pair of elements(x1, x2)
can be drawn synchronously from the sequencess1
ands2
. The parameterdirection
determines on what side iteration must begin and in which direction it must progress. The lengths of the sequencess1
ands2
need not be equal: iteration stops as soon as the shortest sequence is exhausted.Time complexity: O(min(n1,n2)), where n1 and n2 denote the lengths of the arguments
s1
ands2
, not counting the cost of the functionf
.
val iter2_segments : direction -> 'a t -> 'b t -> ('a, 'b) segments2
iter2_segments direction s1 s2 f
repeatedly invokesf seg1 seg2
as long as a pair of nonempty array segmentsseg1
andseg2
of matching lengths can be drawn synchronously from the sequencess1
ands2
. The functionf
is allowed to read these array segments. The parameterdirection
determines on what side iteration must begin and in which direction it must progress. The lengths of the sequencess1
ands2
need not be equal: iteration stops as soon as the shortest sequence is exhausted.Time complexity: O(min(n1,n2)/K), where n1 and n2 denote the lengths of the arguments
s1
ands2
, not counting the cost of the functionf
.
val fold_left2 : ('c -> 'a -> 'b -> 'c) -> 'c -> 'a t -> 'b t -> 'c
fold_left2
is analogous toiter2 forward
, with the added feature that an accumulator is threaded through the calls tof
.Time complexity: same as
iter2
.
val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
fold_right2
is analogous toiter2 backward
, with the added feature that an accumulator is threaded through the calls tof
.Time complexity: same as
iter2
.
val map2 : 'c -> ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
map2 d f s1 s2
repeatedly invokesf x1 x2
as long as a pair of elements(x1, x2)
can be drawn synchronously from the sequencess1
ands2
, and returns the sequence of the results. Iteration is carried out in the forward direction. The lengths of the sequencess1
ands2
need not be equal: the length of the result is the minimum of the lengths ofs1
ands2
.Time complexity: O(n + K), where n denotes the length of the result, not counting the cost of the function
f
.
val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
for_all2 p s1 s2
tests whether all pairs(x1, x2)
drawn synchronously froms1
ands2
satisfy the predicatep
. The sequencess1
ands2
need not have the same length: any excess elements are ignored.Time complexity: O(min(n1,n2)), where n1 and n2 denote the lengths of the arguments
s1
ands2
, not counting the cost of the functionp
.
val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
exists2 p s
tests whether some pair(x1, x2)
drawn synchronously froms1
ands2
satisfies the predicatep
. The sequencess1
ands2
need not have the same length: any excess elements are ignored.Time complexity: O(min(n1,n2)), where n1 and n2 denote the lengths of the arguments
s1
ands2
, not counting the cost of the functionp
.
Comparison
val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
equal p s1 s2
tests whether the sequencess1
ands2
have the same length and all pairs(x1, x2)
drawn synchronously froms1
ands2
satisfy the predicatep
. Ifp x1 x2
compares the elementsx1
andx2
for equality, thenequal p s1 s2
compares the sequencess1
ands2
for equality.Time complexity: O(1) if the sequences have distinct lengths; otherwise O(i), where i is the index of the first pair that does not satisfy the predicate
p
, or n if all pairs satisfyp
. This does not count the cost of the functionp
.
val compare : ('a -> 'b -> comparison) -> 'a t -> 'b t -> comparison
If
cmp
implements a preorder on elements, thencompare cmp
implements the lexicographic preorder on sequences. (A preorder is an antisymmetric and transitive relation. For more details on comparison functions in OCaml, see the documentation ofArray.sort
.)Time complexity: same as
equal
.
Sorting
val sort : ('a -> 'a -> comparison) -> 'a t -> unit
sort cmp s
sorts the sequences
according to the preordercmp
. (For more details, see the documentation ofArray.sort
.)Time complexity: O(n log n + K).
The current implementation converts the data to an array and back. A future release may provide a more efficient implementation.
val stable_sort : ('a -> 'a -> comparison) -> 'a t -> unit
stable_sort cmp s
sorts the sequences
according to the preordercmp
. (For more details, see the documentation ofArray.sort
.) The sorting algorithm is stable: two elements that are equal according tocmp
are never permuted.Time complexity: O(n log n + K).
The current implementation converts the data to an array and back. A future release may provide a more efficient implementation.
val uniq : ('a -> 'a -> comparison) -> 'a t -> 'a t
uniq cmp s
returns a copy of the sequences
where adjacent duplicate elements have been filtered out. That is, an element is dropped if it is equal (according to the preordercmp
) to its left neighbor. If the sequences
is sorted with respect tocmp
, then the sequenceuniq cmp s
has no duplicate elements. The sequences
is unaffected.Time complexity: O(n + K).
val merge : ('a -> 'a -> comparison) -> 'a t -> 'a t -> 'a t
merge cmp s1 s2
requires the sequencess1
ands2
to be sorted with respect to the preordercmp
. It constructs a new sequence that is a sorted copy of the sequenceconcat s1 s2
. The sequencess1
ands2
are unaffected.Time complexity: O(n + K), where
n
denotes the sum of the lengths ofs1
ands2
, that is, the length of the result.
In-Place Transformation
val fill : 'a t -> index -> length -> 'a -> unit
fill s i k x
modifies the sequences
by overwriting the elements in the range[i, i+k)
with the elementx
.Time complexity: if the sequence involves chunks that may be shared with other sequences, the complexity is O(k + k/K * log n + K in the worst case. If none of the chunks that correspond to the range
[i, i+k)
were ever shared, then the cost is only O(k + log n).
val blit : 'a t -> index -> 'a t -> index -> length -> unit
blit s1 i1 s2 i2 k
modifies the sequences2
by overwriting the elements ofs2
in the range[i2, i2+k)
with the elements found in the sequences1
in the range[i1, i1+k)
. It is permitted fors1
ands2
to be the same sequence; in that case, all reads appear to take place before any writes.Time complexity: same as
fill
.
Miscellaneous
val format : Stdlib.Format.formatter -> int t -> unit
format
is a printer for sequences of integers. It can be installed in the OCaml toplevel loop by#install_printer format
. It is intended to be used only while debugging the library.
val check : 'a t -> unit
In a release build,
check s
does nothing. In a development build, it checks that the data structure's internal invariant is satisfied.