Salvador Abreu / PaCCS

Blame view

src/constraints/exactly.c 2.11 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
 
/* exactly(X, c, k) == #{ x \in X | x = k } = c */

static int fd_exactly_filter(fd_constraint this)
{
  int k, c;
  int set, possible;
  int value;
  int i;

  k = this->constants[0];
  c = this->constants[1];

  set = possible = 0;

  // count the variables that are set to k and those which contain k
  // in their domain
  for (i = 0; i < this->nvariables; ++i)
    if (fd_var_single(VAR(this, i), &value))
      {
	if (value == k)
	  // if there are more than c variables set to k, fail
	  if (++set > c)
	    return FD_NOSOLUTION;
      }
    else if (_fd_var_contains_val(VAR(this, i), k))
      possible++;

  // see if it still possible to satisfy the constraint
  if (set + possible < c)
    return FD_NOSOLUTION;

  if (set + possible == c)
    {
      for (i = 0; possible > 0; ++i)
	if (!fd_var_single(VAR(this, i), NULL) &&
	    _fd_var_contains_val(VAR(this, i), k))
	  {
	    _fd_var_set_value(VAR(this, i), k);

	    possible--;

	    _fd_revise_connected(this, VAR(this, i));
	  }

      fd__constraint_set_entailed(this);

      return FD_OK;
    }

  if (set == c)
    {
      for (i = 0;  possible > 0; ++i)
	if (!fd_var_single(VAR(this, i), NULL) &&
	    _fd_var_del_val(k, VAR(this, i)))
	  {
	    possible--;

	    _fd_revise_connected(this, VAR(this, i));
	  }

      fd__constraint_set_entailed(this);

      return FD_OK;
    }

  // the constraint can still be satisfied: set < c && set + possible > c
  return FD_OK;
}

static int fd_exactly_propagate2(fd_constraint this, fd_int culprit)
{
  return fd_exactly_filter(this);
}

fd_constraint fd_exactly(fd_int *variables, int nvariables, int cardinal, int k)
{
eef94371   Vasco Pedro   Update to PaCCS v... 
77
 
  fd_constraint c = _fd_constraint_new(nvariables, 2);
965dadaa   Salvador Abreu   initial commit fr... 
78
79
80
81
82
83
84
85
 
  int i;

  if (c)
    {
      for (i = 0; i < nvariables; ++i)
	c->variables[i] = FD_INT2C_VAR(variables[i]);
      c->constants[0] = k;
      c->constants[1] = cardinal;
eef94371   Vasco Pedro   Update to PaCCS v... 
86
 
#ifdef CONSTRAINT_CLASS
965dadaa   Salvador Abreu   initial commit fr... 
87
 
      c->kind = FD_CONSTR_EXACTLY;
965dadaa   Salvador Abreu   initial commit fr... 
88
89
90
91
92
93
94
95
96
 
#else /* CONSTRAINT_CLASS */
      c->propagator2 = fd_exactly_propagate2;
#endif /* CONSTRAINT_CLASS */

      for (i = 0; i < nvariables; ++i)
	_fd_var_add_constraint(VAR(c, i), c);

      _fd_add_constraint(c);
    }