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 * Last modified: 00012 * $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $ 00013 * $Revision: 11551 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { namespace Scheduling { 00041 00042 forceinline int 00043 plus(int x, int y) { 00044 assert(y != -Int::Limits::infinity); 00045 return (x == -Int::Limits::infinity) ? x : x+y; 00046 } 00047 00048 forceinline double 00049 plus(double x, double y) { 00050 assert(y != -Int::Limits::double_infinity); 00051 return (x == -Int::Limits::double_infinity) ? x : x+y; 00052 } 00053 00054 forceinline double 00055 div(double x, double y) { 00056 assert(y != -Int::Limits::double_infinity); 00057 return (x == -Int::Limits::double_infinity) ? x : x / y; 00058 } 00059 00060 template<class TaskView, class Node> 00061 forceinline int 00062 TaskTree<TaskView,Node>::n_inner(void) const { 00063 return tasks.size()-1; 00064 } 00065 template<class TaskView, class Node> 00066 forceinline int 00067 TaskTree<TaskView,Node>::n_nodes(void) const { 00068 return 2*tasks.size() - 1; 00069 } 00070 00071 template<class TaskView, class Node> 00072 forceinline bool 00073 TaskTree<TaskView,Node>::n_root(int i) { 00074 return i == 0; 00075 } 00076 template<class TaskView, class Node> 00077 forceinline bool 00078 TaskTree<TaskView,Node>::n_leaf(int i) const { 00079 return i >= n_inner(); 00080 } 00081 template<class TaskView, class Node> 00082 forceinline int 00083 TaskTree<TaskView,Node>::n_left(int i) { 00084 return 2*(i+1) - 1; 00085 } 00086 template<class TaskView, class Node> 00087 forceinline bool 00088 TaskTree<TaskView,Node>::left(int i) { 00089 assert(!n_root(i)); 00090 // A left node has an odd number 00091 return (i & 1) != 0; 00092 } 00093 template<class TaskView, class Node> 00094 forceinline int 00095 TaskTree<TaskView,Node>::n_right(int i) { 00096 return 2*(i+1); 00097 } 00098 template<class TaskView, class Node> 00099 forceinline bool 00100 TaskTree<TaskView,Node>::right(int i) { 00101 assert(!n_root(i)); 00102 // A left node has an even number 00103 return (i & 1) == 0; 00104 } 00105 template<class TaskView, class Node> 00106 forceinline int 00107 TaskTree<TaskView,Node>::n_parent(int i) { 00108 return (i+1)/2 - 1; 00109 } 00110 00111 template<class TaskView, class Node> 00112 forceinline Node& 00113 TaskTree<TaskView,Node>::leaf(int i) { 00114 return node[_leaf[i]]; 00115 } 00116 00117 template<class TaskView, class Node> 00118 forceinline const Node& 00119 TaskTree<TaskView,Node>::root(void) const { 00120 return node[0]; 00121 } 00122 00123 template<class TaskView, class Node> 00124 forceinline void 00125 TaskTree<TaskView,Node>::init(void) { 00126 for (int i=n_inner(); i--; ) 00127 node[i].init(node[n_left(i)],node[n_right(i)]); 00128 } 00129 00130 template<class TaskView, class Node> 00131 forceinline void 00132 TaskTree<TaskView,Node>::update(void) { 00133 for (int i=n_inner(); i--; ) 00134 node[i].update(node[n_left(i)],node[n_right(i)]); 00135 } 00136 00137 template<class TaskView, class Node> 00138 forceinline void 00139 TaskTree<TaskView,Node>::update(int i, bool l) { 00140 if (l) 00141 i = _leaf[i]; 00142 assert(!n_root(i)); 00143 do { 00144 i = n_parent(i); 00145 node[i].update(node[n_left(i)],node[n_right(i)]); 00146 } while (!n_root(i)); 00147 } 00148 00149 template<class TaskView, class Node> 00150 forceinline 00151 TaskTree<TaskView,Node>::TaskTree(Region& r, 00152 const TaskViewArray<TaskView>& t) 00153 : tasks(t), 00154 node(r.alloc<Node>(n_nodes())), 00155 _leaf(r.alloc<int>(tasks.size())) { 00156 // Compute a sorting map to order by non decreasing est 00157 int* map = r.alloc<int>(tasks.size()); 00158 sort<TaskView,STO_EST,true>(map, tasks); 00159 // Compute inverse of sorting map 00160 for (int i=tasks.size(); i--; ) 00161 _leaf[map[i]] = i; 00162 r.free<int>(map,tasks.size()); 00163 // Compute index of first leaf in tree: the next larger power of two 00164 int fst = 1; 00165 while (fst < tasks.size()) 00166 fst <<= 1; 00167 fst--; 00168 // Remap task indices to leaf indices 00169 for (int i=tasks.size(); i--; ) 00170 if (_leaf[i] + fst >= n_nodes()) 00171 _leaf[i] += fst - tasks.size(); 00172 else 00173 _leaf[i] += fst; 00174 } 00175 00176 template<class TaskView, class Node> template<class Node2> 00177 forceinline 00178 TaskTree<TaskView,Node>::TaskTree(Region& r, 00179 const TaskTree<TaskView,Node2>& t) 00180 : tasks(t.tasks), 00181 node(r.alloc<Node>(n_nodes())), 00182 _leaf(r.alloc<int>(tasks.size())) { 00183 for (int i=tasks.size(); i--; ) 00184 _leaf[i] = t._leaf[i]; 00185 } 00186 00187 }} 00188 00189 // STATISTICS: scheduling-prop