Salvador Abreu / PaCCS

Blame view

src/constraints/element.c 2.81 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
97
98
99
100
101
102
103
104
 
/* 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)
{
eef94371   Vasco Pedro   Update to PaCCS v... 
105
 
  fd_constraint c = _fd_constraint_new(nvariables + 1, 1);
965dadaa   Salvador Abreu   initial commit fr... 
106
107
108
109
110
111
112
113
114
115
 
  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;
eef94371   Vasco Pedro   Update to PaCCS v... 
116
 
#ifdef CONSTRAINT_CLASS
965dadaa   Salvador Abreu   initial commit fr... 
117
 
      c->kind = FD_CONSTR_ELEMENT;
965dadaa   Salvador Abreu   initial commit fr... 
118
119
120
121
122
123
124
125
126
 
#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);
    }