Salvador Abreu / PaCCS

Blame view

src/constraints/var-eq-minus.c 4.96 KB
Edit Raw Normal View History Permalink
eef94371   Vasco Pedro   Update to PaCCS v... 
1
 
/* x = y - z */
965dadaa   Salvador Abreu   initial commit fr... 
2
3
4
5
6
7
8
9
10
11
12
 

static int fd_var_eq_minus_filter(fd_constraint this)
{
  fd_int x, y, z;
  int xmin, xmax, ymin, ymax, zmin, zmax;
  int changed_x, changed_y, changed_z;

  x = VAR(this, 0);
  y = VAR(this, 1);
  z = VAR(this, 2);
eef94371   Vasco Pedro   Update to PaCCS v... 
13
 
  // bounds consistency
965dadaa   Salvador Abreu   initial commit fr... 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 

  xmin = _fd_var_min(x);
  xmax = _fd_var_max(x);

  zmin = _fd_var_min(z);
  zmax = _fd_var_max(z);

  changed_y = _fd_var_del_lt(xmin + zmin, y) | _fd_var_del_gt(xmax + zmax, y);

  if (changed_y)
    {
      if (fd_domain_empty(y))
	return FD_NOSOLUTION;

      _fd_revise_connected(NULL, y);
    }
eef94371   Vasco Pedro   Update to PaCCS v... 
31
32
33
34
35
36
37
38
39
 
#ifndef DISABLE_ENTAILED
  if ((xmin == xmax) + (zmin == zmax) == 2)
    {
      fd__constraint_set_entailed(this);

      return FD_OK;
    }
#endif
965dadaa   Salvador Abreu   initial commit fr... 
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
 
  ymin = _fd_var_min(y);
  ymax = _fd_var_max(y);

  changed_z = _fd_var_del_lt(ymin - xmax, z) | _fd_var_del_gt(ymax - xmin, z);

  if (changed_z)
    {
      if (fd_domain_empty(z))
	return FD_NOSOLUTION;

      _fd_revise_connected(NULL, z);

      zmin = _fd_var_min(z);
      zmax = _fd_var_max(z);
    }

  changed_x = _fd_var_del_lt(ymin - zmax, x) | _fd_var_del_gt(ymax - zmin, x);

  if (changed_x)
    {
      if (fd_domain_empty(x))
	return FD_NOSOLUTION;

      _fd_revise_connected(NULL, x);
    }
eef94371   Vasco Pedro   Update to PaCCS v... 
66
67
 
#ifndef DISABLE_ENTAILED
  if ((ymin == ymax) + (zmin == zmax) == 2)
965dadaa   Salvador Abreu   initial commit fr... 
68
69
70
71
72
73
 
    fd__constraint_set_entailed(this);
#endif

  return FD_OK;
}
eef94371   Vasco Pedro   Update to PaCCS v... 
74
 
static int fd_var_eq_minus_propagate2(fd_constraint this, fd_int culprit)
965dadaa   Salvador Abreu   initial commit fr... 
75
76
 
{
  fd_int x, y, z;
eef94371   Vasco Pedro   Update to PaCCS v... 
77
 
  int xmin, xmax, ymin, ymax, zmin, zmax;
965dadaa   Salvador Abreu   initial commit fr... 
78
79
80
81
82
83
 
  int changed_x = 0, changed_y = 0, changed_z = 0;

  x = VAR(this, 0);
  y = VAR(this, 1);
  z = VAR(this, 2);
eef94371   Vasco Pedro   Update to PaCCS v... 
84
 
  // bounds consistency
965dadaa   Salvador Abreu   initial commit fr... 
85
86
87
 

  if (culprit == x)
    {
eef94371   Vasco Pedro   Update to PaCCS v... 
88
89
 
      xmin = _fd_var_min(x);
      xmax = _fd_var_max(x);
965dadaa   Salvador Abreu   initial commit fr... 
90
eef94371   Vasco Pedro   Update to PaCCS v... 
91
92
93
94
95
96
97
98
99
100
101
102
103
 
      changed_y = _fd_var_del_lt(xmin + _fd_var_min(z), y) |
	_fd_var_del_gt(xmax + _fd_var_max(z), y);

      if (changed_y)
	{
	  if (fd_domain_empty(y))
	    return FD_NOSOLUTION;

	  _fd_revise_connected(NULL, y);	// XXX: NULL or this?
	}

      ymin = _fd_var_min(y);
      ymax = _fd_var_max(y);
965dadaa   Salvador Abreu   initial commit fr... 
104
105
 

      changed_z =
eef94371   Vasco Pedro   Update to PaCCS v... 
106
 
	_fd_var_del_lt(ymin - xmax, z) | _fd_var_del_gt(ymax - xmin, z);
965dadaa   Salvador Abreu   initial commit fr... 
107
eef94371   Vasco Pedro   Update to PaCCS v... 
108
109
110
111
112
113
114
 
      if (changed_z)
	{
	  if (fd_domain_empty(z))
	    return FD_NOSOLUTION;

	  _fd_revise_connected(NULL, z);	// XXX: NULL or this?
	}
965dadaa   Salvador Abreu   initial commit fr... 
115
116
117
 
    }
  else if (culprit == y)
    {
eef94371   Vasco Pedro   Update to PaCCS v... 
118
119
 
      ymin = _fd_var_min(y);
      ymax = _fd_var_max(y);
965dadaa   Salvador Abreu   initial commit fr... 
120
eef94371   Vasco Pedro   Update to PaCCS v... 
121
122
123
124
125
126
127
128
129
130
131
132
133
 
      changed_x = _fd_var_del_lt(ymin - _fd_var_max(z), x) |
	_fd_var_del_gt(ymax - _fd_var_min(z), x);

      if (changed_x)
	{
	  if (fd_domain_empty(x))
	    return FD_NOSOLUTION;

	  _fd_revise_connected(NULL, x);	// XXX: NULL or this?
	}

      xmin = _fd_var_min(x);
      xmax = _fd_var_max(x);
965dadaa   Salvador Abreu   initial commit fr... 
134
135
 

      changed_z =
eef94371   Vasco Pedro   Update to PaCCS v... 
136
 
	_fd_var_del_lt(ymin - xmax, z) | _fd_var_del_gt(ymax - xmin, z);
965dadaa   Salvador Abreu   initial commit fr... 
137
eef94371   Vasco Pedro   Update to PaCCS v... 
138
139
140
141
142
143
144
 
      if (changed_z)
	{
	  if (fd_domain_empty(z))
	    return FD_NOSOLUTION;

	  _fd_revise_connected(NULL, z);	// XXX: NULL or this?
	}
965dadaa   Salvador Abreu   initial commit fr... 
145
146
147
 
    }
  else // culprit == z
    {
eef94371   Vasco Pedro   Update to PaCCS v... 
148
149
 
      zmin = _fd_var_min(z);
      zmax = _fd_var_max(z);
965dadaa   Salvador Abreu   initial commit fr... 
150
eef94371   Vasco Pedro   Update to PaCCS v... 
151
152
 
      changed_x = _fd_var_del_lt(_fd_var_min(y) - zmax, x) |
	_fd_var_del_gt(_fd_var_max(y) - zmin, x);
965dadaa   Salvador Abreu   initial commit fr... 
153
eef94371   Vasco Pedro   Update to PaCCS v... 
154
155
156
157
 
      if (changed_x)
	{
	  if (fd_domain_empty(x))
	    return FD_NOSOLUTION;
965dadaa   Salvador Abreu   initial commit fr... 
158
eef94371   Vasco Pedro   Update to PaCCS v... 
159
160
 
	  _fd_revise_connected(NULL, x);	// XXX: NULL or this?
	}
965dadaa   Salvador Abreu   initial commit fr... 
161
eef94371   Vasco Pedro   Update to PaCCS v... 
162
163
 
      xmin = _fd_var_min(x);
      xmax = _fd_var_max(x);
965dadaa   Salvador Abreu   initial commit fr... 
164
eef94371   Vasco Pedro   Update to PaCCS v... 
165
166
 
      changed_y =
	_fd_var_del_lt(xmin + zmin, y) | _fd_var_del_gt(xmax + zmax, y);
965dadaa   Salvador Abreu   initial commit fr... 
167
eef94371   Vasco Pedro   Update to PaCCS v... 
168
169
170
171
 
      if (changed_y)
	{
	  if (fd_domain_empty(y))
	    return FD_NOSOLUTION;
965dadaa   Salvador Abreu   initial commit fr... 
172
eef94371   Vasco Pedro   Update to PaCCS v... 
173
174
175
176
177
178
179
180
181
 
	  _fd_revise_connected(NULL, y);	// XXX: NULL or this?
	}

      ymin = zmin + xmin;
      ymax = zmax + xmax;
    }

#ifndef DISABLE_ENTAILED
  if ((xmin == xmax) + (ymin == ymax) == 2)
965dadaa   Salvador Abreu   initial commit fr... 
182
183
184
185
186
187
 
    fd__constraint_set_entailed(this);
#endif

  return FD_OK;
}
eef94371   Vasco Pedro   Update to PaCCS v... 
188
 
static int fd_var_eq_minus_propagate(fd_constraint this, fd_int revise)
965dadaa   Salvador Abreu   initial commit fr... 
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
{
  fd_int x, y, z;
  int changed;

  x = VAR(this, 0);
  y = VAR(this, 1);
  z = VAR(this, 2);

  // XXX: just do bounds consistency, for now

  if (revise == x)
    {
      changed =
	_fd_var_del_lt(_fd_var_min(y) - _fd_var_max(z), revise);
      changed |=
	_fd_var_del_gt(_fd_var_max(y) - _fd_var_min(z), revise);
    }
  else if (revise == y)
    {
      changed =
	_fd_var_del_lt(_fd_var_min(x) + _fd_var_min(z), revise);
      changed |=
	_fd_var_del_gt(_fd_var_max(x) + _fd_var_max(z), revise);
    }
  else // revise == z
    {
      changed =
	_fd_var_del_lt(_fd_var_min(y) - _fd_var_max(x), revise);
      changed |=
	_fd_var_del_gt(_fd_var_max(y) - _fd_var_min(x), revise);
    }

  if (changed && fd_domain_empty(revise))
    return FD_NOSOLUTION;

  // XXX: enqueue further updates here?
  if (changed)
    _fd_revise_connected(this, revise);

  return FD_OK;
}

fd_constraint fd_var_eq_minus(fd_int x, fd_int y, fd_int z)
{
eef94371   Vasco Pedro   Update to PaCCS v... 
233
 
  fd_constraint c = fd__constraint_new(3, 0);
965dadaa   Salvador Abreu   initial commit fr... 
234
235
236
237
238
239
 

  if (c)
    {
      c->variables[0] = FD_INT2C_VAR(x);
      c->variables[1] = FD_INT2C_VAR(y);
      c->variables[2] = FD_INT2C_VAR(z);
eef94371   Vasco Pedro   Update to PaCCS v... 
240
965dadaa   Salvador Abreu   initial commit fr... 
241
 
      c->kind = FD_CONSTR_VAR_EQ_MINUS;
965dadaa   Salvador Abreu   initial commit fr... 
242
243
244
245
246
247
248
249
250
251
 

      _fd_var_add_constraint(x, c);
      _fd_var_add_constraint(y, c);
      _fd_var_add_constraint(z, c);

      _fd_add_constraint(c);
    }

  return c;
}