sbuckets.cc
Go to the documentation of this file.
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 <kernel/p_Procs.h>
20 
21 
22 
23 //////////////////////////////////////////////////////////////////////////
24 // Declarations
25 //
26 
28 {
29 public:
31  long length;
32 };
33 
34 class sBucket
35 {
36 public:
38  long max_bucket;
40 }
41 ;
42 
44 
45 
46 //////////////////////////////////////////////////////////////////////////
47 // New API:
48 //
49 
50 /// Returns bucket ring
52 { return bucket->bucket_ring; }
53 
54 
56 {
57  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
58  {
59  assume( i < (BIT_SIZEOF_LONG - 3) );
60  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
61 
62  if( bucket->buckets[i].p != NULL )
63  return false;
64 
65  if( bucket->buckets[i].length != 0 )
66  return false;
67  }
68 
69  return( bucket->max_bucket == 0 );
70 
71 }
72 
73 
74 /// Copy sBucket non-intrusive!!!
76 {
77  const ring r = bucket->bucket_ring;
78 
79  sBucket_pt newbucket = sBucketCreate(r);
80 
81  newbucket->max_bucket = bucket->max_bucket;
82 
83  for(int i = 0; i <= bucket->max_bucket; i++)
84  {
85  assume( i < (BIT_SIZEOF_LONG - 3) );
86  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
87 
88  newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
89  newbucket->buckets[i].length = bucket->buckets[i].length;
90 
91  assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
92  }
93 
94  return newbucket;
95 }
96 
97 /////////////////////////////////////////////////////////////////////////////
98 // internal routines
99 //
100 // returns floor(log_2(i))
101 static inline int LOG2(int i)
102 {
103  assume (i > 0);
104  int j = 0;
105 
106  do
107  {
108  i = i >> 1;
109  if (i == 0) return j;
110  j++;
111  }
112  while (1);
113 
114  return j;
115 }
116 
117 //////////////////////////////////////////////////////////////////////////
118 // Creation/Destruction of buckets
119 //
121 {
123  bucket->bucket_ring = r;
124  return bucket;
125 }
126 
128 {
129  assume(bucket != NULL);
130  omFreeBin(*bucket, sBucket_bin);
131  *bucket = NULL;
132 }
133 
135 {
136  sBucket_pt bucket = *bucket_pt;
137  int i;
138  for (i=0; i<= bucket->max_bucket; i++)
139  {
140 
141  if (bucket->buckets[i].p != NULL)
142  {
143  p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
144  }
145  }
146  omFreeBin(bucket, sBucket_bin);
147  *bucket_pt = NULL;
148 }
149 
150 
151 /////////////////////////////////////////////////////////////////////////////
152 // Convertion from/to SBpolys
153 //
154 
156 {
157  assume(p != NULL && pNext(p) == NULL);
158  int length = 1;
159  int i = 0;
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(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 
177 {
178  assume(bucket != NULL);
179  assume(length <= 0 || length == pLength(p));
180 
181  if (p == NULL) return;
182  if (length <= 0) length = pLength(p);
183 
184  int i = LOG2(length);
185 
186  while (bucket->buckets[i].p != NULL)
187  {
188  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
189  length += bucket->buckets[i].length;
190  bucket->buckets[i].p = NULL;
191  bucket->buckets[i].length = 0;
192  i++;
193  assume(LOG2(length) == i);
194  }
195 
196  bucket->buckets[i].p = p;
197  bucket->buckets[i].length = length;
198  if (i > bucket->max_bucket) bucket->max_bucket = i;
199 }
200 
202 {
203  assume(bucket != NULL);
204  assume(length <= 0 || length == pLength(p));
205 
206  if (p == NULL) return;
207  if (length <= 0) length = pLength(p);
208 
209  int i = LOG2(length);
210 
211  while (bucket->buckets[i].p != NULL)
212  {
213  p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
214  bucket->bucket_ring);
215  bucket->buckets[i].p = NULL;
216  bucket->buckets[i].length = 0;
217  if (p==NULL)
218  {
219  if (i > bucket->max_bucket) bucket->max_bucket = i;
220  return;
221  }
222  i = LOG2(length);
223  }
224 
225  bucket->buckets[i].p = p;
226  bucket->buckets[i].length = length;
227  if (i > bucket->max_bucket) bucket->max_bucket = i;
228 }
229 
230 // Converts SBpoly into a poly and clears bucket
231 // i.e., afterwards SBpoly == 0
233 {
234  poly pr = NULL;
235  int lr = 0;
236  int i = 0;
237 
238  while (bucket->buckets[i].p == NULL)
239  {
240  i++;
241  if (i > bucket->max_bucket) goto done;
242  }
243 
244  pr = bucket->buckets[i].p;
245  lr = bucket->buckets[i].length;
246  bucket->buckets[i].p = NULL;
247  bucket->buckets[i].length = 0;
248  i++;
249 
250  while (i <= bucket->max_bucket)
251  {
252  if (bucket->buckets[i].p != NULL)
253  {
254  pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
255  lr += bucket->buckets[i].length;
256  bucket->buckets[i].p = NULL;
257  bucket->buckets[i].length = 0;
258  }
259  i++;
260  }
261 
262  done:
263  *p = pr;
264  *length = lr;
265  bucket->max_bucket = 0;
266 }
267 
268 // Converts SBpoly into a poly and clears bucket
269 // i.e., afterwards SBpoly == 0
271 {
272  poly pr = NULL;
273  int lr = 0;
274  int i = 0;
275 
276  while (bucket->buckets[i].p == NULL)
277  {
278  assume( bucket->buckets[i].length == 0 );
279  i++;
280  if (i > bucket->max_bucket) goto done;
281  }
282 
283  pr = bucket->buckets[i].p;
284  lr = bucket->buckets[i].length;
285 
286  assume( pr != NULL && (lr > 0) );
287 
288  bucket->buckets[i].p = NULL;
289  bucket->buckets[i].length = 0;
290  i++;
291 
292  while (i <= bucket->max_bucket)
293  {
294  if (bucket->buckets[i].p != NULL)
295  {
296  assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
297 
298  pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
299  bucket->bucket_ring);
300 
301  bucket->buckets[i].p = NULL;
302  bucket->buckets[i].length = 0;
303  }
304 
305  assume( bucket->buckets[i].p == NULL );
306  assume( bucket->buckets[i].length == 0 );
307  i++;
308  }
309 
310 done:
311 
312  *p = pr;
313  *length = lr;
314 
315  bucket->max_bucket = 0;
316 
317  assume( sIsEmpty(bucket) );
318 }
319 
320 
321 
322 
323 /////////////////////////////////////////////////////////////////////////////
324 // Sorts a poly using BucketSort
325 //
326 
328 {
329 #ifdef HAVE_ASSUME
330  int l_in = pLength(p);
331 #endif
332 
333  if (p == NULL || pNext(p) == NULL) return p;
334 
336  poly pn = pNext(p);
337 
338  do
339  {
340  pNext(p) = NULL;
341  sBucket_Merge_m(bucket, p);
342  p = pn;
343  if (p == NULL) break;
344  pn = pNext(pn);
345  }
346  while (1);
347 
348  int l_dummy;
349  sBucketClearMerge(bucket, &pn, &l_dummy);
350  sBucketDestroy(&bucket);
351 
352  p_Test(pn, r);
353 #ifdef HAVE_ASSUME
354  assume(l_dummy == pLength(pn));
355  assume(l_in == l_dummy);
356 #endif
357  return pn;
358 }
359 
360 /////////////////////////////////////////////////////////////////////////////
361 // Sorts a poly using BucketSort
362 //
363 
364 poly sBucketSortAdd(poly p, const ring r)
365 {
366 #ifdef HAVE_ASSUME
367  int l_in = pLength(p);
368 #endif
369 
370  if (p == NULL || pNext(p) == NULL) return p;
371 
373  poly pn = pNext(p);
374 
375  do
376  {
377  pNext(p) = NULL;
378  sBucket_Add_p(bucket, p, 1);
379  p = pn;
380  if (p == NULL) break;
381  pn = pNext(pn);
382  }
383  while (1);
384 
385  int l_dummy;
386  sBucketClearAdd(bucket, &pn, &l_dummy);
387  sBucketDestroy(&bucket);
388 
389  p_Test(pn, r);
390 #ifdef HAVE_ASSUME
391  assume(l_dummy == pLength(pn));
392  assume(l_in >= l_dummy);
393 #endif
394  return pn;
395 }
omBin_t * omBin
Definition: omStructs.h:12
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:201
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
static int LOG2(int i)
Definition: sbuckets.cc:101
poly sBucketSortMerge(poly p, const ring r)
Sorts p with bucketSort: assumes all monomials of p are different.
Definition: sbuckets.cc:327
const ring r
Definition: syzextra.cc:208
poly sBucketSortAdd(poly p, const ring r)
Sorts p with bucketSort: p may have equal monomials.
Definition: sbuckets.cc:364
void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!
Definition: sbuckets.cc:176
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:403
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:127
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
P bucket
Definition: myNF.cc:79
All the auxiliary stuff.
int i
Definition: cfEzgcd.cc:123
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:232
static unsigned pLength(poly a)
Definition: p_polys.h:189
static omBin sBucket_bin
Definition: sbuckets.cc:43
#define p_Test(p, r)
Definition: p_polys.h:160
ring bucket_ring
Definition: sbuckets.cc:37
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omGetSpecBin(size)
Definition: omBin.h:11
sBucket * sBucket_pt
Definition: summator.h:15
ring sBucketGetRing(const sBucket_pt bucket)
Returns bucket ring.
Definition: sbuckets.cc:51
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135
void sBucketDeleteAndDestroy(sBucket_pt *bucket_pt)
Definition: sbuckets.cc:134
#define pNext(p)
Definition: monomials.h:43
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:79
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:55
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:270
static void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:155
sBucket_pt sBucketCopy(const sBucket_pt bucket)
Copy sBucket non-intrusive!!!
Definition: sbuckets.cc:75