1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dynamic_tree.h Sat Nov 17 20:58:11 2007 +0000
1.3 @@ -0,0 +1,1076 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +#ifndef LEMON_DYNAMIC_TREE_H
1.22 +#define LEMON_DYNAMIC_TREE_H
1.23 +
1.24 +/// \ingroup auxdata
1.25 +/// \file
1.26 +/// \brief The dynamic tree data structure of Sleator and Tarjan.
1.27 +///
1.28 +
1.29 +#include <vector>
1.30 +#include <limits>
1.31 +#include <lemon/tolerance.h>
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 + /// \ingroup auxdata
1.36 + ///
1.37 + /// \brief The dynamic tree data structure of Sleator and Tarjan.
1.38 + ///
1.39 + /// This class provides an implementation of the dynamic tree data
1.40 + /// structure for maintaining a set of node-disjoint rooted
1.41 + /// trees. Each item has an associated value, and the item with
1.42 + /// minimum value can be find in \f$O(\log(n)\f$ on the path from a
1.43 + /// node to the its root, and the items on such path can be
1.44 + /// increased or decreased globally with a certain value in the same
1.45 + /// running time. We regard a tree edge as directed toward the root,
1.46 + /// that is from child to parent. Its structure can be modified by
1.47 + /// two basic operations: \e link(v,w) adds an edge between a root v
1.48 + /// and a node w in a different component; \e cut(v) removes the
1.49 + /// edge between v and its parent.
1.50 + ///
1.51 + /// \param _Value The value type of the items.
1.52 + /// \param _ItemIntMap Converts item type of node to integer.
1.53 + /// \param _Tolerance The tolerance class to handle computation
1.54 + /// problems.
1.55 + /// \param _enableSize If true then the data structre manatain the
1.56 + /// size of each tree. The feature is used in \ref GoldbergTarjan
1.57 + /// algorithm. The default value is true.
1.58 + ///
1.59 + /// \author Hamori Tamas
1.60 +#ifdef DOXYGEN
1.61 + template <typename _Value, typename _ItemIntMap,
1.62 + typename _Tolerance, bool _enableSize>
1.63 +#else
1.64 + template <typename _Value, typename _ItemIntMap,
1.65 + typename _Tolerance = lemon::Tolerance<_Value>,
1.66 + bool _enableSize = true>
1.67 +#endif
1.68 + class DynamicTree {
1.69 + public:
1.70 + /// \brief The integer map on the items.
1.71 + typedef _ItemIntMap ItemIntMap;
1.72 + /// \brief The item type of nodes.
1.73 + typedef typename ItemIntMap::Key Item;
1.74 + /// \brief The value type of the algorithms.
1.75 + typedef _Value Value;
1.76 + /// \brief The tolerance used by the algorithm.
1.77 + typedef _Tolerance Tolerance;
1.78 +
1.79 + private:
1.80 +
1.81 + class ItemData;
1.82 +
1.83 + std::vector<ItemData> _data;
1.84 + ItemIntMap &_iim;
1.85 + Value _max_value;
1.86 + Tolerance _tolerance;
1.87 +
1.88 + public:
1.89 + /// \brief The constructor of the class.
1.90 + ///
1.91 + /// \param iim The integer map on the items.
1.92 + /// \param tolerance Tolerance class.
1.93 + DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
1.94 + : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
1.95 + _tolerance(tolerance) {}
1.96 +
1.97 + ~DynamicTree() {}
1.98 +
1.99 + /// \brief Clears the data structure
1.100 + ///
1.101 + /// Clears the data structure
1.102 + void clear() {
1.103 + _data.clear();
1.104 + }
1.105 +
1.106 + /// \brief Sets the tolerance used by algorithm.
1.107 + ///
1.108 + /// Sets the tolerance used by algorithm.
1.109 + void tolerance(const Tolerance& tolerance) const {
1.110 + _tolerance = tolerance;
1.111 + return *this;
1.112 + }
1.113 +
1.114 + /// \brief Returns the tolerance used by algorithm.
1.115 + ///
1.116 + /// Returns the tolerance used by algorithm.
1.117 + const Tolerance& tolerance() const {
1.118 + return tolerance;
1.119 + }
1.120 +
1.121 + /// \brief Create a new tree containing a single node with cost zero.
1.122 + void makeTree(const Item &item) {
1.123 + _data[makePath(item)].successor = -1;
1.124 + }
1.125 +
1.126 + /// \brief Return the root of the tree containing node with itemtype
1.127 + /// \e item.
1.128 + Item findRoot(const Item &item) {
1.129 + return _data[findTail(expose(_iim[item]))].id;
1.130 + }
1.131 +
1.132 + /// \brief Return the the value of nodes in the tree containing
1.133 + /// node with itemtype \e item.
1.134 + int findSize(const Item &item) {
1.135 + return _data[expose(_iim[item])].size;
1.136 + }
1.137 +
1.138 + /// \brief Return the minimum cost containing node.
1.139 + ///
1.140 + /// Return into \e d the minimum cost on the tree path from \e item
1.141 + /// to findRoot(item). Return the last item (closest to its root)
1.142 + /// on this path of the minimum cost.
1.143 + Item findCost(const Item &item, Value& d){
1.144 + return _data[findPathCost(expose(_iim[item]),d)].id;
1.145 + }
1.146 +
1.147 + /// \brief Add \e x value to the cost of every node on the path from
1.148 + /// \e item to findRoot(item).
1.149 + void addCost(const Item &item, Value x){
1.150 + addPathCost(expose(_iim[item]), x);
1.151 + }
1.152 +
1.153 + /// \brief Combine the trees containing nodes \e item1 and \e item2
1.154 + /// by adding an edge from \e item1 \e item2.
1.155 + ///
1.156 + /// This operation assumes that \e item1 is root and \e item2 is in
1.157 + /// a different tree.
1.158 + void link(const Item &item1, const Item &item2){
1.159 + int v = _iim[item1];
1.160 + int w = _iim[item2];
1.161 + int p = expose(w);
1.162 + join(-1, expose(v), p);
1.163 + _data[v].successor = -1;
1.164 + _data[v].size += _data[p].size;
1.165 +
1.166 + }
1.167 +
1.168 + /// \brief Divide the tree containing node \e item into two trees by
1.169 + /// deleting the edge out of \e item.
1.170 + ///
1.171 + /// This operation assumes that \e item is not a tree root.
1.172 + void cut(const Item &item) {
1.173 + int v = _iim[item];
1.174 + int p, q;
1.175 + expose(v);
1.176 + split(p, v, q);
1.177 + if (p != -1) {
1.178 + _data[p].successor = v;
1.179 + }
1.180 + _data[v].size -= _data[q].size;
1.181 + if (q != -1) {
1.182 + _data[q].successor = _data[v].successor;
1.183 + }
1.184 + _data[v].successor = -1;
1.185 + }
1.186 +
1.187 + ///\brief
1.188 + Item parent(const Item &item){
1.189 + return _data[_iim[item].p].id;
1.190 + }
1.191 +
1.192 + ///\brief Return the upper bound of the costs.
1.193 + Value maxValue() const {
1.194 + return _max_value;
1.195 + }
1.196 +
1.197 + private:
1.198 +
1.199 + int makePath(const Item &item) {
1.200 + _iim.set(item, _data.size());
1.201 + ItemData v(item);
1.202 + _data.push_back(v);
1.203 + return _iim[item];
1.204 + }
1.205 +
1.206 + int findPath(int v){
1.207 + splay(v);
1.208 + return v;
1.209 + }
1.210 +
1.211 + int findPathCost(int p, Value &d){
1.212 + while ((_data[p].right != -1 &&
1.213 + !_tolerance.less(0, _data[_data[p].right].dmin)) ||
1.214 + (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
1.215 + if (_data[p].right != -1 &&
1.216 + !_tolerance.less(0, _data[_data[p].right].dmin)) {
1.217 + p = _data[p].right;
1.218 + } else if (_data[p].left != -1 &&
1.219 + !_tolerance.less(0, _data[_data[p].left].dmin)){
1.220 + p = _data[p].left;
1.221 + }
1.222 + }
1.223 + splay(p);
1.224 + d = _data[p].dmin;
1.225 + return p;
1.226 + }
1.227 +
1.228 + int findTail(int p){
1.229 + while (_data[p].right != -1) {
1.230 + p = _data[p].right;
1.231 + }
1.232 + splay(p);
1.233 + return p;
1.234 + }
1.235 +
1.236 + void addPathCost(int p, Value x){
1.237 + if (!_tolerance.less(x, _max_value)) {
1.238 + _data[p].dmin = x;_data[p].dcost = x;
1.239 + } else if (!_tolerance.less(-x, _max_value)) {
1.240 + _data[p].dmin = 0;
1.241 + _data[p].dcost = 0;
1.242 + } else {
1.243 + _data[p].dmin += x;
1.244 + }
1.245 + }
1.246 +
1.247 + void join(int p, int v, int q) {
1.248 + Value min = _max_value;
1.249 + Value pmin = _max_value;
1.250 + Value vmin = _data[v].dmin;
1.251 + Value qmin = _max_value;
1.252 + if (p != -1){
1.253 + pmin = _data[p].dmin;
1.254 + }
1.255 + if (q != -1){
1.256 + qmin = _data[q].dmin;
1.257 + }
1.258 +
1.259 + if (_tolerance.less(vmin, qmin)) {
1.260 + if (_tolerance.less(vmin,pmin)) {
1.261 + min = vmin;
1.262 + } else {
1.263 + min = pmin;
1.264 + }
1.265 + } else if (_tolerance.less(qmin,pmin)) {
1.266 + min = qmin;
1.267 + } else {
1.268 + min = pmin;
1.269 + }
1.270 +
1.271 + if (p != -1){
1.272 + _data[p].parent = v;
1.273 + _data[p].dmin -= min;
1.274 + }
1.275 + if (q!=-1){
1.276 + _data[q].parent = v;
1.277 + if (_tolerance.less(_data[q].dmin,_max_value)) {
1.278 + _data[q].dmin -= min;
1.279 + }
1.280 + }
1.281 + _data[v].left = p;
1.282 + _data[v].right = q;
1.283 + if (_tolerance.less(min,_max_value)) {
1.284 + _data[v].dcost = _data[v].dmin - min;
1.285 + }
1.286 + _data[v].dmin = min;
1.287 + }
1.288 +
1.289 + void split(int &p, int v, int &q){
1.290 + splay(v);
1.291 + p = -1;
1.292 + if (_data[v].left != -1){
1.293 + p = _data[v].left;
1.294 + _data[p].dmin += _data[v].dmin;
1.295 + _data[p].parent = -1;
1.296 + _data[v].left = -1;
1.297 + }
1.298 + q = -1;
1.299 + if (_data[v].right != -1) {
1.300 + q=_data[v].right;
1.301 + if (_tolerance.less(_data[q].dmin, _max_value)) {
1.302 + _data[q].dmin += _data[v].dmin;
1.303 + }
1.304 + _data[q].parent = -1;
1.305 + _data[v].right = -1;
1.306 + }
1.307 + if (_tolerance.less(_data[v].dcost, _max_value)) {
1.308 + _data[v].dmin += _data[v].dcost;
1.309 + _data[v].dcost = 0;
1.310 + } else {
1.311 + _data[v].dmin = _data[v].dcost;
1.312 + }
1.313 + }
1.314 +
1.315 + int expose(int v) {
1.316 + int p, q, r, w;
1.317 + p = -1;
1.318 + while (v != -1) {
1.319 + w = _data[findPath(v)].successor;
1.320 + split(q, v, r);
1.321 + if (q != -1) {
1.322 + _data[q].successor = v;
1.323 + }
1.324 + join(p, v, r);
1.325 + p = v;
1.326 + v = w;
1.327 + }
1.328 + _data[p].successor = -1;
1.329 + return p;
1.330 + }
1.331 +
1.332 + void splay(int v) {
1.333 + while (_data[v].parent != -1) {
1.334 + if (v == _data[_data[v].parent].left) {
1.335 + if (_data[_data[v].parent].parent == -1) {
1.336 + zig(v);
1.337 + } else {
1.338 + if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
1.339 + zig(_data[v].parent);
1.340 + zig(v);
1.341 + } else {
1.342 + zig(v);
1.343 + zag(v);
1.344 + }
1.345 + }
1.346 + } else {
1.347 + if (_data[_data[v].parent].parent == -1) {
1.348 + zag(v);
1.349 + } else {
1.350 + if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
1.351 + zag(v);
1.352 + zig(v);
1.353 + } else {
1.354 + zag(_data[v].parent);
1.355 + zag(v);
1.356 + }
1.357 + }
1.358 + }
1.359 + }
1.360 + }
1.361 +
1.362 +
1.363 + void zig(int v) {
1.364 + Value min = _data[_data[v].parent].dmin;
1.365 + int a = _data[v].parent;
1.366 +
1.367 + Value aa = _data[a].dcost;
1.368 + if (_tolerance.less(aa, _max_value)) {
1.369 + aa+= min;
1.370 + }
1.371 +
1.372 +
1.373 + int b = v;
1.374 + Value ab = min + _data[b].dmin;
1.375 + Value bb = _data[b].dcost;
1.376 + if (_tolerance.less(bb, _max_value)) {
1.377 + bb+= ab;
1.378 + }
1.379 +
1.380 + int c = -1;
1.381 + Value cc = _max_value;
1.382 + if (_data[a].right != -1) {
1.383 + c = _data[a].right;
1.384 + cc = _data[c].dmin;
1.385 + if (_tolerance.less(cc, _max_value)) {
1.386 + cc+=min;
1.387 + }
1.388 + }
1.389 +
1.390 + int d = -1;
1.391 + Value dd = _max_value;
1.392 + if (_data[v].left != -1){
1.393 + d = _data[v].left;
1.394 + dd = ab + _data[d].dmin;
1.395 + }
1.396 +
1.397 + int e = -1;
1.398 + Value ee = _max_value;
1.399 + if (_data[v].right != -1) {
1.400 + e = _data[v].right;
1.401 + ee = ab + _data[e].dmin;
1.402 + }
1.403 +
1.404 + Value min2;
1.405 + if (_tolerance.less(0, _data[b].dmin) ||
1.406 + (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
1.407 + min2 = min;
1.408 + } else {
1.409 + if (_tolerance.less(aa, cc)) {
1.410 + if (_tolerance.less(aa, ee)) {
1.411 + min2 = aa;
1.412 + } else {
1.413 + min2 = ee;
1.414 + }
1.415 + } else if (_tolerance.less(cc, ee)) {
1.416 + min2 = cc;
1.417 + } else {
1.418 + min2 = ee;
1.419 + }
1.420 + }
1.421 +
1.422 + _data[a].dcost = aa;
1.423 + if (_tolerance.less(aa, _max_value)) {
1.424 + _data[a].dcost -= min2;
1.425 + }
1.426 + _data[a].dmin = min2;
1.427 + if (_tolerance.less(min2,_max_value)) {
1.428 + _data[a].dmin -= min;
1.429 + }
1.430 + _data[a].size -= _data[b].size;
1.431 + _data[b].dcost = bb;
1.432 + if (_tolerance.less(bb, _max_value)) {
1.433 + _data[b].dcost -= min;
1.434 + }
1.435 + _data[b].dmin = min;
1.436 + _data[b].size += _data[a].size;
1.437 + if (c != -1) {
1.438 + _data[c].dmin = cc;
1.439 + if (_tolerance.less(cc, _max_value)) {
1.440 + _data[c].dmin -= min2;
1.441 + }
1.442 + }
1.443 + if (d != -1) {
1.444 + _data[d].dmin = dd - min;
1.445 + _data[a].size += _data[d].size;
1.446 + _data[b].size -= _data[d].size;
1.447 + }
1.448 + if (e != -1) {
1.449 + _data[e].dmin = ee - min2;
1.450 + }
1.451 +
1.452 + int w = _data[v].parent;
1.453 + _data[v].successor = _data[w].successor;
1.454 + _data[w].successor = -1;
1.455 + _data[v].parent = _data[w].parent;
1.456 + _data[w].parent = v;
1.457 + _data[w].left = _data[v].right;
1.458 + _data[v].right = w;
1.459 + if (_data[v].parent != -1){
1.460 + if (_data[_data[v].parent].right == w) {
1.461 + _data[_data[v].parent].right = v;
1.462 + } else {
1.463 + _data[_data[v].parent].left = v;
1.464 + }
1.465 + }
1.466 + if (_data[w].left != -1){
1.467 + _data[_data[w].left].parent = w;
1.468 + }
1.469 + }
1.470 +
1.471 +
1.472 + void zag(int v) {
1.473 +
1.474 + Value min = _data[_data[v].parent].dmin;
1.475 +
1.476 + int a = _data[v].parent;
1.477 + Value aa = _data[a].dcost;
1.478 + if (_tolerance.less(aa, _max_value)) {
1.479 + aa += min;
1.480 + }
1.481 +
1.482 + int b = v;
1.483 + Value ab = min + _data[b].dmin;
1.484 + Value bb = _data[b].dcost;
1.485 + if (_tolerance.less(bb, _max_value)) {
1.486 + bb += ab;
1.487 + }
1.488 +
1.489 + int c = -1;
1.490 + Value cc = _max_value;
1.491 + if (_data[a].left != -1){
1.492 + c = _data[a].left;
1.493 + cc = min + _data[c].dmin;
1.494 + }
1.495 +
1.496 + int d = -1;
1.497 + Value dd = _max_value;
1.498 + if (_data[v].right!=-1) {
1.499 + d = _data[v].right;
1.500 + dd = _data[d].dmin;
1.501 + if (_tolerance.less(dd, _max_value)) {
1.502 + dd += ab;
1.503 + }
1.504 + }
1.505 +
1.506 + int e = -1;
1.507 + Value ee = _max_value;
1.508 + if (_data[v].left != -1){
1.509 + e = _data[v].left;
1.510 + ee = ab + _data[e].dmin;
1.511 + }
1.512 +
1.513 + Value min2;
1.514 + if (_tolerance.less(0, _data[b].dmin) ||
1.515 + (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
1.516 + min2 = min;
1.517 + } else {
1.518 + if (_tolerance.less(aa, cc)) {
1.519 + if (_tolerance.less(aa, ee)) {
1.520 + min2 = aa;
1.521 + } else {
1.522 + min2 = ee;
1.523 + }
1.524 + } else if (_tolerance.less(cc, ee)) {
1.525 + min2 = cc;
1.526 + } else {
1.527 + min2 = ee;
1.528 + }
1.529 + }
1.530 + _data[a].dcost = aa;
1.531 + if (_tolerance.less(aa, _max_value)) {
1.532 + _data[a].dcost -= min2;
1.533 + }
1.534 + _data[a].dmin = min2;
1.535 + if (_tolerance.less(min2, _max_value)) {
1.536 + _data[a].dmin -= min;
1.537 + }
1.538 + _data[a].size -= _data[b].size;
1.539 + _data[b].dcost = bb;
1.540 + if (_tolerance.less(bb, _max_value)) {
1.541 + _data[b].dcost -= min;
1.542 + }
1.543 + _data[b].dmin = min;
1.544 + _data[b].size += _data[a].size;
1.545 + if (c != -1) {
1.546 + _data[c].dmin = cc - min2;
1.547 + }
1.548 + if (d != -1) {
1.549 + _data[d].dmin = dd;
1.550 + _data[a].size += _data[d].size;
1.551 + _data[b].size -= _data[d].size;
1.552 + if (_tolerance.less(dd, _max_value)) {
1.553 + _data[d].dmin -= min;
1.554 + }
1.555 + }
1.556 + if (e != -1) {
1.557 + _data[e].dmin = ee - min2;
1.558 + }
1.559 +
1.560 + int w = _data[v].parent;
1.561 + _data[v].successor = _data[w].successor;
1.562 + _data[w].successor = -1;
1.563 + _data[v].parent = _data[w].parent;
1.564 + _data[w].parent = v;
1.565 + _data[w].right = _data[v].left;
1.566 + _data[v].left = w;
1.567 + if (_data[v].parent != -1){
1.568 + if (_data[_data[v].parent].left == w) {
1.569 + _data[_data[v].parent].left = v;
1.570 + } else {
1.571 + _data[_data[v].parent].right = v;
1.572 + }
1.573 + }
1.574 + if (_data[w].right != -1){
1.575 + _data[_data[w].right].parent = w;
1.576 + }
1.577 + }
1.578 +
1.579 + private:
1.580 +
1.581 + class ItemData {
1.582 + public:
1.583 + Item id;
1.584 + int size;
1.585 + int successor;
1.586 + int parent;
1.587 + int left;
1.588 + int right;
1.589 + Value dmin;
1.590 + Value dcost;
1.591 +
1.592 + public:
1.593 + ItemData(const Item &item)
1.594 + : id(item), size(1), successor(), parent(-1),
1.595 + left(-1), right(-1), dmin(0), dcost(0) {}
1.596 + };
1.597 +
1.598 + };
1.599 +
1.600 + template <typename _Value, typename _ItemIntMap, typename _Tolerance>
1.601 + class DynamicTree<_Value, _ItemIntMap, _Tolerance, false> {
1.602 + public:
1.603 + typedef _ItemIntMap ItemIntMap;
1.604 + typedef typename ItemIntMap::Key Item;
1.605 + typedef _Value Value;
1.606 + typedef _Tolerance Tolerance;
1.607 +
1.608 + private:
1.609 +
1.610 + class ItemData;
1.611 +
1.612 + std::vector<ItemData> _data;
1.613 + ItemIntMap &_iim;
1.614 + Value _max_value;
1.615 + Tolerance _tolerance;
1.616 +
1.617 + public:
1.618 + DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
1.619 + : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
1.620 + _tolerance(tolerance) {}
1.621 +
1.622 + ~DynamicTree() {}
1.623 +
1.624 + void clear() {
1.625 + _data.clear();
1.626 + }
1.627 +
1.628 + void tolerance(const Tolerance& tolerance) const {
1.629 + _tolerance = tolerance;
1.630 + return *this;
1.631 + }
1.632 +
1.633 + const Tolerance& tolerance() const {
1.634 + return tolerance;
1.635 + }
1.636 +
1.637 + void makeTree(const Item &item) {
1.638 + _data[makePath(item)].successor = -1;
1.639 + }
1.640 +
1.641 + Item findRoot(const Item &item) {
1.642 + return _data[findTail(expose(_iim[item]))].id;
1.643 + }
1.644 +
1.645 + Item findCost(const Item &item, Value& d){
1.646 + return _data[findPathCost(expose(_iim[item]),d)].id;
1.647 + }
1.648 +
1.649 + void addCost(const Item &item, Value x){
1.650 + addPathCost(expose(_iim[item]), x);
1.651 + }
1.652 +
1.653 + void link(const Item &item1, const Item &item2){
1.654 + int v = _iim[item1];
1.655 + int w = _iim[item2];
1.656 + int p = expose(w);
1.657 + join(-1, expose(v), p);
1.658 + _data[v].successor = -1;
1.659 + }
1.660 +
1.661 + void cut(const Item &item) {
1.662 + int v = _iim[item];
1.663 + int p, q;
1.664 + expose(v);
1.665 + split(p, v, q);
1.666 + if (p != -1) {
1.667 + _data[p].successor = v;
1.668 + }
1.669 + if (q != -1) {
1.670 + _data[q].successor = _data[v].successor;
1.671 + }
1.672 + _data[v].successor = -1;
1.673 + }
1.674 +
1.675 + Item parent(const Item &item){
1.676 + return _data[_iim[item].p].id;
1.677 + }
1.678 +
1.679 + Value maxValue() const {
1.680 + return _max_value;
1.681 + }
1.682 +
1.683 + private:
1.684 +
1.685 + int makePath(const Item &item) {
1.686 + _iim.set(item, _data.size());
1.687 + ItemData v(item);
1.688 + _data.push_back(v);
1.689 + return _iim[item];
1.690 + }
1.691 +
1.692 + int findPath(int v){
1.693 + splay(v);
1.694 + return v;
1.695 + }
1.696 +
1.697 + int findPathCost(int p, Value &d){
1.698 + while ((_data[p].right != -1 &&
1.699 + !_tolerance.less(0, _data[_data[p].right].dmin)) ||
1.700 + (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
1.701 + if (_data[p].right != -1 &&
1.702 + !_tolerance.less(0, _data[_data[p].right].dmin)) {
1.703 + p = _data[p].right;
1.704 + } else if (_data[p].left != -1 &&
1.705 + !_tolerance.less(0, _data[_data[p].left].dmin)){
1.706 + p = _data[p].left;
1.707 + }
1.708 + }
1.709 + splay(p);
1.710 + d = _data[p].dmin;
1.711 + return p;
1.712 + }
1.713 +
1.714 + int findTail(int p){
1.715 + while (_data[p].right != -1) {
1.716 + p = _data[p].right;
1.717 + }
1.718 + splay(p);
1.719 + return p;
1.720 + }
1.721 +
1.722 + void addPathCost(int p, Value x){
1.723 + if (!_tolerance.less(x, _max_value)) {
1.724 + _data[p].dmin = x;_data[p].dcost = x;
1.725 + } else if (!_tolerance.less(-x, _max_value)) {
1.726 + _data[p].dmin = 0;
1.727 + _data[p].dcost = 0;
1.728 + } else {
1.729 + _data[p].dmin += x;
1.730 + }
1.731 + }
1.732 +
1.733 + void join(int p, int v, int q) {
1.734 + Value min = _max_value;
1.735 + Value pmin = _max_value;
1.736 + Value vmin = _data[v].dmin;
1.737 + Value qmin = _max_value;
1.738 + if (p != -1){
1.739 + pmin = _data[p].dmin;
1.740 + }
1.741 + if (q != -1){
1.742 + qmin = _data[q].dmin;
1.743 + }
1.744 +
1.745 + if (_tolerance.less(vmin, qmin)) {
1.746 + if (_tolerance.less(vmin,pmin)) {
1.747 + min = vmin;
1.748 + } else {
1.749 + min = pmin;
1.750 + }
1.751 + } else if (_tolerance.less(qmin,pmin)) {
1.752 + min = qmin;
1.753 + } else {
1.754 + min = pmin;
1.755 + }
1.756 +
1.757 + if (p != -1){
1.758 + _data[p].parent = v;
1.759 + _data[p].dmin -= min;
1.760 + }
1.761 + if (q!=-1){
1.762 + _data[q].parent = v;
1.763 + if (_tolerance.less(_data[q].dmin,_max_value)) {
1.764 + _data[q].dmin -= min;
1.765 + }
1.766 + }
1.767 + _data[v].left = p;
1.768 + _data[v].right = q;
1.769 + if (_tolerance.less(min,_max_value)) {
1.770 + _data[v].dcost = _data[v].dmin - min;
1.771 + }
1.772 + _data[v].dmin = min;
1.773 + }
1.774 +
1.775 + void split(int &p, int v, int &q){
1.776 + splay(v);
1.777 + p = -1;
1.778 + if (_data[v].left != -1){
1.779 + p = _data[v].left;
1.780 + _data[p].dmin += _data[v].dmin;
1.781 + _data[p].parent = -1;
1.782 + _data[v].left = -1;
1.783 + }
1.784 + q = -1;
1.785 + if (_data[v].right != -1) {
1.786 + q=_data[v].right;
1.787 + if (_tolerance.less(_data[q].dmin, _max_value)) {
1.788 + _data[q].dmin += _data[v].dmin;
1.789 + }
1.790 + _data[q].parent = -1;
1.791 + _data[v].right = -1;
1.792 + }
1.793 + if (_tolerance.less(_data[v].dcost, _max_value)) {
1.794 + _data[v].dmin += _data[v].dcost;
1.795 + _data[v].dcost = 0;
1.796 + } else {
1.797 + _data[v].dmin = _data[v].dcost;
1.798 + }
1.799 + }
1.800 +
1.801 + int expose(int v) {
1.802 + int p, q, r, w;
1.803 + p = -1;
1.804 + while (v != -1) {
1.805 + w = _data[findPath(v)].successor;
1.806 + split(q, v, r);
1.807 + if (q != -1) {
1.808 + _data[q].successor = v;
1.809 + }
1.810 + join(p, v, r);
1.811 + p = v;
1.812 + v = w;
1.813 + }
1.814 + _data[p].successor = -1;
1.815 + return p;
1.816 + }
1.817 +
1.818 + void splay(int v) {
1.819 + while (_data[v].parent != -1) {
1.820 + if (v == _data[_data[v].parent].left) {
1.821 + if (_data[_data[v].parent].parent == -1) {
1.822 + zig(v);
1.823 + } else {
1.824 + if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
1.825 + zig(_data[v].parent);
1.826 + zig(v);
1.827 + } else {
1.828 + zig(v);
1.829 + zag(v);
1.830 + }
1.831 + }
1.832 + } else {
1.833 + if (_data[_data[v].parent].parent == -1) {
1.834 + zag(v);
1.835 + } else {
1.836 + if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
1.837 + zag(v);
1.838 + zig(v);
1.839 + } else {
1.840 + zag(_data[v].parent);
1.841 + zag(v);
1.842 + }
1.843 + }
1.844 + }
1.845 + }
1.846 + }
1.847 +
1.848 +
1.849 + void zig(int v) {
1.850 + Value min = _data[_data[v].parent].dmin;
1.851 + int a = _data[v].parent;
1.852 +
1.853 + Value aa = _data[a].dcost;
1.854 + if (_tolerance.less(aa, _max_value)) {
1.855 + aa+= min;
1.856 + }
1.857 +
1.858 +
1.859 + int b = v;
1.860 + Value ab = min + _data[b].dmin;
1.861 + Value bb = _data[b].dcost;
1.862 + if (_tolerance.less(bb, _max_value)) {
1.863 + bb+= ab;
1.864 + }
1.865 +
1.866 + int c = -1;
1.867 + Value cc = _max_value;
1.868 + if (_data[a].right != -1) {
1.869 + c = _data[a].right;
1.870 + cc = _data[c].dmin;
1.871 + if (_tolerance.less(cc, _max_value)) {
1.872 + cc+=min;
1.873 + }
1.874 + }
1.875 +
1.876 + int d = -1;
1.877 + Value dd = _max_value;
1.878 + if (_data[v].left != -1){
1.879 + d = _data[v].left;
1.880 + dd = ab + _data[d].dmin;
1.881 + }
1.882 +
1.883 + int e = -1;
1.884 + Value ee = _max_value;
1.885 + if (_data[v].right != -1) {
1.886 + e = _data[v].right;
1.887 + ee = ab + _data[e].dmin;
1.888 + }
1.889 +
1.890 + Value min2;
1.891 + if (_tolerance.less(0, _data[b].dmin) ||
1.892 + (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
1.893 + min2 = min;
1.894 + } else {
1.895 + if (_tolerance.less(aa, cc)) {
1.896 + if (_tolerance.less(aa, ee)) {
1.897 + min2 = aa;
1.898 + } else {
1.899 + min2 = ee;
1.900 + }
1.901 + } else if (_tolerance.less(cc, ee)) {
1.902 + min2 = cc;
1.903 + } else {
1.904 + min2 = ee;
1.905 + }
1.906 + }
1.907 +
1.908 + _data[a].dcost = aa;
1.909 + if (_tolerance.less(aa, _max_value)) {
1.910 + _data[a].dcost -= min2;
1.911 + }
1.912 + _data[a].dmin = min2;
1.913 + if (_tolerance.less(min2,_max_value)) {
1.914 + _data[a].dmin -= min;
1.915 + }
1.916 + _data[b].dcost = bb;
1.917 + if (_tolerance.less(bb, _max_value)) {
1.918 + _data[b].dcost -= min;
1.919 + }
1.920 + _data[b].dmin = min;
1.921 + if (c != -1) {
1.922 + _data[c].dmin = cc;
1.923 + if (_tolerance.less(cc, _max_value)) {
1.924 + _data[c].dmin -= min2;
1.925 + }
1.926 + }
1.927 + if (d != -1) {
1.928 + _data[d].dmin = dd - min;
1.929 + }
1.930 + if (e != -1) {
1.931 + _data[e].dmin = ee - min2;
1.932 + }
1.933 +
1.934 + int w = _data[v].parent;
1.935 + _data[v].successor = _data[w].successor;
1.936 + _data[w].successor = -1;
1.937 + _data[v].parent = _data[w].parent;
1.938 + _data[w].parent = v;
1.939 + _data[w].left = _data[v].right;
1.940 + _data[v].right = w;
1.941 + if (_data[v].parent != -1){
1.942 + if (_data[_data[v].parent].right == w) {
1.943 + _data[_data[v].parent].right = v;
1.944 + } else {
1.945 + _data[_data[v].parent].left = v;
1.946 + }
1.947 + }
1.948 + if (_data[w].left != -1){
1.949 + _data[_data[w].left].parent = w;
1.950 + }
1.951 + }
1.952 +
1.953 +
1.954 + void zag(int v) {
1.955 +
1.956 + Value min = _data[_data[v].parent].dmin;
1.957 +
1.958 + int a = _data[v].parent;
1.959 + Value aa = _data[a].dcost;
1.960 + if (_tolerance.less(aa, _max_value)) {
1.961 + aa += min;
1.962 + }
1.963 +
1.964 + int b = v;
1.965 + Value ab = min + _data[b].dmin;
1.966 + Value bb = _data[b].dcost;
1.967 + if (_tolerance.less(bb, _max_value)) {
1.968 + bb += ab;
1.969 + }
1.970 +
1.971 + int c = -1;
1.972 + Value cc = _max_value;
1.973 + if (_data[a].left != -1){
1.974 + c = _data[a].left;
1.975 + cc = min + _data[c].dmin;
1.976 + }
1.977 +
1.978 + int d = -1;
1.979 + Value dd = _max_value;
1.980 + if (_data[v].right!=-1) {
1.981 + d = _data[v].right;
1.982 + dd = _data[d].dmin;
1.983 + if (_tolerance.less(dd, _max_value)) {
1.984 + dd += ab;
1.985 + }
1.986 + }
1.987 +
1.988 + int e = -1;
1.989 + Value ee = _max_value;
1.990 + if (_data[v].left != -1){
1.991 + e = _data[v].left;
1.992 + ee = ab + _data[e].dmin;
1.993 + }
1.994 +
1.995 + Value min2;
1.996 + if (_tolerance.less(0, _data[b].dmin) ||
1.997 + (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
1.998 + min2 = min;
1.999 + } else {
1.1000 + if (_tolerance.less(aa, cc)) {
1.1001 + if (_tolerance.less(aa, ee)) {
1.1002 + min2 = aa;
1.1003 + } else {
1.1004 + min2 = ee;
1.1005 + }
1.1006 + } else if (_tolerance.less(cc, ee)) {
1.1007 + min2 = cc;
1.1008 + } else {
1.1009 + min2 = ee;
1.1010 + }
1.1011 + }
1.1012 + _data[a].dcost = aa;
1.1013 + if (_tolerance.less(aa, _max_value)) {
1.1014 + _data[a].dcost -= min2;
1.1015 + }
1.1016 + _data[a].dmin = min2;
1.1017 + if (_tolerance.less(min2, _max_value)) {
1.1018 + _data[a].dmin -= min;
1.1019 + }
1.1020 + _data[b].dcost = bb;
1.1021 + if (_tolerance.less(bb, _max_value)) {
1.1022 + _data[b].dcost -= min;
1.1023 + }
1.1024 + _data[b].dmin = min;
1.1025 + if (c != -1) {
1.1026 + _data[c].dmin = cc - min2;
1.1027 + }
1.1028 + if (d != -1) {
1.1029 + _data[d].dmin = dd;
1.1030 + if (_tolerance.less(dd, _max_value)) {
1.1031 + _data[d].dmin -= min;
1.1032 + }
1.1033 + }
1.1034 + if (e != -1) {
1.1035 + _data[e].dmin = ee - min2;
1.1036 + }
1.1037 +
1.1038 + int w = _data[v].parent;
1.1039 + _data[v].successor = _data[w].successor;
1.1040 + _data[w].successor = -1;
1.1041 + _data[v].parent = _data[w].parent;
1.1042 + _data[w].parent = v;
1.1043 + _data[w].right = _data[v].left;
1.1044 + _data[v].left = w;
1.1045 + if (_data[v].parent != -1){
1.1046 + if (_data[_data[v].parent].left == w) {
1.1047 + _data[_data[v].parent].left = v;
1.1048 + } else {
1.1049 + _data[_data[v].parent].right = v;
1.1050 + }
1.1051 + }
1.1052 + if (_data[w].right != -1){
1.1053 + _data[_data[w].right].parent = w;
1.1054 + }
1.1055 + }
1.1056 +
1.1057 + private:
1.1058 +
1.1059 + class ItemData {
1.1060 + public:
1.1061 + Item id;
1.1062 + int successor;
1.1063 + int parent;
1.1064 + int left;
1.1065 + int right;
1.1066 + Value dmin;
1.1067 + Value dcost;
1.1068 +
1.1069 + public:
1.1070 + ItemData(const Item &item)
1.1071 + : id(item), successor(), parent(-1),
1.1072 + left(-1), right(-1), dmin(0), dcost(0) {}
1.1073 + };
1.1074 +
1.1075 + };
1.1076 +
1.1077 +}
1.1078 +
1.1079 +#endif