00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 namespace Gecode { namespace Int {
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
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
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
00157 int* map = r.alloc<int>(tasks.size());
00158 sort<TaskView,STO_EST,true>(map, tasks);
00159
00160 for (int i=tasks.size(); i--; )
00161 _leaf[map[i]] = i;
00162 r.free<int>(map,tasks.size());
00163
00164 int fst = 1;
00165 while (fst < tasks.size())
00166 fst <<= 1;
00167 fst--;
00168
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