1queue(3) Erlang Module Definition queue(3)
2
6 queue - Abstract data type for FIFO queues.
7
9 This module provides (double-ended) FIFO queues in an efficient manner.
10 All functions fail with reason badarg if arguments are of wrong type,
12 for example, queue arguments are not queues, indexes are not integers,
13 and list arguments are not lists. Improper lists cause internal
14 crashes. An index out of range for a queue also causes a failure with
15 reason badarg.
16 Some functions, where noted, fail with reason empty for an empty queue.
18 The data representing a queue as used by this module is to be regarded
20 as opaque by other modules. Any code assuming knowledge of the format
21 is running on thin ice.
22 All operations have an amortized O(1) running time, except all/2,
24 any/2, delete/2, delete_r/2, delete_with/2, delete_with_r/2, filter/2,
25 filtermap/2, fold/3, join/2, len/1, member/2, split/2 that have O(n).
26 To minimize the size of a queue minimizing the amount of garbage built
27 by queue operations, the queues do not contain explicit length informa‐
28 tion, and that is why len/1 is O(n). If better performance for this
29 particular operation is essential, it is easy for the caller to keep
30 track of the length.
31 Queues are double-ended. The mental picture of a queue is a line of
33 people (items) waiting for their turn. The queue front is the end with
34 the item that has waited the longest. The queue rear is the end an item
35 enters when it starts to wait. If instead using the mental picture of a
36 list, the front is called head and the rear is called tail.
37 Entering at the front and exiting at the rear are reverse operations on
39 the queue.
40 This module has three sets of interface functions: the "Original API",
42 the "Extended API", and the "Okasaki API".
43 The "Original API" and the "Extended API" both use the mental picture
45 of a waiting line of items. Both have reverse operations suffixed "_r".
46 The "Original API" item removal functions return compound terms with
48 both the removed item and the resulting queue. The "Extended API" con‐
49 tains alternative functions that build less garbage and functions for
50 just inspecting the queue ends. Also the "Okasaki API" functions build
51 less garbage.
52 The "Okasaki API" is inspired by "Purely Functional Data Structures" by
54 Chris Okasaki. It regards queues as lists. This API is by many regarded
55 as strange and avoidable. For example, many reverse operations have
56 lexically reversed names, some with more readable but perhaps less un‐
57 derstandable aliases.
58
60 queue(Item)
61 As returned by new/0.
63 queue() = queue(term())
65
68 all(Pred, Q :: queue(Item)) -> boolean()
69 Types:
71 Pred = fun((Item) -> boolean())
73 Returns true if Pred(Item) returns true for all items Item in Q,
75 otherwise false.
76 any(Pred, Q :: queue(Item)) -> boolean()
78 Types:
80 Pred = fun((Item) -> boolean())
82 Returns true if Pred(Item) returns true for at least one item
84 Item in Q, otherwise false.
85 delete(Item, Q1) -> Q2
87 Types:
89 Item = T
91 Q1 = Q2 = queue(T)
92 T = term()
93 Returns a copy of Q1 where the first item matching Item is
95 deleted, if there is such an item.
96 delete_r(Item, Q1) -> Q2
98 Types:
100 Item = T
102 Q1 = Q2 = queue(T)
103 T = term()
104 Returns a copy of Q1 where the last item matching Item is
106 deleted, if there is such an item.
107 delete_with(Pred, Q1) -> Q2
109 Types:
111 Pred = fun((Item) -> boolean())
113 Q1 = Q2 = queue(Item)
114 Item = term()
115 Returns a copy of Q1 where the first item for which Pred returns
117 true is deleted, if there is such an item.
118 delete_with_r(Pred, Q1) -> Q2
120 Types:
122 Pred = fun((Item) -> boolean())
124 Q1 = Q2 = queue(Item)
125 Item = term()
126 Returns a copy of Q1 where the last item for which Pred returns
128 true is deleted, if there is such an item.
129 filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item)
131 Types:
133 Fun = fun((Item) -> boolean() | [Item])
135 Returns a queue Q2 that is the result of calling Fun(Item) on
137 all items in Q1.
138 If Fun(Item) returns true, Item is copied to the result queue.
140 If it returns false, Item is not copied. If it returns a list,
141 the list elements are inserted instead of Item in the result
142 queue.
143 So, Fun(Item) returning [Item] is thereby semantically equiva‐
145 lent to returning true, just as returning [] is semantically
146 equivalent to returning false. But returning a list builds more
147 garbage than returning an atom.
148 filtermap(Fun, Q1) -> Q2
150 Types:
152 Fun = fun((Item) -> boolean() | {true, Value})
154 Q1 = queue(Item)
155 Q2 = queue(Item | Value)
156 Item = Value = term()
157 Returns a queue Q2 that is the result of calling Fun(Item) on
159 all items in Q1.
160 If Fun(Item) returns true, Item is copied to the result queue.
162 If it returns false, Item is not copied. If it returns {true,
163 NewItem}, the queue element at this position is replaced with
164 NewItem in the result queue.
165 fold(Fun, Acc0, Q :: queue(Item)) -> Acc1
167 Types:
169 Fun = fun((Item, AccIn) -> AccOut)
171 Acc0 = Acc1 = AccIn = AccOut = term()
172 Calls Fun(Item, AccIn) on successive items Item of Queue, start‐
174 ing with AccIn == Acc0. The queue is traversed in queue order,
175 that is, from front to rear. Fun/2 must return a new accumula‐
176 tor, which is passed to the next call. The function returns the
177 final value of the accumulator. Acc0 is returned if the queue is
178 empty.
179 Example:
181 > queue:fold(fun(X, Sum) -> X + Sum end, 0, queue:from_list([1,2,3,4,5])).
183 15
184 > queue:fold(fun(X, Prod) -> X * Prod end, 1, queue:from_list([1,2,3,4,5])).
185 120
186 from_list(L :: [Item]) -> queue(Item)
188 Returns a queue containing the items in L in the same order; the
190 head item of the list becomes the front item of the queue.
191 in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
193 Inserts Item at the rear of queue Q1. Returns the resulting
195 queue Q2.
196 in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
198 Inserts Item at the front of queue Q1. Returns the resulting
200 queue Q2.
201 is_empty(Q :: queue()) -> boolean()
203 Tests if Q is empty and returns true if so, otherwise false.
205 is_queue(Term :: term()) -> boolean()
207 Tests if Term is a queue and returns true if so, otherwise
209 false.
210 join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item)
212 Returns a queue Q3 that is the result of joining Q1 and Q2 with
214 Q1 in front of Q2.
215 len(Q :: queue()) -> integer() >= 0
217 Calculates and returns the length of queue Q.
219 member(Item, Q :: queue(Item)) -> boolean()
221 Returns true if Item matches some element in Q, otherwise false.
223 new() -> queue()
225 Returns an empty queue.
227 out(Q1 :: queue(Item)) ->
229 {{value, Item}, Q2 :: queue(Item)} |
230 {empty, Q1 :: queue(Item)}
231 Removes the item at the front of queue Q1. Returns tuple
233 {{value, Item}, Q2}, where Item is the item removed and Q2 is
234 the resulting queue. If Q1 is empty, tuple {empty, Q1} is re‐
235 turned.
236 out_r(Q1 :: queue(Item)) ->
238 {{value, Item}, Q2 :: queue(Item)} |
239 {empty, Q1 :: queue(Item)}
240 Removes the item at the rear of queue Q1. Returns tuple {{value,
242 Item}, Q2}, where Item is the item removed and Q2 is the new
243 queue. If Q1 is empty, tuple {empty, Q1} is returned.
244 reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item)
246 Returns a queue Q2 containing the items of Q1 in the reverse or‐
248 der.
249 split(N :: integer() >= 0, Q1 :: queue(Item)) ->
251 {Q2 :: queue(Item), Q3 :: queue(Item)}
252 Splits Q1 in two. The N front items are put in Q2 and the rest
254 in Q3.
255 to_list(Q :: queue(Item)) -> [Item]
257 Returns a list of the items in the queue in the same order; the
259 front item of the queue becomes the head of the list.
260
263 drop(Q1 :: queue(Item)) -> Q2 :: queue(Item)
264 Returns a queue Q2 that is the result of removing the front item
266 from Q1.
267 Fails with reason empty if Q1 is empty.
269 drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item)
271 Returns a queue Q2 that is the result of removing the rear item
273 from Q1.
274 Fails with reason empty if Q1 is empty.
276 get(Q :: queue(Item)) -> Item
278 Returns Item at the front of queue Q.
280 Fails with reason empty if Q is empty.
282 get_r(Q :: queue(Item)) -> Item
284 Returns Item at the rear of queue Q.
286 Fails with reason empty if Q is empty.
288 peek(Q :: queue(Item)) -> empty | {value, Item}
290 Returns tuple {value, Item}, where Item is the front item of Q,
292 or empty if Q is empty.
293 peek_r(Q :: queue(Item)) -> empty | {value, Item}
295 Returns tuple {value, Item}, where Item is the rear item of Q,
297 or empty if Q is empty.
298
301 cons(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
302 Inserts Item at the head of queue Q1. Returns the new queue Q2.
304 daeh(Q :: queue(Item)) -> Item
306 Returns the tail item of queue Q.
308 Fails with reason empty if Q is empty.
310 head(Q :: queue(Item)) -> Item
312 Returns Item from the head of queue Q.
314 Fails with reason empty if Q is empty.
316 init(Q1 :: queue(Item)) -> Q2 :: queue(Item)
318 Returns a queue Q2 that is the result of removing the tail item
320 from Q1.
321 Fails with reason empty if Q1 is empty.
323 lait(Q1 :: queue(Item)) -> Q2 :: queue(Item)
325 Returns a queue Q2 that is the result of removing the tail item
327 from Q1.
328 Fails with reason empty if Q1 is empty.
330 The name lait/1 is a misspelling - do not use it anymore.
332 last(Q :: queue(Item)) -> Item
334 Returns the tail item of queue Q.
336 Fails with reason empty if Q is empty.
338 liat(Q1 :: queue(Item)) -> Q2 :: queue(Item)
340 Returns a queue Q2 that is the result of removing the tail item
342 from Q1.
343 Fails with reason empty if Q1 is empty.
345 snoc(Q1 :: queue(Item), Item) -> Q2 :: queue(Item)
347 Inserts Item as the tail item of queue Q1. Returns the new queue
349 Q2.
350 tail(Q1 :: queue(Item)) -> Q2 :: queue(Item)
352 Returns a queue Q2 that is the result of removing the head item
354 from Q1.
355 Fails with reason empty if Q1 is empty.
357Ericsson AB stdlib 3.16.1 queue(3)