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. In abstract terms, the representation is a
21 composite type of existing Erlang terms. See note on data types. Any
22 code assuming knowledge of the format is running on thin ice.
23 All operations have an amortized O(1) running time, except all/2,
25 any/2, delete/2, delete_r/2, delete_with/2, delete_with_r/2, filter/2,
26 filtermap/2, fold/3, join/2, len/1, member/2, split/2 that have O(n).
27 To minimize the size of a queue minimizing the amount of garbage built
28 by queue operations, the queues do not contain explicit length informa‐
29 tion, and that is why len/1 is O(n). If better performance for this
30 particular operation is essential, it is easy for the caller to keep
31 track of the length.
32 Queues are double-ended. The mental picture of a queue is a line of
34 people (items) waiting for their turn. The queue front is the end with
35 the item that has waited the longest. The queue rear is the end an item
36 enters when it starts to wait. If instead using the mental picture of a
37 list, the front is called head and the rear is called tail.
38 Entering at the front and exiting at the rear are reverse operations on
40 the queue.
41 This module has three sets of interface functions: the "Original API",
43 the "Extended API", and the "Okasaki API".
44 The "Original API" and the "Extended API" both use the mental picture
46 of a waiting line of items. Both have reverse operations suffixed "_r".
47 The "Original API" item removal functions return compound terms with
49 both the removed item and the resulting queue. The "Extended API" con‐
50 tains alternative functions that build less garbage and functions for
51 just inspecting the queue ends. Also the "Okasaki API" functions build
52 less garbage.
53 The "Okasaki API" is inspired by "Purely Functional Data Structures" by
55 Chris Okasaki. It regards queues as lists. This API is by many regarded
56 as strange and avoidable. For example, many reverse operations have
57 lexically reversed names, some with more readable but perhaps less un‐
58 derstandable aliases.
59
61 queue(Item)
62 As returned by new/0.
64 queue() = queue(term())
66
69 all(Pred, Q :: queue(Item)) -> boolean()
70 Types:
72 Pred = fun((Item) -> boolean())
74 Returns true if Pred(Item) returns true for all items Item in Q,
76 otherwise false.
77 Example:
79 1> Queue = queue:from_list([1,2,3,4,5]).
81 2> queue:all(fun (E) -> E > 3 end, Queue).
82 false
83 3> queue:all(fun (E) -> E > 0 end, Queue).
84 true
85 any(Pred, Q :: queue(Item)) -> boolean()
87 Types:
89 Pred = fun((Item) -> boolean())
91 Returns true if Pred(Item) returns true for at least one item
93 Item in Q, otherwise false.
94 Example:
96 1> Queue = queue:from_list([1,2,3,4,5]).
98 2> queue:any(fun (E) -> E > 10 end, Queue).
99 false
100 3> queue:any(fun (E) -> E > 3 end, Queue).
101 true
102 delete(Item, Q1) -> Q2
104 Types:
106 Item = T
108 Q1 = Q2 = queue(T)
109 T = term()
110 Returns a copy of Q1 where the first item matching Item is
112 deleted, if there is such an item.
113 Example:
115 1> Queue = queue:from_list([1,2,3,4,5]).
117 2> Queue1 = queue:delete(3, Queue).
118 3> queue:member(3, Queue1).
119 false
120 delete_r(Item, Q1) -> Q2
122 Types:
124 Item = T
126 Q1 = Q2 = queue(T)
127 T = term()
128 Returns a copy of Q1 where the last item matching Item is
130 deleted, if there is such an item.
131 Example:
133 1> Queue = queue:from_list([1,2,3,4,3,5]).
135 2> Queue1 = queue:delete_r(3, Queue).
136 3> queue:to_list(Queue1).
137 [1,2,3,4,5]
138 delete_with(Pred, Q1) -> Q2
140 Types:
142 Pred = fun((Item) -> boolean())
144 Q1 = Q2 = queue(Item)
145 Item = term()
146 Returns a copy of Q1 where the first item for which Pred returns
148 true is deleted, if there is such an item.
149 Example:
151 1> Queue = queue:from_list([100,1,2,3,4,5]).
153 2> Queue1 = queue:delete_with(fun (E) -> E > 0, Queue).
154 3> queue:to_list(Queue1).
155 [1,2,3,4,5]
156 delete_with_r(Pred, Q1) -> Q2
158 Types:
160 Pred = fun((Item) -> boolean())
162 Q1 = Q2 = queue(Item)
163 Item = term()
164 Returns a copy of Q1 where the last item for which Pred returns
166 true is deleted, if there is such an item.
167 Example:
169 1> Queue = queue:from_list([1,2,3,4,5,100]).
171 2> Queue1 = queue:delete_with(fun (E) -> E > 10, Queue).
172 3> queue:to_list(Queue1).
173 [1,2,3,4,5]
174 filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item)
176 Types:
178 Fun = fun((Item) -> boolean() | [Item])
180 Returns a queue Q2 that is the result of calling Fun(Item) on
182 all items in Q1.
183 If Fun(Item) returns true, Item is copied to the result queue.
185 If it returns false, Item is not copied. If it returns a list,
186 the list elements are inserted instead of Item in the result
187 queue.
188 Example 1:
190 1> Queue = queue:from_list([1,2,3,4,5]).
192 {[5,4,3],[1,2]}
193 2> Queue1 = queue:filter(fun (E) -> E > 2 end, Queue).
194 {[5],[3,4]}
195 3> queue:to_list(Queue1).
196 [3,4,5]
197 So, Fun(Item) returning [Item] is thereby semantically equiva‐
199 lent to returning true, just as returning [] is semantically
200 equivalent to returning false. But returning a list builds more
201 garbage than returning an atom.
202 Example 2:
204 1> Queue = queue:from_list([1,2,3,4,5]).
206 {[5,4,3],[1,2]}
207 2> Queue1 = queue:filter(fun (E) -> [E, E+1] end, Queue).
208 {[6,5,5,4,4,3],[1,2,2,3]}
209 3> queue:to_list(Queue1).
210 [1,2,2,3,3,4,4,5,5,6]
211 filtermap(Fun, Q1) -> Q2
213 Types:
215 Fun = fun((Item) -> boolean() | {true, Value})
217 Q1 = queue(Item)
218 Q2 = queue(Item | Value)
219 Item = Value = term()
220 Returns a queue Q2 that is the result of calling Fun(Item) on
222 all items in Q1.
223 If Fun(Item) returns true, Item is copied to the result queue.
225 If it returns false, Item is not copied. If it returns {true,
226 NewItem}, the queue element at this position is replaced with
227 NewItem in the result queue.
228 Example 1:
230 1> Queue = queue:from_list([1,2,3,4,5]).
232 {[5,4,3],[1,2]}
233 2> Queue1 = queue:filtermap(fun (E) -> E > 2 end, Queue).
234 {[5],[3,4]}
235 3> queue:to_list(Queue1).
236 [3,4,5]
237 4> Queue1 = queue:filtermap(fun (E) -> {true, E+100} end, Queue).
238 {"ihg","ef"}
239 5> queue:to_list(Queue1).
240 "efghi
241 fold(Fun, Acc0, Q :: queue(Item)) -> Acc1
243 Types:
245 Fun = fun((Item, AccIn) -> AccOut)
247 Acc0 = Acc1 = AccIn = AccOut = term()
248 Calls Fun(Item, AccIn) on successive items Item of Queue, start‐
250 ing with AccIn == Acc0. The queue is traversed in queue order,
251 that is, from front to rear. Fun/2 must return a new accumula‐
252 tor, which is passed to the next call. The function returns the
253 final value of the accumulator. Acc0 is returned if the queue is
254 empty.
255 Example:
257 1> queue:fold(fun(X, Sum) -> X + Sum end, 0, queue:from_list([1,2,3,4,5])).
259 15
260 2> queue:fold(fun(X, Prod) -> X * Prod end, 1, queue:from_list([1,2,3,4,5])).
261 120
262 from_list(L :: [Item]) -> queue(Item)
264 Returns a queue containing the items in L in the same order; the
266 head item of the list becomes the front item of the queue.
267 in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
269 Inserts Item at the rear of queue Q1. Returns the resulting
271 queue Q2.
272 Example:
274 1> Queue = queue:from_list([1,2,3,4,5]).
276 {[5,4,3],[1,2]}
277 2> Queue1 = queue:in(100, Queue).
278 {[100,5,4,3],[1,2]}
279 3> queue:to_list(Queue1).
280 [1,2,3,4,5,100]
281 in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
283 Inserts Item at the front of queue Q1. Returns the resulting
285 queue Q2.
286 Example:
288 1> Queue = queue:from_list([1,2,3,4,5]).
290 {[5,4,3],[1,2]}
291 2> Queue1 = queue:in_r(100, Queue).
292 {[5,4,3],[100,1,2]}
293 3> queue:to_list(Queue1).
294 [100,1,2,3,4,5]
295 is_empty(Q :: queue()) -> boolean()
297 Tests if Q is empty and returns true if so, otherwise false.
299 is_queue(Term :: term()) -> boolean()
301 Tests if Term is a queue and returns true if so, otherwise
303 false. Note that the test will return true for a term coinciding
304 with the representation of a queue, even when not constructed by
305 thus module. See also note on data types.
306 join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item)
308 Returns a queue Q3 that is the result of joining Q1 and Q2 with
310 Q1 in front of Q2.
311 Example:
313 1> Queue1 = queue:from_list([1,3]).
315 {[3],[1]}
316 2> Queue2 = queue:from_list([2,4]).
317 {[4],[2]}
318 3> queue:to_list(queue:join(Queue1, Queue2)).
319 [1,3,2,4]
320 len(Q :: queue()) -> integer() >= 0
322 Calculates and returns the length of queue Q.
324 member(Item, Q :: queue(Item)) -> boolean()
326 Returns true if Item matches some element in Q, otherwise false.
328 new() -> queue(none())
330 Returns an empty queue.
332 out(Q1 :: queue(Item)) ->
334 {{value, Item}, Q2 :: queue(Item)} |
335 {empty, Q1 :: queue(Item)}
336 Removes the item at the front of queue Q1. Returns tuple
338 {{value, Item}, Q2}, where Item is the item removed and Q2 is
339 the resulting queue. If Q1 is empty, tuple {empty, Q1} is re‐
340 turned.
341 Example:
343 1> Queue = queue:from_list([1,2,3,4,5]).
345 {[5,4,3],[1,2]}
346 2> {{value, 1=Item}, Queue1} = queue:out(Queue).
347 {{value,1},{[5,4,3],[2]}}
348 3> queue:to_list(Queue1).
349 [2,3,4,5]
350 out_r(Q1 :: queue(Item)) ->
352 {{value, Item}, Q2 :: queue(Item)} |
353 {empty, Q1 :: queue(Item)}
354 Removes the item at the rear of queue Q1. Returns tuple {{value,
356 Item}, Q2}, where Item is the item removed and Q2 is the new
357 queue. If Q1 is empty, tuple {empty, Q1} is returned.
358 Example:
360 1> Queue = queue:from_list([1,2,3,4,5]).
362 {[5,4,3],[1,2]}
363 2> {{value, 5=Item}, Queue1} = queue:out_r(Queue).
364 {{value,5},{[4,3],[1,2]}}
365 3> queue:to_list(Queue1).
366 [1,2,3,4]
367 reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item)
369 Returns a queue Q2 containing the items of Q1 in the reverse or‐
371 der.
372 split(N :: integer() >= 0, Q1 :: queue(Item)) ->
374 {Q2 :: queue(Item), Q3 :: queue(Item)}
375 Splits Q1 in two. The N front items are put in Q2 and the rest
377 in Q3.
378 to_list(Q :: queue(Item)) -> [Item]
380 Returns a list of the items in the queue in the same order; the
382 front item of the queue becomes the head of the list.
383 Example:
385 1> Queue = queue:from_list([1,2,3,4,5]).
387 {[5,4,3],[1,2]}
388 2> List == queue:to_list(Queue).
389 true
390
393 drop(Q1 :: queue(Item)) -> Q2 :: queue(Item)
394 Returns a queue Q2 that is the result of removing the front item
396 from Q1.
397 Fails with reason empty if Q1 is empty.
399 Example:
401 1> Queue = queue:from_list([1,2,3,4,5]).
403 {[5,4,3],[1,2]}
404 2> Queue = queue:drop(Queue).
405 {[5,4,3],[2]}
406 3> queue:to_list(Queue1).
407 [2,3,4,5]
408 drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item)
410 Returns a queue Q2 that is the result of removing the rear item
412 from Q1.
413 Fails with reason empty if Q1 is empty.
415 Example:
417 1> Queue = queue:from_list([1,2,3,4,5]).
419 {[5,4,3],[1,2]}
420 2> Queue = queue:drop_r(Queue).
421 {[4,3],[1,2]}
422 3> queue:to_list(Queue1).
423 [1,2,3,4]
424 get(Q :: queue(Item)) -> Item
426 Returns Item at the front of queue Q.
428 Fails with reason empty if Q is empty.
430 Example 1:
432 1> Queue = queue:from_list([1,2,3,4,5]).
434 {[5,4,3],[1,2]}
435 2> 1 == queue:get(Queue).
436 true
437 get_r(Q :: queue(Item)) -> Item
439 Returns Item at the rear of queue Q.
441 Fails with reason empty if Q is empty.
443 Example 1:
445 1> Queue = queue:from_list([1,2,3,4,5]).
447 {[5,4,3],[1,2]}
448 2> 5 == queue:get_r(Queue).
449 true
450 peek(Q :: queue(Item)) -> empty | {value, Item}
452 Returns tuple {value, Item}, where Item is the front item of Q,
454 or empty if Q is empty.
455 Example 1:
457 1> queue:peek(queue:new()).
459 empty
460 2> Queue = queue:from_list([1,2,3,4,5]).
461 {[5,4,3],[1,2]}
462 3> queue:peek(Queue).
463 {value, 1}
464 peek_r(Q :: queue(Item)) -> empty | {value, Item}
466 Returns tuple {value, Item}, where Item is the rear item of Q,
468 or empty if Q is empty.
469 Example 1:
471 1> queue:peek_r(queue:new()).
473 empty
474 2> Queue = queue:from_list([1,2,3,4,5]).
475 {[5,4,3],[1,2]}
476 3> queue:peek_r(Queue).
477 {value, 5}
478
481 cons(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
482 Inserts Item at the head of queue Q1. Returns the new queue Q2.
484 Example:
486 1> Queue = queue:cons(0, queue:from_list([1,2,3])).
488 {[3,2],[0,1]}
489 2> queue:to_list(Queue).
490 [0,1,2,3]
491 daeh(Q :: queue(Item)) -> Item
493 Returns the tail item of queue Q.
495 Fails with reason empty if Q is empty.
497 Example 1:
499 1> queue:daeh(queue:from_list([1,2,3])).
501 3
502 head(Q :: queue(Item)) -> Item
504 Returns Item from the head of queue Q.
506 Fails with reason empty if Q is empty.
508 Example 1:
510 1> queue:head(queue:from_list([1,2,3])).
512 1
513 init(Q1 :: queue(Item)) -> Q2 :: queue(Item)
515 Returns a queue Q2 that is the result of removing the tail item
517 from Q1.
518 Fails with reason empty if Q1 is empty.
520 Example:
522 1> Queue = queue:init(queue:from_list([1,2,3])).
524 {[2],[1]}
525 2> queue:to_list(Queue).
526 [1,2]
527 lait(Q1 :: queue(Item)) -> Q2 :: queue(Item)
529 Returns a queue Q2 that is the result of removing the tail item
531 from Q1.
532 Fails with reason empty if Q1 is empty.
534 The name lait/1 is a misspelling - do not use it anymore.
536 last(Q :: queue(Item)) -> Item
538 Returns the tail item of queue Q.
540 Fails with reason empty if Q is empty.
542 Example:
544 1> queue:last(queue:from_list([1,2,3])).
546 3
547 liat(Q1 :: queue(Item)) -> Q2 :: queue(Item)
549 Returns a queue Q2 that is the result of removing the tail item
551 from Q1.
552 Fails with reason empty if Q1 is empty.
554 Example:
556 1> Queue = queue:liat(queue:from_list([1,2,3])).
558 {[2],[1]}
559 2> queue:to_list(Queue).
560 [1,2]
561 snoc(Q1 :: queue(Item), Item) -> Q2 :: queue(Item)
563 Inserts Item as the tail item of queue Q1. Returns the new queue
565 Q2.
566 Example:
568 1> Queue = queue:snoc(queue:from_list([1,2,3]), 4).
570 {[4,3,2],[1]}
571 2> queue:to_list(Queue).
572 [1,2,3,4]
573 tail(Q1 :: queue(Item)) -> Q2 :: queue(Item)
575 Returns a queue Q2 that is the result of removing the head item
577 from Q1.
578 Fails with reason empty if Q1 is empty.
580Ericsson AB stdlib 5.1.1 queue(3)