source: git/kernel/sbuckets.cc @ 5fdd0f

spielwiese
Last change on this file since 5fdd0f was f56364, checked in by Viktor Levandovskyy <levandov@…>, 20 years ago
*levandov: noncomm preimage fixed, buckets fixed git-svn-id: file:///usr/local/Singular/svn/trunk@7186 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 6.3 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: sbuckets.cc,v 1.2 2004-05-14 16:26:06 levandov Exp $
11 *******************************************************************/
12#include "mod2.h"
13
14#include "sbuckets.h"
15#include "omalloc.h"
16#include "ring.h"
17#include "p_Procs.h"
18#include "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// internal routines
46//
47// returns floor(log_2(i))
48inline int LOG2(int i)
49{
50  assume (i > 0);
51  int j = 0;
52
53  do
54  {
55    i = i >> 1;
56    if (i == 0) return j;
57    j++;
58  }
59  while (1);
60
61  return j;
62}
63
64//////////////////////////////////////////////////////////////////////////
65// Creation/Destruction of buckets
66//
67sBucket_pt    sBucketCreate(ring r)
68{
69  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
70  bucket->bucket_ring = r;
71  return bucket;
72}
73
74void          sBucketDestroy(sBucket_pt *bucket)
75{
76  assume(bucket != NULL);
77  omFreeBin(*bucket, sBucket_bin);
78  *bucket = NULL;
79}
80
81/////////////////////////////////////////////////////////////////////////////
82// Convertion from/to SBpolys
83//
84
85static void sBucket_Merge_m(sBucket_pt bucket, poly p)
86{
87  assume(p != NULL && pNext(p) == NULL);
88  int length = 1;
89  int i = 0;
90
91  while (bucket->buckets[i].p != NULL)
92  {
93    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
94    length += bucket->buckets[i].length;
95    bucket->buckets[i].p = NULL;
96    bucket->buckets[i].length = 0;
97    i++;
98    assume(LOG2(length) == i);
99  }
100
101  bucket->buckets[i].p = p;
102  bucket->buckets[i].length = length;
103  if (i > bucket->max_bucket) bucket->max_bucket = i;
104}
105
106void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
107{
108  assume(bucket != NULL);
109  assume(length <= 0 || length == pLength(p));
110
111  if (p == NULL) return;
112  if (length <= 0) length = pLength(p);
113
114  int i = LOG2(length);
115
116  while (bucket->buckets[i].p != NULL)
117  {
118    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
119    length += bucket->buckets[i].length;
120    bucket->buckets[i].p = NULL;
121    bucket->buckets[i].length = 0;
122    i++;
123    assume(LOG2(length) == i);
124  }
125
126  bucket->buckets[i].p = p;
127  bucket->buckets[i].length = length;
128  if (i > bucket->max_bucket) bucket->max_bucket = i;
129}
130
131void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
132{
133  assume(bucket != NULL);
134  assume(length <= 0 || length == pLength(p));
135
136  if (p == NULL) return;
137  if (length <= 0) length = pLength(p);
138
139  int i = LOG2(length);
140
141  while (bucket->buckets[i].p != NULL)
142  {
143    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
144                bucket->bucket_ring);
145    bucket->buckets[i].p = NULL;
146    bucket->buckets[i].length = 0;
147    if (p==NULL)
148    {
149      if (i > bucket->max_bucket) bucket->max_bucket = i;
150      return;
151    }
152    i = LOG2(length);
153  }
154
155  bucket->buckets[i].p = p;
156  bucket->buckets[i].length = length;
157  if (i > bucket->max_bucket) bucket->max_bucket = i;
158}
159
160// Converts SBpoly into a poly and clears bucket
161// i.e., afterwards SBpoly == 0
162void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
163{
164  poly pr = NULL;
165  int  lr = 0;
166  int i = 0;
167
168  while (bucket->buckets[i].p == NULL)
169  {
170    i++;
171    if (i > bucket->max_bucket) goto done;
172  }
173
174  pr = bucket->buckets[i].p;
175  lr = bucket->buckets[i].length;
176  bucket->buckets[i].p = NULL;
177  bucket->buckets[i].length = 0;
178  i++;
179
180  while (i <= bucket->max_bucket)
181  {
182    if (bucket->buckets[i].p != NULL)
183    {
184      pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
185      lr += bucket->buckets[i].length;
186      bucket->buckets[i].p = NULL;
187      bucket->buckets[i].length = 0;
188    }
189    i++;
190  }
191
192  done:
193  *p = pr;
194  *length = lr;
195  bucket->max_bucket = 0;
196}
197
198// Converts SBpoly into a poly and clears bucket
199// i.e., afterwards SBpoly == 0
200void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
201{
202  poly pr = NULL;
203  int  lr = 0;
204  int i = 0;
205
206  while (bucket->buckets[i].p == NULL)
207  {
208    i++;
209    if (i > bucket->max_bucket) goto done;
210  }
211
212  pr = bucket->buckets[i].p;
213  lr = bucket->buckets[i].length;
214  bucket->buckets[i].p = NULL;
215  bucket->buckets[i].length = 0;
216  i++;
217
218  while (i <= bucket->max_bucket)
219  {
220    if (bucket->buckets[i].p != NULL)
221    {
222      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
223                   bucket->bucket_ring);
224      bucket->buckets[i].p = NULL;
225      bucket->buckets[i].length = 0;
226    }
227    i++;
228  }
229
230  done:
231  *p = pr;
232  *length = lr;
233  bucket->max_bucket = 0;
234}
235
236/////////////////////////////////////////////////////////////////////////////
237// Sorts a poly using BucketSort
238//
239
240poly sBucketSortMerge(poly p, ring r)
241{
242#ifdef HAVE_ASSUME
243  int l_in = pLength(p);
244#endif
245
246  if (p == NULL || pNext(p) == NULL) return p;
247
248  sBucket_pt bucket = sBucketCreate(r);
249  poly pn = pNext(p);
250
251  do
252  {
253    pNext(p) = NULL;
254    sBucket_Merge_m(bucket, p);
255    p = pn;
256    if (p == NULL) break;
257    pn = pNext(pn);
258  }
259  while (1);
260
261  int l_dummy;
262  sBucketClearMerge(bucket, &pn, &l_dummy);
263  sBucketDestroy(&bucket);
264
265  p_Test(pn, r);
266#ifdef HAVE_ASSUME
267  assume(l_dummy == pLength(pn));
268  assume(l_in == l_dummy);
269#endif
270  return pn;
271}
272
273/////////////////////////////////////////////////////////////////////////////
274// Sorts a poly using BucketSort
275//
276
277poly sBucketSortAdd(poly p, ring r)
278{
279#ifdef HAVE_ASSUME
280  int l_in = pLength(p);
281#endif
282
283  if (p == NULL || pNext(p) == NULL) return p;
284
285  sBucket_pt bucket = sBucketCreate(r);
286  poly pn = pNext(p);
287
288  do
289  {
290    pNext(p) = NULL;
291    sBucket_Add_p(bucket, p, 1);
292    p = pn;
293    if (p == NULL) break;
294    pn = pNext(pn);
295  }
296  while (1);
297
298  int l_dummy;
299  sBucketClearAdd(bucket, &pn, &l_dummy);
300  sBucketDestroy(&bucket);
301
302  p_Test(pn, r);
303#ifdef HAVE_ASSUME
304  assume(l_dummy == pLength(pn));
305  assume(l_in >= l_dummy);
306#endif
307  return pn;
308}
Note: See TracBrowser for help on using the repository browser.