Changeset 15076

Timestamp:

Sep 28, 2007, 11:03:24 AM (19 years ago)

Author:

eugene

Message:

added psArraySortIndex

Location:

trunk/psLib/src/types

Files:

• psArray.c (modified) (3 diffs)
• psArray.h (modified) (3 diffs)

trunk/psLib/src/types/psArray.c

@@ -9 +9 @@
  *  @author Ross Harman, MHPCC
  *
- *  @version $Revision: 1.62 $ $Name: not supported by cvs2svn $
- *  @date $Date: 2007-09-20 23:56:57 $
+ *  @version $Revision: 1.63 $ $Name: not supported by cvs2svn $
+ *  @date $Date: 2007-09-28 21:03:24 $
  *
  *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
@@ -31 +31 @@
 #include "psArray.h"
 #include "psLogMsg.h"
+#include "psAbort.h"
 #include "psAssert.h"
 
@@ -243 +244 @@
 }
 
+// Heap sort of the index array
+psVector *psArraySortIndex (psVector *out, psArray *in, psCompareFunc func) {
+
+    if (in == NULL) {
+        return NULL;
+    }
+
+    // XXX isn't this line a waste of space?
+    out = psVectorRecycle(out, in->n, PS_TYPE_S32); // Vector for output
+    out = psVectorCreate(out, 0, in->n, 1, PS_TYPE_S32);
+    long N = out->n;                    // Number of elements
+    if (N < 2) {
+        return out;
+    }
+
+    long I = N >> 1;
+    long J = N - 1;
+
+    int result;
+
+    psS32 temp;
+    psS32 *index = out->data.S32;
+    while (1) {
+        if (I > 0) {
+            // I--;
+            temp = index[--I];
+        } else {
+            temp = index[J];
+            index[J] = index[0];
+            // J--;
+            if (--J == 0) {
+                index[0] = temp;
+                return out;
+            }
+        }
+        long i = I;
+        long j = (I << 1) + 1;
+        while (j <= J) {
+            result = func (in->data[index[j]], in->data[index[j+1]]);
+            if ((j < J) && (result < 0)) {
+                j++;
+            }
+            result = func (in->data[temp], in->data[index[j]]);
+            if (result < 0) {
+                index[i]=index[j];
+                j += (i=j) + 1;
+            } else {
+                j = J + 1;
+            }
+        }
+        index[i] = temp;
+    }
+    psAbort ("impossible to reach here");
+}
+
 psArray* psArraySort(psArray* array,
                      psComparePtrFunc func)

trunk/psLib/src/types/psArray.h

@@ -10 +10 @@
  *  @author Joshua Hoblitt, University of Hawaii
  *
- *  @version $Revision: 1.50 $ $Name: not supported by cvs2svn $
- *  @date $Date: 2007-09-20 23:56:57 $
+ *  @version $Revision: 1.51 $ $Name: not supported by cvs2svn $
+ *  @date $Date: 2007-09-28 21:03:24 $
  *
  *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
@@ -21 +21 @@
 #include "psType.h"
 #include "psCompare.h"
+#include "psVector.h"
 
 /// @addtogroup DataContainer Data Containers
@@ -220 +221 @@
 );
 
+// return the index which sorts the array
+psVector *psArraySortIndex (psVector *outIndex, psArray *in, psCompareFunc func);
 
 /** Set an element in the array.  If the current element is non-NULL, the old