queue.erl
1
%%
2
%% %CopyrightBegin%
3
%%
4
%% SPDX-License-Identifier: Apache-2.0
6
%% Copyright Ericsson AB 1996-2025. All Rights Reserved.
8
%% Licensed under the Apache License, Version 2.0 (the "License");
9
%% you may not use this file except in compliance with the License.
10
%% You may obtain a copy of the License at
11
%%
12
%% http://www.apache.org/licenses/LICENSE-2.0
13
%%
14
%% Unless required by applicable law or agreed to in writing, software
15
%% distributed under the License is distributed on an "AS IS" BASIS,
16
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17
%% See the License for the specific language governing permissions and
18
%% limitations under the License.
19
%%
20
%% %CopyrightEnd%
21
%%
22
-module(queue).
23
-moduledoc """
24
Abstract data type for FIFO queues.
25
26
This module provides (double-ended) FIFO queues in an efficient manner.
27
28
All functions fail with reason `badarg` if arguments are of wrong type, for
29
example, queue arguments are not queues, indexes are not integers, and list
30
arguments are not lists. Improper lists cause internal crashes. An index out of
31
range for a queue also causes a failure with reason `badarg`.
32
33
Some functions, where noted, fail with reason `empty` for an empty queue.
34
35
The data representing a queue as used by this module is to be regarded as opaque
36
by other modules. In abstract terms, the representation is a composite type of
37
existing Erlang terms. See note on
38
[data types](`e:system:data_types.md#no_user_types`). Any code assuming
39
knowledge of the format is running on thin ice.
40
41
All operations have an amortized O(1) running time, except `all/2`, `any/2`,
42
`delete/2`, `delete_r/2`, `delete_with/2`, `delete_with_r/2`, `filter/2`,
43
`filtermap/2`, `fold/3`, `join/2`, `len/1`, `member/2`, `split/2` that have
44
O(n). To minimize the size of a queue minimizing the amount of garbage built by
45
queue operations, the queues do not contain explicit length information, and
46
that is why [`len/1`](`len/1`) is O(n). If better performance for this
47
particular operation is essential, it is easy for the caller to keep track of
48
the length.
49
50
Queues are double-ended. The mental picture of a queue is a line of people
51
(items) waiting for their turn. The queue front is the end with the item that
52
has waited the longest. The queue rear is the end an item enters when it starts
53
to wait. If instead using the mental picture of a list, the front is called head
54
and the rear is called tail.
55
56
Entering at the front and exiting at the rear are reverse operations on the
57
queue.
58
59
This module has three sets of interface functions: the _"Original API"_, the
60
_"Extended API"_, and the _"Okasaki API"_.
61
62
The "Original API" and the "Extended API" both use the mental picture of a
63
waiting line of items. Both have reverse operations suffixed "\_r".
64
65
The "Original API" item removal functions return compound terms with both the
66
removed item and the resulting queue. The "Extended API" contains alternative
67
functions that build less garbage and functions for just inspecting the queue
68
ends. Also the "Okasaki API" functions build less garbage.
69
70
The "Okasaki API" is inspired by "Purely Functional Data Structures" by Chris
71
Okasaki. It regards queues as lists. This API is by many regarded as strange and
72
avoidable. For example, many reverse operations have lexically reversed names,
73
some with more readable but perhaps less understandable aliases.
74
""".
75
76
%% Creation, inspection and conversion
77
-export([new/0,is_queue/1,is_empty/1,len/1,to_list/1,from_list/1,member/2]).
78
%% Original style API
79
-export([in/2,in_r/2,out/1,out_r/1]).
80
%% Less garbage style API
81
-export([get/1,get_r/1,peek/1,peek_r/1,drop/1,drop_r/1]).
82
83
%% Higher level API
84
-export([reverse/1,join/2,split/2,filter/2,filtermap/2,fold/3,any/2,all/2,
85
delete/2,delete_r/2,delete_with/2,delete_with_r/2]).
86
87
%% Okasaki API from klacke
88
-export([cons/2,head/1,tail/1,
89
snoc/2,last/1,daeh/1,init/1,liat/1]).
91
-export_type([queue/0, queue/1]).
92
93
%% Mis-spelled, deprecated.
94
-export([lait/1]).
95
-deprecated([{lait,1,"use queue:liat/1 instead"}]).
97
%%--------------------------------------------------------------------------
98
%% Efficient implementation of double ended fifo queues
99
%%
100
%% Queue representation
101
%%
102
%% {RearList,FrontList}
103
%%
104
%% The first element in the queue is at the head of the FrontList.
105
%% The last element in the queue is at the head of the RearList,
106
%% that is; the RearList is reversed.
107
%%
108
109
-doc "As returned by `new/0`.".
110
-opaque queue(Item) :: {list(Item), list(Item)}.
111
112
-type queue() :: queue(_).
113
114
%% Creation, inspection and conversion
115
116
%% O(1)
117
-doc """
118
Returns an empty queue.
119
120
## Examples
121
122
```erlang
123
1> Q = queue:new().
124
2> queue:to_list(Q).
125
[]
126
3> queue:is_empty(Q).
127
true
128
```
129
""".
130
-doc(#{group => <<"Original API">>}).
131
-spec new() -> queue(none()).
132
new() -> {[],[]}. %{RearList,FrontList}
133
134
%% O(1)
135
-doc """
136
Returns `true` if `Term` is queue; otherwise, returns `false`.
137
138
Note that the test will return `true` for a term coinciding with the
139
representation of a queue, even when not constructed by this
140
module. See also note on [data types](`e:system:data_types.md#no_user_types`).
141
142
## Examples
143
144
```erlang
145
1> queue:is_queue(queue:from_list([1,2,3,4,5])).
146
true
147
2> queue:is_queue(42).
148
false
149
```
151
-doc(#{group => <<"Original API">>}).
152
-spec is_queue(Term :: term()) -> boolean().
153
is_queue({R,F}) when is_list(R), is_list(F) ->
154
true;
155
is_queue(_) ->
156
false.
157
158
%% O(1)
159
-doc """
160
Returns `true` if `Q` is empty; otherwise, returns `false`.
161
162
## Examples
163
164
```erlang
165
1> queue:is_empty(queue:new()).
166
true
167
2> queue:is_empty(queue:from_list([a])).
168
false
169
3> queue:is_empty(42).
170
** exception error: bad argument
171
in function queue:is_empty/1
172
called as queue:is_empty(42)
173
```
174
""".
175
-doc(#{group => <<"Original API">>}).
176
-spec is_empty(Q :: queue()) -> boolean().
177
is_empty({[],[]}) ->
178
true;
179
is_empty({In,Out}) when is_list(In), is_list(Out) ->
180
false;
181
is_empty(Q) ->
182
erlang:error(badarg, [Q]).
183
184
%% O(len(Q))
185
-doc """
186
Calculates and returns the length of queue `Q`.
187
188
## Examples
189
190
```erlang
191
1> queue:len(queue:from_list([1,2,3])).
192
3
193
```
194
""".
195
-doc(#{group => <<"Original API">>}).
196
-spec len(Q :: queue()) -> non_neg_integer().
197
len({R,F}) when is_list(R), is_list(F) ->
198
length(R)+length(F);
199
len(Q) ->
200
erlang:error(badarg, [Q]).
201
202
%% O(len(Q))
203
-doc """
204
Returns a list of the items in the queue in the same order; the front item of
205
the queue becomes the head of the list.
206
207
## Examples
208
209
```erlang
210
1> List = [1,2,3,4,5].
211
2> Queue = queue:from_list(List).
212
3> queue:to_list(Queue).
213
[1,2,3,4,5]
214
```
215
""".
216
-doc(#{group => <<"Original API">>}).
217
-spec to_list(Q :: queue(Item)) -> list(Item).
218
to_list({In,Out}) when is_list(In), is_list(Out) ->
219
Out++lists:reverse(In, []);
220
to_list(Q) ->
221
erlang:error(badarg, [Q]).
222
223
%% O(length(L))
224
-doc """
225
Returns a queue containing the items in `L` in the same order; the head item of
226
the list becomes the front item of the queue.
227
228
## Examples
229
230
```erlang
231
1> Queue = queue:from_list([a,b,c,d,e]).
232
2> queue:get(Queue).
233
a
234
3> queue:to_list(Queue).
235
[a,b,c,d,e]
236
```
238
-doc(#{group => <<"Original API">>}).
239
-spec from_list(L :: list(Item)) -> queue(Item).
240
from_list(L) when is_list(L) ->
241
f2r(L);
242
from_list(L) ->
243
erlang:error(badarg, [L]).
244
245
%% O(length(Q))
246
-doc """
247
Returns `true` if `Item` matches some element in `Q`; otherwise, returns `false`.
248
249
## Examples
250
251
```erlang
252
1> Queue = queue:from_list([a,b,c,d,e]).
253
2> queue:member(b, Queue).
254
true
255
3> queue:member(42, Queue).
256
false
257
```
258
""".
259
-doc(#{group => <<"Original API">>}).
260
-spec member(Item, Q :: queue(Item)) -> boolean().
261
member(X, {R,F}) when is_list(R), is_list(F) ->
262
lists:member(X, R) orelse lists:member(X, F);
263
member(X, Q) ->
264
erlang:error(badarg, [X,Q]).
265
266
%%--------------------------------------------------------------------------
267
%% Original style API
268
269
%% Append to tail/rear
270
%% Put at least one element in each list, if it is cheap
271
%%
272
%% O(1)
273
-doc """
274
Inserts `Item` at the rear of queue `Q1` and returns the resulting queue `Q2`.
276
## Examples
277
278
```erlang
279
1> Queue = queue:from_list([1,2,3,4,5]).
280
2> Queue1 = queue:in(100, Queue).
281
3> queue:to_list(Queue1).
282
[1,2,3,4,5,100]
283
```
284
""".
285
-doc(#{group => <<"Original API">>}).
286
-spec in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item).
287
in(X, {[_]=In,[]}) ->
288
{[X], In};
289
in(X, {In,Out}) when is_list(In), is_list(Out) ->
290
{[X|In],Out};
291
in(X, Q) ->
292
erlang:error(badarg, [X,Q]).
293
294
%% Prepend to head/front
295
%% Put at least one element in each list, if it is cheap
296
%%
297
%% O(1)
298
-doc """
299
Inserts `Item` at the front of queue `Q1` and returns the resulting queue `Q2`.
301
## Examples
302
303
```erlang
304
1> Queue = queue:from_list([1,2,3,4,5]).
305
2> Queue1 = queue:in_r(100, Queue).
306
3> queue:to_list(Queue1).
307
[100,1,2,3,4,5]
308
```
309
""".
310
-doc(#{group => <<"Original API">>}).
311
-spec in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item).
312
in_r(X, {[],[_]=F}) ->
313
{F,[X]};
314
in_r(X, {R,F}) when is_list(R), is_list(F) ->
315
{R,[X|F]};
316
in_r(X, Q) ->
317
erlang:error(badarg, [X,Q]).
318
319
%% O(1) amortized, O(len(Q)) worst case
320
-doc """
321
Removes the item at the front of queue `Q1`.
322
323
Returns tuple `{{value, Item}, Q2}`, where `Item` is the item removed
324
and `Q2` is the resulting queue. If `Q1` is empty, tuple `{empty, Q1}`
325
is returned.
327
## Examples
328
329
```erlang
330
1> Queue = queue:from_list([1,2,3,4,5]).
331
2> {{value, 1=Item}, Queue1} = queue:out(Queue).
332
3> queue:to_list(Queue1).
333
[2,3,4,5]
334
4> {empty, _} = queue:out(queue:new()).
335
```
336
""".
337
-doc(#{group => <<"Original API">>}).
338
-spec out(Q1 :: queue(Item)) ->
339
{{value, Item}, Q2 :: queue(Item)} |
340
{empty, Q1 :: queue(Item)}.
341
out({[],[]}=Q) ->
342
{empty,Q};
343
out({[V],[]}) ->
344
{{value,V},{[],[]}};
345
out({[Y|In],[]}) ->
346
[V|Out] = lists:reverse(In, []),
347
{{value,V},{[Y],Out}};
348
out({In,[V]}) when is_list(In) ->
349
{{value,V},r2f(In)};
350
out({In,[V|Out]}) when is_list(In) ->
351
{{value,V},{In,Out}};
352
out(Q) ->
353
erlang:error(badarg, [Q]).
354
355
%% O(1) amortized, O(len(Q)) worst case
356
-doc """
357
Removes the item at the rear of queue `Q1`.
359
Returns tuple `{{value, Item}, Q2}`, where `Item` is the item removed
360
and `Q2` is the new queue. If `Q1` is empty, tuple `{empty, Q1}` is
361
returned.
362
363
## Examples
364
365
```erlang
366
1> Queue = queue:from_list([1,2,3,4,5]).
367
2> {{value, 5=Item}, Queue1} = queue:out_r(Queue).
368
3> queue:to_list(Queue1).
369
[1,2,3,4]
370
4> {empty, _} = queue:out_r(queue:new()).
371
```
372
""".
373
-doc(#{group => <<"Original API">>}).
374
-spec out_r(Q1 :: queue(Item)) ->
375
{{value, Item}, Q2 :: queue(Item)} |
376
{empty, Q1 :: queue(Item)}.
377
out_r({[],[]}=Q) ->
378
{empty,Q};
379
out_r({[],[V]}) ->
380
{{value,V},{[],[]}};
381
out_r({[],[Y|Out]}) ->
382
[V|In] = lists:reverse(Out, []),
383
{{value,V},{In,[Y]}};
384
out_r({[V],Out}) when is_list(Out) ->
385
{{value,V},f2r(Out)};
386
out_r({[V|In],Out}) when is_list(Out) ->
387
{{value,V},{In,Out}};
388
out_r(Q) ->
389
erlang:error(badarg, [Q]).
390
391
%%--------------------------------------------------------------------------
392
%% Less garbage style API.
393
394
%% O(1) since the queue is supposed to be well formed
395
-doc """
396
Returns `Item` at the front of queue `Q`.
397
398
Fails with reason `empty` if `Q` is empty.
399
400
## Examples
401
402
```erlang
403
1> Queue = queue:from_list([1,2,3,4,5]).
404
2> queue:get(Queue).
405
1
406
3> queue:drop(queue:new()).
407
** exception error: empty
408
```
409
""".
410
-doc(#{group => <<"Extended API">>}).
411
-spec get(Q :: queue(Item)) -> Item.
412
get({[],[]}=Q) ->
413
erlang:error(empty, [Q]);
414
get({R,F}) when is_list(R), is_list(F) ->
415
get(R, F);
416
get(Q) ->
417
erlang:error(badarg, [Q]).
418
419
-spec get(list(), list()) -> term().
420
get(R, [H|_]) when is_list(R) ->
421
H;
422
get([H], []) ->
423
H;
424
get([_|R], []) -> % malformed queue -> O(len(Q))
425
lists:last(R).
426
427
%% O(1) since the queue is supposed to be well formed
428
-doc """
429
Returns `Item` at the rear of queue `Q`.
430
431
Fails with reason `empty` if `Q` is empty.
432
433
## Examples
434
435
```erlang
436
1> Queue = queue:from_list([1,2,3,4,5]).
437
2> queue:get_r(Queue).
438
5
439
3> queue:drop(queue:new()).
440
** exception error: empty
441
```
442
""".
443
-doc(#{group => <<"Extended API">>}).
444
-spec get_r(Q :: queue(Item)) -> Item.
445
get_r({[],[]}=Q) ->
446
erlang:error(empty, [Q]);
447
get_r({[H|_],F}) when is_list(F) ->
448
H;
449
get_r({[],[H]}) ->
450
H;
451
get_r({[],[_|F]}) -> % malformed queue -> O(len(Q))
452
lists:last(F);
453
get_r(Q) ->
454
erlang:error(badarg, [Q]).
455
456
%% O(1) since the queue is supposed to be well formed
457
-doc """
458
Returns tuple `{value, Item}`, where `Item` is the front item of `Q`, or `empty`
459
if `Q` is empty.
460
461
## Examples
462
463
```erlang
464
1> queue:peek(queue:new()).
465
empty
466
2> Queue = queue:from_list([1,2,3,4,5]).
467
3> queue:peek(Queue).
468
{value,1}
469
```
470
""".
471
-doc(#{group => <<"Extended API">>}).
472
-spec peek(Q :: queue(Item)) -> empty | {value, Item}.
473
peek({[],[]}) ->
474
empty;
475
peek({R,[H|_]}) when is_list(R) ->
476
{value,H};
477
peek({[H],[]}) ->
478
{value,H};
479
peek({[_|R],[]}) -> % malformed queue -> O(len(Q))
480
{value,lists:last(R)};
481
peek(Q) ->
482
erlang:error(badarg, [Q]).
483
484
%% O(1) since the queue is supposed to be well formed
485
-doc """
486
Returns tuple `{value, Item}`, where `Item` is the rear item of `Q`, or `empty`
487
if `Q` is empty.
488
489
## Examples
490
491
```erlang
492
1> queue:peek_r(queue:new()).
493
empty
494
2> Queue = queue:from_list([1,2,3,4,5]).
495
3> queue:peek_r(Queue).
496
{value,5}
497
```
498
""".
499
-doc(#{group => <<"Extended API">>}).
500
-spec peek_r(Q :: queue(Item)) -> empty | {value, Item}.
501
peek_r({[],[]}) ->
502
empty;
503
peek_r({[H|_],F}) when is_list(F) ->
504
{value,H};
505
peek_r({[],[H]}) ->
506
{value,H};
507
peek_r({[],[_|R]}) -> % malformed queue -> O(len(Q))
508
{value,lists:last(R)};
509
peek_r(Q) ->
510
erlang:error(badarg, [Q]).
511
512
%% O(1) amortized
513
-doc """
514
Returns a queue `Q2` that is the result of removing the front item from `Q1`.
515
516
Fails with reason `empty` if `Q1` is empty.
517
518
## Examples
519
520
```erlang
521
1> Queue1 = queue:from_list([1,2,3,4,5]).
522
2> Queue2 = queue:drop(Queue1).
523
3> queue:to_list(Queue2).
524
[2,3,4,5]
525
4> queue:drop(queue:new()).
526
** exception error: empty
527
```
528
""".
529
-doc(#{group => <<"Extended API">>}).
530
-spec drop(Q1 :: queue(Item)) -> Q2 :: queue(Item).
531
drop({[],[]}=Q) ->
532
erlang:error(empty, [Q]);
533
drop({[_],[]}) ->
534
{[],[]};
535
drop({[Y|R],[]}) ->
536
[_|F] = lists:reverse(R, []),
537
{[Y],F};
538
drop({R, [_]}) when is_list(R) ->
539
r2f(R);
540
drop({R, [_|F]}) when is_list(R) ->
541
{R,F};
542
drop(Q) ->
543
erlang:error(badarg, [Q]).
544
545
%% O(1) amortized
546
-doc """
547
Returns a queue `Q2` that is the result of removing the rear item from `Q1`.
548
549
Fails with reason `empty` if `Q1` is empty.
550
551
## Examples
552
553
```erlang
554
1> Queue1 = queue:from_list([1,2,3,4,5]).
555
2> Queue2 = queue:drop_r(Queue1).
556
3> queue:to_list(Queue2).
557
[1,2,3,4]
558
4> queue:drop(queue:new()).
559
** exception error: empty
560
```
561
""".
562
-doc(#{group => <<"Extended API">>}).
563
-spec drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item).
564
drop_r({[],[]}=Q) ->
565
erlang:error(empty, [Q]);
566
drop_r({[],[_]}) ->
567
{[],[]};
568
drop_r({[],[Y|F]}) ->
569
[_|R] = lists:reverse(F, []),
570
{R,[Y]};
571
drop_r({[_], F}) when is_list(F) ->
572
f2r(F);
573
drop_r({[_|R], F}) when is_list(F) ->
574
{R,F};
575
drop_r(Q) ->
576
erlang:error(badarg, [Q]).
577
578
%%--------------------------------------------------------------------------
579
%% Higher level API
580
581
%% O(1)
582
-doc """
583
Returns a queue `Q2` containing the items of `Q1` in the reverse order.
584
585
## Examples
586
587
```erlang
588
1> Queue = queue:from_list([1,2,3,4,5]).
589
2> QueueRev = queue:reverse(Queue).
590
3> queue:to_list(QueueRev).
591
[5,4,3,2,1]
592
```
593
""".
594
-doc(#{group => <<"Original API">>}).
595
-spec reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item).
596
reverse({R,F}) when is_list(R), is_list(F) ->
597
{F,R};
598
reverse(Q) ->
599
erlang:error(badarg, [Q]).
600
601
%% Q2 empty: O(1)
602
%% else: O(len(Q1))
603
-doc """
604
Returns a queue `Q3` that is the result of joining `Q1` and `Q2` with `Q1` in
605
front of `Q2`.
606
607
## Examples
608
609
```erlang
610
1> Queue1 = queue:from_list([1,3]).
611
2> Queue2 = queue:from_list([2,4]).
612
3> queue:to_list(queue:join(Queue1, Queue2)).
613
[1,3,2,4]
614
```
615
""".
616
-doc(#{group => <<"Original API">>}).
617
-spec join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item).
618
join({R,F}=Q, {[],[]}) when is_list(R), is_list(F) ->
619
Q;
620
join({[],[]}, {R,F}=Q) when is_list(R), is_list(F) ->
621
Q;
622
join({R1,F1}, {R2,F2}) when is_list(R1), is_list(F1), is_list(R2), is_list(F2) ->
623
{R2,F1++lists:reverse(R1,F2)};
624
join(Q1, Q2) ->
625
erlang:error(badarg, [Q1,Q2]).
626
627
%% N = 0..len(Q)
628
%% O(max(N, len(Q)))
629
-doc """
630
Splits `Q1` into two queues.
631
632
The `N` front items are put in `Q2` and the rest in `Q3`.
633
634
## Examples
635
636
```erlang
637
1> Queue1 = queue:from_list([1,2,3,4,5]).
638
2> {Queue2, Queue3} = queue:split(2, Queue1).
639
3> queue:to_list(Queue2).
640
[1,2]
641
4> queue:to_list(Queue3).
642
[3,4,5]
643
```
644
""".
645
-doc(#{group => <<"Original API">>}).
646
-spec split(N :: non_neg_integer(), Q1 :: queue(Item)) ->
647
{Q2 :: queue(Item),Q3 :: queue(Item)}.
648
split(0, {R,F}=Q) when is_list(R), is_list(F) ->
649
{{[],[]},Q};
650
split(N, {R,F}=Q) when is_integer(N), N >= 1, is_list(R), is_list(F) ->
651
Lf = erlang:length(F),
652
if N < Lf -> % Lf >= 2
653
[X|F1] = F,
654
split_f1_to_r2(N-1, R, F1, [], [X]);
655
N > Lf ->
656
Lr = length(R),
657
M = Lr - (N-Lf),
658
if M < 0 ->
659
erlang:error(badarg, [N,Q]);
660
M > 0 ->
661
[X|R1] = R,
662
split_r1_to_f2(M-1, R1, F, [X], []);
663
true -> % M == 0
664
{Q,{[],[]}}
665
end;
666
true -> % N == Lf
667
{f2r(F),r2f(R)}
668
end;
669
split(N, Q) ->
670
erlang:error(badarg, [N,Q]).
671
672
%% Move N elements from F1 to R2
673
split_f1_to_r2(0, R1, F1, R2, F2) ->
674
{{R2,F2},{R1,F1}};
675
split_f1_to_r2(N, R1, [X|F1], R2, F2) ->
676
split_f1_to_r2(N-1, R1, F1, [X|R2], F2).
677
678
%% Move N elements from R1 to F2
679
split_r1_to_f2(0, R1, F1, R2, F2) ->
680
{{R1,F1},{R2,F2}};
681
split_r1_to_f2(N, [X|R1], F1, R2, F2) ->
682
split_r1_to_f2(N-1, R1, F1, R2, [X|F2]).
683
684
%% Fun(_) -> List: O(length(List) * len(Q))
685
%% else: O(len(Q))
686
-doc """
687
Returns a queue `Q2` that is the result of calling `Fun(Item)` on all items in
688
`Q1`.
689
690
If `Fun(Item)` returns `true`, `Item` is copied to the result queue. If it
691
returns `false`, `Item` is not copied. If it returns a list, the list elements
692
are inserted instead of `Item` in the result queue.
693
694
## Examples
695
696
```erlang
697
1> Queue = queue:from_list([1,2,3,4,5]).
698
2> Queue1 = queue:filter(fun (E) -> E > 2 end, Queue).
699
3> queue:to_list(Queue1).
700
[3,4,5]
701
```
702
703
So, `Fun(Item)` returning `[Item]` is thereby semantically equivalent to
704
returning `true`, just as returning `[]` is semantically equivalent to returning
705
`false`. But returning a list builds more garbage than returning an atom.
706
707
## Examples
708
709
```erlang
710
1> Queue = queue:from_list([1,2,3,4,5]).
711
2> Queue1 = queue:filter(fun (E) -> [E, E+1] end, Queue).
712
3> queue:to_list(Queue1).
713
[1,2,2,3,3,4,4,5,5,6]
714
```
715
""".
716
-doc(#{group => <<"Original API">>}).
717
-spec filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item) when
718
Fun :: fun((Item) -> boolean() | list(Item)).
719
filter(Fun, {R0,F0}) when is_function(Fun, 1), is_list(R0), is_list(F0) ->
720
F = filter_f(Fun, F0),
721
R = filter_r(Fun, R0),
722
if R =:= [] ->
723
f2r(F);
724
F =:= [] ->
725
r2f(R);
726
true ->
727
{R,F}
728
end;
729
filter(Fun, Q) ->
730
erlang:error(badarg, [Fun,Q]).
731
732
%% Call Fun in head to tail order
733
filter_f(_, []) ->
734
[];
735
filter_f(Fun, [X|F]) ->
736
case Fun(X) of
737
true ->
738
[X|filter_f(Fun, F)];
739
[Y] ->
740
[Y|filter_f(Fun, F)];
741
false ->
742
filter_f(Fun, F);
743
[] ->
744
filter_f(Fun, F);
745
L when is_list(L) ->
746
L++filter_f(Fun, F)
747
end.
748
749
%% Call Fun in reverse order, i.e tail to head
750
%% and reverse list result from fun to match queue order
751
filter_r(_, []) ->
752
[];
753
filter_r(Fun, [X|R0]) ->
754
R = filter_r(Fun, R0),
755
case Fun(X) of
756
true ->
757
[X|R];
758
[Y] ->
759
[Y|R];
760
false ->
761
R;
762
[] ->
763
R;
764
L when is_list(L) ->
765
lists:reverse(L, R)
766
end.
767
768
%% O(len(Q1))
769
-doc """
770
Returns a queue `Q2` that is the result of calling `Fun(Item)` on all items in
771
`Q1`.
772
773
If `Fun(Item)` returns `true`, `Item` is copied to the result queue. If it
774
returns `false`, `Item` is not copied. If it returns `{true, NewItem}`, the
775
queue element at this position is replaced with `NewItem` in the result queue.
776
777
## Examples
778
779
```erlang
780
1> Queue = queue:from_list([1,2,3,4,5]).
781
2> Queue1 = queue:filtermap(fun (E) -> E > 2 end, Queue).
782
3> queue:to_list(Queue1).
783
[3,4,5]
784
4> Queue2 = queue:filtermap(fun (E) -> {true, E - 100} end, Queue).
785
5> queue:to_list(Queue2).
786
[-99,-98,-97,-96,-95]
787
```
788
""".
789
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
790
-spec filtermap(Fun, Q1) -> Q2 when
791
Fun :: fun((Item) -> boolean() | {'true', Value}),
792
Q1 :: queue(Item),
793
Q2 :: queue(Item | Value),
794
Item :: term(),
795
Value :: term().
796
filtermap(Fun, {R0, F0}) when is_function(Fun, 1), is_list(R0), is_list(F0) ->
797
F = lists:filtermap(Fun, F0),
798
R = filtermap_r(Fun, R0),
799
if R =:= [] ->
800
f2r(F);
801
F =:= [] ->
802
r2f(R);
803
true ->
804
{R,F}
805
end;
806
filtermap(Fun, Q) ->
807
erlang:error(badarg, [Fun,Q]).
808
809
%% Call Fun in reverse order, i.e tail to head
810
filtermap_r(_, []) ->
811
[];
812
filtermap_r(Fun, [X|R0]) ->
813
R = filtermap_r(Fun, R0),
814
case Fun(X) of
815
true ->
816
[X|R];
817
{true, Y} ->
818
[Y|R];
819
false ->
820
R
821
end.
822
823
%% O(len(Q))
824
-doc """
825
Calls `Fun(Item, AccIn)` on successive items `Item` of `Queue`, starting with
826
`AccIn == Acc0`.
828
The queue is traversed in queue order, that is, from front to
829
rear. `Fun/2` must return a new accumulator, which is passed to the
830
next call. The function returns the final value of the
831
accumulator. `Acc0` is returned if the queue is empty.
832
833
## Examples
834
835
```erlang
836
1> Queue = queue:from_list([1,2,3,4,5]).
837
2> queue:fold(fun(X, Sum) -> X + Sum end, 0, Queue).
839
3> queue:fold(fun(X, Prod) -> X * Prod end, 1, Queue).
840
120
841
```
842
""".
843
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
844
-spec fold(Fun, Acc0, Q :: queue(Item)) -> Acc1 when
845
Fun :: fun((Item, AccIn) -> AccOut),
846
Acc0 :: term(),
847
Acc1 :: term(),
848
AccIn :: term(),
849
AccOut :: term().
850
fold(Fun, Acc0, {R, F}) when is_function(Fun, 2), is_list(R), is_list(F) ->
851
Acc1 = lists:foldl(Fun, Acc0, F),
852
lists:foldr(Fun, Acc1, R);
853
fold(Fun, Acc0, Q) ->
854
erlang:error(badarg, [Fun, Acc0, Q]).
855
856
%% O(len(Q)) worst case
857
-doc """
858
Returns `true` if `Pred(Item)` returns `true` for at least one item `Item` in
859
`Q`, otherwise `false`.
860
861
## Examples
862
863
```erlang
864
1> Queue = queue:from_list([1,2,3,4,5]).
865
2> queue:any(fun (E) -> E > 10 end, Queue).
866
false
867
3> queue:any(fun (E) -> E > 3 end, Queue).
868
true
869
```
870
""".
871
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
872
-spec any(Pred, Q :: queue(Item)) -> boolean() when
873
Pred :: fun((Item) -> boolean()).
874
any(Pred, {R, F}) when is_function(Pred, 1), is_list(R), is_list(F) ->
875
lists:any(Pred, F) orelse
876
lists:any(Pred, R);
877
any(Pred, Q) ->
878
erlang:error(badarg, [Pred, Q]).
879
880
%% O(len(Q)) worst case
881
-doc """
882
Returns `true` if `Pred(Item)` returns `true` for all items `Item` in `Q`,
883
otherwise `false`.
884
885
## Examples
886
887
```erlang
888
1> Queue = queue:from_list([1,2,3,4,5]).
889
2> queue:all(fun (E) -> E > 3 end, Queue).
890
false
891
3> queue:all(fun (E) -> E > 0 end, Queue).
892
true
893
```
894
""".
895
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
896
-spec all(Pred, Q :: queue(Item)) -> boolean() when
897
Pred :: fun((Item) -> boolean()).
898
all(Pred, {R, F}) when is_function(Pred, 1), is_list(R), is_list(F) ->
899
lists:all(Pred, F) andalso
900
lists:all(Pred, R);
901
all(Pred, Q) ->
902
erlang:error(badarg, [Pred, Q]).
903
904
%% O(len(Q1)) worst case
905
-doc """
906
Returns a copy of `Q1` where the first item matching `Item` is deleted, if there
907
is such an item.
908
909
## Examples
910
911
```erlang
912
1> Queue = queue:from_list([1,2,3,4,5]).
913
2> Queue1 = queue:delete(3, Queue).
914
3> queue:member(3, Queue1).
915
false
916
```
917
""".
918
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
919
-spec delete(Item, Q1) -> Q2 when
920
Item :: T,
921
Q1 :: queue(T),
922
Q2 :: queue(T),
923
T :: term().
924
delete(Item, {R0, F0} = Q) when is_list(R0), is_list(F0) ->
925
case delete_front(Item, F0) of
926
false ->
927
case delete_rear(Item, R0) of
928
false ->
929
Q;
930
[] ->
931
f2r(F0);
932
R1 ->
933
{R1, F0}
934
end;
935
[] ->
936
r2f(R0);
937
F1 ->
938
{R0, F1}
939
end;
940
delete(Item, Q) ->
941
erlang:error(badarg, [Item, Q]).
942
943
%% O(len(Q1)) worst case
944
-doc """
945
Returns a copy of `Q1` where the last item matching `Item` is deleted, if there
946
is such an item.
947
948
## Examples
949
950
```erlang
951
1> Queue = queue:from_list([1,2,3,4,3,5]).
952
2> Queue1 = queue:delete_r(3, Queue).
953
3> queue:to_list(Queue1).
954
[1,2,3,4,5]
955
```
956
""".
957
-doc(#{group => <<"Original API">>,since => <<"OTP 24.0">>}).
958
-spec delete_r(Item, Q1) -> Q2 when
959
Item :: T,
960
Q1 :: queue(T),
961
Q2 :: queue(T),
962
T :: term().
963
delete_r(Item, {R0, F0}) when is_list(R0), is_list(F0) ->
964
{F1, R1}=delete(Item, {F0, R0}),
965
{R1, F1};
966
delete_r(Item, Q) ->
967
erlang:error(badarg, [Item, Q]).
968
969
delete_front(Item, [Item|Rest]) ->
970
Rest;
971
delete_front(Item, [X|Rest]) ->
972
case delete_front(Item, Rest) of
973
false -> false;
974
F -> [X|F]
975
end;
976
delete_front(_, []) ->
977
false.
978
979
delete_rear(Item, [X|Rest]) ->
980
case delete_rear(Item, Rest) of
981
false when X=:=Item ->
982
Rest;
983
false ->
984
false;
985
R ->
986
[X|R]
987
end;
988
delete_rear(_, []) ->
989
false.
990
991
%% O(len(Q1)) worst case
992
-doc """
993
Returns a copy of `Q1` where the first item for which `Pred` returns `true` is
994
deleted, if there is such an item.
995
996
## Examples
997
998
```erlang
999
1> Queue = queue:from_list([1,2,3,4,5]).
1000
2> Queue1 = queue:delete_with(fun (E) -> E rem 2 =:= 0 end, Queue).