blob: 539fe757d1ec8fb18ae83ca409e7db3c2e964d87 (
plain)
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
|
/*
* (Double-linked) list data structure with Queue and Stack operations
*/
public class List {
Element head @=> Element @tail;
/*
* Stack operations
*/
fun void
push(Object @data)
{
Element el;
tail @=> el.prev;
el @=> tail.next @=> tail;
data @=> el.payload;
}
fun Object @
getTail()
{
/* NOTE: null for tail == head */
return tail.payload;
}
fun Object @
pop()
{
tail @=> Element @el;
if (el.prev == null)
/* empty */
return null;
el.prev @=> tail;
null @=> tail.next;
return el.payload;
}
/*
* Queue operations
*/
fun void
put(Object @data)
{
data => push;
}
fun Object @
getHead()
{
if (head.next == null)
/* empty */
return null;
else
return head.next.payload;
}
fun Object @
get()
{
head.next @=> Element @el;
if (el == null)
/* empty */
return null;
el.next @=> head.next;
if (el.next == null)
/* but now it's empty! */
head @=> tail;
else
head @=> el.next.prev;
return el.payload;
}
/*
* Common operations
*/
fun void
flush()
{
while (pop() != null);
}
}
|
