My Project  UNKNOWN_GIT_VERSION
sbuckets.cc
Go to the documentation of this file.
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  *******************************************************************/
11 #include "omalloc/omalloc.h"
12 
13 #include "misc/auxiliary.h"
14 
15 #include "polys/sbuckets.h"
16 
17 #include "polys/monomials/ring.h"
19 
20 //////////////////////////////////////////////////////////////////////////
21 // Declarations
22 //
23 
25 {
26 public:
27  poly p;
28  long length;
29 };
30 
31 class sBucket
32 {
33 public:
35  long max_bucket;
37 }
38 ;
39 
41 
42 
43 //////////////////////////////////////////////////////////////////////////
44 // New API:
45 //
46 
47 /// Returns bucket ring
48 ring sBucketGetRing(const sBucket_pt bucket)
49 { return bucket->bucket_ring; }
50 
51 
52 bool sIsEmpty(const sBucket_pt bucket)
53 {
54  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
55  {
56  assume( i < (BIT_SIZEOF_LONG - 3) );
57  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
58 
59  if( bucket->buckets[i].p != NULL )
60  return false;
61 
62  if( bucket->buckets[i].length != 0 )
63  return false;
64  }
65 
66  return( bucket->max_bucket == 0 );
67 
68 }
69 
70 
71 /// Copy sBucket non-intrusive!!!
73 {
74  sBucketCanonicalize(bucket);
75  const ring r = bucket->bucket_ring;
76 
77  sBucket_pt newbucket = sBucketCreate(r);
78 
79  newbucket->max_bucket = bucket->max_bucket;
80 
81  for(int i = 0; i <= bucket->max_bucket; i++)
82  {
83  assume( i < (BIT_SIZEOF_LONG - 3) );
84  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
85 
86  newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
87  newbucket->buckets[i].length = bucket->buckets[i].length;
88 
89  assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
90  }
91 
92  return newbucket;
93 }
94 
95 //////////////////////////////////////////////////////////////////////////
96 // Creation/Destruction of buckets
97 //
99 {
101  bucket->bucket_ring = r;
102  return bucket;
103 }
104 
106 {
107  assume(bucket != NULL);
108  omFreeBin(*bucket, sBucket_bin);
109  *bucket = NULL;
110 }
111 
113 {
114  sBucket_pt bucket = *bucket_pt;
115  int i;
116  for (i=0; i<= bucket->max_bucket; i++)
117  {
118  p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
119  }
120  omFreeBin(bucket, sBucket_bin);
121  *bucket_pt = NULL;
122 }
123 
124 
125 /////////////////////////////////////////////////////////////////////////////
126 // Convertion from/to SBpolys
127 //
128 
129 void sBucket_Merge_m(sBucket_pt bucket, poly p)
130 {
131  assume(p != NULL && pNext(p) == NULL);
132  int length = 1;
133  int i = 0;
134 
135  while (bucket->buckets[i].p != NULL)
136  {
137  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
138  length += bucket->buckets[i].length;
139  bucket->buckets[i].p = NULL;
140  bucket->buckets[i].length = 0;
141  i++;
142  assume(SI_LOG2(length) == i);
143  }
144 
145  bucket->buckets[i].p = p;
146  bucket->buckets[i].length = length;
147  if (i > bucket->max_bucket) bucket->max_bucket = i;
148 }
149 
150 void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
151 {
152  assume(bucket != NULL);
153  assume(length <= 0 || length == pLength(p));
154 
155  if (p == NULL) return;
156  if (length <= 0) length = pLength(p);
157 
158  int i = SI_LOG2(length);
159 
160  while (bucket->buckets[i].p != NULL)
161  {
162  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
163  length += bucket->buckets[i].length;
164  bucket->buckets[i].p = NULL;
165  bucket->buckets[i].length = 0;
166  i++;
167  assume(SI_LOG2(length) == i);
168  }
169 
170  bucket->buckets[i].p = p;
171  bucket->buckets[i].length = length;
172  if (i > bucket->max_bucket) bucket->max_bucket = i;
173 }
174 
175 void sBucket_Add_m(sBucket_pt bucket, poly p)
176 {
177  assume(bucket != NULL);
178  assume(1 == pLength(p));
179 
180  int length = 1;
181 
182  int i = 0; //SI_LOG2(length);
183 
184  while (bucket->buckets[i].p != NULL)
185  {
186  int shorter;
187  p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
188  shorter, bucket->bucket_ring);
189  length+=bucket->buckets[i].length-shorter;
190  bucket->buckets[i].p = NULL;
191  bucket->buckets[i].length = 0;
192  if (p==NULL)
193  {
194  if (i > bucket->max_bucket) bucket->max_bucket = i;
195  return;
196  }
197  i = SI_LOG2(length);
198  }
199 
200  bucket->buckets[i].p = p;
201  bucket->buckets[i].length = length;
202  if (i > bucket->max_bucket) bucket->max_bucket = i;
203 }
204 
205 void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
206 {
207  assume(bucket != NULL);
208  assume(length <= 0 || length == pLength(p));
209 
210  if (p == NULL) return;
211  p_Test(p,bucket->bucket_ring);
212  if (length <= 0) length = pLength(p);
213 
214  int i = SI_LOG2(length);
215 
216  while (bucket->buckets[i].p != NULL)
217  {
218  int shorter;
219  p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
220  bucket->bucket_ring);
221  length+= bucket->buckets[i].length-shorter;
222  bucket->buckets[i].p = NULL;
223  bucket->buckets[i].length = 0;
224  if (p==NULL)
225  {
226  if (i > bucket->max_bucket) bucket->max_bucket = i;
227  return;
228  }
229  i = SI_LOG2(length);
230  }
231 
232  bucket->buckets[i].p = p;
233  bucket->buckets[i].length = length;
234  if (i > bucket->max_bucket) bucket->max_bucket = i;
235 }
236 
237 // Converts SBpoly into a poly and clears bucket
238 // i.e., afterwards SBpoly == 0
239 void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
240 {
241  poly pr = NULL;
242  int lr = 0;
243  int i = 0;
244 
245  while (bucket->buckets[i].p == NULL)
246  {
247  i++;
248  if (i > bucket->max_bucket) goto done;
249  }
250 
251  pr = bucket->buckets[i].p;
252  lr = bucket->buckets[i].length;
253  bucket->buckets[i].p = NULL;
254  bucket->buckets[i].length = 0;
255  i++;
256 
257  while (i <= bucket->max_bucket)
258  {
259  if (bucket->buckets[i].p != NULL)
260  {
261  pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
262  lr += bucket->buckets[i].length;
263  bucket->buckets[i].p = NULL;
264  bucket->buckets[i].length = 0;
265  }
266  i++;
267  }
268 
269  done:
270  *p = pr;
271  *length = lr;
272  bucket->max_bucket = 0;
273 }
274 
275 // Converts SBpoly into a poly and clears bucket
276 // i.e., afterwards SBpoly == 0
277 void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
278 {
279  poly pr = NULL;
280  int lr = 0;
281  int i = 0;
282 
283  while (bucket->buckets[i].p == NULL)
284  {
285  assume( bucket->buckets[i].length == 0 );
286  i++;
287  if (i > bucket->max_bucket) goto done;
288  }
289 
290  pr = bucket->buckets[i].p;
291  lr = bucket->buckets[i].length;
292 
293  assume( pr != NULL && (lr > 0) );
294 
295  bucket->buckets[i].p = NULL;
296  bucket->buckets[i].length = 0;
297  i++;
298 
299  while (i <= bucket->max_bucket)
300  {
301  if (bucket->buckets[i].p != NULL)
302  {
303  assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
304 
305  pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
306  bucket->bucket_ring);
307 
308  bucket->buckets[i].p = NULL;
309  bucket->buckets[i].length = 0;
310  }
311 
312  assume( bucket->buckets[i].p == NULL );
313  assume( bucket->buckets[i].length == 0 );
314  i++;
315  }
316 
317 done:
318 
319  *p = pr;
320  *length = lr;
321 
322  bucket->max_bucket = 0;
323 
324  assume( sIsEmpty(bucket) );
325 }
326 
327 
328 
329 
330 /////////////////////////////////////////////////////////////////////////////
331 // Sorts a poly using BucketSort
332 //
333 
334 poly sBucketSortMerge(poly p, const ring r)
335 {
336  if (p == NULL || pNext(p) == NULL) return p;
337 
338 #ifndef SING_NDEBUG
339  int l_in = pLength(p);
340 #endif
341  sBucket_pt bucket = sBucketCreate(r);
342  poly pn = pNext(p);
343 
344  do
345  {
346  pNext(p) = NULL;
347  sBucket_Merge_m(bucket, p);
348  p = pn;
349  if (p == NULL) break;
350  pn = pNext(pn);
351  }
352  while (1);
353 
354  int l_dummy;
355  sBucketClearMerge(bucket, &pn, &l_dummy);
356  sBucketDestroy(&bucket);
357 
358  p_Test(pn, r);
359  assume(l_dummy == pLength(pn));
360  assume(l_in == l_dummy);
361  return pn;
362 }
363 
364 /////////////////////////////////////////////////////////////////////////////
365 // Sorts a poly using BucketSort
366 //
367 
368 poly sBucketSortAdd(poly p, const ring r)
369 {
370 #ifndef SING_NDEBUG
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;
382  sBucket_Add_m(bucket, p);
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);
394 #ifndef SING_NDEBUG
395  assume(l_dummy == pLength(pn));
396  assume(l_in >= l_dummy);
397 #endif
398  return pn;
399 }
400 
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  {
427  p_Test(pr,bucket->bucket_ring);
428  assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
429 
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);
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:
445  lr=pLength(pr);
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 
456 {
458  return b->buckets[b->max_bucket].p;
459 }
460 
462 {
463  return (p_String(sBucketPeek(bucket),sBucketGetRing(bucket)));
464 }
465 
467 {
468  p_Write0(sBucketPeek(bucket),sBucketGetRing(bucket));
469 }
470 
omBin_t * omBin
Definition: omStructs.h:12
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:36
char * p_String(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:184
void sBucketPrint(sBucket_pt bucket)
Definition: sbuckets.cc:466
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:205
long max_bucket
Definition: sbuckets.cc:35
long length
Definition: sbuckets.cc:28
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:813
poly sBucketSortMerge(poly p, const ring r)
Sorts p with bucketSort: assumes all monomials of p are different.
Definition: sbuckets.cc:334
CanonicalForm b
Definition: cfModGcd.cc:4044
poly sBucketSortAdd(poly p, const ring r)
Sorts p with bucketSort: p may have equal monomials.
Definition: sbuckets.cc:368
void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!
Definition: sbuckets.cc:150
#define assume(x)
Definition: mod2.h:390
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:105
sBucket * sBucket_pt
Definition: sbuckets.h:16
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:98
All the auxiliary stuff.
int i
Definition: cfEzgcd.cc:125
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:239
static unsigned pLength(poly a)
Definition: p_polys.h:193
static omBin sBucket_bin
Definition: sbuckets.cc:40
#define p_Test(p, r)
Definition: p_polys.h:164
ring bucket_ring
Definition: sbuckets.cc:34
void p_Write0(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:194
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omGetSpecBin(size)
Definition: omBin.h:11
void sBucketCanonicalize(sBucket_pt bucket)
Definition: sbuckets.cc:401
ring sBucketGetRing(const sBucket_pt bucket)
Returns bucket ring.
Definition: sbuckets.cc:48
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1149
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
char * sBucketString(sBucket_pt bucket)
Definition: sbuckets.cc:461
void sBucketDeleteAndDestroy(sBucket_pt *bucket_pt)
Definition: sbuckets.cc:112
#define pNext(p)
Definition: monomials.h:37
poly sBucketPeek(sBucket_pt b)
Definition: sbuckets.cc:455
void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:129
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:78
static int SI_LOG2(int v)
Definition: auxiliary.h:119
int p
Definition: cfModGcd.cc:4019
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:52
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:893
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
void sBucket_Add_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:175
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:277
sBucket_pt sBucketCopy(const sBucket_pt bucket)
Copy sBucket non-intrusive!!!
Definition: sbuckets.cc:72