(*
* Dllist
* Copyright (C) 2004 Brian Hurt, Jesse Guardiani
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version,
* 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 GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*)
(** A mutable, imperative, doubly linked list library with 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).
*)
type 'a t (** Doubly linked list *)
type 'a iterator (** Circular iterator *)
val make : 'a -> 'a t
(** Creates an empty list. This is an O(1) operation. *)
val copy : 'a t -> 'a t
(** Copy the list attached to the given node and return the copy of
the given node. This is an O(N) operation. *)
val length : 'a t -> int
(** Returns the length of the list. This is an O(N) operation. *)
val rev : 'a t -> unit
(** In place list reversal. This is an O(N) operation. *)
val append : 'a t -> 'a -> unit
(** [append l a] inserts [a] at the end of the list [l]. This is an
O(1) operation. *)
val prepend : 'a t -> 'a -> 'a t
(** [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 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. *)
module Iterator :
sig
val make : 'a t -> 'a iterator
(** [make l] creates an iterator initially pointing to the first
node of the list. *)
val add : 'a iterator -> 'a -> 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 iterator -> 'a -> 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 iterator -> 'a -> 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). 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). This is an O(1) operation. *)
val splice : 'a iterator -> 'a iterator -> unit
(** [splice n1 n2] Connects [n1] and [n2] so that [next n1 == n2
&& prev n2 == n1]. This can be used to connect two discrete
lists, or, if used on two nodes within the same list, it can be
used to separate the nodes between [n1] and [n2] from the rest
of the list. In this case, those nodes become a discrete list by
themselves. 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 iterator -> 'a -> 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 node_t -> int -> 'a node_t
(** [skip n i] Return the node that is [i] nodes after node [n] in
the list. If [i] is negative then return the node that is [i]
nodes before node [n] in the list. This is an O(N) 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 node_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 reverse enum of the 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. *)