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 namespace Gecode { namespace Search { 00043 00045 class CutoffConstant : public Cutoff { 00046 friend class Cutoff; 00047 private: 00049 unsigned long int c; 00051 CutoffConstant(unsigned long int c); 00052 public: 00054 virtual unsigned long int operator() (void); 00055 }; 00056 00058 class CutoffLinear : public Cutoff { 00059 friend class Cutoff; 00060 private: 00062 unsigned long int scale; 00064 unsigned long int n; 00066 CutoffLinear(unsigned long int scale); 00067 public: 00069 virtual unsigned long int operator() (void); 00070 }; 00071 00073 class CutoffLuby : public Cutoff { 00074 friend class Cutoff; 00075 private: 00077 unsigned long int i; 00079 unsigned long int scale; 00081 static const unsigned long int n_start = 63U; 00083 static unsigned long int start[n_start]; 00085 static unsigned long int log(unsigned long int i); 00087 static unsigned long int luby(unsigned long int i); 00089 CutoffLuby(unsigned long int scale); 00090 public: 00092 virtual unsigned long int operator() (void); 00093 }; 00094 00096 class CutoffGeometric : public Cutoff { 00097 friend class Cutoff; 00098 private: 00100 double n; 00102 double base; 00104 CutoffGeometric(unsigned long int scale, double base); 00105 public: 00107 virtual unsigned long int operator ()(void); 00108 }; 00109 00111 class CutoffRandom : public Cutoff { 00112 friend class Cutoff; 00113 private: 00115 Support::RandomGenerator rnd; 00117 unsigned long int min; 00119 unsigned long int n; 00121 unsigned long int step; 00123 CutoffRandom(unsigned int seed, 00124 unsigned long int min, unsigned long int max, 00125 unsigned long int n); 00126 public: 00128 virtual unsigned long int operator ()(void); 00129 }; 00130 00132 class CutoffAppend : public Cutoff { 00133 friend class Cutoff; 00134 private: 00136 Cutoff* c1; 00138 Cutoff* c2; 00140 unsigned long int n; 00142 CutoffAppend(Cutoff* c1, unsigned long int n, Cutoff* c2); 00143 public: 00145 virtual unsigned long int operator ()(void); 00147 virtual ~CutoffAppend(void); 00148 }; 00149 00151 class CutoffRepeat : public Cutoff { 00152 friend class Cutoff; 00153 private: 00155 Cutoff* c; 00156 // Current cutoff 00157 unsigned int cutoff; 00158 // Iteration 00159 unsigned long int i; 00160 // Number of repetitions 00161 unsigned long int n; 00163 CutoffRepeat(Cutoff* c, unsigned long int n); 00164 public: 00166 virtual unsigned long int operator ()(void); 00168 virtual ~CutoffRepeat(void); 00169 }; 00170 00171 forceinline 00172 Cutoff::Cutoff(void) {} 00173 forceinline 00174 Cutoff::~Cutoff(void) {} 00175 forceinline void* 00176 Cutoff::operator new(size_t s) { 00177 return heap.ralloc(s); 00178 } 00179 forceinline void 00180 Cutoff::operator delete(void* p) { 00181 heap.rfree(p); 00182 } 00183 00184 }} 00185 00186 // STATISTICS: search-other