Generated on Tue Jul 27 2010 21:59:18 for Gecode by doxygen 1.7.1

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