My Project
Loading...
Searching...
No Matches
Data Structures | Functions | Variables
sbuckets.cc File Reference
#include "misc/auxiliary.h"
#include "polys/sbuckets.h"
#include "polys/monomials/ring.h"
#include "polys/monomials/p_polys.h"

Go to the source code of this file.

Data Structures

class  sBucketPoly
 
class  sBucket
 

Functions

ring sBucketGetRing (const sBucket_pt bucket)
 Returns bucket ring. More...
 
bool sIsEmpty (const sBucket_pt bucket)
 Test whether bucket is empty!? More...
 
sBucket_pt sBucketCopy (const sBucket_pt bucket)
 Copy sBucket non-intrusive!!! More...
 
sBucket_pt sBucketCreate (const ring r)
 
void sBucketDestroy (sBucket_pt *bucket)
 
void sBucketDeleteAndDestroy (sBucket_pt *bucket_pt)
 
void sBucket_Merge_m (sBucket_pt bucket, poly p)
 
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! More...
 
void sBucket_Add_m (sBucket_pt bucket, poly p)
 
void sBucket_Add_p (sBucket_pt bucket, poly p, int length)
 adds poly p to bucket destroys p! More...
 
void sBucketClearMerge (sBucket_pt bucket, poly *p, int *length)
 
void sBucketClearAdd (sBucket_pt bucket, poly *p, int *length)
 
poly sBucketSortMerge (poly p, const ring r)
 Sorts p with bucketSort: assumes all monomials of p are different. More...
 
poly sBucketSortAdd (poly p, const ring r)
 Sorts p with bucketSort: p may have equal monomials. More...
 
void sBucketCanonicalize (sBucket_pt bucket)
 
poly sBucketPeek (sBucket_pt b)
 
char * sBucketString (sBucket_pt bucket)
 
void sBucketPrint (sBucket_pt bucket)
 

Variables

STATIC_VAR omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))
 

Data Structure Documentation

◆ sBucketPoly

class sBucketPoly

Definition at line 22 of file sbuckets.cc.

Data Fields
long length
poly p

◆ sBucket

class sBucket

Definition at line 29 of file sbuckets.cc.

Data Fields
ring bucket_ring
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
long max_bucket

Function Documentation

◆ sBucket_Add_m()

void sBucket_Add_m ( sBucket_pt  bucket,
poly  p 
)

Definition at line 173 of file sbuckets.cc.

174{
175 assume(bucket != NULL);
176 assume(1 == pLength(p));
177
178 int length = 1;
179
180 int i = 0; //SI_LOG2(length);
181
182 while (bucket->buckets[i].p != NULL)
183 {
184 int shorter;
185 p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
186 shorter, bucket->bucket_ring);
187 length+=bucket->buckets[i].length-shorter;
188 bucket->buckets[i].p = NULL;
189 bucket->buckets[i].length = 0;
190 if (p==NULL)
191 {
192 if (i > bucket->max_bucket) bucket->max_bucket = i;
193 return;
194 }
195 i = SI_LOG2(length);
196 }
197
198 bucket->buckets[i].p = p;
199 bucket->buckets[i].length = length;
200 if (i > bucket->max_bucket) bucket->max_bucket = i;
201}
i
int i
Definition: cfEzgcd.cc:132
p
int p
Definition: cfModGcd.cc:4078
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
assume
#define assume(x)
Definition: mod2.h:389
NULL
#define NULL
Definition: omList.c:12
pLength
static int pLength(poly a)
Definition: p_polys.h:188
sBucketPoly::length
long length
Definition: sbuckets.cc:26
sBucket::max_bucket
long max_bucket
Definition: sbuckets.cc:33
sBucket::buckets
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:34
sBucket::bucket_ring
ring bucket_ring
Definition: sbuckets.cc:32
SI_LOG2
static int SI_LOG2(int v)
Definition: si_log2.h:6

◆ sBucket_Add_p()

void sBucket_Add_p ( sBucket_pt  bucket,
poly  p,
int  length 
)

adds poly p to bucket destroys p!

Definition at line 203 of file sbuckets.cc.

204{
205 assume(bucket != NULL);
206 assume(length <= 0 || length == (int)pLength(p));
207
208 if (p == NULL) return;
209 p_Test(p,bucket->bucket_ring);
210 if (length <= 0) length = (int)pLength(p);
211
212 int i = SI_LOG2(length);
213
214 while (bucket->buckets[i].p != NULL)
215 {
216 int shorter;
217 p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
218 bucket->bucket_ring);
219 length+= bucket->buckets[i].length-shorter;
220 bucket->buckets[i].p = NULL;
221 bucket->buckets[i].length = 0;
222 if (p==NULL)
223 {
224 if (i > bucket->max_bucket) bucket->max_bucket = i;
225 return;
226 }
227 i = SI_LOG2(length);
228 }
229
230 bucket->buckets[i].p = p;
231 bucket->buckets[i].length = length;
232 if (i > bucket->max_bucket) bucket->max_bucket = i;
233}
p_Test
#define p_Test(p, r)
Definition: p_polys.h:159

◆ sBucket_Merge_m()

void sBucket_Merge_m ( sBucket_pt  bucket,
poly  p 
)

Definition at line 127 of file sbuckets.cc.

128{
129 assume(p != NULL && pNext(p) == NULL);
130 int length = 1;
131 int i = 0;
132
133 while (bucket->buckets[i].p != NULL)
134 {
135 p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
136 length += bucket->buckets[i].length;
137 bucket->buckets[i].p = NULL;
138 bucket->buckets[i].length = 0;
139 i++;
140 assume(SI_LOG2(length) == i);
141 }
142
143 bucket->buckets[i].p = p;
144 bucket->buckets[i].length = length;
145 if (i > bucket->max_bucket) bucket->max_bucket = i;
146}
pNext
#define pNext(p)
Definition: monomials.h:36
p_Merge_q
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1210

◆ sBucket_Merge_p()

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 at line 148 of file sbuckets.cc.

149{
150 assume(bucket != NULL);
151 assume(length <= 0 || length == (int)pLength(p));
152
153 if (p == NULL) return;
154 if (length <= 0) length = pLength(p);
155
156 int i = SI_LOG2(length);
157
158 while (bucket->buckets[i].p != NULL)
159 {
160 p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
161 length += bucket->buckets[i].length;
162 bucket->buckets[i].p = NULL;
163 bucket->buckets[i].length = 0;
164 i++;
165 assume(SI_LOG2(length) == i);
166 }
167
168 bucket->buckets[i].p = p;
169 bucket->buckets[i].length = length;
170 if (i > bucket->max_bucket) bucket->max_bucket = i;
171}

◆ sBucketCanonicalize()

void sBucketCanonicalize ( sBucket_pt  bucket)

Definition at line 401 of file sbuckets.cc.

402{
403 poly pr = NULL;
404 int lr = 0;
405 int i = 0;
406
407 while (bucket->buckets[i].p == NULL)
408 {
409 assume( bucket->buckets[i].length == 0 );
410 i++;
411 if (i > bucket->max_bucket) goto done;
412 }
413
414 pr = bucket->buckets[i].p;
415 lr = bucket->buckets[i].length;
416
417 assume( pr != NULL && (lr > 0) );
418
419 bucket->buckets[i].p = NULL;
420 bucket->buckets[i].length = 0;
421 i++;
422
423 while (i <= bucket->max_bucket)
424 {
425 if (bucket->buckets[i].p != NULL)
426 {
427 p_Test(pr,bucket->bucket_ring);
428 assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
429
430 p_Test(bucket->buckets[i].p,bucket->bucket_ring);
431 //pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
432 // bucket->bucket_ring);
433 pr = p_Add_q(pr, bucket->buckets[i].p, bucket->bucket_ring);
434
435 bucket->buckets[i].p = NULL;
436 bucket->buckets[i].length = 0;
437 }
438
439 assume( bucket->buckets[i].p == NULL );
440 assume( bucket->buckets[i].length == 0 );
441 i++;
442 }
443
444done:
445 lr=pLength(pr);
446 if (pr!=NULL)
447 {
448 i = SI_LOG2(lr);
449 bucket->buckets[i].p = pr;
450 bucket->buckets[i].length = lr;
451 bucket->max_bucket = i;
452 }
453}
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934

◆ sBucketClearAdd()

void sBucketClearAdd ( sBucket_pt  bucket,
poly *  p,
int *  length 
)

Definition at line 275 of file sbuckets.cc.

276{
277 poly pr = NULL;
278 int lr = 0;
279 int i = 0;
280
281 while (bucket->buckets[i].p == NULL)
282 {
283 assume( bucket->buckets[i].length == 0 );
284 i++;
285 if (i > bucket->max_bucket) goto done;
286 }
287
288 pr = bucket->buckets[i].p;
289 lr = bucket->buckets[i].length;
290
291 assume( pr != NULL && (lr > 0) );
292
293 bucket->buckets[i].p = NULL;
294 bucket->buckets[i].length = 0;
295 i++;
296
297 while (i <= bucket->max_bucket)
298 {
299 if (bucket->buckets[i].p != NULL)
300 {
301 assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
302
303 pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
304 bucket->bucket_ring);
305
306 bucket->buckets[i].p = NULL;
307 bucket->buckets[i].length = 0;
308 }
309
310 assume( bucket->buckets[i].p == NULL );
311 assume( bucket->buckets[i].length == 0 );
312 i++;
313 }
314
315done:
316
317 *p = pr;
318 *length = lr;
319
320 bucket->max_bucket = 0;
321
322 assume( sIsEmpty(bucket) );
323}
sIsEmpty
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:50

◆ sBucketClearMerge()

void sBucketClearMerge ( sBucket_pt  bucket,
poly *  p,
int *  length 
)

Definition at line 237 of file sbuckets.cc.

238{
239 poly pr = NULL;
240 int lr = 0;
241 int i = 0;
242
243 while (bucket->buckets[i].p == NULL)
244 {
245 i++;
246 if (i > bucket->max_bucket) goto done;
247 }
248
249 pr = bucket->buckets[i].p;
250 lr = bucket->buckets[i].length;
251 bucket->buckets[i].p = NULL;
252 bucket->buckets[i].length = 0;
253 i++;
254
255 while (i <= bucket->max_bucket)
256 {
257 if (bucket->buckets[i].p != NULL)
258 {
259 pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
260 lr += bucket->buckets[i].length;
261 bucket->buckets[i].p = NULL;
262 bucket->buckets[i].length = 0;
263 }
264 i++;
265 }
266
267 done:
268 *p = pr;
269 *length = lr;
270 bucket->max_bucket = 0;
271}

◆ sBucketCopy()

sBucket_pt sBucketCopy ( const sBucket_pt  bucket)

Copy sBucket non-intrusive!!!

Definition at line 70 of file sbuckets.cc.

71{
72 sBucketCanonicalize(bucket);
73 const ring r = bucket->bucket_ring;
74
75 sBucket_pt newbucket = sBucketCreate(r);
76
77 newbucket->max_bucket = bucket->max_bucket;
78
79 for(int i = 0; i <= bucket->max_bucket; i++)
80 {
81 assume( i < (BIT_SIZEOF_LONG - 3) );
82 assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
83
84 newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
85 newbucket->buckets[i].length = bucket->buckets[i].length;
86
87 assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
88 }
89
90 return newbucket;
91}
BIT_SIZEOF_LONG
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:80
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
sBucketCanonicalize
void sBucketCanonicalize(sBucket_pt bucket)
Definition: sbuckets.cc:401
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96

◆ sBucketCreate()

sBucket_pt sBucketCreate ( const ring  r)

Definition at line 96 of file sbuckets.cc.

97{
98 sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
99 bucket->bucket_ring = r;
100 return bucket;
101}
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
sBucket_bin
STATIC_VAR omBin sBucket_bin
Definition: sbuckets.cc:38
sBucket_pt
sBucket * sBucket_pt
Definition: sbuckets.h:16

◆ sBucketDeleteAndDestroy()

void sBucketDeleteAndDestroy ( sBucket_pt *  bucket_pt)

Definition at line 110 of file sbuckets.cc.

111{
112 sBucket_pt bucket = *bucket_pt;
113 int i;
114 for (i=0; i<= bucket->max_bucket; i++)
115 {
116 p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
117 }
118 omFreeBin(bucket, sBucket_bin);
119 *bucket_pt = NULL;
120}
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899

◆ sBucketDestroy()

void sBucketDestroy ( sBucket_pt *  bucket)

Definition at line 103 of file sbuckets.cc.

104{
105 assume(bucket != NULL);
106 omFreeBin(*bucket, sBucket_bin);
107 *bucket = NULL;
108}

◆ sBucketGetRing()

ring sBucketGetRing ( const sBucket_pt  bucket)

Returns bucket ring.

Definition at line 46 of file sbuckets.cc.

47{ return bucket->bucket_ring; }

◆ sBucketPeek()

poly sBucketPeek ( sBucket_pt  b)

Definition at line 455 of file sbuckets.cc.

456{
457 sBucketCanonicalize(b);
458 return b->buckets[b->max_bucket].p;
459}
b
CanonicalForm b
Definition: cfModGcd.cc:4103

◆ sBucketPrint()

void sBucketPrint ( sBucket_pt  bucket)

Definition at line 466 of file sbuckets.cc.

467{
468 p_Write0(sBucketPeek(bucket),sBucketGetRing(bucket));
469}
p_Write0
void p_Write0(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:332
sBucketPeek
poly sBucketPeek(sBucket_pt b)
Definition: sbuckets.cc:455
sBucketGetRing
ring sBucketGetRing(const sBucket_pt bucket)
Returns bucket ring.
Definition: sbuckets.cc:46

◆ sBucketSortAdd()

poly sBucketSortAdd ( poly  p,
const ring  r 
)

Sorts p with bucketSort: p may have equal monomials.

Definition at line 368 of file sbuckets.cc.

369{
370#ifndef SING_NDEBUG
371 int l_in = pLength(p);
372#endif
373
374 if (p == NULL || pNext(p) == NULL) return p;
375
376 sBucket_pt bucket = sBucketCreate(r);
377 poly pn = pNext(p);
378
379 do
380 {
381 pNext(p) = NULL;
382 sBucket_Add_m(bucket, p);
383 p = pn;
384 if (p == NULL) break;
385 pn = pNext(pn);
386 }
387 while (1);
388
389 int l_dummy;
390 sBucketClearAdd(bucket, &pn, &l_dummy);
391 sBucketDestroy(&bucket);
392
393 p_Test(pn, r);
394#ifndef SING_NDEBUG
395 assume(l_dummy == (int)pLength(pn));
396 assume(l_in >= l_dummy);
397#endif
398 return pn;
399}
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:103
sBucket_Add_m
void sBucket_Add_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:173
sBucketClearAdd
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:275

◆ sBucketSortMerge()

poly sBucketSortMerge ( poly  p,
const ring  r 
)

Sorts p with bucketSort: assumes all monomials of p are different.

Definition at line 332 of file sbuckets.cc.

333{
334 if (p == NULL || pNext(p) == NULL) return p;
335
336#ifndef SING_NDEBUG
337 int l_in = pLength(p);
338#endif
339 sBucket_pt bucket = sBucketCreate(r);
340 poly pn = pNext(p);
341
342 do
343 {
344 pNext(p) = NULL;
345 sBucket_Merge_m(bucket, p);
346 p = pn;
347 if (p == NULL) break;
348 pn = pNext(pn);
349 }
350 while (1);
351
352 int l_dummy;
353 sBucketClearMerge(bucket, &pn, &l_dummy);
354 sBucketDestroy(&bucket);
355
356 p_Test(pn, r);
357 assume(l_dummy == (int)pLength(pn));
358#ifndef SING_NDEBUG
359 assume(l_in == l_dummy);
360#endif
361 return pn;
362}
sBucketClearMerge
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:237
sBucket_Merge_m
void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:127

◆ sBucketString()

char * sBucketString ( sBucket_pt  bucket)

Definition at line 461 of file sbuckets.cc.

462{
463 return (p_String(sBucketPeek(bucket),sBucketGetRing(bucket)));
464}
p_String
char * p_String(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:322

◆ sIsEmpty()

bool sIsEmpty ( const sBucket_pt  bucket)

Test whether bucket is empty!?

Definition at line 50 of file sbuckets.cc.

51{
52 for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
53 {
54 assume( i < (BIT_SIZEOF_LONG - 3) );
55 assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
56
57 if( bucket->buckets[i].p != NULL )
58 return false;
59
60 if( bucket->buckets[i].length != 0 )
61 return false;
62 }
63
64 return( bucket->max_bucket == 0 );
65
66}

Variable Documentation

◆ sBucket_bin

STATIC_VAR omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))

Definition at line 38 of file sbuckets.cc.

Generated on Mon Feb 27 2023 10:53:52 for My Project by   doxygen 1.9.5 for Singular