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

fieker-DuValspielwiese
Last change on this file since bf6fa7 was 798f685, checked in by Hans Schoenemann <hannes@…>, 7 years ago
chg: LOG2 -> auxiliary.h, use in [s|k]buckets.cc, longrat.h
  • Property mode set to 100644
File size: 8.4 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(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 = 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(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; //LOG2(length);
188
189  while (bucket->buckets[i].p != NULL)
190  {
191    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
192                bucket->bucket_ring);
193    bucket->buckets[i].p = NULL;
194    bucket->buckets[i].length = 0;
195    if (p==NULL)
196    {
197      if (i > bucket->max_bucket) bucket->max_bucket = i;
198      return;
199    }
200    i = LOG2(length);
201  }
202
203  bucket->buckets[i].p = p;
204  bucket->buckets[i].length = length;
205  if (i > bucket->max_bucket) bucket->max_bucket = i;
206}
207
208void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
209{
210  assume(bucket != NULL);
211  assume(length <= 0 || length == pLength(p));
212
213  if (p == NULL) return;
214  if (length <= 0) length = pLength(p);
215
216  int i = LOG2(length);
217
218  while (bucket->buckets[i].p != NULL)
219  {
220    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
221                bucket->bucket_ring);
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 = 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#ifdef HAVE_ASSUME
337  int l_in = pLength(p);
338#endif
339
340  if (p == NULL || pNext(p) == NULL) return p;
341
342  sBucket_pt bucket = sBucketCreate(r);
343  poly pn = pNext(p);
344
345  do
346  {
347    pNext(p) = NULL;
348    sBucket_Merge_m(bucket, p);
349    p = pn;
350    if (p == NULL) break;
351    pn = pNext(pn);
352  }
353  while (1);
354
355  int l_dummy;
356  sBucketClearMerge(bucket, &pn, &l_dummy);
357  sBucketDestroy(&bucket);
358
359  p_Test(pn, r);
360#ifdef HAVE_ASSUME
361  assume(l_dummy == pLength(pn));
362  assume(l_in == l_dummy);
363#endif
364  return pn;
365}
366
367/////////////////////////////////////////////////////////////////////////////
368// Sorts a poly using BucketSort
369//
370
371poly sBucketSortAdd(poly p, const ring r)
372{
373#ifdef HAVE_ASSUME
374  int l_in = pLength(p);
375#endif
376
377  if (p == NULL || pNext(p) == NULL) return p;
378
379  sBucket_pt bucket = sBucketCreate(r);
380  poly pn = pNext(p);
381
382  do
383  {
384    pNext(p) = NULL;
385    sBucket_Add_m(bucket, p);
386    p = pn;
387    if (p == NULL) break;
388    pn = pNext(pn);
389  }
390  while (1);
391
392  int l_dummy;
393  sBucketClearAdd(bucket, &pn, &l_dummy);
394  sBucketDestroy(&bucket);
395
396  p_Test(pn, r);
397#ifdef HAVE_ASSUME
398  assume(l_dummy == pLength(pn));
399  assume(l_in >= l_dummy);
400#endif
401  return pn;
402}
Note: See TracBrowser for help on using the repository browser.