View difference between Paste ID: N56whwCW and EBuSQnVW

 #include <iostream>
 #include <string>
 #include <cassert>
-#include <cstdlib>
+
-#include <ctime>
+
 
 
 struct Qnode{
-struct BST_Node {
+	string val;
-	string key;
+	Qnode* next;
-	// we'll ignore "stuff"
+
-	string stuff;
+
-	BST_Node* left;
+struct Queue{
-	BST_Node* right;
+	Qnode *first;
 	Qnode *last;
 };
-typedef BST_Node* BST;
+
 struct PQnode{
-void BST_init (BST& root) {
+	int priority;
-	root = NULL;
+	Queue q;
 	PQnode* next;
 
-bool BST_isEmpty(BST root) {
+
-	return NULL == root;
+
 typedef PQnode* PQ;
 
-bool BST_has(string key, BST curNode) {
+void initPQ (PQ& pq) {
-	if (BST_isEmpty(curNode)) { // i.e., NULL == ROOT
+	pq = NULL;
-		return false;
+
-	} else if (key == curNode->key) {
+
-		return true;
+bool isEmptyPQ (const PQ& pq){
-	} else if (key < curNode->key) {
+	return NULL == pq;
-		return BST_has (key,curNode->left);
+
-	} else {
+
-		return BST_has (key,curNode->right);
+void enterPQ (PQ& pq, string val, int priority) {
 	Qnode *newQnode = new Qnode;
 	newQnode->val = val;
 	newQnode->next = NULL;
-BST BST_insert (string key, BST &curNode) {
+	if(isEmptyPQ(pq) || priority < pq->priority){
-	if (NULL == curNode) {
+		PQnode *newpq = new PQnode;
-		curNode = new BST_Node;
+		newpq->priority = priority;
-		curNode->key = key;
+		newpq->next = NULL;
-		curNode->left = NULL;
+		newpq->q.first = newQnode;
-		curNode->right = NULL;
+		newpq->q.last = newQnode;
-	} else if (key == curNode->key) {
+		newpq->next = pq;
-		cerr << "duplicate key: " << key << endl;
+		pq = newpq;
-		assert(false);
+
-	} else if (key < curNode->key) {
+		PQnode *temp = pq;
-		curNode->left = BST_insert (key,curNode->left);
+		while(temp->next!=NULL && temp->next->priority <= priority){
-	} else {
+			temp = temp->next;
-		curNode->right = BST_insert(key,curNode->right);
+
 		if(temp->priority == priority){
-	return curNode;
+			temp->q.last->next = newQnode;
 			temp->q.last = newQnode;
 		}else{
-void BST_print(BST curNode) {
+			PQnode *newpq = new PQnode;
-	if (curNode != NULL) {
+			newpq->priority = priority;
-		BST_print (curNode->left);
+			newpq->next = NULL;
-		cout << curNode->key << endl;
+			newpq->q.first = newQnode;
-		BST_print (curNode->right);
+			newpq->q.last = newQnode;
 			if(temp->next != NULL){
 				newpq->next = temp->next;
 			}
-string BST_lookup (const BST& root, string key) {
+			temp->next = newpq;
-	if (BST_isEmpty(root)) {
+
-		return ""; // or "ERROR", or ... umm ...
+
-	} else if (key == root->key) {
+
-		return root->stuff;
+
-	} else if (key < root->key) {
+string firstPQ (const PQ& pq){
-		return BST_lookup (root->left, key);
+	assert (!isEmptyPQ(pq));
-	} else {
+	return(pq->q.first->val);
-		return BST_lookup (root->right, key);
+
 
 void leavePQ (PQ& pq) {
 	assert (!isEmptyPQ(pq));
-void BST_delete(string key, BST& tree) {
+	if(pq->q.first->next == NULL){
-	assert (!BST_isEmpty(tree));
+		PQnode *temppq = pq;
-	BST_Node *previousNode = tree;
+		pq=pq->next;
-	BST_Node *deleteNode = tree;
+		delete temppq->q.first;
 		delete temppq;
-	while(deleteNode != NULL && key != deleteNode->key){
+
-		if (key < deleteNode->key) {
+		Qnode *temp = pq->q.first;
-			previousNode = deleteNode;
+		pq->q.first = pq->q.first->next;
-			deleteNode = deleteNode->left;
+		delete temp;
-		} else {
+
-			previousNode = deleteNode;
+
-			deleteNode = deleteNode->right;
+int sizePQ (const PQ& pq) {
 	if (isEmptyPQ(pq)) {
 		return 0;
-	if (NULL == deleteNode) {
+
-		return;
+	int numPQ = 0;
 	PQnode *temp = pq;
-	if(deleteNode->left == NULL && deleteNode->right == NULL){
+	while(temp!= NULL){
-		//		cout << "Test: " << previousNode->left->key << deleteNode->key;
+		Qnode *tempQ = temp->q.first;
-		if(tree->key == deleteNode->key){
+		//cout << "Blah: " << tempQ->val << endl;
-			tree = NULL;
+		while(tempQ!=NULL){
-		}else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
+			//cout << tempQ->val << endl;
-			previousNode->left=NULL;
+			numPQ++;
 			tempQ = tempQ->next;
-			previousNode->right=NULL;
+
 		temp = temp->next;
-		delete deleteNode;
+
-	}else if(deleteNode->left == NULL && deleteNode->right != NULL){
+	return numPQ;
-		if(tree->key == deleteNode->key){
+
-			tree = deleteNode->right;
+
-		}else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
+int sizeByPriority (const PQ& pq, int priority) {
-			previousNode->left = deleteNode->right;
+	if (isEmptyPQ(pq)) {
-		}else if(previousNode->right != NULL && previousNode->right->key == deleteNode->key){
+		return 0;
-			previousNode->right = deleteNode->right;
+
 	int numPQ = 0;
-		delete deleteNode;
+	PQnode *temp = pq;
-	}else if(deleteNode->right == NULL && deleteNode->left != NULL){
+	while(temp->next!=NULL && temp->next->priority <= priority){
-		if(tree->key == deleteNode->key){
+		temp = temp->next;
-			tree = deleteNode->left;
+
-		}else if(previousNode->right != NULL && previousNode->right->key == deleteNode->key){
+	if (NULL == temp || temp->priority != priority) {
-			previousNode->right = deleteNode->left;
+		return 0;
-		}else if(previousNode->left != NULL && previousNode->left->key == deleteNode->key){
+
-			previousNode->left = deleteNode->left;
+	Qnode *tempQ = temp->q.first;
 	while(tempQ!=NULL){
-		delete deleteNode;
+		numPQ ++;
 		tempQ = tempQ->next;
-		BST_Node *switchNode = deleteNode->left;
+
-		BST_Node *previousSwitchNode = deleteNode;
+	return numPQ;
-		while(switchNode->right != NULL){
+
-			previousSwitchNode = switchNode;
+
-			switchNode = switchNode->right;
+int numPriorities (const PQ& pq) {
 	if (isEmptyPQ(pq)) {
 		return 0;
-		if(deleteNode->key == previousSwitchNode->key){
+
-			//previousSwitchNode->left = switchNode->left;
+	int numPQ = 0;
-			switchNode->right = deleteNode->right;
+	PQnode *temp = pq;
-			if(tree->key == deleteNode->key){
+	while(temp!=NULL){
-				tree = switchNode;
+		numPQ ++;
-				delete deleteNode;
+		temp = temp->next;
-			}else{
+
-				if(previousNode->left == NULL || previousNode->left->key == deleteNode->key){
+	return numPQ;
-					previousNode->left = switchNode;
+
-				}else if(previousNode->right == NULL || previousNode->right->key == deleteNode->key){
+
-					previousNode->right = switchNode;
+void CGprint(const PQ& pq){
-				}
+	PQ temp=pq;
-				delete deleteNode;
+	while(temp!=NULL){
 		//cout<<"priority "<<temp->priority<<". Priority size: "<<sizeByPriority(pq, temp->priority)<<" :"<<endl;
 		Qnode* iter=temp->q.first;
-			previousSwitchNode->right = switchNode->left;
+		while(iter!=NULL){
-			switchNode->left = deleteNode->left;
+			cout<<iter->val<<endl;
-			switchNode->right = deleteNode->right;
+			iter=iter->next;
-			if(tree->key == deleteNode->key){
+
-				tree = switchNode;
+		temp=temp->next;
-				delete deleteNode;
+
-			}else{
+