The goal of the homework is to implement a priority queue as a BST adapter. This requires: 1. The creation of a method: removeMin for the BST class 2. The modification of the usual insert method in the BST class to allow for insertion of duplicate data. The following program is missing its insert and removeMin methods. The main purpose of the project is to supply these methods. The main program is designed to operate a PQsort function on random integer data. ********************************************************************/ import java.util.ArrayList; import java.util.Iterator; import java.util.Random; import class22.BST; import class13.BinaryNode; import class17.PriorityQueue; class BSTPQ> extends BST implements PriorityQueue { public void insert(K x) throws Exception { // TODO add this code return; } public K removeMin() throws Exception { // TODO add this code return null; } } // ---- main program to test priority queue methods class E00000000 { public static Iterator PQsort(Iterator x) throws Exception { PriorityQueue q = new BSTPQ(); while (x.hasNext()) q.insert(x.next()); ArrayList temp = new ArrayList<>(); try { while (true) temp.add(q.removeMin()); } catch (Exception e) {} return temp.iterator(); } public static void main(String args[]) throws Exception { Random r = new Random(); ArrayList v = new ArrayList<>(); for (int i = 0; i < 20; i++) v.add(r.nextInt(30)); System.out.print("Unsorted: "); for (Integer x:v) System.out.print("" + x + " "); System.out.print(" Sorted: "); Iterator sorted = PQsort(v.iterator()); while (sorted.hasNext()) System.out.print("" + sorted.next() + " "); System.out.println(); } }

*****************************************

class22.BST;

import java.util.ArrayList; import java.util.Iterator; public class BST> extends BinTree { public BinNode findNode(K target) { if (root() == null) return null; return recursiveFindNode((BinNode) root(), target); } // either find the node containing target or the future parent of a Node that would contain target protected BinNode recursiveFindNode(BinNode node, K target) { int comparison = target.compareTo(node.getData()); if (comparison == 0) return node; if (comparison < 0 && node.getLeft() != null) return recursiveFindNode((BinNode) node.getLeft(), target); if (comparison > 0 && node.getRight() != null) return recursiveFindNode((BinNode) node.getRight(), target); return node; } public void remove(K target) throws Exception { BinNode n = findNode(target); if (n == null || !n.getData().equals(target)) throw new Exception("Target not present"); removeNode(n); } public void add(K newData) throws Exception { BinNode node = findNode(newData); if (node == null) addRoot(newData); else if ((node.getData()).compareTo(newData) > 0) addLeft(node, newData); else if ((node.getData()).compareTo(newData) < 0) addRight(node, newData); else node.setData(newData); } public boolean contains(K target) { BinNode node = findNode(target); if (node == null || !node.getData().equals(target)) return false; return true; } public boolean isEmpty() { return root == null; } public K get(K partialData) { BinNode node = findNode(partialData); if (node == null || !node.getData().equals(partialData)) return null; return node.getData(); } public Iterator iterator() { ArrayList list = inOrder(); ArrayList dataList = new ArrayList(); for (TNode node: list) dataList.add(((BinNode) node).getData()); return dataList.iterator(); } public void dumpData() { System.out.println(treePrint(null)); } @Override // when removing from a BST, we can only promote from a neighbor in order protected BinaryNode descendant(BinaryNode node) { BinaryNode lower = node.getLeft(); if (lower != null) { while (lower.getRight() != null) lower = lower.getRight(); return lower; // immediate predecessor of node (in order) } lower = node.getRight(); if (lower != null) { while (lower.getLeft() != null) lower = lower.getLeft(); return lower; // immediate successor of node (in order) } return null; } }

 package trees; import java.util.ArrayList; import java.util.Iterator; import binaryTree.BinaryNode; public class BinTree extends BinaryTree { public void addRoot(T t) throws Exception { addRoot(new BinNode(null, null, null, t)); } public void addLeft(BinNode position, T t) throws Exception { addLeft(position, new BinNode(null, null, null, t)); } public void addRight(BinNode position, T t) throws Exception { addRight(position, new BinNode(null, null, null, t)); } @Override protected void promote(BinaryNode lower, BinaryNode node) { ((BinNode) node).data = ((BinNode) lower).data; } @Override protected BinaryNode descendant(BinaryNode node) { if (node.left != null) return node.left; return node.right; } }

package trees; import java.util.ArrayList; public abstract class BinaryTree extends Tree { public BinaryTree() { super(); } public void addRoot(BinaryNode node) throws Exception { if (root != null) throw new Exception("The tree is not empty"); root = node; size++; } public void addLeft(BinaryNode node, BinaryNode newChild) throws Exception { if (node.getLeft() != null) throw new Exception("Left child already exists"); node.setLeft(newChild); newChild.setParent(node); size++; } public void addRight(BinaryNode node, BinaryNode newChild) throws Exception { if (node.getRight() != null) throw new Exception("Right child already exists"); node.setRight(newChild); newChild.setParent(node); size++; } // removes a leaf but promotes and removes a descendant otherwise // returns the parent of the node that is actually removed public BinaryNode removeNode(BinaryNode node) { if (isLeaf(node)) { // base case BinaryNode parent = (BinaryNode) node.getParent(); if (parent == null) root = null; else parent.removeChild(node); size--; return parent; } BinaryNode lower = descendant(node); promote(lower, node); return removeNode(lower); } protected abstract void promote(BinaryNode lower, BinaryNode node); protected abstract BinaryNode descendant(BinaryNode node); public ArrayList inOrder() { ArrayList answer = new ArrayList(); inOrder((BinaryNode) root(), answer); return answer; } public void inOrder(BinaryNode node, ArrayList v) { if (node == null) return; inOrder(node.getLeft(), v); v.add(node); inOrder(node.getRight(), v); } public ArrayList flatOrder() { return inOrder(); } }

package trees; import java.util.ArrayList; import java.util.Iterator; public class Tree { protected TNode root; public int size; public Tree() { root = null; size = 0; } public TNode root() { return root; } public TNode parent(TNode node) { return node.getParent(); } public boolean isRoot(TNode node) { return node == root; } public boolean isInternal(TNode node) { return node.children().hasNext(); } public boolean isLeaf(TNode v) { return !isInternal(v); } public int size() { return size; } public boolean empty() { return size == 0; } public int depth(TNode node) { if (isRoot(node)) return 0; return 1 + depth(node.getParent()); } public int height(TNode node) { if (isLeaf(node)) return 0; int maxChild = 0; Iterator c = node.children(); while (c.hasNext()) { int hc = height(c.next()); if (hc > maxChild) maxChild = hc; } return maxChild + 1; } public int height() { if (root == null) return -1; return height(root); } public ArrayList preOrder() { ArrayList answer = new ArrayList<>(); preOrder(root(), answer); return answer; } public void preOrder(TNode node, ArrayList nodeOrder) { if (node == null) return; nodeOrder.add(node); Iterator x = node.children(); while (x.hasNext()) { TNode m = x.next(); preOrder(m, nodeOrder); } } public ArrayList postOrder() { ArrayList answer = new ArrayList(); postOrder(root(), answer); return answer; } public void postOrder(TNode node, ArrayList nodeOrder) { if (node == null) return; Iterator x = node.children(); while (x.hasNext()) { TNode m = x.next(); postOrder(m, nodeOrder); } nodeOrder.add(node); } public ArrayList levelOrder() { ArrayList waiting = new ArrayList<>(); waiting.add(null); if (root() == null) return waiting; waiting.add(root()); int done = 0; while (done < waiting.size()) { TNode oldNode = waiting.get(done++); if (oldNode == null) { if (done < waiting.size()) waiting.add(null); continue; } Iterator c = oldNode.children(); while (c.hasNext()) waiting.add(c.next()); } return waiting; } public ArrayList flatOrder() { return preOrder(); } public String toString() { return treePrint(null); } public String treePrint(TNode cursor) { String answer = " "; Iterator lev = levelOrder().iterator(); Iterator flat = flatOrder().iterator(); lev.next(); // skip first new line while (lev.hasNext()) { TNode o = lev.next(); if (o == null) { answer += " "; flat = flatOrder().iterator(); } else while (true) { boolean atCursor = false; TNode n = flat.next(); if (n == cursor) atCursor = true; String s = n.printData(); if (atCursor) s = "* " + s + " *"; if (n == o) { answer += s + " "; break; } else { for (int i = 0; i < s.length(); i++) answer += ' '; answer += ' '; } } } return answer; } }

**********************************************

class13.BNode;

package trees; public class BinNode extends BinaryNode { T data; public BinNode() { super(); } public BinNode(BinNode p, BinNode l, BinNode r, T d) { super(p, l, r); data = d; } @Override public String printData() { return data.toString(); } public T getData() { return data; } public void setData(T newData) { data = newData; } }

package trees; import java.util.ArrayList; import java.util.Iterator; public abstract class BinaryNode implements TNode { BinaryNode left, right, parent; public BinaryNode() { parent = left = right = null; } public BinaryNode(BinaryNode p, BinaryNode l, BinaryNode r) { parent = p; left = l; right = r; } @Override public Iterator children() { ArrayList children = new ArrayList<>(); if (left != null) children.add(left); if (right != null) children.add(right); return children.iterator(); } @Override public TNode getParent() { return parent; } public void setLeft(BinaryNode n) { left = n; } public void setRight(BinaryNode n) { right = n; } public BinaryNode getLeft() { return left; } public BinaryNode getRight() { return right; } public void removeChild(BinaryNode n) { if (getLeft() == n) setLeft(null); if (getRight() == n) setRight(null); } public void setParent(BinaryNode node) { parent = node; } }

package trees; import java.util.Iterator; public interface TNode { public Iterator children(); public TNode getParent(); public String printData(); }

************************************************

class17.PriorityQueue;

public interface PriorityQueue> { public void add(K x) throws Exception; public K removeMin() throws Exception;

}