# Module `Sek`

This library offers efficient implementations of ephemeral sequences and persistent sequences, together with efficient conversions between these two data structures.

## Type Abbreviations

`type index`

`= int`

An index into a sequence is an integer. It is comprised between 0 (included) and the length of the sequence (excluded or included, depending on the circumstances).

`type 'a segment`

`= 'a array * index * length`

An array segment is described by a triple of an array

`a`

, a start index`i`

, and a length`k`

.

`type 'a segments`

`= ('a segment -> unit) -> unit`

A sequence of array segments is represented by a higher-order iterator.

## Library API

`module type ITER = sig ... end`

The signature

`ITER`

is the core iterator API. It is common to ephemeral and persistent sequences. Please follow the link for details.

`module type ITER_EPHEMERAL = sig ... end`

The signature

`ITER_EPHEMERAL`

extends the iterator API with concepts and operations that exist only in the case of iterators over ephemeral sequences. Please follow the link for details.

### Ephemeral and Persistent Sequences

`val front : side`

`val back : side`

A side appears as a parameter to several operations, such as

`push`

and`pop`

, which can operate at either end of a sequence.

`val forward : direction`

`val backward : direction`

A direction appears as a parameter to several operations, such as

`iter`

, which can traverse the sequence either forward (from front to back) or backward (from back to front).

`val sign : direction -> int`

`sign forward`

is`+1`

.`sign backward`

is`-1`

.

`exception`

`Empty`

The exception

`Empty`

is raised by`pop`

and`peek`

operations when applied to an empty sequence.

`exception`

`End`

The exception

`End`

is raised by the iterator operations`get`

,`get_segment`

,`get_and_move`

, and`get_segment_and_jump`

when the iterator has moved past the end of the sequence.

`module Ephemeral : sig ... end`

The submodule

`Ephemeral`

, also available under the name`E`

, offers an implementation of ephemeral (mutable) sequences. Please follow the link for details.

`module Persistent : sig ... end`

The submodule

`Persistent`

, also available under the name`P`

, offers an implementation of persistent (immutable) sequences. Please follow the link for details.

`module P = Persistent`

`P`

is a short name for the submodule`Persistent`

.

### Conversion Functions

`val snapshot : 'a Ephemeral.t -> 'a Persistent.t`

`snapshot s`

constructs and returns a persistent sequence whose elements are the elements of`s`

. It is less efficient than`snapshot_and_clear`

, whose use should be preferred, when possible.Time complexity:

*O(K)*. Note that this operation introduces sharing: therefore, it may increase the cost of subsequent operations.

`val snapshot_and_clear : 'a Ephemeral.t -> 'a Persistent.t`

`snapshot_and_clear s`

constructs and returns a persistent sequence whose elements are the elements of an ephemeral sequence`s`

. As a side effect, it clears`s`

.Time complexity:

*O(min(K,n))*. In other words, the cost is always*O(K)*and, in the specific case of short sequences, it is only*O(n)*.In the particular case where the ephemeral sequence

`s`

has been constructed by applying a series of`push`

operations, the cost of`snapshot_and_clear`

may be charged to these`push`

operations, allowing one to consider that`snapshot_and_clear`

costs*O(1)*.

`val edit : 'a Persistent.t -> 'a Ephemeral.t`

`edit s`

constructs and returns a new ephemeral sequence whose elements are the elements of`s`

.Time complexity:

*O(K)*.

### Emulation Layers

### Miscellaneous

`val released : unit -> unit`

The function call

`released()`

does nothing if the library was compiled in release mode, and fails (with an assertion failure) if the library was compiled with assertions enabled.

`module Segment : sig ... end`

The module

`Segment`

offers facilities for working with array segments. An array segment is a triple of an array, a start index, and a length.

## Settings

### Chunk Capacity

`module type CAPACITY = sig ... end`

### Overwriting Empty Slots

`module type OVERWRITE_EMPTY_SLOTS = sig ... end`

### Compact Persistent Sequence Threshold

`module type THRESHOLD = sig ... end`

### Dynamic Checking of Iterator Validity

`module type CHECK_ITERATOR_VALIDITY = sig ... end`

### The Functor `Make`

`module Make : functor (Settings : sig ... end) -> SEK`

The functor

`Make`

constructs an implementation of the signature`SEK`

, and allows the user to choose the value of the settings described above. Be warned, however, that the number and the nature of the settings expected by this functor may change in the future. A relatively forward-compatible way of using this functor is to always pass it a structure that is built by including the structure`DefaultSettings`

and overriding the definition of one or more settings.

`module DefaultSettings : sig ... end`

The module

`DefaultSettings`

provides a set of recommended settings for the functor`Make`

.

### The Functor `SupplyDefault`

`module SupplyDefault = SupplyDefault.SupplyDefault`