From 2b93aea87324ce887633d8508f1f2dc49257acb0 Mon Sep 17 00:00:00 2001
From: Matthew Strapp <msattr@gmail.com>
Date: Fri, 6 Dec 2019 08:32:42 -0600
Subject: Finish lab 12

---
 csci1913/Java/lab12_strap012.java | 41 +++++++++++++++++++--------------------
 1 file changed, 20 insertions(+), 21 deletions(-)

(limited to 'csci1913/Java')

diff --git a/csci1913/Java/lab12_strap012.java b/csci1913/Java/lab12_strap012.java
index bd46813..3125395 100644
--- a/csci1913/Java/lab12_strap012.java
+++ b/csci1913/Java/lab12_strap012.java
@@ -11,54 +11,53 @@ class PriorityQueue<Base> {
             right = null; 
         } 
     }
-    private Node root;  //  Root node of the BST.
+    private Node root;              // Root node of the BST.
+
     public PriorityQueue() {
-        root = new Node(null, -1);
-      } //root is the King of Kings
+        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.right != null) {
+        while (bottom.left != null) {
             top = bottom;
-            bottom = bottom.right;
+            bottom = bottom.left;
         }
-        top.right = bottom.right;
-        top.left = 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;
     }
-    // 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)
+        if (rank < 0)               // No extra negative ranks allowed
             throw new IllegalArgumentException();
-        boolean LR = true;
+        boolean lessOrEqual = false;
         Node top = root;
         Node bottom = root.right;
         while (bottom != null) {
             top = bottom;
-            if (bottom.rank <= rank) {
+            if (rank <= bottom.rank) {
                 bottom = bottom.left;
-                LR = false;
+                lessOrEqual = true;
             } else {
                 bottom = bottom.right;
-                LR = true;
+                lessOrEqual = false;
             }
         }
-        if (LR) {
-            top.right = new Node(object, rank);
-        } else {
+        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.
 
-- 
cgit v1.2.3