Statistics
| Revision:

root / trunk / code / projects / warehouse / helper_classes / PQWrapper.cpp @ 2003

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
*/