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

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