(*
* Dllist- a mutable, circular, doubly linked list library
* Copyright (C) 2004 Brian Hurt
*
* 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, imperitive, circular, doubly linked list library
*
* This module implements a doubly linked list in a mutable or imperitive
* style (changes to the list are visible to all copies of the list).
*)
type 'a node_t (* abstract *)
type 'a t (* abstract *)
exception Empty (** Raised when {!head} or {!remove} is called on
* an empty list
*)
(** Creates an empty list. This is an O(1) operation. *)
val create : unit -> 'a t
(** Returns the length of the list. This is an O(N) operation. *)
val length : 'a t -> int
(** Adds an element onto the end of the list. This is an O(1) operation. *)
val append : 'a t -> 'a -> 'a node_t
(** Adds an element onto the begining of the list. This is an O(1)
* operation.
*)
val prepend : 'a t -> 'a -> 'a node_t
(** Returns the first element of the list. This is an O(1) operation. *)
val first : 'a t -> 'a
(** Returns the list element of the list. This is an O(1) operation. *)
val last : 'a t -> 'a
(** Returns the nth element of the list. This is an O(N) operation.
* This function will call invalid_arg if the index passed in is equal
* to or greater than the length of the list or is negative.
*)
val nth : 'a t -> int -> 'a
(** Returns the node of the first element in the list. This is an
* O(1) operation.
*)
val first_node : 'a t -> 'a node_t
(** Returns the node of the last element in the list. This is an
* O(1) operation.
*)
val last_node : 'a t -> 'a node_t
(** Return the node of the nth element in the list. This is an O(N)
* operation.
*)
val nth_node : 'a t -> int -> 'a node_t
(** Remove (and return) the first element of the list. This is an O(1)
* operation.
*)
val remove_first : 'a t -> 'a
(** Remove (and return) the last element of the list. This is an O(1)
* operation.
*)
val remove_last : 'a t -> 'a
(** Remove (and return) the nth element of a list. This is an O(1)
* operation.
*)
val remove_nth : 'a t -> int -> 'a
(** Given a node, remove that node from the list no matter where it is.
* This is an O(1) operation.
*)
val remove_node : 'a t -> 'a node_t -> 'a
(** Converts a dllist to a normal list. This is an O(N) operation. *)
val to_list : 'a t -> 'a list
(** Converts from a normal list to a Dllist.t. This is an O(N) operation. *)
val of_list : 'a list -> 'a t
(** Given a node, get the element associated with that node. This is an
* O(1) operation.
*)
val node_data : 'a node_t -> 'a
(** Given a node, get the next element in the list after the node.
*
* The list is circular, so the last node of the list returns the first
* node of the list as it's next node. Check against {!first_node} to
* detect this.
*
* This is an O(1) operation.
*
*)
val node_next : 'a node_t -> 'a node_t
(** Given a node, get the previous element in the list before the node.
*
* The list is circular, so the first node of the list returns the
* last element of the list as it's previous node. Check against
* {!last_node} to detect this.
*
* This is an O(1) operation.
*)
val node_prev : 'a node_t -> 'a node_t
(** Call a function on every element of a list. This is an O(N) operation. *)
val iter : ('a -> unit) -> 'a t -> unit
(** Accumulate a value over the entire list.
* This works like List.fold_left. 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_right, but since the list is bidirectional,
* it doesn't suffer the performance problems of List.fold_right.
* This is an O(N) operation.
*)
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** 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 map : ('a -> 'b) -> 'a t -> 'b 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 enum : 'a t -> 'a Enum.t
(** Create a list from an enum.
* This consumes the enum, and allocates a whole new dllist.
* This is an O(N) operation.
*)
val of_enum : 'a Enum.t -> 'a t