Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
cutoff.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2013
11  * Guido Tack, 2013
12  *
13  * Last modified:
14  * $Date: 2014-10-21 17:09:50 +0200 (Tue, 21 Oct 2014) $ by $Author: schulte $
15  * $Revision: 14258 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <algorithm>
43 #include <gecode/search.hh>
44 
45 namespace Gecode { namespace Search {
46 
48  CutoffConstant::CutoffConstant(unsigned long int c0)
49  : c(c0) {}
50  unsigned long int
51  CutoffConstant::operator ()(void) const {
52  return c;
53  }
54  unsigned long int
55  CutoffConstant::operator ++(void) {
56  return c;
57  }
58 
59 
61  CutoffLinear::CutoffLinear(unsigned long int s)
62  : scale(s), n(0) {}
63  unsigned long int
65  return n;
66  }
67  unsigned long int
69  n += scale;
70  return n;
71  }
72 
73 
74  unsigned long int
75  CutoffLuby::start[CutoffLuby::n_start] = {
76  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,
77  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
78  };
80  CutoffLuby::CutoffLuby(unsigned long int scale0)
81  : i(1U), scale(scale0) {}
82  forceinline unsigned long int
83  CutoffLuby::log(unsigned long int i) {
84  if (i == 1U)
85  return 0U;
86  unsigned long int exp = 0U;
87  while ( (i >> (++exp)) > 1U ) {}
88  return exp;
89  }
90  forceinline unsigned long int
91  CutoffLuby::luby(unsigned long int i) {
92  while (true) {
93  if (i <= n_start)
94  return start[i-1];
95  unsigned long int l = log(i);
96  if (i == (1U<<(l+1))-1)
97  return 1UL<<l;
98  i=i-(1U<<l)+1;
99  }
100  GECODE_NEVER;
101  return 0;
102  }
103  unsigned long int
105  return scale*luby(i);
106  }
107  unsigned long int
109  return scale*luby(i++);
110  }
111 
112 
114  CutoffGeometric::CutoffGeometric(unsigned long int scale0, double base0)
115  : n(1.0), scale(static_cast<double>(scale0)), base(base0) {}
116  unsigned long int
118  return scale * n;
119  }
120  unsigned long int
122  n *= base;
123  return scale * n;
124  }
125 
126 
127  unsigned long int
129  cur = min+step*rnd(n);
130  return cur;
131  }
133  CutoffRandom::CutoffRandom(unsigned int seed,
134  unsigned long int min0,
135  unsigned long int max0,
136  unsigned long int n0)
137  : rnd(seed), min(min0), n(n0 == 0 ? (max0-min+1U) : n0),
138  step(std::max(1UL,
139  static_cast<unsigned long int>((max0-min0+1U)/n))) {
140  cur = ++(*this);
141  }
142  unsigned long int
144  return cur;
145  }
146 
147 
149  CutoffAppend::CutoffAppend(Cutoff* d1, unsigned long int n0, Cutoff* d2)
150  : c1(d1), c2(d2), n(n0) {}
151  unsigned long int
153  if (n > 0) {
154  return (*c1)();
155  } else {
156  return (*c2)();
157  }
158  }
159  unsigned long int
161  if (n > 0) {
162  n--;
163  return ++(*c1);
164  } else {
165  return ++(*c2);
166  }
167  }
170  delete c1; delete c2;
171  }
172 
173 
175  CutoffMerge::CutoffMerge(Cutoff* d1, Cutoff* d2)
176  : c1(d1), c2(d2) {}
177  unsigned long int
179  return (*c1)();
180  }
181  unsigned long int
183  (void) ++(*c1);
184  std::swap(c1,c2);
185  return (*c1)();
186  }
189  delete c1; delete c2;
190  }
191 
192 
194  CutoffRepeat::CutoffRepeat(Cutoff* c1, unsigned long int n0)
195  : c(c1), i(0), n(n0) {
196  cutoff = (*c)();
197  }
198  unsigned long int
200  return cutoff;
201  }
202  unsigned long int
204  i++;
205  if (i == n) {
206  cutoff = (*c)();
207  i = 0;
208  }
209  return cutoff;
210  }
213  delete c;
214  }
215 
216 
217  Cutoff*
218  Cutoff::constant(unsigned long int scale) {
219  return new CutoffConstant(scale);
220  }
221  Cutoff*
222  Cutoff::linear(unsigned long int scale) {
223  return new CutoffLinear(scale);
224  }
225  Cutoff*
226  Cutoff::luby(unsigned long int scale) {
227  return new CutoffLuby(scale);
228  }
229  Cutoff*
230  Cutoff::geometric(unsigned long int base, double scale) {
231  return new CutoffGeometric(base,scale);
232  }
233  Cutoff*
234  Cutoff::rnd(unsigned int seed,
235  unsigned long int min,
236  unsigned long int max,
237  unsigned long int n) {
238  return new CutoffRandom(seed,min,max,n);
239  }
240  Cutoff*
241  Cutoff::append(Cutoff* c1, unsigned long int n, Cutoff* c2) {
242  return new CutoffAppend(c1,n,c2);
243  }
244  Cutoff*
246  return new CutoffMerge(c1,c2);
247  }
248  Cutoff*
249  Cutoff::repeat(Cutoff* c, unsigned long int n) {
250  return new CutoffRepeat(c,n);
251  }
252 
253 }}
254 
255 // STATISTICS: search-other
const Gecode::FloatNum step
Definition: arithmetic.cpp:789
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:64
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:160
static Cutoff * merge(Cutoff *c1, Cutoff *c2)
Merge cutoff values from c1 with values from c2.
Definition: cutoff.cpp:245
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:152
static Cutoff * geometric(unsigned long int scale=1U, double base=1.5)
Definition: cutoff.cpp:230
Cutoff generator appending two cutoff generators.
Definition: cutoff.hpp:146
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:128
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:108
virtual ~CutoffAppend(void)
Destructor.
Definition: cutoff.cpp:169
Cutoff generator for the Luby sequence.
Definition: cutoff.hpp:77
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:389
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Definition: cutoff.cpp:249
Gecode::IntSet d1(v1, 7)
Gecode::FloatVal c(-8, 8)
Cutoff generator merging two cutoff generators.
Definition: cutoff.hpp:167
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:203
Gecode::IntArgs i(4, 1, 2, 3, 4)
Cutoff generator for the random sequence.
Definition: cutoff.hpp:121
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Gecode::IntSet d2(v2, 9)
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:199
virtual ~CutoffRepeat(void)
Destructor.
Definition: cutoff.cpp:212
static Cutoff * linear(unsigned long int scale=1U)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:222
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Definition: cutoff.cpp:234
static Cutoff * constant(unsigned long int scale=1U)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:218
Cutoff generator for linear sequence.
Definition: cutoff.hpp:60
virtual ~CutoffMerge(void)
Destructor.
Definition: cutoff.cpp:188
Cutoff generator for the geometric sequence.
Definition: cutoff.hpp:102
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
static Cutoff * append(Cutoff *c1, unsigned long int n, Cutoff *c2)
Append cutoff values from c2 after n values from c1.
Definition: cutoff.cpp:241
Cutoff generator for constant sequence.
Definition: cutoff.hpp:45
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:104
#define forceinline
Definition: config.hpp:132
static Cutoff * luby(unsigned long int scale=1U)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:226
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: cutoff.hpp:186
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:143
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:178
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:182
virtual unsigned long int operator()(void) const
Return the current cutoff value.
Definition: cutoff.cpp:117
Gecode toplevel namespace
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:121
virtual unsigned long int operator++(void)
Increment and return the next cutoff value.
Definition: cutoff.cpp:68