Generated on Tue Jun 4 2019 05:23:33 for Gecode by doxygen 1.8.15
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: 2013-10-30 13:25:29 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
15  * $Revision: 14036 $
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 <gecode/search.hh>
43 
44 namespace Gecode { namespace Search {
45 
47  CutoffConstant::CutoffConstant(unsigned long int c0)
48  : c(c0) {}
49  unsigned long int
50  CutoffConstant::operator ()(void) {
51  return c;
52  }
53 
54 
56  CutoffLinear::CutoffLinear(unsigned long int s)
57  : scale(s), n(0) {}
58  unsigned long int
60  n += scale;
61  return n;
62  }
63 
64 
65  unsigned long int
66  CutoffLuby::start[CutoffLuby::n_start] = {
67  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,
68  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
69  };
71  CutoffLuby::CutoffLuby(unsigned long int scale0)
72  : i(1U), scale(scale0) {}
73  forceinline unsigned long int
74  CutoffLuby::log(unsigned long int i) {
75  if (i == 1U)
76  return 0U;
77  unsigned long int exp = 0U;
78  while ( (i >> (++exp)) > 1U ) {}
79  return exp;
80  }
81  forceinline unsigned long int
82  CutoffLuby::luby(unsigned long int i) {
83  while (true) {
84  if (i <= n_start)
85  return start[i-1];
86  unsigned long int l = log(i);
87  if (i == (1U<<(l+1))-1)
88  return 1UL<<l;
89  i=i-(1U<<l)+1;
90  }
92  return 0;
93  }
94  unsigned long int
96  return scale*luby(i++);
97  }
98 
99 
101  CutoffGeometric::CutoffGeometric(unsigned long int scale, double base0)
102  : n(static_cast<double>(scale)), base(base0) {}
103  unsigned long int
105  unsigned long int oldn = static_cast<unsigned long int>(n);
106  n *= base;
107  return oldn;
108  }
109 
110 
112  CutoffRandom::CutoffRandom(unsigned int seed,
113  unsigned long int min0,
114  unsigned long int max0,
115  unsigned long int n0)
116  : rnd(seed), min(min0), n(n0 == 0 ? (max0-min+1U) : n0),
117  step(std::max(1UL,
118  static_cast<unsigned long int>((max0-min0+1U)/n))) {}
119  unsigned long int
121  return min+step*rnd(n);
122  }
123 
124 
126  CutoffAppend::CutoffAppend(Cutoff* d1, unsigned long int n0, Cutoff* d2)
127  : c1(d1), c2(d2), n(n0) {}
128  unsigned long int
130  if (n > 0) {
131  n--;
132  return (*c1)();
133  } else {
134  return (*c2)();
135  }
136  }
139  delete c1; delete c2;
140  }
141 
142 
144  CutoffRepeat::CutoffRepeat(Cutoff* c1, unsigned long int n0)
145  : c(c1), i(0), n(n0) {
146  cutoff = (*c)();
147  }
148  unsigned long int
150  unsigned long int current = cutoff;
151  i++;
152  if (i == n) {
153  cutoff = (*c)();
154  i = 0;
155  }
156  return current;
157  }
160  delete c;
161  }
162 
163 
164  Cutoff*
165  Cutoff::constant(unsigned long int scale) {
166  return new CutoffConstant(scale);
167  }
168  Cutoff*
169  Cutoff::linear(unsigned long int scale) {
170  return new CutoffLinear(scale);
171  }
172  Cutoff*
173  Cutoff::luby(unsigned long int scale) {
174  return new CutoffLuby(scale);
175  }
176  Cutoff*
177  Cutoff::geometric(unsigned long int base, double scale) {
178  return new CutoffGeometric(base,scale);
179  }
180  Cutoff*
181  Cutoff::rnd(unsigned int seed,
182  unsigned long int min,
183  unsigned long int max,
184  unsigned long int n) {
185  return new CutoffRandom(seed,min,max,n);
186  }
187  Cutoff*
188  Cutoff::append(Cutoff* c1, unsigned long int n, Cutoff* c2) {
189  return new CutoffAppend(c1,n,c2);
190  }
191  Cutoff*
192  Cutoff::repeat(Cutoff* c, unsigned long int n) {
193  return new CutoffRepeat(c,n);
194  }
195 
196 }}
197 
198 // STATISTICS: search-other
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:95
const Gecode::FloatNum step
Definition: arithmetic.cpp:789
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:104
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
static Cutoff * geometric(unsigned long int scale=1U, double base=1.5)
Definition: cutoff.cpp:177
Cutoff generator appending two cutoff generators.
Definition: cutoff.hpp:132
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
virtual ~CutoffAppend(void)
Destructor.
Definition: cutoff.cpp:138
Cutoff generator for the Luby sequence.
Definition: cutoff.hpp:73
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:389
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:120
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:149
static Cutoff * repeat(Cutoff *c, unsigned long int n)
Create generator that repeats n times each cutoff value from c.
Definition: cutoff.cpp:192
Gecode::IntSet d1(v1, 7)
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
Cutoff generator for the random sequence.
Definition: cutoff.hpp:111
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Gecode::IntSet d2(v2, 9)
virtual ~CutoffRepeat(void)
Destructor.
Definition: cutoff.cpp:159
static Cutoff * linear(unsigned long int scale=1U)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:169
static Cutoff * rnd(unsigned int seed, unsigned long int min, unsigned long int max, unsigned long int n)
Definition: cutoff.cpp:181
static Cutoff * constant(unsigned long int scale=1U)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:165
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:59
Cutoff generator for linear sequence.
Definition: cutoff.hpp:58
Cutoff generator for the geometric sequence.
Definition: cutoff.hpp:96
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:188
Cutoff generator for constant sequence.
Definition: cutoff.hpp:45
#define forceinline
Definition: config.hpp:167
static Cutoff * luby(unsigned long int scale=1U)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:173
Cutoff generator that repeats a cutoff from another cutoff generator.
Definition: cutoff.hpp:151
virtual unsigned long int operator()(void)
Return next cutoff value.
Definition: cutoff.cpp:129
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