source: git/kernel/sbuckets.cc @ fec53d

fieker-DuValspielwiese
Last change on this file since fec53d was b1dfaf, checked in by Frank Seelisch <seelisch@…>, 14 years ago
patch from Kai (checked for problems under Windows OS: no problems) git-svn-id: file:///usr/local/Singular/svn/trunk@13210 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • 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 *  Version: $Id$
11 *******************************************************************/
12#include <kernel/mod2.h>
13
14#include <kernel/sbuckets.h>
15#include <omalloc/omalloc.h>
16#include <kernel/ring.h>
17#include <kernel/p_Procs.h>
18#include <kernel/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
50const ring sBucketGetRing(const sBucket_pt bucket)
51{ return bucket->bucket_ring; }
52
53/// Copy sBucket non-intrusive!!!
54sBucket_pt    sBucketCopy(const sBucket_pt bucket)
55{
56  const ring r = bucket->bucket_ring;
57
58  sBucket_pt newbucket = sBucketCreate(r);
59
60  for(int i = 0; bucket->buckets[i].p != NULL; i++)
61  {
62    assume( i < (BIT_SIZEOF_LONG - 3) );
63    assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
64
65    newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
66    newbucket->buckets[i].length = bucket->buckets[i].length;
67
68    assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
69  }
70
71  return newbucket;
72}
73
74/////////////////////////////////////////////////////////////////////////////
75// internal routines
76//
77// returns floor(log_2(i))
78static inline int LOG2(int i)
79{
80  assume (i > 0);
81  int j = 0;
82
83  do
84  {
85    i = i >> 1;
86    if (i == 0) return j;
87    j++;
88  }
89  while (1);
90
91  return j;
92}
93
94//////////////////////////////////////////////////////////////////////////
95// Creation/Destruction of buckets
96//
97sBucket_pt    sBucketCreate(ring r)
98{
99  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
100  bucket->bucket_ring = r;
101  return bucket;
102}
103
104void          sBucketDestroy(sBucket_pt *bucket)
105{
106  assume(bucket != NULL);
107  omFreeBin(*bucket, sBucket_bin);
108  *bucket = NULL;
109}
110
111void sBucketDeleteAndDestroy(sBucket_pt *bucket_pt)
112{
113  sBucket_pt bucket = *bucket_pt;
114  int i;
115  for (i=0; i<= bucket->max_bucket; i++)
116  {
117
118    if (bucket->buckets[i].p != NULL)
119    {
120      p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
121    }
122  }
123  omFreeBin(bucket, sBucket_bin);
124  *bucket_pt = NULL;
125}
126
127
128/////////////////////////////////////////////////////////////////////////////
129// Convertion from/to SBpolys
130//
131
132static void sBucket_Merge_m(sBucket_pt bucket, poly p)
133{
134  assume(p != NULL && pNext(p) == NULL);
135  int length = 1;
136  int i = 0;
137
138  while (bucket->buckets[i].p != NULL)
139  {
140    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
141    length += bucket->buckets[i].length;
142    bucket->buckets[i].p = NULL;
143    bucket->buckets[i].length = 0;
144    i++;
145    assume(LOG2(length) == i);
146  }
147
148  bucket->buckets[i].p = p;
149  bucket->buckets[i].length = length;
150  if (i > bucket->max_bucket) bucket->max_bucket = i;
151}
152
153void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
154{
155  assume(bucket != NULL);
156  assume(length <= 0 || length == pLength(p));
157
158  if (p == NULL) return;
159  if (length <= 0) length = pLength(p);
160
161  int i = LOG2(length);
162
163  while (bucket->buckets[i].p != NULL)
164  {
165    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
166    length += bucket->buckets[i].length;
167    bucket->buckets[i].p = NULL;
168    bucket->buckets[i].length = 0;
169    i++;
170    assume(LOG2(length) == i);
171  }
172
173  bucket->buckets[i].p = p;
174  bucket->buckets[i].length = length;
175  if (i > bucket->max_bucket) bucket->max_bucket = i;
176}
177
178void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
179{
180  assume(bucket != NULL);
181  assume(length <= 0 || length == pLength(p));
182
183  if (p == NULL) return;
184  if (length <= 0) length = pLength(p);
185
186  int i = LOG2(length);
187
188  while (bucket->buckets[i].p != NULL)
189  {
190    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
191                bucket->bucket_ring);
192    bucket->buckets[i].p = NULL;
193    bucket->buckets[i].length = 0;
194    if (p==NULL)
195    {
196      if (i > bucket->max_bucket) bucket->max_bucket = i;
197      return;
198    }
199    i = LOG2(length);
200  }
201
202  bucket->buckets[i].p = p;
203  bucket->buckets[i].length = length;
204  if (i > bucket->max_bucket) bucket->max_bucket = i;
205}
206
207// Converts SBpoly into a poly and clears bucket
208// i.e., afterwards SBpoly == 0
209void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
210{
211  poly pr = NULL;
212  int  lr = 0;
213  int i = 0;
214
215  while (bucket->buckets[i].p == NULL)
216  {
217    i++;
218    if (i > bucket->max_bucket) goto done;
219  }
220
221  pr = bucket->buckets[i].p;
222  lr = bucket->buckets[i].length;
223  bucket->buckets[i].p = NULL;
224  bucket->buckets[i].length = 0;
225  i++;
226
227  while (i <= bucket->max_bucket)
228  {
229    if (bucket->buckets[i].p != NULL)
230    {
231      pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
232      lr += bucket->buckets[i].length;
233      bucket->buckets[i].p = NULL;
234      bucket->buckets[i].length = 0;
235    }
236    i++;
237  }
238
239  done:
240  *p = pr;
241  *length = lr;
242  bucket->max_bucket = 0;
243}
244
245// Converts SBpoly into a poly and clears bucket
246// i.e., afterwards SBpoly == 0
247void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
248{
249  poly pr = NULL;
250  int  lr = 0;
251  int i = 0;
252
253  while (bucket->buckets[i].p == NULL)
254  {
255    i++;
256    if (i > bucket->max_bucket) goto done;
257  }
258
259  pr = bucket->buckets[i].p;
260  lr = bucket->buckets[i].length;
261  bucket->buckets[i].p = NULL;
262  bucket->buckets[i].length = 0;
263  i++;
264
265  while (i <= bucket->max_bucket)
266  {
267    if (bucket->buckets[i].p != NULL)
268    {
269      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
270                   bucket->bucket_ring);
271      bucket->buckets[i].p = NULL;
272      bucket->buckets[i].length = 0;
273    }
274    i++;
275  }
276
277  done:
278  *p = pr;
279  *length = lr;
280  bucket->max_bucket = 0;
281}
282
283/////////////////////////////////////////////////////////////////////////////
284// Sorts a poly using BucketSort
285//
286
287poly sBucketSortMerge(poly p, ring r)
288{
289#ifdef HAVE_ASSUME
290  int l_in = pLength(p);
291#endif
292
293  if (p == NULL || pNext(p) == NULL) return p;
294
295  sBucket_pt bucket = sBucketCreate(r);
296  poly pn = pNext(p);
297
298  do
299  {
300    pNext(p) = NULL;
301    sBucket_Merge_m(bucket, p);
302    p = pn;
303    if (p == NULL) break;
304    pn = pNext(pn);
305  }
306  while (1);
307
308  int l_dummy;
309  sBucketClearMerge(bucket, &pn, &l_dummy);
310  sBucketDestroy(&bucket);
311
312  p_Test(pn, r);
313#ifdef HAVE_ASSUME
314  assume(l_dummy == pLength(pn));
315  assume(l_in == l_dummy);
316#endif
317  return pn;
318}
319
320/////////////////////////////////////////////////////////////////////////////
321// Sorts a poly using BucketSort
322//
323
324poly sBucketSortAdd(poly p, ring r)
325{
326#ifdef HAVE_ASSUME
327  int l_in = pLength(p);
328#endif
329
330  if (p == NULL || pNext(p) == NULL) return p;
331
332  sBucket_pt bucket = sBucketCreate(r);
333  poly pn = pNext(p);
334
335  do
336  {
337    pNext(p) = NULL;
338    sBucket_Add_p(bucket, p, 1);
339    p = pn;
340    if (p == NULL) break;
341    pn = pNext(pn);
342  }
343  while (1);
344
345  int l_dummy;
346  sBucketClearAdd(bucket, &pn, &l_dummy);
347  sBucketDestroy(&bucket);
348
349  p_Test(pn, r);
350#ifdef HAVE_ASSUME
351  assume(l_dummy == pLength(pn));
352  assume(l_in >= l_dummy);
353#endif
354  return pn;
355}
Note: See TracBrowser for help on using the repository browser.