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

The capacity of a chunk is a nonnegative integer.

type depth = int

The depth of a chunk is a nonnegative integer.

Library API

module type SEK = sig ... end

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.

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

exception Empty

The exception Empty is raised by pop and peek operations when applied to an empty sequence.

module Ephemeral : sig ... end

The submodule Ephemeral, also available under the name E, offers an implementation of ephemeral (mutable) sequences.

module Persistent : sig ... end

The submodule Persistent, also available under the name P, offers an implementation of persistent (immutable) sequences.

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.

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 s. As a side effect, it clears s.

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

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

Emulation Layers

module Queue : sig ... end

The submodule Queue is a replacement for OCaml's standard Queue module, where a queue is implemented as an ephemeral sequence. Elements are enqueued at the back end of the sequence and dequeued at the front end.

module Stack : sig ... end

The submodule Stack is a replacement for OCaml's standard Stack module, where a stack is implemented as an ephemeral sequence. Elements are pushed and popped at the front end of the sequence.

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.

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

The Functor Make

module Make : functor (C : CAPACITY) -> functor (O : OVERWRITE_EMPTY_SLOTS) -> functor (T : THRESHOLD) -> SEK

The functor Make constructs an implementation of the signature SEK, and allows the user to choose the value of the parameters described above. Be warned, however, that the number and types of the parameters of this functor may change in the future. Users who want maximum forward compatibility should not use this functor.

Complexity Guide