root / scout / libscout / src / helper_classes / PQWrapper.cpp @ 7db6cf9f
History | View | Annotate | Download (4.03 KB)
| 1 | 4469dadd | unknown | #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 | dc742c14 | Alex | unsigned int position=0; |
| 24 | 4469dadd | unknown | bool foundPosition = false; |
| 25 | while (!foundPosition && position < arrContents)
|
||
| 26 | {
|
||
| 27 | 6761a531 | Priya | if (o.get_priority() < minElems[position].get_priority())
|
| 28 | 4469dadd | unknown | {
|
| 29 | foundPosition=true;
|
||
| 30 | } |
||
| 31 | else
|
||
| 32 | {
|
||
| 33 | position++; |
||
| 34 | } |
||
| 35 | } |
||
| 36 | if (foundPosition)
|
||
| 37 | {
|
||
| 38 | if (arrContents<arrCapacity)
|
||
| 39 | {
|
||
| 40 | dc742c14 | Alex | for (unsigned int i = arrContents; i >=position+1; i--) |
| 41 | 4469dadd | unknown | {
|
| 42 | minElems[i] = minElems[i-1];
|
||
| 43 | } |
||
| 44 | minElems[position] = o; |
||
| 45 | arrContents++; |
||
| 46 | } |
||
| 47 | else
|
||
| 48 | {
|
||
| 49 | pq.push(minElems[arrCapacity-1]);
|
||
| 50 | dc742c14 | Alex | for (unsigned int i = arrContents-1; i >= position+1; i--) |
| 51 | 4469dadd | unknown | {
|
| 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 | 7db6cf9f | Priya | if (index >= arrContents) return minElems[-1];// @todo: can I return null? |
| 73 | 4469dadd | unknown | Order toDelete = minElems[index]; |
| 74 | dc742c14 | Alex | for (unsigned int i = index; i < arrContents - 1; i++) |
| 75 | 4469dadd | unknown | {
|
| 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 | 7db6cf9f | Priya | return minElems[-1];// @todo: can I return null? |
| 96 | 4469dadd | unknown | } |
| 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 | */ |