root / scout / libscout / src / helper_classes / PQWrapper.cpp @ 4469dadd
History | View | Annotate | Download (3.99 KB)
1 |
#include "PQWrapper.h" |
---|---|
2 |
|
3 |
using namespace std; |
4 |
|
5 |
/** @Brief: Initialize PQWrapper data structures. */
|
6 |
PQWrapper::PQWrapper(unsigned int numElems) |
7 |
{ |
8 |
minElems = new Order[numElems];
|
9 |
arrCapacity = numElems; |
10 |
arrContents = 0;
|
11 |
} |
12 |
|
13 |
/** @Brief: Free allocatetd memory. */
|
14 |
PQWrapper::~PQWrapper() |
15 |
{ |
16 |
while (!pq.empty()) pq.pop();
|
17 |
} |
18 |
|
19 |
/** @Brief: Insert an order into the PQWrapper. */
|
20 |
void PQWrapper::insert(Order o)
|
21 |
{ |
22 |
|
23 |
int position=0; |
24 |
bool foundPosition = false; |
25 |
while (!foundPosition && position < arrContents)
|
26 |
{ |
27 |
if (o.getpriority() < minElems[position].getpriority())
|
28 |
{ |
29 |
foundPosition=true;
|
30 |
} |
31 |
else
|
32 |
{ |
33 |
position++; |
34 |
} |
35 |
} |
36 |
if (foundPosition)
|
37 |
{ |
38 |
if (arrContents<arrCapacity)
|
39 |
{ |
40 |
for (int i = arrContents; i >=position+1; i--) |
41 |
{ |
42 |
minElems[i] = minElems[i-1];
|
43 |
} |
44 |
minElems[position] = o; |
45 |
arrContents++; |
46 |
} |
47 |
else
|
48 |
{ |
49 |
pq.push(minElems[arrCapacity-1]);
|
50 |
for (int i = arrContents-1; i >= position+1; i--) |
51 |
{ |
52 |
minElems[i] = minElems[i-1];
|
53 |
} |
54 |
minElems[position] = o; |
55 |
} |
56 |
} |
57 |
else
|
58 |
{ |
59 |
if (arrContents<arrCapacity)
|
60 |
{ |
61 |
minElems[arrContents] = o; |
62 |
arrContents++; |
63 |
} else {
|
64 |
pq.push(o); |
65 |
} |
66 |
} |
67 |
} |
68 |
|
69 |
/** @Brief: Remove and return an Order from the array if 0 <= index < arrContents. */
|
70 |
Order PQWrapper::remove(unsigned int index) |
71 |
{ |
72 |
if (index >= arrContents) return minElems[-1];//TODO: can I return null? |
73 |
Order toDelete = minElems[index]; |
74 |
for (int i = index; i < arrContents - 1; i++) |
75 |
{ |
76 |
minElems[i] = minElems[i+1];
|
77 |
} |
78 |
if (!pq.empty())
|
79 |
{ |
80 |
minElems[arrContents-1] = pq.top();
|
81 |
pq.pop(); |
82 |
} |
83 |
else
|
84 |
{ |
85 |
arrContents--; |
86 |
} |
87 |
return toDelete;
|
88 |
} |
89 |
|
90 |
/** @Brief: Return an Order from the array if 0 <= index < arrContents */
|
91 |
Order PQWrapper::peek(unsigned int index) const |
92 |
{ |
93 |
if (index >= arrContents)
|
94 |
{ |
95 |
return minElems[-1];//TODO: can I return null? |
96 |
} |
97 |
else
|
98 |
{ |
99 |
return minElems[index];
|
100 |
} |
101 |
} |
102 |
|
103 |
/** @Brief: Return the size of the minElems array */
|
104 |
unsigned int PQWrapper::arraySize() const |
105 |
{ |
106 |
return arrContents;
|
107 |
} |
108 |
|
109 |
|
110 |
/*
|
111 |
//For testing purposes only
|
112 |
int main() {
|
113 |
Order a(1,0,0,101,0,0,0);
|
114 |
Order b(2,0,0,11,0,0,0);
|
115 |
Order c(3,0,0,91,0,0,0);
|
116 |
Order d(4,0,0,21,0,0,0);
|
117 |
Order e(5,0,0,41,0,0,0);
|
118 |
Order f(6,0,0,81,0,0,0);
|
119 |
Order g(7,0,0,31,0,0,0);
|
120 |
Order h(8,0,0,71,0,0,0);
|
121 |
Order i(9,0,0,51,0,0,0);
|
122 |
Order j(10,0,0,61,0,0,0);
|
123 |
|
124 |
PQWrapper pqw(5);
|
125 |
|
126 |
pqw.insert(a);
|
127 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
128 |
cout << endl;
|
129 |
|
130 |
|
131 |
pqw.insert(b);
|
132 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
133 |
cout << endl;
|
134 |
|
135 |
pqw.insert(c);
|
136 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
137 |
cout << endl;
|
138 |
|
139 |
pqw.insert(d);
|
140 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
141 |
cout << endl;
|
142 |
|
143 |
pqw.insert(e);
|
144 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
145 |
cout << endl;
|
146 |
|
147 |
pqw.insert(f);
|
148 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
149 |
cout << endl;
|
150 |
|
151 |
pqw.insert(g);
|
152 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
153 |
cout << endl;
|
154 |
|
155 |
pqw.insert(h);
|
156 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
157 |
cout << endl;
|
158 |
|
159 |
pqw.insert(i);
|
160 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
161 |
cout << endl;
|
162 |
|
163 |
pqw.insert(j);
|
164 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
165 |
cout << endl;
|
166 |
|
167 |
for (int i=0;i<10;i++)
|
168 |
{
|
169 |
pqw.remove(0);
|
170 |
for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";
|
171 |
cout << endl;
|
172 |
}
|
173 |
|
174 |
return 0;
|
175 |
}
|
176 |
*/
|