Type of a sequence holding values of type 'a

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

Returns the contents of a node

Change the contents of a node

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

create () creates a new empty sequence

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

Returns true iff the given sequence is empty

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.

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

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

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

take_l x s remove and returns the leftmost element of s

• raises Empty

  if the sequence is empty

take_r x s remove and returns the rightmost element of s

• raises Empty

  if the sequence is empty

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

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

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.

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.

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

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

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

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

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

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

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.

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.

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.

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.