deba@2514: /* -*- C++ -*-
deba@2514:  *
deba@2514:  * This file is a part of LEMON, a generic C++ optimization library
deba@2514:  *
alpar@2553:  * Copyright (C) 2003-2008
deba@2514:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2514:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2514:  *
deba@2514:  * Permission to use, modify and distribute this software is granted
deba@2514:  * provided that this copyright notice appears in all copies. For
deba@2514:  * precise terms see the accompanying LICENSE file.
deba@2514:  *
deba@2514:  * This software is provided "AS IS" with no warranty of any kind,
deba@2514:  * express or implied, and with no claim as to its suitability for any
deba@2514:  * purpose.
deba@2514:  *
deba@2514:  */
alpar@2553: 
deba@2514: #ifndef LEMON_DYNAMIC_TREE_H
deba@2514: #define LEMON_DYNAMIC_TREE_H
deba@2514: 
deba@2514: /// \ingroup auxdata
deba@2514: /// \file
deba@2514: /// \brief The dynamic tree data structure of Sleator and Tarjan.
deba@2514: ///
deba@2514: 
deba@2514: #include <vector>
deba@2514: #include <limits>
deba@2514: #include <lemon/tolerance.h>
deba@2514: 
deba@2514: namespace lemon {
deba@2514: 
deba@2514:   /// \ingroup auxdata
deba@2514:   ///
deba@2514:   /// \brief The dynamic tree data structure of Sleator and Tarjan.
deba@2514:   ///
deba@2514:   /// This class provides an implementation of the dynamic tree data
deba@2514:   /// structure for maintaining a set of node-disjoint rooted
deba@2514:   /// trees. Each item has an associated value, and the item with
deba@2514:   /// minimum value can be find in \f$O(\log(n)\f$ on the path from a
deba@2514:   /// node to the its root, and the items on such path can be
deba@2514:   /// increased or decreased globally with a certain value in the same
deba@2514:   /// running time. We regard a tree edge as directed toward the root,
deba@2514:   /// that is from child to parent. Its structure can be modified by
deba@2514:   /// two basic operations: \e link(v,w) adds an edge between a root v
deba@2514:   /// and a node w in a different component; \e cut(v) removes the
deba@2514:   /// edge between v and its parent.
deba@2514:   /// 
deba@2514:   /// \param _Value The value type of the items.  
deba@2514:   /// \param _ItemIntMap Converts item type of node to integer.
deba@2514:   /// \param _Tolerance The tolerance class to handle computation
deba@2514:   /// problems.
deba@2514:   /// \param _enableSize If true then the data structre manatain the
deba@2514:   /// size of each tree. The feature is used in \ref GoldbergTarjan
deba@2514:   /// algorithm. The default value is true.
deba@2514:   ///
deba@2514:   /// \author Hamori Tamas
deba@2514: #ifdef DOXYGEN
deba@2514:   template <typename _Value, typename _ItemIntMap, 
deba@2514: 	    typename _Tolerance, bool _enableSize>
deba@2514: #else
deba@2514:   template <typename _Value, typename _ItemIntMap, 
deba@2514: 	    typename _Tolerance = lemon::Tolerance<_Value>,
deba@2514: 	    bool _enableSize = true>
deba@2514: #endif
deba@2514:   class DynamicTree {
deba@2514:   public:
deba@2514:     /// \brief The integer map on the items.
deba@2514:     typedef _ItemIntMap ItemIntMap;
deba@2514:     /// \brief The item type of nodes.
deba@2514:     typedef typename ItemIntMap::Key Item;
deba@2514:     /// \brief The value type of the algorithms.
deba@2514:     typedef _Value Value;
deba@2514:     /// \brief The tolerance used by the algorithm.
deba@2514:     typedef _Tolerance Tolerance;
deba@2514: 
deba@2514:   private:
deba@2514:   
deba@2514:     class ItemData;
deba@2514: 
deba@2514:     std::vector<ItemData> _data;
deba@2514:     ItemIntMap &_iim;
deba@2514:     Value _max_value;
deba@2514:     Tolerance _tolerance;
deba@2514: 
deba@2514:   public:
deba@2514:     /// \brief The constructor of the class.
deba@2514:     ///
deba@2514:     /// \param iim The integer map on the items. 
deba@2514:     /// \param tolerance Tolerance class.
deba@2514:     DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
deba@2514:       : _iim(iim), _max_value(std::numeric_limits<Value>::max()), 
deba@2514: 	_tolerance(tolerance) {}
deba@2514:   
deba@2514:     ~DynamicTree() {}
deba@2514: 
deba@2514:     /// \brief Clears the data structure
deba@2514:     ///
deba@2514:     /// Clears the data structure
deba@2514:     void clear() {
deba@2514:       _data.clear();
deba@2514:     }
deba@2514: 
deba@2514:     /// \brief Sets the tolerance used by algorithm.
deba@2514:     ///
deba@2514:     /// Sets the tolerance used by algorithm.
deba@2514:     void tolerance(const Tolerance& tolerance) const {
deba@2514:       _tolerance = tolerance;
deba@2514:       return *this;
deba@2514:     } 
deba@2514:   
deba@2514:     /// \brief Returns the tolerance used by algorithm.
deba@2514:     ///
deba@2514:     /// Returns the tolerance used by algorithm.
deba@2514:     const Tolerance& tolerance() const {
deba@2514:       return tolerance;
deba@2514:     } 
deba@2514:   
deba@2514:     /// \brief Create a new tree containing a single node with cost zero.
deba@2514:     void makeTree(const Item &item) {
deba@2514:       _data[makePath(item)].successor = -1;
deba@2514:     }
deba@2514:     
deba@2514:     /// \brief Return the root of the tree containing node with itemtype
deba@2514:     /// \e item.
deba@2514:     Item findRoot(const Item &item) {
deba@2514:       return _data[findTail(expose(_iim[item]))].id;
deba@2514:     }
deba@2514:     
deba@2514:     /// \brief Return the the value of nodes in the tree containing
deba@2514:     /// node with itemtype \e item.
deba@2514:     int findSize(const Item &item) {
deba@2514:       return _data[expose(_iim[item])].size;
deba@2514:     }
deba@2514:     
deba@2514:     /// \brief Return the minimum cost containing node.
deba@2514:     /// 
deba@2514:     /// Return into \e d the minimum cost on the tree path from \e item
deba@2514:     /// to findRoot(item).  Return the last item (closest to its root)
deba@2514:     /// on this path of the minimum cost.
deba@2514:     Item findCost(const Item &item, Value& d){
deba@2514:       return _data[findPathCost(expose(_iim[item]),d)].id;
deba@2514:     }
deba@2514:     
deba@2514:     /// \brief Add \e x value to the cost of every node on the path from
deba@2514:     /// \e item to findRoot(item).
deba@2519:     void addCost(const Item &item, Value x) {
deba@2514:       addPathCost(expose(_iim[item]), x);
deba@2514:     }
deba@2514:     
deba@2514:     /// \brief Combine the trees containing nodes \e item1 and \e item2
deba@2514:     /// by adding an edge from \e item1 \e item2.
deba@2514:     /// 
deba@2514:     /// This operation assumes that \e item1 is root and \e item2 is in
deba@2514:     /// a different tree.
deba@2514:     void link(const Item &item1, const Item &item2){
deba@2514:       int v = _iim[item1];
deba@2514:       int w = _iim[item2];
deba@2514:       int p = expose(w);
deba@2514:       join(-1, expose(v), p);
deba@2514:       _data[v].successor = -1;
deba@2514:       _data[v].size += _data[p].size;
deba@2514: 
deba@2514:     }    
deba@2514:     
deba@2514:     /// \brief Divide the tree containing node \e item into two trees by
deba@2514:     /// deleting the edge out of \e item.
deba@2514:     /// 
deba@2514:     /// This operation assumes that \e item is not a tree root.
deba@2514:     void cut(const Item &item) {
deba@2514:       int v = _iim[item];
deba@2514:       int p, q;
deba@2514:       expose(v);
deba@2514:       split(p, v, q);
deba@2514:       if (p != -1) {
deba@2514: 	_data[p].successor = v;
deba@2514:       }
deba@2514:       _data[v].size -= _data[q].size;
deba@2514:       if (q != -1) {
deba@2514: 	_data[q].successor = _data[v].successor;
deba@2514:       }
deba@2514:       _data[v].successor = -1;
deba@2514:     }
deba@2514: 
deba@2514:     ///\brief 
deba@2514:     Item parent(const Item &item){
deba@2514:       return _data[_iim[item].p].id;
deba@2514:     }
deba@2514: 
deba@2514:     ///\brief Return the upper bound of the costs.
deba@2514:     Value maxValue() const {
deba@2514:       return _max_value;
deba@2514:     }
deba@2514:     
deba@2514:   private:
deba@2514: 
deba@2514:     int makePath(const Item &item) {
deba@2514:       _iim.set(item, _data.size());
deba@2514:       ItemData v(item);
deba@2514:       _data.push_back(v);
deba@2514:       return _iim[item];
deba@2514:     }
deba@2514: 
deba@2519:     int findPath(int v) {
deba@2514:       splay(v);
deba@2514:       return v;
deba@2514:     }
deba@2514:     
deba@2519:     int findPathCost(int p, Value &d) {
deba@2514:       while ((_data[p].right != -1 && 
deba@2514: 	      !_tolerance.less(0, _data[_data[p].right].dmin)) || 
deba@2514: 	     (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
deba@2514: 	if (_data[p].right != -1 && 
deba@2514: 	    !_tolerance.less(0, _data[_data[p].right].dmin)) {
deba@2514: 	  p = _data[p].right;
deba@2514: 	} else if (_data[p].left != -1 && 
deba@2519: 		   !_tolerance.less(0, _data[_data[p].left].dmin)) {
deba@2514: 	  p = _data[p].left;
deba@2514: 	}
deba@2514:       }
deba@2514:       splay(p);
deba@2514:       d = _data[p].dmin;
deba@2514:       return p; 
deba@2514:     }
deba@2514: 
deba@2514:     int findTail(int p){
deba@2514:       while (_data[p].right != -1) {
deba@2514: 	p = _data[p].right;
deba@2514:       }
deba@2514:       splay(p);
deba@2514:       return p;
deba@2514:     }
deba@2514:     
deba@2519:     void addPathCost(int p, Value x) {
deba@2514:       if (!_tolerance.less(x, _max_value)) {
deba@2519: 	_data[p].dmin = x;
deba@2519: 	_data[p].dcost = x;
deba@2514:       } else if (!_tolerance.less(-x, _max_value)) {
deba@2514: 	_data[p].dmin = 0;
deba@2514: 	_data[p].dcost = 0;
deba@2514:       } else {
deba@2514: 	_data[p].dmin += x;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514:     void join(int p, int v, int q) {
deba@2514:       Value min = _max_value;
deba@2514:       Value pmin = _max_value;
deba@2514:       Value vmin = _data[v].dmin;
deba@2514:       Value qmin = _max_value;
deba@2514:       if (p != -1){
deba@2514: 	pmin = _data[p].dmin;
deba@2514:       }
deba@2514:       if (q != -1){
deba@2514: 	qmin = _data[q].dmin;
deba@2514:       }
deba@2514:         
deba@2514:       if (_tolerance.less(vmin, qmin)) {
deba@2514: 	if (_tolerance.less(vmin,pmin)) {
deba@2514: 	  min = vmin;
deba@2514: 	} else {
deba@2514: 	  min = pmin;
deba@2514: 	}
deba@2514:       } else if (_tolerance.less(qmin,pmin)) {
deba@2514: 	min = qmin;
deba@2514:       } else {
deba@2514: 	min = pmin;
deba@2514:       }
deba@2514: 
deba@2514:       if (p != -1){
deba@2514: 	_data[p].parent = v;
deba@2514: 	_data[p].dmin -= min;
deba@2514:       }
deba@2514:       if (q!=-1){
deba@2514: 	_data[q].parent = v;
deba@2514: 	if (_tolerance.less(_data[q].dmin,_max_value)) {
deba@2514: 	  _data[q].dmin -= min;
deba@2514: 	}
deba@2514:       }
deba@2514:       _data[v].left = p;
deba@2514:       _data[v].right = q;
deba@2514:       if (_tolerance.less(min,_max_value)) {
deba@2514: 	_data[v].dcost = _data[v].dmin - min;
deba@2514:       }
deba@2514:       _data[v].dmin = min;
deba@2514:     }
deba@2514: 
deba@2514:     void split(int &p, int v, int &q){
deba@2514:       splay(v);
deba@2514:       p = -1;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	p = _data[v].left;
deba@2514: 	_data[p].dmin += _data[v].dmin;
deba@2514: 	_data[p].parent = -1;
deba@2514: 	_data[v].left = -1;
deba@2514:       }
deba@2514:       q = -1;
deba@2514:       if (_data[v].right != -1) {
deba@2514: 	q=_data[v].right;
deba@2514: 	if (_tolerance.less(_data[q].dmin, _max_value)) {
deba@2514: 	  _data[q].dmin += _data[v].dmin;
deba@2514: 	}
deba@2514: 	_data[q].parent = -1;
deba@2514: 	_data[v].right = -1;
deba@2514:       } 
deba@2514:       if (_tolerance.less(_data[v].dcost, _max_value)) {
deba@2514: 	_data[v].dmin += _data[v].dcost;
deba@2514: 	_data[v].dcost = 0;
deba@2514:       } else {
deba@2514: 	_data[v].dmin = _data[v].dcost;
deba@2514:       }
deba@2514:     }
deba@2514:  
deba@2514:     int expose(int v) {
deba@2514:       int p, q, r, w;
deba@2514:       p = -1;
deba@2514:       while (v != -1) {
deba@2514: 	w = _data[findPath(v)].successor;
deba@2514: 	split(q, v, r);
deba@2514: 	if (q != -1) {
deba@2514: 	  _data[q].successor = v;
deba@2514: 	}
deba@2514: 	join(p, v, r);
deba@2514: 	p = v;
deba@2514: 	v = w;
deba@2514:       }
deba@2514:       _data[p].successor = -1;
deba@2514:       return p;
deba@2514:     }
deba@2514: 
deba@2514:     void splay(int v) {
deba@2514:       while (_data[v].parent != -1) {
deba@2514: 	if (v == _data[_data[v].parent].left) {
deba@2514: 	  if (_data[_data[v].parent].parent == -1) {
deba@2514: 	    zig(v);
deba@2514: 	  } else {
deba@2514: 	    if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
deba@2514: 	      zig(_data[v].parent);
deba@2514: 	      zig(v);
deba@2514: 	    } else {
deba@2514: 	      zig(v);
deba@2514: 	      zag(v);
deba@2514: 	    }
deba@2514: 	  }
deba@2514: 	} else {
deba@2514: 	  if (_data[_data[v].parent].parent == -1) {
deba@2514: 	    zag(v);
deba@2514: 	  } else {
deba@2514: 	    if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
deba@2514: 	      zag(v);
deba@2514: 	      zig(v);
deba@2514: 	    } else {
deba@2514: 	      zag(_data[v].parent);
deba@2514: 	      zag(v);
deba@2514: 	    }
deba@2514: 	  }
deba@2514: 	}
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514: 
deba@2514:     void zig(int v) {
deba@2514:       Value min = _data[_data[v].parent].dmin;
deba@2514:       int a = _data[v].parent;
deba@2514:         
deba@2514:       Value aa = _data[a].dcost;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2519: 	aa += min;
deba@2514:       }
deba@2514: 
deba@2514: 
deba@2514:       int b = v;
deba@2514:       Value ab = min + _data[b].dmin;
deba@2514:       Value bb = _data[b].dcost;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2519: 	bb += ab;
deba@2514:       }
deba@2514: 
deba@2514:       int c = -1;
deba@2514:       Value cc = _max_value;
deba@2514:       if (_data[a].right != -1) {
deba@2514: 	c = _data[a].right;
deba@2514: 	cc = _data[c].dmin;
deba@2514: 	if (_tolerance.less(cc, _max_value)) {
deba@2519: 	  cc += min;
deba@2514: 	}
deba@2514:       }
deba@2514: 
deba@2514:       int d = -1;
deba@2514:       Value dd = _max_value;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	d = _data[v].left;
deba@2514: 	dd = ab + _data[d].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       int e = -1;
deba@2514:       Value ee = _max_value;
deba@2514:       if (_data[v].right != -1) {
deba@2514: 	e = _data[v].right;
deba@2514: 	ee = ab + _data[e].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       Value min2;
deba@2514:       if (_tolerance.less(0, _data[b].dmin) || 
deba@2514: 	  (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
deba@2514: 	min2 = min;
deba@2514:       } else {
deba@2514: 	if (_tolerance.less(aa, cc)) {
deba@2514: 	  if (_tolerance.less(aa, ee)) {
deba@2514: 	    min2 = aa;
deba@2514: 	  } else {
deba@2514: 	    min2 = ee;
deba@2514: 	  }
deba@2514: 	} else if (_tolerance.less(cc, ee)) {
deba@2514: 	  min2 = cc;
deba@2514: 	} else {
deba@2514: 	  min2 = ee;
deba@2514: 	}
deba@2514:       }
deba@2514:         
deba@2514:       _data[a].dcost = aa;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	_data[a].dcost -= min2;
deba@2514:       }
deba@2514:       _data[a].dmin = min2;
deba@2514:       if (_tolerance.less(min2,_max_value)) { 
deba@2514: 	_data[a].dmin -= min; 
deba@2514:       }
deba@2514:       _data[a].size -= _data[b].size;
deba@2514:       _data[b].dcost = bb;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2514: 	_data[b].dcost -= min;
deba@2514:       }
deba@2514:       _data[b].dmin = min;
deba@2514:       _data[b].size += _data[a].size;
deba@2514:       if (c != -1) {
deba@2514: 	_data[c].dmin = cc;
deba@2514: 	if (_tolerance.less(cc, _max_value)) {
deba@2514: 	  _data[c].dmin -= min2;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (d != -1) {
deba@2514: 	_data[d].dmin = dd - min;
deba@2514: 	_data[a].size += _data[d].size;
deba@2514: 	_data[b].size -= _data[d].size;
deba@2514:       }
deba@2514:       if (e != -1) {
deba@2514: 	_data[e].dmin = ee - min2;
deba@2514:       }
deba@2514:         
deba@2514:       int w = _data[v].parent;
deba@2514:       _data[v].successor = _data[w].successor;
deba@2514:       _data[w].successor = -1;
deba@2514:       _data[v].parent = _data[w].parent;
deba@2514:       _data[w].parent = v;
deba@2514:       _data[w].left = _data[v].right;
deba@2514:       _data[v].right = w;
deba@2514:       if (_data[v].parent != -1){
deba@2514: 	if (_data[_data[v].parent].right == w) {
deba@2514: 	  _data[_data[v].parent].right = v;
deba@2514: 	} else {
deba@2514: 	  _data[_data[v].parent].left = v;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (_data[w].left != -1){
deba@2514: 	_data[_data[w].left].parent = w;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514: 
deba@2514:     void zag(int v) {
deba@2514: 
deba@2514:       Value min = _data[_data[v].parent].dmin;
deba@2514: 
deba@2514:       int a = _data[v].parent;
deba@2514:       Value aa = _data[a].dcost;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	aa += min;
deba@2514:       }
deba@2514:         
deba@2514:       int b = v;
deba@2514:       Value ab = min + _data[b].dmin;
deba@2514:       Value bb = _data[b].dcost;
deba@2514:       if (_tolerance.less(bb, _max_value)) {
deba@2514: 	bb += ab;
deba@2514:       }
deba@2514: 
deba@2514:       int c = -1;
deba@2514:       Value cc = _max_value;
deba@2514:       if (_data[a].left != -1){
deba@2514: 	c = _data[a].left;
deba@2514: 	cc = min + _data[c].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       int d = -1;
deba@2514:       Value dd = _max_value;
deba@2514:       if (_data[v].right!=-1) {
deba@2514: 	d = _data[v].right;
deba@2514: 	dd = _data[d].dmin;
deba@2514: 	if (_tolerance.less(dd, _max_value)) {
deba@2514: 	  dd += ab;
deba@2514: 	}
deba@2514:       }
deba@2514: 
deba@2514:       int e = -1;
deba@2514:       Value ee = _max_value;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	e = _data[v].left;
deba@2514: 	ee = ab + _data[e].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       Value min2;
deba@2514:       if (_tolerance.less(0, _data[b].dmin) || 
deba@2514: 	  (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
deba@2514: 	min2 = min;
deba@2514:       } else {
deba@2514: 	if (_tolerance.less(aa, cc)) {
deba@2514: 	  if (_tolerance.less(aa, ee)) {
deba@2514: 	    min2 = aa;
deba@2514: 	  } else {
deba@2514: 	    min2 = ee;
deba@2514: 	  }
deba@2514: 	} else if (_tolerance.less(cc, ee)) {
deba@2514: 	  min2 = cc;
deba@2514: 	} else {
deba@2514: 	  min2 = ee;
deba@2514: 	}
deba@2514:       }
deba@2514:       _data[a].dcost = aa;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	_data[a].dcost -= min2;
deba@2514:       }
deba@2514:       _data[a].dmin = min2;
deba@2514:       if (_tolerance.less(min2, _max_value)) {
deba@2514: 	_data[a].dmin -= min;
deba@2514:       }
deba@2514:       _data[a].size -= _data[b].size;
deba@2514:       _data[b].dcost = bb;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2514: 	_data[b].dcost -= min;
deba@2514:       }
deba@2514:       _data[b].dmin = min;
deba@2514:       _data[b].size += _data[a].size;
deba@2514:       if (c != -1) {
deba@2514: 	_data[c].dmin = cc - min2;
deba@2514:       }
deba@2514:       if (d != -1) {
deba@2514: 	_data[d].dmin = dd;
deba@2514: 	_data[a].size += _data[d].size;
deba@2514: 	_data[b].size -= _data[d].size;
deba@2514: 	if (_tolerance.less(dd, _max_value)) {
deba@2514: 	  _data[d].dmin -= min;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (e != -1) {
deba@2514: 	_data[e].dmin = ee - min2;
deba@2514:       }
deba@2514:         
deba@2514:       int w = _data[v].parent;
deba@2514:       _data[v].successor = _data[w].successor;
deba@2514:       _data[w].successor = -1;
deba@2514:       _data[v].parent = _data[w].parent;
deba@2514:       _data[w].parent = v;
deba@2514:       _data[w].right = _data[v].left;
deba@2514:       _data[v].left = w;
deba@2514:       if (_data[v].parent != -1){
deba@2514: 	if (_data[_data[v].parent].left == w) {
deba@2514: 	  _data[_data[v].parent].left = v;
deba@2514: 	} else {
deba@2514: 	  _data[_data[v].parent].right = v;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (_data[w].right != -1){
deba@2514: 	_data[_data[w].right].parent = w;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514:   private:
deba@2514: 
deba@2514:     class ItemData {
deba@2514:     public:
deba@2514:       Item id;
deba@2514:       int size;
deba@2514:       int successor;
deba@2514:       int parent;
deba@2514:       int left;
deba@2514:       int right;
deba@2514:       Value dmin;
deba@2514:       Value dcost;
deba@2514:         
deba@2514:     public:
deba@2514:       ItemData(const Item &item)
deba@2514: 	: id(item), size(1), successor(), parent(-1), 
deba@2514: 	  left(-1), right(-1), dmin(0), dcost(0) {}
deba@2514:     };
deba@2514:      
deba@2514:   };
deba@2514: 
deba@2514:   template <typename _Value, typename _ItemIntMap, typename _Tolerance>
deba@2514:   class DynamicTree<_Value, _ItemIntMap, _Tolerance, false> {
deba@2514:   public:
deba@2514:     typedef _ItemIntMap ItemIntMap;
deba@2514:     typedef typename ItemIntMap::Key Item;
deba@2514:     typedef _Value Value;
deba@2514:     typedef _Tolerance Tolerance;
deba@2514: 
deba@2514:   private:
deba@2514:   
deba@2514:     class ItemData;
deba@2514: 
deba@2514:     std::vector<ItemData> _data;
deba@2514:     ItemIntMap &_iim;
deba@2514:     Value _max_value;
deba@2514:     Tolerance _tolerance;
deba@2514: 
deba@2514:   public:
deba@2514:     DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
deba@2514:       : _iim(iim), _max_value(std::numeric_limits<Value>::max()), 
deba@2514: 	_tolerance(tolerance) {}
deba@2514:   
deba@2514:     ~DynamicTree() {}
deba@2514: 
deba@2514:     void clear() {
deba@2514:       _data.clear();
deba@2514:     }
deba@2514: 
deba@2514:     void tolerance(const Tolerance& tolerance) const {
deba@2514:       _tolerance = tolerance;
deba@2514:       return *this;
deba@2514:     } 
deba@2514:   
deba@2514:     const Tolerance& tolerance() const {
deba@2514:       return tolerance;
deba@2514:     } 
deba@2514:   
deba@2514:     void makeTree(const Item &item) {
deba@2514:       _data[makePath(item)].successor = -1;
deba@2514:     }
deba@2514:     
deba@2514:     Item findRoot(const Item &item) {
deba@2514:       return _data[findTail(expose(_iim[item]))].id;
deba@2514:     }
deba@2514:     
deba@2514:     Item findCost(const Item &item, Value& d){
deba@2514:       return _data[findPathCost(expose(_iim[item]),d)].id;
deba@2514:     }
deba@2514:     
deba@2514:     void addCost(const Item &item, Value x){
deba@2514:       addPathCost(expose(_iim[item]), x);
deba@2514:     }
deba@2514:     
deba@2514:     void link(const Item &item1, const Item &item2){
deba@2514:       int v = _iim[item1];
deba@2514:       int w = _iim[item2];
deba@2514:       int p = expose(w);
deba@2514:       join(-1, expose(v), p);
deba@2514:       _data[v].successor = -1;
deba@2514:     }    
deba@2514:     
deba@2514:     void cut(const Item &item) {
deba@2514:       int v = _iim[item];
deba@2514:       int p, q;
deba@2514:       expose(v);
deba@2514:       split(p, v, q);
deba@2514:       if (p != -1) {
deba@2514: 	_data[p].successor = v;
deba@2514:       }
deba@2514:       if (q != -1) {
deba@2514: 	_data[q].successor = _data[v].successor;
deba@2514:       }
deba@2514:       _data[v].successor = -1;
deba@2514:     }
deba@2514: 
deba@2514:     Item parent(const Item &item){
deba@2514:       return _data[_iim[item].p].id;
deba@2514:     }
deba@2514: 
deba@2514:     Value maxValue() const {
deba@2514:       return _max_value;
deba@2514:     }
deba@2514:     
deba@2514:   private:
deba@2514: 
deba@2514:     int makePath(const Item &item) {
deba@2514:       _iim.set(item, _data.size());
deba@2514:       ItemData v(item);
deba@2514:       _data.push_back(v);
deba@2514:       return _iim[item];
deba@2514:     }
deba@2514: 
deba@2519:     int findPath(int v) {
deba@2514:       splay(v);
deba@2514:       return v;
deba@2514:     }
deba@2514:     
deba@2519:     int findPathCost(int p, Value &d) {
deba@2514:       while ((_data[p].right != -1 && 
deba@2514: 	      !_tolerance.less(0, _data[_data[p].right].dmin)) || 
deba@2514: 	     (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
deba@2514: 	if (_data[p].right != -1 && 
deba@2514: 	    !_tolerance.less(0, _data[_data[p].right].dmin)) {
deba@2514: 	  p = _data[p].right;
deba@2514: 	} else if (_data[p].left != -1 && 
deba@2514: 		   !_tolerance.less(0, _data[_data[p].left].dmin)){
deba@2514: 	  p = _data[p].left;
deba@2514: 	}
deba@2514:       }
deba@2514:       splay(p);
deba@2514:       d = _data[p].dmin;
deba@2514:       return p; 
deba@2514:     }
deba@2514: 
deba@2519:     int findTail(int p) {
deba@2514:       while (_data[p].right != -1) {
deba@2514: 	p = _data[p].right;
deba@2514:       }
deba@2514:       splay(p);
deba@2514:       return p;
deba@2514:     }
deba@2514:     
deba@2519:     void addPathCost(int p, Value x) {
deba@2514:       if (!_tolerance.less(x, _max_value)) {
deba@2514: 	_data[p].dmin = x;_data[p].dcost = x;
deba@2514:       } else if (!_tolerance.less(-x, _max_value)) {
deba@2514: 	_data[p].dmin = 0;
deba@2514: 	_data[p].dcost = 0;
deba@2514:       } else {
deba@2514: 	_data[p].dmin += x;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514:     void join(int p, int v, int q) {
deba@2514:       Value min = _max_value;
deba@2514:       Value pmin = _max_value;
deba@2514:       Value vmin = _data[v].dmin;
deba@2514:       Value qmin = _max_value;
deba@2514:       if (p != -1){
deba@2514: 	pmin = _data[p].dmin;
deba@2514:       }
deba@2514:       if (q != -1){
deba@2514: 	qmin = _data[q].dmin;
deba@2514:       }
deba@2514:         
deba@2514:       if (_tolerance.less(vmin, qmin)) {
deba@2514: 	if (_tolerance.less(vmin,pmin)) {
deba@2514: 	  min = vmin;
deba@2514: 	} else {
deba@2514: 	  min = pmin;
deba@2514: 	}
deba@2514:       } else if (_tolerance.less(qmin,pmin)) {
deba@2514: 	min = qmin;
deba@2514:       } else {
deba@2514: 	min = pmin;
deba@2514:       }
deba@2514: 
deba@2514:       if (p != -1){
deba@2514: 	_data[p].parent = v;
deba@2514: 	_data[p].dmin -= min;
deba@2514:       }
deba@2519:       if (q != -1){
deba@2514: 	_data[q].parent = v;
deba@2514: 	if (_tolerance.less(_data[q].dmin,_max_value)) {
deba@2514: 	  _data[q].dmin -= min;
deba@2514: 	}
deba@2514:       }
deba@2514:       _data[v].left = p;
deba@2514:       _data[v].right = q;
deba@2519:       if (_tolerance.less(min, _max_value)) {
deba@2514: 	_data[v].dcost = _data[v].dmin - min;
deba@2514:       }
deba@2514:       _data[v].dmin = min;
deba@2514:     }
deba@2514: 
deba@2514:     void split(int &p, int v, int &q){
deba@2514:       splay(v);
deba@2514:       p = -1;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	p = _data[v].left;
deba@2514: 	_data[p].dmin += _data[v].dmin;
deba@2514: 	_data[p].parent = -1;
deba@2514: 	_data[v].left = -1;
deba@2514:       }
deba@2514:       q = -1;
deba@2514:       if (_data[v].right != -1) {
deba@2514: 	q=_data[v].right;
deba@2514: 	if (_tolerance.less(_data[q].dmin, _max_value)) {
deba@2514: 	  _data[q].dmin += _data[v].dmin;
deba@2514: 	}
deba@2514: 	_data[q].parent = -1;
deba@2514: 	_data[v].right = -1;
deba@2514:       } 
deba@2514:       if (_tolerance.less(_data[v].dcost, _max_value)) {
deba@2514: 	_data[v].dmin += _data[v].dcost;
deba@2514: 	_data[v].dcost = 0;
deba@2514:       } else {
deba@2514: 	_data[v].dmin = _data[v].dcost;
deba@2514:       }
deba@2514:     }
deba@2514:  
deba@2514:     int expose(int v) {
deba@2514:       int p, q, r, w;
deba@2514:       p = -1;
deba@2514:       while (v != -1) {
deba@2514: 	w = _data[findPath(v)].successor;
deba@2514: 	split(q, v, r);
deba@2514: 	if (q != -1) {
deba@2514: 	  _data[q].successor = v;
deba@2514: 	}
deba@2514: 	join(p, v, r);
deba@2514: 	p = v;
deba@2514: 	v = w;
deba@2514:       }
deba@2514:       _data[p].successor = -1;
deba@2514:       return p;
deba@2514:     }
deba@2514: 
deba@2514:     void splay(int v) {
deba@2514:       while (_data[v].parent != -1) {
deba@2514: 	if (v == _data[_data[v].parent].left) {
deba@2514: 	  if (_data[_data[v].parent].parent == -1) {
deba@2514: 	    zig(v);
deba@2514: 	  } else {
deba@2514: 	    if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
deba@2514: 	      zig(_data[v].parent);
deba@2514: 	      zig(v);
deba@2514: 	    } else {
deba@2514: 	      zig(v);
deba@2514: 	      zag(v);
deba@2514: 	    }
deba@2514: 	  }
deba@2514: 	} else {
deba@2514: 	  if (_data[_data[v].parent].parent == -1) {
deba@2514: 	    zag(v);
deba@2514: 	  } else {
deba@2514: 	    if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
deba@2514: 	      zag(v);
deba@2514: 	      zig(v);
deba@2514: 	    } else {
deba@2514: 	      zag(_data[v].parent);
deba@2514: 	      zag(v);
deba@2514: 	    }
deba@2514: 	  }
deba@2514: 	}
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514: 
deba@2514:     void zig(int v) {
deba@2514:       Value min = _data[_data[v].parent].dmin;
deba@2514:       int a = _data[v].parent;
deba@2514:         
deba@2514:       Value aa = _data[a].dcost;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	aa+= min;
deba@2514:       }
deba@2514: 
deba@2514: 
deba@2514:       int b = v;
deba@2514:       Value ab = min + _data[b].dmin;
deba@2514:       Value bb = _data[b].dcost;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2514: 	bb+= ab;
deba@2514:       }
deba@2514: 
deba@2514:       int c = -1;
deba@2514:       Value cc = _max_value;
deba@2514:       if (_data[a].right != -1) {
deba@2514: 	c = _data[a].right;
deba@2514: 	cc = _data[c].dmin;
deba@2514: 	if (_tolerance.less(cc, _max_value)) {
deba@2514: 	  cc+=min;
deba@2514: 	}
deba@2514:       }
deba@2514: 
deba@2514:       int d = -1;
deba@2514:       Value dd = _max_value;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	d = _data[v].left;
deba@2514: 	dd = ab + _data[d].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       int e = -1;
deba@2514:       Value ee = _max_value;
deba@2514:       if (_data[v].right != -1) {
deba@2514: 	e = _data[v].right;
deba@2514: 	ee = ab + _data[e].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       Value min2;
deba@2514:       if (_tolerance.less(0, _data[b].dmin) || 
deba@2514: 	  (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
deba@2514: 	min2 = min;
deba@2514:       } else {
deba@2514: 	if (_tolerance.less(aa, cc)) {
deba@2514: 	  if (_tolerance.less(aa, ee)) {
deba@2514: 	    min2 = aa;
deba@2514: 	  } else {
deba@2514: 	    min2 = ee;
deba@2514: 	  }
deba@2514: 	} else if (_tolerance.less(cc, ee)) {
deba@2514: 	  min2 = cc;
deba@2514: 	} else {
deba@2514: 	  min2 = ee;
deba@2514: 	}
deba@2514:       }
deba@2514:         
deba@2514:       _data[a].dcost = aa;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	_data[a].dcost -= min2;
deba@2514:       }
deba@2514:       _data[a].dmin = min2;
deba@2514:       if (_tolerance.less(min2,_max_value)) { 
deba@2514: 	_data[a].dmin -= min; 
deba@2514:       }
deba@2514:       _data[b].dcost = bb;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2514: 	_data[b].dcost -= min;
deba@2514:       }
deba@2514:       _data[b].dmin = min;
deba@2514:       if (c != -1) {
deba@2514: 	_data[c].dmin = cc;
deba@2514: 	if (_tolerance.less(cc, _max_value)) {
deba@2514: 	  _data[c].dmin -= min2;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (d != -1) {
deba@2514: 	_data[d].dmin = dd - min;
deba@2514:       }
deba@2514:       if (e != -1) {
deba@2514: 	_data[e].dmin = ee - min2;
deba@2514:       }
deba@2514:         
deba@2514:       int w = _data[v].parent;
deba@2514:       _data[v].successor = _data[w].successor;
deba@2514:       _data[w].successor = -1;
deba@2514:       _data[v].parent = _data[w].parent;
deba@2514:       _data[w].parent = v;
deba@2514:       _data[w].left = _data[v].right;
deba@2514:       _data[v].right = w;
deba@2514:       if (_data[v].parent != -1){
deba@2514: 	if (_data[_data[v].parent].right == w) {
deba@2514: 	  _data[_data[v].parent].right = v;
deba@2514: 	} else {
deba@2514: 	  _data[_data[v].parent].left = v;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (_data[w].left != -1){
deba@2514: 	_data[_data[w].left].parent = w;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514: 
deba@2514:     void zag(int v) {
deba@2514: 
deba@2514:       Value min = _data[_data[v].parent].dmin;
deba@2514: 
deba@2514:       int a = _data[v].parent;
deba@2514:       Value aa = _data[a].dcost;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	aa += min;
deba@2514:       }
deba@2514:         
deba@2514:       int b = v;
deba@2514:       Value ab = min + _data[b].dmin;
deba@2514:       Value bb = _data[b].dcost;
deba@2514:       if (_tolerance.less(bb, _max_value)) {
deba@2514: 	bb += ab;
deba@2514:       }
deba@2514: 
deba@2514:       int c = -1;
deba@2514:       Value cc = _max_value;
deba@2514:       if (_data[a].left != -1){
deba@2514: 	c = _data[a].left;
deba@2514: 	cc = min + _data[c].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       int d = -1;
deba@2514:       Value dd = _max_value;
deba@2514:       if (_data[v].right!=-1) {
deba@2514: 	d = _data[v].right;
deba@2514: 	dd = _data[d].dmin;
deba@2514: 	if (_tolerance.less(dd, _max_value)) {
deba@2514: 	  dd += ab;
deba@2514: 	}
deba@2514:       }
deba@2514: 
deba@2514:       int e = -1;
deba@2514:       Value ee = _max_value;
deba@2514:       if (_data[v].left != -1){
deba@2514: 	e = _data[v].left;
deba@2514: 	ee = ab + _data[e].dmin;
deba@2514:       }
deba@2514: 
deba@2514:       Value min2;
deba@2514:       if (_tolerance.less(0, _data[b].dmin) || 
deba@2514: 	  (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
deba@2514: 	min2 = min;
deba@2514:       } else {
deba@2514: 	if (_tolerance.less(aa, cc)) {
deba@2514: 	  if (_tolerance.less(aa, ee)) {
deba@2514: 	    min2 = aa;
deba@2514: 	  } else {
deba@2514: 	    min2 = ee;
deba@2514: 	  }
deba@2514: 	} else if (_tolerance.less(cc, ee)) {
deba@2514: 	  min2 = cc;
deba@2514: 	} else {
deba@2514: 	  min2 = ee;
deba@2514: 	}
deba@2514:       }
deba@2514:       _data[a].dcost = aa;
deba@2514:       if (_tolerance.less(aa, _max_value)) { 
deba@2514: 	_data[a].dcost -= min2;
deba@2514:       }
deba@2514:       _data[a].dmin = min2;
deba@2514:       if (_tolerance.less(min2, _max_value)) {
deba@2514: 	_data[a].dmin -= min;
deba@2514:       }
deba@2514:       _data[b].dcost = bb;
deba@2514:       if (_tolerance.less(bb, _max_value)) { 
deba@2514: 	_data[b].dcost -= min;
deba@2514:       }
deba@2514:       _data[b].dmin = min;
deba@2514:       if (c != -1) {
deba@2514: 	_data[c].dmin = cc - min2;
deba@2514:       }
deba@2514:       if (d != -1) {
deba@2514: 	_data[d].dmin = dd;
deba@2514: 	if (_tolerance.less(dd, _max_value)) {
deba@2514: 	  _data[d].dmin -= min;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (e != -1) {
deba@2514: 	_data[e].dmin = ee - min2;
deba@2514:       }
deba@2514:         
deba@2514:       int w = _data[v].parent;
deba@2514:       _data[v].successor = _data[w].successor;
deba@2514:       _data[w].successor = -1;
deba@2514:       _data[v].parent = _data[w].parent;
deba@2514:       _data[w].parent = v;
deba@2514:       _data[w].right = _data[v].left;
deba@2514:       _data[v].left = w;
deba@2514:       if (_data[v].parent != -1){
deba@2514: 	if (_data[_data[v].parent].left == w) {
deba@2514: 	  _data[_data[v].parent].left = v;
deba@2514: 	} else {
deba@2514: 	  _data[_data[v].parent].right = v;
deba@2514: 	}
deba@2514:       }
deba@2514:       if (_data[w].right != -1){
deba@2514: 	_data[_data[w].right].parent = w;
deba@2514:       }
deba@2514:     }
deba@2514: 
deba@2514:   private:
deba@2514: 
deba@2514:     class ItemData {
deba@2514:     public:
deba@2514:       Item id;
deba@2514:       int successor;
deba@2514:       int parent;
deba@2514:       int left;
deba@2514:       int right;
deba@2514:       Value dmin;
deba@2514:       Value dcost;
deba@2514:         
deba@2514:     public:
deba@2514:       ItemData(const Item &item)
deba@2514: 	: id(item), successor(), parent(-1), 
deba@2514: 	  left(-1), right(-1), dmin(0), dcost(0) {}
deba@2514:     };
deba@2514:      
deba@2514:   };
deba@2514: 
deba@2514: }
deba@2514: 
deba@2514: #endif