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

spielwiese
Last change on this file since caf8c6 was caf8c6, checked in by Hans Schoenemann <hannes@…>, 6 years ago
chg: HAVE_ASSUME -> !SING_NDEBUG
  • 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    p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
120  }
121  omFreeBin(bucket, sBucket_bin);
122  *bucket_pt = NULL;
123}
124
125
126/////////////////////////////////////////////////////////////////////////////
127// Convertion from/to SBpolys
128//
129
130void sBucket_Merge_m(sBucket_pt bucket, poly p)
131{
132  assume(p != NULL && pNext(p) == NULL);
133  int length = 1;
134  int i = 0;
135
136  while (bucket->buckets[i].p != NULL)
137  {
138    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
139    length += bucket->buckets[i].length;
140    bucket->buckets[i].p = NULL;
141    bucket->buckets[i].length = 0;
142    i++;
143    assume(SI_LOG2(length) == i);
144  }
145
146  bucket->buckets[i].p = p;
147  bucket->buckets[i].length = length;
148  if (i > bucket->max_bucket) bucket->max_bucket = i;
149}
150
151void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
152{
153  assume(bucket != NULL);
154  assume(length <= 0 || length == pLength(p));
155
156  if (p == NULL) return;
157  if (length <= 0) length = pLength(p);
158
159  int i = SI_LOG2(length);
160
161  while (bucket->buckets[i].p != NULL)
162  {
163    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
164    length += bucket->buckets[i].length;
165    bucket->buckets[i].p = NULL;
166    bucket->buckets[i].length = 0;
167    i++;
168    assume(SI_LOG2(length) == i);
169  }
170
171  bucket->buckets[i].p = p;
172  bucket->buckets[i].length = length;
173  if (i > bucket->max_bucket) bucket->max_bucket = i;
174}
175
176void sBucket_Add_m(sBucket_pt bucket, poly p)
177{
178  assume(bucket != NULL);
179  assume(1 == pLength(p));
180
181  int length = 1;
182
183  int i = 0; //SI_LOG2(length);
184
185  while (bucket->buckets[i].p != NULL)
186  {
187    int shorter;
188    p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
189                shorter, bucket->bucket_ring);
190    length+=bucket->buckets[i].length-shorter;
191    bucket->buckets[i].p = NULL;
192    bucket->buckets[i].length = 0;
193    if (p==NULL)
194    {
195      if (i > bucket->max_bucket) bucket->max_bucket = i;
196      return;
197    }
198    i = SI_LOG2(length);
199  }
200
201  bucket->buckets[i].p = p;
202  bucket->buckets[i].length = length;
203  if (i > bucket->max_bucket) bucket->max_bucket = i;
204}
205
206void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
207{
208  assume(bucket != NULL);
209  assume(length <= 0 || length == pLength(p));
210
211  if (p == NULL) return;
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
239void 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
277void 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
317done:
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
334poly 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
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}
Note: See TracBrowser for help on using the repository browser.