package lwt-dllist

  1. Overview
  2. Docs
package lwt-dllist
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Lwt_dllistSource

Mutable double-linked list of elements

A sequence is an object holding a list of elements which support the following operations:

  • adding an element to the left or the right in time and space O(1)
  • taking an element from the left or the right in time and space O(1)
  • removing a previously added element from a sequence in time and space O(1)
  • removing an element while the sequence is being transversed.
Sourcetype 'a t

Type of a sequence holding values of type 'a

Sourcetype 'a node

Type of a node holding one value of type 'a in a sequence

Operation on nodes

Sourceval get : 'a node -> 'a

Returns the contents of a node

Sourceval set : 'a node -> 'a -> unit

Changes the contents of a node

Sourceval remove : 'a node -> unit

Removes a node from the sequence it is part of. It does nothing if the node has already been removed.

Operations on sequence

Sourceval create : unit -> 'a t

create () creates a new empty sequence

Sourceval clear : 'a t -> unit

Removes all nodes from the given sequence. The nodes are not actually mutated to note their removal. Only the sequence's pointers are updated.

Sourceval is_empty : 'a t -> bool

Returns true iff the given sequence is empty

Sourceval length : 'a t -> int

Returns the number of elements in the given sequence. This is a O(n) operation where n is the number of elements in the sequence.

Sourceval add_l : 'a -> 'a t -> 'a node

add_l x s adds x to the left of the sequence s

Sourceval add_r : 'a -> 'a t -> 'a node

add_r x s adds x to the right of the sequence s

Sourceexception Empty

Exception raised by take_l and take_r and when the sequence is empty

Sourceval take_l : 'a t -> 'a

take_l x s removes and returns the leftmost element of s

  • raises Empty

    if the sequence is empty

Sourceval take_r : 'a t -> 'a

take_r x s removes and returns the rightmost element of s

  • raises Empty

    if the sequence is empty

Sourceval take_opt_l : 'a t -> 'a option

take_opt_l x s removes and returns Some x where x is the leftmost element of s or None if s is empty

Sourceval take_opt_r : 'a t -> 'a option

take_opt_r x s removes and returns Some x where x is the rightmost element of s or None if s is empty

Sourceval transfer_l : 'a t -> 'a t -> unit

transfer_l s1 s2 removes all elements of s1 and add them at the left of s2. This operation runs in constant time and space.

Sourceval transfer_r : 'a t -> 'a t -> unit

transfer_r s1 s2 removes all elements of s1 and add them at the right of s2. This operation runs in constant time and space.

Sequence iterators

Note: it is OK to remove a node while traversing a sequence

Sourceval iter_l : ('a -> unit) -> 'a t -> unit

iter_l f s applies f on all elements of s starting from the left

Sourceval iter_r : ('a -> unit) -> 'a t -> unit

iter_r f s applies f on all elements of s starting from the right

Sourceval iter_node_l : ('a node -> unit) -> 'a t -> unit

iter_node_l f s applies f on all nodes of s starting from the left

Sourceval iter_node_r : ('a node -> unit) -> 'a t -> unit

iter_node_r f s applies f on all nodes of s starting from the right

Sourceval fold_l : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

fold_l f s is:

  fold_l f s x = f en (... (f e2 (f e1 x)))

where e1, e2, ..., en are the elements of s

Sourceval fold_r : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

fold_r f s is:

  fold_r f s x = f e1 (f e2 (... (f en x)))

where e1, e2, ..., en are the elements of s

Sourceval find_node_opt_l : ('a -> bool) -> 'a t -> 'a node option

find_node_opt_l f s returns Some x, where x is the first node of s starting from the left that satisfies f or None if none exists.

Sourceval find_node_opt_r : ('a -> bool) -> 'a t -> 'a node option

find_node_opt_r f s returns Some x, where x is the first node of s starting from the right that satisfies f or None if none exists.

Sourceval find_node_l : ('a -> bool) -> 'a t -> 'a node

find_node_l f s returns the first node of s starting from the left that satisfies f or raises Not_found if none exists.

Sourceval find_node_r : ('a -> bool) -> 'a t -> 'a node

find_node_r f s returns the first node of s starting from the right that satisfies f or raises Not_found if none exists.