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
|
#############################################################################
##
#W queue.gd GAP library Reimer Behrends
##
##
#Y Copyright (C) 2013 The GAP Group
##
## This file implements queues. These can be used both as FIFO queues,
## as deques, and as stacks.
BIND_GLOBAL("NewQueue", function()
local result, i;
result := EmptyPlist(10);
result[1] := 3;
result[2] := 3;
for i in [3..10] do
result[i] := fail;
od;
return result;
end);
BIND_GLOBAL("ExpandQueue", function(queue)
local result, p, head, tail, last;
head := queue[1];
tail := queue[2];
last := Length(queue);
p := Length(queue) - 2;
p := p * 2 + 2;
result := EmptyPlist(p);
while p > 2 do
result[p] := fail;
p := p - 1;
od;
result[1] := 3;
p := 3;
while head <> tail do
result[p] := queue[head];
p := p + 1;
head := head + 1;
if head > last then
head := 3;
fi;
od;
result[2] := p;
MigrateSingleObj(result, queue);
SWITCH_OBJ(queue, result);
end);
BIND_GLOBAL("PushQueue", function(queue, el)
local head, tail, last;
head := queue[1];
tail := queue[2];
last := Length(queue);
if tail = last then
if head = 3 then
ExpandQueue(queue);
tail := queue[2];
queue[tail] := el;
tail := tail + 1;
queue[2] := tail;
else
queue[2] := 3;
queue[last] := el;
fi;
elif tail + 1 <> head then
queue[tail] := el;
tail := tail + 1;
queue[2] := tail;
else
ExpandQueue(queue);
tail := queue[2];
queue[tail] := el;
tail := tail + 1;
queue[2] := tail;
fi;
end);
BIND_GLOBAL("PushQueueBack", PushQueue);
BIND_GLOBAL("PushQueueFront", function(queue, el)
local head, tail, last;
head := queue[1];
tail := queue[2];
last := Length(queue);
if head = 3 then
if tail = last then
ExpandQueue(queue);
head := Length(queue);
queue[head] := el;
queue[1] := head;
else
queue[1] := last;
queue[last] := el;
fi;
elif tail + 1 <> head then
head := head - 1;
queue[head] := el;
queue[1] := head;
else
ExpandQueue(queue);
head := Length(queue);
queue[head] := el;
queue[1] := head;
fi;
end);
BIND_GLOBAL("PopQueue", function(queue)
local head, tail, last, result;
head := queue[1];
tail := queue[2];
last := Length(queue);
if head <> tail then
if head = last then
head := 3;
result := queue[last];
queue[last] := fail;
else
head := head + 1;
result := queue[head-1];
queue[head-1] := fail;
fi;
queue[1] := head;
return result;
fi;
end);
BIND_GLOBAL("PopQueueFront", PopQueue);
BIND_GLOBAL("PopQueueBack", function(queue)
local head, tail, last, result;
head := queue[1];
tail := queue[2];
last := Length(queue);
if head <> tail then
if tail = 3 then
tail := last;
else
tail := tail - 1;
fi;
result := queue[tail];
queue[tail] := fail;
queue[2] := tail;
return result;
fi;
end);
BIND_GLOBAL("EmptyQueue", function(queue)
return queue[1] = queue[2];
end);
BIND_GLOBAL("LengthQueue", function(queue)
local head, tail;
head := queue[1];
tail := queue[2];
if tail >= head then
return tail - head;
else
return Length(queue) - 2 - (head - tail);
fi;
end);
BIND_GLOBAL("QueueHead", function(queue)
if queue[1] <> queue[2] then
return queue[queue[1]];
fi;
end);
BIND_GLOBAL("QueueTail", function(queue)
local tail;
tail := queue[2];
if queue[1] <> tail then
if tail <> 3 then
return queue[tail-1];
else
return queue[Length(queue)];
fi;
fi;
end);
|
