equal
deleted
inserted
replaced
141 return _data[findPathCost(expose(_iim[item]),d)].id; |
141 return _data[findPathCost(expose(_iim[item]),d)].id; |
142 } |
142 } |
143 |
143 |
144 /// \brief Add \e x value to the cost of every node on the path from |
144 /// \brief Add \e x value to the cost of every node on the path from |
145 /// \e item to findRoot(item). |
145 /// \e item to findRoot(item). |
146 void addCost(const Item &item, Value x){ |
146 void addCost(const Item &item, Value x) { |
147 addPathCost(expose(_iim[item]), x); |
147 addPathCost(expose(_iim[item]), x); |
148 } |
148 } |
149 |
149 |
150 /// \brief Combine the trees containing nodes \e item1 and \e item2 |
150 /// \brief Combine the trees containing nodes \e item1 and \e item2 |
151 /// by adding an edge from \e item1 \e item2. |
151 /// by adding an edge from \e item1 \e item2. |
198 ItemData v(item); |
198 ItemData v(item); |
199 _data.push_back(v); |
199 _data.push_back(v); |
200 return _iim[item]; |
200 return _iim[item]; |
201 } |
201 } |
202 |
202 |
203 int findPath(int v){ |
203 int findPath(int v) { |
204 splay(v); |
204 splay(v); |
205 return v; |
205 return v; |
206 } |
206 } |
207 |
207 |
208 int findPathCost(int p, Value &d){ |
208 int findPathCost(int p, Value &d) { |
209 while ((_data[p].right != -1 && |
209 while ((_data[p].right != -1 && |
210 !_tolerance.less(0, _data[_data[p].right].dmin)) || |
210 !_tolerance.less(0, _data[_data[p].right].dmin)) || |
211 (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { |
211 (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { |
212 if (_data[p].right != -1 && |
212 if (_data[p].right != -1 && |
213 !_tolerance.less(0, _data[_data[p].right].dmin)) { |
213 !_tolerance.less(0, _data[_data[p].right].dmin)) { |
214 p = _data[p].right; |
214 p = _data[p].right; |
215 } else if (_data[p].left != -1 && |
215 } else if (_data[p].left != -1 && |
216 !_tolerance.less(0, _data[_data[p].left].dmin)){ |
216 !_tolerance.less(0, _data[_data[p].left].dmin)) { |
217 p = _data[p].left; |
217 p = _data[p].left; |
218 } |
218 } |
219 } |
219 } |
220 splay(p); |
220 splay(p); |
221 d = _data[p].dmin; |
221 d = _data[p].dmin; |
228 } |
228 } |
229 splay(p); |
229 splay(p); |
230 return p; |
230 return p; |
231 } |
231 } |
232 |
232 |
233 void addPathCost(int p, Value x){ |
233 void addPathCost(int p, Value x) { |
234 if (!_tolerance.less(x, _max_value)) { |
234 if (!_tolerance.less(x, _max_value)) { |
235 _data[p].dmin = x;_data[p].dcost = x; |
235 _data[p].dmin = x; |
|
236 _data[p].dcost = x; |
236 } else if (!_tolerance.less(-x, _max_value)) { |
237 } else if (!_tolerance.less(-x, _max_value)) { |
237 _data[p].dmin = 0; |
238 _data[p].dmin = 0; |
238 _data[p].dcost = 0; |
239 _data[p].dcost = 0; |
239 } else { |
240 } else { |
240 _data[p].dmin += x; |
241 _data[p].dmin += x; |
361 Value min = _data[_data[v].parent].dmin; |
362 Value min = _data[_data[v].parent].dmin; |
362 int a = _data[v].parent; |
363 int a = _data[v].parent; |
363 |
364 |
364 Value aa = _data[a].dcost; |
365 Value aa = _data[a].dcost; |
365 if (_tolerance.less(aa, _max_value)) { |
366 if (_tolerance.less(aa, _max_value)) { |
366 aa+= min; |
367 aa += min; |
367 } |
368 } |
368 |
369 |
369 |
370 |
370 int b = v; |
371 int b = v; |
371 Value ab = min + _data[b].dmin; |
372 Value ab = min + _data[b].dmin; |
372 Value bb = _data[b].dcost; |
373 Value bb = _data[b].dcost; |
373 if (_tolerance.less(bb, _max_value)) { |
374 if (_tolerance.less(bb, _max_value)) { |
374 bb+= ab; |
375 bb += ab; |
375 } |
376 } |
376 |
377 |
377 int c = -1; |
378 int c = -1; |
378 Value cc = _max_value; |
379 Value cc = _max_value; |
379 if (_data[a].right != -1) { |
380 if (_data[a].right != -1) { |
380 c = _data[a].right; |
381 c = _data[a].right; |
381 cc = _data[c].dmin; |
382 cc = _data[c].dmin; |
382 if (_tolerance.less(cc, _max_value)) { |
383 if (_tolerance.less(cc, _max_value)) { |
383 cc+=min; |
384 cc += min; |
384 } |
385 } |
385 } |
386 } |
386 |
387 |
387 int d = -1; |
388 int d = -1; |
388 Value dd = _max_value; |
389 Value dd = _max_value; |
684 ItemData v(item); |
685 ItemData v(item); |
685 _data.push_back(v); |
686 _data.push_back(v); |
686 return _iim[item]; |
687 return _iim[item]; |
687 } |
688 } |
688 |
689 |
689 int findPath(int v){ |
690 int findPath(int v) { |
690 splay(v); |
691 splay(v); |
691 return v; |
692 return v; |
692 } |
693 } |
693 |
694 |
694 int findPathCost(int p, Value &d){ |
695 int findPathCost(int p, Value &d) { |
695 while ((_data[p].right != -1 && |
696 while ((_data[p].right != -1 && |
696 !_tolerance.less(0, _data[_data[p].right].dmin)) || |
697 !_tolerance.less(0, _data[_data[p].right].dmin)) || |
697 (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { |
698 (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { |
698 if (_data[p].right != -1 && |
699 if (_data[p].right != -1 && |
699 !_tolerance.less(0, _data[_data[p].right].dmin)) { |
700 !_tolerance.less(0, _data[_data[p].right].dmin)) { |
706 splay(p); |
707 splay(p); |
707 d = _data[p].dmin; |
708 d = _data[p].dmin; |
708 return p; |
709 return p; |
709 } |
710 } |
710 |
711 |
711 int findTail(int p){ |
712 int findTail(int p) { |
712 while (_data[p].right != -1) { |
713 while (_data[p].right != -1) { |
713 p = _data[p].right; |
714 p = _data[p].right; |
714 } |
715 } |
715 splay(p); |
716 splay(p); |
716 return p; |
717 return p; |
717 } |
718 } |
718 |
719 |
719 void addPathCost(int p, Value x){ |
720 void addPathCost(int p, Value x) { |
720 if (!_tolerance.less(x, _max_value)) { |
721 if (!_tolerance.less(x, _max_value)) { |
721 _data[p].dmin = x;_data[p].dcost = x; |
722 _data[p].dmin = x;_data[p].dcost = x; |
722 } else if (!_tolerance.less(-x, _max_value)) { |
723 } else if (!_tolerance.less(-x, _max_value)) { |
723 _data[p].dmin = 0; |
724 _data[p].dmin = 0; |
724 _data[p].dcost = 0; |
725 _data[p].dcost = 0; |
753 |
754 |
754 if (p != -1){ |
755 if (p != -1){ |
755 _data[p].parent = v; |
756 _data[p].parent = v; |
756 _data[p].dmin -= min; |
757 _data[p].dmin -= min; |
757 } |
758 } |
758 if (q!=-1){ |
759 if (q != -1){ |
759 _data[q].parent = v; |
760 _data[q].parent = v; |
760 if (_tolerance.less(_data[q].dmin,_max_value)) { |
761 if (_tolerance.less(_data[q].dmin,_max_value)) { |
761 _data[q].dmin -= min; |
762 _data[q].dmin -= min; |
762 } |
763 } |
763 } |
764 } |
764 _data[v].left = p; |
765 _data[v].left = p; |
765 _data[v].right = q; |
766 _data[v].right = q; |
766 if (_tolerance.less(min,_max_value)) { |
767 if (_tolerance.less(min, _max_value)) { |
767 _data[v].dcost = _data[v].dmin - min; |
768 _data[v].dcost = _data[v].dmin - min; |
768 } |
769 } |
769 _data[v].dmin = min; |
770 _data[v].dmin = min; |
770 } |
771 } |
771 |
772 |