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