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 length = int

The length of a sequence is a nonnegative integer.

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.

type ('a1, 'a2) segments2 = ('a1 segment -> 'a2 segment -> unit) -> unit

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

type capacity = int

The capacity of a chunk is a nonnegative integer.

type depth = int

The depth of a chunk is a nonnegative integer.

type comparison = int

The result of a comparison is encoded as an integer value. A negative value means "less than"; zero means "equal"; a positive value means "greater than".

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.

module type SEK = sig ... end

The signature SEK is the public API of the library. If you are a new user, you do not need to follow this link: the library's API appears below anyway. Just read on!

Ephemeral and Persistent Sequences

type side
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 other : side -> side

other front is back. other back is front.

type direction
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 opposite : direction -> direction

opposite forward is backward. opposite backward is forward.

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 E = Ephemeral

E is a short name for the submodule Ephemeral.

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

module Emulated : sig ... end

The submodule Emulated contains Sek-based replacements for several modules in OCaml's standard library: Array, List, Queue, Stack.

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

Complexity Guide

The outermost layer

The inner layers

Short persistent sequences

Constant factors

Conversions