Changeset 18145 for trunk/psLib/src/math/psSort.h

Timestamp:

Jun 16, 2008, 11:58:43 AM (18 years ago)

Author:

Paul Price

Message:

Adding simple kd-tree implementation.

File:

• trunk/psLib/src/math/psSort.h (modified) (2 diffs)

trunk/psLib/src/math/psSort.h

@@ -30 +30 @@
 
 
-// Use of the PSSORT() macro requires additional macros defined:
+// Use of the PSSORT() and PSSELECT() macros require additional macros defined:
 // COMPAREEXPR(A,B): expression to compare element A with element B; true if element A is smaller than B.
 // SWAPFUNC(TYPE,A,B): swap element A with element B; the type is provided so that a temporary variable can
@@ -74 +74 @@
 
 
+
+// The following algorithm for selection was provided by http://en.wikipedia.org/wiki/Selection_algorithm
+// (version as of 21 May 2008, at 17:38), and implemented below as PSSELECT():
+//
+// function partition(list, left, right, pivotIndex)
+//     pivotValue := list[pivotIndex]
+//     swap list[pivotIndex] and list[right]  // Move pivot to end
+//     storeIndex := left
+//     for i from left to right-1
+//         if list[i] < pivotValue
+//             swap list[storeIndex] and list[i]
+//             storeIndex := storeIndex + 1
+//     swap list[right] and list[storeIndex]  // Move pivot to its final place
+//     return storeIndex
+//
+// function select(list, k, left, right)
+//     loop
+//         select a pivot value list[pivotIndex]
+//         pivotNewIndex := partition(list, left, right, pivotIndex)
+//         if k = pivotNewIndex
+//             return list[k]
+//         else if k < pivotNewIndex
+//             right := pivotNewIndex-1
+//         else
+//             left := pivotNewIndex+1
+
+
+// Select the RANK-th element
+// This macro reorders the array so that the RANK-th element is in the correct position
+// SIZE: Size of the array
+// RANK: RANK to move into the correct position
+// COMPAREEXPR: Macro with expression for comparison
+// SWAPFUNC: Macro to swap elements
+// SWAPTYPE: Type for swapping, passed to SWAPFUNC
+#define PSSELECT(SIZE, RANK, COMPAREEXPR, SWAPFUNC, SWAPTYPE) { \
+    bool selectContinue = true;         /* Continue swapping? */ \
+    long selectMax = SIZE - 1;           /* Maximum index */ \
+    long selectMin = 0;                  /* Minimum index */ \
+    while (selectContinue) { \
+        long selectPivot = (selectMin + selectMax) >> 1; /* Pivot index */ \
+        SWAPFUNC(SWAPTYPE, selectPivot, selectMax); /* Move pivot to end */ \
+        long selectStore = selectMin;    /* Index of interest */ \
+        for (long i = selectMin; i < selectMax; i++) { \
+            if (COMPAREEXPR(i, selectMax)) { /* Note: comparing with the original pivot */ \
+                SWAPFUNC(SWAPTYPE, selectStore, i); \
+                selectStore++; \
+            } \
+        } \
+        SWAPFUNC(SWAPTYPE, selectMax, selectStore); /* Move pivot to its final place */ \
+        if (selectStore == RANK) { \
+            selectContinue = false;     /* Done */ \
+        } else if (selectStore > RANK) { \
+            selectMax = selectStore - 1; \
+        } else { \
+            selectMin = selectStore + 1; \
+        } \
+    } \
+}
+
+
+
 #endif