IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Changeset 15713


Ignore:
Timestamp:
Nov 29, 2007, 11:46:55 AM (18 years ago)
Author:
Paul Price
Message:

Removing sort code of unknown (and suspicious: NR?) provenance from psArraySortIndex. Generalising sort macro so that it can be used throughout psLib.

Location:
trunk/psLib/src
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/math/Makefile.am

    r12502 r15713  
    5757
    5858noinst_HEADERS = \
    59         md5.h
     59        md5.h   \
     60        psSort.h
    6061
    6162CLEANFILES = *~ *.bb *.bbg *.da

  • trunk/psLib/src/mathtypes/psVector.c

    r15711 r15713  
    1010*  @author Joshua Hoblitt, University of Hawaii
    1111*
    12 *  @version $Revision: 1.100 $ $Name: not supported by cvs2svn $
    13 *  @date $Date: 2007-11-29 02:56:01 $
     12*  @version $Revision: 1.101 $ $Name: not supported by cvs2svn $
     13*  @date $Date: 2007-11-29 21:46:54 $
    1414*
    1515*  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
    … …  
    3333#include "psAssert.h"
    3434#include "psString.h"
     35#include "psSort.h"
    3536
    3637static void vectorFree(psVector* psVec)
    … …  
    341342}
    342343
    343 // Heap sort of the array
    344 // XXX since the key size is fixed (same number of bits) a Radix sort could be
    345 // a big win here -- someone should benchmark this -JH
    346 
    347 // The following sort code is based on gsl_heapsort from GSL-1.8 (www.gnu.org/software/gsl), file
    348 // gsl-1.8/sort/sort.c, which is distributed under the GNU General Public License, version 2.
    349 //
    350 // Implement Heap sort -- direct and indirect sorting
    351 // Based on descriptions in Sedgewick "Algorithms in C"
    352 //
    353 // Copyright (C) 1999  Thomas Walter
    354 //
    355 // 18 February 2000: Modified for GSL by Brian Gough
    356344
    357345// Comparison and swap functions for sorting values directly
    … …  
    375363}
    376364
    377 // Sort the heap
    378 #define PSVECTOR_SORT_DOWNHEAP(SWAPTYPE, COMPAREFUNC, SWAPFUNC, K) { \
    379     unsigned long k = K; /* Local version of k --- so the higher-level version isn't modified */ \
    380     while (k <= N / 2) { \
    381         unsigned long j = 2 * k; \
    382         if (j < N && COMPAREFUNC(j, j + 1)) { \
    383             j++; \
    384         } \
    385         if (COMPAREFUNC(k, j)) { \
    386             SWAPFUNC(SWAPTYPE, j, k); \
    387         } else { \
    388             break; \
    389         } \
    390         k = j; \
    391     } \
    392 }
    393 
    394 // Driver for heap sort
    395 #define PSVECTOR_SORT_CASE(ELEMTYPE, SWAPTYPE, COMPAREFUNC, SWAPFUNC) \
     365#define PSVECTOR_SORT_CASE(ELEMTYPE, COMPAREEXPR, SWAPFUNC, SWAPTYPE) \
    396366case PS_TYPE_##ELEMTYPE: { \
    397367    ps##ELEMTYPE *value = vector->data.ELEMTYPE; \
    398     unsigned long N = vector->n - 1; /* Index of last element */ \
    399     unsigned long i = N / 2 + 1; /* Adding one to compensate for i-- below */ \
    400     do { \
    401         i--; \
    402         PSVECTOR_SORT_DOWNHEAP(SWAPTYPE, COMPAREFUNC, SWAPFUNC, i); \
    403     } while (i > 0); \
    404     while (N > 0) { \
    405         SWAPFUNC(SWAPTYPE, 0, N); /* Swap elements */ \
    406         /* Process the heap */ \
    407         N--; \
    408         PSVECTOR_SORT_DOWNHEAP(SWAPTYPE, COMPAREFUNC, SWAPFUNC, 0); \
    409     } \
     368    PSSORT(vector->n, COMPAREEXPR, SWAPFUNC, SWAPTYPE); \
    410369    break; \
    411370}
    412 // END of heap sort code from GSL
    413371
    414372bool psVectorSortInPlace(const psVector *vector)
    … …  
    422380
    423381    switch (vector->type.type) {
    424         PSVECTOR_SORT_CASE(U8 , U8 , PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    425         PSVECTOR_SORT_CASE(U16, U16, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    426         PSVECTOR_SORT_CASE(U32, U32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    427         PSVECTOR_SORT_CASE(U64, U64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    428         PSVECTOR_SORT_CASE(S8 , S8 , PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    429         PSVECTOR_SORT_CASE(S16, S16, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    430         PSVECTOR_SORT_CASE(S32, S32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    431         PSVECTOR_SORT_CASE(S64, S64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    432         PSVECTOR_SORT_CASE(F32, F32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
    433         PSVECTOR_SORT_CASE(F64, F64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT);
     382        PSVECTOR_SORT_CASE(U8 , PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, U8 );
     383        PSVECTOR_SORT_CASE(U16, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, U16);
     384        PSVECTOR_SORT_CASE(U32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, U32);
     385        PSVECTOR_SORT_CASE(U64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, U64);
     386        PSVECTOR_SORT_CASE(S8 , PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, S8 );
     387        PSVECTOR_SORT_CASE(S16, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, S16);
     388        PSVECTOR_SORT_CASE(S32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, S32);
     389        PSVECTOR_SORT_CASE(S64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, S64);
     390        PSVECTOR_SORT_CASE(F32, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, F32);
     391        PSVECTOR_SORT_CASE(F64, PSVECTOR_SORT_COMPARE_DIRECT, PSVECTOR_SORT_SWAP_DIRECT, F64);
    434392    default:
    435393        psError(PS_ERR_BAD_PARAMETER_TYPE, true,
    … …  
    484442    }
    485443    switch (vector->type.type) {
    486         PSVECTOR_SORT_CASE(U8 , S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    487         PSVECTOR_SORT_CASE(U16, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    488         PSVECTOR_SORT_CASE(U32, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    489         PSVECTOR_SORT_CASE(U64, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    490         PSVECTOR_SORT_CASE(S8 , S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    491         PSVECTOR_SORT_CASE(S16, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    492         PSVECTOR_SORT_CASE(S32, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    493         PSVECTOR_SORT_CASE(S64, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    494         PSVECTOR_SORT_CASE(F32, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
    495         PSVECTOR_SORT_CASE(F64, S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX);
     444        PSVECTOR_SORT_CASE(U8 , PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     445        PSVECTOR_SORT_CASE(U16, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     446        PSVECTOR_SORT_CASE(U32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     447        PSVECTOR_SORT_CASE(U64, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     448        PSVECTOR_SORT_CASE(S8 , PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     449        PSVECTOR_SORT_CASE(S16, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     450        PSVECTOR_SORT_CASE(S32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     451        PSVECTOR_SORT_CASE(S64, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     452        PSVECTOR_SORT_CASE(F32, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
     453        PSVECTOR_SORT_CASE(F64, PSVECTOR_SORT_COMPARE_INDEX, PSVECTOR_SORT_SWAP_INDEX, S32);
    496454    default:
    497455        psError(PS_ERR_BAD_PARAMETER_TYPE, true,

  • trunk/psLib/src/types/psArray.c

    r15454 r15713  
    99 *  @author Ross Harman, MHPCC
    1010 *
    11  *  @version $Revision: 1.65 $ $Name: not supported by cvs2svn $
    12  *  @date $Date: 2007-11-05 23:42:46 $
     11 *  @version $Revision: 1.66 $ $Name: not supported by cvs2svn $
     12 *  @date $Date: 2007-11-29 21:46:55 $
    1313 *
    1414 *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
    … …  
    3333#include "psAbort.h"
    3434#include "psAssert.h"
     35#include "psSort.h"
    3536
    3637#define DEFAULT_ARRAY_ADD 10            // Default number to add to an array when not specified
    … …  
    243244}
    244245
     246// Comparison and swap functions for sorting values directly
     247#define PSARRAY_SORT_COMPARE_INDEX(A,B) (func(array[index[A]], array[index[B]]) < 0)
     248#define PSARRAY_SORT_SWAP_INDEX(TYPE,A,B) { \
     249    if (A != B) { \
     250        ps##TYPE temp = index[A]; \
     251        index[A] = index[B]; \
     252        index[B] = temp; \
     253    } \
     254}
     255
    245256// Heap sort of the index array
    246257psVector *psArraySortIndex (psVector *out, psArray *in, psCompareFunc func) {
    … …  
    250261    }
    251262
    252     // XXX isn't this line a waste of space?
    253     out = psVectorRecycle(out, in->n, PS_TYPE_S32); // Vector for output
    254263    out = psVectorCreate(out, 0, in->n, 1, PS_TYPE_S32);
    255     long N = out->n;                    // Number of elements
    256     if (N < 2) {
    257         return out;
    258     }
    259 
    260     long I = N >> 1;
    261     long J = N - 1;
    262 
    263     int result;
    264 
    265     psS32 temp;
    266     psS32 *index = out->data.S32;
    267     while (1) {
    268         if (I > 0) {
    269             // I--;
    270             temp = index[--I];
    271         } else {
    272             temp = index[J];
    273             index[J] = index[0];
    274             // J--;
    275             if (--J == 0) {
    276                 index[0] = temp;
    277                 return out;
    278             }
    279         }
    280         long i = I;
    281         long j = (I << 1) + 1;
    282         while (j <= J) {
    283             if (j < J) {
    284                 result = func (in->data[index[j]], in->data[index[j+1]]);
    285                 if (result < 0) {
    286                     j++;
    287                 }
    288             }
    289             result = func (in->data[temp], in->data[index[j]]);
    290             if (result < 0) {
    291                 index[i]=index[j];
    292                 j += (i=j) + 1;
    293             } else {
    294                 j = J + 1;
    295             }
    296         }
    297         index[i] = temp;
    298     }
    299     psAbort ("impossible to reach here");
     264    psS32 *index = out->data.S32;       // Dereference index vector
     265    psPtr *array = in->data;            // Dereference input array
     266    PSSORT(out->n, PSARRAY_SORT_COMPARE_INDEX, PSARRAY_SORT_SWAP_INDEX, S32);
     267    return out;
    300268}
    301269
Note: See TracChangeset for help on using the changeset viewer.