COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dynamic_tree.h @ 2519:a7376f7ed899

Last change on this file since 2519:a7376f7ed899 was 2519:a7376f7ed899, checked in by Balazs Dezso, 12 years ago

Changed queue implementation

File size: 24.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18#ifndef LEMON_DYNAMIC_TREE_H
19#define LEMON_DYNAMIC_TREE_H
20
21/// \ingroup auxdata
22/// \file
23/// \brief The dynamic tree data structure of Sleator and Tarjan.
24///
25
26#include <vector>
27#include <limits>
28#include <lemon/tolerance.h>
29
30namespace lemon {
31
32  /// \ingroup auxdata
33  ///
34  /// \brief The dynamic tree data structure of Sleator and Tarjan.
35  ///
36  /// This class provides an implementation of the dynamic tree data
37  /// structure for maintaining a set of node-disjoint rooted
38  /// trees. Each item has an associated value, and the item with
39  /// minimum value can be find in \f$O(\log(n)\f$ on the path from a
40  /// node to the its root, and the items on such path can be
41  /// increased or decreased globally with a certain value in the same
42  /// running time. We regard a tree edge as directed toward the root,
43  /// that is from child to parent. Its structure can be modified by
44  /// two basic operations: \e link(v,w) adds an edge between a root v
45  /// and a node w in a different component; \e cut(v) removes the
46  /// edge between v and its parent.
47  ///
48  /// \param _Value The value type of the items. 
49  /// \param _ItemIntMap Converts item type of node to integer.
50  /// \param _Tolerance The tolerance class to handle computation
51  /// problems.
52  /// \param _enableSize If true then the data structre manatain the
53  /// size of each tree. The feature is used in \ref GoldbergTarjan
54  /// algorithm. The default value is true.
55  ///
56  /// \author Hamori Tamas
57#ifdef DOXYGEN
58  template <typename _Value, typename _ItemIntMap,
59            typename _Tolerance, bool _enableSize>
60#else
61  template <typename _Value, typename _ItemIntMap,
62            typename _Tolerance = lemon::Tolerance<_Value>,
63            bool _enableSize = true>
64#endif
65  class DynamicTree {
66  public:
67    /// \brief The integer map on the items.
68    typedef _ItemIntMap ItemIntMap;
69    /// \brief The item type of nodes.
70    typedef typename ItemIntMap::Key Item;
71    /// \brief The value type of the algorithms.
72    typedef _Value Value;
73    /// \brief The tolerance used by the algorithm.
74    typedef _Tolerance Tolerance;
75
76  private:
77 
78    class ItemData;
79
80    std::vector<ItemData> _data;
81    ItemIntMap &_iim;
82    Value _max_value;
83    Tolerance _tolerance;
84
85  public:
86    /// \brief The constructor of the class.
87    ///
88    /// \param iim The integer map on the items.
89    /// \param tolerance Tolerance class.
90    DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
91      : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
92        _tolerance(tolerance) {}
93 
94    ~DynamicTree() {}
95
96    /// \brief Clears the data structure
97    ///
98    /// Clears the data structure
99    void clear() {
100      _data.clear();
101    }
102
103    /// \brief Sets the tolerance used by algorithm.
104    ///
105    /// Sets the tolerance used by algorithm.
106    void tolerance(const Tolerance& tolerance) const {
107      _tolerance = tolerance;
108      return *this;
109    }
110 
111    /// \brief Returns the tolerance used by algorithm.
112    ///
113    /// Returns the tolerance used by algorithm.
114    const Tolerance& tolerance() const {
115      return tolerance;
116    }
117 
118    /// \brief Create a new tree containing a single node with cost zero.
119    void makeTree(const Item &item) {
120      _data[makePath(item)].successor = -1;
121    }
122   
123    /// \brief Return the root of the tree containing node with itemtype
124    /// \e item.
125    Item findRoot(const Item &item) {
126      return _data[findTail(expose(_iim[item]))].id;
127    }
128   
129    /// \brief Return the the value of nodes in the tree containing
130    /// node with itemtype \e item.
131    int findSize(const Item &item) {
132      return _data[expose(_iim[item])].size;
133    }
134   
135    /// \brief Return the minimum cost containing node.
136    ///
137    /// Return into \e d the minimum cost on the tree path from \e item
138    /// to findRoot(item).  Return the last item (closest to its root)
139    /// on this path of the minimum cost.
140    Item findCost(const Item &item, Value& d){
141      return _data[findPathCost(expose(_iim[item]),d)].id;
142    }
143   
144    /// \brief Add \e x value to the cost of every node on the path from
145    /// \e item to findRoot(item).
146    void addCost(const Item &item, Value x) {
147      addPathCost(expose(_iim[item]), x);
148    }
149   
150    /// \brief Combine the trees containing nodes \e item1 and \e item2
151    /// by adding an edge from \e item1 \e item2.
152    ///
153    /// This operation assumes that \e item1 is root and \e item2 is in
154    /// a different tree.
155    void link(const Item &item1, const Item &item2){
156      int v = _iim[item1];
157      int w = _iim[item2];
158      int p = expose(w);
159      join(-1, expose(v), p);
160      _data[v].successor = -1;
161      _data[v].size += _data[p].size;
162
163    }   
164   
165    /// \brief Divide the tree containing node \e item into two trees by
166    /// deleting the edge out of \e item.
167    ///
168    /// This operation assumes that \e item is not a tree root.
169    void cut(const Item &item) {
170      int v = _iim[item];
171      int p, q;
172      expose(v);
173      split(p, v, q);
174      if (p != -1) {
175        _data[p].successor = v;
176      }
177      _data[v].size -= _data[q].size;
178      if (q != -1) {
179        _data[q].successor = _data[v].successor;
180      }
181      _data[v].successor = -1;
182    }
183
184    ///\brief
185    Item parent(const Item &item){
186      return _data[_iim[item].p].id;
187    }
188
189    ///\brief Return the upper bound of the costs.
190    Value maxValue() const {
191      return _max_value;
192    }
193   
194  private:
195
196    int makePath(const Item &item) {
197      _iim.set(item, _data.size());
198      ItemData v(item);
199      _data.push_back(v);
200      return _iim[item];
201    }
202
203    int findPath(int v) {
204      splay(v);
205      return v;
206    }
207   
208    int findPathCost(int p, Value &d) {
209      while ((_data[p].right != -1 &&
210              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
211             (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
212        if (_data[p].right != -1 &&
213            !_tolerance.less(0, _data[_data[p].right].dmin)) {
214          p = _data[p].right;
215        } else if (_data[p].left != -1 &&
216                   !_tolerance.less(0, _data[_data[p].left].dmin)) {
217          p = _data[p].left;
218        }
219      }
220      splay(p);
221      d = _data[p].dmin;
222      return p;
223    }
224
225    int findTail(int p){
226      while (_data[p].right != -1) {
227        p = _data[p].right;
228      }
229      splay(p);
230      return p;
231    }
232   
233    void addPathCost(int p, Value x) {
234      if (!_tolerance.less(x, _max_value)) {
235        _data[p].dmin = x;
236        _data[p].dcost = x;
237      } else if (!_tolerance.less(-x, _max_value)) {
238        _data[p].dmin = 0;
239        _data[p].dcost = 0;
240      } else {
241        _data[p].dmin += x;
242      }
243    }
244
245    void join(int p, int v, int q) {
246      Value min = _max_value;
247      Value pmin = _max_value;
248      Value vmin = _data[v].dmin;
249      Value qmin = _max_value;
250      if (p != -1){
251        pmin = _data[p].dmin;
252      }
253      if (q != -1){
254        qmin = _data[q].dmin;
255      }
256       
257      if (_tolerance.less(vmin, qmin)) {
258        if (_tolerance.less(vmin,pmin)) {
259          min = vmin;
260        } else {
261          min = pmin;
262        }
263      } else if (_tolerance.less(qmin,pmin)) {
264        min = qmin;
265      } else {
266        min = pmin;
267      }
268
269      if (p != -1){
270        _data[p].parent = v;
271        _data[p].dmin -= min;
272      }
273      if (q!=-1){
274        _data[q].parent = v;
275        if (_tolerance.less(_data[q].dmin,_max_value)) {
276          _data[q].dmin -= min;
277        }
278      }
279      _data[v].left = p;
280      _data[v].right = q;
281      if (_tolerance.less(min,_max_value)) {
282        _data[v].dcost = _data[v].dmin - min;
283      }
284      _data[v].dmin = min;
285    }
286
287    void split(int &p, int v, int &q){
288      splay(v);
289      p = -1;
290      if (_data[v].left != -1){
291        p = _data[v].left;
292        _data[p].dmin += _data[v].dmin;
293        _data[p].parent = -1;
294        _data[v].left = -1;
295      }
296      q = -1;
297      if (_data[v].right != -1) {
298        q=_data[v].right;
299        if (_tolerance.less(_data[q].dmin, _max_value)) {
300          _data[q].dmin += _data[v].dmin;
301        }
302        _data[q].parent = -1;
303        _data[v].right = -1;
304      }
305      if (_tolerance.less(_data[v].dcost, _max_value)) {
306        _data[v].dmin += _data[v].dcost;
307        _data[v].dcost = 0;
308      } else {
309        _data[v].dmin = _data[v].dcost;
310      }
311    }
312 
313    int expose(int v) {
314      int p, q, r, w;
315      p = -1;
316      while (v != -1) {
317        w = _data[findPath(v)].successor;
318        split(q, v, r);
319        if (q != -1) {
320          _data[q].successor = v;
321        }
322        join(p, v, r);
323        p = v;
324        v = w;
325      }
326      _data[p].successor = -1;
327      return p;
328    }
329
330    void splay(int v) {
331      while (_data[v].parent != -1) {
332        if (v == _data[_data[v].parent].left) {
333          if (_data[_data[v].parent].parent == -1) {
334            zig(v);
335          } else {
336            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
337              zig(_data[v].parent);
338              zig(v);
339            } else {
340              zig(v);
341              zag(v);
342            }
343          }
344        } else {
345          if (_data[_data[v].parent].parent == -1) {
346            zag(v);
347          } else {
348            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
349              zag(v);
350              zig(v);
351            } else {
352              zag(_data[v].parent);
353              zag(v);
354            }
355          }
356        }
357      }
358    }
359
360
361    void zig(int v) {
362      Value min = _data[_data[v].parent].dmin;
363      int a = _data[v].parent;
364       
365      Value aa = _data[a].dcost;
366      if (_tolerance.less(aa, _max_value)) {
367        aa += min;
368      }
369
370
371      int b = v;
372      Value ab = min + _data[b].dmin;
373      Value bb = _data[b].dcost;
374      if (_tolerance.less(bb, _max_value)) {
375        bb += ab;
376      }
377
378      int c = -1;
379      Value cc = _max_value;
380      if (_data[a].right != -1) {
381        c = _data[a].right;
382        cc = _data[c].dmin;
383        if (_tolerance.less(cc, _max_value)) {
384          cc += min;
385        }
386      }
387
388      int d = -1;
389      Value dd = _max_value;
390      if (_data[v].left != -1){
391        d = _data[v].left;
392        dd = ab + _data[d].dmin;
393      }
394
395      int e = -1;
396      Value ee = _max_value;
397      if (_data[v].right != -1) {
398        e = _data[v].right;
399        ee = ab + _data[e].dmin;
400      }
401
402      Value min2;
403      if (_tolerance.less(0, _data[b].dmin) ||
404          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
405        min2 = min;
406      } else {
407        if (_tolerance.less(aa, cc)) {
408          if (_tolerance.less(aa, ee)) {
409            min2 = aa;
410          } else {
411            min2 = ee;
412          }
413        } else if (_tolerance.less(cc, ee)) {
414          min2 = cc;
415        } else {
416          min2 = ee;
417        }
418      }
419       
420      _data[a].dcost = aa;
421      if (_tolerance.less(aa, _max_value)) {
422        _data[a].dcost -= min2;
423      }
424      _data[a].dmin = min2;
425      if (_tolerance.less(min2,_max_value)) {
426        _data[a].dmin -= min;
427      }
428      _data[a].size -= _data[b].size;
429      _data[b].dcost = bb;
430      if (_tolerance.less(bb, _max_value)) {
431        _data[b].dcost -= min;
432      }
433      _data[b].dmin = min;
434      _data[b].size += _data[a].size;
435      if (c != -1) {
436        _data[c].dmin = cc;
437        if (_tolerance.less(cc, _max_value)) {
438          _data[c].dmin -= min2;
439        }
440      }
441      if (d != -1) {
442        _data[d].dmin = dd - min;
443        _data[a].size += _data[d].size;
444        _data[b].size -= _data[d].size;
445      }
446      if (e != -1) {
447        _data[e].dmin = ee - min2;
448      }
449       
450      int w = _data[v].parent;
451      _data[v].successor = _data[w].successor;
452      _data[w].successor = -1;
453      _data[v].parent = _data[w].parent;
454      _data[w].parent = v;
455      _data[w].left = _data[v].right;
456      _data[v].right = w;
457      if (_data[v].parent != -1){
458        if (_data[_data[v].parent].right == w) {
459          _data[_data[v].parent].right = v;
460        } else {
461          _data[_data[v].parent].left = v;
462        }
463      }
464      if (_data[w].left != -1){
465        _data[_data[w].left].parent = w;
466      }
467    }
468
469
470    void zag(int v) {
471
472      Value min = _data[_data[v].parent].dmin;
473
474      int a = _data[v].parent;
475      Value aa = _data[a].dcost;
476      if (_tolerance.less(aa, _max_value)) {
477        aa += min;
478      }
479       
480      int b = v;
481      Value ab = min + _data[b].dmin;
482      Value bb = _data[b].dcost;
483      if (_tolerance.less(bb, _max_value)) {
484        bb += ab;
485      }
486
487      int c = -1;
488      Value cc = _max_value;
489      if (_data[a].left != -1){
490        c = _data[a].left;
491        cc = min + _data[c].dmin;
492      }
493
494      int d = -1;
495      Value dd = _max_value;
496      if (_data[v].right!=-1) {
497        d = _data[v].right;
498        dd = _data[d].dmin;
499        if (_tolerance.less(dd, _max_value)) {
500          dd += ab;
501        }
502      }
503
504      int e = -1;
505      Value ee = _max_value;
506      if (_data[v].left != -1){
507        e = _data[v].left;
508        ee = ab + _data[e].dmin;
509      }
510
511      Value min2;
512      if (_tolerance.less(0, _data[b].dmin) ||
513          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
514        min2 = min;
515      } else {
516        if (_tolerance.less(aa, cc)) {
517          if (_tolerance.less(aa, ee)) {
518            min2 = aa;
519          } else {
520            min2 = ee;
521          }
522        } else if (_tolerance.less(cc, ee)) {
523          min2 = cc;
524        } else {
525          min2 = ee;
526        }
527      }
528      _data[a].dcost = aa;
529      if (_tolerance.less(aa, _max_value)) {
530        _data[a].dcost -= min2;
531      }
532      _data[a].dmin = min2;
533      if (_tolerance.less(min2, _max_value)) {
534        _data[a].dmin -= min;
535      }
536      _data[a].size -= _data[b].size;
537      _data[b].dcost = bb;
538      if (_tolerance.less(bb, _max_value)) {
539        _data[b].dcost -= min;
540      }
541      _data[b].dmin = min;
542      _data[b].size += _data[a].size;
543      if (c != -1) {
544        _data[c].dmin = cc - min2;
545      }
546      if (d != -1) {
547        _data[d].dmin = dd;
548        _data[a].size += _data[d].size;
549        _data[b].size -= _data[d].size;
550        if (_tolerance.less(dd, _max_value)) {
551          _data[d].dmin -= min;
552        }
553      }
554      if (e != -1) {
555        _data[e].dmin = ee - min2;
556      }
557       
558      int w = _data[v].parent;
559      _data[v].successor = _data[w].successor;
560      _data[w].successor = -1;
561      _data[v].parent = _data[w].parent;
562      _data[w].parent = v;
563      _data[w].right = _data[v].left;
564      _data[v].left = w;
565      if (_data[v].parent != -1){
566        if (_data[_data[v].parent].left == w) {
567          _data[_data[v].parent].left = v;
568        } else {
569          _data[_data[v].parent].right = v;
570        }
571      }
572      if (_data[w].right != -1){
573        _data[_data[w].right].parent = w;
574      }
575    }
576
577  private:
578
579    class ItemData {
580    public:
581      Item id;
582      int size;
583      int successor;
584      int parent;
585      int left;
586      int right;
587      Value dmin;
588      Value dcost;
589       
590    public:
591      ItemData(const Item &item)
592        : id(item), size(1), successor(), parent(-1),
593          left(-1), right(-1), dmin(0), dcost(0) {}
594    };
595     
596  };
597
598  template <typename _Value, typename _ItemIntMap, typename _Tolerance>
599  class DynamicTree<_Value, _ItemIntMap, _Tolerance, false> {
600  public:
601    typedef _ItemIntMap ItemIntMap;
602    typedef typename ItemIntMap::Key Item;
603    typedef _Value Value;
604    typedef _Tolerance Tolerance;
605
606  private:
607 
608    class ItemData;
609
610    std::vector<ItemData> _data;
611    ItemIntMap &_iim;
612    Value _max_value;
613    Tolerance _tolerance;
614
615  public:
616    DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
617      : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
618        _tolerance(tolerance) {}
619 
620    ~DynamicTree() {}
621
622    void clear() {
623      _data.clear();
624    }
625
626    void tolerance(const Tolerance& tolerance) const {
627      _tolerance = tolerance;
628      return *this;
629    }
630 
631    const Tolerance& tolerance() const {
632      return tolerance;
633    }
634 
635    void makeTree(const Item &item) {
636      _data[makePath(item)].successor = -1;
637    }
638   
639    Item findRoot(const Item &item) {
640      return _data[findTail(expose(_iim[item]))].id;
641    }
642   
643    Item findCost(const Item &item, Value& d){
644      return _data[findPathCost(expose(_iim[item]),d)].id;
645    }
646   
647    void addCost(const Item &item, Value x){
648      addPathCost(expose(_iim[item]), x);
649    }
650   
651    void link(const Item &item1, const Item &item2){
652      int v = _iim[item1];
653      int w = _iim[item2];
654      int p = expose(w);
655      join(-1, expose(v), p);
656      _data[v].successor = -1;
657    }   
658   
659    void cut(const Item &item) {
660      int v = _iim[item];
661      int p, q;
662      expose(v);
663      split(p, v, q);
664      if (p != -1) {
665        _data[p].successor = v;
666      }
667      if (q != -1) {
668        _data[q].successor = _data[v].successor;
669      }
670      _data[v].successor = -1;
671    }
672
673    Item parent(const Item &item){
674      return _data[_iim[item].p].id;
675    }
676
677    Value maxValue() const {
678      return _max_value;
679    }
680   
681  private:
682
683    int makePath(const Item &item) {
684      _iim.set(item, _data.size());
685      ItemData v(item);
686      _data.push_back(v);
687      return _iim[item];
688    }
689
690    int findPath(int v) {
691      splay(v);
692      return v;
693    }
694   
695    int findPathCost(int p, Value &d) {
696      while ((_data[p].right != -1 &&
697              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
698             (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
699        if (_data[p].right != -1 &&
700            !_tolerance.less(0, _data[_data[p].right].dmin)) {
701          p = _data[p].right;
702        } else if (_data[p].left != -1 &&
703                   !_tolerance.less(0, _data[_data[p].left].dmin)){
704          p = _data[p].left;
705        }
706      }
707      splay(p);
708      d = _data[p].dmin;
709      return p;
710    }
711
712    int findTail(int p) {
713      while (_data[p].right != -1) {
714        p = _data[p].right;
715      }
716      splay(p);
717      return p;
718    }
719   
720    void addPathCost(int p, Value x) {
721      if (!_tolerance.less(x, _max_value)) {
722        _data[p].dmin = x;_data[p].dcost = x;
723      } else if (!_tolerance.less(-x, _max_value)) {
724        _data[p].dmin = 0;
725        _data[p].dcost = 0;
726      } else {
727        _data[p].dmin += x;
728      }
729    }
730
731    void join(int p, int v, int q) {
732      Value min = _max_value;
733      Value pmin = _max_value;
734      Value vmin = _data[v].dmin;
735      Value qmin = _max_value;
736      if (p != -1){
737        pmin = _data[p].dmin;
738      }
739      if (q != -1){
740        qmin = _data[q].dmin;
741      }
742       
743      if (_tolerance.less(vmin, qmin)) {
744        if (_tolerance.less(vmin,pmin)) {
745          min = vmin;
746        } else {
747          min = pmin;
748        }
749      } else if (_tolerance.less(qmin,pmin)) {
750        min = qmin;
751      } else {
752        min = pmin;
753      }
754
755      if (p != -1){
756        _data[p].parent = v;
757        _data[p].dmin -= min;
758      }
759      if (q != -1){
760        _data[q].parent = v;
761        if (_tolerance.less(_data[q].dmin,_max_value)) {
762          _data[q].dmin -= min;
763        }
764      }
765      _data[v].left = p;
766      _data[v].right = q;
767      if (_tolerance.less(min, _max_value)) {
768        _data[v].dcost = _data[v].dmin - min;
769      }
770      _data[v].dmin = min;
771    }
772
773    void split(int &p, int v, int &q){
774      splay(v);
775      p = -1;
776      if (_data[v].left != -1){
777        p = _data[v].left;
778        _data[p].dmin += _data[v].dmin;
779        _data[p].parent = -1;
780        _data[v].left = -1;
781      }
782      q = -1;
783      if (_data[v].right != -1) {
784        q=_data[v].right;
785        if (_tolerance.less(_data[q].dmin, _max_value)) {
786          _data[q].dmin += _data[v].dmin;
787        }
788        _data[q].parent = -1;
789        _data[v].right = -1;
790      }
791      if (_tolerance.less(_data[v].dcost, _max_value)) {
792        _data[v].dmin += _data[v].dcost;
793        _data[v].dcost = 0;
794      } else {
795        _data[v].dmin = _data[v].dcost;
796      }
797    }
798 
799    int expose(int v) {
800      int p, q, r, w;
801      p = -1;
802      while (v != -1) {
803        w = _data[findPath(v)].successor;
804        split(q, v, r);
805        if (q != -1) {
806          _data[q].successor = v;
807        }
808        join(p, v, r);
809        p = v;
810        v = w;
811      }
812      _data[p].successor = -1;
813      return p;
814    }
815
816    void splay(int v) {
817      while (_data[v].parent != -1) {
818        if (v == _data[_data[v].parent].left) {
819          if (_data[_data[v].parent].parent == -1) {
820            zig(v);
821          } else {
822            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
823              zig(_data[v].parent);
824              zig(v);
825            } else {
826              zig(v);
827              zag(v);
828            }
829          }
830        } else {
831          if (_data[_data[v].parent].parent == -1) {
832            zag(v);
833          } else {
834            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
835              zag(v);
836              zig(v);
837            } else {
838              zag(_data[v].parent);
839              zag(v);
840            }
841          }
842        }
843      }
844    }
845
846
847    void zig(int v) {
848      Value min = _data[_data[v].parent].dmin;
849      int a = _data[v].parent;
850       
851      Value aa = _data[a].dcost;
852      if (_tolerance.less(aa, _max_value)) {
853        aa+= min;
854      }
855
856
857      int b = v;
858      Value ab = min + _data[b].dmin;
859      Value bb = _data[b].dcost;
860      if (_tolerance.less(bb, _max_value)) {
861        bb+= ab;
862      }
863
864      int c = -1;
865      Value cc = _max_value;
866      if (_data[a].right != -1) {
867        c = _data[a].right;
868        cc = _data[c].dmin;
869        if (_tolerance.less(cc, _max_value)) {
870          cc+=min;
871        }
872      }
873
874      int d = -1;
875      Value dd = _max_value;
876      if (_data[v].left != -1){
877        d = _data[v].left;
878        dd = ab + _data[d].dmin;
879      }
880
881      int e = -1;
882      Value ee = _max_value;
883      if (_data[v].right != -1) {
884        e = _data[v].right;
885        ee = ab + _data[e].dmin;
886      }
887
888      Value min2;
889      if (_tolerance.less(0, _data[b].dmin) ||
890          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
891        min2 = min;
892      } else {
893        if (_tolerance.less(aa, cc)) {
894          if (_tolerance.less(aa, ee)) {
895            min2 = aa;
896          } else {
897            min2 = ee;
898          }
899        } else if (_tolerance.less(cc, ee)) {
900          min2 = cc;
901        } else {
902          min2 = ee;
903        }
904      }
905       
906      _data[a].dcost = aa;
907      if (_tolerance.less(aa, _max_value)) {
908        _data[a].dcost -= min2;
909      }
910      _data[a].dmin = min2;
911      if (_tolerance.less(min2,_max_value)) {
912        _data[a].dmin -= min;
913      }
914      _data[b].dcost = bb;
915      if (_tolerance.less(bb, _max_value)) {
916        _data[b].dcost -= min;
917      }
918      _data[b].dmin = min;
919      if (c != -1) {
920        _data[c].dmin = cc;
921        if (_tolerance.less(cc, _max_value)) {
922          _data[c].dmin -= min2;
923        }
924      }
925      if (d != -1) {
926        _data[d].dmin = dd - min;
927      }
928      if (e != -1) {
929        _data[e].dmin = ee - min2;
930      }
931       
932      int w = _data[v].parent;
933      _data[v].successor = _data[w].successor;
934      _data[w].successor = -1;
935      _data[v].parent = _data[w].parent;
936      _data[w].parent = v;
937      _data[w].left = _data[v].right;
938      _data[v].right = w;
939      if (_data[v].parent != -1){
940        if (_data[_data[v].parent].right == w) {
941          _data[_data[v].parent].right = v;
942        } else {
943          _data[_data[v].parent].left = v;
944        }
945      }
946      if (_data[w].left != -1){
947        _data[_data[w].left].parent = w;
948      }
949    }
950
951
952    void zag(int v) {
953
954      Value min = _data[_data[v].parent].dmin;
955
956      int a = _data[v].parent;
957      Value aa = _data[a].dcost;
958      if (_tolerance.less(aa, _max_value)) {
959        aa += min;
960      }
961       
962      int b = v;
963      Value ab = min + _data[b].dmin;
964      Value bb = _data[b].dcost;
965      if (_tolerance.less(bb, _max_value)) {
966        bb += ab;
967      }
968
969      int c = -1;
970      Value cc = _max_value;
971      if (_data[a].left != -1){
972        c = _data[a].left;
973        cc = min + _data[c].dmin;
974      }
975
976      int d = -1;
977      Value dd = _max_value;
978      if (_data[v].right!=-1) {
979        d = _data[v].right;
980        dd = _data[d].dmin;
981        if (_tolerance.less(dd, _max_value)) {
982          dd += ab;
983        }
984      }
985
986      int e = -1;
987      Value ee = _max_value;
988      if (_data[v].left != -1){
989        e = _data[v].left;
990        ee = ab + _data[e].dmin;
991      }
992
993      Value min2;
994      if (_tolerance.less(0, _data[b].dmin) ||
995          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
996        min2 = min;
997      } else {
998        if (_tolerance.less(aa, cc)) {
999          if (_tolerance.less(aa, ee)) {
1000            min2 = aa;
1001          } else {
1002            min2 = ee;
1003          }
1004        } else if (_tolerance.less(cc, ee)) {
1005          min2 = cc;
1006        } else {
1007          min2 = ee;
1008        }
1009      }
1010      _data[a].dcost = aa;
1011      if (_tolerance.less(aa, _max_value)) {
1012        _data[a].dcost -= min2;
1013      }
1014      _data[a].dmin = min2;
1015      if (_tolerance.less(min2, _max_value)) {
1016        _data[a].dmin -= min;
1017      }
1018      _data[b].dcost = bb;
1019      if (_tolerance.less(bb, _max_value)) {
1020        _data[b].dcost -= min;
1021      }
1022      _data[b].dmin = min;
1023      if (c != -1) {
1024        _data[c].dmin = cc - min2;
1025      }
1026      if (d != -1) {
1027        _data[d].dmin = dd;
1028        if (_tolerance.less(dd, _max_value)) {
1029          _data[d].dmin -= min;
1030        }
1031      }
1032      if (e != -1) {
1033        _data[e].dmin = ee - min2;
1034      }
1035       
1036      int w = _data[v].parent;
1037      _data[v].successor = _data[w].successor;
1038      _data[w].successor = -1;
1039      _data[v].parent = _data[w].parent;
1040      _data[w].parent = v;
1041      _data[w].right = _data[v].left;
1042      _data[v].left = w;
1043      if (_data[v].parent != -1){
1044        if (_data[_data[v].parent].left == w) {
1045          _data[_data[v].parent].left = v;
1046        } else {
1047          _data[_data[v].parent].right = v;
1048        }
1049      }
1050      if (_data[w].right != -1){
1051        _data[_data[w].right].parent = w;
1052      }
1053    }
1054
1055  private:
1056
1057    class ItemData {
1058    public:
1059      Item id;
1060      int successor;
1061      int parent;
1062      int left;
1063      int right;
1064      Value dmin;
1065      Value dcost;
1066       
1067    public:
1068      ItemData(const Item &item)
1069        : id(item), successor(), parent(-1),
1070          left(-1), right(-1), dmin(0), dcost(0) {}
1071    };
1072     
1073  };
1074
1075}
1076
1077#endif
Note: See TracBrowser for help on using the repository browser.