# Module `1-S.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 value`default`

is used to fill empty array slots.Time complexity:

*O(K)*.

`val make : 'a -> Sek__.PublicSignature.length -> 'a -> 'a t`

`make default n v`

constructs and returns a fresh sequence whose length is`n`

and which consists of`n`

copies of the value`v`

. It is equivalent to`of_array default (Array.make n v)`

.Time complexity:

*O(n + K)*.

`val init : 'a -> Sek__.PublicSignature.length -> (Sek__.PublicSignature.index -> 'a) -> 'a t`

`init default n f`

constructs and returns a fresh sequence whose length is`n`

and whose elements are the values produced by the calls`f 0`

,`f 1`

, ...`f (n-1)`

, in this order. It is equivalent to`of_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 sequence`s`

.Time complexity:

*O(1)*.

`val length : 'a t -> Sek__.PublicSignature.length`

`length s`

returns the length of the sequence`s`

.Time complexity:

*O(1)*.

`val is_empty : 'a t -> bool`

`is_empty s`

returns`true`

if the sequence`s`

is empty and`false`

otherwise. It is equivalent to`length s = 0`

.Time complexity:

*O(1)*.

### Assignment and Copy

`val clear : 'a t -> unit`

`clear s`

empties the sequence`s`

.Time complexity:

*O(K)*, unless the global parameter`overwrite_empty_slots`

is`false`

, in which case the complexity is*O(1)*.

`val copy : ?mode:[ `Copy | `Share ] -> 'a t -> 'a t`

`copy ~mode s`

constructs and returns a copy`s'`

of the sequence`s`

. The sequences`s`

and`s'`

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 from`s`

. 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 sequence`s`

is unaffected, and the sequence`s'`

has unique ownership of its chunks.

`copy ~mode:`Share s`

creates a sequence whose chunks are physically shared with those of`s`

. The copying of individual chunks is delayed until`s`

or`s'`

is actually modified. This operation has complexity*O(K)*, which is fast, but on the downside, there is a latent cost: subsequent update operations on`s`

and`s'`

are more costly.

The default mode is

``Copy`

. That is,`copy s`

is a short-hand for`copy ~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`

and`s2`

are distinct sequences, then`assign s1 s2`

moves`s2`

's elements into`s1`

, overwriting`s1`

's previous content, and clears`s2`

. If`s1`

and`s2`

are the same sequence, then`assign 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 element`x`

onto the front or back end of the sequence`s`

. The parameter`side`

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, then`pop side s`

pops an element`x`

off the front or back end of the sequence`s`

and returns`x`

. The parameter`side`

determines which end of the sequence is acted upon. If the sequence`s`

is empty, the exception`Empty`

is raised.Time complexity: same as

`push`

.

`val pop_opt : side -> 'a t -> 'a option`

If the sequence

`s`

is nonempty, then`pop_opt side s`

pops an element`x`

off the front or back end of the sequence`s`

and returns`Some x`

. The parameter`side`

determines which end of the sequence is acted upon. If the sequence`s`

is empty,`None`

is returned.Time complexity: same as

`pop`

.

`val peek : side -> 'a t -> 'a`

If the sequence

`s`

is nonempty, then`peek side s`

reads the element`x`

found at the front or back end of the sequence`s`

and returns`x`

. The parameter`side`

determines which end of the sequence is acted upon. If the sequence`s`

is empty, the exception`Empty`

is raised.Time complexity:

*O(1)*.

`val peek_opt : side -> 'a t -> 'a option`

If the sequence

`s`

is nonempty, then`peek_opt side s`

reads the element`x`

found at the front or back end of the sequence`s`

and returns`Some x`

. The parameter`side`

determines which end of the sequence is acted upon. If the sequence`s`

is empty,`None`

is returned.Time complexity:

*O(1)*.

### Random Access

`val get : 'a t -> Sek__.PublicSignature.index -> 'a`

`get s i`

returns the element`x`

located at index`i`

in the sequence`s`

. The index`i`

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 -> Sek__.PublicSignature.index -> 'a -> unit`

`set s i x`

replaces the element located at index`i`

in the sequence`s`

with the element`x`

. The index`i`

must lie in the semi-open interval`[0, length s)`

. The sequence`s`

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 sequences`s1`

and`s2`

. The sequences`s1`

and`s2`

are cleared. The sequences`s1`

and`s2`

must be distinct.`concat`

is slightly less efficient than`append`

, 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 expect`concat`

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 to`assign s1 (concat s1 s2)`

. Thus,`s1`

is assigned the concatenation of the sequences`s1`

and`s2`

, while`s2`

is cleared. In other words,`append back s1 s2`

appends the sequence`s2`

at the back end of the sequence`s1`

.`append front s1 s2`

is equivalent to`assign s1 (concat s2 s1)`

. Thus,`s1`

is assigned the concatenation of the sequences`s2`

and`s1`

, while`s2`

is cleared. In other words,`append front s1 s2`

prepends the sequence`s2`

at the front end of the sequence`s1`

.In either case, the sequences

`s1`

and`s2`

must be distinct.Time complexity: same as

`concat`

.

`val split : 'a t -> Sek__.PublicSignature.index -> 'a t * 'a t`

`split s i`

splits the sequence`s`

at index`i`

. It returns two new sequences`s1`

and`s2`

such that the length of`s1`

is`i`

and the concatenation of`s1`

and`s2`

is`s`

. The sequence`s`

is cleared. The index`i`

must lie in the closed interval`[0, length s]`

.`split`

is slightly less efficient than`carve`

, 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 expect`split`

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 -> Sek__.PublicSignature.index -> 'a t`

`carve back s i`

is equivalent to`let s1, s2 = split s i in assign s s1; s2`

. Thus, it splits the sequence`s`

at index`i`

into two parts: the first part is written to`s`

, while the second part is returned.`carve front s i`

is equivalent to`let s1, s2 = split s i in assign s s2; s1`

. Thus, it splits the sequence`s`

at index`i`

into two parts: the second part is written to`s`

, 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 -> Sek__.PublicSignature.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 sequence`s`

at index`i`

, and keeps only the front part;`take back s i`

truncates the sequence`s`

at index`i`

, and keeps only the back part. The index`i`

must lie in the closed interval`[0, length s]`

.Time complexity: same as

`split`

.

`val drop : side -> 'a t -> Sek__.PublicSignature.index -> unit`

`drop side s i`

is equivalent to`take (other side) s i`

. The index`i`

must lie in the closed interval`[0, length s]`

.Time complexity: same as

`split`

.

`val sub : 'a t -> Sek__.PublicSignature.index -> Sek__.PublicSignature.length -> 'a t`

`sub s head size`

extracts the sequence segment defined by the sequence`s`

, the start index`head`

, and the size`size`

. The sequence`s`

is unaffected.Time complexity:

*O(size + K)*.

### Iteration

`val iter : direction -> ('a -> unit) -> 'a t -> unit`

`iter direction f s`

applies the function`f`

in turn to every element`x`

of the sequence`s`

. The parameter`direction`

determines in what order the elements are presented. The function`f`

is not allowed to modify the sequence`s`

while iteration is ongoing. If the flag`check_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 -> (Sek__.PublicSignature.index -> 'a -> unit) -> 'a t -> unit`

`iteri direction f s`

applies the function`f`

in turn to every index`i`

and matching element`x`

of the sequence`s`

. The parameter`direction`

determines in what order the elements are presented. The function`f`

is not allowed to modify the sequence`s`

while iteration is ongoing. If the flag`check_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 Sek__.PublicSignature.segments`

`iter_segments direction s f`

applies the function`f`

to a series of nonempty array segments whose concatenation represents the sequence`s`

. The function`f`

is allowed to*read*these array segments. When iterating backward, each segment must be traversed in reverse order.**The function**The function`f`

is not allowed to write these array segments.`f`

is not allowed to modify the sequence`s`

while iteration is ongoing. If the flag`check_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 function`f`

in turn to each element of the sequence`s`

, in the forward direction. An accumulator is threaded through the calls to`f`

. The function`f`

is not allowed to modify the sequence`s`

while iteration is ongoing. Subject to this condition,`fold_left f a s`

is equivalent to`List.fold_left f a (to_list s)`

. If the flag`check_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 function`f`

in turn to each element of the sequence`s`

, in the backward direction. An accumulator is threaded through the calls to`f`

. The function`f`

is not allowed to modify the sequence`s`

while iteration is ongoing. Subject to this condition,`fold_right f s a`

is equivalent to`List.fold_right f (to_list s) a`

. If the flag`check_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 sequence`s`

.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 sequence`s`

.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 sequence`s`

, enumerated according to`direction`

. The sequence`to_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 -> Sek__.PublicSignature.length -> 'a list -> 'a t`

`of_list_segment default n xs`

creates a new sequence out of the`n`

first elements of the list`xs`

. The list`xs`

must have at least`n`

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 list`xs`

. If the length of the list`xs`

is known, then the use of`of_list_segment`

should be preferred.Time complexity:

*O(n + K)*.

`val of_array_segment : 'a -> 'a array -> Sek__.PublicSignature.index -> Sek__.PublicSignature.length -> 'a t`

`of_array_segment default a head size`

creates a new sequence out of the array segment defined by the array`a`

, the start index`head`

, and the size`size`

. The data is copied, so the array`a`

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 array`a`

. The data is copied, so the array`a`

can still be used afterwards.Time complexity:

*O(n + K)*.

`val of_seq_segment : 'a -> Sek__.PublicSignature.length -> 'a Stdlib.Seq.t -> 'a t`

`of_seq_segment default n xs`

creates a new sequence out of the`n`

first elements of the sequence`xs`

. The sequence`xs`

must have at least`n`

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 sequence`xs`

. The sequence`xs`

must be finite. It is consumed once. If the length of the sequence`xs`

is known, then the use of`of_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 sequence`s`

, along the direction`direction`

, that satisfies the predicate`p`

. If no element of the sequence satisfies`p`

, the exception`Not_found`

is raised.Time complexity:

*O(i)*, where`i`

is the index of the first element that satisfies`p`

, or*n*if no element satisfies`p`

. This does not count the cost of the function`p`

.

`val find_opt : direction -> ('a -> bool) -> 'a t -> 'a option`

`find_opt direction p s`

finds and returns the first element of the sequence`s`

, along the direction`direction`

, that satisfies the predicate`p`

. If no element of the sequence satisfies`p`

,`None`

is returned.Time complexity: same as

`find`

.

`val find_map : direction -> ('a -> 'b option) -> 'a t -> 'b option`

`find_map direction f s`

applies`f`

to each element of the sequence`s`

, along the direction`direction`

, and returns the first result other than`None`

. If there is no such result, it returns`None`

. If`f`

is pure, then it is equivalent to`find direction (fun o -> o <> None) (map f s)`

.Time complexity: same as

`find`

, not counting the cost of the function`f`

.

`val for_all : ('a -> bool) -> 'a t -> bool`

`for_all p s`

tests whether all elements of the sequence`s`

satisfy the predicate`p`

.Time complexity:

*O(i)*, where`i`

is the index of the first element that does not satisfy`p`

, or*n*if every element satisfies`p`

. This does not count the cost of the function`p`

.

`val exists : ('a -> bool) -> 'a t -> bool`

`exists p s`

tests whether some element of the sequence`s`

satisfies the predicate`p`

.Time complexity:

*O(i)*, where`i`

is the index of the first element that satisfies`p`

, or*n*if no element satisfies`p`

. This does not count the cost of the function`p`

.

`val mem : 'a -> 'a t -> bool`

`mem x s`

is equivalent to`exists (fun y -> x = y) s`

.

`val memq : 'a -> 'a t -> bool`

`memq x s`

is equivalent to`exists (fun y -> x == y) s`

.

### Transformation

`val map : 'b -> ('a -> 'b) -> 'a t -> 'b t`

`map default f s`

applies the function`f`

in turn to each element of the sequence`s`

, in the forward direction, and returns a sequence of the results. The sequence`s`

is unaffected.Time complexity:

*O(n + K)*, not counting the cost of the function`f`

.

`val mapi : 'b -> (Sek__.PublicSignature.index -> 'a -> 'b) -> 'a t -> 'b t`

`mapi default f s`

applies the function`f`

in turn to each index-and-element pair in the sequence`s`

, in the forward direction, and returns a sequence of the results. The sequence`s`

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 sequence`s`

, in reverse order. The sequence`s`

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)`

, where`x1`

and`x2`

are drawn*synchronously*from the sequences`s1`

and`s2`

. The lengths of the sequences`s1`

and`s2`

need not be equal: the length of the result is the minimum of the lengths of`s1`

and`s2`

.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 of`s`

that satisfy the predicate`p`

. The sequence`s`

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 of`s`

through the partial function`f`

.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 invokes`f x1 x2`

as long as a pair of elements`(x1, x2)`

can be drawn*synchronously*from the sequences`s1`

and`s2`

. The parameter`direction`

determines on what side iteration must begin and in which direction it must progress. The lengths of the sequences`s1`

and`s2`

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`

and`s2`

, not counting the cost of the function`f`

.

`val iter2_segments : direction -> 'a t -> 'b t -> ('a, 'b) Sek__.PublicSignature.segments2`

`iter2_segments direction s1 s2 f`

repeatedly invokes`f seg1 seg2`

as long as a pair of nonempty array segments`seg1`

and`seg2`

of matching lengths can be drawn*synchronously*from the sequences`s1`

and`s2`

. The function`f`

is allowed to*read*these array segments. The parameter`direction`

determines on what side iteration must begin and in which direction it must progress. The lengths of the sequences`s1`

and`s2`

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`

and`s2`

, not counting the cost of the function`f`

.

`val fold_left2 : ('c -> 'a -> 'b -> 'c) -> 'c -> 'a t -> 'b t -> 'c`

`fold_left2`

is analogous to`iter2 forward`

, with the added feature that an accumulator is threaded through the calls to`f`

.Time complexity: same as

`iter2`

.

`val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c`

`fold_right2`

is analogous to`iter2 backward`

, with the added feature that an accumulator is threaded through the calls to`f`

.Time complexity: same as

`iter2`

.

`val map2 : 'c -> ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t`

`map2 d f s1 s2`

repeatedly invokes`f x1 x2`

as long as a pair of elements`(x1, x2)`

can be drawn*synchronously*from the sequences`s1`

and`s2`

, and returns the sequence of the results. Iteration is carried out in the forward direction. The lengths of the sequences`s1`

and`s2`

need not be equal: the length of the result is the minimum of the lengths of`s1`

and`s2`

.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 from`s1`

and`s2`

satisfy the predicate`p`

. The sequences`s1`

and`s2`

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`

and`s2`

, not counting the cost of the function`p`

.

`val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool`

`exists2 p s`

tests whether some pair`(x1, x2)`

drawn synchronously from`s1`

and`s2`

satisfies the predicate`p`

. The sequences`s1`

and`s2`

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`

and`s2`

, not counting the cost of the function`p`

.

### Comparison

`val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool`

`equal p s1 s2`

tests whether the sequences`s1`

and`s2`

have the same length and all pairs`(x1, x2)`

drawn synchronously from`s1`

and`s2`

satisfy the predicate`p`

. If`p x1 x2`

compares the elements`x1`

and`x2`

for equality, then`equal p s1 s2`

compares the sequences`s1`

and`s2`

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 satisfy`p`

. This does not count the cost of the function`p`

.

`val compare : ('a -> 'b -> Sek__.PublicSignature.comparison) -> 'a t -> 'b t -> Sek__.PublicSignature.comparison`

If

`cmp`

implements a preorder on elements, then`compare 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 of`Array.sort`

.)Time complexity: same as

`equal`

.

### Sorting

`val sort : ('a -> 'a -> Sek__.PublicSignature.comparison) -> 'a t -> unit`

`sort cmp s`

sorts the sequence`s`

according to the preorder`cmp`

. (For more details, see the documentation of`Array.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 -> Sek__.PublicSignature.comparison) -> 'a t -> unit`

`stable_sort cmp s`

sorts the sequence`s`

according to the preorder`cmp`

. (For more details, see the documentation of`Array.sort`

.) The sorting algorithm is stable: two elements that are equal according to`cmp`

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 -> Sek__.PublicSignature.comparison) -> 'a t -> 'a t`

`uniq cmp s`

returns a copy of the sequence`s`

where adjacent duplicate elements have been filtered out. That is, an element is dropped if it is equal (according to the preorder`cmp`

) to its left neighbor. If the sequence`s`

is sorted with respect to`cmp`

, then the sequence`uniq cmp s`

has no duplicate elements. The sequence`s`

is unaffected.Time complexity:

*O(n + K)*.

`val merge : ('a -> 'a -> Sek__.PublicSignature.comparison) -> 'a t -> 'a t -> 'a t`

`merge cmp s1 s2`

requires the sequences`s1`

and`s2`

to be sorted with respect to the preorder`cmp`

. It constructs a new sequence that is a sorted copy of the sequence`concat s1 s2`

. The sequences`s1`

and`s2`

are unaffected.Time complexity:

*O(n + K)*, where`n`

denotes the sum of the lengths of`s1`

and`s2`

, that is, the length of the result.

### In-Place Transformation

`val fill : 'a t -> Sek__.PublicSignature.index -> Sek__.PublicSignature.length -> 'a -> unit`

`fill s i k x`

modifies the sequence`s`

by overwriting the elements in the range`[i, i+k)`

with the element`x`

.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 -> Sek__.PublicSignature.index -> 'a t -> Sek__.PublicSignature.index -> Sek__.PublicSignature.length -> unit`

`blit s1 i1 s2 i2 k`

modifies the sequence`s2`

by overwriting the elements of`s2`

in the range`[i2, i2+k)`

with the elements found in the sequence`s1`

in the range`[i1, i1+k)`

. It is permitted for`s1`

and`s2`

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.