1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189 | #include "cassert"
#include "PriorityQueue.hpp"
#include "CubitMessage.hpp"
#ifdef INLINE_TEMPLATES
#define MY_INLINE inline
#else
#define MY_INLINE
#endif
template <class Object> MY_INLINE
PriorityQueue<Object>::PriorityQueue(typename PriorityQueue<Object>::CompareFunc compare)
: theItems(1)
{
lessThanFunc = compare;
}
template <class Object> MY_INLINE
int PriorityQueue<Object>::size() const
{
return theItems.size() - 1;
}
template <class Object> MY_INLINE
bool PriorityQueue<Object>::empty() const
{
if ( size() == 0 )
return true;
else
return false;
}
template <class Object> MY_INLINE
const Object PriorityQueue<Object>::top() const
{
if ( empty() )
{
PRINT_ERROR("Empty priority queue had top request.\n");
assert(!empty());
return (Object)0;
}
return theItems[1];
}
template <class Object> MY_INLINE
void PriorityQueue<Object>::push(Object x)
{
theItems.push_back(x);
theItems[0] = x;//stash the item here...
//Percolate up.
int hole = size();
//While x is less than the parrent, do (1): then go up the tree (hole /= 2 is the parent...).
for ( ; lessThanFunc(x, theItems[hole/2]); hole /= 2 )
{
//(1) set the replace the parent with the child.
theItems[hole] = theItems[hole/2];
}
//Now where the item is greater than the parent, set this value.
theItems[hole] = x;
}
template <class Object> MY_INLINE
void PriorityQueue<Object>::pop()
{
if ( empty() )
{
PRINT_ERROR("Trying to delete min from empty priority queue.\n");
assert(!empty());
return;
}
int hole = 1;
int child;
Object tmp = theItems.back();
theItems.pop_back();
int the_size = size();
//while the current isn't at the end, do (1): then set hole to child.
for ( ; hole*2 <= the_size; hole = child )
{
child = hole*2;
if ( child != the_size &&
lessThanFunc(theItems[child+1], theItems[child]) )
child++;
if ( lessThanFunc(theItems[child], tmp) )
theItems[hole] = theItems[child];
else
break;
}
if ( !empty() )
theItems[hole] = tmp;
}
template <class Object> MY_INLINE
int PriorityQueue<Object>::where_is_item(Object &a, int start_index, bool queue_is_valid)
{
size_t i;<--- The scope of the variable 'i' can be reduced. [+]The scope of the variable 'i' can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for 'i' can be reduced:
void f(int x)
{
int i = 0;
if (x) {
// it's safe to move 'int i = 0;' here
for (int n = 0; n < 10; ++n) {
// it is possible but not safe to move 'int i = 0;' here
do_something(&i);
}
}
}
When you see this message it is always safe to reduce the variable scope 1 level. <--- The scope of the variable 'i' can be reduced. [+]The scope of the variable 'i' can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for 'i' can be reduced:
void f(int x)
{
int i = 0;
if (x) {
// it's safe to move 'int i = 0;' here
for (int n = 0; n < 10; ++n) {
// it is possible but not safe to move 'int i = 0;' here
do_something(&i);
}
}
}
When you see this message it is always safe to reduce the variable scope 1 level. <--- The scope of the variable 'i' can be reduced. [+]The scope of the variable 'i' can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for 'i' can be reduced:
void f(int x)
{
int i = 0;
if (x) {
// it's safe to move 'int i = 0;' here
for (int n = 0; n < 10; ++n) {
// it is possible but not safe to move 'int i = 0;' here
do_something(&i);
}
}
}
When you see this message it is always safe to reduce the variable scope 1 level. <--- The scope of the variable 'i' can be reduced. [+]The scope of the variable 'i' can be reduced. Warning: Be careful when fixing this message, especially when there are inner loops. Here is an example where cppcheck will write that the scope for 'i' can be reduced:
void f(int x)
{
int i = 0;
if (x) {
// it's safe to move 'int i = 0;' here
for (int n = 0; n < 10; ++n) {
// it is possible but not safe to move 'int i = 0;' here
do_something(&i);
}
}
}
When you see this message it is always safe to reduce the variable scope 1 level.
if (!queue_is_valid)
{
for (i=0; i < theItems.size(); ++i)
{
if (theItems[i] == a) {return i;}
}
return -1;
}
if (a == theItems[start_index]) {return start_index;}
if (!lessThanFunc(a, theItems[start_index]) && 2*start_index+1 <= size())
{
int result;
result = where_is_item(a, 2*start_index);
if (result > 0) {return result;}
result = where_is_item(a, 2*start_index+1);
if (result > 0) {return result;}
}
return -1;
}
template <class Object> MY_INLINE
bool PriorityQueue<Object>::update_item(Object &a, bool queue_is_valid)
{
int index = where_is_item(a, queue_is_valid);
if (index == -1) {return false;}
else {return update_item(index);}
}
template <class Object> MY_INLINE
bool PriorityQueue<Object>::update_item(int object_index)
{
if (object_index == 0) {return true;}
if (lessThanFunc(theItems[object_index], theItems[object_index/2]))
{
Object temp = theItems[object_index];
theItems[object_index] = theItems[object_index/2];
theItems[object_index/2] = temp;
update_item(object_index/2);
return true;
}
int smaller_child = 2*object_index;
if (2*object_index > size()) {return true;}
if (2*object_index+1 <= size())
{
if (lessThanFunc(theItems[2*object_index+1],theItems[2*object_index])) {++smaller_child;}
}
if (lessThanFunc(theItems[smaller_child], theItems[object_index]))
{
Object temp = theItems[object_index];
theItems[object_index] = theItems[smaller_child];
theItems[smaller_child] = temp;
update_item(smaller_child);
}
return true;
}
template <class Object> MY_INLINE
bool PriorityQueue<Object>::validate(int index)
{
bool fine = true, kid_one = false, kid_two = false;
if (2*index <= size())
{
kid_one = true;
if ((lessThanFunc(theItems[2*index], theItems[index])))
{
fine = false;
}
}
if (2*index+1 <= size())
{
kid_two = true;
if ((lessThanFunc(theItems[2*index+1], theItems[index])))
{
fine = false;
}
}
if (fine)
{
if (kid_one && !kid_two) {return validate(2*index);}
if (!kid_one && kid_two) {return validate(2*index+1);}
if (kid_one && kid_two) {return (validate(2*index) && validate(2*index+1));}
else {return true;}
}
return false;
}
|