From 7a73162607544204032aa66cce755daf21edebda Mon Sep 17 00:00:00 2001
From: Matt Strapp <matt@mattstrapp.net>
Date: Tue, 24 May 2022 11:18:46 -0500
Subject: Graduate

Signed-off-by: Matt Strapp <matt@mattstrapp.net>
---
 csci1913/Java/lab12_strap012.java | 103 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)
 create mode 100644 csci1913/Java/lab12_strap012.java

(limited to 'csci1913/Java/lab12_strap012.java')

diff --git a/csci1913/Java/lab12_strap012.java b/csci1913/Java/lab12_strap012.java
new file mode 100644
index 0000000..351cc1c
--- /dev/null
+++ b/csci1913/Java/lab12_strap012.java
@@ -0,0 +1,103 @@
+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 lone 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;
+        while (bottom.left != null) {
+            top = bottom;
+            bottom = bottom.left;
+        }
+        if (top.object == null)     // Special case for top being the head node
+            top.right = bottom.right;    
+        else
+            top.left = bottom.right;
+        return bottom.object;
+    }
+
+    public void enqueue(Base object, int rank) {
+        if (rank < 0)               // No extra negative ranks allowed
+            throw new IllegalArgumentException();
+        boolean lessOrEqual = false;
+        Node top = root;
+        Node bottom = root.right;
+        while (bottom != null) {
+            top = bottom;
+            if (rank <= bottom.rank) {
+                bottom = bottom.left;
+                lessOrEqual = true;
+            } else {
+                bottom = bottom.right;
+                lessOrEqual = false;
+            }
+        }
+        if (lessOrEqual)
+            top.left = new Node(object, rank);
+        else 
+            top.right = 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.
+    }
+
+}
-- 
cgit v1.2.3