sorttpllex.c File Reference

template functions for lexicographic sorting More...

Go to the source code of this file.

Macros
#define	SORTTPL_SHELLSORTMAX   25 /* maximal size for shell sort */
#define	SORTTPL_MINSIZENINTHER   729 /* minimum input size to use ninther (median of nine) for pivot selection */
#define	SORTTPL_HASFIELD1(x)
#define	SORTTPL_HASFIELD1PAR(x)
#define	SORTTPL_HASFIELD2(x)
#define	SORTTPL_HASFIELD2PAR(x)
#define	SORTTPL_HASFIELD3(x)
#define	SORTTPL_HASFIELD3PAR(x)
#define	SORTTPL_HASFIELD4(x)
#define	SORTTPL_HASFIELD4PAR(x)
#define	SORTTPL_HASFIELD5(x)
#define	SORTTPL_HASFIELD5PAR(x)
#define	SORTTPL_HASFIELD6(x)
#define	SORTTPL_HASFIELD6PAR(x)
#define	SORTTPL_EXPANDNAME(method, methodname)   method ## methodname
#define	SORTTPL_NAME(method, methodname)   SORTTPL_EXPANDNAME(method, methodname)
#define	SORTTPL_ISLEXBETTER(x1, x2, y1, y2)   (SORTTPL_CMP(x1,x2,y1,y2) < 0)
#define	SORTTPL_ISLEXWORSE(x1, x2, y1, y2)   (SORTTPL_CMP(x1,x2,y1,y2) > 0)
#define	SORTTPL_SWAP(T, x, y)

Functions
static int	SORTTPL_CMP (SORTTPL_KEYTYPE x1, SORTTPL_KEYTYPE x2, SORTTPL_KEYTYPE y1, SORTTPL_KEYTYPE y2)
static void	SORTTPL_NAME (sorttpl_lexShellSort, SORTTPL_NAMEEXT)
static int	SORTTPL_NAME (sorttpl_lexMedianThree, SORTTPL_NAMEEXT)
static int	SORTTPL_NAME (sorttpl_lexSelectPivotIndex, SORTTPL_NAMEEXT)
static void	SORTTPL_NAME (sorttpl_lexQSort, SORTTPL_NAMEEXT)
static void	SORTTPL_NAME (sorttpl_lexCheckSort, SORTTPL_NAMEEXT)
static void	SORTTPL_NAME (SCIPlexSort, SORTTPL_NAMEEXT)

Detailed Description

template functions for lexicographic sorting

Author

Marc Pfetsch

Definition in file sorttpllex.c.

Macro Definition Documentation

#define SORTTPL_SHELLSORTMAX   25 /* maximal size for shell sort */

Definition at line 43 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_MINSIZENINTHER   729 /* minimum input size to use ninther (median of nine) for pivot selection */

Definition at line 44 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD1

(

x

)

Definition at line 65 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD1PAR

(

x

)

Definition at line 66 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD2

(

x

)

Definition at line 72 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD2PAR

(

x

)

Definition at line 73 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD3

(

x

)

Definition at line 79 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD3PAR

(

x

)

Definition at line 80 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD4

(

x

)

Definition at line 86 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD4PAR

(

x

)

Definition at line 87 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD5

(

x

)

Definition at line 93 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD5PAR

(

x

)

Definition at line 94 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD6

(

x

)

Definition at line 100 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD6PAR

(

x

)

Definition at line 101 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_EXPANDNAME	(		method,
			methodname
	)		method ## methodname

Definition at line 108 of file sorttpllex.c.

#define SORTTPL_NAME	(		method,
			methodname
	)		SORTTPL_EXPANDNAME(method, methodname)

Definition at line 110 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_ISLEXBETTER	(		x1,
			x2,
			y1,
			y2
	)		(SORTTPL_CMP(x1,x2,y1,y2) < 0)

Definition at line 143 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_ISLEXWORSE	(		x1,
			x2,
			y1,
			y2
	)		(SORTTPL_CMP(x1,x2,y1,y2) > 0)

Definition at line 144 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_SWAP	(		T,
			x,
			y
	)

Value:

{                \
      T temp = x;   \
      x = y;        \
      y = temp;     \
   }

Definition at line 148 of file sorttpllex.c.

Referenced by SORTTPL_NAME().

Function Documentation

static int SORTTPL_CMP ( SORTTPL_KEYTYPE  x1, SORTTPL_KEYTYPE  x2, SORTTPL_KEYTYPE  y1, SORTTPL_KEYTYPE  y2  )

static

default comparer for integers

Parameters

x1	primary key
x2	secondary key
y1	primary key
y2	secondary key

Definition at line 115 of file sorttpllex.c.

static void SORTTPL_NAME ( sorttpl_lexShellSort  , SORTTPL_NAMEEXT    )

static

shell-lex-sort an array of data elements; use it only for arrays smaller than 25 entries ending index

Definition at line 158 of file sorttpllex.c.

References SORTTPL_FIELD1TYPE, SORTTPL_HASFIELD1, SORTTPL_HASFIELD2, SORTTPL_HASFIELD3, SORTTPL_HASFIELD4, SORTTPL_HASFIELD5, SORTTPL_HASFIELD6, SORTTPL_ISLEXBETTER, and SORTTPL_KEYTYPE.

static int SORTTPL_NAME ( sorttpl_lexMedianThree  , SORTTPL_NAMEEXT    )

static

returns the index a, b, or c of the lexicographic median element among key[a], key[b], and key[c] third index of the array to consider

Definition at line 228 of file sorttpllex.c.

References SORTTPL_ISLEXBETTER.

static int SORTTPL_NAME ( sorttpl_lexSelectPivotIndex  , SORTTPL_NAMEEXT    )

static

guess a lexicographic median for the key array [start, ..., end] by using the median of the first, last, and middle element last index of the key array to consider

Definition at line 279 of file sorttpllex.c.

References SORTTPL_MINSIZENINTHER, SORTTPL_NAME, SORTTPL_NAMEEXT, and SORTTPL_SHELLSORTMAX.

static void SORTTPL_NAME ( sorttpl_lexQSort  , SORTTPL_NAMEEXT    )

static

lexicographic quick-sort an array of pointers; pivot is the medial element TRUE, if quick-sort should start with with key[lo] < pivot <= key[hi], key[lo] <= pivot < key[hi] otherwise

Definition at line 324 of file sorttpllex.c.

References SORTTPL_FIELD1TYPE, SORTTPL_HASFIELD1, SORTTPL_HASFIELD1PAR, SORTTPL_HASFIELD2, SORTTPL_HASFIELD2PAR, SORTTPL_HASFIELD3, SORTTPL_HASFIELD3PAR, SORTTPL_HASFIELD4, SORTTPL_HASFIELD4PAR, SORTTPL_HASFIELD5, SORTTPL_HASFIELD5PAR, SORTTPL_HASFIELD6, SORTTPL_HASFIELD6PAR, SORTTPL_ISLEXBETTER, SORTTPL_ISLEXWORSE, SORTTPL_KEYTYPE, SORTTPL_NAME, SORTTPL_NAMEEXT, SORTTPL_SHELLSORTMAX, and SORTTPL_SWAP.

static void SORTTPL_NAME ( sorttpl_lexCheckSort  , SORTTPL_NAMEEXT    )

static

verifies that an array is indeed sorted length of the array

Definition at line 498 of file sorttpllex.c.

References SORTTPL_ISLEXBETTER.

static void SORTTPL_NAME ( SCIPlexSort  , SORTTPL_NAMEEXT    )

static

SCIPsort...(): lexicographically sorts array 'key1/key2' and performs the same permutations on the additional 'field' arrays additional field that should be sorted in the same way additional field that should be sorted in the same way additional field that should be sorted in the same way additional field that should be sorted in the same way additional field that should be sorted in the same way additional field that should be sorted in the same way length of arrays

Definition at line 516 of file sorttpllex.c.

References SORTTPL_HASFIELD1PAR, SORTTPL_HASFIELD2PAR, SORTTPL_HASFIELD3PAR, SORTTPL_HASFIELD4PAR, SORTTPL_HASFIELD5PAR, SORTTPL_HASFIELD6PAR, SORTTPL_NAME, SORTTPL_NAMEEXT, and SORTTPL_SHELLSORTMAX.