IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Ignore:
Timestamp:
Nov 29, 2007, 11:46:55 AM (19 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.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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,
Note: See TracChangeset for help on using the changeset viewer.