element.c
2.81 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
119
120
121
122
123
124
125
126
127
128
129
/* element */
/* element(X, Y, k) == X[Y] = k */
static int fd_element_filter(fd_constraint this)
{
fd_int index;
int k;
int value;
int i;
// do some filtering...
index = VAR(this, this->nvariables - 1);
k = this->constants[0];
// see if the index is already fixed
if (fd_var_single(index, &value))
{
if (_fd_var_del_other(VAR(this, value), k))
{
if (fd_domain_empty(VAR(this, value)))
return FD_NOSOLUTION;
_fd_revise_connected(this, VAR(this, value));
}
fd__constraint_set_entailed(this);
return FD_OK;
}
// check which variables have k in their domain
for (i = 0; i < this->nvariables - 1; ++i)
if (!_fd_var_contains_val(VAR(this, i), k) && _fd_var_del_val(i, index))
{
if (fd_domain_empty(index))
return FD_NOSOLUTION;
_fd_revise_connected(NULL, index);
}
// the index may have become fixed
if (fd_var_single(index, &value))
{
if (_fd_var_del_other(VAR(this, value), k))
_fd_revise_connected(this, VAR(this, value));
fd__constraint_set_entailed(this);
}
return FD_OK;
}
static int fd_element_propagate2(fd_constraint this, fd_int culprit)
{
fd_int index;
int k;
int value;
int i;
// do some filtering...
// XXX: assuming that, in time, the last (index) variable's domain's
// values will all correspond to variables which have k in their
// domain
index = VAR(this, this->nvariables - 1);
k = this->constants[0];
// see if the culprit is the index variable
if (culprit == index)
{
if (fd_var_single(index, &value))
{
if (_fd_var_del_other(VAR(this, value), k))
{
if (fd_domain_empty(VAR(this, value)))
return FD_NOSOLUTION;
_fd_revise_connected(this, VAR(this, value));
}
fd__constraint_set_entailed(this);
}
return FD_OK; // XXX: there's more to be done...
}
// find which non-index variable caused the propagation
for (i = 0; culprit != VAR(this, i); ++i)
;
if (!_fd_var_contains_val(culprit, k) && _fd_var_del_val(i, index))
{
if (fd_domain_empty(index))
return FD_NOSOLUTION;
_fd_revise_connected(NULL, index);
}
return FD_OK;
}
fd_constraint fd_element(fd_int *variables, int nvariables, fd_int index, int k)
{
fd_constraint c = _fd_constraint_new(nvariables + 1, 1);
int i;
// XXX: add a constraint 0 <= INDEX < nvariables
if (c)
{
for (i = 0; i < nvariables; ++i)
c->variables[i] = FD_INT2C_VAR(variables[i]);
c->variables[nvariables] = FD_INT2C_VAR(index);
c->constants[0] = k;
#ifdef CONSTRAINT_CLASS
c->kind = FD_CONSTR_ELEMENT;
#else /* CONSTRAINT_CLASS */
c->propagator2 = fd_element_propagate2;
#endif /* CONSTRAINT_CLASS */
for (i = 0; i < c->nvariables; ++i)
_fd_var_add_constraint(VAR(c, i), c);
_fd_add_constraint(c);
}
return c;
}