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
00041
00042 #include <gecode/search.hh>
00043
00044 namespace Gecode { namespace Search {
00045
00046 forceinline
00047 CutoffConstant::CutoffConstant(unsigned long int c0)
00048 : c(c0) {}
00049 unsigned long int
00050 CutoffConstant::operator ()(void) {
00051 return c;
00052 }
00053
00054
00055 forceinline
00056 CutoffLinear::CutoffLinear(unsigned long int s)
00057 : scale(s), n(0) {}
00058 unsigned long int
00059 CutoffLinear::operator ()(void) {
00060 n += scale;
00061 return n;
00062 }
00063
00064
00065 unsigned long int
00066 CutoffLuby::start[CutoffLuby::n_start] = {
00067 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,
00068 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,32
00069 };
00070 forceinline
00071 CutoffLuby::CutoffLuby(unsigned long int scale0)
00072 : i(1U), scale(scale0) {}
00073 forceinline unsigned long int
00074 CutoffLuby::log(unsigned long int i) {
00075 if (i == 1U)
00076 return 0U;
00077 unsigned long int exp = 0U;
00078 while ( (i >> (++exp)) > 1U ) {}
00079 return exp;
00080 }
00081 forceinline unsigned long int
00082 CutoffLuby::luby(unsigned long int i) {
00083 while (true) {
00084 if (i <= n_start)
00085 return start[i-1];
00086 unsigned long int l = log(i);
00087 if (i == (1U<<(l+1))-1)
00088 return 1UL<<l;
00089 i=i-(1U<<l)+1;
00090 }
00091 GECODE_NEVER;
00092 return 0;
00093 }
00094 unsigned long int
00095 CutoffLuby::operator() (void) {
00096 return scale*luby(i++);
00097 }
00098
00099
00100 forceinline
00101 CutoffGeometric::CutoffGeometric(unsigned long int scale, double base0)
00102 : n(static_cast<double>(scale)), base(base0) {}
00103 unsigned long int
00104 CutoffGeometric::operator ()(void) {
00105 unsigned long int oldn = static_cast<unsigned long int>(n);
00106 n *= base;
00107 return oldn;
00108 }
00109
00110
00111 forceinline
00112 CutoffRandom::CutoffRandom(unsigned int seed,
00113 unsigned long int min0,
00114 unsigned long int max0,
00115 unsigned long int n0)
00116 : rnd(seed), min(min0), n(n0 == 0 ? (max0-min+1U) : n0),
00117 step(std::max(1UL,
00118 static_cast<unsigned long int>((max0-min0+1U)/n))) {}
00119 unsigned long int
00120 CutoffRandom::operator ()(void) {
00121 return min+step*rnd(n);
00122 }
00123
00124
00125 forceinline
00126 CutoffAppend::CutoffAppend(Cutoff* d1, unsigned long int n0, Cutoff* d2)
00127 : c1(d1), c2(d2), n(n0) {}
00128 unsigned long int
00129 CutoffAppend::operator ()(void) {
00130 if (n > 0) {
00131 n--;
00132 return (*c1)();
00133 } else {
00134 return (*c2)();
00135 }
00136 }
00137 forceinline
00138 CutoffAppend::~CutoffAppend(void) {
00139 delete c1; delete c2;
00140 }
00141
00142
00143 forceinline
00144 CutoffRepeat::CutoffRepeat(Cutoff* c1, unsigned long int n0)
00145 : c(c1), i(0), n(n0) {
00146 cutoff = (*c)();
00147 }
00148 unsigned long int
00149 CutoffRepeat::operator ()(void) {
00150 unsigned long int current = cutoff;
00151 i++;
00152 if (i == n) {
00153 cutoff = (*c)();
00154 i = 0;
00155 }
00156 return current;
00157 }
00158 forceinline
00159 CutoffRepeat::~CutoffRepeat(void) {
00160 delete c;
00161 }
00162
00163
00164 Cutoff*
00165 Cutoff::constant(unsigned long int scale) {
00166 return new CutoffConstant(scale);
00167 }
00168 Cutoff*
00169 Cutoff::linear(unsigned long int scale) {
00170 return new CutoffLinear(scale);
00171 }
00172 Cutoff*
00173 Cutoff::luby(unsigned long int scale) {
00174 return new CutoffLuby(scale);
00175 }
00176 Cutoff*
00177 Cutoff::geometric(unsigned long int base, double scale) {
00178 return new CutoffGeometric(base,scale);
00179 }
00180 Cutoff*
00181 Cutoff::rnd(unsigned int seed,
00182 unsigned long int min,
00183 unsigned long int max,
00184 unsigned long int n) {
00185 return new CutoffRandom(seed,min,max,n);
00186 }
00187 Cutoff*
00188 Cutoff::append(Cutoff* c1, unsigned long int n, Cutoff* c2) {
00189 return new CutoffAppend(c1,n,c2);
00190 }
00191 Cutoff*
00192 Cutoff::repeat(Cutoff* c, unsigned long int n) {
00193 return new CutoffRepeat(c,n);
00194 }
00195
00196 }}
00197
00198