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
|
/** -*-C-*-ish
Kaya standard library
Copyright (C) 2004, 2005, 2006 Edwin Brady
This file is distributed under the terms of the GNU Lesser General
Public Licence. See COPYING for licence.
*/
// I suspect this representation (two stacks rather than an array),
// is both faster for lookup and insertion (constant time mostly)
// and uses less memory for small structures (due to arrays allocating a
// largeish block). Experimentation is probably neeed.
module Queue;
import Prelude;
"FIFO queue."
abstract data Queue<a>(List<a> inq, List<a> out, Int length);
Exception EmptyQueue = Exception("Can't dequeue from an empty queue",210);
"Create an empty queue."
public Queue<a> empty = Queue(nil,nil,0);
"Get length of a queue."
public Int length(Queue<a> q) = q.length;
"Add an item to a queue."
public Void enqueue(var Queue<a> q, a item)
{
q.inq = cons(item,q.inq);
q.length++;
}
"Remove an item from a queue.
Returns the item at the front and modifies the queue."
public a dequeue(var Queue<a> q) {
if (q.length==0)
throw(EmptyQueue);
case q.out of {
nil ->
reverse(q.inq);
q.out = q.inq;
q.inq = nil;
return dequeue(q);
| cons(x,xs) ->
q.out = xs;
q.length--;
return x;
}
}
"Coerce a queue to an array.
Does not modify the queue."
// Needs to work on the actual data, not using dequeue, since coercions
// shouldn't modify the original data.
public [a] array(Queue<a> q)
{
ina = array(q.inq);
outa = array(q.out);
reverse(ina);
concat(outa,ina);
return outa;
}
// Enqueue a list of ordered numbers.
// Every so often, dequeue some and maintain a list of the dequeued numbers.
// They should be strictly in sequence.
/*
Void testQueue(Int num) {
srand(time());
xs = [1..num];
dequeued = [];
q = empty;
for x@i in xs {
enqueue(q,x);
// Every 50, on average, dequeue up to 20.
if ((i+(rand()%5))%50 == 1) {
for x in [0..(rand()%100)] {
if (length(q)>0) {
y = dequeue(q);
push(dequeued,y);
}
}
}
}
// Dequeue the rest.
while (length(q)>0) {
y = dequeue(q);
push(dequeued,y);
}
// for y in dequeued {
// putStr(y+",");
// }
// putStrLn("END");
if (xs == dequeued) {
putStrLn("Queues are identical");
} else {
putStrLn("QUEUES ARE BROKEN!");
}
}
*/
|
