View difference between Paste ID: B6J3h8ZM and 2dKkkWih
SHOW: | | - or go back to the newest paste.
1
#include <iostream>
2
#include <string>
3
#include <cassert>
4
using namespace std;
5
6
struct Qnode{
7
	string val;
8
	Qnode* next;
9
};
10
struct Queue{
11
	Qnode *first;
12
	Qnode *last;
13
};
14
struct PQnode{
15
	int priority;
16
	Queue q;
17
	PQnode* next;
18
};
19
typedef PQnode* PQ;
20
21
void initPQ (PQ& pq) {
22
	pq = NULL;
23
}
24
25
bool isEmptyPQ (const PQ& pq){
26
	return NULL == pq;
27
}
28
29
void enterPQ (PQ& pq, string val, int priority) {
30
	Qnode *newQnode = new Qnode;
31
	newQnode->val = val;
32
	newQnode->next = NULL;
33
	if(isEmptyPQ(pq) || priority < pq->priority){
34
		PQnode *newpq = new PQnode;
35
		newpq->priority = priority;
36
		newpq->next = NULL;
37
		newpq->q.first = newQnode;
38
		newpq->q.last = newQnode;
39
		newpq->next = pq;
40
		pq = newpq;
41
	}else{
42
		PQnode *temp = pq;
43
		while(temp->next!=NULL && temp->next->priority <= priority){
44
			temp = temp->next;
45
		}
46
		if(temp->priority == priority){
47
			temp->q.last->next = newQnode;
48
			temp->q.last = newQnode;
49
		}else{
50
			PQnode *newpq = new PQnode;
51
			newpq->priority = priority;
52
			newpq->next = NULL;
53
			newpq->q.first = newQnode;
54
			newpq->q.last = newQnode;
55
			if(temp->next != NULL){
56
				newpq->next = temp->next;
57
			}
58
			temp->next = newpq;
59
		}
60
	}
61
}
62
63
string firstPQ (const PQ& pq){
64
	assert (!isEmptyPQ(pq));
65
	return(pq->q.first->val);
66
}
67
68
void leavePQ (PQ& pq) {
69
	assert (!isEmptyPQ(pq));
70
	if(pq->q.first->next == NULL){
71
		PQnode *temppq = pq;
72
		pq=pq->next;
73
		delete temppq->q.first;
74
		delete temppq;
75
	}else{
76
		Qnode *temp = pq->q.first;
77
		pq->q.first = pq->q.first->next;
78
		delete temp;
79
}
80
81
int sizePQ (const PQ& pq) {
82
	if (isEmptyPQ(pq)) {
83
		return 0;
84
	}
85
	int numPQ = 0;
86
	PQnode *temp = pq;
87
	while(temp!= NULL){
88
		Qnode *tempQ = temp->q.first;
89
		//cout << "Blah: " << tempQ->val << endl;
90
		while(tempQ!=NULL){
91
			//cout << tempQ->val << endl;
92
			numPQ++;
93
			tempQ = tempQ->next;
94
		}
95
		temp = temp->next;
96
	}
97
	return numPQ;
98
}
99
100
int sizeByPriority (const PQ& pq, int priority) {
101
	if (isEmptyPQ(pq)) {
102
		return 0;
103
	}
104
	int numPQ = 0;
105
	PQnode *temp = pq;
106
	while(temp->next!=NULL && temp->next->priority <= priority){
107
		temp = temp->next;
108
	}
109
	if (NULL == temp || temp->priority != priority) {
110
		return 0;
111
	}
112
	Qnode *tempQ = temp->q.first;
113
	while(tempQ!=NULL){
114
		numPQ ++;
115
		tempQ = tempQ->next;
116
	}
117
	return numPQ;
118
}
119
120
int numPriorities (const PQ& pq) {
121
	if (isEmptyPQ(pq)) {
122
		return 0;
123
	}
124
	int numPQ = 0;
125
	PQnode *temp = pq;
126
	while(temp!=NULL){
127
		numPQ ++;
128
		temp = temp->next;
129
	}
130
	return numPQ;
131
}
132
133
void CGprint(const PQ& pq){
134
	PQ temp=pq;
135
	while(temp!=NULL){
136
		Qnode* iter=temp->q.first;
137
		while(iter!=NULL){
138
			cout<<iter->val<<endl;
139
			iter=iter->next;
140-
		//cout<<"priority "<<temp->priority<<". Priority size: "<<sizeByPriority(pq, temp->priority)<<" :"<<endl;
140+
141
		temp=temp->next;
142
	}
143
}