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