blob: 433f58a7f7383b1fc696410431735fc715742ea3 (
plain) (
blame)
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
|
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();
} else {
Node Test = root.right;
return Test.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();
} else {
}
}
}
// 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.
}
}
|
