source: git/libpolys/polys/sbuckets.cc @ 0803a18

spielwiese
Last change on this file since 0803a18 was 0803a18, checked in by Hans Schoenemann <hannes@…>, 6 years ago
for SAGE: LOG2 -> SI_LOG2
  • Property mode set to 100644
File size: 8.5 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 "omalloc/omalloc.h"
12
13#include "misc/auxiliary.h"
14
15#include "polys/sbuckets.h"
16
17#include "polys/monomials/ring.h"
18#include "polys/monomials/p_polys.h"
19
20
21
22//////////////////////////////////////////////////////////////////////////
23// Declarations
24//
25
26class sBucketPoly
27{
28public:
29  poly p;
30  long length;
31};
32
33class sBucket
34{
35public:
36  ring          bucket_ring;
37  long          max_bucket;
38  sBucketPoly   buckets[BIT_SIZEOF_LONG - 3];
39}
40;
41
42static omBin sBucket_bin = omGetSpecBin(sizeof(sBucket));
43
44
45//////////////////////////////////////////////////////////////////////////
46// New API:
47//
48
49/// Returns bucket ring
50ring sBucketGetRing(const sBucket_pt bucket)
51{ return bucket->bucket_ring; }
52
53
54bool sIsEmpty(const sBucket_pt bucket)
55{
56  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
57  {
58    assume( i < (BIT_SIZEOF_LONG - 3) );
59    assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
60
61    if( bucket->buckets[i].p != NULL )
62      return false;
63
64    if( bucket->buckets[i].length != 0 )
65      return false;
66  }
67
68  return( bucket->max_bucket == 0 );
69
70}
71
72
73/// Copy sBucket non-intrusive!!!
74sBucket_pt    sBucketCopy(const sBucket_pt bucket)
75{
76  const ring r = bucket->bucket_ring;
77
78  sBucket_pt newbucket = sBucketCreate(r);
79
80  newbucket->max_bucket = bucket->max_bucket;
81
82  for(int i = 0; i <= bucket->max_bucket; i++)
83  {
84    assume( i < (BIT_SIZEOF_LONG - 3) );
85    assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
86
87    newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
88    newbucket->buckets[i].length = bucket->buckets[i].length;
89
90    assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
91  }
92
93  return newbucket;
94}
95
96//////////////////////////////////////////////////////////////////////////
97// Creation/Destruction of buckets
98//
99sBucket_pt    sBucketCreate(const ring r)
100{
101  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
102  bucket->bucket_ring = r;
103  return bucket;
104}
105
106void          sBucketDestroy(sBucket_pt *bucket)
107{
108  assume(bucket != NULL);
109  omFreeBin(*bucket, sBucket_bin);
110  *bucket = NULL;
111}
112
113void sBucketDeleteAndDestroy(sBucket_pt *bucket_pt)
114{
115  sBucket_pt bucket = *bucket_pt;
116  int i;
117  for (i=0; i<= bucket->max_bucket; i++)
118  {
119
120    if (bucket->buckets[i].p != NULL)
121    {
122      p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
123    }
124  }
125  omFreeBin(bucket, sBucket_bin);
126  *bucket_pt = NULL;
127}
128
129
130/////////////////////////////////////////////////////////////////////////////
131// Convertion from/to SBpolys
132//
133
134void sBucket_Merge_m(sBucket_pt bucket, poly p)
135{
136  assume(p != NULL && pNext(p) == NULL);
137  int length = 1;
138  int i = 0;
139
140  while (bucket->buckets[i].p != NULL)
141  {
142    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
143    length += bucket->buckets[i].length;
144    bucket->buckets[i].p = NULL;
145    bucket->buckets[i].length = 0;
146    i++;
147    assume(SI_LOG2(length) == i);
148  }
149
150  bucket->buckets[i].p = p;
151  bucket->buckets[i].length = length;
152  if (i > bucket->max_bucket) bucket->max_bucket = i;
153}
154
155void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
156{
157  assume(bucket != NULL);
158  assume(length <= 0 || length == pLength(p));
159
160  if (p == NULL) return;
161  if (length <= 0) length = pLength(p);
162
163  int i = SI_LOG2(length);
164
165  while (bucket->buckets[i].p != NULL)
166  {
167    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
168    length += bucket->buckets[i].length;
169    bucket->buckets[i].p = NULL;
170    bucket->buckets[i].length = 0;
171    i++;
172    assume(SI_LOG2(length) == i);
173  }
174
175  bucket->buckets[i].p = p;
176  bucket->buckets[i].length = length;
177  if (i > bucket->max_bucket) bucket->max_bucket = i;
178}
179
180void sBucket_Add_m(sBucket_pt bucket, poly p)
181{
182  assume(bucket != NULL);
183  assume(1 == pLength(p));
184
185  int length = 1;
186
187  int i = 0; //SI_LOG2(length);
188
189  while (bucket->buckets[i].p != NULL)
190  {
191    int shorter;
192    p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
193                shorter, bucket->bucket_ring);
194    length+=bucket->buckets[i].length-shorter;
195    bucket->buckets[i].p = NULL;
196    bucket->buckets[i].length = 0;
197    if (p==NULL)
198    {
199      if (i > bucket->max_bucket) bucket->max_bucket = i;
200      return;
201    }
202    i = SI_LOG2(length);
203  }
204
205  bucket->buckets[i].p = p;
206  bucket->buckets[i].length = length;
207  if (i > bucket->max_bucket) bucket->max_bucket = i;
208}
209
210void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
211{
212  assume(bucket != NULL);
213  assume(length <= 0 || length == pLength(p));
214
215  if (p == NULL) return;
216  if (length <= 0) length = pLength(p);
217
218  int i = SI_LOG2(length);
219
220  while (bucket->buckets[i].p != NULL)
221  {
222    int shorter;
223    p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
224                bucket->bucket_ring);
225    length+= bucket->buckets[i].length-shorter;
226    bucket->buckets[i].p = NULL;
227    bucket->buckets[i].length = 0;
228    if (p==NULL)
229    {
230      if (i > bucket->max_bucket) bucket->max_bucket = i;
231      return;
232    }
233    i = SI_LOG2(length);
234  }
235
236  bucket->buckets[i].p = p;
237  bucket->buckets[i].length = length;
238  if (i > bucket->max_bucket) bucket->max_bucket = i;
239}
240
241// Converts SBpoly into a poly and clears bucket
242// i.e., afterwards SBpoly == 0
243void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
244{
245  poly pr = NULL;
246  int  lr = 0;
247  int i = 0;
248
249  while (bucket->buckets[i].p == NULL)
250  {
251    i++;
252    if (i > bucket->max_bucket) goto done;
253  }
254
255  pr = bucket->buckets[i].p;
256  lr = bucket->buckets[i].length;
257  bucket->buckets[i].p = NULL;
258  bucket->buckets[i].length = 0;
259  i++;
260
261  while (i <= bucket->max_bucket)
262  {
263    if (bucket->buckets[i].p != NULL)
264    {
265      pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
266      lr += bucket->buckets[i].length;
267      bucket->buckets[i].p = NULL;
268      bucket->buckets[i].length = 0;
269    }
270    i++;
271  }
272
273  done:
274  *p = pr;
275  *length = lr;
276  bucket->max_bucket = 0;
277}
278
279// Converts SBpoly into a poly and clears bucket
280// i.e., afterwards SBpoly == 0
281void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
282{
283  poly pr = NULL;
284  int  lr = 0;
285  int i = 0;
286
287  while (bucket->buckets[i].p == NULL)
288  {
289    assume( bucket->buckets[i].length == 0 );
290    i++;
291    if (i > bucket->max_bucket) goto done;
292  }
293
294  pr = bucket->buckets[i].p;
295  lr = bucket->buckets[i].length;
296
297  assume( pr != NULL && (lr > 0) );
298
299  bucket->buckets[i].p = NULL;
300  bucket->buckets[i].length = 0;
301  i++;
302
303  while (i <= bucket->max_bucket)
304  {
305    if (bucket->buckets[i].p != NULL)
306    {
307      assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
308
309      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
310                   bucket->bucket_ring);
311
312      bucket->buckets[i].p = NULL;
313      bucket->buckets[i].length = 0;
314    }
315
316    assume( bucket->buckets[i].p == NULL );
317    assume( bucket->buckets[i].length == 0 );
318    i++;
319  }
320
321done:
322
323  *p = pr;
324  *length = lr;
325
326  bucket->max_bucket = 0;
327
328  assume( sIsEmpty(bucket) );
329}
330
331
332
333
334/////////////////////////////////////////////////////////////////////////////
335// Sorts a poly using BucketSort
336//
337
338poly sBucketSortMerge(poly p, const ring r)
339{
340#ifdef HAVE_ASSUME
341  int l_in = pLength(p);
342#endif
343
344  if (p == NULL || pNext(p) == NULL) return p;
345
346  sBucket_pt bucket = sBucketCreate(r);
347  poly pn = pNext(p);
348
349  do
350  {
351    pNext(p) = NULL;
352    sBucket_Merge_m(bucket, p);
353    p = pn;
354    if (p == NULL) break;
355    pn = pNext(pn);
356  }
357  while (1);
358
359  int l_dummy;
360  sBucketClearMerge(bucket, &pn, &l_dummy);
361  sBucketDestroy(&bucket);
362
363  p_Test(pn, r);
364#ifdef HAVE_ASSUME
365  assume(l_dummy == pLength(pn));
366  assume(l_in == l_dummy);
367#endif
368  return pn;
369}
370
371/////////////////////////////////////////////////////////////////////////////
372// Sorts a poly using BucketSort
373//
374
375poly sBucketSortAdd(poly p, const ring r)
376{
377#ifdef HAVE_ASSUME
378  int l_in = pLength(p);
379#endif
380
381  if (p == NULL || pNext(p) == NULL) return p;
382
383  sBucket_pt bucket = sBucketCreate(r);
384  poly pn = pNext(p);
385
386  do
387  {
388    pNext(p) = NULL;
389    sBucket_Add_m(bucket, p);
390    p = pn;
391    if (p == NULL) break;
392    pn = pNext(pn);
393  }
394  while (1);
395
396  int l_dummy;
397  sBucketClearAdd(bucket, &pn, &l_dummy);
398  sBucketDestroy(&bucket);
399
400  p_Test(pn, r);
401#ifdef HAVE_ASSUME
402  assume(l_dummy == pLength(pn));
403  assume(l_in >= l_dummy);
404#endif
405  return pn;
406}
Note: See TracBrowser for help on using the repository browser.