Generated on Fri Oct 19 11:25:03 2018 for Gecode by doxygen 1.6.3

tree.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2009
00009  *     Guido Tack, 2010
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <algorithm>
00037 #include <cmath>
00038 
00039 namespace Gecode { namespace Int { namespace Cumulative {
00040 
00041   /*
00042    * Omega tree
00043    */
00044 
00045   forceinline void
00046   OmegaNode::init(const OmegaNode&, const OmegaNode&) {
00047     e = 0; env = -Limits::llinfinity;
00048   }
00049 
00050   forceinline void
00051   OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
00052     e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
00053   }
00054 
00055   template<class TaskView>
00056   OmegaTree<TaskView>::OmegaTree(Region& r, int c0,
00057                                  const TaskViewArray<TaskView>& t)
00058     : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
00059     for (int i=0; i<tasks.size(); i++) {
00060       leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
00061     }
00062     init();
00063   }
00064 
00065   template<class TaskView>
00066   forceinline void
00067   OmegaTree<TaskView>::insert(int i) {
00068     leaf(i).e = tasks[i].e();
00069     leaf(i).env =
00070       static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00071     update(i);
00072   }
00073 
00074   template<class TaskView>
00075   forceinline void
00076   OmegaTree<TaskView>::remove(int i) {
00077     leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
00078     update(i);
00079   }
00080 
00081   template<class TaskView>
00082   forceinline long long int
00083   OmegaTree<TaskView>::env(void) const {
00084     return root().env;
00085   }
00086 
00087   /*
00088    * Extended Omega tree
00089    */
00090 
00091   forceinline void
00092   ExtOmegaNode::init(const ExtOmegaNode& l, const ExtOmegaNode& r) {
00093     OmegaNode::init(l,r);
00094     cenv = -Limits::llinfinity;
00095   }
00096 
00097   forceinline void
00098   ExtOmegaNode::update(const ExtOmegaNode& l, const ExtOmegaNode& r) {
00099     OmegaNode::update(l,r);
00100     cenv = std::max(plus(l.cenv,r.e), r.cenv);
00101   }
00102 
00103   template<class TaskView> void
00104   ExtOmegaTree<TaskView>::init(int ci0) {
00105     ci = ci0;
00106     for (int i=0; i<tasks.size(); i++) {
00107       leaf(i).e = 0;
00108       leaf(i).env = leaf(i).cenv = -Limits::llinfinity;
00109     }
00110     init();
00111   }
00112 
00113   template<class TaskView> template<class Node>
00114   ExtOmegaTree<TaskView>::ExtOmegaTree(Region& r, int c0,
00115                                        const TaskTree<TaskView,Node>& t)
00116     : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
00117 
00118   template<class TaskView>
00119   forceinline long long int
00120   ExtOmegaTree<TaskView>::env(int i) {
00121     // Enter task i
00122     leaf(i).e = tasks[i].e();
00123     leaf(i).env =
00124       static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00125     leaf(i).cenv =
00126       static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e();
00127     TaskTree<TaskView,ExtOmegaNode>::update(i);
00128 
00129     // Perform computation of node for task with minest
00130     int met = 0;
00131     {
00132       long long int e = 0;
00133       while (!n_leaf(met)) {
00134         if (plus(node[n_right(met)].cenv,e) >
00135             static_cast<long long int>(c-ci) * tasks[i].lct()) {
00136           met = n_right(met);
00137         } else {
00138           e += node[n_right(met)].e; met = n_left(met);
00139         }
00140       }
00141     }
00142 
00143     /*
00144      * The following idea to compute the cut in one go is taken from:
00145      * Joseph Scott, Filtering Algorithms for Discrete Resources,
00146      * Master Thesis, Uppsala University, 2010 (in preparation).
00147      */
00148 
00149     // Now perform split from leaf met upwards
00150     long long int a_e = node[met].e;
00151     long long int a_env = node[met].env;
00152     long long int b_e = 0;
00153 
00154     while (!n_root(met)) {
00155       if (left(met)) {
00156         b_e += node[n_right(n_parent(met))].e;
00157       } else {
00158         a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
00159         a_e += node[n_left(n_parent(met))].e;
00160       }
00161       met = n_parent(met);
00162     }
00163 
00164     return plus(a_env,b_e);
00165   }
00166 
00167 
00168 
00169   /*
00170    * Omega lambda tree
00171    */
00172 
00173   forceinline void
00174   OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00175     OmegaNode::init(l,r);
00176     le = 0; lenv = -Limits::llinfinity;
00177     resLe = undef; resLenv = undef;
00178   }
00179 
00180   forceinline void
00181   OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00182     OmegaNode::update(l,r);
00183     if (l.le + r.e > l.e + r.le) {
00184       le = l.le + r.e;
00185       resLe = l.resLe;
00186     } else {
00187       le = l.e + r.le;
00188       resLe = r.resLe;
00189     }
00190     if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) {
00191       lenv = r.lenv; resLenv = r.resLenv;
00192     } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) {
00193       assert(plus(l.env,r.le) > r.lenv);
00194       lenv = plus(l.env,r.le); resLenv = r.resLe;
00195     } else {
00196       assert((plus(l.lenv,r.e) > r.lenv) &&
00197              (plus(l.lenv,r.e) > plus(l.env,r.le)));
00198       lenv = plus(l.lenv,r.e); resLenv = l.resLenv;
00199     }
00200   }
00201 
00202 
00203   template<class TaskView>
00204   OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, int c0,
00205                                              const TaskViewArray<TaskView>& t)
00206     : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) {
00207     // Enter all tasks into tree (omega = all tasks, lambda = empty)
00208     for (int i=0; i<tasks.size(); i++) {
00209       leaf(i).e = tasks[i].e();
00210       leaf(i).le = 0;
00211       leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
00212       leaf(i).lenv = -Limits::llinfinity;
00213       leaf(i).resLe = OmegaLambdaNode::undef;
00214       leaf(i).resLenv = OmegaLambdaNode::undef;
00215     }
00216     update();
00217   }
00218 
00219   template<class TaskView>
00220   forceinline void
00221   OmegaLambdaTree<TaskView>::shift(int i) {
00222     // i is in omega
00223     assert(leaf(i).env > -Limits::llinfinity);
00224     leaf(i).le = leaf(i).e;
00225     leaf(i).e = 0;
00226     leaf(i).lenv = leaf(i).env;
00227     leaf(i).env = -Limits::llinfinity;
00228     leaf(i).resLe = i;
00229     leaf(i).resLenv = i;
00230     update(i);
00231   }
00232 
00233   template<class TaskView>
00234   forceinline void
00235   OmegaLambdaTree<TaskView>::lremove(int i) {
00236     // i not in omega but in lambda
00237     assert(leaf(i).env == -Limits::llinfinity);
00238     assert(leaf(i).lenv > -Limits::llinfinity);
00239     leaf(i).le = 0;
00240     leaf(i).lenv = -Limits::llinfinity;
00241     leaf(i).resLe = OmegaLambdaNode::undef;
00242     leaf(i).resLenv = OmegaLambdaNode::undef;
00243     update(i);
00244   }
00245 
00246   template<class TaskView>
00247   forceinline bool
00248   OmegaLambdaTree<TaskView>::lempty(void) const {
00249     return root().resLenv < 0;
00250   }
00251 
00252   template<class TaskView>
00253   forceinline int
00254   OmegaLambdaTree<TaskView>::responsible(void) const {
00255     return root().resLenv;
00256   }
00257 
00258   template<class TaskView>
00259   forceinline long long int
00260   OmegaLambdaTree<TaskView>::env(void) const {
00261     return root().env;
00262   }
00263 
00264   template<class TaskView>
00265   forceinline long long int
00266   OmegaLambdaTree<TaskView>::lenv(void) const {
00267     return root().lenv;
00268   }
00269 
00270 }}}
00271 
00272 // STATISTICS: int-prop