anil.recoil.org
My working unpac repository
1(**************************************************************************)
2(* *)
3(* OCaml *)
4(* *)
5(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
6(* *)
7(* Copyright 1996 Institut National de Recherche en Informatique et *)
8(* en Automatique. *)
9(* *)
10(* All rights reserved. This file is distributed under the terms of *)
11(* the GNU Lesser General Public License version 2.1, with the *)
12(* special exception on linking described in the file LICENSE. *)
13(* *)
14(**************************************************************************)
15
16(** First-in first-out queues.
17
18 This module implements queues (FIFOs), with in-place modification.
19 See {{!examples} the example section} below.
20*)
21
22(** {b Unsynchronized accesses} *)
23
24[@@@alert unsynchronized_access
25 "Unsynchronized accesses to queues are a programming error."
26]
27
28(**
29 Unsynchronized accesses to a queue may lead to an invalid queue state.
30 Thus, concurrent accesses to queues must be synchronized (for instance
31 with a {!Mutex.t}).
32*)
33
34type !'a t
35(** The type of queues containing elements of type ['a]. *)
36
37
38exception Empty
39(** Raised when {!Queue.take} or {!Queue.peek} is applied to an empty queue. *)
40
41
42val create : unit -> 'a t
43(** Return a new queue, initially empty. *)
44
45val add : 'a -> 'a t -> unit
46(** [add x q] adds the element [x] at the end of the queue [q]. *)
47
48val push : 'a -> 'a t -> unit
49(** [push] is a synonym for [add]. *)
50
51val take : 'a t -> 'a
52(** [take q] removes and returns the first element in queue [q],
53 or raises {!Empty} if the queue is empty. *)
54
55val take_opt : 'a t -> 'a option
56(** [take_opt q] removes and returns the first element in queue [q],
57 or returns [None] if the queue is empty.
58 @since 4.08 *)
59
60val pop : 'a t -> 'a
61(** [pop] is a synonym for [take]. *)
62
63val peek : 'a t -> 'a
64(** [peek q] returns the first element in queue [q], without removing
65 it from the queue, or raises {!Empty} if the queue is empty. *)
66
67val peek_opt : 'a t -> 'a option
68(** [peek_opt q] returns the first element in queue [q], without removing
69 it from the queue, or returns [None] if the queue is empty.
70 @since 4.08 *)
71
72val top : 'a t -> 'a
73(** [top] is a synonym for [peek]. *)
74
75val drop : 'a t -> unit
76(** [drop q] removes the first element in queue [q], or raises {!Empty}
77 if the queue is empty.
78 @since 5.3 *)
79
80val clear : 'a t -> unit
81(** Discard all elements from a queue. *)
82
83val copy : 'a t -> 'a t
84(** Return a copy of the given queue. *)
85
86val is_empty : 'a t -> bool
87(** Return [true] if the given queue is empty, [false] otherwise. *)
88
89val length : 'a t -> int
90(** Return the number of elements in a queue. *)
91
92val iter : ('a -> unit) -> 'a t -> unit
93(** [iter f q] applies [f] in turn to all elements of [q],
94 from the least recently entered to the most recently entered.
95 The queue itself is unchanged. *)
96
97val fold : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc
98(** [fold f accu q] is equivalent to [List.fold_left f accu l],
99 where [l] is the list of [q]'s elements. The queue remains
100 unchanged. *)
101
102val transfer : 'a t -> 'a t -> unit
103(** [transfer q1 q2] adds all of [q1]'s elements at the end of
104 the queue [q2], then clears [q1]. It is equivalent to the
105 sequence [iter (fun x -> add x q2) q1; clear q1], but runs
106 in constant time. *)
107
108(** {1 Iterators} *)
109
110val to_seq : 'a t -> 'a Seq.t
111(** Iterate on the queue, in front-to-back order.
112 The behavior is not specified if the queue is modified
113 during the iteration.
114 @since 4.07 *)
115
116val add_seq : 'a t -> 'a Seq.t -> unit
117(** Add the elements from a sequence to the end of the queue.
118 @since 4.07 *)
119
120val of_seq : 'a Seq.t -> 'a t
121(** Create a queue from a sequence.
122 @since 4.07 *)
123
124(** {1:examples Examples}
125
126 {2 Basic Example}
127
128 A basic example:
129 {[
130 # let q = Queue.create ()
131 val q : '_weak1 Queue.t = <abstr>
132
133
134 # Queue.push 1 q; Queue.push 2 q; Queue.push 3 q
135 - : unit = ()
136
137 # Queue.length q
138 - : int = 3
139
140 # Queue.pop q
141 - : int = 1
142
143 # Queue.pop q
144 - : int = 2
145
146 # Queue.pop q
147 - : int = 3
148
149 # Queue.pop q
150 Exception: Stdlib.Queue.Empty.
151 ]}
152
153 {2 Search Through a Graph}
154
155 For a more elaborate example, a classic algorithmic use of queues
156 is to implement a BFS (breadth-first search) through a graph.
157
158 {[
159 type graph = {
160 edges: (int, int list) Hashtbl.t
161 }
162
163 (* Search in graph [g] using BFS, starting from node [start].
164 It returns the first node that satisfies [p], or [None] if
165 no node reachable from [start] satisfies [p].
166 *)
167 let search_for ~(g:graph) ~(start:int) (p:int -> bool) : int option =
168 let to_explore = Queue.create() in
169 let explored = Hashtbl.create 16 in
170
171 Queue.push start to_explore;
172 let rec loop () =
173 if Queue.is_empty to_explore then None
174 else
175 (* node to explore *)
176 let node = Queue.pop to_explore in
177 explore_node node
178
179 and explore_node node =
180 if not (Hashtbl.mem explored node) then (
181 if p node then Some node (* found *)
182 else (
183 Hashtbl.add explored node ();
184 let children =
185 Hashtbl.find_opt g.edges node
186 |> Option.value ~default:[]
187 in
188 List.iter (fun child -> Queue.push child to_explore) children;
189 loop()
190 )
191 ) else loop()
192 in
193 loop()
194
195 (* a sample graph *)
196 let my_graph: graph =
197 let edges =
198 List.to_seq [
199 1, [2;3];
200 2, [10; 11];
201 3, [4;5];
202 5, [100];
203 11, [0; 20];
204 ]
205 |> Hashtbl.of_seq
206 in {edges}
207
208 # search_for ~g:my_graph ~start:1 (fun x -> x = 30)
209 - : int option = None
210
211 # search_for ~g:my_graph ~start:1 (fun x -> x >= 15)
212 - : int option = Some 20
213
214 # search_for ~g:my_graph ~start:1 (fun x -> x >= 50)
215 - : int option = Some 100
216 ]}
217 *)