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
|
class PriorityQueue<Base> {
private class Node {
private Base object;
private int rank;
private Node left;
private Node right;
private Node(Base object, int rank) {
this.object = object;
this.rank = rank;
left = null;
right = null;
}
}
private Node root; // Root node of the BST.
public PriorityQueue() {
root = new Node(null, -1);
} //root is the King of Kings
public boolean isEmpty() {
return root.right==root.left;
}
public Base dequeue() {
if (isEmpty())
throw new IllegalStateException();
Node top = root;
Node bottom = root.right; //First node is always to the right of the root.
while (bottom.right != null) { //Find lowest rank
top = bottom;
bottom = bottom.right;
}
return bottom.object;
}
// Unlike the BST’s discussed in the lectures, the nodes in
// each left subtree have ranks less than or equal to the
// rank at the root. The nodes in each right subtree have
// ranks greater than the rank at the root.
// This allows two or more nodes to have the same rank.
public void enqueue(Base object, int rank) {
if (rank < 0)
throw new IllegalArgumentException();
boolean LR = true;
Node top = root;
Node bottom = root.right;
while (bottom != null) {
top = bottom;
if (bottom.rank <= rank) {
bottom = bottom.left;
LR = false;
//LR = true;
} else {
bottom = bottom.right;
LR = true;
//LR = false;
}
}
if (LR) {
top.right = new Node(object, rank);
} else {
top.left = new Node(object, rank);
}
}
}
// SNOBBERY. How the aristocracy behaves in a queue. 20 points.
class Snobbery {
// MAIN. Queue them up.
public static void main(String[] args) {
PriorityQueue<String> queue = new PriorityQueue<String>();
System.out.println(queue.isEmpty()); // true 2 points
try {
System.out.println(queue.dequeue());
} catch (IllegalStateException ignore) {
System.out.println("Blimey!"); // Blimey! 2 points
}
queue.enqueue("Lancelot", 5);
queue.enqueue("Fawlty", 7);
queue.enqueue("Elizabeth", 0);
queue.enqueue("Charles", 1);
queue.enqueue("Turing", 7);
try {
queue.enqueue("Zeus", -100);
} catch (IllegalArgumentException ignore) {
System.out.println("No gods!"); // No gods! 2 points
}
System.out.println(queue.isEmpty()); // false 2 points
System.out.println(queue.dequeue()); // Elizabeth 2 points
System.out.println(queue.dequeue()); // Charles 2 points
System.out.println(queue.dequeue()); // Lancelot 2 points
System.out.println(queue.dequeue()); // Turing 2 points
System.out.println(queue.dequeue()); // Fawlty 2 points
// It's OK if Fawlty comes out before Turing, but both must come out last.
System.out.println(queue.isEmpty()); // true 2 points.
}
}
|
