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 long long int
00049 plus(long long int x, long long int y) {
00050 assert(y != -Int::Limits::llinfinity);
00051 return (x == -Int::Limits::llinfinity) ? x : x+y;
00052 }
00053
00054 template<class TaskView, class Node>
00055 forceinline int
00056 TaskTree<TaskView,Node>::n_inner(void) const {
00057 return tasks.size()-1;
00058 }
00059 template<class TaskView, class Node>
00060 forceinline int
00061 TaskTree<TaskView,Node>::n_nodes(void) const {
00062 return 2*tasks.size() - 1;
00063 }
00064
00065 template<class TaskView, class Node>
00066 forceinline bool
00067 TaskTree<TaskView,Node>::n_root(int i) {
00068 return i == 0;
00069 }
00070 template<class TaskView, class Node>
00071 forceinline bool
00072 TaskTree<TaskView,Node>::n_leaf(int i) const {
00073 return i >= n_inner();
00074 }
00075 template<class TaskView, class Node>
00076 forceinline int
00077 TaskTree<TaskView,Node>::n_left(int i) {
00078 return 2*(i+1) - 1;
00079 }
00080 template<class TaskView, class Node>
00081 forceinline bool
00082 TaskTree<TaskView,Node>::left(int i) {
00083 assert(!n_root(i));
00084
00085 return (i & 1) != 0;
00086 }
00087 template<class TaskView, class Node>
00088 forceinline int
00089 TaskTree<TaskView,Node>::n_right(int i) {
00090 return 2*(i+1);
00091 }
00092 template<class TaskView, class Node>
00093 forceinline bool
00094 TaskTree<TaskView,Node>::right(int i) {
00095 assert(!n_root(i));
00096
00097 return (i & 1) == 0;
00098 }
00099 template<class TaskView, class Node>
00100 forceinline int
00101 TaskTree<TaskView,Node>::n_parent(int i) {
00102 return (i+1)/2 - 1;
00103 }
00104
00105 template<class TaskView, class Node>
00106 forceinline Node&
00107 TaskTree<TaskView,Node>::leaf(int i) {
00108 return node[_leaf[i]];
00109 }
00110
00111 template<class TaskView, class Node>
00112 forceinline const Node&
00113 TaskTree<TaskView,Node>::root(void) const {
00114 return node[0];
00115 }
00116
00117 template<class TaskView, class Node>
00118 forceinline void
00119 TaskTree<TaskView,Node>::init(void) {
00120 for (int i=n_inner(); i--; )
00121 node[i].init(node[n_left(i)],node[n_right(i)]);
00122 }
00123
00124 template<class TaskView, class Node>
00125 forceinline void
00126 TaskTree<TaskView,Node>::update(void) {
00127 for (int i=n_inner(); i--; )
00128 node[i].update(node[n_left(i)],node[n_right(i)]);
00129 }
00130
00131 template<class TaskView, class Node>
00132 forceinline void
00133 TaskTree<TaskView,Node>::update(int i, bool l) {
00134 if (l)
00135 i = _leaf[i];
00136 assert(!n_root(i));
00137 do {
00138 i = n_parent(i);
00139 node[i].update(node[n_left(i)],node[n_right(i)]);
00140 } while (!n_root(i));
00141 }
00142
00143 template<class TaskView, class Node>
00144 forceinline
00145 TaskTree<TaskView,Node>::TaskTree(Region& r,
00146 const TaskViewArray<TaskView>& t)
00147 : tasks(t),
00148 node(r.alloc<Node>(n_nodes())),
00149 _leaf(r.alloc<int>(tasks.size())) {
00150
00151 int* map = r.alloc<int>(tasks.size());
00152 sort<TaskView,STO_EST,true>(map, tasks);
00153
00154 for (int i=tasks.size(); i--; )
00155 _leaf[map[i]] = i;
00156 r.free<int>(map,tasks.size());
00157
00158 int fst = 1;
00159 while (fst < tasks.size())
00160 fst <<= 1;
00161 fst--;
00162
00163 for (int i=tasks.size(); i--; )
00164 if (_leaf[i] + fst >= n_nodes())
00165 _leaf[i] += fst - tasks.size();
00166 else
00167 _leaf[i] += fst;
00168 }
00169
00170 template<class TaskView, class Node> template<class Node2>
00171 forceinline
00172 TaskTree<TaskView,Node>::TaskTree(Region& r,
00173 const TaskTree<TaskView,Node2>& t)
00174 : tasks(t.tasks),
00175 node(r.alloc<Node>(n_nodes())),
00176 _leaf(r.alloc<int>(tasks.size())) {
00177 for (int i=tasks.size(); i--; )
00178 _leaf[i] = t._leaf[i];
00179 }
00180
00181 }}
00182
00183