Generated on Wed Nov 5 2014 05:18:31 for Gecode by doxygen 1.7.6.1
cutoff.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2013
00011  *     Guido Tack, 2013
00012  *
00013  *  Last modified:
00014  *     $Date: 2013-10-30 13:25:29 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
00015  *     $Revision: 14036 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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 // STATISTICS: search-other