10.32 Queue Operations —library(queues)

This module provides an implementation of queues, where you can

• create an empty queue
• add an element at either end of a queue
• add a list of elements at either end of a queue
• remove an element from the front of a queue
• remove a list of elements from the front of a queue
• determine the length of a queue
• enumerate the elements of a queue
• recognise a queue
• print a queue nicely

The representation was invented by Mark Johnson of the Center for the Study of Language and Information. All operations are fast.

Exported predicates:

empty_queue(?Queue)

is true when Queue represents an empty queue. It can be used to test whether an existing queue is empty or to make a new empty queue.

singleton_queue(?X, ?Queue)

is true when Queue is a queue with just one element X.

portray_queue(+Queue)

writes a queue out in a pretty form, as Queue[elements]. This form cannot be read back in, it is just supposed to be readable. While it is meant to be called only when is_queue(Queue) has been established, as by user:portray(Q) :- is_queue(Q), !, portray_queue(Q). it is also meant to work however it is called.

is_queue(+Queue)

is true when Queue is a queue. The elements of Queue do not have to be instantiated, and the Back of the Queue may or may not be. It can only be used to recognise queues, not to generate them. To generate queues, use queue_length(Queue, _).

queue_head(+Queue, -Head)

is true when Head is the first element of the given Queue. It does not remove Head from Queue; Head is still there afterwards. It can only be used to find Head, it cannot be used to make a Queue.

queue_tail(?Queue, ?Tail)

is true when Queue and Tail are both queues and Tail contains all the elements of Queue except the first. Note that Queue and Tail share structure, so that you can add elements at the back of only one of them. It can solve for either argument given the other.

queue_cons(?Head, ?Tail, ?Queue)

is true when Head is the head of Queue and Tail is the tail of Queue, that is, when Tail and Queue are both queues, and the elements of the Queue are Head followed by the elements of Tail in order. It can be used in either direction, so

    queue_cons(+Head, +Q0, -Q)      adds Head to Q0 giving Q
    queue_cons(-Head, -Q, +Q0)      removes Head from Q0 giving Q

queue_last(?Last, ?Queue)

is true when Last is the last element currently in Queue. It does not remove Last from Queue; it is still there. This can be used to generate a non-empty Queue. The cost is O(|Queue|).

queue_last(+Fore, +Last, -Queue)

is true when Fore and Queue are both lists and the elements of Queue are the elements of Fore in order followed by Last. This is the operation which adds an element at the end of Fore giving Queue; it is not reversible, unlike queue_cons/3, and it side-effects Fore, again unlike queue_cons/3.

append_queue(?List, ?Queue0, ?Queue)

is true when Queue is obtained by appending the elements of List in order at the front of Queue0, e.g. append_queue([a,b,c], Queue[d,e], Queue[a,b,c,d,e]). Use

    append_queue([+X1,...,+Xn], +Q0, -Q) to add X1,...,Xn to Q0 giving Q
    append_queue([-X1,...,-Xn], -Q, +Q0) to take X1...Xn from Q0 giving Q

The cost is O(n) and the operation is pure.

queue_append(+Queue0, +List, -Queue)

is true when Queue is obtained by appending the elements of List in order at the rear end of Queue0, e.g. append_queue(Queue[a,b,c], [d,e], Queue[a,b,c,d,e]). This is like queue_last/3; it side-effects Queue0.

list_queue(?List, ?Queue)

is true when Queue is a queue and List is a list and both have the same elements in the same order. list_queue/2 and queue_list/2 are the same except for argument order.

queue_list(?Queue, ?List)

is true when Queue is a queue and List is a list and both have the same elements in the same order. queue_list/2 and list_queue/2 are the same except for argument order.

queue_length(?Queue, ?Length)

is true when Queue is a queue having Length elements. It may be used to determine the Length of a Queue or to make a Queue of given Length.

queue_member(?Element, +Queue)

is true when Element is an element of Queue. It could be made to generate queues, but that would be rather inefficient. It bears the name queue_member/2 because it is prepared to enumerate Elements.

queue_memberchk(+Element, +Queue)

is true when the given Element is an element of Queue. Once it finds a member of Queue which unifies with Element, it commits to it. Use it to check a ground Element.

map_queue(:Pred, +Queue[X1,...,Xn])

succeeds when Pred(Xi) succeeds for each element Xi of the Queue.

map_queue(:Pred, +Queue[X1,...,Xn], ?Queue[Y1,...,Yn])

succeeds when Pred(Xi,Yi) succeeds for each corresponding pair of elements Xi, Yi of the two queues.

map_queue_list(:Pred, ?Queue[X1,...,Xn], ?[Y1,...,Yn])

succeeds when Pred(Xi, Yi) is true for each corresponding pair Xi,Yi of elements of the Queue and the List. It may be used to generate either of the sequences from the other.

map_list_queue(:Pred, ?[X1,...,Xn], ?Queue[Y1,...,Yn])

succeeds when Pred(Xi, Yi) is true for each corresponding pair Xi,Yi of elements of the List and the Queue. It may be used to generate either of the sequences from the other.

some_queue(:Pred, +Queue[X1,...,Xn])

succeeds when Pred(Xi) succeeds for some Xi in the Queue. It will try all ways of proving Pred(Xi) for each Xi, and will try each Xi in the Queue. somechk_queue/2 is to some_queue/2 as memberchk/2 is to member/2; you are more likely to want somechk_queue/2. This acts on backtracking like member/2; Queue should be proper.

some_queue(:Pred, +Queue[X1,...,Xn], ?Queue[Y1,...,Yn])

is true when Pred(Xi, Yi) is true for some i.

somechk_queue(:Pred, +Queue[X1,...,Xn])

is true when Pred(Xi) is true for some i, and it commits to the first solution it finds (like memberchk/2).

somechk_queue(:Pred, +Queue[X1,...,Xn], ?Queue[Y1,...,Yn])

is true when Pred(Xi, Yi) is true for some i, and it commits to the first solution it finds (like memberchk/2).