1/* BEGIN LICENSE BLOCK
2 * Version: CMPL 1.1
3 *
4 * The contents of this file are subject to the Cisco-style Mozilla Public
5 * License Version 1.1 (the "License"); you may not use this file except
6 * in compliance with the License.  You may obtain a copy of the License
7 * at www.eclipse-clp.org/license.
8 *
9 * Software distributed under the License is distributed on an "AS IS"
10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11 * the License for the specific language governing rights and limitations
12 * under the License.
13 *
14 * The Original Code is  The ECLiPSe Constraint Logic Programming System.
15 * The Initial Developer of the Original Code is  Cisco Systems, Inc.
16 * Portions created by the Initial Developer are
17 * Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
18 *
19 * Contributor(s): Pascal Brisset
20 *
21 * END LICENSE BLOCK */
22// $Id: ec2il.cc,v 1.1 2006/09/23 01:54:04 snovello Exp $
23
24#define EC2IL_CC
25#include <string.h>
26#include <ilsolver/ilcpath.h>
27#include "ec2il.h"
28#include "stdecil.h"
29#include "classes.h"
30#include "outof.h"
31
32long
33EC_long(EC_word t)
34{
35  long e;
36  int x = t.is_long(&e);
37  Assert(x == EC_succeed, "EC_long");
38  return e;
39}
40
41inline int
42EC_functor_size(EC_word table)
43{
44  EC_functor f;
45  int x = table.functor(&f);
46  Assert(x == EC_succeed, "EC_functor_size");
47  return f.arity();
48}
49
50IlcBool
51binary_functor(EC_word e, EC_functor *f)
52{
53  return (e.functor(f) == EC_succeed  && f->arity() == 2);
54}
55
56IlcIntVar
57var_or_int(EC_word w)
58{
59  IlcInt i;
60  IlcIntVar v;
61
62  if (w.is_long(&i) == EC_succeed) {
63    return IlcIntVar(m, i, i);
64  } else if (w.is_handle(intvar_method, (void**)&v) == EC_succeed) {
65    return v;
66  }
67  // var or int expected in var_or_int()
68  throw Ec2ilException();
69}
70
71IlcIntVarArray
72array_of_list(EC_word list)
73{
74  // compute the length of the list
75  int size=0;
76  EC_word p = list;
77  while (p.is_nil() != EC_succeed) {
78    EC_word head, tail;
79    if (p.is_list(head, tail) == EC_succeed) {
80      size++;
81    } else {
82      // Bad argument in sum/1, must be a cons
83      throw Ec2ilException();
84    }
85    p = tail;
86  } // size computed
87
88  IlcIntVarArray array(m, size);
89
90  // Store the variables or integers from the list in the array
91  p = list;
92  int index;
93  for(index = 0; index < size; index++) {
94    EC_word head, tail;
95    p.is_list(head, tail); // No checks (done in the previous loop)
96    array[index] = var_or_int(head);
97    p = tail;
98  } // array initialized
99
100  return array;
101}
102
103IlcIntArray
104int_array_of_list(EC_word list)
105{
106  // compute the length of the list
107  int size=0;
108  EC_word p = list;
109  while (p.is_nil() != EC_succeed) {
110    EC_word head, tail;
111    if (p.is_list(head, tail) == EC_succeed) {
112      size++;
113    } else {
114      // Bad argument in sum/1, must be a cons
115      throw Ec2ilException();
116    }
117    p = tail;
118  } // size computed
119
120  IlcIntArray array(m, size);
121
122  // Store the integers from the list in the array
123  p = list;
124  int index;
125  for(index = 0; index < size; index++) {
126    EC_word head, tail;
127    p.is_list(head, tail); // No checks (done in the previous loop)
128    IlcInt n;
129    if (head.is_long(&n) == EC_succeed) {
130      array[index] = n;
131    } else {
132      throw IsLongException();
133    }
134    p = tail;
135  } // array initialized
136
137  return array;
138}
139
140IlcIntExp
141sum(EC_word E) // The argument is a list of variables or integer
142{
143  return (IlcSum(array_of_list(EC_argument(E, 1))));
144}
145
146
147IlcIntExp
148ec2il_expr(EC_word e)
149{
150  long i;
151  IlcIntVar var;
152  EC_functor f;
153
154  if (e.functor(&f) == EC_succeed) {
155    switch (f.arity()) {
156    case 1: {
157      if (strcmp(f.name(), "sum") == 0) { // sum(of a list)
158	return sum(e);
159      }
160      // Unknown unary expression
161      throw Ec2ilException();
162    }
163    case 2: {
164      if (EC_argument(e, 1).is_long(&i) == EC_succeed) {
165	IlcIntExp arg2 = ec2il_expr(EC_argument(e, 2));
166
167	if (strcmp(f.name(), "+") == 0) { return (i + arg2); };
168	if (strcmp(f.name(), "-") == 0) { return (i - arg2); };
169	if (strcmp(f.name(), "*") == 0) { return (i * arg2); };
170	if (strcmp(f.name(), "/") == 0) { return (i / arg2); };
171
172	// Unknown binary expression
173	throw Ec2ilException();
174      } else if (EC_argument(e, 2).is_long(&i) == EC_succeed) {
175	IlcIntExp arg1 = ec2il_expr(EC_argument(e, 1));
176
177	if (strcmp(f.name(), "+") == 0) { return (arg1 + i); };
178	if (strcmp(f.name(), "-") == 0) { return (arg1 - i); };
179	if (strcmp(f.name(), "*") == 0) { return (arg1 * i); };
180	if (strcmp(f.name(), "/") == 0) { return (arg1 / i); };
181
182	// Unknown binary expression
183	throw Ec2ilException();
184      } else {
185	IlcIntExp arg1 = ec2il_expr(EC_argument(e, 1));
186      	IlcIntExp arg2 = ec2il_expr(EC_argument(e, 2));
187
188	if (strcmp(f.name(), "+") == 0) { return (arg1 + arg2); };
189	if (strcmp(f.name(), "-") == 0) { return (arg1 - arg2); };
190	if (strcmp(f.name(), "*") == 0) { return (arg1 * arg2); };
191	if (strcmp(f.name(), "/") == 0) { return (arg1 / arg2); };
192
193	// Unknown binary expression
194	throw Ec2ilException();
195      }
196    }
197    default:
198      // Unknown compound expression
199      throw Ec2ilException();
200    }
201  } else /* non compound */ if (e.is_long(&i) == EC_succeed) { // Integer
202    IlcIntExp e = (zero + i);
203    return e;
204  } else if (e.is_handle(intvar_method, (void**)&var) == EC_succeed) {// Variable
205    return var;
206  } else {
207    // Unknown integer expression
208    throw Ec2ilException();
209  }
210}
211
212IlcConstraint
213distribute(EC_word c)
214{
215  // distribute(Cards, Values, Vars, Level)
216  // if Level = 0 then IlcBasic else IlcExtended
217
218  EC_word Cards = EC_argument(c, 1);
219  EC_word Values = EC_argument(c, 2);
220  EC_word Vars = EC_argument(c, 3);
221  int nb_values = EC_functor_size(Cards);
222  int nb_vars = EC_functor_size(Vars);
223  long level; EC_argument(c, 4).is_long(&level);
224  if (nb_values != EC_functor_size(Values)) { throw Ec2ilException(); }
225
226  IlcIntVarArray cards(m, nb_values);
227  IlcIntArray values(m, nb_values);
228  IlcIntVarArray vars(m, nb_vars);
229
230  // Initialize cards and values from Cards and Values
231  for(int i = 0; i < nb_values; i++) {
232    cards[i] = var_or_int(EC_argument(Cards, i+1));
233
234    IlcInt val;
235    if (EC_argument(Values, i+1).is_long(&val) == EC_succeed) {
236      values[i] = val;
237    } else {
238      // Integers expected in array Values
239      throw Ec2ilException();
240    }
241  }
242  // Initialize vars from Vars
243  for(i = 0; i < nb_vars; i++) {
244    vars[i] = var_or_int(EC_argument(Vars, i+1));
245  }
246
247  if (level == 0) {
248    return IlcDistribute(cards, values, vars, IlcBasic);
249  } else {
250    return IlcDistribute(cards, values, vars, IlcExtended);
251  }
252}
253
254
255IlcConstraint
256element(EC_word C) // element(Index, List, Value)
257{
258  IlcIntExp arg1 = ec2il_expr(EC_argument(C,1));
259  EC_word List = EC_argument(C, 2);
260  IlcIntExp arg3 = ec2il_expr(EC_argument(C,3));
261
262  // array[0] unused (because array[arg1-1] does not propagate correctly)
263  List = list(EC_word(0L), List);
264
265  try { // Try with an array of integers
266    IlcIntArray array = int_array_of_list(List);
267    return (arg1 > 0 && array[arg1] == arg3);
268  }
269  catch (IsLongException) { // Bad luck, the List contains variables
270    IlcIntVarArray array = array_of_list(List);
271    return (arg1 > 0 && array[arg1] == arg3);
272  }
273}
274
275
276IlcConstraint
277all_diff(EC_word C, EC_functor f) // alldistinct(Table) or alldifferent(Table)
278{
279  EC_word table = EC_argument(C, 1);
280  int size = EC_functor_size(table);
281
282  IlcIntVarArray array(m, size);
283  for(int i = 0; i < size; i++) {
284    array[i] = var_or_int(EC_argument(table, i+1));
285  }
286
287  if (strcmp(f.name(), "alldistinct") == 0) {
288    return IlcAllDiff(array, IlcWhenValue);
289  }
290  if (strcmp(f.name(), "alldifferent") == 0) {
291    return IlcAllDiff(array, IlcWhenDomain);
292  }
293}
294
295class DistanceI : public IlcPathTransitI {
296  IlcFloat *_distance;
297  int _size;
298public:
299  DistanceI(EC_word, int);
300  IlcFloat transit(IlcInt i,IlcInt j) { return _distance[i*_size+j]; }
301};
302
303DistanceI::DistanceI(EC_word ArrayDistances, int size): _size(size)
304{
305  _distance = new (m.getHeap()) (IlcFloat[size*size]);
306  int i;
307
308  for(i = 1; i <= size; i++) {
309    EC_word From_i = EC_argument(ArrayDistances, i);
310    int j;
311    for(j = 1; j <= size; j++) {
312      _distance[(i-1)*size+j-1] = IlcFloat(EC_long(EC_argument(From_i, j)));
313    }
314  }
315}
316
317IlcPathTransit Distance(IlcManager m, EC_word ArrayDistances, int size)
318{
319  return new (m.getHeap()) DistanceI(ArrayDistances, size);
320}
321
322
323IlcConstraint
324path(EC_word Path) // path(NextCumulArray, ArrayDistances, MaxNbPaths, WhenEvent)
325{
326 IlcInitFloat();
327
328  EC_word NextCumulArray = EC_argument(Path, 1); // Array of couples
329  EC_word ArrayDistances = EC_argument(Path, 2); // Matrix
330  IlcInt maxNbPaths = EC_long(EC_argument(Path, 3));
331  // if WhenEvent = 0 then WhenValue else When WhenDomain
332  IlcWhenEvent whenEvent =
333    (EC_long(EC_argument(Path, 4)) == 0 ? IlcWhenValue: IlcWhenDomain);
334
335  IlcInt nbNodes = EC_functor_size(NextCumulArray);
336
337  // Construction of next and cumul
338  IlcIntVarArray next(m, nbNodes);
339  IlcFloatVarArray cumul(m, nbNodes);
340  int i;
341  for(i = 1; i <= nbNodes; i++) {
342    EC_word NextCumul = EC_argument(NextCumulArray, i);
343    EC_word Next = EC_argument(NextCumul, 1);
344    EC_word Cumul = EC_argument(NextCumul, 2);
345
346    next[i-1] = var_or_int(Next);
347    cumul[i-1] = IlcFloatVar(var_or_int(Cumul));
348  } // next and cumul initialized
349
350  // Construction of the transit function
351  IlcPathTransit transit = Distance(m, ArrayDistances, nbNodes);
352  return(IlcPath(next, cumul, transit, maxNbPaths, whenEvent));
353}
354
355IlcConstraint
356outof(EC_word Outof) // outof(Var, List), forall X in Array, Var ## X
357{
358  IlcIntVar var = var_or_int(EC_argument(Outof, 1));
359  EC_word List = EC_argument(Outof, 2);
360
361  return OutOf(var, array_of_list(List));
362}
363
364
365
366IlcConstraint
367ec2il_cstr(EC_word c)
368{
369  EC_functor f;
370
371  if (c.functor(&f) == EC_succeed) {
372    switch (f.arity()) {
373    case 1: {
374      if (strcmp(f.name(), "alldistinct") == 0 || strcmp(f.name(), "alldifferent") == 0) {
375	return all_diff(c, f);
376      } else if (strcmp(f.name(), "#\\+") == 0) { // NEGATION
377	return (! ec2il_cstr(EC_argument(c, 1)));
378      }
379
380      // Unknown unary constraint
381      throw Ec2ilException();
382    }
383    case 2: {
384      EC_word c1 = EC_argument(c,1);
385      EC_word c2 = EC_argument(c,2);
386
387      if (strcmp(f.name(), "#/\\") == 0 || strcmp(f.name(), "#\\/") == 0 ||
388	  strcmp(f.name(), "#=>") == 0 || strcmp(f.name(), "#<=>") == 0) {
389	IlcConstraint arg1 = ec2il_cstr(c1);
390	IlcConstraint arg2 = ec2il_cstr(c2);
391
392	if (strcmp(f.name(), "#/\\") == 0) { return (arg1 && arg2); };
393	if (strcmp(f.name(), "#\\/") == 0) { return (arg1 || arg2); };
394	if (strcmp(f.name(), "#=>") == 0) { return ((! arg1) || arg2); };
395	if (strcmp(f.name(), "#<=>") == 0) { return (arg1 == arg2); };
396      } else if (strcmp(f.name(), "isd") == 0) {
397	IlcIntExp arg1 = ec2il_expr(c1);
398	IlcConstraint arg2 = ec2il_cstr(c2);
399
400	return (arg1 >= 0 && arg1 <= 1 && (arg1 == 1) == arg2);
401      } else if (strcmp(f.name(), "outof") == 0) {
402	return outof(c);
403      } else { // Binary constraint on expressions
404	IlcIntExp arg1 = ec2il_expr(c1);
405	IlcIntExp arg2 = ec2il_expr(c2);
406
407	if (strcmp(f.name(), "#=") == 0) { return (arg1 == arg2); };
408	if (strcmp(f.name(), "##") == 0) { return (arg1 != arg2); };
409	if (strcmp(f.name(), "#\\=") == 0) { return (arg1 != arg2); };
410	if (strcmp(f.name(), "#>") == 0) { return (arg1 > arg2); };
411	if (strcmp(f.name(), "#<") == 0) { return (arg1 < arg2); };
412	if (strcmp(f.name(), "#>=") == 0) { return (arg1 >= arg2); };
413	if (strcmp(f.name(), "#<=") == 0) { return (arg1 <= arg2); };
414	if (strcmp(f.name(), "#>") == 0) { return (arg1 > arg2); };
415
416	// Unknown binary constraint
417	throw Ec2ilException();
418      }
419    }
420    case 3: {
421      if (strcmp(f.name(), "element") == 0) { // ELEMENT constraint
422	return element(c);
423      }
424
425      // Unknown ternary constraint
426      throw Ec2ilException();
427    }
428    case 4: {
429      if (strcmp(f.name(), "distribute") == 0) {
430	return distribute(c);
431      } else if (strcmp(f.name(), "path") == 0) {
432	return path(c);
433      }
434
435      // Unknown 4-ary constraint
436      throw Ec2ilException();
437    }
438    default: {
439      // Unknown constraint
440      throw Ec2ilException();
441    }
442    }
443  } else { // Not a compound term
444    throw Ec2ilException();
445  }
446}
447
448