bundles/extlib/extlib-1.5.2/dllist.mli

   1 (*
   2  * Dllist- a mutable, circular, doubly linked list library
   3  * Copyright (C) 2004 Brian Hurt, Jesse Guardiani
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version,
   9  * with the special exception on linking described in file LICENSE.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *)
  20
  21 (** A mutable, imperative, circular, doubly linked list library
  22
  23     This module implements a doubly linked list in a mutable or imperitive
  24     style (changes to the list are visible to all copies of the list).
  25 *)
  26
  27
  28 type 'a node_t (* abstract *)
  29
  30 exception Empty
  31
  32 (** {6 node functions } *)
  33
  34 (** Creates a node.  This is an O(1) operation. *)
  35 val create : 'a -> 'a node_t
  36
  37 (** Copy the list attached to the given node and return the copy of the given
  38     node.  This is an O(N) operation.
  39 *)
  40 val copy : 'a node_t -> 'a node_t
  41
  42 (** Returns the length of the list.  This is an O(N) operation. *)
  43 val length : 'a node_t -> int
  44
  45 (** List reversal.  This is an O(N) operation.
  46 *)
  47 val rev : 'a node_t -> unit
  48
  49 (** [add n a] Creates a new node containing data [a] and inserts it into
  50     the list after node [n].  This is an O(1) operation.
  51 *)
  52 val add : 'a node_t -> 'a -> unit
  53
  54 (** [append n a] Creates a new node containing data [a] and inserts it into
  55     the list after node [n]. Returns new node.  This is an O(1) operation.
  56 *)
  57 val append : 'a node_t -> 'a -> 'a node_t
  58
  59 (** [prepend n a] Creates a new node containing data [a] and inserts it into
  60     the list before node [n]. Returns new node.  This is an O(1) operation.
  61 *)
  62 val prepend : 'a node_t -> 'a -> 'a node_t
  63
  64 (** [promote n] Swaps [n] with [next n].  This is an O(1) operation.
  65 *)
  66 val promote : 'a node_t -> unit
  67
  68 (** [demote n] Swaps [n] with [prev n].  This is an O(1) operation.
  69 *)
  70 val demote : 'a node_t -> unit
  71
  72 (** Remove node from the list no matter where it is.  This is an O(1) operation.
  73 *)
  74 val remove : 'a node_t -> unit
  75
  76 (** Remove node from the list no matter where it is. Return next node.  This is
  77     an O(1) operation.
  78 *)
  79 val drop : 'a node_t -> 'a node_t
  80
  81 (** Remove node from the list no matter where it is. Return previous node.  This
  82     is an O(1) operation.
  83 *)
  84 val rev_drop : 'a node_t -> 'a node_t
  85
  86 (** [splice n1 n2] Connects [n1] and [n2] so that
  87     [next n1 == n2 && prev n2 == n1]. This can be used to connect two discrete
  88     lists, or, if used on two nodes within the same list, it can be used to
  89     separate the nodes between [n1] and [n2] from the rest of the list. In this
  90     case, those nodes become a discrete list by themselves.  This is an O(1)
  91     operation.
  92 *)
  93 val splice : 'a node_t -> 'a node_t -> unit
  94
  95 (** Given a node, get the data associated with that node.  This is an
  96     O(1) operation.
  97 *)
  98 val get : 'a node_t -> 'a
  99
 100 (** Given a node, set the data associated with that node.  This is an O(1)
 101     operation.
 102 *)
 103 val set : 'a node_t -> 'a -> unit
 104
 105 (** Given a node, get the next element in the list after the node.
 106
 107     The list is circular, so the last node of the list returns the first
 108     node of the list as it's next node.
 109
 110     This is an O(1) operation.
 111 *)
 112 val next : 'a node_t -> 'a node_t
 113
 114 (** Given a node, get the previous element in the list before the node.
 115
 116     The list is circular, so the first node of the list returns the
 117     last element of the list as it's previous node.
 118
 119     This is an O(1) operation.
 120 *)
 121 val prev : 'a node_t -> 'a node_t
 122
 123 (** [skip n i] Return the node that is [i] nodes after node [n] in the list.
 124     If [i] is negative then return the node that is [i] nodes before node [n]
 125     in the list.  This is an O(N) operation.
 126 *)
 127 val skip : 'a node_t -> int -> 'a node_t
 128
 129 (** [iter f n] Apply [f] to every element in the list, starting at [n].  This
 130     is an O(N) operation.
 131 *)
 132 val iter : ('a -> unit) -> 'a node_t -> unit
 133
 134 (** Accumulate a value over the entire list.
 135     This works like List.fold_left. This is an O(N) operation.
 136 *)
 137 val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b node_t -> 'a
 138
 139 (** Accumulate a value over the entire list.
 140     This works like List.fold_right, but since the list is bidirectional,
 141     it doesn't suffer the performance problems of List.fold_right.
 142     This is an O(N) operation.
 143 *)
 144 val fold_right : ('a -> 'b -> 'b) -> 'a node_t -> 'b -> 'b
 145
 146 (** Allocate a new list, with entirely new nodes, whose values are
 147     the transforms of the values of the original list.  Note that this
 148     does not modify the given list.  This is an O(N) operation.
 149 *)
 150 val map : ('a -> 'b) -> 'a node_t -> 'b node_t
 151
 152
 153 (** {6 list conversion } *)
 154
 155 (** Converts a dllist to a normal list.  This is an O(N) operation. *)
 156 val to_list : 'a node_t -> 'a list
 157
 158 (** Converts from a normal list to a Dllist and returns the first node. Raises
 159     [Empty] if given list is empty.  This is an O(N) operation.
 160 *)
 161 val of_list : 'a list -> 'a node_t
 162
 163
 164 (** {6 enums } *)
 165
 166 (** Create an enum of the list.
 167     Note that modifying the list while the enum exists will have undefined
 168     effects.  This is an O(1) operation.
 169 *)
 170 val enum : 'a node_t -> 'a Enum.t
 171
 172 (** Create a reverse enum of the list.
 173     Note that modifying the list while the enum exists will have undefined
 174     effects.  This is an O(1) operation.
 175 *)
 176 val rev_enum : 'a node_t -> 'a Enum.t
 177
 178 (** Create a dllist from an enum.
 179     This consumes the enum, and allocates a whole new dllist. Raises
 180     [Empty] if given enum is empty.  This is an O(N) operation.
 181 *)
 182 val of_enum : 'a Enum.t -> 'a node_t