source: git/libpolys/polys/sbuckets.cc @ 85bcd6

jengelh-datetimespielwiese
Last change on this file since 85bcd6 was 6ce030f, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
removal of the $Id$ svn tag from everywhere NOTE: the git SHA1 may be used instead (only on special places) NOTE: the libraries Singular/LIB/*.lib still contain the marker due to our current use of svn
  • Property mode set to 100644
File size: 7.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 <kernel/mod2.h>
12
13#include <polys/sbuckets.h>
14#include <omalloc/omalloc.h>
15#include <polys/monomials/ring.h>
16//#include <kernel/p_Procs.h>
17#include <polys/monomials//p_polys.h>
18
19
20
21//////////////////////////////////////////////////////////////////////////
22// Declarations
23//
24
25class sBucketPoly
26{
27public:
28  poly p;
29  long length;
30};
31
32class sBucket
33{
34public:
35  ring          bucket_ring;
36  long          max_bucket;
37  sBucketPoly   buckets[BIT_SIZEOF_LONG - 3];
38}
39;
40
41static omBin sBucket_bin = omGetSpecBin(sizeof(sBucket));
42
43
44//////////////////////////////////////////////////////////////////////////
45// New API:
46//
47
48/// Returns bucket ring
49ring sBucketGetRing(const sBucket_pt bucket)
50{ return bucket->bucket_ring; }
51
52/// Copy sBucket non-intrusive!!!
53sBucket_pt    sBucketCopy(const sBucket_pt bucket)
54{
55  const ring r = bucket->bucket_ring;
56
57  sBucket_pt newbucket = sBucketCreate(r);
58
59  for(int i = 0; bucket->buckets[i].p != NULL; i++)
60  {
61    assume( i < (BIT_SIZEOF_LONG - 3) );
62    assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
63
64    newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
65    newbucket->buckets[i].length = bucket->buckets[i].length;
66
67    assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
68  }
69
70  return newbucket;
71}
72
73/////////////////////////////////////////////////////////////////////////////
74// internal routines
75//
76// returns floor(log_2(i))
77static inline int LOG2(int i)
78{
79  assume (i > 0);
80  int j = 0;
81
82  do
83  {
84    i = i >> 1;
85    if (i == 0) return j;
86    j++;
87  }
88  while (1);
89
90  return j;
91}
92
93//////////////////////////////////////////////////////////////////////////
94// Creation/Destruction of buckets
95//
96sBucket_pt    sBucketCreate(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
117    if (bucket->buckets[i].p != NULL)
118    {
119      p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
120    }
121  }
122  omFreeBin(bucket, sBucket_bin);
123  *bucket_pt = NULL;
124}
125
126
127/////////////////////////////////////////////////////////////////////////////
128// Convertion from/to SBpolys
129//
130
131static void sBucket_Merge_m(sBucket_pt bucket, poly p)
132{
133  assume(p != NULL && pNext(p) == NULL);
134  int length = 1;
135  int i = 0;
136
137  while (bucket->buckets[i].p != NULL)
138  {
139    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
140    length += bucket->buckets[i].length;
141    bucket->buckets[i].p = NULL;
142    bucket->buckets[i].length = 0;
143    i++;
144    assume(LOG2(length) == i);
145  }
146
147  bucket->buckets[i].p = p;
148  bucket->buckets[i].length = length;
149  if (i > bucket->max_bucket) bucket->max_bucket = i;
150}
151
152void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
153{
154  assume(bucket != NULL);
155  assume(length <= 0 || length == pLength(p));
156
157  if (p == NULL) return;
158  if (length <= 0) length = pLength(p);
159
160  int i = LOG2(length);
161
162  while (bucket->buckets[i].p != NULL)
163  {
164    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
165    length += bucket->buckets[i].length;
166    bucket->buckets[i].p = NULL;
167    bucket->buckets[i].length = 0;
168    i++;
169    assume(LOG2(length) == i);
170  }
171
172  bucket->buckets[i].p = p;
173  bucket->buckets[i].length = length;
174  if (i > bucket->max_bucket) bucket->max_bucket = i;
175}
176
177void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
178{
179  assume(bucket != NULL);
180  assume(length <= 0 || length == pLength(p));
181
182  if (p == NULL) return;
183  if (length <= 0) length = pLength(p);
184
185  int i = LOG2(length);
186
187  while (bucket->buckets[i].p != NULL)
188  {
189    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
190                bucket->bucket_ring);
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 = 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
206// Converts SBpoly into a poly and clears bucket
207// i.e., afterwards SBpoly == 0
208void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
209{
210  poly pr = NULL;
211  int  lr = 0;
212  int i = 0;
213
214  while (bucket->buckets[i].p == NULL)
215  {
216    i++;
217    if (i > bucket->max_bucket) goto done;
218  }
219
220  pr = bucket->buckets[i].p;
221  lr = bucket->buckets[i].length;
222  bucket->buckets[i].p = NULL;
223  bucket->buckets[i].length = 0;
224  i++;
225
226  while (i <= bucket->max_bucket)
227  {
228    if (bucket->buckets[i].p != NULL)
229    {
230      pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
231      lr += bucket->buckets[i].length;
232      bucket->buckets[i].p = NULL;
233      bucket->buckets[i].length = 0;
234    }
235    i++;
236  }
237
238  done:
239  *p = pr;
240  *length = lr;
241  bucket->max_bucket = 0;
242}
243
244// Converts SBpoly into a poly and clears bucket
245// i.e., afterwards SBpoly == 0
246void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
247{
248  poly pr = NULL;
249  int  lr = 0;
250  int i = 0;
251
252  while (bucket->buckets[i].p == NULL)
253  {
254    i++;
255    if (i > bucket->max_bucket) goto done;
256  }
257
258  pr = bucket->buckets[i].p;
259  lr = bucket->buckets[i].length;
260  bucket->buckets[i].p = NULL;
261  bucket->buckets[i].length = 0;
262  i++;
263
264  while (i <= bucket->max_bucket)
265  {
266    if (bucket->buckets[i].p != NULL)
267    {
268      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
269                   bucket->bucket_ring);
270      bucket->buckets[i].p = NULL;
271      bucket->buckets[i].length = 0;
272    }
273    i++;
274  }
275
276  done:
277  *p = pr;
278  *length = lr;
279  bucket->max_bucket = 0;
280}
281
282/////////////////////////////////////////////////////////////////////////////
283// Sorts a poly using BucketSort
284//
285
286poly sBucketSortMerge(poly p, ring r)
287{
288#ifdef HAVE_ASSUME
289  int l_in = pLength(p);
290#endif
291
292  if (p == NULL || pNext(p) == NULL) return p;
293
294  sBucket_pt bucket = sBucketCreate(r);
295  poly pn = pNext(p);
296
297  do
298  {
299    pNext(p) = NULL;
300    sBucket_Merge_m(bucket, p);
301    p = pn;
302    if (p == NULL) break;
303    pn = pNext(pn);
304  }
305  while (1);
306
307  int l_dummy;
308  sBucketClearMerge(bucket, &pn, &l_dummy);
309  sBucketDestroy(&bucket);
310
311  p_Test(pn, r);
312#ifdef HAVE_ASSUME
313  assume(l_dummy == pLength(pn));
314  assume(l_in == l_dummy);
315#endif
316  return pn;
317}
318
319/////////////////////////////////////////////////////////////////////////////
320// Sorts a poly using BucketSort
321//
322
323poly sBucketSortAdd(poly p, ring r)
324{
325#ifdef HAVE_ASSUME
326  int l_in = pLength(p);
327#endif
328
329  if (p == NULL || pNext(p) == NULL) return p;
330
331  sBucket_pt bucket = sBucketCreate(r);
332  poly pn = pNext(p);
333
334  do
335  {
336    pNext(p) = NULL;
337    sBucket_Add_p(bucket, p, 1);
338    p = pn;
339    if (p == NULL) break;
340    pn = pNext(pn);
341  }
342  while (1);
343
344  int l_dummy;
345  sBucketClearAdd(bucket, &pn, &l_dummy);
346  sBucketDestroy(&bucket);
347
348  p_Test(pn, r);
349#ifdef HAVE_ASSUME
350  assume(l_dummy == pLength(pn));
351  assume(l_in >= l_dummy);
352#endif
353  return pn;
354}
Note: See TracBrowser for help on using the repository browser.