source: git/libpolys/polys/sbuckets.cc @ a3f0fea

spielwiese
Last change on this file since a3f0fea was a3f0fea, checked in by Reimer Behrends <behrends@…>, 5 years ago
Modify variable declarions for pSingular.
  • Property mode set to 100644
File size: 10.0 KB
Line 
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 "misc/auxiliary.h"
12
13#include "polys/sbuckets.h"
14
15#include "polys/monomials/ring.h"
16#include "polys/monomials/p_polys.h"
17
18//////////////////////////////////////////////////////////////////////////
19// Declarations
20//
21
22class sBucketPoly
23{
24public:
25  poly p;
26  long length;
27};
28
29class sBucket
30{
31public:
32  ring          bucket_ring;
33  long          max_bucket;
34  sBucketPoly   buckets[BIT_SIZEOF_LONG - 3];
35}
36;
37
38STATIC_VAR omBin sBucket_bin = omGetSpecBin(sizeof(sBucket));
39
40
41//////////////////////////////////////////////////////////////////////////
42// New API:
43//
44
45/// Returns bucket ring
46ring sBucketGetRing(const sBucket_pt bucket)
47{ return bucket->bucket_ring; }
48
49
50bool sIsEmpty(const sBucket_pt bucket)
51{
52  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
53  {
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
69/// Copy sBucket non-intrusive!!!
70sBucket_pt    sBucketCopy(const sBucket_pt bucket)
71{
72  sBucketCanonicalize(bucket);
73  const ring r = bucket->bucket_ring;
74
75  sBucket_pt newbucket = sBucketCreate(r);
76
77  newbucket->max_bucket = bucket->max_bucket;
78
79  for(int i = 0; i <= bucket->max_bucket; i++)
80  {
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
93//////////////////////////////////////////////////////////////////////////
94// Creation/Destruction of buckets
95//
96sBucket_pt    sBucketCreate(const ring r)
97{
98  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
99  bucket->bucket_ring = r;
100  return bucket;
101}
102
103void          sBucketDestroy(sBucket_pt *bucket)
104{
105  assume(bucket != NULL);
106  omFreeBin(*bucket, sBucket_bin);
107  *bucket = NULL;
108}
109
110void 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  {
116    p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
117  }
118  omFreeBin(bucket, sBucket_bin);
119  *bucket_pt = NULL;
120}
121
122
123/////////////////////////////////////////////////////////////////////////////
124// Convertion from/to SBpolys
125//
126
127void sBucket_Merge_m(sBucket_pt bucket, poly p)
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++;
140    assume(SI_LOG2(length) == i);
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
148void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
149{
150  assume(bucket != NULL);
151  assume(length <= 0 || length == pLength(p));
152
153  if (p == NULL) return;
154  if (length <= 0) length = pLength(p);
155
156  int i = SI_LOG2(length);
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++;
165    assume(SI_LOG2(length) == i);
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
173void sBucket_Add_m(sBucket_pt bucket, poly p)
174{
175  assume(bucket != NULL);
176  assume(1 == pLength(p));
177
178  int length = 1;
179
180  int i = 0; //SI_LOG2(length);
181
182  while (bucket->buckets[i].p != NULL)
183  {
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;
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    }
195    i = SI_LOG2(length);
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
203void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
204{
205  assume(bucket != NULL);
206  assume(length <= 0 || length == pLength(p));
207
208  if (p == NULL) return;
209  p_Test(p,bucket->bucket_ring);
210  if (length <= 0) length = pLength(p);
211
212  int i = SI_LOG2(length);
213
214  while (bucket->buckets[i].p != NULL)
215  {
216    int shorter;
217    p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
218                bucket->bucket_ring);
219    length+= bucket->buckets[i].length-shorter;
220    bucket->buckets[i].p = NULL;
221    bucket->buckets[i].length = 0;
222    if (p==NULL)
223    {
224      if (i > bucket->max_bucket) bucket->max_bucket = i;
225      return;
226    }
227    i = SI_LOG2(length);
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
237void 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
275void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
276{
277  poly pr = NULL;
278  int  lr = 0;
279  int i = 0;
280
281  while (bucket->buckets[i].p == NULL)
282  {
283    assume( bucket->buckets[i].length == 0 );
284    i++;
285    if (i > bucket->max_bucket) goto done;
286  }
287
288  pr = bucket->buckets[i].p;
289  lr = bucket->buckets[i].length;
290
291  assume( pr != NULL && (lr > 0) );
292
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    {
301      assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
302
303      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
304                   bucket->bucket_ring);
305
306      bucket->buckets[i].p = NULL;
307      bucket->buckets[i].length = 0;
308    }
309
310    assume( bucket->buckets[i].p == NULL );
311    assume( bucket->buckets[i].length == 0 );
312    i++;
313  }
314
315done:
316
317  *p = pr;
318  *length = lr;
319
320  bucket->max_bucket = 0;
321
322  assume( sIsEmpty(bucket) );
323}
324
325
326
327
328/////////////////////////////////////////////////////////////////////////////
329// Sorts a poly using BucketSort
330//
331
332poly sBucketSortMerge(poly p, const ring r)
333{
334  if (p == NULL || pNext(p) == NULL) return p;
335
336#ifndef SING_NDEBUG
337  int l_in = pLength(p);
338#endif
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);
357  assume(l_dummy == pLength(pn));
358#ifndef SING_NDEBUG
359  assume(l_in == l_dummy);
360#endif
361  return pn;
362}
363
364/////////////////////////////////////////////////////////////////////////////
365// Sorts a poly using BucketSort
366//
367
368poly 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
401void 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    {
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
444done:
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
455poly sBucketPeek(sBucket_pt b)
456{
457  sBucketCanonicalize(b);
458  return b->buckets[b->max_bucket].p;
459}
460
461char* sBucketString(sBucket_pt bucket)
462{
463  return (p_String(sBucketPeek(bucket),sBucketGetRing(bucket)));
464}
465
466void sBucketPrint(sBucket_pt bucket)
467{
468  p_Write0(sBucketPeek(bucket),sBucketGetRing(bucket));
469}
470
Note: See TracBrowser for help on using the repository browser.