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
|
/** -*-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.
*/
"<summary>Queue implementation</summary>
<prose>This module implements a first-in, first-out queue.</prose>"
// 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.
// CIM: might be worth checking this now that operations on the left
// of an array are almost as fast as operations on the right.
module Queue;
import Prelude;
"<summary>FIFO queue.</summary>
<prose>This data type represents a first-in, first-out queue.</prose>"
abstract data Queue<a>(List<a> inq, List<a> out, Int length);
"<summary>Queue was empty</summary>
<prose>This Exception is thrown if the Queue was empty</prose>"
Exception EmptyQueue();
"<summary>Create an empty queue.</summary>
<prose>Create a new empty queue.</prose>
<related><functionref>array</functionref></related>
<related><functionref>dequeue</functionref></related>
<related><functionref>enqueue</functionref></related>
<related><functionref>length</functionref></related>"
public Queue<a> empty = Queue(nil,nil,0);
"<argument name='q'>The queue</argument>
<summary>Get the length of a queue.</summary>
<prose>Returns the number of items currently in the queue.</prose>
<related><functionref>array</functionref></related>
<related><functionref>dequeue</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>enqueue</functionref></related>"
public Int length(Queue<a> q) = q.length;
"<argument name='q'>The queue</argument>
<argument name='item'>The item to add</argument>
<summary>Add an item to a queue.</summary>
<prose>Adds an item to the queue.</prose>
<related><functionref>array</functionref></related>
<related><functionref>dequeue</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>length</functionref></related>"
public Void enqueue(Queue<a> q, a item)
{
q.inq = cons(item,q.inq);
q.length++;
}
"<argument name='q'>The queue</argument>
<summary>Remove an item from a queue.</summary>
<prose>Removes the front item from the queue, and returns the removed item. If the queue is empty, then the <exceptref>EmptyQueue</exceptref> exception will be thrown.</prose>
<related><functionref>array</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>enqueue</functionref></related>
<related><functionref>length</functionref></related>"
public a dequeue(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;
}
}
"<argument name='block'>The block of code to execute for each queue element.</argument>
<argument name='list'>The queue to traverse</argument>
<summary>Iteration over queues</summary>
<prose>Used by <code>for</code> loops to traverse <dataref>Queue</dataref> data structure. It is unlikely that you will need to call this function directly.</prose>
<prose>Iteration over a queue does not dequeue elements in the queue.</prose>"
public Void traverse(Bool(a,Int) block, Queue<a> q) {
for x@i in array(q) {
if (!block(x, i)) { return; }
}
}
"<argument name='q'>The queue</argument>
<summary>Coercion to array.</summary>
<prose>Return a list of the elements in the queue (front item in index 0), without modifying the queue.</prose>
<related><functionref>dequeue</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>enqueue</functionref></related>
<related><functionref>length</functionref></related>"
// 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!");
}
}
*/
|
