(* 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. *)