File Coverage

lib/PDL/Image2D/select.c

Criterion	Covered	Total	%
statement	2	13	15.3
branch	18	264	6.8
condition			n/a
subroutine			n/a
pod			n/a
total	20	277	7.2

line	stmt	bran	code
1			#include "EXTERN.h"
2			#include "perl.h"
3			#include "pdl.h"
4
5			/*
6			* this routine is based on code referenced from
7			* http://www.eso.org/~ndevilla/median/
8			* the original algorithm is described in Numerical Recipes
9			*/
10
11			#define ELEM_SWAP(ctype,a,b) { register ctype t=(a);(a)=(b);(b)=t; }
12
13			/* for use with PDL_TYPELIST_REAL */
14			#define X(symbol, ctype, ppsym, ...) \
15			ctype quick_select_ ## ppsym(ctype arr[], int n) \
16			{ \
17			int low, high ; \
18			int median; \
19			int middle, ll, hh; \
20			low = 0 ; high = n-1 ; median = (low + high) / 2; \
21			for (;;) { \
22			if (high <= low) /* One element only */ \
23			return arr[median] ; \
24			if (high == low + 1) { /* Two elements only */ \
25			if (arr[low] > arr[high]) \
26			ELEM_SWAP(ctype, arr[low], arr[high]) ; \
27			return arr[median] ; \
28			} \
29			/* Find median of low, middle and high items; swap into position low */ \
30			middle = (low + high) / 2; \
31			if (arr[middle] > arr[high]) ELEM_SWAP(ctype, arr[middle], arr[high]) ; \
32			if (arr[low] > arr[high]) ELEM_SWAP(ctype, arr[low], arr[high]) ; \
33			if (arr[middle] > arr[low]) ELEM_SWAP(ctype, arr[middle], arr[low]) ; \
34			/* Swap low item (now in position middle) into position (low+1) */ \
35			ELEM_SWAP(ctype, arr[middle], arr[low+1]) ; \
36			/* Nibble from each end towards middle, swapping items when stuck */ \
37			ll = low + 1; \
38			hh = high; \
39			for (;;) { \
40			do ll++; while (arr[low] > arr[ll]) ; \
41			do hh--; while (arr[hh] > arr[low]) ; \
42			if (hh < ll) \
43			break; \
44			ELEM_SWAP(ctype, arr[ll], arr[hh]) ; \
45			} \
46			/* Swap middle item (in position low) back into correct position */ \
47			ELEM_SWAP(ctype, arr[low], arr[hh]) ; \
48			/* Re-set active partition */ \
49			if (hh <= median) \
50			low = ll; \
51			if (hh >= median) \
52			high = hh - 1; \
53			} \
54			}
55	716	0	PDL_TYPELIST_REAL(X)
	0	0
	716	0
	0	0
	0	0
	0	0
	0	0
	0	0
	0	0
	0	0
	0	0
	0	100
	0	100
		50
		100
		50
		50
		100
		50
		100
		100
		100
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
56			#undef ELEM_SWAP
57			#undef X