74 lines
2.3 KiB
OCaml
74 lines
2.3 KiB
OCaml
(* This file was originally part of lwt-dllist, which is licensed
|
|
under MIT: https://github.com/ocsigen/lwt/blob/master/LICENSE.md. *)
|
|
|
|
type 'a t
|
|
(** Type of a sequence holding values of type ['a] *)
|
|
|
|
type 'a node
|
|
(** Type of a node holding one value of type ['a] in a sequence *)
|
|
|
|
(** {2 Operation on nodes} *)
|
|
|
|
val remove : 'a node -> unit
|
|
(** Removes a node from the sequence it is part of. It does nothing
|
|
if the node has already been removed. *)
|
|
|
|
(** {2 Operations on sequence} *)
|
|
|
|
val create : unit -> 'a t
|
|
(** [create ()] creates a new empty sequence *)
|
|
|
|
val is_empty : 'a t -> bool
|
|
(** Returns [true] iff the given sequence is empty *)
|
|
|
|
val reset : 'a t -> unit
|
|
(** [reset ()] is a lazy way to remove all the elements from the sequence *)
|
|
|
|
val add_l : 'a -> 'a t -> 'a node
|
|
(** [add_l x s] adds [x] to the left of the sequence [s] *)
|
|
|
|
val add_r : 'a -> 'a t -> 'a node
|
|
(** [add_r x s] adds [x] to the right of the sequence [s] *)
|
|
|
|
val take_l : 'a t -> 'a
|
|
(** [take_l x s] removes and returns the leftmost element of [s]
|
|
|
|
@raise Not_found if the sequence is empty *)
|
|
|
|
val take_r : 'a t -> 'a
|
|
(** [take_l x s] removes and returns the rightmost element of [s]
|
|
|
|
@raise Not_found if the sequence is empty *)
|
|
|
|
(** {2 Sequence iterators} *)
|
|
|
|
(** Note: it is OK to remove a node while traversing a sequence *)
|
|
|
|
(* val 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] *)
|
|
(* *\) *)
|
|
|
|
val 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]
|
|
*)
|
|
|
|
val iter_l : ('a -> unit) -> 'a t -> unit
|
|
(** [iter_l f s] applies [f] on all elements of [s] starting from
|
|
the left *)
|
|
|
|
val find : ('a -> bool) -> 'a t -> 'a
|
|
(** [find_node_l f s] returns the first element of [s] starting from the left
|
|
that satisfies [f] or raises [Not_found] if none exists. *)
|
|
|
|
val exists : ('a -> bool) -> 'a t -> bool
|
|
(** [find_node_l f s] returns [true] if some node [s] starting from the left
|
|
that satisfies [f] or returns [false] if none exists. *)
|