Previous: Trees Up: Contents Next: Error handling

Arc: Queue operations

Arc implements a queue datatype, which is useful to add and remove elements in a first-in-first-out order. The queue datatype provides two advantages over using a plain list. The queue provides constant-time operations to add and remove elements and to determine the queue length. The queue also provides atomic access to its contents.

Internally the queue is implemented by a three-element list. The first element is the queue's contents as a list. The second element is a reference to the last element in the list. The third element is the length of the queue. By maintaining a reference to the end of the queue, an element can be added to the end of the queue in constant time, without traversing the whole list. By storing the length explicitly, the length can also be returned in constant time. For example, the following shows a queue with two elements:

arc> (let q (queue) (enq 'a q) (enq 'b q) q)
((a b) (b) 2)

Most Arc operations do not have any "knowledge" of a queue, and if applied to a queue will act on the list implementing the queue; the results are likely to be undesired. The qlist operation should be used to access the contents of the queue.

arc> (do (= q (queue)) (enq 1 q) (enq 2 q))
(1 2)
arc> (apply + q)
Error: "+: expects type  as 1st argument, given: (1 2); other arguments were: (2) 2"
arc> (apply + (qlist q))
3

Queue operations

Procedure queue
Creates a queue.

>(queue) (nil nil 0)

>(type (queue)) cons

Destructive enq obj q
Adds obj to the end of queue q. Returns the queue as a list. The operation is wrapped in atomic.

>(let q (queue) (enq 'a q) (enq '(1 2) q)) (a (1 2))

Procedure enq-limit obj q [limit]
Adds obj to the queue q. If the new length would exceed the limit, the first element is dequeued. The new contents of the queue is returned as a list. Note that the length of the queue will either grow by one or remain constant; the queue will not be shortened to the limit. The operation is wrapped in atomic.

>(let q (queue) (enq-limit 'a q 2) (enq-limit 'b q 2) (enq-limit 'c q 2)) (b c)

Procedure Destructive deq q
Removes the first element from the queue q and returns the removed element. The operation is wrapped in atomic.

>(let q (queue) (enq 'a q) (enq 4 q) (deq q)) a

qlen q
Returns the length of queue q.

>(let q (queue) (enq 'a q) (enq 4 q) (deq q) (qlen q)) 1

Procedure qlist q
Returns the contents of queue q as a list.

>(let q (queue) (enq 'a q) (enq '(1 2) q) (qlist q)) (a (1 2))

queue Creates a queue.	>(queue) (nil nil 0) >(type (queue)) cons
enq obj q Adds obj to the end of queue q. Returns the queue as a list. The operation is wrapped in `atomic`.	>(let q (queue) (enq 'a q) (enq '(1 2) q)) (a (1 2))
enq-limit obj q [limit] Adds obj to the queue q. If the new length would exceed the limit, the first element is dequeued. The new contents of the queue is returned as a list. Note that the length of the queue will either grow by one or remain constant; the queue will not be shortened to the limit. The operation is wrapped in `atomic`.	>(let q (queue) (enq-limit 'a q 2) (enq-limit 'b q 2) (enq-limit 'c q 2)) (b c)
deq q Removes the first element from the queue q and returns the removed element. The operation is wrapped in `atomic`.	>(let q (queue) (enq 'a q) (enq 4 q) (deq q)) a
qlen q Returns the length of queue q.	>(let q (queue) (enq 'a q) (enq 4 q) (deq q) (qlen q)) 1
qlist q Returns the contents of queue q as a list.	>(let q (queue) (enq 'a q) (enq '(1 2) q) (qlist q)) (a (1 2))