Module Dllist

module Dllist: sig  end

Definitions for doubly-linked lists which allow for in-place insertion and removal.

This data structure is not thread safe.
See also testing/test_dllist.ml for simple examples of how to use this module.

exception Empty

Raised by some operations when the list is empty.

exception OutOfBounds

Raised by some operations when going beyond the elements in the list.

type 'a t

The type of doubly-linked lists of elements of type 'a.

type 'a cons

The opaque type of a cell in a doubly-linked list of elements of type 'a.

val deref : 'a cons -> 'a

Returns the value associated with a cell.

val create : unit -> 'a t

Creates a new doubly-linked list.

val first : 'a t -> 'a cons

first d returns the first cell in the dllist d. Raise Empty if the dllist is empty.

val last : 'a t -> 'a cons

last d returns the last cell in the dllist d. Raise Empty if the dllist is empty.

val next : 'a cons -> 'a cons

next c returns the next cell in the dllist in which c is contained. Returns OutOfBounds if c is the last cell.

val prev : 'a cons -> 'a cons

prev c returns the previous cell in the dllist in which c is contained. Returns OutOfBounds if c is the first cell.

val insert_end : 'a -> 'a t -> 'a cons

insert_end v q inserts a new cell with value v at the end of the dllist q, and returns the newly created cell.

val insert_before : 'a -> 'a cons -> 'a cons

insert_before v c inserts a new cell with value v just before cell c in the dllist in which c exists, and returns the newly created cell.

exception Cons_already_free

val remove : 'a cons -> unit

remove c removes the cell c from dllist where it exists.

val count : 'a t -> int

count q returns the number of cells in the dllist q.

val to_list : 'a t -> 'a cons list

This reverses the order...

val iter : ('a -> unit) -> 'a t -> unit

iter f q applies f e for each entry e of the dllist q.