[0e1846] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
[8d1bbc] | 4 | /* $Id: hutil.cc,v 1.22 2003-03-11 16:48:04 Singular Exp $ */ |
---|
[0e1846] | 5 | /* |
---|
| 6 | * ABSTRACT: Utilities for staircase operations |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | #include "mod2.h" |
---|
| 10 | #include "tok.h" |
---|
| 11 | #include "febase.h" |
---|
[512a2b] | 12 | #include "omalloc.h" |
---|
[0e1846] | 13 | #include "ipid.h" |
---|
| 14 | #include "ideals.h" |
---|
| 15 | #include "polys.h" |
---|
| 16 | #include "hutil.h" |
---|
| 17 | |
---|
| 18 | scfmon hexist, hstc, hrad, hwork; |
---|
| 19 | scmon hpure, hpur0; |
---|
| 20 | varset hvar, hsel; |
---|
| 21 | int hNexist, hNstc, hNrad, hNvar, hNpure; |
---|
[8d1bbc] | 22 | int hisModule; |
---|
[0e1846] | 23 | monf stcmem, radmem; |
---|
| 24 | |
---|
[e78cce] | 25 | // Making a global "security" copy of the allocated exponent vectors |
---|
[233e4c] | 26 | // is a dirty fix for correct memory disallocation: It would be |
---|
[e78cce] | 27 | // better, if either the fields of heist are never touched |
---|
| 28 | // (i.e. changed) except in hInit, or, if hInit would return the |
---|
| 29 | // "security" copy as well. But then, all the relevant data is held in |
---|
| 30 | // global variables, so we might do that here, as well. |
---|
[8d1bbc] | 31 | static int **hsecure= NULL; |
---|
[0e1846] | 32 | |
---|
[fc83e4] | 33 | scfmon hInit(ideal S, ideal Q, int *Nexist, ring tailRing) |
---|
[0e1846] | 34 | { |
---|
| 35 | int sl, ql, i, k = 0; |
---|
| 36 | polyset si, qi, ss; |
---|
| 37 | scfmon ex, ek; |
---|
[fc83e4] | 38 | if (tailRing != currRing) |
---|
| 39 | hisModule = idRankFreeModule(S, currRing, tailRing); |
---|
| 40 | else |
---|
| 41 | hisModule = idRankFreeModule(S); |
---|
[0e1846] | 42 | if (hisModule < 0) |
---|
| 43 | hisModule = 0; |
---|
| 44 | if (S) |
---|
| 45 | { |
---|
| 46 | si = S->m; |
---|
| 47 | sl = IDELEMS(S); |
---|
| 48 | } |
---|
| 49 | else |
---|
| 50 | { |
---|
| 51 | si = NULL; |
---|
| 52 | sl = 0; |
---|
| 53 | } |
---|
| 54 | if (Q) |
---|
| 55 | { |
---|
| 56 | qi = Q->m; |
---|
| 57 | ql = IDELEMS(Q); |
---|
| 58 | } |
---|
| 59 | else |
---|
| 60 | { |
---|
| 61 | qi = NULL; |
---|
| 62 | ql = 0; |
---|
| 63 | } |
---|
| 64 | if (!(sl + ql)) |
---|
| 65 | { |
---|
| 66 | *Nexist = 0; |
---|
| 67 | return NULL; |
---|
| 68 | } |
---|
| 69 | ss = si; |
---|
| 70 | for (i = sl; i; i--) |
---|
| 71 | { |
---|
[ccf4f2e] | 72 | if (*ss!=0) |
---|
[0e1846] | 73 | k++; |
---|
| 74 | ss++; |
---|
| 75 | } |
---|
| 76 | ss = qi; |
---|
| 77 | for (i = ql; i; i--) |
---|
| 78 | { |
---|
[ccf4f2e] | 79 | if (*ss!=0) |
---|
[0e1846] | 80 | k++; |
---|
| 81 | ss++; |
---|
| 82 | } |
---|
| 83 | *Nexist = k; |
---|
| 84 | if (!k) |
---|
| 85 | return NULL; |
---|
[c232af] | 86 | ek = ex = (scfmon)omAlloc(k * sizeof(scmon)); |
---|
[8d1bbc] | 87 | hsecure = (int**) omAlloc(k * sizeof(scmon)); |
---|
[cf3ff4] | 88 | for (i = sl; i>0; i--) |
---|
[0e1846] | 89 | { |
---|
[cf3ff4] | 90 | if (*si!=NULL) |
---|
[0e1846] | 91 | { |
---|
[8d1bbc] | 92 | *ek = (int*) omAlloc((pVariables+1)*sizeof(int)); |
---|
[e78cce] | 93 | pGetExpV(*si, *ek); |
---|
[0e1846] | 94 | ek++; |
---|
| 95 | } |
---|
| 96 | si++; |
---|
| 97 | } |
---|
| 98 | for (i = ql; i; i--) |
---|
| 99 | { |
---|
[ccf4f2e] | 100 | if (*qi!=NULL) |
---|
[0e1846] | 101 | { |
---|
[8d1bbc] | 102 | *ek = (int*) omAlloc((pVariables+1)*sizeof(int)); |
---|
[e78cce] | 103 | pGetExpV(*qi, *ek); |
---|
[0e1846] | 104 | ek++; |
---|
| 105 | } |
---|
| 106 | qi++; |
---|
| 107 | } |
---|
[e78cce] | 108 | memcpy(hsecure, ex, k * sizeof(scmon)); |
---|
[0e1846] | 109 | return ex; |
---|
| 110 | } |
---|
| 111 | |
---|
[76c101] | 112 | void hWeight() |
---|
| 113 | { |
---|
| 114 | int i, k; |
---|
[8d1bbc] | 115 | int x; |
---|
[76c101] | 116 | |
---|
| 117 | i = pVariables; |
---|
| 118 | loop |
---|
| 119 | { |
---|
| 120 | if (pWeight(i) != 1) break; |
---|
| 121 | i--; |
---|
| 122 | if (i == 0) return; |
---|
| 123 | } |
---|
| 124 | for (i=pVariables; i; i--) |
---|
| 125 | { |
---|
| 126 | x = pWeight(i); |
---|
| 127 | if (x != 1) |
---|
| 128 | { |
---|
| 129 | for (k=hNexist-1; k>=0; k--) |
---|
| 130 | { |
---|
| 131 | hexist[k][i] *= x; |
---|
| 132 | } |
---|
| 133 | } |
---|
| 134 | } |
---|
| 135 | } |
---|
| 136 | |
---|
[e78cce] | 137 | void hDelete(scfmon ev, int ev_length) |
---|
| 138 | { |
---|
| 139 | int i; |
---|
| 140 | |
---|
| 141 | for (i=0;i<ev_length;i++) |
---|
[8d1bbc] | 142 | omFreeSize(hsecure[i],(pVariables+1)*sizeof(int)); |
---|
[c232af] | 143 | omFreeSize(hsecure, ev_length*sizeof(scmon)); |
---|
| 144 | omFreeSize(ev, ev_length*sizeof(scmon)); |
---|
[e78cce] | 145 | } |
---|
[0e1846] | 146 | |
---|
[743c32] | 147 | |
---|
[8d1bbc] | 148 | void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc) |
---|
[0e1846] | 149 | { |
---|
| 150 | int i = Nexist, k = 0; |
---|
| 151 | scfmon ex = exist, co = stc; |
---|
| 152 | for (; i; i--) |
---|
| 153 | { |
---|
| 154 | if (!(**ex) || ((**ex) == ak)) |
---|
| 155 | { |
---|
| 156 | *co = *ex; |
---|
| 157 | co++; |
---|
| 158 | k++; |
---|
| 159 | } |
---|
| 160 | ex++; |
---|
| 161 | } |
---|
| 162 | *Nstc = k; |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | |
---|
| 166 | void hSupp(scfmon stc, int Nstc, varset var, int *Nvar) |
---|
| 167 | { |
---|
| 168 | int nv, i0, i1, i, j; |
---|
| 169 | nv = i0 = *Nvar; |
---|
| 170 | i1 = 0; |
---|
| 171 | for (i = 1; i <= nv; i++) |
---|
| 172 | { |
---|
| 173 | j = 0; |
---|
| 174 | loop |
---|
| 175 | { |
---|
| 176 | if (stc[j][i]) |
---|
| 177 | { |
---|
| 178 | i1++; |
---|
| 179 | var[i1] = i; |
---|
| 180 | break; |
---|
| 181 | } |
---|
| 182 | j++; |
---|
| 183 | if (j == Nstc) |
---|
| 184 | { |
---|
| 185 | var[i0] = i; |
---|
| 186 | i0--; |
---|
| 187 | break; |
---|
| 188 | } |
---|
| 189 | } |
---|
| 190 | } |
---|
| 191 | *Nvar = i1; |
---|
| 192 | } |
---|
| 193 | |
---|
| 194 | void hOrdSupp(scfmon stc, int Nstc, varset var, int Nvar) |
---|
| 195 | { |
---|
| 196 | int i, i1, j, jj, k, l; |
---|
[8d1bbc] | 197 | int x; |
---|
[f9326d2] | 198 | scmon temp, count; |
---|
| 199 | float o, h, g, *v1; |
---|
| 200 | |
---|
[c232af] | 201 | v1 = (float *)omAlloc(Nvar * sizeof(float)); |
---|
[8d1bbc] | 202 | temp = (int *)omAlloc(Nstc * sizeof(int)); |
---|
| 203 | count = (int *)omAlloc(Nstc * sizeof(int)); |
---|
[0e1846] | 204 | for (i = 1; i <= Nvar; i++) |
---|
| 205 | { |
---|
| 206 | i1 = var[i]; |
---|
| 207 | *temp = stc[0][i1]; |
---|
[f9326d2] | 208 | *count = 1; |
---|
[0e1846] | 209 | jj = 1; |
---|
| 210 | for (j = 1; j < Nstc; j++) |
---|
| 211 | { |
---|
| 212 | x = stc[j][i1]; |
---|
| 213 | k = 0; |
---|
| 214 | loop |
---|
| 215 | { |
---|
| 216 | if (x > temp[k]) |
---|
| 217 | { |
---|
| 218 | k++; |
---|
| 219 | if (k == jj) |
---|
| 220 | { |
---|
| 221 | temp[k] = x; |
---|
[f9326d2] | 222 | count[k] = 1; |
---|
[0e1846] | 223 | jj++; |
---|
| 224 | break; |
---|
| 225 | } |
---|
| 226 | } |
---|
| 227 | else if (x < temp[k]) |
---|
| 228 | { |
---|
[f9326d2] | 229 | for (l = jj; l > k; l--) |
---|
| 230 | { |
---|
[0e1846] | 231 | temp[l] = temp[l-1]; |
---|
[f9326d2] | 232 | count[l] = count[l-1]; |
---|
| 233 | } |
---|
[0e1846] | 234 | temp[k] = x; |
---|
[f9326d2] | 235 | count[k] = 1; |
---|
[0e1846] | 236 | jj++; |
---|
| 237 | break; |
---|
| 238 | } |
---|
| 239 | else |
---|
[f9326d2] | 240 | { |
---|
| 241 | count[k]++; |
---|
[0e1846] | 242 | break; |
---|
[f9326d2] | 243 | } |
---|
[0e1846] | 244 | } |
---|
| 245 | } |
---|
[f9326d2] | 246 | h = 0.0; |
---|
| 247 | o = (float)Nstc/(float)jj; |
---|
| 248 | for(j = 0; j < jj; j++) |
---|
| 249 | { |
---|
| 250 | g = (float)count[j]; |
---|
| 251 | if (g > o) |
---|
| 252 | g -= o; |
---|
| 253 | else |
---|
[743c32] | 254 | g = o - g; |
---|
[f9326d2] | 255 | if (g > h) |
---|
| 256 | h = g; |
---|
| 257 | } |
---|
| 258 | v1[i-1] = h * (float)jj; |
---|
[0e1846] | 259 | } |
---|
[8d1bbc] | 260 | omFreeSize((ADDRESS)count, Nstc * sizeof(int)); |
---|
| 261 | omFreeSize((ADDRESS)temp, Nstc * sizeof(int)); |
---|
[0e1846] | 262 | for (i = 1; i < Nvar; i++) |
---|
| 263 | { |
---|
| 264 | i1 = var[i+1]; |
---|
[f9326d2] | 265 | h = v1[i]; |
---|
[0e1846] | 266 | j = 0; |
---|
| 267 | loop |
---|
| 268 | { |
---|
[f9326d2] | 269 | if (h > v1[j]) |
---|
[0e1846] | 270 | { |
---|
| 271 | for (l = i; l > j; l--) |
---|
| 272 | { |
---|
| 273 | v1[l] = v1[l-1]; |
---|
| 274 | var[l+1] = var[l]; |
---|
| 275 | } |
---|
[f9326d2] | 276 | v1[j] = h; |
---|
[0e1846] | 277 | var[j+1] = i1; |
---|
| 278 | break; |
---|
| 279 | } |
---|
| 280 | j++; |
---|
| 281 | if (j == i) |
---|
| 282 | break; |
---|
| 283 | } |
---|
| 284 | } |
---|
[c232af] | 285 | omFreeSize((ADDRESS)v1, Nvar * sizeof(float)); |
---|
[0e1846] | 286 | } |
---|
| 287 | |
---|
| 288 | |
---|
| 289 | static void hShrink(scfmon co, int a, int Nco) |
---|
| 290 | { |
---|
[241f58] | 291 | while ((co[a]!=NULL) && (a<Nco)) a++; |
---|
| 292 | int i = a; |
---|
| 293 | int j; |
---|
| 294 | for (j = a; j < Nco; j++) |
---|
[0e1846] | 295 | { |
---|
[241f58] | 296 | if (co[j]!=NULL) |
---|
[0e1846] | 297 | { |
---|
| 298 | co[i] = co[j]; |
---|
| 299 | i++; |
---|
| 300 | } |
---|
| 301 | } |
---|
| 302 | } |
---|
| 303 | |
---|
| 304 | |
---|
| 305 | void hStaircase(scfmon stc, int *Nstc, varset var, int Nvar) |
---|
| 306 | { |
---|
[241f58] | 307 | int nc = *Nstc; |
---|
[0e1846] | 308 | if (nc < 2) |
---|
| 309 | return; |
---|
[241f58] | 310 | int z = 0; |
---|
| 311 | int i = 0; |
---|
| 312 | int j = 1; |
---|
| 313 | scmon n = stc[1 /*j*/]; |
---|
| 314 | scmon o = stc[0]; |
---|
| 315 | int k = Nvar; |
---|
[0e1846] | 316 | loop |
---|
| 317 | { |
---|
[241f58] | 318 | int k1 = var[k]; |
---|
[0e1846] | 319 | if (o[k1] > n[k1]) |
---|
| 320 | { |
---|
| 321 | loop |
---|
| 322 | { |
---|
| 323 | k--; |
---|
[241f58] | 324 | if (k==0) |
---|
[0e1846] | 325 | { |
---|
| 326 | stc[i] = NULL; |
---|
| 327 | z++; |
---|
| 328 | break; |
---|
| 329 | } |
---|
| 330 | else |
---|
| 331 | { |
---|
| 332 | k1 = var[k]; |
---|
| 333 | if (o[k1] < n[k1]) |
---|
| 334 | break; |
---|
| 335 | } |
---|
| 336 | } |
---|
| 337 | k = Nvar; |
---|
| 338 | } |
---|
| 339 | else if (o[k1] < n[k1]) |
---|
| 340 | { |
---|
| 341 | loop |
---|
| 342 | { |
---|
| 343 | k--; |
---|
[241f58] | 344 | if (k==0) |
---|
[0e1846] | 345 | { |
---|
| 346 | stc[j] = NULL; |
---|
| 347 | z++; |
---|
| 348 | break; |
---|
| 349 | } |
---|
| 350 | else |
---|
| 351 | { |
---|
| 352 | k1 = var[k]; |
---|
| 353 | if (o[k1] > n[k1]) |
---|
| 354 | break; |
---|
| 355 | } |
---|
| 356 | } |
---|
| 357 | k = Nvar; |
---|
| 358 | } |
---|
| 359 | else |
---|
| 360 | { |
---|
| 361 | k--; |
---|
[241f58] | 362 | if (k==0) |
---|
[0e1846] | 363 | { |
---|
| 364 | stc[j] = NULL; |
---|
| 365 | z++; |
---|
| 366 | k = Nvar; |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | if (k == Nvar) |
---|
| 370 | { |
---|
[241f58] | 371 | if (stc[j]==NULL) |
---|
[0e1846] | 372 | i = j - 1; |
---|
| 373 | loop |
---|
| 374 | { |
---|
| 375 | i++; |
---|
| 376 | if (i == j) |
---|
| 377 | { |
---|
| 378 | i = -1; |
---|
| 379 | j++; |
---|
| 380 | if (j < nc) |
---|
| 381 | n = stc[j]; |
---|
| 382 | else |
---|
| 383 | { |
---|
[241f58] | 384 | if (z!=0) |
---|
[0e1846] | 385 | { |
---|
| 386 | *Nstc -= z; |
---|
| 387 | hShrink(stc, 0, nc); |
---|
| 388 | } |
---|
| 389 | return; |
---|
| 390 | } |
---|
| 391 | } |
---|
[241f58] | 392 | else if (stc[i]!=NULL) |
---|
[0e1846] | 393 | { |
---|
| 394 | o = stc[i]; |
---|
| 395 | break; |
---|
| 396 | } |
---|
| 397 | } |
---|
| 398 | } |
---|
| 399 | } |
---|
| 400 | } |
---|
| 401 | |
---|
| 402 | |
---|
| 403 | void hRadical(scfmon rad, int *Nrad, int Nvar) |
---|
| 404 | { |
---|
| 405 | int nc = *Nrad, z = 0, i, j, k; |
---|
| 406 | scmon n, o; |
---|
| 407 | if (nc < 2) |
---|
| 408 | return; |
---|
| 409 | i = 0; |
---|
| 410 | j = 1; |
---|
| 411 | n = rad[j]; |
---|
[ccf4f2e] | 412 | o = rad[0]; |
---|
[0e1846] | 413 | k = Nvar; |
---|
| 414 | loop |
---|
| 415 | { |
---|
[ccf4f2e] | 416 | if ((o[k]!=0) && (n[k]==0)) |
---|
[0e1846] | 417 | { |
---|
| 418 | loop |
---|
| 419 | { |
---|
| 420 | k--; |
---|
[ccf4f2e] | 421 | if (k==0) |
---|
[0e1846] | 422 | { |
---|
| 423 | rad[i] = NULL; |
---|
| 424 | z++; |
---|
| 425 | break; |
---|
| 426 | } |
---|
| 427 | else |
---|
| 428 | { |
---|
[ccf4f2e] | 429 | if ((o[k]==0) && (n[k]!=0)) |
---|
[0e1846] | 430 | break; |
---|
| 431 | } |
---|
| 432 | } |
---|
| 433 | k = Nvar; |
---|
| 434 | } |
---|
| 435 | else if (!o[k] && n[k]) |
---|
| 436 | { |
---|
| 437 | loop |
---|
| 438 | { |
---|
| 439 | k--; |
---|
| 440 | if (!k) |
---|
| 441 | { |
---|
| 442 | rad[j] = NULL; |
---|
| 443 | z++; |
---|
| 444 | break; |
---|
| 445 | } |
---|
| 446 | else |
---|
| 447 | { |
---|
| 448 | if (o[k] && !n[k]) |
---|
| 449 | break; |
---|
| 450 | } |
---|
| 451 | } |
---|
| 452 | k = Nvar; |
---|
| 453 | } |
---|
| 454 | else |
---|
| 455 | { |
---|
| 456 | k--; |
---|
| 457 | if (!k) |
---|
| 458 | { |
---|
| 459 | rad[j] = NULL; |
---|
| 460 | z++; |
---|
| 461 | k = Nvar; |
---|
| 462 | } |
---|
| 463 | } |
---|
| 464 | if (k == Nvar) |
---|
| 465 | { |
---|
| 466 | if (!rad[j]) |
---|
| 467 | i = j - 1; |
---|
| 468 | loop |
---|
| 469 | { |
---|
| 470 | i++; |
---|
| 471 | if (i == j) |
---|
| 472 | { |
---|
| 473 | i = -1; |
---|
| 474 | j++; |
---|
| 475 | if (j < nc) |
---|
| 476 | n = rad[j]; |
---|
| 477 | else |
---|
| 478 | { |
---|
| 479 | if (z) |
---|
| 480 | { |
---|
| 481 | *Nrad -= z; |
---|
| 482 | hShrink(rad, 0, nc); |
---|
| 483 | } |
---|
| 484 | return; |
---|
| 485 | } |
---|
| 486 | } |
---|
| 487 | else if (rad[i]) |
---|
| 488 | { |
---|
| 489 | o = rad[i]; |
---|
| 490 | break; |
---|
| 491 | } |
---|
| 492 | } |
---|
| 493 | } |
---|
| 494 | } |
---|
| 495 | } |
---|
| 496 | |
---|
| 497 | |
---|
| 498 | void hLexS(scfmon stc, int Nstc, varset var, int Nvar) |
---|
| 499 | { |
---|
| 500 | if (Nstc < 2) |
---|
| 501 | return; |
---|
[4ab486] | 502 | int j = 1, i = 0; |
---|
| 503 | scmon n = stc[j]; |
---|
[ccf4f2e] | 504 | scmon o = stc[0]; |
---|
[4ab486] | 505 | int k = Nvar; |
---|
[0e1846] | 506 | loop |
---|
| 507 | { |
---|
[4ab486] | 508 | int k1 = var[k]; |
---|
[0e1846] | 509 | if (o[k1] < n[k1]) |
---|
| 510 | { |
---|
| 511 | i++; |
---|
| 512 | if (i < j) |
---|
| 513 | { |
---|
| 514 | o = stc[i]; |
---|
| 515 | k = Nvar; |
---|
| 516 | } |
---|
| 517 | else |
---|
| 518 | { |
---|
| 519 | j++; |
---|
| 520 | if (j < Nstc) |
---|
| 521 | { |
---|
| 522 | i = 0; |
---|
[ccf4f2e] | 523 | o = stc[0]; |
---|
[0e1846] | 524 | n = stc[j]; |
---|
| 525 | k = Nvar; |
---|
| 526 | } |
---|
| 527 | else |
---|
| 528 | return; |
---|
| 529 | } |
---|
| 530 | } |
---|
| 531 | else if (o[k1] > n[k1]) |
---|
[0c9669] | 532 | { |
---|
[4ab486] | 533 | int tmp_k; |
---|
| 534 | for (tmp_k = j; tmp_k > i; tmp_k--) |
---|
| 535 | stc[tmp_k] = stc[tmp_k - 1]; |
---|
[0e1846] | 536 | stc[i] = n; |
---|
| 537 | j++; |
---|
| 538 | if (j < Nstc) |
---|
| 539 | { |
---|
| 540 | i = 0; |
---|
[ccf4f2e] | 541 | o = stc[0]; |
---|
[0e1846] | 542 | n = stc[j]; |
---|
| 543 | k = Nvar; |
---|
| 544 | } |
---|
| 545 | else |
---|
| 546 | return; |
---|
| 547 | } |
---|
| 548 | else |
---|
[241f58] | 549 | { |
---|
[0e1846] | 550 | k--; |
---|
[9e55dd] | 551 | if (k<=0) return; |
---|
[241f58] | 552 | } |
---|
[0e1846] | 553 | } |
---|
| 554 | } |
---|
| 555 | |
---|
| 556 | |
---|
| 557 | void hLexR(scfmon rad, int Nrad, varset var, int Nvar) |
---|
| 558 | { |
---|
| 559 | int j = 1, i = 0, k, k1; |
---|
| 560 | scmon n, o; |
---|
| 561 | if (Nrad < 2) |
---|
| 562 | return; |
---|
| 563 | n = rad[j]; |
---|
[ccf4f2e] | 564 | o = rad[0]; |
---|
[0e1846] | 565 | k = Nvar; |
---|
| 566 | loop |
---|
| 567 | { |
---|
| 568 | k1 = var[k]; |
---|
| 569 | if (!o[k1] && n[k1]) |
---|
| 570 | { |
---|
| 571 | i++; |
---|
| 572 | if (i < j) |
---|
| 573 | { |
---|
| 574 | o = rad[i]; |
---|
| 575 | k = Nvar; |
---|
| 576 | } |
---|
| 577 | else |
---|
| 578 | { |
---|
| 579 | j++; |
---|
| 580 | if (j < Nrad) |
---|
| 581 | { |
---|
| 582 | i = 0; |
---|
[ccf4f2e] | 583 | o = rad[0]; |
---|
[0e1846] | 584 | n = rad[j]; |
---|
| 585 | k = Nvar; |
---|
| 586 | } |
---|
| 587 | else |
---|
| 588 | return; |
---|
| 589 | } |
---|
| 590 | } |
---|
| 591 | else if (o[k1] && !n[k1]) |
---|
| 592 | { |
---|
| 593 | for (k = j; k > i; k--) |
---|
| 594 | rad[k] = rad[k - 1]; |
---|
| 595 | rad[i] = n; |
---|
| 596 | j++; |
---|
| 597 | if (j < Nrad) |
---|
| 598 | { |
---|
| 599 | i = 0; |
---|
[ccf4f2e] | 600 | o = rad[0]; |
---|
[0e1846] | 601 | n = rad[j]; |
---|
| 602 | k = Nvar; |
---|
| 603 | } |
---|
| 604 | else |
---|
| 605 | return; |
---|
| 606 | } |
---|
| 607 | else |
---|
| 608 | k--; |
---|
| 609 | } |
---|
| 610 | } |
---|
| 611 | |
---|
| 612 | |
---|
| 613 | void hPure(scfmon stc, int a, int *Nstc, varset var, int Nvar, |
---|
| 614 | scmon pure, int *Npure) |
---|
| 615 | { |
---|
| 616 | int nc = *Nstc, np = 0, nq = 0, j, i, i1, c, l; |
---|
| 617 | scmon x; |
---|
| 618 | for (j = a; j < nc; j++) |
---|
| 619 | { |
---|
| 620 | x = stc[j]; |
---|
| 621 | i = Nvar; |
---|
| 622 | c = 2; |
---|
| 623 | l = 0; |
---|
| 624 | loop |
---|
| 625 | { |
---|
| 626 | i1 = var[i]; |
---|
| 627 | if (x[i1]) |
---|
| 628 | { |
---|
| 629 | c--; |
---|
| 630 | if (!c) |
---|
| 631 | { |
---|
| 632 | l = 0; |
---|
| 633 | break; |
---|
| 634 | } |
---|
| 635 | else if (c == 1) |
---|
| 636 | l = i1; |
---|
| 637 | } |
---|
| 638 | i--; |
---|
| 639 | if (!i) |
---|
| 640 | break; |
---|
| 641 | } |
---|
| 642 | if (l) |
---|
| 643 | { |
---|
| 644 | if (!pure[l]) |
---|
| 645 | { |
---|
| 646 | np++; |
---|
| 647 | pure[l] = x[l]; |
---|
| 648 | } |
---|
| 649 | else if (x[l] < pure[l]) |
---|
| 650 | pure[l] = x[l]; |
---|
| 651 | stc[j] = NULL; |
---|
| 652 | nq++; |
---|
| 653 | } |
---|
| 654 | } |
---|
| 655 | *Npure = np; |
---|
[ccf4f2e] | 656 | if (nq!=0) |
---|
[0e1846] | 657 | { |
---|
| 658 | *Nstc -= nq; |
---|
| 659 | hShrink(stc, a, nc); |
---|
| 660 | } |
---|
| 661 | } |
---|
| 662 | |
---|
| 663 | |
---|
| 664 | void hElimS(scfmon stc, int *e1, int a2, int e2, varset var, int Nvar) |
---|
| 665 | { |
---|
| 666 | int nc = *e1, z = 0, i, j, k, k1; |
---|
| 667 | scmon n, o; |
---|
| 668 | if (!nc || (a2 == e2)) |
---|
| 669 | return; |
---|
| 670 | j = 0; |
---|
| 671 | i = a2; |
---|
| 672 | o = stc[i]; |
---|
[ccf4f2e] | 673 | n = stc[0]; |
---|
[0e1846] | 674 | k = Nvar; |
---|
| 675 | loop |
---|
| 676 | { |
---|
| 677 | k1 = var[k]; |
---|
| 678 | if (o[k1] > n[k1]) |
---|
| 679 | { |
---|
| 680 | k = Nvar; |
---|
| 681 | i++; |
---|
| 682 | if (i < e2) |
---|
| 683 | o = stc[i]; |
---|
[ccf4f2e] | 684 | else |
---|
| 685 | { |
---|
[0e1846] | 686 | j++; |
---|
| 687 | if (j < nc) |
---|
| 688 | { |
---|
| 689 | i = a2; |
---|
| 690 | o = stc[i]; |
---|
| 691 | n = stc[j]; |
---|
| 692 | } |
---|
| 693 | else |
---|
| 694 | { |
---|
[ccf4f2e] | 695 | if (z!=0) |
---|
[0e1846] | 696 | { |
---|
| 697 | *e1 -= z; |
---|
| 698 | hShrink(stc, 0, nc); |
---|
| 699 | } |
---|
| 700 | return; |
---|
| 701 | } |
---|
| 702 | } |
---|
| 703 | } |
---|
| 704 | else |
---|
| 705 | { |
---|
| 706 | k--; |
---|
[ccf4f2e] | 707 | if (k==0) |
---|
[0e1846] | 708 | { |
---|
| 709 | stc[j] = NULL; |
---|
| 710 | z++; |
---|
| 711 | j++; |
---|
| 712 | if (j < nc) |
---|
| 713 | { |
---|
| 714 | i = a2; |
---|
| 715 | o = stc[i]; |
---|
| 716 | n = stc[j]; |
---|
| 717 | k = Nvar; |
---|
| 718 | } |
---|
| 719 | else |
---|
| 720 | { |
---|
[ccf4f2e] | 721 | if (z!=0) |
---|
[0e1846] | 722 | { |
---|
| 723 | *e1 -= z; |
---|
| 724 | hShrink(stc, 0, nc); |
---|
| 725 | } |
---|
| 726 | return; |
---|
| 727 | } |
---|
| 728 | } |
---|
| 729 | } |
---|
| 730 | } |
---|
| 731 | } |
---|
| 732 | |
---|
| 733 | |
---|
| 734 | void hElimR(scfmon rad, int *e1, int a2, int e2, varset var, int Nvar) |
---|
| 735 | { |
---|
| 736 | int nc = *e1, z = 0, i, j, k, k1; |
---|
| 737 | scmon n, o; |
---|
| 738 | if (!nc || (a2 == e2)) |
---|
| 739 | return; |
---|
| 740 | j = 0; |
---|
| 741 | i = a2; |
---|
| 742 | o = rad[i]; |
---|
[ccf4f2e] | 743 | n = rad[0]; |
---|
[0e1846] | 744 | k = Nvar; |
---|
| 745 | loop |
---|
| 746 | { |
---|
| 747 | k1 = var[k]; |
---|
| 748 | if (o[k1] && !n[k1]) |
---|
| 749 | { |
---|
| 750 | k = Nvar; |
---|
| 751 | i++; |
---|
| 752 | if (i < e2) |
---|
| 753 | o = rad[i]; |
---|
| 754 | else |
---|
| 755 | { |
---|
| 756 | j++; |
---|
| 757 | if (j < nc) |
---|
| 758 | { |
---|
| 759 | i = a2; |
---|
| 760 | o = rad[i]; |
---|
| 761 | n = rad[j]; |
---|
| 762 | } |
---|
| 763 | else |
---|
| 764 | { |
---|
[ccf4f2e] | 765 | if (z!=0) |
---|
[0e1846] | 766 | { |
---|
| 767 | *e1 -= z; |
---|
| 768 | hShrink(rad, 0, nc); |
---|
| 769 | } |
---|
| 770 | return; |
---|
| 771 | } |
---|
| 772 | } |
---|
| 773 | } |
---|
| 774 | else |
---|
| 775 | { |
---|
| 776 | k--; |
---|
| 777 | if (!k) |
---|
| 778 | { |
---|
| 779 | rad[j] = NULL; |
---|
| 780 | z++; |
---|
| 781 | j++; |
---|
| 782 | if (j < nc) |
---|
| 783 | { |
---|
| 784 | i = a2; |
---|
| 785 | o = rad[i]; |
---|
| 786 | n = rad[j]; |
---|
| 787 | k = Nvar; |
---|
| 788 | } |
---|
| 789 | else |
---|
| 790 | { |
---|
[ccf4f2e] | 791 | if (z!=0) |
---|
[0e1846] | 792 | { |
---|
| 793 | *e1 -= z; |
---|
| 794 | hShrink(rad, 0, nc); |
---|
| 795 | } |
---|
| 796 | return; |
---|
| 797 | } |
---|
| 798 | } |
---|
| 799 | } |
---|
| 800 | } |
---|
| 801 | } |
---|
| 802 | |
---|
| 803 | |
---|
| 804 | void hLex2S(scfmon rad, int e1, int a2, int e2, varset var, |
---|
| 805 | int Nvar, scfmon w) |
---|
| 806 | { |
---|
| 807 | int j0 = 0, j = 0, i = a2, k, k1; |
---|
| 808 | scmon n, o; |
---|
| 809 | if (!e1) |
---|
| 810 | { |
---|
| 811 | for (; i < e2; i++) |
---|
| 812 | rad[i - a2] = rad[i]; |
---|
| 813 | return; |
---|
| 814 | } else if (i == e2) |
---|
| 815 | return; |
---|
| 816 | n = rad[j]; |
---|
| 817 | o = rad[i]; |
---|
| 818 | loop |
---|
| 819 | { |
---|
| 820 | k = Nvar; |
---|
| 821 | loop |
---|
| 822 | { |
---|
| 823 | k1 = var[k]; |
---|
| 824 | if (o[k1] < n[k1]) |
---|
| 825 | { |
---|
| 826 | w[j0] = o; |
---|
| 827 | j0++; |
---|
| 828 | i++; |
---|
| 829 | if (i < e2) |
---|
| 830 | { |
---|
| 831 | o = rad[i]; |
---|
| 832 | break; |
---|
| 833 | } |
---|
| 834 | else |
---|
| 835 | { |
---|
| 836 | for (; j < e1; j++) |
---|
| 837 | { |
---|
| 838 | w[j0] = rad[j]; |
---|
| 839 | j0++; |
---|
| 840 | } |
---|
| 841 | memcpy(rad, w, (e1 + e2 - a2) * sizeof(scmon)); |
---|
| 842 | return; |
---|
| 843 | } |
---|
| 844 | } |
---|
| 845 | else if (o[k1] > n[k1]) |
---|
| 846 | { |
---|
| 847 | w[j0] = n; |
---|
| 848 | j0++; |
---|
| 849 | j++; |
---|
| 850 | if (j < e1) |
---|
| 851 | { |
---|
| 852 | n = rad[j]; |
---|
| 853 | break; |
---|
| 854 | } |
---|
| 855 | else |
---|
| 856 | { |
---|
| 857 | for (; i < e2; i++) |
---|
| 858 | { |
---|
| 859 | w[j0] = rad[i]; |
---|
| 860 | j0++; |
---|
| 861 | } |
---|
| 862 | memcpy(rad, w, (e1 + e2 - a2) * sizeof(scmon)); |
---|
| 863 | return; |
---|
| 864 | } |
---|
| 865 | } |
---|
| 866 | k--; |
---|
| 867 | } |
---|
| 868 | } |
---|
| 869 | } |
---|
| 870 | |
---|
| 871 | |
---|
| 872 | void hLex2R(scfmon rad, int e1, int a2, int e2, varset var, |
---|
| 873 | int Nvar, scfmon w) |
---|
| 874 | { |
---|
| 875 | int j0 = 0, j = 0, i = a2, k, k1; |
---|
| 876 | scmon n, o; |
---|
| 877 | if (!e1) |
---|
| 878 | { |
---|
| 879 | for (; i < e2; i++) |
---|
| 880 | rad[i - a2] = rad[i]; |
---|
| 881 | return; |
---|
| 882 | } |
---|
| 883 | else if (i == e2) |
---|
| 884 | return; |
---|
| 885 | n = rad[j]; |
---|
| 886 | o = rad[i]; |
---|
| 887 | loop |
---|
| 888 | { |
---|
| 889 | k = Nvar; |
---|
| 890 | loop |
---|
| 891 | { |
---|
| 892 | k1 = var[k]; |
---|
| 893 | if (!o[k1] && n[k1]) |
---|
| 894 | { |
---|
| 895 | w[j0] = o; |
---|
| 896 | j0++; |
---|
| 897 | i++; |
---|
| 898 | if (i < e2) |
---|
| 899 | { |
---|
| 900 | o = rad[i]; |
---|
| 901 | break; |
---|
| 902 | } |
---|
| 903 | else |
---|
| 904 | { |
---|
| 905 | for (; j < e1; j++) |
---|
| 906 | { |
---|
| 907 | w[j0] = rad[j]; |
---|
| 908 | j0++; |
---|
| 909 | } |
---|
| 910 | memcpy(rad, w, (e1 + e2 - a2) * sizeof(scmon)); |
---|
| 911 | return; |
---|
| 912 | } |
---|
| 913 | } |
---|
| 914 | else if (o[k1] && !n[k1]) |
---|
| 915 | { |
---|
| 916 | w[j0] = n; |
---|
| 917 | j0++; |
---|
| 918 | j++; |
---|
| 919 | if (j < e1) |
---|
| 920 | { |
---|
| 921 | n = rad[j]; |
---|
| 922 | break; |
---|
| 923 | } |
---|
| 924 | else |
---|
| 925 | { |
---|
| 926 | for (; i < e2; i++) |
---|
| 927 | { |
---|
| 928 | w[j0] = rad[i]; |
---|
| 929 | j0++; |
---|
| 930 | } |
---|
| 931 | memcpy(rad, w, (e1 + e2 - a2) * sizeof(scmon)); |
---|
| 932 | return; |
---|
| 933 | } |
---|
| 934 | } |
---|
| 935 | k--; |
---|
| 936 | } |
---|
| 937 | } |
---|
| 938 | } |
---|
| 939 | |
---|
| 940 | |
---|
[8d1bbc] | 941 | void hStepS(scfmon stc, int Nstc, varset var, int Nvar, int *a, int *x) |
---|
[0e1846] | 942 | { |
---|
| 943 | int k1, i; |
---|
[8d1bbc] | 944 | int y; |
---|
[0e1846] | 945 | k1 = var[Nvar]; |
---|
| 946 | y = *x; |
---|
| 947 | i = *a; |
---|
| 948 | loop |
---|
| 949 | { |
---|
| 950 | if (y < stc[i][k1]) |
---|
| 951 | { |
---|
| 952 | *a = i; |
---|
| 953 | *x = stc[i][k1]; |
---|
| 954 | return; |
---|
| 955 | } |
---|
| 956 | i++; |
---|
| 957 | if (i == Nstc) |
---|
| 958 | { |
---|
| 959 | *a = i; |
---|
| 960 | return; |
---|
| 961 | } |
---|
| 962 | } |
---|
| 963 | } |
---|
| 964 | |
---|
| 965 | |
---|
| 966 | void hStepR(scfmon rad, int Nrad, varset var, int Nvar, int *a) |
---|
| 967 | { |
---|
| 968 | int k1, i; |
---|
| 969 | k1 = var[Nvar]; |
---|
| 970 | i = 0; |
---|
| 971 | loop |
---|
| 972 | { |
---|
| 973 | if (rad[i][k1]) |
---|
| 974 | { |
---|
| 975 | *a = i; |
---|
| 976 | return; |
---|
| 977 | } |
---|
| 978 | i++; |
---|
| 979 | if (i == Nrad) |
---|
| 980 | { |
---|
| 981 | *a = i; |
---|
| 982 | return; |
---|
| 983 | } |
---|
| 984 | } |
---|
| 985 | } |
---|
| 986 | |
---|
| 987 | |
---|
| 988 | monf hCreate(int Nvar) |
---|
| 989 | { |
---|
| 990 | monf xmem; |
---|
| 991 | int i; |
---|
[c232af] | 992 | xmem = (monf)omAlloc((Nvar + 1) * sizeof(monp)); |
---|
[cf3ff4] | 993 | for (i = Nvar; i>0; i--) |
---|
[0e1846] | 994 | { |
---|
[c232af] | 995 | xmem[i] = (monp)omAlloc(LEN_MON); |
---|
[0e1846] | 996 | xmem[i]->mo = NULL; |
---|
| 997 | } |
---|
| 998 | return xmem; |
---|
| 999 | } |
---|
| 1000 | |
---|
| 1001 | |
---|
| 1002 | void hKill(monf xmem, int Nvar) |
---|
| 1003 | { |
---|
| 1004 | int i; |
---|
[ccf4f2e] | 1005 | for (i = Nvar; i!=0; i--) |
---|
[0e1846] | 1006 | { |
---|
[ccf4f2e] | 1007 | if (xmem[i]->mo!=NULL) |
---|
[c232af] | 1008 | omFreeSize((ADDRESS)xmem[i]->mo, xmem[i]->a * sizeof(scmon)); |
---|
| 1009 | omFreeSize((ADDRESS)xmem[i], LEN_MON); |
---|
[0e1846] | 1010 | } |
---|
[c232af] | 1011 | omFreeSize((ADDRESS)xmem, (Nvar + 1) * sizeof(monp)); |
---|
[0e1846] | 1012 | } |
---|
| 1013 | |
---|
| 1014 | |
---|
| 1015 | scfmon hGetmem(int lm, scfmon old, monp monmem) |
---|
| 1016 | { |
---|
| 1017 | scfmon x = monmem->mo; |
---|
| 1018 | int lx = monmem->a; |
---|
[9e55dd] | 1019 | if ((x==NULL) || (lm > lx)) |
---|
[0e1846] | 1020 | { |
---|
[9e55dd] | 1021 | if ((x!=NULL)&&(lx>0)) omFreeSize((ADDRESS)x, lx * sizeof(scmon)); |
---|
[c232af] | 1022 | monmem->mo = x = (scfmon)omAlloc(lm * sizeof(scmon)); |
---|
[0e1846] | 1023 | monmem->a = lm; |
---|
| 1024 | } |
---|
| 1025 | memcpy(x, old, lm * sizeof(scmon)); |
---|
| 1026 | return x; |
---|
| 1027 | } |
---|
| 1028 | |
---|
[81422c] | 1029 | /* |
---|
| 1030 | * a bug in Metrowerks with "lifetime analysis" |
---|
| 1031 | *scmon hGetpure(scmon p) |
---|
| 1032 | *{ |
---|
| 1033 | * scmon p1, pn; |
---|
| 1034 | * p1 = p + 1; |
---|
| 1035 | * pn = p1 + pVariables; |
---|
[8d1bbc] | 1036 | * memcpy(pn, p1, pVariables * sizeof(int)); |
---|
[81422c] | 1037 | * return pn - 1; |
---|
| 1038 | *} |
---|
| 1039 | */ |
---|
[0e1846] | 1040 | scmon hGetpure(scmon p) |
---|
| 1041 | { |
---|
[81422c] | 1042 | scmon p1 = p; |
---|
| 1043 | scmon pn; |
---|
| 1044 | p1++; |
---|
| 1045 | pn = p1; |
---|
| 1046 | pn += pVariables; |
---|
[8d1bbc] | 1047 | memcpy(pn, p1, pVariables * sizeof(int)); |
---|
[0e1846] | 1048 | return pn - 1; |
---|
| 1049 | } |
---|
| 1050 | |
---|