Detailed Description
template functions for sorting
Definition in file sorttpl.c.
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_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_CMP(x, y) ((x) - (y)) |
#define | SORTTPL_ISBETTER(x, y) (SORTTPL_CMP(x,y) < 0) |
#define | SORTTPL_ISWORSE(x, y) (SORTTPL_CMP(x,y) > 0) |
#define | SORTTPL_SWAP(T, x, y) |
#define | EXCH(x, y) |
Functions | |
static void | SORTTPL_NAME (sorttpl_shellSort, SORTTPL_NAMEEXT) |
static int | SORTTPL_NAME (sorttpl_medianThree, SORTTPL_NAMEEXT) |
static int | SORTTPL_NAME (sorttpl_selectPivotIndex, 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) |
static void | SORTTPL_NAME (sorttpl_checkWeightedSelection, SORTTPL_NAMEEXT) |
void | SORTTPL_NAME (SCIPselectWeighted, SORTTPL_NAMEEXT) |
void | SORTTPL_NAME (SCIPselect, SORTTPL_NAMEEXT) |
Macro Definition Documentation
◆ SORTTPL_SHELLSORTMAX
#define SORTTPL_SHELLSORTMAX 25 /* maximal size for shell sort */ |
Definition at line 50 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_MINSIZENINTHER
#define SORTTPL_MINSIZENINTHER 729 /* minimum input size to use ninther (median of nine) for pivot selection */ |
Definition at line 51 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD1
#define SORTTPL_HASFIELD1 | ( | x | ) |
Definition at line 72 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD1PAR
#define SORTTPL_HASFIELD1PAR | ( | x | ) |
Definition at line 73 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD2
#define SORTTPL_HASFIELD2 | ( | x | ) |
Definition at line 79 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD2PAR
#define SORTTPL_HASFIELD2PAR | ( | x | ) |
Definition at line 80 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD3
#define SORTTPL_HASFIELD3 | ( | x | ) |
Definition at line 86 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD3PAR
#define SORTTPL_HASFIELD3PAR | ( | x | ) |
Definition at line 87 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD4
#define SORTTPL_HASFIELD4 | ( | x | ) |
Definition at line 93 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD4PAR
#define SORTTPL_HASFIELD4PAR | ( | x | ) |
Definition at line 94 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD5
#define SORTTPL_HASFIELD5 | ( | x | ) |
Definition at line 100 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD5PAR
#define SORTTPL_HASFIELD5PAR | ( | x | ) |
Definition at line 101 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD6
#define SORTTPL_HASFIELD6 | ( | x | ) |
Definition at line 107 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASFIELD6PAR
#define SORTTPL_HASFIELD6PAR | ( | x | ) |
Definition at line 108 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASPTRCOMP
◆ SORTTPL_HASPTRCOMPPAR
#define SORTTPL_HASPTRCOMPPAR | ( | x | ) |
Definition at line 115 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_HASINDCOMP
◆ SORTTPL_HASINDCOMPPAR
#define SORTTPL_HASINDCOMPPAR | ( | x | ) |
Definition at line 122 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_EXPANDNAME
#define SORTTPL_EXPANDNAME | ( | method, | |
methodname | |||
) | method ## methodname |
◆ SORTTPL_NAME
#define SORTTPL_NAME | ( | method, | |
methodname | |||
) | SORTTPL_EXPANDNAME(method, methodname) |
Definition at line 132 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_CMP
Definition at line 153 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_ISBETTER
#define SORTTPL_ISBETTER | ( | x, | |
y | |||
) | (SORTTPL_CMP(x,y) < 0) |
Definition at line 158 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_ISWORSE
#define SORTTPL_ISWORSE | ( | x, | |
y | |||
) | (SORTTPL_CMP(x,y) > 0) |
Definition at line 159 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ SORTTPL_SWAP
Definition at line 162 of file sorttpl.c.
Referenced by SORTTPL_NAME().
◆ EXCH
macro that performs an exchange in the weighted selection algorithm, including weights
Definition at line 788 of file sorttpl.c.
Referenced by SORTTPL_NAME().
Function Documentation
◆ SORTTPL_NAME() [1/12]
|
static |
shell-sort an array of data elements; use it only for arrays smaller than 25 entries ending index
Definition at line 172 of file sorttpl.c.
References h, NULL, SCIP_Real, 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.
◆ SORTTPL_NAME() [2/12]
|
static |
returns the index a, b, or c of the median element among key[a], key[b], and key[c] third index of the array to consider
Definition at line 248 of file sorttpl.c.
References a, b, and SORTTPL_ISBETTER.
◆ SORTTPL_NAME() [3/12]
|
static |
guess a 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 301 of file sorttpl.c.
References SORTTPL_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_MINSIZENINTHER, SORTTPL_NAME, SORTTPL_NAMEEXT, and SORTTPL_SHELLSORTMAX.
◆ SORTTPL_NAME() [4/12]
|
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 374 of file sorttpl.c.
References NULL, 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.
◆ SORTTPL_NAME() [5/12]
|
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 559 of file sorttpl.c.
References SORTTPL_ISBETTER.
◆ SORTTPL_NAME() [6/12]
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 578 of file sorttpl.c.
References NULL, SORTTPL_HASFIELD1PAR, SORTTPL_HASFIELD2PAR, SORTTPL_HASFIELD3PAR, SORTTPL_HASFIELD4PAR, SORTTPL_HASFIELD5PAR, SORTTPL_HASFIELD6PAR, SORTTPL_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_NAME, SORTTPL_NAMEEXT, SORTTPL_SHELLSORTMAX, and TRUE.
◆ SORTTPL_NAME() [7/12]
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 644 of file sorttpl.c.
References NULL, SORTTPL_HASFIELD1, SORTTPL_HASFIELD2, SORTTPL_HASFIELD3, SORTTPL_HASFIELD4, SORTTPL_HASFIELD5, SORTTPL_HASFIELD6, and SORTTPL_ISBETTER.
◆ SORTTPL_NAME() [8/12]
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 695 of file sorttpl.c.
References SORTTPL_FIELD1TYPE, SORTTPL_HASFIELD1, SORTTPL_HASFIELD2, SORTTPL_HASFIELD3, SORTTPL_HASFIELD4, SORTTPL_HASFIELD5, and SORTTPL_HASFIELD6.
◆ SORTTPL_NAME() [9/12]
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 741 of file sorttpl.c.
References FALSE, NULL, SORTTPL_ISBETTER, and TRUE.
◆ SORTTPL_NAME() [10/12]
|
static |
verifies that the partial sorting and especially the median element satisfy all properties the position of the weighted median
Definition at line 808 of file sorttpl.c.
References NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_DEFAULT_EPSILON, SCIP_Real, SCIPquadprecSumQD, and SORTTPL_ISBETTER.
◆ SORTTPL_NAME() [11/12]
void SORTTPL_NAME | ( | SCIPselectWeighted | , |
SORTTPL_NAMEEXT | |||
) |
partially sorts a given keys array around the weighted median w.r.t. the capacity
and permutes the additional 'field' arrays in the same way
If no weights-array is passed, the algorithm assumes weights equal to 1.pointer to store the index of the weighted median, or NULL, if not needed
Definition at line 860 of file sorttpl.c.
References EXCH, MAX, NULL, SCIP_Real, SORTTPL_CMP, SORTTPL_HASFIELD1PAR, SORTTPL_HASFIELD2PAR, SORTTPL_HASFIELD3PAR, SORTTPL_HASFIELD4PAR, SORTTPL_HASFIELD5PAR, SORTTPL_HASFIELD6PAR, SORTTPL_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_ISBETTER, SORTTPL_ISWORSE, SORTTPL_KEYTYPE, SORTTPL_NAME, SORTTPL_NAMEEXT, and SORTTPL_SHELLSORTMAX.
◆ SORTTPL_NAME() [12/12]
void SORTTPL_NAME | ( | SCIPselect | , |
SORTTPL_NAMEEXT | |||
) |
partially sorts a given keys array around the given index k
and permutes the additional 'field' arrays are in the same way length of arrays
Definition at line 1078 of file sorttpl.c.
References NULL, SCIP_Real, SORTTPL_HASFIELD1PAR, SORTTPL_HASFIELD2PAR, SORTTPL_HASFIELD3PAR, SORTTPL_HASFIELD4PAR, SORTTPL_HASFIELD5PAR, SORTTPL_HASFIELD6PAR, SORTTPL_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_NAME, and SORTTPL_NAMEEXT.