sorttpl.c File Reference

Detailed Description

template functions for sorting

Author

Michael Winkler

Tobias Achterberg

Definition in file sorttpl.c.

Go to the source code of this file.

Macros
#define	SORTTPL_SHELLSORTMAX   25
#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_HASPTRCOMP(x)
#define	SORTTPL_HASPTRCOMPPAR(x)
#define	SORTTPL_HASINDCOMP(x)
#define	SORTTPL_HASINDCOMPPAR(x)
#define	SORTTPL_EXPANDNAME(method, methodname)   method ## methodname
#define	SORTTPL_NAME(method, methodname)   SORTTPL_EXPANDNAME(method, methodname)
#define	SORTTPL_ISBETTER(x, y)   ((x) < (y))
#define	SORTTPL_ISWORSE(x, y)   ((x) > (y))
#define	SORTTPL_SWAP(T, x, y)

Functions
static void	SORTTPL_NAME (sorttpl_shellSort, SORTTPL_NAMEEXT)
static void	SORTTPL_NAME (sorttpl_qSort, SORTTPL_NAMEEXT)
static void	SORTTPL_NAME (sorttpl_checkSort, SORTTPL_NAMEEXT)
void	SORTTPL_NAME (SCIPsort, SORTTPL_NAMEEXT)
void	SORTTPL_NAME (SCIPsortedvecInsert, SORTTPL_NAMEEXT)
void	SORTTPL_NAME (SCIPsortedvecDelPos, SORTTPL_NAMEEXT)
SCIP_Bool	SORTTPL_NAME (SCIPsortedvecFind, SORTTPL_NAMEEXT)

Macro Definition Documentation

#define SORTTPL_SHELLSORTMAX   25

Definition at line 38 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD1

(

x

)

Definition at line 59 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD1PAR

(

x

)

Definition at line 60 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD2

(

x

)

Definition at line 66 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD2PAR

(

x

)

Definition at line 67 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD3

(

x

)

Definition at line 73 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD3PAR

(

x

)

Definition at line 74 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD4

(

x

)

Definition at line 80 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD4PAR

(

x

)

Definition at line 81 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD5

(

x

)

Definition at line 87 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD5PAR

(

x

)

Definition at line 88 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD6

(

x

)

Definition at line 94 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASFIELD6PAR

(

x

)

Definition at line 95 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASPTRCOMP

(

x

)

Definition at line 101 of file sorttpl.c.

#define SORTTPL_HASPTRCOMPPAR

(

x

)

Definition at line 102 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_HASINDCOMP

(

x

)

Definition at line 108 of file sorttpl.c.

#define SORTTPL_HASINDCOMPPAR

(

x

)

Definition at line 109 of file sorttpl.c.

Referenced by SORTTPL_NAME().

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

Definition at line 117 of file sorttpl.c.

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

Definition at line 119 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_ISBETTER	(		x,
			y
	)		((x) < (y))

Definition at line 145 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_ISWORSE	(		x,
			y
	)		((x) > (y))

Definition at line 146 of file sorttpl.c.

Referenced by SORTTPL_NAME().

#define SORTTPL_SWAP	(		T,
			x,
			y
	)

Value:

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

Definition at line 152 of file sorttpl.c.

Referenced by SORTTPL_NAME().

Function Documentation

static void SORTTPL_NAME ( sorttpl_shellSort  , SORTTPL_NAMEEXT    )

static

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

Definition at line 162 of file sorttpl.c.

References SORTTPL_FIELD1TYPE, SORTTPL_FIELD2TYPE, SORTTPL_FIELD3TYPE, SORTTPL_FIELD4TYPE, SORTTPL_FIELD5TYPE, SORTTPL_HASFIELD1, SORTTPL_HASFIELD2, SORTTPL_HASFIELD3, SORTTPL_HASFIELD4, SORTTPL_HASFIELD5, SORTTPL_HASFIELD6, SORTTPL_ISBETTER, and SORTTPL_KEYTYPE.

static void SORTTPL_NAME ( sorttpl_qSort  , SORTTPL_NAMEEXT    )

static

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 228 of file sorttpl.c.

References SORTTPL_FIELD1TYPE, SORTTPL_FIELD2TYPE, SORTTPL_FIELD3TYPE, SORTTPL_FIELD4TYPE, SORTTPL_FIELD5TYPE, 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_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_ISBETTER, SORTTPL_ISWORSE, SORTTPL_KEYTYPE, SORTTPL_NAME, SORTTPL_NAMEEXT, SORTTPL_SHELLSORTMAX, and SORTTPL_SWAP.

static void SORTTPL_NAME ( sorttpl_checkSort  , SORTTPL_NAMEEXT    )

static

verifies that an array is indeed sorted data element comparator data element comparator pointer to data field that is given to the external compare method length of the array

Definition at line 408 of file sorttpl.c.

References SORTTPL_ISBETTER.

void SORTTPL_NAME	(	SCIPsort	,
		SORTTPL_NAMEEXT
	)

SCIPsort...(): sorts array 'key' 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 data element comparator data element comparator pointer to data field that is given to the external compare method length of arrays

Definition at line 427 of file sorttpl.c.

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

void SORTTPL_NAME	(	SCIPsortedvecInsert	,
		SORTTPL_NAMEEXT
	)

SCIPsortedvecInsert...(): adds an element to a sorted multi-vector; This method does not do any memory allocation! It assumes that the arrays are large enough to store the additional values.pointer to store the insert position, or NULL

Definition at line 492 of file sorttpl.c.

References NULL, SORTTPL_HASFIELD1, SORTTPL_HASFIELD2, SORTTPL_HASFIELD3, SORTTPL_HASFIELD4, SORTTPL_HASFIELD5, SORTTPL_HASFIELD6, and SORTTPL_ISBETTER.

void SORTTPL_NAME	(	SCIPsortedvecDelPos	,
		SORTTPL_NAMEEXT
	)

SCIPsortedvecDelPos...(): deletes an element at a given position from a sorted multi-vector pointer to length of arrays (will be decreased by 1)

Definition at line 543 of file sorttpl.c.

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

SCIP_Bool SORTTPL_NAME	(	SCIPsortedvecFind	,
		SORTTPL_NAMEEXT
	)

SCIPsortedvecFind...(): Finds the position at which 'val' is located in the sorted vector by binary search. If the element exists, the method returns TRUE and stores the position of the element in '*pos'. If the element does not exist, the method returns FALSE and stores the position of the element that follows 'val' in the ordering in '*pos', i.e., '*pos' is the position at which 'val' would be inserted. Note that if the element is not found, '*pos' may be equal to len if all existing elements are smaller than 'val'.pointer to store the insert position

Definition at line 589 of file sorttpl.c.

References FALSE, NULL, SORTTPL_ISBETTER, and TRUE.