1queue(3)                   Erlang Module Definition                   queue(3)
2
3
4

NAME

6       queue - Abstract data type for FIFO queues.
7

DESCRIPTION

9       This module provides (double-ended) FIFO queues in an efficient manner.
10
11       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
17       Some functions, where noted, fail with reason empty for an empty queue.
18
19       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
23       All  operations  has  an  amortized O(1) running time, except filter/2,
24       join/2, len/1, member/2, split/2 that have O(n). To minimize  the  size
25       of  a queue minimizing the amount of garbage built by queue operations,
26       the queues do not contain explicit length information, and that is  why
27       len/1  is  O(n). If better performance for this particular operation is
28       essential, it is easy for the caller to keep track of the length.
29
30       Queues are double-ended. The mental picture of a queue  is  a  line  of
31       people  (items) waiting for their turn. The queue front is the end with
32       the item that has waited the longest. The queue rear is the end an item
33       enters when it starts to wait. If instead using the mental picture of a
34       list, the front is called head and the rear is called tail.
35
36       Entering at the front and exiting at the rear are reverse operations on
37       the queue.
38
39       This  module has three sets of interface functions: the "Original API",
40       the "Extended API", and the "Okasaki API".
41
42       The "Original API" and the "Extended API" both use the  mental  picture
43       of a waiting line of items. Both have reverse operations suffixed "_r".
44
45       The  "Original  API"  item removal functions return compound terms with
46       both the removed item and the resulting queue. The "Extended API"  con‐
47       tains  alternative  functions that build less garbage and functions for
48       just inspecting the queue ends. Also the "Okasaki API" functions  build
49       less garbage.
50
51       The "Okasaki API" is inspired by "Purely Functional Data Structures" by
52       Chris Okasaki. It regards queues as lists. This API is by many regarded
53       as  strange  and  avoidable.  For example, many reverse operations have
54       lexically reversed names, some with  more  readable  but  perhaps  less
55       understandable aliases.
56

ORIGINAL API

DATA TYPES

59       queue(Item)
60
61              As returned by new/0.
62
63       queue() = queue(term())
64

EXPORTS

66       filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item)
67
68              Types:
69
70                 Fun = fun((Item) -> boolean() | [Item])
71
72              Returns  a  queue  Q2 that is the result of calling Fun(Item) on
73              all items in Q1, in order from front to rear.
74
75              If Fun(Item) returns true, Item is copied to the  result  queue.
76              If  it  returns false, Item is not copied. If it returns a list,
77              the list elements are inserted instead of  Item  in  the  result
78              queue.
79
80              So,  Fun(Item)  returning [Item] is thereby semantically equiva‐
81              lent to returning true, just as  returning  []  is  semantically
82              equivalent  to returning false. But returning a list builds more
83              garbage than returning an atom.
84
85       from_list(L :: [Item]) -> queue(Item)
86
87              Returns a queue containing the items in L in the same order; the
88              head item of the list becomes the front item of the queue.
89
90       in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
91
92              Inserts  Item  at  the  rear  of queue Q1. Returns the resulting
93              queue Q2.
94
95       in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
96
97              Inserts Item at the front of queue  Q1.  Returns  the  resulting
98              queue Q2.
99
100       is_empty(Q :: queue()) -> boolean()
101
102              Tests if Q is empty and returns true if so, otherwise false.
103
104       is_queue(Term :: term()) -> boolean()
105
106              Tests  if  Term  is  a  queue  and returns true if so, otherwise
107              false.
108
109       join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item)
110
111              Returns a queue Q3 that is the result of joining Q1 and Q2  with
112              Q1 in front of Q2.
113
114       len(Q :: queue()) -> integer() >= 0
115
116              Calculates and returns the length of queue Q.
117
118       member(Item, Q :: queue(Item)) -> boolean()
119
120              Returns true if Item matches some element in Q, otherwise false.
121
122       new() -> queue()
123
124              Returns an empty queue.
125
126       out(Q1 :: queue(Item)) ->
127              {{value, Item}, Q2 :: queue(Item)} |
128              {empty, Q1 :: queue(Item)}
129
130              Removes  the  item  at  the  front  of  queue  Q1. Returns tuple
131              {{value, Item}, Q2}, where Item is the item removed  and  Q2  is
132              the  resulting  queue.  If  Q1  is  empty,  tuple {empty, Q1} is
133              returned.
134
135       out_r(Q1 :: queue(Item)) ->
136                {{value, Item}, Q2 :: queue(Item)} |
137                {empty, Q1 :: queue(Item)}
138
139              Removes the item at the rear of queue Q1. Returns tuple {{value,
140              Item},  Q2},  where  Item  is the item removed and Q2 is the new
141              queue. If Q1 is empty, tuple {empty, Q1} is returned.
142
143       reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item)
144
145              Returns a queue Q2 containing the items of  Q1  in  the  reverse
146              order.
147
148       split(N :: integer() >= 0, Q1 :: queue(Item)) ->
149                {Q2 :: queue(Item), Q3 :: queue(Item)}
150
151              Splits  Q1  in two. The N front items are put in Q2 and the rest
152              in Q3.
153
154       to_list(Q :: queue(Item)) -> [Item]
155
156              Returns a list of the items in the queue in the same order;  the
157              front item of the queue becomes the head of the list.
158

EXTENDED API

EXPORTS

161       drop(Q1 :: queue(Item)) -> Q2 :: queue(Item)
162
163              Returns a queue Q2 that is the result of removing the front item
164              from Q1.
165
166              Fails with reason empty if Q1 is empty.
167
168       drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item)
169
170              Returns a queue Q2 that is the result of removing the rear  item
171              from Q1.
172
173              Fails with reason empty if Q1 is empty.
174
175       get(Q :: queue(Item)) -> Item
176
177              Returns Item at the front of queue Q.
178
179              Fails with reason empty if Q is empty.
180
181       get_r(Q :: queue(Item)) -> Item
182
183              Returns Item at the rear of queue Q.
184
185              Fails with reason empty if Q is empty.
186
187       peek(Q :: queue(Item)) -> empty | {value, Item}
188
189              Returns  tuple {value, Item}, where Item is the front item of Q,
190              or empty if Q is empty.
191
192       peek_r(Q :: queue(Item)) -> empty | {value, Item}
193
194              Returns tuple {value, Item}, where Item is the rear item  of  Q,
195              or empty if Q is empty.
196

OKASAKI API

EXPORTS

199       cons(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
200
201              Inserts Item at the head of queue Q1. Returns the new queue Q2.
202
203       daeh(Q :: queue(Item)) -> Item
204
205              Returns the tail item of queue Q.
206
207              Fails with reason empty if Q is empty.
208
209       head(Q :: queue(Item)) -> Item
210
211              Returns Item from the head of queue Q.
212
213              Fails with reason empty if Q is empty.
214
215       init(Q1 :: queue(Item)) -> Q2 :: queue(Item)
216
217              Returns  a queue Q2 that is the result of removing the tail item
218              from Q1.
219
220              Fails with reason empty if Q1 is empty.
221
222       lait(Q1 :: queue(Item)) -> Q2 :: queue(Item)
223
224              Returns a queue Q2 that is the result of removing the tail  item
225              from Q1.
226
227              Fails with reason empty if Q1 is empty.
228
229              The name lait/1 is a misspelling - do not use it anymore.
230
231       last(Q :: queue(Item)) -> Item
232
233              Returns the tail item of queue Q.
234
235              Fails with reason empty if Q is empty.
236
237       liat(Q1 :: queue(Item)) -> Q2 :: queue(Item)
238
239              Returns  a queue Q2 that is the result of removing the tail item
240              from Q1.
241
242              Fails with reason empty if Q1 is empty.
243
244       snoc(Q1 :: queue(Item), Item) -> Q2 :: queue(Item)
245
246              Inserts Item as the tail item of queue Q1. Returns the new queue
247              Q2.
248
249       tail(Q1 :: queue(Item)) -> Q2 :: queue(Item)
250
251              Returns  a queue Q2 that is the result of removing the head item
252              from Q1.
253
254              Fails with reason empty if Q1 is empty.
255
256
257
258Ericsson AB                       stdlib 3.10                         queue(3)