IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Changeset 18145


Ignore:
Timestamp:
Jun 16, 2008, 11:58:43 AM (18 years ago)
Author:
Paul Price
Message:

Adding simple kd-tree implementation.

Location:
trunk/psLib
Files:
3 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/math/psSort.h

    r15713 r18145  
    3030
    3131
    32 // Use of the PSSORT() macro requires additional macros defined:
     32// Use of the PSSORT() and PSSELECT() macros require additional macros defined:
    3333// COMPAREEXPR(A,B): expression to compare element A with element B; true if element A is smaller than B.
    3434// SWAPFUNC(TYPE,A,B): swap element A with element B; the type is provided so that a temporary variable can
    … …  
    7474
    7575
     76
     77// The following algorithm for selection was provided by http://en.wikipedia.org/wiki/Selection_algorithm
     78// (version as of 21 May 2008, at 17:38), and implemented below as PSSELECT():
     79//
     80// function partition(list, left, right, pivotIndex)
     81//     pivotValue := list[pivotIndex]
     82//     swap list[pivotIndex] and list[right]  // Move pivot to end
     83//     storeIndex := left
     84//     for i from left to right-1
     85//         if list[i] < pivotValue
     86//             swap list[storeIndex] and list[i]
     87//             storeIndex := storeIndex + 1
     88//     swap list[right] and list[storeIndex]  // Move pivot to its final place
     89//     return storeIndex
     90//
     91// function select(list, k, left, right)
     92//     loop
     93//         select a pivot value list[pivotIndex]
     94//         pivotNewIndex := partition(list, left, right, pivotIndex)
     95//         if k = pivotNewIndex
     96//             return list[k]
     97//         else if k < pivotNewIndex
     98//             right := pivotNewIndex-1
     99//         else
     100//             left := pivotNewIndex+1
     101
     102
     103// Select the RANK-th element
     104// This macro reorders the array so that the RANK-th element is in the correct position
     105// SIZE: Size of the array
     106// RANK: RANK to move into the correct position
     107// COMPAREEXPR: Macro with expression for comparison
     108// SWAPFUNC: Macro to swap elements
     109// SWAPTYPE: Type for swapping, passed to SWAPFUNC
     110#define PSSELECT(SIZE, RANK, COMPAREEXPR, SWAPFUNC, SWAPTYPE) { \
     111    bool selectContinue = true;         /* Continue swapping? */ \
     112    long selectMax = SIZE - 1;           /* Maximum index */ \
     113    long selectMin = 0;                  /* Minimum index */ \
     114    while (selectContinue) { \
     115        long selectPivot = (selectMin + selectMax) >> 1; /* Pivot index */ \
     116        SWAPFUNC(SWAPTYPE, selectPivot, selectMax); /* Move pivot to end */ \
     117        long selectStore = selectMin;    /* Index of interest */ \
     118        for (long i = selectMin; i < selectMax; i++) { \
     119            if (COMPAREEXPR(i, selectMax)) { /* Note: comparing with the original pivot */ \
     120                SWAPFUNC(SWAPTYPE, selectStore, i); \
     121                selectStore++; \
     122            } \
     123        } \
     124        SWAPFUNC(SWAPTYPE, selectMax, selectStore); /* Move pivot to its final place */ \
     125        if (selectStore == RANK) { \
     126            selectContinue = false;     /* Done */ \
     127        } else if (selectStore > RANK) { \
     128            selectMax = selectStore - 1; \
     129        } else { \
     130            selectMin = selectStore + 1; \
     131        } \
     132    } \
     133}
     134
     135
     136
    76137#endif

  • trunk/psLib/src/pslib_strict.h

    r16793 r18145  
    99*  @author Eric Van Alst, MHPCC
    1010*
    11 *  @version $Revision: 1.35 $ $Name: not supported by cvs2svn $
    12 *  @date $Date: 2008-03-04 22:02:09 $
     11*  @version $Revision: 1.36 $ $Name: not supported by cvs2svn $
     12*  @date $Date: 2008-06-16 21:58:42 $
    1313*
    1414*  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
    … …  
    114114#include "psSparse.h"
    115115#include "psSlurp.h"
     116#include "psTree.h"
    116117
    117118#endif // #ifndef PS_LIB_STRICT_H

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

    r12298 r18145  
    1515        psMetadataItemCompare.c \
    1616        psPixels.c \
    17         psArguments.c
     17        psArguments.c   \
     18        psTree.c
    1819
    1920EXTRA_DIST = types.i
    … …  
    3031        psMetadataItemCompare.h \
    3132        psPixels.h \
    32         psArguments.h
     33        psArguments.h   \
     34        psTree.h
    3335
    3436CLEANFILES = *~ *.bb *.bbg *.da

  • trunk/psLib/test/types

    • Property svn:ignore

      •  

        old new  
        7474tap_psMetadataUpdate
        7575tap_psMetadataOverlay
         76tap_psTree

  • trunk/psLib/test/types/.cvsignore

    r17515 r18145  
    7777tap_psMetadataUpdate
    7878tap_psMetadataOverlay
     79tap_psTree

  • trunk/psLib/test/types/Makefile.am

    r14008 r18145  
    3737        tap_psMetadataConfigFormat \
    3838        tap_psMetadataConfig_input \
    39         tap_psHash_845
     39        tap_psHash_845  \
     40        tap_psTree
    4041
    4142if BUILD_TESTS
Note: See TracChangeset for help on using the changeset viewer.