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. 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
24       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
33       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
39       Entering at the front and exiting at the rear are reverse operations on
40       the queue.
41
42       This module has three sets of interface functions: the "Original  API",
43       the "Extended API", and the "Okasaki API".
44
45       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
48       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
54       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

DATA TYPES

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

ORIGINAL API

EXPORTS

69       all(Pred, Q :: queue(Item)) -> boolean()
70
71              Types:
72
73                 Pred = fun((Item) -> boolean())
74
75              Returns true if Pred(Item) returns true for all items Item in Q,
76              otherwise false.
77
78       any(Pred, Q :: queue(Item)) -> boolean()
79
80              Types:
81
82                 Pred = fun((Item) -> boolean())
83
84              Returns  true  if  Pred(Item) returns true for at least one item
85              Item in Q, otherwise false.
86
87       delete(Item, Q1) -> Q2
88
89              Types:
90
91                 Item = T
92                 Q1 = Q2 = queue(T)
93                 T = term()
94
95              Returns a copy of Q1 where  the  first  item  matching  Item  is
96              deleted, if there is such an item.
97
98       delete_r(Item, Q1) -> Q2
99
100              Types:
101
102                 Item = T
103                 Q1 = Q2 = queue(T)
104                 T = term()
105
106              Returns  a  copy  of  Q1  where  the  last item matching Item is
107              deleted, if there is such an item.
108
109       delete_with(Pred, Q1) -> Q2
110
111              Types:
112
113                 Pred = fun((Item) -> boolean())
114                 Q1 = Q2 = queue(Item)
115                 Item = term()
116
117              Returns a copy of Q1 where the first item for which Pred returns
118              true is deleted, if there is such an item.
119
120       delete_with_r(Pred, Q1) -> Q2
121
122              Types:
123
124                 Pred = fun((Item) -> boolean())
125                 Q1 = Q2 = queue(Item)
126                 Item = term()
127
128              Returns  a copy of Q1 where the last item for which Pred returns
129              true is deleted, if there is such an item.
130
131       filter(Fun, Q1 :: queue(Item)) -> Q2 :: queue(Item)
132
133              Types:
134
135                 Fun = fun((Item) -> boolean() | [Item])
136
137              Returns a queue Q2 that is the result of  calling  Fun(Item)  on
138              all items in Q1.
139
140              If  Fun(Item)  returns true, Item is copied to the result queue.
141              If it returns false, Item is not copied. If it returns  a  list,
142              the  list  elements  are  inserted instead of Item in the result
143              queue.
144
145              So, Fun(Item) returning [Item] is thereby  semantically  equiva‐
146              lent  to  returning  true,  just as returning [] is semantically
147              equivalent to returning false. But returning a list builds  more
148              garbage than returning an atom.
149
150       filtermap(Fun, Q1) -> Q2
151
152              Types:
153
154                 Fun = fun((Item) -> boolean() | {true, Value})
155                 Q1 = queue(Item)
156                 Q2 = queue(Item | Value)
157                 Item = Value = term()
158
159              Returns  a  queue  Q2 that is the result of calling Fun(Item) on
160              all items in Q1.
161
162              If Fun(Item) returns true, Item is copied to the  result  queue.
163              If  it  returns  false, Item is not copied. If it returns {true,
164              NewItem}, the queue element at this position  is  replaced  with
165              NewItem in the result queue.
166
167       fold(Fun, Acc0, Q :: queue(Item)) -> Acc1
168
169              Types:
170
171                 Fun = fun((Item, AccIn) -> AccOut)
172                 Acc0 = Acc1 = AccIn = AccOut = term()
173
174              Calls Fun(Item, AccIn) on successive items Item of Queue, start‐
175              ing with AccIn == Acc0. The queue is traversed in  queue  order,
176              that  is,  from front to rear. Fun/2 must return a new accumula‐
177              tor, which is passed to the next call. The function returns  the
178              final value of the accumulator. Acc0 is returned if the queue is
179              empty.
180
181              Example:
182
183              > queue:fold(fun(X, Sum) -> X + Sum end, 0, queue:from_list([1,2,3,4,5])).
184              15
185              > queue:fold(fun(X, Prod) -> X * Prod end, 1, queue:from_list([1,2,3,4,5])).
186              120
187
188       from_list(L :: [Item]) -> queue(Item)
189
190              Returns a queue containing the items in L in the same order; the
191              head item of the list becomes the front item of the queue.
192
193       in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
194
195              Inserts  Item  at  the  rear  of queue Q1. Returns the resulting
196              queue Q2.
197
198       in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
199
200              Inserts Item at the front of queue  Q1.  Returns  the  resulting
201              queue Q2.
202
203       is_empty(Q :: queue()) -> boolean()
204
205              Tests if Q is empty and returns true if so, otherwise false.
206
207       is_queue(Term :: term()) -> boolean()
208
209              Tests  if  Term  is  a  queue  and returns true if so, otherwise
210              false. Note that the test will return true for a term coinciding
211              with the representation of a queue, even when not constructed by
212              thus module. See also note on data types.
213
214       join(Q1 :: queue(Item), Q2 :: queue(Item)) -> Q3 :: queue(Item)
215
216              Returns a queue Q3 that is the result of joining Q1 and Q2  with
217              Q1 in front of Q2.
218
219       len(Q :: queue()) -> integer() >= 0
220
221              Calculates and returns the length of queue Q.
222
223       member(Item, Q :: queue(Item)) -> boolean()
224
225              Returns true if Item matches some element in Q, otherwise false.
226
227       new() -> queue()
228
229              Returns an empty queue.
230
231       out(Q1 :: queue(Item)) ->
232              {{value, Item}, Q2 :: queue(Item)} |
233              {empty, Q1 :: queue(Item)}
234
235              Removes  the  item  at  the  front  of  queue  Q1. Returns tuple
236              {{value, Item}, Q2}, where Item is the item removed  and  Q2  is
237              the  resulting  queue.  If Q1 is empty, tuple {empty, Q1} is re‐
238              turned.
239
240       out_r(Q1 :: queue(Item)) ->
241                {{value, Item}, Q2 :: queue(Item)} |
242                {empty, Q1 :: queue(Item)}
243
244              Removes the item at the rear of queue Q1. Returns tuple {{value,
245              Item},  Q2},  where  Item  is the item removed and Q2 is the new
246              queue. If Q1 is empty, tuple {empty, Q1} is returned.
247
248       reverse(Q1 :: queue(Item)) -> Q2 :: queue(Item)
249
250              Returns a queue Q2 containing the items of Q1 in the reverse or‐
251              der.
252
253       split(N :: integer() >= 0, Q1 :: queue(Item)) ->
254                {Q2 :: queue(Item), Q3 :: queue(Item)}
255
256              Splits  Q1  in two. The N front items are put in Q2 and the rest
257              in Q3.
258
259       to_list(Q :: queue(Item)) -> [Item]
260
261              Returns a list of the items in the queue in the same order;  the
262              front item of the queue becomes the head of the list.
263

EXTENDED API

EXPORTS

266       drop(Q1 :: queue(Item)) -> Q2 :: queue(Item)
267
268              Returns a queue Q2 that is the result of removing the front item
269              from Q1.
270
271              Fails with reason empty if Q1 is empty.
272
273       drop_r(Q1 :: queue(Item)) -> Q2 :: queue(Item)
274
275              Returns a queue Q2 that is the result of removing the rear  item
276              from Q1.
277
278              Fails with reason empty if Q1 is empty.
279
280       get(Q :: queue(Item)) -> Item
281
282              Returns Item at the front of queue Q.
283
284              Fails with reason empty if Q is empty.
285
286       get_r(Q :: queue(Item)) -> Item
287
288              Returns Item at the rear of queue Q.
289
290              Fails with reason empty if Q is empty.
291
292       peek(Q :: queue(Item)) -> empty | {value, Item}
293
294              Returns  tuple {value, Item}, where Item is the front item of Q,
295              or empty if Q is empty.
296
297       peek_r(Q :: queue(Item)) -> empty | {value, Item}
298
299              Returns tuple {value, Item}, where Item is the rear item  of  Q,
300              or empty if Q is empty.
301

OKASAKI API

EXPORTS

304       cons(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item)
305
306              Inserts Item at the head of queue Q1. Returns the new queue Q2.
307
308       daeh(Q :: queue(Item)) -> Item
309
310              Returns the tail item of queue Q.
311
312              Fails with reason empty if Q is empty.
313
314       head(Q :: queue(Item)) -> Item
315
316              Returns Item from the head of queue Q.
317
318              Fails with reason empty if Q is empty.
319
320       init(Q1 :: queue(Item)) -> Q2 :: queue(Item)
321
322              Returns  a queue Q2 that is the result of removing the tail item
323              from Q1.
324
325              Fails with reason empty if Q1 is empty.
326
327       lait(Q1 :: queue(Item)) -> Q2 :: queue(Item)
328
329              Returns a queue Q2 that is the result of removing the tail  item
330              from Q1.
331
332              Fails with reason empty if Q1 is empty.
333
334              The name lait/1 is a misspelling - do not use it anymore.
335
336       last(Q :: queue(Item)) -> Item
337
338              Returns the tail item of queue Q.
339
340              Fails with reason empty if Q is empty.
341
342       liat(Q1 :: queue(Item)) -> Q2 :: queue(Item)
343
344              Returns  a queue Q2 that is the result of removing the tail item
345              from Q1.
346
347              Fails with reason empty if Q1 is empty.
348
349       snoc(Q1 :: queue(Item), Item) -> Q2 :: queue(Item)
350
351              Inserts Item as the tail item of queue Q1. Returns the new queue
352              Q2.
353
354       tail(Q1 :: queue(Item)) -> Q2 :: queue(Item)
355
356              Returns  a queue Q2 that is the result of removing the head item
357              from Q1.
358
359              Fails with reason empty if Q1 is empty.
360
361
362
363Ericsson AB                     stdlib 4.3.1.3                        queue(3)
Impressum