Index: Singular/sbuckets.cc
===================================================================
--- Singular/sbuckets.cc	(revision 4469359e15fa7f254c1e096b60cae9cd0e8629e2)
+++ Singular/sbuckets.cc	(revision 4469359e15fa7f254c1e096b60cae9cd0e8629e2)
@@ -0,0 +1,307 @@
+/****************************************
+*  Computer Algebra System SINGULAR     *
+****************************************/
+/***************************************************************
+ *  File:    sbuckets.cc
+ *  Purpose: implementation of routines for sorting polys using 
+ *           a bucket sort
+ *  Author:  obachman (Olaf Bachmann)
+ *  Created: 9/00
+ *  Version: $Id: sbuckets.cc,v 1.1 2000-12-31 15:17:47 obachman Exp $
+ *******************************************************************/
+#include "sbuckets.h"
+#include "omalloc.h"
+#include "ring.h"
+#include "p_Procs.h"
+#include "p_polys.h"
+
+
+
+//////////////////////////////////////////////////////////////////////////
+// Declarations
+//
+
+class sBucketPoly
+{
+public:
+  poly p;
+  long length;
+};
+
+class sBucket
+{
+public:
+  ring          bucket_ring;
+  long          max_bucket;
+  sBucketPoly   buckets[BIT_SIZEOF_LONG - 3];
+}
+;
+
+static omBin sBucket_bin = omGetSpecBin(sizeof(sBucket));
+
+/////////////////////////////////////////////////////////////////////////////
+// internal routines
+//
+// returns floor(log_2(i))
+inline int LOG2(int i)
+{
+  assume (i > 0);
+  int j = 0;
+
+  do
+  {
+    i = i >> 1;
+    if (i == 0) return j;
+    j++;
+  }
+  while (1);
+  
+  return j;
+}
+  
+//////////////////////////////////////////////////////////////////////////
+// Creation/Destruction of buckets
+//
+sBucket_pt    sBucketCreate(ring r)
+{
+  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
+  bucket->bucket_ring = r;
+  return bucket;
+}
+
+void          sBucketDestroy(sBucket_pt *bucket)
+{
+  assume(bucket != NULL);
+  omFreeBin(*bucket, sBucket_bin);
+  *bucket = NULL;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// Convertion from/to SBpolys
+//
+
+static void sBucket_Merge_m(sBucket_pt bucket, poly p)
+{
+  assume(p != NULL && pNext(p) == NULL);
+  int length = 1;
+  int i = 0;
+
+  while (bucket->buckets[i].p != NULL)
+  {
+    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
+    length += bucket->buckets[i].length;
+    bucket->buckets[i].p = NULL;
+    bucket->buckets[i].length = 0;
+    i++;
+    assume(LOG2(length) == i);
+  }
+  
+  bucket->buckets[i].p = p;
+  bucket->buckets[i].length = length;
+  if (i > bucket->max_bucket) bucket->max_bucket = i;
+}
+  
+void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
+{
+  assume(bucket != NULL);
+  assume(length <= 0 || length == pLength(p));
+  
+  if (p == NULL) return;
+  if (length <= 0) length = pLength(p);
+  
+  int i = LOG2(length);
+  
+  while (bucket->buckets[i].p != NULL)
+  {
+    p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
+    length += bucket->buckets[i].length;
+    bucket->buckets[i].p = NULL;
+    bucket->buckets[i].length = 0;
+    i++;
+    assume(LOG2(length) == i);
+  }
+  
+  bucket->buckets[i].p = p;
+  bucket->buckets[i].length = length;
+  if (i > bucket->max_bucket) bucket->max_bucket = i;
+}
+
+void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
+{
+  assume(bucket != NULL);
+  assume(length <= 0 || length == pLength(p));
+  
+  if (p == NULL) return;
+  if (length <= 0) length = pLength(p);
+  
+  int i = LOG2(length);
+  
+  while (bucket->buckets[i].p != NULL)
+  {
+    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length, 
+                bucket->bucket_ring);
+    bucket->buckets[i].p = NULL;
+    bucket->buckets[i].length = 0;
+    i = LOG2(length);
+  }
+  
+  bucket->buckets[i].p = p;
+  bucket->buckets[i].length = length;
+  if (i > bucket->max_bucket) bucket->max_bucket = i;
+}
+
+// Converts SBpoly into a poly and clears bucket
+// i.e., afterwards SBpoly == 0
+void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
+{
+  poly pr = NULL;
+  int  lr = 0;
+  int i = 0;
+  
+  while (bucket->buckets[i].p == NULL)
+  {
+    i++;
+    if (i > bucket->max_bucket) goto done;
+  }
+
+  pr = bucket->buckets[i].p;
+  lr = bucket->buckets[i].length;
+  bucket->buckets[i].p = NULL;
+  bucket->buckets[i].length = 0;
+  i++;
+  
+  while (i <= bucket->max_bucket)
+  {
+    if (bucket->buckets[i].p != NULL)
+    {
+      pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
+      lr += bucket->buckets[i].length;
+      bucket->buckets[i].p = NULL;
+      bucket->buckets[i].length = 0;
+    }
+    i++;
+  }
+  
+  done:
+  *p = pr;
+  *length = lr;
+  bucket->max_bucket = 0;
+}
+
+// Converts SBpoly into a poly and clears bucket
+// i.e., afterwards SBpoly == 0
+void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
+{
+  poly pr = NULL;
+  int  lr = 0;
+  int i = 0;
+  
+  while (bucket->buckets[i].p == NULL)
+  {
+    i++;
+    if (i > bucket->max_bucket) goto done;
+  }
+
+  pr = bucket->buckets[i].p;
+  lr = bucket->buckets[i].length;
+  bucket->buckets[i].p = NULL;
+  bucket->buckets[i].length = 0;
+  i++;
+  
+  while (i <= bucket->max_bucket)
+  {
+    if (bucket->buckets[i].p != NULL)
+    {
+      pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length, 
+                   bucket->bucket_ring);
+      bucket->buckets[i].p = NULL;
+      bucket->buckets[i].length = 0;
+    }
+    i++;
+  }
+  
+  done:
+  *p = pr;
+  *length = lr;
+  bucket->max_bucket = 0;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// Sorts a poly using BucketSort
+//
+
+poly sBucketSortMerge(poly p, ring r)
+{
+#ifdef HAVE_ASSUME
+  int l_in = pLength(p);
+#endif
+  
+  if (p == NULL || pNext(p) == NULL) return p;
+  
+  sBucket_pt bucket = sBucketCreate(r);
+  poly pn = pNext(p);
+  
+  do
+  {
+    pNext(p) = NULL;
+    sBucket_Merge_m(bucket, p);
+    p = pn;
+    if (p == NULL) break;
+    pn = pNext(pn);
+  }
+  while (1);
+  
+  int l_dummy;
+  sBucketClearMerge(bucket, &pn, &l_dummy);
+  sBucketDestroy(&bucket);
+
+  p_Test(pn, r);
+#ifdef HAVE_ASSUME
+  assume(l_dummy == pLength(pn));
+  assume(l_in == l_dummy);
+#endif
+  return pn;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// Sorts a poly using BucketSort
+//
+
+poly sBucketSortAdd(poly p, ring r)
+{
+#ifdef HAVE_ASSUME
+  int l_in = pLength(p);
+#endif
+  
+  if (p == NULL || pNext(p) == NULL) return p;
+  
+  sBucket_pt bucket = sBucketCreate(r);
+  poly pn = pNext(p);
+  
+  do
+  {
+    pNext(p) = NULL;
+    sBucket_Add_p(bucket, p, 1);
+    p = pn;
+    if (p == NULL) break;
+    pn = pNext(pn);
+  }
+  while (1);
+  
+  int l_dummy;
+  sBucketClearAdd(bucket, &pn, &l_dummy);
+  sBucketDestroy(&bucket);
+
+  p_Test(pn, r);
+#ifdef HAVE_ASSUME
+  assume(l_dummy == pLength(pn));
+  assume(l_in >= l_dummy);
+#endif
+  return pn;
+}
+
+
+
+  
+  
+
Index: Singular/sbuckets.h
===================================================================
--- Singular/sbuckets.h	(revision 4469359e15fa7f254c1e096b60cae9cd0e8629e2)
+++ Singular/sbuckets.h	(revision 4469359e15fa7f254c1e096b60cae9cd0e8629e2)
@@ -0,0 +1,85 @@
+/****************************************
+*  Computer Algebra System SINGULAR     *
+****************************************/
+/***************************************************************
+ *  File:    sbuckets.h
+ *  Purpose: declaration of routines for sorting and adding up polys using 
+ *           a bucket sort
+ *  Note:    If you need to extract the leading momonial of a bucket,
+ *           use kbuckets, instead.
+ *  Author:  obachman (Olaf Bachmann)
+ *  Created: 9/00
+ *  Version: $Id: sbuckets.h,v 1.1 2000-12-31 15:17:47 obachman Exp $
+ *******************************************************************/
+#ifndef S_BUCKETS_H
+#define S_BUCKETS_H
+
+#include "mod2.h"
+#include "structs.h"
+
+//////////////////////////////////////////////////////////////////////////
+// Creation/Destruction of buckets
+//
+sBucket_pt    sBucketCreate(ring r = currRing);
+void          sBucketDestroy(sBucket_pt *bucket);
+
+
+/////////////////////////////////////////////////////////////////////////////
+// Convertion from/to SBpolys
+//
+
+// Converts p into a bucket poly (SBpoly) and destroys p
+// Assumes length <= 0 || pLength(p) == length
+void sBucketInit(sBucket_pt bucket, poly p, int length);
+
+// creates and returns new bucket, initializes it with p
+sBucket_pt  sBucketInit( poly p, int length, ring r = currRing);
+
+// Converts SBpoly into a poly and clears bucket
+// i.e., afterwards SBpoly == 0
+// assumes all monomials in bucket are different
+void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length);
+
+// Converts SBpoly into a poly and clears bucket
+// i.e., afterwards SBpoly == 0
+// bucket may contain equal monials
+void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length);
+
+// Converts SBpoly into a poly and detroys bucket
+inline void sBucketDestroyMerge(sBucket_pt bucket, poly *p, int *length)
+{
+  sBucketClearMerge(bucket, p, length);
+  sBucketDestroy(&bucket);
+}
+
+// Converts SBpoly into a poly and detroys bucket
+inline void sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)
+{
+  sBucketClearAdd(bucket, p, length);
+  sBucketDestroy(&bucket);
+}
+
+
+//////////////////////////////////////////////////////////////////////////
+///
+/// Merges p into Spoly: assumes Bpoly and p have no common monoms
+///
+void sBucket_Merge_p(sBucket_pt bucket, poly p, int lp);
+// adds poly p to bucket
+void sBucket_Add_p(sBucket_pt bucket, poly p, int lp);
+
+
+//////////////////////////////////////////////////////////////////////////
+///
+/// Sorts p with bucektSort: assumes all monomials of p are different
+///
+poly sBucketSortMerge(poly p, ring r);
+
+//////////////////////////////////////////////////////////////////////////
+///
+/// Sorts p with bucektSort: p may have equal monomials
+///
+poly sBucketSortAdd(poly p, ring r);
+
+
+#endif // P_BUCKET_SORT
