Changeset c81bf7 in git for kernel/ideals.cc

Timestamp:

Jan 9, 2013, 3:25:33 PM (10 years ago)

Author:

Andreas Steenpass <steenpass@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')

Children:

b0a81177e7c506b38836a82dc86bca5774eab0e8

Parents:

9234fbc7d06a2db6993e0fdb4ba27976c1ed5341

git-author:

Andreas Steenpass <steenpass@mathematik.uni-kl.de>2013-01-09 15:25:33+01:00

git-committer:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2013-02-19 20:27:28+01:00

Message:

chg: rewrite idDelEquals based on qsort()

Conflicts:
	kernel/ideals.cc

File:

• kernel/ideals.cc (modified) (1 diff)

kernel/ideals.cc

@@ -2571 +2571 @@
 }
 
+/*
+* compare the leading terms of a and b
+*/
+static int tCompare(const poly a, const poly b)
+{
+  if (b == NULL)
+  {
+    if (a == NULL) return(0);
+
+    return(1);
+  }
+
+  if (a == NULL) return(-1);
+
+  /* a != NULL && b != NULL */
+  int r = pLmCmp(a, b);
+  if (r != 0) return(r);
+  number h = nSub(pGetCoeff(a), pGetCoeff(b));
+  r = -1 + nIsZero(h) + 2*nGreaterZero(h);   /* -1: <, 0:==, 1: > */
+  nDelete(&h);
+  return(r);
+}
+
+/*
+* compare a and b (rev-lex on terms)
+*/
+static int pCompare(const poly a, const poly b)
+{
+  int r = tCompare(a, b);
+  if (r != 0) return(r);
+
+  poly aa = a;
+  poly bb = b;
+  while (r == 0 && aa != NULL && bb != NULL)
+  {
+    pIter(aa);
+    pIter(bb);
+    r = tCompare(aa, bb);
+  }
+  return(r);
+}
+
+typedef struct
+{
+  poly p;
+  int index;
+} poly_sort;
+
+int pCompare_qsort(const void *a, const void *b)
+{
+  int res = pCompare(((poly_sort *)a)->p, ((poly_sort *)b)->p);
+  return(res);
+}
+
+void idSort_qsort(poly_sort *id_sort, int idsize)
+{
+  qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
+}
+
+/*2
+* ideal id = (id[i])
+* if id[i] = id[j] then id[j] is deleted for j > i
+*/
+void idDelEquals(ideal id)
+{
+  int idsize = IDELEMS(id);
+  poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
+  for (int i = 0; i < idsize; i++)
+  {
+    id_sort[i].p = id->m[i];
+    id_sort[i].index = i;
+  }
+  idSort_qsort(id_sort, idsize);
+  int index, index_i, index_j;
+  int i = 0;
+  for (int j = 1; j < idsize; j++)
+  {
+    if (pEqualPolys(id_sort[i].p, id_sort[j].p))
+    {
+      index_i = id_sort[i].index;
+      index_j = id_sort[j].index;
+      if (index_j > index_i)
+      {
+        index = index_j;
+      }
+      else
+      {
+        index = index_i;
+        i = j;
+      }
+      if (id->m[index] != NULL) {
+        pDelete(&id->m[index]);
+      }
+    }
+    else
+    {
+      i = j;
+    }
+  }
+  omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
+}
+