not-first-not-last.hpp
Go to the documentation of this file.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 #include <algorithm>
00039
00040 namespace Gecode { namespace Int { namespace Unary {
00041
00042 template<class ManTaskView>
00043 forceinline ExecStatus
00044 notlast(Space& home, TaskViewArray<ManTaskView>& t) {
00045 sort<ManTaskView,STO_LCT,true>(t);
00046
00047 Region r(home);
00048
00049 OmegaTree<ManTaskView> o(r,t);
00050 TaskViewIter<ManTaskView,STO_LST,true> q(r,t);
00051 int* lct = r.alloc<int>(t.size());
00052
00053 for (int i=t.size(); i--; )
00054 lct[i] = t[i].lct();
00055
00056 for (int i=0; i<t.size(); i++) {
00057 int j = -1;
00058 while (q() && (t[i].lct() > t[q.task()].lst())) {
00059 if ((j >= 0) && (o.ect() > t[q.task()].lst()))
00060 lct[q.task()] = std::min(lct[q.task()],t[j].lst());
00061 j = q.task();
00062 o.insert(j); ++q;
00063 }
00064 if ((j >= 0) && (o.ect(i) > t[i].lst()))
00065 lct[i] = std::min(lct[i],t[j].lst());
00066 }
00067
00068 for (int i=t.size(); i--; )
00069 GECODE_ME_CHECK(t[i].lct(home,lct[i]));
00070
00071 return ES_OK;
00072 }
00073
00074 template<class ManTask>
00075 ExecStatus
00076 notfirstnotlast(Space& home, TaskArray<ManTask>& t) {
00077 TaskViewArray<typename TaskTraits<ManTask>::TaskViewFwd> f(t);
00078 GECODE_ES_CHECK(notlast(home,f));
00079 TaskViewArray<typename TaskTraits<ManTask>::TaskViewBwd> b(t);
00080 return notlast(home,b);
00081 }
00082
00083 template<class OptTaskView, class PL>
00084 forceinline ExecStatus
00085 notlast(Space& home, Propagator& p, TaskViewArray<OptTaskView>& t) {
00086 sort<OptTaskView,STO_LCT,true>(t);
00087
00088 Region r(home);
00089
00090 OmegaTree<OptTaskView> o(r,t);
00091 ManTaskViewIter<OptTaskView,STO_LST,true> q(r,t);
00092 int* lct = r.alloc<int>(t.size());
00093
00094 for (int i=t.size(); i--; )
00095 lct[i] = t[i].lct();
00096
00097 for (int i=0; i<t.size(); i++) {
00098 int j = -1;
00099 while (q() && (t[i].lct() > t[q.task()].lst())) {
00100 if ((j >= 0) && (o.ect() > t[q.task()].lst()))
00101 lct[q.task()] = std::min(lct[q.task()],t[j].lst());
00102 j = q.task();
00103 o.insert(j); ++q;
00104 }
00105 if ((j >= 0) && (o.ect(i) > t[i].lst()))
00106 lct[i] = std::min(lct[i],t[j].lst());
00107 }
00108
00109 {
00110 int n = t.size();
00111 for (int i=n; i--; )
00112 if (t[i].mandatory()) {
00113 GECODE_ME_CHECK(t[i].lct(home,lct[i]));
00114 } else if (lct[i] < t[i].ect()) {
00115 GECODE_ME_CHECK(t[i].excluded(home));
00116 t[i].cancel(home,p,PL::pc); t[i]=t[--n];
00117 }
00118 t.size(n);
00119 }
00120
00121 return (t.size() < 2) ? home.ES_SUBSUMED(p) : ES_OK;
00122 }
00123
00124 template<class OptTask, class PL>
00125 ExecStatus
00126 notfirstnotlast(Space& home, Propagator& p, TaskArray<OptTask>& t) {
00127 TaskViewArray<typename TaskTraits<OptTask>::TaskViewFwd> f(t);
00128 GECODE_ES_CHECK((notlast<typename TaskTraits<OptTask>::TaskViewFwd,PL>
00129 (home,p,f)));
00130 TaskViewArray<typename TaskTraits<OptTask>::TaskViewBwd> b(t);
00131 return notlast<typename TaskTraits<OptTask>::TaskViewBwd,PL>(home,p,b);
00132 }
00133
00134 }}}
00135
00136