Generated on Mon Nov 30 23:53:34 2009 for Gecode by doxygen 1.6.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: 2009-10-05 14:07:04 +0200 (Mon, 05 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9815 $
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 
00040 namespace Gecode { namespace Scheduling { namespace Unary {
00041 
00042   /*
00043    * Omega tree
00044    */
00045 
00046   forceinline void
00047   OmegaNode::init(const OmegaNode&, const OmegaNode&) {
00048     p = 0; ect = -Int::Limits::infinity;
00049   }
00050 
00051   forceinline void
00052   OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
00053     p = l.p + r.p; 
00054     ect = std::max(plus(l.ect,r.p), r.ect);
00055   }
00056 
00057   template<class TaskView>
00058   OmegaTree<TaskView>::OmegaTree(Region& r, const TaskViewArray<TaskView>& t)
00059     : TaskTree<TaskView,OmegaNode>(r,t) {
00060     for (int i=tasks.size(); i--; ) {
00061       leaf(i).p = 0; leaf(i).ect = -Int::Limits::infinity;
00062     }
00063     init();
00064   }
00065 
00066   template<class TaskView>
00067   forceinline void 
00068   OmegaTree<TaskView>::insert(int i) {
00069     leaf(i).p = tasks[i].p(); leaf(i).ect = tasks[i].ect();
00070     update(i);
00071   }
00072 
00073   template<class TaskView>
00074   forceinline void
00075   OmegaTree<TaskView>::remove(int i) {
00076     leaf(i).p = 0; leaf(i).ect = -Int::Limits::infinity;
00077     update(i);
00078   }
00079 
00080   template<class TaskView>
00081   forceinline int 
00082   OmegaTree<TaskView>::ect(void) const {
00083     return root().ect;
00084   }
00085   
00086   template<class TaskView>
00087   forceinline int 
00088   OmegaTree<TaskView>::ect(int i) const {
00089     // Check whether task i is in?
00090     OmegaTree<TaskView>& o = const_cast<OmegaTree<TaskView>&>(*this);
00091     if (o.leaf(i).p > 0) {
00092       o.remove(i);
00093       int ect = o.root().ect;
00094       o.insert(i);
00095       return ect;
00096     } else {
00097       return root().ect;
00098     }
00099   }
00100   
00101 
00102 
00103   /*
00104    * Ome lambda tree
00105    */
00106 
00107   forceinline void
00108   OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00109     OmegaNode::init(l,r);
00110     lp = p; lect = ect; res = undef;
00111   }
00112 
00113   forceinline void
00114   OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
00115     OmegaNode::update(l,r);
00116     lp = std::max(l.lp + r.p, l.p + r.lp);
00117     if ((r.lect >= plus(l.ect,r.lp)) && (r.lect >= plus(l.lect,r.p))) {
00118       lect = r.lect; res = r.res;
00119     } else if (plus(l.ect,r.lp) >= plus(l.lect,r.p)) {
00120       assert(plus(l.ect,r.lp) > r.lect);
00121       lect = plus(l.ect,r.lp); res = r.res;
00122     } else {
00123       assert((plus(l.lect,r.p) > r.lect) && 
00124              (plus(l.lect,r.p) > plus(l.ect,r.lp)));
00125       lect = plus(l.lect,r.p); res = l.res;
00126     }
00127   }
00128 
00129 
00130   template<class TaskView>
00131   OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r, 
00132                                              const TaskViewArray<TaskView>& t,
00133                                              bool inc)
00134     : TaskTree<TaskView,OmegaLambdaNode>(r,t) {
00135     if (inc) {
00136       // Enter all tasks into tree (omega = all tasks, lambda = empty)
00137       for (int i=tasks.size(); i--; ) {
00138         leaf(i).p = leaf(i).lp = tasks[i].p();
00139         leaf(i).ect = leaf(i).lect = tasks[i].ect();
00140         leaf(i).res = OmegaLambdaNode::undef;
00141       }
00142     } else {
00143       // Enter no tasks into tree (omega = empty, lambda = empty)
00144       for (int i=tasks.size(); i--; ) {
00145         leaf(i).p = leaf(i).lp = 0;
00146         leaf(i).ect = leaf(i).lect = -Int::Limits::infinity;
00147         leaf(i).res = OmegaLambdaNode::undef;
00148       }
00149      }
00150     init();
00151   }
00152 
00153   template<class TaskView>
00154   forceinline void 
00155   OmegaLambdaTree<TaskView>::shift(int i) {
00156     // That means that i is in omega
00157     assert(leaf(i).p > 0);
00158     leaf(i).p = 0;
00159     leaf(i).ect = -Int::Limits::infinity;
00160     leaf(i).res = i;
00161     update(i);
00162   }
00163 
00164   template<class TaskView>
00165   forceinline void
00166   OmegaLambdaTree<TaskView>::oinsert(int i) {
00167     leaf(i).p = tasks[i].p(); 
00168     leaf(i).ect = tasks[i].ect();
00169     update(i);
00170   }
00171 
00172   template<class TaskView>
00173   forceinline void
00174   OmegaLambdaTree<TaskView>::linsert(int i) {
00175     leaf(i).lp = tasks[i].p(); 
00176     leaf(i).lect = tasks[i].ect();
00177     leaf(i).res = i;
00178     update(i);
00179   }
00180 
00181   template<class TaskView>
00182   forceinline void
00183   OmegaLambdaTree<TaskView>::lremove(int i) {
00184     leaf(i).lp = 0; 
00185     leaf(i).lect = -Int::Limits::infinity;
00186     leaf(i).res = OmegaLambdaNode::undef;
00187     update(i);
00188   }
00189 
00190   template<class TaskView>
00191   forceinline bool
00192   OmegaLambdaTree<TaskView>::lempty(void) const {
00193     return root().res < 0;
00194   }
00195   
00196   template<class TaskView>
00197   forceinline int 
00198   OmegaLambdaTree<TaskView>::responsible(void) const {
00199     return root().res;
00200   }
00201   
00202   template<class TaskView>
00203   forceinline int 
00204   OmegaLambdaTree<TaskView>::ect(void) const {
00205     return root().ect;
00206   }
00207   
00208   template<class TaskView>
00209   forceinline int 
00210   OmegaLambdaTree<TaskView>::lect(void) const {
00211     return root().lect;
00212   }
00213   
00214 }}}
00215 
00216 // STATISTICS: scheduling-prop