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-03 13:11:11 +0200 (Thu, 03 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11013 $ 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 namespace Gecode { namespace Scheduling { 00039 00040 forceinline int 00041 plus(int x, int y) { 00042 assert(y != -Int::Limits::infinity); 00043 return (x == -Int::Limits::infinity) ? x : x+y; 00044 } 00045 00046 forceinline double 00047 plus(double x, double y) { 00048 assert(y != -Int::Limits::double_infinity); 00049 return (x == -Int::Limits::double_infinity) ? x : x+y; 00050 } 00051 00052 forceinline double 00053 div(double x, double y) { 00054 assert(y != -Int::Limits::double_infinity); 00055 return (x == -Int::Limits::double_infinity) ? x : x / y; 00056 } 00057 00058 template<class TaskView, class Node> 00059 forceinline int 00060 TaskTree<TaskView,Node>::n_inner(void) const { 00061 return tasks.size()-1; 00062 } 00063 template<class TaskView, class Node> 00064 forceinline int 00065 TaskTree<TaskView,Node>::n_nodes(void) const { 00066 return 2*tasks.size() - 1; 00067 } 00068 00069 template<class TaskView, class Node> 00070 forceinline bool 00071 TaskTree<TaskView,Node>::n_root(int i) { 00072 return i == 0; 00073 } 00074 template<class TaskView, class Node> 00075 forceinline bool 00076 TaskTree<TaskView,Node>::n_leaf(int i) const { 00077 return i >= n_inner(); 00078 } 00079 template<class TaskView, class Node> 00080 forceinline int 00081 TaskTree<TaskView,Node>::n_left(int i) { 00082 return 2*(i+1) - 1; 00083 } 00084 template<class TaskView, class Node> 00085 forceinline bool 00086 TaskTree<TaskView,Node>::left(int i) { 00087 assert(!n_root(i)); 00088 // A left node has an odd number 00089 return (i & 1) != 0; 00090 } 00091 template<class TaskView, class Node> 00092 forceinline int 00093 TaskTree<TaskView,Node>::n_right(int i) { 00094 return 2*(i+1); 00095 } 00096 template<class TaskView, class Node> 00097 forceinline bool 00098 TaskTree<TaskView,Node>::right(int i) { 00099 assert(!n_root(i)); 00100 // A left node has an even number 00101 return (i & 1) == 0; 00102 } 00103 template<class TaskView, class Node> 00104 forceinline int 00105 TaskTree<TaskView,Node>::n_parent(int i) { 00106 return (i+1)/2 - 1; 00107 } 00108 00109 template<class TaskView, class Node> 00110 forceinline Node& 00111 TaskTree<TaskView,Node>::leaf(int i) { 00112 return node[_leaf[i]]; 00113 } 00114 00115 template<class TaskView, class Node> 00116 forceinline const Node& 00117 TaskTree<TaskView,Node>::root(void) const { 00118 return node[0]; 00119 } 00120 00121 template<class TaskView, class Node> 00122 forceinline void 00123 TaskTree<TaskView,Node>::init(void) { 00124 for (int i=n_inner(); i--; ) 00125 node[i].init(node[n_left(i)],node[n_right(i)]); 00126 } 00127 00128 template<class TaskView, class Node> 00129 forceinline void 00130 TaskTree<TaskView,Node>::update(int i, bool l) { 00131 if (l) 00132 i = _leaf[i]; 00133 assert(!n_root(i)); 00134 do { 00135 i = n_parent(i); 00136 node[i].update(node[n_left(i)],node[n_right(i)]); 00137 } while (!n_root(i)); 00138 } 00139 00140 template<class TaskView, class Node> 00141 forceinline 00142 TaskTree<TaskView,Node>::TaskTree(Region& r, 00143 const TaskViewArray<TaskView>& t) 00144 : tasks(t), 00145 node(r.alloc<Node>(n_nodes())), 00146 _leaf(r.alloc<int>(tasks.size())) { 00147 // Compute a sorting map to order by non decreasing est 00148 int* map = r.alloc<int>(tasks.size()); 00149 sort<TaskView,STO_EST,true>(map, tasks); 00150 // Compute inverse of sorting map 00151 for (int i=tasks.size(); i--; ) 00152 _leaf[map[i]] = i; 00153 r.free<int>(map,tasks.size()); 00154 // Compute index of first leaf in tree: the next larger power of two 00155 int fst = 1; 00156 while (fst < tasks.size()) 00157 fst <<= 1; 00158 fst--; 00159 // Remap task indices to leaf indices 00160 for (int i=tasks.size(); i--; ) 00161 if (_leaf[i] + fst >= n_nodes()) 00162 _leaf[i] += fst - tasks.size(); 00163 else 00164 _leaf[i] += fst; 00165 } 00166 00167 template<class TaskView, class Node> template<class Node2> 00168 forceinline 00169 TaskTree<TaskView,Node>::TaskTree(Region& r, 00170 const TaskTree<TaskView,Node2>& t) 00171 : tasks(t.tasks), 00172 node(r.alloc<Node>(n_nodes())), 00173 _leaf(r.alloc<int>(tasks.size())) { 00174 for (int i=tasks.size(); i--; ) 00175 _leaf[i] = t._leaf[i]; 00176 } 00177 00178 }} 00179 00180 // STATISTICS: scheduling-prop