sum2.c
2.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* sum2(X, x) */
#include <alloca.h>
static int fd_sum2_filter(fd_constraint this)
{
int sum = this->nvariables - 1;
int min, max;
int *mins, *maxs;
int i;
mins = alloca(this->nvariables * sizeof(int));
maxs = alloca(this->nvariables * sizeof(int));
/* do bounds filtering */
mins[sum] = _fd_var_min(VAR(this, sum));
maxs[sum] = _fd_var_max(VAR(this, sum));
// sum the minima of the summands domains
min = 0;
for (i = 0; i < this->nvariables - 1; ++i)
{
min += mins[i] = _fd_var_min(VAR(this, i));
if (min > maxs[sum])
return FD_NOSOLUTION;
}
// sum the maxima of the summands domains
max = 0;
for (i = 0; i < this->nvariables - 1; ++i)
max += maxs[i] = _fd_var_max(VAR(this, i));
if (max < mins[sum])
return FD_NOSOLUTION;
for (i = 0; i < this->nvariables - 1; ++i)
{
int changed = 0;
if (mins[i] + maxs[sum] - min < maxs[i])
{
_fd_var_del_gt(mins[i] + maxs[sum] - min, VAR(this, i));
changed = 1;
}
if (maxs[i] - (max - mins[sum]) > mins[i])
{
_fd_var_del_lt(maxs[i] - (max - mins[sum]), VAR(this, i));
changed = 1;
}
if (changed)
{
if (fd_domain_empty(VAR(this, i)))
return FD_NOSOLUTION;
_fd_revise_connected(this, VAR(this, i));
}
}
if (min > mins[sum])
{
_fd_var_del_lt(min, VAR(this, sum));
if (fd_domain_empty(VAR(this, sum)))
return FD_NOSOLUTION;
_fd_revise_connected(this, VAR(this, sum));
}
if (max < maxs[sum])
{
_fd_var_del_gt(max, VAR(this, sum));
if (fd_domain_empty(VAR(this, sum)))
return FD_NOSOLUTION;
_fd_revise_connected(this, VAR(this, sum));
}
return FD_OK;
}
static int fd_sum2_propagate2(fd_constraint this, fd_int culprit)
{
return fd_sum2_filter(this);
}
fd_constraint fd_sum2(fd_int *variables, int nvariables, fd_int x)
{
fd_constraint c = _fd_constraint_new(nvariables + 1, 0);
int i;
if (c)
{
for (i = 0; i < nvariables; ++i)
c->variables[i] = FD_INT2C_VAR(variables[i]);
c->variables[nvariables] = FD_INT2C_VAR(x);
#ifdef CONSTRAINT_CLASS
c->kind = FD_CONSTR_SUM2;
#else /* CONSTRAINT_CLASS */
c->propagator2 = fd_sum2_propagate2;
#endif /* CONSTRAINT_CLASS */
for (i = 0; i < nvariables + 1; ++i)
_fd_var_add_constraint(VAR(c, i), c);
_fd_add_constraint(c);
}
return c;
}