/usr/share/Yap/queues.yap is in yap 5.1.3-6.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 | % This file has been included as an YAP library by Vitor Santos Costa, 1999
% File : QUEUES.PL
% Author : R.A.O'Keefe
% Updated: Friday November 18th, 1983, 8:09:31 pm
% Purpose: define queue operations
% Needs : lib(lists) for append/3.
:- module(queues, [
make_queue/1, % create empty queue
join_queue/3, % add element to end of queue
list_join_queue/3, % add many elements to end of queue
jump_queue/3, % add element to front of queue
list_jump_queue/3, % add many elements to front of queue
head_queue/2, % look at first element of queue
serve_queue/3, % remove first element of queue
length_queue/2, % count elements of queue
empty_queue/1, % test whether queue is empty
list_to_queue/2, % convert list to queue
queue_to_list/2 % convert queue to list
]).
:- use_module(library(lists), [append/3]).
/*
:- mode
make_queue(-),
join_queue(+, +, -),
list_join_queue(+, +, -),
jump_queue(+, +, -),
list_jump_queue(+, +, -),
head_queue(+, ?),
serve_queue(+, ?, -),
length_queue(+, ?),
length_queue(+, +, +, -),
empty_queue(+),
list_to_queue(+, -),
queue_to_list(+, -),
queue_to_list(+, +, -).
*/
/* In this package, a queue is represented as a term Front-Back, where
Front is a list and Back is a tail of that list, and is normally a
variable. join_queue will only work when the Back is a variable,
the other routines will accept any tail. The elements of the queue
are the list difference, that is, all the elements starting at Front
and stopping at Back. Examples:
[a,b,c,d,e|Z]-Z has elements a,b,c,d,e
[a,b,c,d,e]-[d,e] has elements a,b,c
Z-Z has no elements
[1,2,3]-[1,2,3] has no elements
*/
% make_queue(Queue)
% creates a new empty queue. It will also match empty queues, but
% because Prolog doesn't do the occurs check, it will also match
% other queues, creating circular lists. So this should ONLY be
% used to make new queues.
make_queue(X-X).
% join_queue(Element, OldQueue, NewQueue)
% adds the new element at the end of the queue. The old queue is
% side-effected, so you *can't* do
% join_queue(1, OldQ, NewQ1),
% join_queue(2, OldQ, NewQ2).
% There isn't any easy way of doing that, sensible though it might
% be. You *can* do
% join_queue(1, OldQ, MidQ),
% join_queue(2, MidQ, NewQ).
% See list_join_queue.
join_queue(Element, Front-[Element|Back], Front-Back).
% list_join_queue(List, OldQueue, NewQueue)
% adds the new elements at the end of the queue. The elements are
% added in the same order that they appear in the list, e.g.
% list_join_queue([y,z], [a,b,c|M]-M, [a,b,c,y,z|N]-N).
list_join_queue(List, Front-OldBack, Front-NewBack) :-
append(List, OldBack, NewBack).
% jump_queue(Element, OldQueue, NewQueue)
% adds the new element at the front of the list. Unlike join_queue,
% jump_queue(1, OldQ, NewQ1),
% jump_queue(2, OldQ, NewQ2)
% *does* work, though if you add things at the end of NewQ1 they
% will also show up in NewQ2. Note that
% jump_queue(1, OldQ, MidQ),
% jump_queue(2, MidQ, NewQ)
% makes NewQ start 2, 1, ...
jump_queue(Element, Front-Back, [Element|Front]-Back).
% list_jump_queue(List, OldQueue, NewQueue)
% adds all the elements of List at the front of the queue. There are
% two ways we might do this. We could add all the elements one at a
% time, so that they would appear at the beginning of the queue in the
% opposite order to the order they had in the list, or we could add
% them in one lump, so that they have the same order in the queue as
% in the list. As you can easily add the elements one at a time if
% that is what you want, I have chosen the latter.
list_jump_queue(List, OldFront-Back, NewFront-Back) :-
append(List, OldFront, NewFront).
% reverse(List, OldFront, NewFront). % for the other definition
% head_queue(Queue, Head)
% unifies Head with the first element of the queue. The tricky part
% is that we might be at the end of a queue: Back-Back, with Back a
% variable, and in that case this predicate should not succeed, as we
% don't know what that element is or whether it exists yet.
head_queue(Front-Back, Head) :-
Front \== Back, % the queue is not empty
Front = [Head|_].
% serve_queue(OldQueue, Head, NewQueue)
% removes the first element of the queue for service.
serve_queue(OldFront-Back, Head, NewFront-Back) :-
OldFront \== Back,
OldFront = [Head|NewFront].
% empty_queue(Queue)
% tests whether the queue is empty. If the back of a queue were
% guaranteed to be a variable, we could have
% empty_queue(Front-Back) :- var(Front).
% but I don't see why you shouldn't be able to treat difference
% lists as queues if you want to.
empty_queue(Front-Back) :-
Front == Back.
% length_queue(Queue, Length)
% counts the number of elements currently in the queue. Note that
% we have to be careful in checking for the end of the list, we
% can't test for [] the way length(List) does.
length_queue(Front-Back, Length) :-
length_queue(Front, Back, 0, N),
Length = N.
length_queue(Front, Back, N, N) :-
Front == Back, !.
length_queue([_|Front], Back, K, N) :-
L is K+1,
length_queue(Front, Back, L, N).
% list_to_queue(List, Queue)
% creates a new queue with the same elements as List.
list_to_queue(List, Front-Back) :-
append(List, Back, Front).
% queue_to_list(Queue, List)
% creates a new list with the same elements as Queue.
queue_to_list(Front-Back, List) :-
queue_to_list(Front, Back, List).
queue_to_list(Front, Back, Ans) :-
Front == Back, !, Ans = [].
queue_to_list([Head|Front], Back, [Head|Tail]) :-
queue_to_list(Front, Back, Tail).
|