main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:30 for Gecode by
doxygen
1.8.4
gecode
minimodel
float-expr.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Vincent Barichard <Vincent.Barichard@univ-angers.fr>
5
*
6
* Copyright:
7
* Vincent Barichard, 2012
8
*
9
* Last modified:
10
* $Date: 2013-03-11 14:47:11 +0100 (Mon, 11 Mar 2013) $ by $Author: schulte $
11
* $Revision: 13490 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <
gecode/minimodel.hh
>
39
40
#ifdef GECODE_HAS_FLOAT_VARS
41
42
#include <
gecode/float/linear.hh
>
43
44
namespace
Gecode {
45
47
class
LinFloatExpr::Node
{
48
public
:
50
unsigned
int
use
;
52
int
n_float
;
54
NodeType
t
;
56
Node
*
l
, *
r
;
58
union
{
60
Float::Linear::Term
*
tf
;
62
NonLinFloatExpr
*
ne
;
63
}
sum
;
65
FloatVal
a
,
c
;
67
FloatVar
x_float
;
69
Node
(
void
);
71
GECODE_MINIMODEL_EXPORT
72
void
fill
(
Home
home,
Float::Linear::Term
*&
tf
,
73
FloatVal
m,
FloatVal
&
d
)
const
;
75
FloatVal
fill
(
Home
home,
Float::Linear::Term
*
tf
)
const
;
77
bool
decrement
(
void
);
79
~Node
(
void
);
81
static
void
*
operator
new
(
size_t
size
);
83
static
void
operator
delete
(
void
*
p
,
size_t
size
);
84
85
};
86
87
/*
88
* Operations for nodes
89
*
90
*/
91
forceinline
92
LinFloatExpr::Node::Node
(
void
) : use(1) {
93
}
94
95
forceinline
96
LinFloatExpr::Node::~Node
(
void
) {
97
switch
(
t
) {
98
case
NT_SUM
:
99
if
(n_float > 0)
100
heap
.
free
<
Float::Linear::Term
>(
sum
.tf,n_float);
101
break
;
102
case
NT_NONLIN
:
103
delete
sum
.ne;
104
break
;
105
default
: ;
106
}
107
}
108
109
forceinline
void
*
110
LinFloatExpr::Node::operator
new
(
size_t
size
) {
111
return
heap
.
ralloc
(
size
);
112
}
113
114
forceinline
void
115
LinFloatExpr::Node::operator
delete
(
void
*
p
, size_t) {
116
heap
.
rfree
(
p
);
117
}
118
119
bool
120
LinFloatExpr::Node::decrement
(
void
) {
121
if
(--use == 0) {
122
if
((
l
!= NULL) &&
l
->decrement())
123
delete
l
;
124
if
((
r
!= NULL) &&
r
->decrement())
125
delete
r
;
126
return
true
;
127
}
128
return
false
;
129
}
130
131
/*
132
* Operations for float expressions
133
*
134
*/
135
136
LinFloatExpr::LinFloatExpr
(
const
LinFloatExpr
& e)
137
: n(e.n) {
138
n->
use
++;
139
}
140
141
NonLinFloatExpr
*
142
LinFloatExpr::nlfe
(
void
)
const
{
143
return
n->
t
==
NT_NONLIN
? n->
sum
.
ne
: NULL;
144
}
145
146
FloatVal
147
LinFloatExpr::Node::fill
(
Home
home,
148
Float::Linear::Term
* tf)
const
{
149
FloatVal
d
=0;
150
fill
(home,tf,1.0,d);
151
Float::Limits::check
(d,
"MiniModel::LinFloatExpr"
);
152
return
d
;
153
}
154
155
void
156
LinFloatExpr::post
(
Home
home,
FloatRelType
frt)
const
{
157
if
(home.
failed
())
return
;
158
Region
r
(home);
159
if
(n->
t
==
NT_ADD
&& n->
l
== NULL && n->
r
->
t
==
NT_NONLIN
) {
160
n->
r
->
sum
.
ne
->
post
(home,frt,-n->
c
);
161
}
else
if
(n->
t
==
NT_SUB
&& n->
r
->
t
==
NT_NONLIN
&& n->
l
==NULL) {
162
switch
(frt) {
163
case
FRT_LQ
: frt=
FRT_GQ
;
break
;
164
case
FRT_GQ
: frt=
FRT_LQ
;
break
;
165
default
:
break
;
166
}
167
n->
r
->
sum
.
ne
->
post
(home,frt,n->
c
);
168
}
else
if
(frt==
FRT_EQ
&&
169
n->
t
==
NT_SUB
&& n->
r
->
t
==
NT_NONLIN
&&
170
n->
l
!= NULL && n->
l
->
t
==
NT_VAR
171
&& n->
l
->
a
==1) {
172
(void) n->
r
->
sum
.
ne
->
post
(home,&n->
l
->
x_float
);
173
}
else
if
(frt==
FRT_EQ
&&
174
n->
t
==
NT_SUB
&& n->
r
->
t
==
NT_VAR
&&
175
n->
l
!= NULL && n->
l
->
t
==
NT_NONLIN
176
&& n->
r
->
a
==1) {
177
(void) n->
l
->
sum
.
ne
->
post
(home,&n->
r
->
x_float
);
178
}
else
{
179
Float::Linear::Term
* fts =
180
r.
alloc
<
Float::Linear::Term
>(n->
n_float
);
181
FloatVal
c
= n->
fill
(home,fts);
182
Float::Linear::post
(home, fts, n->
n_float
, frt, -c);
183
}
184
}
185
186
void
187
LinFloatExpr::post
(
Home
home,
FloatRelType
frt,
const
BoolVar
&
b
)
const
{
188
if
(home.
failed
())
return
;
189
Region
r
(home);
190
if
(n->
t
==
NT_ADD
&& n->
l
==NULL && n->
r
->
t
==
NT_NONLIN
) {
191
n->
r
->
sum
.
ne
->
post
(home,frt,-n->
c
,b);
192
}
else
if
(n->
t
==
NT_SUB
&& n->
l
==NULL && n->
r
->
t
==
NT_NONLIN
) {
193
switch
(frt) {
194
case
FRT_LQ
: frt=
FRT_GQ
;
break
;
195
case
FRT_LE
: frt=
FRT_GR
;
break
;
196
case
FRT_GQ
: frt=
FRT_LQ
;
break
;
197
case
FRT_GR
: frt=
FRT_LE
;
break
;
198
default
:
break
;
199
}
200
n->
r
->
sum
.
ne
->
post
(home,frt,n->
c
,b);
201
}
else
{
202
Float::Linear::Term
* fts =
203
r.
alloc
<
Float::Linear::Term
>(n->
n_float
);
204
FloatVal
c
= n->
fill
(home,fts);
205
Float::Linear::post
(home, fts, n->
n_float
, frt, -c, b);
206
}
207
208
}
209
210
FloatVar
211
LinFloatExpr::post
(
Home
home)
const
{
212
if
(home.
failed
())
return
FloatVar
(home,0,0);
213
Region
r
(home);
214
Float::Linear::Term
* fts =
215
r.
alloc
<
Float::Linear::Term
>(n->
n_float
+1);
216
FloatVal
c
= n->
fill
(home,fts);
217
if
((n->
n_float
== 1) && (c == 0) && (fts[0].
a
== 1))
218
return
fts[0].
x
;
219
FloatNum
min
,
max
;
220
Float::Linear::estimate
(&fts[0],n->
n_float
,c,min,max);
221
FloatVar
x
(home, min, max);
222
fts[n->
n_float
].
x
=
x
; fts[n->
n_float
].
a
= -1;
223
Float::Linear::post
(home, fts, n->
n_float
+1,
FRT_EQ
, -c);
224
return
x
;
225
226
}
227
228
LinFloatExpr::LinFloatExpr
(
void
) :
229
n(new
Node
) {
230
n->
n_float
= 0;
231
n->
t
=
NT_VAR
;
232
n->
l
= n->
r
= NULL;
233
n->
a
= 0;
234
}
235
236
LinFloatExpr::LinFloatExpr
(
const
FloatVal
&
c
) :
237
n
(new
Node
) {
238
n->
n_float
= 0;
239
n->
t
=
NT_CONST
;
240
n->
l
= n->
r
= NULL;
241
n->
a
= 0;
242
Float::Limits::check
(c,
"MiniModel::LinFloatExpr"
);
243
n->
c
=
c
;
244
}
245
246
LinFloatExpr::LinFloatExpr
(
const
FloatVar
&
x
) :
247
n
(new
Node
) {
248
n->
n_float
= 1;
249
n->
t
=
NT_VAR
;
250
n->
l
= n->
r
= NULL;
251
n->
a
= 1.0;
252
n->
x_float
=
x
;
253
}
254
255
LinFloatExpr::LinFloatExpr
(
const
FloatVar
&
x
,
FloatVal
a
) :
256
n
(new
Node
) {
257
n->
n_float
= 1;
258
n->
t
=
NT_VAR
;
259
n->
l
= n->
r
= NULL;
260
n->
a
=
a
;
261
n->
x_float
=
x
;
262
}
263
264
LinFloatExpr::LinFloatExpr
(
const
FloatVarArgs
&
x
) :
265
n
(new
Node
) {
266
n->
n_float
= x.
size
();
267
n->
t
=
NT_SUM
;
268
n->
l
= n->
r
= NULL;
269
if
(x.
size
() > 0) {
270
n->
sum
.
tf
=
heap
.
alloc
<
Float::Linear::Term
>(x.
size
());
271
for
(
int
i
=x.
size
();
i
--; ) {
272
n->
sum
.
tf
[
i
].
x
= x[
i
];
273
n->
sum
.
tf
[
i
].
a
= 1.0;
274
}
275
}
276
}
277
278
LinFloatExpr::LinFloatExpr
(
const
FloatValArgs
&
a
,
const
FloatVarArgs
&
x
) :
279
n
(new
Node
) {
280
if
(a.
size
() != x.
size
())
281
throw
Float::ArgumentSizeMismatch
(
"MiniModel::LinFloatExpr"
);
282
n->
n_float
= x.
size
();
283
n->
t
=
NT_SUM
;
284
n->
l
= n->
r
= NULL;
285
if
(x.
size
() > 0) {
286
n->
sum
.
tf
=
heap
.
alloc
<
Float::Linear::Term
>(x.
size
());
287
for
(
int
i
=x.
size
();
i
--; ) {
288
n->
sum
.
tf
[
i
].
x
= x[
i
];
289
n->
sum
.
tf
[
i
].
a
= a[
i
];
290
}
291
}
292
}
293
294
LinFloatExpr::LinFloatExpr
(
const
LinFloatExpr
& e0,
NodeType
t
,
const
LinFloatExpr
& e1) :
295
n
(new
Node
) {
296
n->
n_float
= e0.n->
n_float
+ e1.n->
n_float
;
297
n->
t
=
t
;
298
n->
l
= e0.n; n->
l
->
use
++;
299
n->
r
= e1.n; n->
r
->
use
++;
300
}
301
302
LinFloatExpr::LinFloatExpr
(
const
LinFloatExpr
& e,
NodeType
t
,
const
FloatVal
&
c
) :
303
n
(new
Node
) {
304
n->
n_float
= e.n->
n_float
;
305
n->
t
=
t
;
306
n->
l
= NULL;
307
n->
r
= e.n; n->
r
->
use
++;
308
n->
c
=
c
;
309
}
310
311
LinFloatExpr::LinFloatExpr
(
FloatVal
a
,
const
LinFloatExpr
& e) :
312
n
(new
Node
) {
313
n->
n_float
= e.n->
n_float
;
314
n->
t
=
NT_MUL
;
315
n->
l
= e.n; n->
l
->
use
++;
316
n->
r
= NULL;
317
n->
a
=
a
;
318
}
319
320
LinFloatExpr::LinFloatExpr
(
NonLinFloatExpr
* e) :
321
n
(new
Node
) {
322
n->
n_float
= 1;
323
n->
t
=
NT_NONLIN
;
324
n->
l
= n->
r
= NULL;
325
n->
a
= 0;
326
n->
sum
.
ne
= e;
327
}
328
329
const
LinFloatExpr
&
330
LinFloatExpr::operator =
(
const
LinFloatExpr
& e) {
331
if
(
this
!= &e) {
332
if
(n->
decrement
())
333
delete
n;
334
n = e.n; n->
use
++;
335
}
336
return
*
this
;
337
}
338
339
LinFloatExpr::~LinFloatExpr
(
void
) {
340
if
(n->
decrement
())
341
delete
n;
342
}
343
344
345
void
346
LinFloatExpr::Node::fill
(
Home
home,
347
Float::Linear::Term
*& tf,
348
FloatVal
m,
FloatVal
&
d
)
const
{
349
switch
(this->
t
) {
350
case
NT_CONST
:
351
Float::Limits::check
(m*
c
,
"MiniModel::LinFloatExpr"
);
352
d += m*
c
;
353
break
;
354
case
NT_VAR
:
355
Float::Limits::check
(m*
a
,
"MiniModel::LinFloatExpr"
);
356
tf->
a
=m*
a
; tf->
x
=
x_float
; tf++;
357
break
;
358
case
NT_NONLIN
:
359
tf->
a
=m; tf->
x
=
sum
.ne->post(home, NULL); tf++;
360
break
;
361
case
NT_SUM
:
362
for
(
int
i
=
n_float
;
i
--; ) {
363
Float::Limits::check
(m*
sum
.tf[
i
].a,
"MiniModel::LinFloatExpr"
);
364
tf[
i
].
x
=
sum
.tf[
i
].x; tf[
i
].
a
= m*
sum
.tf[
i
].a;
365
}
366
tf +=
n_float
;
367
break
;
368
case
NT_ADD
:
369
if
(
l
== NULL) {
370
Float::Limits::check
(m*c,
"MiniModel::LinFloatExpr"
);
371
d += m*
c
;
372
}
else
{
373
l
->
fill
(home,tf,m,d);
374
}
375
r
->
fill
(home,tf,m,d);
376
break
;
377
case
NT_SUB
:
378
if
(
l
== NULL) {
379
Float::Limits::check
(m*c,
"MiniModel::LinFloatExpr"
);
380
d += m*
c
;
381
}
else
{
382
l
->
fill
(home,tf,m,d);
383
}
384
r
->
fill
(home,tf,-m,d);
385
break
;
386
case
NT_MUL
:
387
Float::Limits::check
(m*a,
"MiniModel::LinFloatExpr"
);
388
l
->
fill
(home,tf,m*a,d);
389
break
;
390
default
:
391
GECODE_NEVER
;
392
}
393
}
394
395
396
/*
397
* Operators
398
*
399
*/
400
LinFloatExpr
401
operator +
(
const
FloatVal
&
c
,
const
FloatVar
&
x
) {
402
if
(x.
assigned
() &&
Float::Limits::valid
(c+x.
val
()))
403
return
LinFloatExpr
(c+x.
val
());
404
else
405
return
LinFloatExpr
(x,
LinFloatExpr::NT_ADD
,c);
406
}
407
LinFloatExpr
408
operator +
(
const
FloatVal
&
c
,
const
LinFloatExpr
& e) {
409
return
LinFloatExpr
(e,
LinFloatExpr::NT_ADD
,c);
410
}
411
LinFloatExpr
412
operator +
(
const
FloatVar
&
x
,
const
FloatVal
&
c
) {
413
if
(x.
assigned
() &&
Float::Limits::valid
(c+x.
val
()))
414
return
LinFloatExpr
(c+x.
val
());
415
else
416
return
LinFloatExpr
(x,
LinFloatExpr::NT_ADD
,c);
417
}
418
LinFloatExpr
419
operator +
(
const
LinFloatExpr
& e,
const
FloatVal
&
c
) {
420
return
LinFloatExpr
(e,
LinFloatExpr::NT_ADD
,c);
421
}
422
LinFloatExpr
423
operator +
(
const
FloatVar
&
x
,
const
FloatVar
& y) {
424
if
(x.
assigned
())
425
return
x.
val
() + y;
426
else
if
(y.
assigned
())
427
return
x + y.
val
();
428
else
429
return
LinFloatExpr
(x,
LinFloatExpr::NT_ADD
,(
const
LinFloatExpr
&)y);
430
}
431
LinFloatExpr
432
operator +
(
const
FloatVar
&
x
,
const
LinFloatExpr
& e) {
433
if
(x.
assigned
())
434
return
x.
val
() + e;
435
else
436
return
LinFloatExpr
(x,
LinFloatExpr::NT_ADD
,e);
437
}
438
LinFloatExpr
439
operator +
(
const
LinFloatExpr
& e,
const
FloatVar
&
x
) {
440
if
(x.
assigned
())
441
return
e + x.
val
();
442
else
443
return
LinFloatExpr
(e,
LinFloatExpr::NT_ADD
,(
const
LinFloatExpr
&)x);
444
}
445
LinFloatExpr
446
operator +
(
const
LinFloatExpr
& e1,
const
LinFloatExpr
& e2) {
447
return
LinFloatExpr
(e1,
LinFloatExpr::NT_ADD
,e2);
448
}
449
450
LinFloatExpr
451
operator -
(
const
FloatVal
&
c
,
const
FloatVar
&
x
) {
452
if
(x.
assigned
() &&
Float::Limits::valid
(c-x.
val
()))
453
return
LinFloatExpr
(c-x.
val
());
454
else
455
return
LinFloatExpr
(x,
LinFloatExpr::NT_SUB
,c);
456
}
457
LinFloatExpr
458
operator -
(
const
FloatVal
&
c
,
const
LinFloatExpr
& e) {
459
return
LinFloatExpr
(e,
LinFloatExpr::NT_SUB
,c);
460
}
461
LinFloatExpr
462
operator -
(
const
FloatVar
&
x
,
const
FloatVal
&
c
) {
463
if
(x.
assigned
() &&
Float::Limits::valid
(x.
val
()-
c
))
464
return
LinFloatExpr
(x.
val
()-
c
);
465
else
466
return
LinFloatExpr
(x,
LinFloatExpr::NT_ADD
,-c);
467
}
468
LinFloatExpr
469
operator -
(
const
LinFloatExpr
& e,
const
FloatVal
&
c
) {
470
return
LinFloatExpr
(e,
LinFloatExpr::NT_ADD
,-c);
471
}
472
LinFloatExpr
473
operator -
(
const
FloatVar
&
x
,
const
FloatVar
& y) {
474
if
(x.
assigned
())
475
return
x.
val
() - y;
476
else
if
(y.
assigned
())
477
return
x - y.
val
();
478
else
479
return
LinFloatExpr
(x,
LinFloatExpr::NT_SUB
,(
const
LinFloatExpr
&)y);
480
}
481
LinFloatExpr
482
operator -
(
const
FloatVar
&
x
,
const
LinFloatExpr
& e) {
483
if
(x.
assigned
())
484
return
x.
val
() - e;
485
else
486
return
LinFloatExpr
(x,
LinFloatExpr::NT_SUB
,e);
487
}
488
LinFloatExpr
489
operator -
(
const
LinFloatExpr
& e,
const
FloatVar
&
x
) {
490
if
(x.
assigned
())
491
return
e - x.
val
();
492
else
493
return
LinFloatExpr
(e,
LinFloatExpr::NT_SUB
,(
const
LinFloatExpr
&)x);
494
}
495
LinFloatExpr
496
operator -
(
const
LinFloatExpr
& e1,
const
LinFloatExpr
& e2) {
497
return
LinFloatExpr
(e1,
LinFloatExpr::NT_SUB
,e2);
498
}
499
500
LinFloatExpr
501
operator -
(
const
FloatVar
&
x
) {
502
if
(x.
assigned
())
503
return
LinFloatExpr
(-x.
val
());
504
else
505
return
LinFloatExpr
(x,
LinFloatExpr::NT_SUB
,0);
506
}
507
LinFloatExpr
508
operator -
(
const
LinFloatExpr
& e) {
509
return
LinFloatExpr
(e,
LinFloatExpr::NT_SUB
,0);
510
}
511
512
LinFloatExpr
513
operator *
(
const
FloatVal
&
a
,
const
FloatVar
&
x
) {
514
if
(a == 0)
515
return
LinFloatExpr
(0.0);
516
else
if
(x.
assigned
() &&
517
Float::Limits::valid
(a*x.
val
()))
518
return
LinFloatExpr
(a*x.
val
());
519
else
520
return
LinFloatExpr
(x,a);
521
}
522
LinFloatExpr
523
operator *
(
const
FloatVar
&
x
,
const
FloatVal
&
a
) {
524
if
(a == 0)
525
return
LinFloatExpr
(0.0);
526
else
if
(x.
assigned
() &&
527
Float::Limits::valid
(a*x.
val
()))
528
return
LinFloatExpr
(a*x.
val
());
529
else
530
return
LinFloatExpr
(x,a);
531
}
532
LinFloatExpr
533
operator *
(
const
LinFloatExpr
& e,
const
FloatVal
&
a
) {
534
if
(a == 0)
535
return
LinFloatExpr
(0.0);
536
else
537
return
LinFloatExpr
(a,e);
538
}
539
LinFloatExpr
540
operator *
(
const
FloatVal
&
a
,
const
LinFloatExpr
& e) {
541
if
(a == 0)
542
return
LinFloatExpr
(0.0);
543
else
544
return
LinFloatExpr
(a,e);
545
}
546
547
LinFloatExpr
548
sum
(
const
FloatVarArgs
&
x
) {
549
return
LinFloatExpr
(x);
550
}
551
LinFloatExpr
552
sum
(
const
FloatValArgs
&
a
,
const
FloatVarArgs
&
x
) {
553
return
LinFloatExpr
(a,x);
554
}
555
556
FloatVar
557
expr
(
Home
home,
const
LinFloatExpr
& e) {
558
if
(!home.
failed
())
559
return
e.
post
(home);
560
FloatVar
x
(home,
Float::Limits::min
,
Float::Limits::max
);
561
return
x
;
562
}
563
564
}
565
566
#endif
567
568
// STATISTICS: minimodel-any