Module Doubly_linked

module Doubly_linked: Doubly_linked

There is a fundamental problem with a data structure (like doubly-linked lists) that is both mutable and provides iteration function that call back to user-supplied functions. If those user-supplied functions modify the data structure, what is the semantics of the remainder of the iteration? This module sidesteps this issue by detecting attempts by user-supplied functions to modify a doubly-linked list while in the middle of iterating over it.

Modification functions include: insert_*, remove*, transfer Iteration functions include: exists, fold*, for_all, find

Calls to modification functions detect if the list is being iterated over, and if so raise an exception rather than modify the list. For example, a use like the following would raise.

iter t ~f:(fun _ -> ... remove t e ...)

module Elt: sig .. end

type 'a t

include Container.S1

val invariant : 'a t -> unit

val create : unit -> 'a t

creating doubly-linked lists

val of_list : 'a list -> 'a t

of_list l returns a doubly-linked list t with the same elements as l and in the same order (i.e. the first element of l is the first element of t). It is always the case that l = to_list (of_list l).

val equal : 'a t -> 'a t -> bool

predicates

val is_first : 'a t -> 'a Elt.t -> bool

val is_last : 'a t -> 'a Elt.t -> bool

val first_elt : 'a t -> 'a Elt.t option

constant-time extraction of first and last elements.

val last_elt : 'a t -> 'a Elt.t option

val first : 'a t -> 'a option

val last : 'a t -> 'a option

val next : 'a t -> 'a Elt.t -> 'a Elt.t option

constant-time move to next or previous element.

val prev : 'a t -> 'a Elt.t -> 'a Elt.t option

val insert_before : 'a t -> 'a Elt.t -> 'a -> 'a Elt.t

constant-time insertion of a new element. It is an error to call

insert_before t e
    a

or insert_after t e a if e is not an element in t, and will break invariants.

val insert_after : 'a t -> 'a Elt.t -> 'a -> 'a Elt.t

val insert_first : 'a t -> 'a -> 'a Elt.t

val insert_last : 'a t -> 'a -> 'a Elt.t

val remove : 'a t -> 'a Elt.t -> unit

constant-time removal of an element. It is an error to call remove t e when e is not in t, and will break invariant.

val remove_first : 'a t -> 'a option

val remove_last : 'a t -> 'a option

val fold_elt : 'a t -> init:'b -> f:('b -> 'a Elt.t -> 'b) -> 'b

fold_elt t ~init ~f is the same as fold, except f is called with the 'a Elt.t's from the list instead of the contained 'a values.

Note that like other iteration functions, it is an error to mutate t inside the fold. If you'd like to call remove on any of the 'a Elt.t's, accumulate them here and do so after fold_elt returns.

val fold_right : 'a t -> init:'b -> f:('a -> 'b -> 'b) -> 'b

val find_elt : 'a t -> f:('a -> bool) -> 'a Elt.t option

find_elt t ~f finds the first element in t that satisfies f, by testing each of element of t in turn until f succeeds.

val clear : 'a t -> unit

clear t removes all elements from the list in constant time.

val copy : 'a t -> 'a t

copy t returns a copy of t.

val transfer : src:'a t -> dst:'a t -> unit

transfer ~src ~dst has the same behavior as iter src ~f:(insert_last dst); clear src except that it runs in constant time.

If s = to_list src and d = to_list dst, then after transfer ~src ~dst: to_list src = [] to_list dst = d @ s

val filter_inplace : 'a t -> f:('a -> bool) -> unit

filter_inplace t ~f removes all elements of t that don't satisfy f.

val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t

val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t