Salvador Abreu / PaCCS

Blame view

src/constraints/sum2.c 2.32 KB
Edit Raw Normal View History
965dadaa   Salvador Abreu   initial commit fr... 
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
 
/* 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)
{
eef94371   Vasco Pedro   Update to PaCCS v... 
97
 
  fd_constraint c = _fd_constraint_new(nvariables + 1, 0);
965dadaa   Salvador Abreu   initial commit fr... 
98
99
100
101
102
103
104
 
  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);
eef94371   Vasco Pedro   Update to PaCCS v... 
105
 
#ifdef CONSTRAINT_CLASS
965dadaa   Salvador Abreu   initial commit fr... 
106
 
      c->kind = FD_CONSTR_SUM2;
965dadaa   Salvador Abreu   initial commit fr... 
107
108
109
110
111
112
113
114
115
 
#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);
    }