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 | } |