[35aab3] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
| 4 | /*************************************************************** |
---|
| 5 | * File: sbuckets.cc |
---|
| 6 | * Purpose: implementation of routines for sorting polys using |
---|
| 7 | * a bucket sort |
---|
| 8 | * Author: obachman (Olaf Bachmann) |
---|
| 9 | * Created: 9/00 |
---|
| 10 | *******************************************************************/ |
---|
[aadd638] | 11 | #include "misc/auxiliary.h" |
---|
[16f511] | 12 | |
---|
[aadd638] | 13 | #include "polys/sbuckets.h" |
---|
[8179468] | 14 | |
---|
[aadd638] | 15 | #include "polys/monomials/ring.h" |
---|
| 16 | #include "polys/monomials/p_polys.h" |
---|
[35aab3] | 17 | |
---|
| 18 | ////////////////////////////////////////////////////////////////////////// |
---|
| 19 | // Declarations |
---|
| 20 | // |
---|
| 21 | |
---|
| 22 | class sBucketPoly |
---|
| 23 | { |
---|
| 24 | public: |
---|
| 25 | poly p; |
---|
| 26 | long length; |
---|
| 27 | }; |
---|
| 28 | |
---|
| 29 | class sBucket |
---|
| 30 | { |
---|
| 31 | public: |
---|
| 32 | ring bucket_ring; |
---|
| 33 | long max_bucket; |
---|
| 34 | sBucketPoly buckets[BIT_SIZEOF_LONG - 3]; |
---|
| 35 | } |
---|
| 36 | ; |
---|
| 37 | |
---|
[a3f0fea] | 38 | STATIC_VAR omBin sBucket_bin = omGetSpecBin(sizeof(sBucket)); |
---|
[35aab3] | 39 | |
---|
[a795c77] | 40 | |
---|
| 41 | ////////////////////////////////////////////////////////////////////////// |
---|
| 42 | // New API: |
---|
| 43 | // |
---|
| 44 | |
---|
| 45 | /// Returns bucket ring |
---|
[760a78f] | 46 | ring sBucketGetRing(const sBucket_pt bucket) |
---|
[a795c77] | 47 | { return bucket->bucket_ring; } |
---|
| 48 | |
---|
[0b7fb8] | 49 | |
---|
| 50 | bool sIsEmpty(const sBucket_pt bucket) |
---|
| 51 | { |
---|
| 52 | for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++) |
---|
[75f460] | 53 | { |
---|
[0b7fb8] | 54 | assume( i < (BIT_SIZEOF_LONG - 3) ); |
---|
| 55 | assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length ); |
---|
| 56 | |
---|
| 57 | if( bucket->buckets[i].p != NULL ) |
---|
| 58 | return false; |
---|
| 59 | |
---|
| 60 | if( bucket->buckets[i].length != 0 ) |
---|
| 61 | return false; |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | return( bucket->max_bucket == 0 ); |
---|
| 65 | |
---|
| 66 | } |
---|
| 67 | |
---|
| 68 | |
---|
[a795c77] | 69 | /// Copy sBucket non-intrusive!!! |
---|
| 70 | sBucket_pt sBucketCopy(const sBucket_pt bucket) |
---|
| 71 | { |
---|
[9ae5a3] | 72 | sBucketCanonicalize(bucket); |
---|
[a795c77] | 73 | const ring r = bucket->bucket_ring; |
---|
| 74 | |
---|
| 75 | sBucket_pt newbucket = sBucketCreate(r); |
---|
| 76 | |
---|
[0b7fb8] | 77 | newbucket->max_bucket = bucket->max_bucket; |
---|
| 78 | |
---|
| 79 | for(int i = 0; i <= bucket->max_bucket; i++) |
---|
[75f460] | 80 | { |
---|
[a795c77] | 81 | assume( i < (BIT_SIZEOF_LONG - 3) ); |
---|
| 82 | assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length ); |
---|
| 83 | |
---|
| 84 | newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r); |
---|
| 85 | newbucket->buckets[i].length = bucket->buckets[i].length; |
---|
| 86 | |
---|
| 87 | assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length ); |
---|
| 88 | } |
---|
| 89 | |
---|
| 90 | return newbucket; |
---|
| 91 | } |
---|
| 92 | |
---|
[35aab3] | 93 | ////////////////////////////////////////////////////////////////////////// |
---|
| 94 | // Creation/Destruction of buckets |
---|
| 95 | // |
---|
[b0ae38] | 96 | sBucket_pt sBucketCreate(const ring r) |
---|
[35aab3] | 97 | { |
---|
| 98 | sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin); |
---|
| 99 | bucket->bucket_ring = r; |
---|
| 100 | return bucket; |
---|
| 101 | } |
---|
| 102 | |
---|
| 103 | void sBucketDestroy(sBucket_pt *bucket) |
---|
| 104 | { |
---|
| 105 | assume(bucket != NULL); |
---|
| 106 | omFreeBin(*bucket, sBucket_bin); |
---|
| 107 | *bucket = NULL; |
---|
| 108 | } |
---|
| 109 | |
---|
[590f989] | 110 | void sBucketDeleteAndDestroy(sBucket_pt *bucket_pt) |
---|
| 111 | { |
---|
| 112 | sBucket_pt bucket = *bucket_pt; |
---|
| 113 | int i; |
---|
| 114 | for (i=0; i<= bucket->max_bucket; i++) |
---|
| 115 | { |
---|
[127208] | 116 | p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring); |
---|
[590f989] | 117 | } |
---|
| 118 | omFreeBin(bucket, sBucket_bin); |
---|
| 119 | *bucket_pt = NULL; |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | |
---|
[35aab3] | 123 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 124 | // Convertion from/to SBpolys |
---|
| 125 | // |
---|
| 126 | |
---|
[53b958] | 127 | void sBucket_Merge_m(sBucket_pt bucket, poly p) |
---|
[35aab3] | 128 | { |
---|
| 129 | assume(p != NULL && pNext(p) == NULL); |
---|
| 130 | int length = 1; |
---|
| 131 | int i = 0; |
---|
| 132 | |
---|
| 133 | while (bucket->buckets[i].p != NULL) |
---|
| 134 | { |
---|
| 135 | p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring); |
---|
| 136 | length += bucket->buckets[i].length; |
---|
| 137 | bucket->buckets[i].p = NULL; |
---|
| 138 | bucket->buckets[i].length = 0; |
---|
| 139 | i++; |
---|
[0803a18] | 140 | assume(SI_LOG2(length) == i); |
---|
[35aab3] | 141 | } |
---|
| 142 | |
---|
| 143 | bucket->buckets[i].p = p; |
---|
| 144 | bucket->buckets[i].length = length; |
---|
| 145 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 146 | } |
---|
| 147 | |
---|
[0d1a36] | 148 | void sBucket_Merge_p(sBucket_pt bucket, poly p, int length) |
---|
[35aab3] | 149 | { |
---|
| 150 | assume(bucket != NULL); |
---|
[d65075] | 151 | assume(length <= 0 || length == (int)pLength(p)); |
---|
[35aab3] | 152 | |
---|
| 153 | if (p == NULL) return; |
---|
[0d1a36] | 154 | if (length <= 0) length = pLength(p); |
---|
[35aab3] | 155 | |
---|
[0803a18] | 156 | int i = SI_LOG2(length); |
---|
[35aab3] | 157 | |
---|
| 158 | while (bucket->buckets[i].p != NULL) |
---|
| 159 | { |
---|
| 160 | p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring); |
---|
| 161 | length += bucket->buckets[i].length; |
---|
| 162 | bucket->buckets[i].p = NULL; |
---|
| 163 | bucket->buckets[i].length = 0; |
---|
| 164 | i++; |
---|
[0803a18] | 165 | assume(SI_LOG2(length) == i); |
---|
[35aab3] | 166 | } |
---|
| 167 | |
---|
| 168 | bucket->buckets[i].p = p; |
---|
| 169 | bucket->buckets[i].length = length; |
---|
| 170 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 171 | } |
---|
| 172 | |
---|
[53b958] | 173 | void sBucket_Add_m(sBucket_pt bucket, poly p) |
---|
| 174 | { |
---|
| 175 | assume(bucket != NULL); |
---|
| 176 | assume(1 == pLength(p)); |
---|
| 177 | |
---|
| 178 | int length = 1; |
---|
| 179 | |
---|
[0803a18] | 180 | int i = 0; //SI_LOG2(length); |
---|
[53b958] | 181 | |
---|
| 182 | while (bucket->buckets[i].p != NULL) |
---|
| 183 | { |
---|
[7abd61] | 184 | int shorter; |
---|
| 185 | p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, |
---|
| 186 | shorter, bucket->bucket_ring); |
---|
| 187 | length+=bucket->buckets[i].length-shorter; |
---|
[53b958] | 188 | bucket->buckets[i].p = NULL; |
---|
| 189 | bucket->buckets[i].length = 0; |
---|
| 190 | if (p==NULL) |
---|
| 191 | { |
---|
| 192 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 193 | return; |
---|
| 194 | } |
---|
[0803a18] | 195 | i = SI_LOG2(length); |
---|
[53b958] | 196 | } |
---|
| 197 | |
---|
| 198 | bucket->buckets[i].p = p; |
---|
| 199 | bucket->buckets[i].length = length; |
---|
| 200 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 201 | } |
---|
| 202 | |
---|
[0d1a36] | 203 | void sBucket_Add_p(sBucket_pt bucket, poly p, int length) |
---|
[35aab3] | 204 | { |
---|
| 205 | assume(bucket != NULL); |
---|
[d65075] | 206 | assume(length <= 0 || length == (int)pLength(p)); |
---|
[35aab3] | 207 | |
---|
| 208 | if (p == NULL) return; |
---|
[9ae5a3] | 209 | p_Test(p,bucket->bucket_ring); |
---|
[d65075] | 210 | if (length <= 0) length = (int)pLength(p); |
---|
[35aab3] | 211 | |
---|
[0803a18] | 212 | int i = SI_LOG2(length); |
---|
[35aab3] | 213 | |
---|
| 214 | while (bucket->buckets[i].p != NULL) |
---|
| 215 | { |
---|
[7abd61] | 216 | int shorter; |
---|
| 217 | p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter, |
---|
[35aab3] | 218 | bucket->bucket_ring); |
---|
[7abd61] | 219 | length+= bucket->buckets[i].length-shorter; |
---|
[35aab3] | 220 | bucket->buckets[i].p = NULL; |
---|
| 221 | bucket->buckets[i].length = 0; |
---|
[f56364] | 222 | if (p==NULL) |
---|
| 223 | { |
---|
| 224 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 225 | return; |
---|
| 226 | } |
---|
[0803a18] | 227 | i = SI_LOG2(length); |
---|
[35aab3] | 228 | } |
---|
| 229 | |
---|
| 230 | bucket->buckets[i].p = p; |
---|
| 231 | bucket->buckets[i].length = length; |
---|
| 232 | if (i > bucket->max_bucket) bucket->max_bucket = i; |
---|
| 233 | } |
---|
| 234 | |
---|
| 235 | // Converts SBpoly into a poly and clears bucket |
---|
| 236 | // i.e., afterwards SBpoly == 0 |
---|
| 237 | void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length) |
---|
| 238 | { |
---|
| 239 | poly pr = NULL; |
---|
| 240 | int lr = 0; |
---|
| 241 | int i = 0; |
---|
| 242 | |
---|
| 243 | while (bucket->buckets[i].p == NULL) |
---|
| 244 | { |
---|
| 245 | i++; |
---|
| 246 | if (i > bucket->max_bucket) goto done; |
---|
| 247 | } |
---|
| 248 | |
---|
| 249 | pr = bucket->buckets[i].p; |
---|
| 250 | lr = bucket->buckets[i].length; |
---|
| 251 | bucket->buckets[i].p = NULL; |
---|
| 252 | bucket->buckets[i].length = 0; |
---|
| 253 | i++; |
---|
| 254 | |
---|
| 255 | while (i <= bucket->max_bucket) |
---|
| 256 | { |
---|
| 257 | if (bucket->buckets[i].p != NULL) |
---|
| 258 | { |
---|
| 259 | pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring); |
---|
| 260 | lr += bucket->buckets[i].length; |
---|
| 261 | bucket->buckets[i].p = NULL; |
---|
| 262 | bucket->buckets[i].length = 0; |
---|
| 263 | } |
---|
| 264 | i++; |
---|
| 265 | } |
---|
| 266 | |
---|
| 267 | done: |
---|
| 268 | *p = pr; |
---|
| 269 | *length = lr; |
---|
| 270 | bucket->max_bucket = 0; |
---|
| 271 | } |
---|
| 272 | |
---|
| 273 | // Converts SBpoly into a poly and clears bucket |
---|
| 274 | // i.e., afterwards SBpoly == 0 |
---|
| 275 | void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length) |
---|
| 276 | { |
---|
| 277 | poly pr = NULL; |
---|
[0d1a36] | 278 | int lr = 0; |
---|
| 279 | int i = 0; |
---|
[35aab3] | 280 | |
---|
| 281 | while (bucket->buckets[i].p == NULL) |
---|
| 282 | { |
---|
[0b7fb8] | 283 | assume( bucket->buckets[i].length == 0 ); |
---|
[35aab3] | 284 | i++; |
---|
| 285 | if (i > bucket->max_bucket) goto done; |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | pr = bucket->buckets[i].p; |
---|
| 289 | lr = bucket->buckets[i].length; |
---|
[0b7fb8] | 290 | |
---|
| 291 | assume( pr != NULL && (lr > 0) ); |
---|
[75f460] | 292 | |
---|
[35aab3] | 293 | bucket->buckets[i].p = NULL; |
---|
| 294 | bucket->buckets[i].length = 0; |
---|
| 295 | i++; |
---|
| 296 | |
---|
| 297 | while (i <= bucket->max_bucket) |
---|
| 298 | { |
---|
| 299 | if (bucket->buckets[i].p != NULL) |
---|
| 300 | { |
---|
[0b7fb8] | 301 | assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) ); |
---|
[75f460] | 302 | |
---|
[35aab3] | 303 | pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length, |
---|
| 304 | bucket->bucket_ring); |
---|
[75f460] | 305 | |
---|
[35aab3] | 306 | bucket->buckets[i].p = NULL; |
---|
| 307 | bucket->buckets[i].length = 0; |
---|
| 308 | } |
---|
[0b7fb8] | 309 | |
---|
| 310 | assume( bucket->buckets[i].p == NULL ); |
---|
[75f460] | 311 | assume( bucket->buckets[i].length == 0 ); |
---|
[35aab3] | 312 | i++; |
---|
| 313 | } |
---|
| 314 | |
---|
[0b7fb8] | 315 | done: |
---|
[75f460] | 316 | |
---|
[35aab3] | 317 | *p = pr; |
---|
| 318 | *length = lr; |
---|
[75f460] | 319 | |
---|
[35aab3] | 320 | bucket->max_bucket = 0; |
---|
[0b7fb8] | 321 | |
---|
| 322 | assume( sIsEmpty(bucket) ); |
---|
[35aab3] | 323 | } |
---|
| 324 | |
---|
[0b7fb8] | 325 | |
---|
| 326 | |
---|
| 327 | |
---|
[35aab3] | 328 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 329 | // Sorts a poly using BucketSort |
---|
| 330 | // |
---|
| 331 | |
---|
[b0ae38] | 332 | poly sBucketSortMerge(poly p, const ring r) |
---|
[35aab3] | 333 | { |
---|
| 334 | if (p == NULL || pNext(p) == NULL) return p; |
---|
| 335 | |
---|
[caf8c6] | 336 | #ifndef SING_NDEBUG |
---|
| 337 | int l_in = pLength(p); |
---|
[f1182f] | 338 | #endif |
---|
[35aab3] | 339 | sBucket_pt bucket = sBucketCreate(r); |
---|
| 340 | poly pn = pNext(p); |
---|
| 341 | |
---|
| 342 | do |
---|
| 343 | { |
---|
| 344 | pNext(p) = NULL; |
---|
| 345 | sBucket_Merge_m(bucket, p); |
---|
| 346 | p = pn; |
---|
| 347 | if (p == NULL) break; |
---|
| 348 | pn = pNext(pn); |
---|
| 349 | } |
---|
| 350 | while (1); |
---|
| 351 | |
---|
| 352 | int l_dummy; |
---|
| 353 | sBucketClearMerge(bucket, &pn, &l_dummy); |
---|
| 354 | sBucketDestroy(&bucket); |
---|
| 355 | |
---|
| 356 | p_Test(pn, r); |
---|
[d65075] | 357 | assume(l_dummy == (int)pLength(pn)); |
---|
[52dbd6] | 358 | #ifndef SING_NDEBUG |
---|
[35aab3] | 359 | assume(l_in == l_dummy); |
---|
[52dbd6] | 360 | #endif |
---|
[35aab3] | 361 | return pn; |
---|
| 362 | } |
---|
| 363 | |
---|
| 364 | ///////////////////////////////////////////////////////////////////////////// |
---|
| 365 | // Sorts a poly using BucketSort |
---|
| 366 | // |
---|
| 367 | |
---|
[b0ae38] | 368 | poly sBucketSortAdd(poly p, const ring r) |
---|
[35aab3] | 369 | { |
---|
[caf8c6] | 370 | #ifndef SING_NDEBUG |
---|
[35aab3] | 371 | int l_in = pLength(p); |
---|
| 372 | #endif |
---|
| 373 | |
---|
| 374 | if (p == NULL || pNext(p) == NULL) return p; |
---|
| 375 | |
---|
| 376 | sBucket_pt bucket = sBucketCreate(r); |
---|
| 377 | poly pn = pNext(p); |
---|
| 378 | |
---|
| 379 | do |
---|
| 380 | { |
---|
| 381 | pNext(p) = NULL; |
---|
[53b958] | 382 | sBucket_Add_m(bucket, p); |
---|
[35aab3] | 383 | p = pn; |
---|
| 384 | if (p == NULL) break; |
---|
| 385 | pn = pNext(pn); |
---|
| 386 | } |
---|
| 387 | while (1); |
---|
| 388 | |
---|
| 389 | int l_dummy; |
---|
| 390 | sBucketClearAdd(bucket, &pn, &l_dummy); |
---|
| 391 | sBucketDestroy(&bucket); |
---|
| 392 | |
---|
| 393 | p_Test(pn, r); |
---|
[caf8c6] | 394 | #ifndef SING_NDEBUG |
---|
[d65075] | 395 | assume(l_dummy == (int)pLength(pn)); |
---|
[35aab3] | 396 | assume(l_in >= l_dummy); |
---|
| 397 | #endif |
---|
| 398 | return pn; |
---|
| 399 | } |
---|
[761e453] | 400 | |
---|
| 401 | void sBucketCanonicalize(sBucket_pt bucket) |
---|
| 402 | { |
---|
| 403 | poly pr = NULL; |
---|
| 404 | int lr = 0; |
---|
| 405 | int i = 0; |
---|
| 406 | |
---|
| 407 | while (bucket->buckets[i].p == NULL) |
---|
| 408 | { |
---|
| 409 | assume( bucket->buckets[i].length == 0 ); |
---|
| 410 | i++; |
---|
| 411 | if (i > bucket->max_bucket) goto done; |
---|
| 412 | } |
---|
| 413 | |
---|
| 414 | pr = bucket->buckets[i].p; |
---|
| 415 | lr = bucket->buckets[i].length; |
---|
| 416 | |
---|
| 417 | assume( pr != NULL && (lr > 0) ); |
---|
| 418 | |
---|
| 419 | bucket->buckets[i].p = NULL; |
---|
| 420 | bucket->buckets[i].length = 0; |
---|
| 421 | i++; |
---|
| 422 | |
---|
| 423 | while (i <= bucket->max_bucket) |
---|
| 424 | { |
---|
| 425 | if (bucket->buckets[i].p != NULL) |
---|
| 426 | { |
---|
[9ae5a3] | 427 | p_Test(pr,bucket->bucket_ring); |
---|
[761e453] | 428 | assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) ); |
---|
| 429 | |
---|
[9ae5a3] | 430 | p_Test(bucket->buckets[i].p,bucket->bucket_ring); |
---|
| 431 | //pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length, |
---|
| 432 | // bucket->bucket_ring); |
---|
| 433 | pr = p_Add_q(pr, bucket->buckets[i].p, bucket->bucket_ring); |
---|
[761e453] | 434 | |
---|
| 435 | bucket->buckets[i].p = NULL; |
---|
| 436 | bucket->buckets[i].length = 0; |
---|
| 437 | } |
---|
| 438 | |
---|
| 439 | assume( bucket->buckets[i].p == NULL ); |
---|
| 440 | assume( bucket->buckets[i].length == 0 ); |
---|
| 441 | i++; |
---|
| 442 | } |
---|
| 443 | |
---|
| 444 | done: |
---|
[9ae5a3] | 445 | lr=pLength(pr); |
---|
[761e453] | 446 | if (pr!=NULL) |
---|
| 447 | { |
---|
| 448 | i = SI_LOG2(lr); |
---|
| 449 | bucket->buckets[i].p = pr; |
---|
| 450 | bucket->buckets[i].length = lr; |
---|
| 451 | bucket->max_bucket = i; |
---|
| 452 | } |
---|
| 453 | } |
---|
| 454 | |
---|
[f1182f] | 455 | poly sBucketPeek(sBucket_pt b) |
---|
| 456 | { |
---|
| 457 | sBucketCanonicalize(b); |
---|
| 458 | return b->buckets[b->max_bucket].p; |
---|
| 459 | } |
---|
| 460 | |
---|
[761e453] | 461 | char* sBucketString(sBucket_pt bucket) |
---|
| 462 | { |
---|
[f1182f] | 463 | return (p_String(sBucketPeek(bucket),sBucketGetRing(bucket))); |
---|
[761e453] | 464 | } |
---|
| 465 | |
---|
| 466 | void sBucketPrint(sBucket_pt bucket) |
---|
| 467 | { |
---|
[f1182f] | 468 | p_Write0(sBucketPeek(bucket),sBucketGetRing(bucket)); |
---|
[761e453] | 469 | } |
---|
[f1182f] | 470 | |
---|