Module Spotlib.DllistSource

Sourcetype 'a t

The type of the dllist

Sourcetype 'a node

The type of the dllist node

Sourceval create : unit -> 'a t

Create an empty dllist

Sourceval length : 'a t -> int

O(1). The length of the dllist

Sourceval is_empty : 'a t -> bool
Sourceval list : 'a node -> 'a t option

list node returns Some t if node is an element of t. If node is removed, it returns None.

Sourceval is_removed : 'a node -> bool
Sourceval value : 'a node -> 'a

Get the value from the node

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

O(1). add t v adds v to dllist t and returns the newly created node for v. The node is used to remove the value from t in constant time.

Sourceval remove : 'a node -> (unit, [> `Already_removed ]) result

O(1). remove node removes node from the dllist it belongs to. Successful removal returns `Ok. If the node is already removed, remove node returns `Already_removed.

Sourceval hd : 'a t -> 'a node option

hd t returns the first node of the dllist t.

Sourceval tl : 'a t -> 'a node option option

tl t returns the second node of the dllist t.

None : t is null Some None : t is a singleton Some (Some n) : n is the second

Sourceval hd_tl : 'a t -> ('a node * 'a node option) option
Sourceval iter : ('a node -> unit) -> 'a t -> unit

Iteration over the nodes of a dllist from the top to the bottom

Sourceval fold_left : ('a -> 'b node -> 'a) -> 'a -> 'b t -> 'a

Folding the nodes of a dllist from the top to the bottom

Sourceval fold_right : ('b node -> 'a -> 'a) -> 'b t -> 'a -> 'a

Folding the nodes of a dllist from the bottom to top

Sourceval scan_left : ('a -> 'b node -> [< `Continue of 'a | `Stop of 'a ]) -> 'a -> 'b t -> 'a

fold_left with stop

Sourceval scan_left_nodes : ('a -> 'b node -> [< `Continue of 'a | `Stop of 'a ]) -> 'a -> 'b node -> 'a

scan but starts with a node

Sourceval to_nodes : 'a t -> 'a node list

list <=> dllist conversion functions

Sourceval to_list : 'a t -> 'a list
Sourceval of_list : 'a list -> 'a t
Sourceval invariant : 'a t -> unit

Invariant checks