Name | Total Lines | Lines of Code | Total Coverage | Code Coverage |
---|---|---|---|---|

lib/gecoder/interface/constraints.rb | 479 |
259 |
100.00% |
100.00% |

Code reported as executed by Ruby looks like this...and this: this line is also marked as covered.Lines considered as run by rcov, but not reported by Ruby, look like this,and this: these lines were inferred by rcov (using simple heuristics).Finally, here's a line marked as not executed.

1 module Gecode |

2 # An error signaling that the constraint specified is missing (e.g. one tried |

3 # to negate a constraint, but no negated form is implemented). |

4 class MissingConstraintError < StandardError |

5 end |

6 |

7 # Describes an operand, something that a constraint can be placed |

8 # on. Constraints are placed by calling #must or #must_not (the |

9 # latter negates the constraint). This produces a |

10 # ConstraintReceiver, which defines methods that places constraints |

11 # on the operand. |

12 # |

13 # In general this produces something like the following. |

14 # |

15 # operand.must.constraint_method(params) |

16 # |

17 # See e.g. Gecode::Int::IntOperand for concrete examples. |

18 # |

19 # Classes that mix in Operand must define the methods #model |

20 # and #construct_receiver. They should also define a method that converts |

21 # the operand into a variable of the operand's type (e.g. int var |

22 # operands should define a method #to_int_var that returns an |

23 # instance of Gecode::IntVar that represents the operand). The |

24 # latter method should be used by constraints to fetch variables |

25 # needed when posting constraints. The presence of the method should |

26 # also be used for type checking (rather than e.g. checking whether |

27 # a parameter is of type IntOperand). |

28 module Operand |

29 # Specifies that a constraint must hold for the left hand side. |

30 def must |

31 construct_receiver :lhs => self, :negate => false |

32 end |

33 alias_method :must_be, :must |

34 |

35 # Specifies that the negation of a constraint must hold for the left hand |

36 # side. |

37 def must_not |

38 construct_receiver :lhs => self, :negate => true |

39 end |

40 alias_method :must_not_be, :must_not |

41 |

42 # Fetches the model that the operand belongs to. |

43 def model |

44 raise NotImplementedError, 'Abstract method has not been implemented.' |

45 end |

46 |

47 private |

48 |

49 # Constructs the appropriate constraint receiver given the |

50 # specified parameters. |

51 def construct_receiver(params) |

52 raise NotImplementedError, 'Abstract method has not been implemented.' |

53 end |

54 end |

55 |

56 # Describes a constraint receiver, something that receives and |

57 # places constraints on various Operand. Constraint receivers |

58 # are created by calling #must or #must_not (the latter negates |

59 # the constraint) on something that mixes in Operand. |

60 # |

61 # A constraint is placed on an Operand +operand+ as follows: |

62 # |

63 # operand.must.constraint_method(params) |

64 # |

65 # The constraint receiver is created by the call to #must and the |

66 # constraint is then placed by the call to #constraint_method. |

67 # See e.g. Gecode::Int::IntConstraintReceiver for |

68 # concrete examples. |

69 # |

70 # The following options can be specified in a hash with symbols as |

71 # keys when placing a constraint: |

72 # |

73 # [:strength] The propagation strength suggests how much effort the |

74 # solver should put into trying to prune the domains of |

75 # variables using the constraint. |

76 # |

77 # The allowed values are: |

78 # [:value] Value consistency (naive). |

79 # [:bounds] Bounds consistency. The bounds of the operand |

80 # will always be constrained as much as possible |

81 # (but pruning may not be done inside the |

82 # bounds, even though it may be possible). |

83 # [:domain] Domain consistency. All values that can be pruned |

84 # away, given the current amount of information, |

85 # are pruned away. |

86 # [:default] Uses the default consistency of the constraint. |

87 # |

88 # The strength generally progresses as |

89 # :value < :bounds < :domain (:value being the weakest, |

90 # :domain being the strongest). A higher strength can |

91 # reduce the search space quicker, but at the cost of |

92 # making each propagation more costly. |

93 # |

94 # [:kind] The propagation kind option suggests the implementation |

95 # that should be preferred if there are multiple |

96 # implementations of a constraint. |

97 # |

98 # The different kinds are: |

99 # [:speed] Prefer speed over memory consumption. |

100 # [:memory] Prefer low memory consumption over speed. |

101 # [:default] Uses the constraint's default propagation kind. |

102 # |

103 # [:reify] Reification is used to link a constraint to a boolean |

104 # operand in such a way that the variable is true if and |

105 # only if the constraint is satisfied. The propagation |

106 # goes both ways, so if the variable is constrained to be |

107 # false then the constraint is not allowed to be |

108 # satisfied. |

109 # |

110 # Reification can be thought of as a last resort glue which |

111 # can be used to combine constraints so that e.g. exactly |

112 # 3 out of 17 constraints must be satisfied. |

113 # |

114 # Not all constraints accept all options. Constraints that have sets |

115 # as operands (e.g. SetConstraintReceiver and |

116 # SetEnumConstraintReceiver) do not accept the :strength and :kind |

117 # options, all other do. Some constraints do not accept the :reify |

118 # option. |

119 # |

120 # See e.g. Gecode::Int::IntConstraintReceiver for |

121 # concrete examples of options being specified. |

122 class ConstraintReceiver |

123 # A list that keeps track of all constraint methods used in the |

124 # program, essentially providing unique ids for each. |

125 @@constraint_names_list ||= [] |

126 |

127 # Constructs a new expression with the specified parameters. The |

128 # parameters should at least contain the keys :lhs, and :negate. |

129 # |

130 # Raises ArgumentError if any of those keys are missing or if :lhs |

131 # is not an operand. |

132 def initialize(model, params) |

133 unless params.has_key?(:lhs) and params.has_key?(:negate) |

134 raise ArgumentError, 'Expression requires at least :lhs, ' + |

135 "and :negate as parameter keys, got #{params.keys.join(', ')}." |

136 end |

137 unless params[:lhs].kind_of? Operand |

138 raise ArgumentError, 'Expected :lhs to be an operand, received ' + |

139 "#{params[:lhs].class}." |

140 end |

141 |

142 @model = model |

143 @params = params |

144 end |

145 |

146 private |

147 |

148 # Provides commutativity for the constraint with the specified |

149 # method name. If the method with the specified method name is |

150 # called with something that, when given to the block, evaluates |

151 # to true, then the constraint will be called on the right hand |

152 # side with the left hand side as argument. |

153 # |

154 # The original constraint method is assumed to take two arguments: |

155 # a right hand side and a hash of options. |

156 def self.provide_commutativity(constraint_name, &block) |

157 unless @@constraint_names_list.include? constraint_name |

158 @@constraint_names_list << constraint_name |

159 end |

160 unique_id = @@constraint_names_list.index(constraint_name) |

161 |

162 pre_alias_method_name = "pre_commutivity_#{unique_id}" |

163 if method_defined? constraint_name |

164 alias_method pre_alias_method_name, constraint_name |

165 end |

166 |

167 module_eval <<-end_code |

168 @@commutivity_check_#{unique_id} = block |

169 def #{constraint_name}(rhs, options = {}) |

170 if @@commutivity_check_#{unique_id}.call(rhs, options) |

171 if @params[:negate] |

172 rhs.must_not.method(:#{constraint_name}).call( |

173 @params[:lhs], options) |

174 else |

175 rhs.must.method(:#{constraint_name}).call( |

176 @params[:lhs], options) |

177 end |

178 else |

179 if self.class.method_defined? :#{pre_alias_method_name} |

180 #{pre_alias_method_name}(rhs, options) |

181 else |

182 raise TypeError, \"Unexpected argument type \#{rhs.class}.\" |

183 end |

184 end |

185 end |

186 end_code |

187 end |

188 |

189 # Creates aliases for any defined comparison methods. |

190 def self.alias_comparison_methods |

191 Gecode::Util::COMPARISON_ALIASES.each_pair do |orig, aliases| |

192 if instance_methods.include?(orig.to_s) |

193 aliases.each do |name| |

194 alias_method(name, orig) |

195 end |

196 end |

197 end |

198 end |

199 |

200 # Creates aliases for any defined set methods. |

201 def self.alias_set_methods |

202 Gecode::Util::SET_ALIASES.each_pair do |orig, aliases| |

203 if instance_methods.include?(orig.to_s) |

204 aliases.each do |name| |

205 alias_method(name, orig) |

206 end |

207 end |

208 end |

209 end |

210 end |

211 |

212 # Base class for all constraints. |

213 class Constraint #:nodoc: |

214 # Creates a constraint with the specified parameters, bound to the |

215 # specified model. |

216 def initialize(model, params) |

217 @model = model |

218 @params = params.clone |

219 end |

220 |

221 # Posts the constraint, adding it to the model. This is an abstract |

222 # method and should be overridden by all sub-classes. |

223 def post |

224 raise NotImplementedError, 'Abstract method has not been implemented.' |

225 end |

226 |

227 private |

228 |

229 # Gives an array of the values selected for the standard propagation |

230 # options (propagation strength and propagation kind) in the order that |

231 # they are given when posting constraints to Gecode. |

232 def propagation_options |

233 Gecode::Util::extract_propagation_options(@params) |

234 end |

235 end |

236 |

237 # A constraint that can be specified by providing a block containing the |

238 # post method. |

239 class BlockConstraint < Constraint #:nodoc: |

240 def initialize(model, params, &block) |

241 super(model, params) |

242 @proc = block |

243 end |

244 |

245 def post |

246 @proc.call |

247 end |

248 end |

249 |

250 # A module that provides some utility-methods for constraints. |

251 module Util #:nodoc: |

252 # Maps the name used in options to the value used in Gecode for |

253 # propagation strengths. |

254 PROPAGATION_STRENGTHS = { |

255 :default => Gecode::Raw::ICL_DEF, |

256 :value => Gecode::Raw::ICL_VAL, |

257 :bounds => Gecode::Raw::ICL_BND, |

258 :domain => Gecode::Raw::ICL_DOM |

259 } |

260 |

261 # Maps the name used in options to the value used in Gecode for |

262 # propagation kinds. |

263 PROPAGATION_KINDS = { |

264 :default => Gecode::Raw::PK_DEF, |

265 :speed => Gecode::Raw::PK_SPEED, |

266 :memory => Gecode::Raw::PK_MEMORY, |

267 } |

268 |

269 # Maps the names of the methods to the corresponding integer relation |

270 # type in Gecode. |

271 RELATION_TYPES = { |

272 :== => Gecode::Raw::IRT_EQ, |

273 :<= => Gecode::Raw::IRT_LQ, |

274 :< => Gecode::Raw::IRT_LE, |

275 :>= => Gecode::Raw::IRT_GQ, |

276 :> => Gecode::Raw::IRT_GR |

277 } |

278 # The same as above, but negated. |

279 NEGATED_RELATION_TYPES = { |

280 :== => Gecode::Raw::IRT_NQ, |

281 :<= => Gecode::Raw::IRT_GR, |

282 :< => Gecode::Raw::IRT_GQ, |

283 :>= => Gecode::Raw::IRT_LE, |

284 :> => Gecode::Raw::IRT_LQ |

285 } |

286 |

287 # Maps the names of the methods to the corresponding set relation type in |

288 # Gecode. |

289 SET_RELATION_TYPES = { |

290 :== => Gecode::Raw::SRT_EQ, |

291 :superset => Gecode::Raw::SRT_SUP, |

292 :subset => Gecode::Raw::SRT_SUB, |

293 :disjoint => Gecode::Raw::SRT_DISJ, |

294 :complement => Gecode::Raw::SRT_CMPL |

295 } |

296 # The same as above, but negated. |

297 NEGATED_SET_RELATION_TYPES = { |

298 :== => Gecode::Raw::SRT_NQ |

299 } |

300 # Maps the names of the methods to the corresponding set operation type in |

301 # Gecode. |

302 SET_OPERATION_TYPES = { |

303 :union => Gecode::Raw::SOT_UNION, |

304 :disjoint_union => Gecode::Raw::SOT_DUNION, |

305 :intersection => Gecode::Raw::SOT_INTER, |

306 :minus => Gecode::Raw::SOT_MINUS |

307 } |

308 |

309 # Various method aliases for comparison methods. Maps the original |

310 # (symbol) name to an array of aliases. |

311 COMPARISON_ALIASES = { |

312 :== => [:equal, :equal_to], |

313 :> => [:greater, :greater_than], |

314 :>= => [:greater_or_equal, :greater_than_or_equal_to], |

315 :< => [:less, :less_than], |

316 :<= => [:less_or_equal, :less_than_or_equal_to] |

317 } |

318 SET_ALIASES = { |

319 :== => [:equal, :equal_to], |

320 :superset => [:superset_of], |

321 :subset => [:subset_of], |

322 :disjoint => [:disjoint_with], |

323 :complement => [:complement_of] |

324 } |

325 |

326 module_function |

327 |

328 # Decodes the common options to constraints: strength, kind and |

329 # reification. Returns a hash with up to three values. :strength is the |

330 # strength that should be used for the constraint, :kind is the |

331 # propagation kind that should be used, and :reif is the (bound) boolean |

332 # operand that should be used for reification. The decoded options are |

333 # removed from the hash (so in general the hash will be consumed in the |

334 # process). |

335 # |

336 # Raises ArgumentError if an unrecognized option is found in the specified |

337 # hash. Or if an unrecognized strength is given. Raises TypeError if the |

338 # reification operand is not a boolean operand. |

339 def decode_options(options) |

340 # Propagation strength. |

341 strength = options.delete(:strength) || :default |

342 unless PROPAGATION_STRENGTHS.include? strength |

343 raise ArgumentError, "Unrecognized propagation strength #{strength}." |

344 end |

345 |

346 # Propagation kind. |

347 kind = options.delete(:kind) || :default |

348 unless PROPAGATION_KINDS.include? kind |

349 raise ArgumentError, "Unrecognized propagation kind #{kind}." |

350 end |

351 |

352 # Reification. |

353 reif_var = options.delete(:reify) |

354 unless reif_var.nil? or reif_var.respond_to? :to_bool_var |

355 raise TypeError, 'Only boolean operands may be used for reification.' |

356 end |

357 |

358 # Check for unrecognized options. |

359 unless options.empty? |

360 raise ArgumentError, 'Unrecognized constraint option: ' + |

361 options.keys.first.to_s |

362 end |

363 return { |

364 :strength => PROPAGATION_STRENGTHS[strength], |

365 :kind => PROPAGATION_KINDS[kind], |

366 :reif => reif_var |

367 } |

368 end |

369 |

370 # Converts the different ways to specify constant sets in the interface |

371 # to the form that the set should be represented in Gecode (possibly |

372 # multiple paramters. The different forms accepted are: |

373 # * Single instance of Fixnum (singleton set). |

374 # * Range (set containing all numbers in range), treated differently from |

375 # other enumerations. |

376 # * Enumeration of integers (set contaning all numbers in set). |

377 def constant_set_to_params(constant_set) |

378 unless constant_set?(constant_set) |

379 raise TypeError, "Expected a constant set, got: #{constant_set}." |

380 end |

381 |

382 if constant_set.kind_of? Range |

383 return constant_set.first, constant_set.last |

384 elsif constant_set.kind_of? Fixnum |

385 return constant_set |

386 else |

387 constant_set = constant_set.to_a |

388 return Gecode::Raw::IntSet.new(constant_set, constant_set.size) |

389 end |

390 end |

391 |

392 # Converts the different ways to specify constant sets in the interface |

393 # to an instance of Gecode::Raw::IntSet. The different forms accepted are: |

394 # * Single instance of Fixnum (singleton set). |

395 # * Range (set containing all numbers in range), treated differently from |

396 # other enumerations. |

397 # * Enumeration of integers (set contaning all numbers in set). |

398 def constant_set_to_int_set(constant_set) |

399 unless constant_set?(constant_set) |

400 raise TypeError, "Expected a constant set, got: #{constant_set}." |

401 end |

402 |

403 if constant_set.kind_of? Range |

404 return Gecode::Raw::IntSet.new(constant_set.first, constant_set.last) |

405 elsif constant_set.kind_of? Fixnum |

406 return Gecode::Raw::IntSet.new([constant_set], 1) |

407 else |

408 constant_set = constant_set.to_a |

409 return Gecode::Raw::IntSet.new(constant_set, constant_set.size) |

410 end |

411 end |

412 |

413 # Checks whether the specified expression is regarded as a constant set. |

414 # Returns true if it is, false otherwise. |

415 def constant_set?(expression) |

416 return ( |

417 expression.kind_of?(Range) && # It's a range. |

418 expression.first.kind_of?(Fixnum) && |

419 expression.last.kind_of?(Fixnum)) || |

420 expression.kind_of?(Fixnum) || # It's a single fixnum. |

421 (expression.kind_of?(Enumerable) && # It's an enum of fixnums. |

422 expression.all?{ |e| e.kind_of? Fixnum }) |

423 end |

424 |

425 # Extracts an array of the values selected for the standard propagation |

426 # options (propagation strength and propagation kind) from the hash of |

427 # parameters given. The options are returned in the order that they are |

428 # given when posting constraints to Gecode. |

429 def extract_propagation_options(params) |

430 params.values_at(:strength, :kind) |

431 end |

432 end |

433 |

434 # A module that contains utility-methods for extensional constraints. |

435 module Util::Extensional #:nodoc: |

436 module_function |

437 |

438 # Checks that the specified enumeration is an enumeration containing |

439 # one or more tuples of the specified size. It also allows the caller |

440 # to define additional tests by providing a block, which is given each |

441 # tuple. If a test fails then an appropriate error is raised. |

442 def perform_tuple_checks(tuples, expected_size, &additional_test) |

443 unless tuples.respond_to?(:each) |

444 raise TypeError, 'Expected an enumeration with tuples, got ' + |

445 "#{tuples.class}." |

446 end |

447 |

448 if tuples.empty? |

449 raise ArgumentError, 'One or more tuples must be specified.' |

450 end |

451 |

452 tuples.each do |tuple| |

453 unless tuple.respond_to?(:each) |

454 raise TypeError, 'Expected an enumeration containing enumeraions, ' + |

455 "got #{tuple.class}." |

456 end |

457 |

458 unless tuple.size == expected_size |

459 raise ArgumentError, 'All tuples must be of the same size as the ' + |

460 'number of operands in the array.' |

461 end |

462 |

463 yield tuple |

464 end |

465 end |

466 end |

467 end |

468 |

469 require 'gecoder/interface/constraints/reifiable_constraints' |

470 require 'gecoder/interface/constraints/int_var_constraints' |

471 require 'gecoder/interface/constraints/int_enum_constraints' |

472 require 'gecoder/interface/constraints/bool_var_constraints' |

473 require 'gecoder/interface/constraints/bool_enum_constraints' |

474 require 'gecoder/interface/constraints/set_var_constraints' |

475 require 'gecoder/interface/constraints/set_enum_constraints' |

476 require 'gecoder/interface/constraints/selected_set_constraints' |

477 require 'gecoder/interface/constraints/set_elements_constraints' |

478 require 'gecoder/interface/constraints/fixnum_enum_constraints' |

479 require 'gecoder/interface/constraints/extensional_regexp' |

Generated on Thu Jan 08 13:27:03 +0100 2015 with rcov 1.0.0