Module Std.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
include Sexpable.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 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.