(* File: dllist.mli
Copyright 2005, Troestler Christophe
Christophe.Troestler(at)umh.ac.be
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
version 2.1 as published by the Free Software Foundation, with the
special exception on linking described in file LICENSE.
This library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the file
LICENSE for more details.
*)
(** A mutable, doubly linked list library with mutable circular
iterators.
This module implements a doubly linked list in a mutable or
imperative style (changes to the list are visible to all copies of
the list). Several iterators can be attached to a list.
In the big-O complexities below, N represent the length of the
list.
*)
type 'a t (** Doubly linked list *)
type 'a iterator (** Circular iterator *)
val make : unit -> 'a t
(** Creates an empty list. This is an O(1) operation. *)
val length : 'a t -> int
(** Returns the length of the list. This is an O(N) operation. *)
val copy : 'a t -> 'a t
(** [copy l] returns a fresh copy of the list -- so modifications to
the copy do not affect the initial list. The data elements
however are shared between the two lists. This is an O(N)
operation. *)
val clear_and_copy : 'a t -> 'a t
(** [clear_and_copy l] make [l] empty and return a copy of it. This
is a O(1) operation. *)
val append : 'a -> 'a t -> unit
(** [append l a] inserts [a] at the end of the list [l]. This is an
O(1) operation. *)
val prepend : 'a -> 'a t -> unit
(** [prepend n a] inserts [a] at the beginning of the list. This is
an O(1) operation. *)
val first : 'a t -> 'a
(** Returns the first element of the list.
@raise Failure if the list is empty. *)
val last : 'a t -> 'a
(** Returns the last element of the list.
@raise Failure if the list is empty. *)
val remove_first : 'a t -> unit
(** Removes the first element from the list.
@raise Failure if the list is empty. *)
val remove_last : 'a t -> unit
(** Removes the last element from the list.
@raise Failure if the list is empty. *)
val rev : 'a t -> unit
(** In place list reversal. This is an O(N) operation. *)
val iter : ('a -> unit) -> 'a t -> unit
(** [iter f n] apply [f] to every element in the list. This is an
O(N) operation. *)
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
(** Accumulate a value over the entire list. This works like
List.fold_left. This is an O(N) operation. *)
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** Accumulate a value over the entire list. This works like
List.fold_right, but since the list is bidirectional, it doesn't
suffer the recursion depth problems of List.fold_right. This is
an O(N) operation. *)
val map : ('a -> 'b) -> 'a t -> 'b t
(** Allocate a new list, with entirely new nodes, whose values are
the transforms of the values of the original list. Note that this
does not modify the given list. This is an O(N) operation. *)
val filter : ('a -> bool) -> 'a t -> unit
(** [filter f l] remove from [l] all elements for which [f] returns
[false]. This is an O(N) operation. *)
module Iterator :
sig
val make : 'a t -> 'a iterator
(** [make l] creates an iterator initially pointing to the first
node of the list. Take care that iterators acts on the
mutable list [l], so changes in [l] influence iterators and
[l] can be modified through iterators. This is an O(1)
operation. *)
val get : 'a iterator -> 'a
(** Given a node, get the data associated with that node. This is
an O(1) operation.
@raise Failure if the list is empty. *)
val set : 'a -> 'a iterator -> unit
(** Given a node, set the data associated with that node. This is
an O(1) operation.
@raise Failure if the list is empty. *)
val next : 'a iterator -> unit
(** Move the iterator on the next node. The iterator is circular,
so the last node of the list returns the first node of the
list as it's next node. This is an O(1) operation. *)
val prev : 'a iterator -> unit
(** Move the iterator on the previous node. The iterator is
circular, so the first node of the list returns the last
element of the list as it's previous node. This is an O(1)
operation. *)
val skip : 'a iterator -> int -> unit
(** [skip it n] advance the iterator by [n] nodes. If [n] is
negative then return the node that is [-n] nodes before node
pointed by [it] in the list. This is an O(n) operation. *)
val add : 'a -> 'a iterator -> unit
(** [add n a] creates a new node containing data [a] and inserts
it into the list after node [n]. If the list is empty, this
creates the first node. This is an O(1) operation. *)
val append : 'a -> 'a iterator -> unit
(** [append n a] Creates a new node containing data [a], inserts
it into the list after node [n] and points the iterator on the
new node. If the list is empty, this creates the first node.
This is an O(1) operation. *)
val prepend : 'a -> 'a iterator -> unit
(** [prepend n a] Creates a new node containing data [a], inserts
it into the list before node [n] and points the iterator on
the new node. If the list is empty, this creates the first
node. This is an O(1) operation. *)
val promote : 'a iterator -> unit
(** [promote n] Swaps [n] with [next n]. If the list has less
than one element, it does nothing. This is an O(1) operation. *)
val demote : 'a iterator -> unit
(** [demote n] Swaps [n] with [prev n]. This is an O(1) operation. *)
val remove : 'a iterator -> unit
(** [remove n] remove the node pointed by [n] from the list and
move the iterator on the next node (if the list has other
elements). If the list is empty, it does nothing. The {i
first} move of other iterator pointing to the deleted node
will will behave like if the deletion did not happen. This is
an O(1) operation. *)
val rev_remove : 'a iterator -> unit
(** [remove n] remove the node pointed by [n] from the list and
move the iterator on the previous node (if the list has other
elements). The {i first} move of other iterator pointing to
the deleted node will will behave like if the deletion did not
happen. This is an O(1) operation. *)
val iter : ('a -> unit) -> 'a iterator -> unit
(** [iter f n] apply [f] to every element in the list, starting at
the position pointed by the iterator. This is an O(N)
operation. *)
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b iterator -> 'a
(** Accumulate a value over the entire list, starting at the
position pointed by the iterator. This works like
List.fold_left. This is an O(N) operation. *)
val fold_right : ('a -> 'b -> 'b) -> 'a iterator -> 'b -> 'b
(** Accumulate a value over the entire list, starting at the
position pointed by the iterator. This works like
List.fold_right, but since the list is bidirectional, it
doesn't suffer the recursion depth problems of
List.fold_right. This is an O(N) operation. *)
val map : ('a -> 'b) -> 'a iterator -> 'b t
(** Allocate a new list, with entirely new nodes, whose values are
the transforms of the values of the original list, starting at
the position pointed by the iterator. Note that this does not
modify the given list. This is an O(N) operation. *)
end
(** {6 List conversion} *)
val to_list : 'a t -> 'a list
(** Converts a dllist to a normal list. This is an O(N) operation. *)
val of_list : 'a list -> 'a t
(** Converts from a normal list to a Dllist and returns the first
node. This is an O(N) operation. *)
(** {6 Enums} *)
val enum : 'a t -> 'a Enum.t
(** Create an enum of the list. Note that modifying the list while
the enum exists will have undefined effects. This is an O(1)
operation. *)
val rev_enum : 'a t -> 'a Enum.t
(** Create a enum of the reversed list. Note that modifying the
list while the enum exists will have undefined effects. This is
an O(1) operation. *)
val of_enum : 'a Enum.t -> 'a t
(** Create a dllist from an enum. This consumes the enum, and
allocates a whole new dllist. This is an O(N) operation. *)