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