Next: lib-random, Previous: lib-prologbeans, Up: The Prolog Library [Contents][Index]

`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(`

has been established, as by`Queue`)`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, soqueue_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])`

. Useappend_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`

).

Send feedback on this subject.