Changeset 17516 for trunk/psphot/src/pmFootprintsAssignPeaks.c

Timestamp:

May 4, 2008, 2:10:40 PM (18 years ago)

Author:

eugene

Message:

some efficiency improvements and cleanups to the footprint code

File:

• trunk/psphot/src/pmFootprintsAssignPeaks.c (modified) (2 diffs)

trunk/psphot/src/pmFootprintsAssignPeaks.c

@@ -8 +8 @@
 psErrorCode
 pmFootprintsAssignPeaks(psArray *footprints,    // the pmFootprints
-                          const psArray *peaks) { // the pmPeaks
+                        const psArray *peaks) { // the pmPeaks
     assert (footprints != NULL);
     assert (footprints->n == 0 || pmFootprintTest(footprints->data[0]));
@@ -54 +54 @@
     
     psFree(ids);
-    //
+
     // Make sure that peaks within each footprint are sorted and unique
-    //
     for (int i = 0; i < footprints->n; i++) {
+        
         pmFootprint *fp = footprints->data[i];
+
+        // XXX are we allowed to have peak-less footprints??
+        if (!fp->peaks->n) continue;
+
         fp->peaks = psArraySort(fp->peaks, pmPeakSortBySN);
 
-        for (int j = 1; j < fp->peaks->n; j++) { // check for duplicates
-            if (fp->peaks->data[j] == fp->peaks->data[j-1]) {
-                (void)psArrayRemoveIndex(fp->peaks, j);
-                j--;                    // we moved everything down one
+        // XXX EAM : the algorithm below should be much faster than using psArrayRemove if
+        // the number of peaks in the footprint is large, or if there are no duplicates.
+        // if we have a lot of small-number peak arrays with duplicates, this may be
+        // slower.
+
+        // track the number of good peaks in the footprint
+        int nGood = 1;
+
+        // check for duplicates
+        // on first pass, we set the index to NULL if peak is a duplicate
+        // XXX EAM : this can leave behind duplicates of the same S/N
+        // (if sorted list has A, B, A, B ...)
+        for (int j = 1; j < fp->peaks->n; j++) { 
+            if (fp->peaks->data[j] == fp->peaks->data[nGood]) {
+                // everything on the array has its own mem reference; free and drop this one
+                psFree (fp->peaks->data[j]);
+                fp->peaks->data[j] = NULL;
+            } else {
+                nGood ++;
             }
         }
+
+        // no deleted peaks, go to next footprint
+        if (nGood == fp->peaks->n) continue;
+
+        int nKeep = 0;
+
+        psArray *goodPeaks = psArrayAlloc (nGood);
+        // on second pass, save the good peaks
+        for (int j = 0; j < fp->peaks->n; j++) { // check for duplicates
+            if (fp->peaks->data[j] == NULL) continue;
+            // transfer the data (NULL to avoid double free)
+            // this is only slightly sleazy
+            goodPeaks->data[nKeep] = fp->peaks->data[j];
+            fp->peaks->data[j] = NULL;
+            nKeep ++;
+        }
+        psAssert (nGood == nKeep, "mis-counted nKeep or nGood");
+
+        // free the old (now NULL-filled) array
+        psFree (fp->peaks);
+        fp->peaks = goodPeaks;
     }
+
+    // (void)psArrayRemoveIndex(fp->peaks, j);
+
 
     return PS_ERR_NONE;