equal
deleted
inserted
replaced
148 } |
148 } |
149 } |
149 } |
150 |
150 |
151 private: |
151 private: |
152 |
152 |
153 bool upper(int box, Prio prio) { |
153 bool upper(int box, Prio pr) { |
154 return prio < boxes[box].min; |
154 return pr < boxes[box].min; |
155 } |
155 } |
156 |
156 |
157 bool lower(int box, Prio prio) { |
157 bool lower(int box, Prio pr) { |
158 return prio >= boxes[box].min + boxes[box].size; |
158 return pr >= boxes[box].min + boxes[box].size; |
159 } |
159 } |
160 |
160 |
161 /// \brief Remove item from the box list. |
161 /// \brief Remove item from the box list. |
162 void remove(int index) { |
162 void remove(int index) { |
163 if (data[index].prev >= 0) { |
163 if (data[index].prev >= 0) { |
185 } |
185 } |
186 |
186 |
187 /// \brief Add a new box to the box list. |
187 /// \brief Add a new box to the box list. |
188 void extend() { |
188 void extend() { |
189 int min = boxes.back().min + boxes.back().size; |
189 int min = boxes.back().min + boxes.back().size; |
190 int size = 2 * boxes.back().size; |
190 int bs = 2 * boxes.back().size; |
191 boxes.push_back(RadixBox(min, size)); |
191 boxes.push_back(RadixBox(min, bs)); |
192 } |
192 } |
193 |
193 |
194 /// \brief Move an item up into the proper box. |
194 /// \brief Move an item up into the proper box. |
195 void bubble_up(int index) { |
195 void bubble_up(int index) { |
196 if (!lower(data[index].box, data[index].prio)) return; |
196 if (!lower(data[index].box, data[index].prio)) return; |
198 int box = findUp(data[index].box, data[index].prio); |
198 int box = findUp(data[index].box, data[index].prio); |
199 insert(box, index); |
199 insert(box, index); |
200 } |
200 } |
201 |
201 |
202 /// \brief Find up the proper box for the item with the given prio. |
202 /// \brief Find up the proper box for the item with the given prio. |
203 int findUp(int start, int prio) { |
203 int findUp(int start, int pr) { |
204 while (lower(start, prio)) { |
204 while (lower(start, pr)) { |
205 if (++start == (int)boxes.size()) { |
205 if (++start == int(boxes.size())) { |
206 extend(); |
206 extend(); |
207 } |
207 } |
208 } |
208 } |
209 return start; |
209 return start; |
210 } |
210 } |
216 int box = findDown(data[index].box, data[index].prio); |
216 int box = findDown(data[index].box, data[index].prio); |
217 insert(box, index); |
217 insert(box, index); |
218 } |
218 } |
219 |
219 |
220 /// \brief Find up the proper box for the item with the given prio. |
220 /// \brief Find up the proper box for the item with the given prio. |
221 int findDown(int start, int prio) { |
221 int findDown(int start, int pr) { |
222 while (upper(start, prio)) { |
222 while (upper(start, pr)) { |
223 if (--start < 0) throw UnderFlowPriorityError(); |
223 if (--start < 0) throw UnderFlowPriorityError(); |
224 } |
224 } |
225 return start; |
225 return start; |
226 } |
226 } |
227 |
227 |
258 curr = next; |
258 curr = next; |
259 } |
259 } |
260 } |
260 } |
261 |
261 |
262 void relocate_last(int index) { |
262 void relocate_last(int index) { |
263 if (index != (int)data.size() - 1) { |
263 if (index != int(data.size()) - 1) { |
264 data[index] = data.back(); |
264 data[index] = data.back(); |
265 if (data[index].prev != -1) { |
265 if (data[index].prev != -1) { |
266 data[data[index].prev].next = index; |
266 data[data[index].prev].next = index; |
267 } else { |
267 } else { |
268 boxes[data[index].box].first = index; |
268 boxes[data[index].box].first = index; |