Scippy

SCIP

Solving Constraint Integer Programs

sorttpl.c File Reference

Detailed Description

template functions for sorting

Author
Michael Winkler
Tobias Achterberg
Gregor Hendel

Definition in file sorttpl.c.

#include "scip/def.h"

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

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD1

#define SORTTPL_HASFIELD1 (   x)

Definition at line 61 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD1PAR

#define SORTTPL_HASFIELD1PAR (   x)

Definition at line 62 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD2

#define SORTTPL_HASFIELD2 (   x)

Definition at line 68 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD2PAR

#define SORTTPL_HASFIELD2PAR (   x)

Definition at line 69 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD3

#define SORTTPL_HASFIELD3 (   x)

Definition at line 75 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD3PAR

#define SORTTPL_HASFIELD3PAR (   x)

Definition at line 76 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD4

#define SORTTPL_HASFIELD4 (   x)

Definition at line 82 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD4PAR

#define SORTTPL_HASFIELD4PAR (   x)

Definition at line 83 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD5

#define SORTTPL_HASFIELD5 (   x)

Definition at line 89 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD5PAR

#define SORTTPL_HASFIELD5PAR (   x)

Definition at line 90 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD6

#define SORTTPL_HASFIELD6 (   x)

Definition at line 96 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASFIELD6PAR

#define SORTTPL_HASFIELD6PAR (   x)

Definition at line 97 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASPTRCOMP

#define SORTTPL_HASPTRCOMP (   x)

Definition at line 103 of file sorttpl.c.

◆ SORTTPL_HASPTRCOMPPAR

#define SORTTPL_HASPTRCOMPPAR (   x)

Definition at line 104 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_HASINDCOMP

#define SORTTPL_HASINDCOMP (   x)

Definition at line 110 of file sorttpl.c.

◆ SORTTPL_HASINDCOMPPAR

#define SORTTPL_HASINDCOMPPAR (   x)

Definition at line 111 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_EXPANDNAME

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

Definition at line 119 of file sorttpl.c.

◆ SORTTPL_NAME

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

Definition at line 121 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_CMP

#define SORTTPL_CMP (   x,
  y 
)    ((x) - (y))

Definition at line 142 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_ISBETTER

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

Definition at line 147 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_ISWORSE

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

Definition at line 148 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ SORTTPL_SWAP

#define SORTTPL_SWAP (   T,
  x,
  y 
)
Value:
{ \
T temp = x; \
x = y; \
y = temp; \
}
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_VAR ** y
Definition: circlepacking.c:55

Definition at line 151 of file sorttpl.c.

Referenced by SORTTPL_NAME().

◆ EXCH

#define EXCH (   x,
  y 
)
Value:
do \
{ \
SORTTPL_SWAP(SORTTPL_KEYTYPE, key[x], key[y]); \
\
if( weights != NULL ) \
SORTTPL_SWAP(SCIP_Real, weights[x], weights[y]); \
SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[x], field2[y]); ) \
SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[x], field3[y]); ) \
SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[x], field4[y]); ) \
SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[x], field5[y]); ) \
SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[x], field6[y]); ) \
} \
while( FALSE )
#define SORTTPL_KEYTYPE
Definition: misc.c:6386
#define NULL
Definition: def.h:246
#define SORTTPL_HASFIELD4(x)
Definition: sorttpl.c:82
#define SORTTPL_FIELD5TYPE
Definition: misc.c:6391
#define FALSE
Definition: def.h:72
SCIP_VAR ** x
Definition: circlepacking.c:54
#define SORTTPL_SWAP(T, x, y)
Definition: sorttpl.c:151
#define SORTTPL_FIELD3TYPE
Definition: misc.c:6389
Definition: grphload.c:88
#define SORTTPL_FIELD4TYPE
Definition: misc.c:6390
#define SORTTPL_HASFIELD2(x)
Definition: sorttpl.c:68
#define SORTTPL_HASFIELD6(x)
Definition: sorttpl.c:96
#define SORTTPL_FIELD1TYPE
Definition: misc.c:6387
#define SCIP_Real
Definition: def.h:157
SCIP_VAR ** y
Definition: circlepacking.c:55
#define SORTTPL_HASFIELD5(x)
Definition: sorttpl.c:89
#define SORTTPL_HASFIELD1(x)
Definition: sorttpl.c:61
#define SORTTPL_FIELD2TYPE
Definition: misc.c:6388
#define SORTTPL_HASFIELD3(x)
Definition: sorttpl.c:75

macro that performs an exchange in the weighted selection algorithm, including weights

Definition at line 777 of file sorttpl.c.

Referenced by SORTTPL_NAME().

Function Documentation

◆ SORTTPL_NAME() [1/12]

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 161 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 int SORTTPL_NAME ( sorttpl_medianThree  ,
SORTTPL_NAMEEXT   
)
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 237 of file sorttpl.c.

References a, b, and SORTTPL_ISBETTER.

◆ SORTTPL_NAME() [3/12]

static int SORTTPL_NAME ( sorttpl_selectPivotIndex  ,
SORTTPL_NAMEEXT   
)
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 290 of file sorttpl.c.

References SORTTPL_HASINDCOMPPAR, SORTTPL_HASPTRCOMPPAR, SORTTPL_MINSIZENINTHER, SORTTPL_NAME, SORTTPL_NAMEEXT, and SORTTPL_SHELLSORTMAX.

◆ SORTTPL_NAME() [4/12]

static void SORTTPL_NAME ( sorttpl_qSort  ,
SORTTPL_NAMEEXT   
)
static

◆ SORTTPL_NAME() [5/12]

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 548 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 567 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 633 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 684 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 730 of file sorttpl.c.

References FALSE, NULL, SORTTPL_ISBETTER, and TRUE.

◆ SORTTPL_NAME() [10/12]

static void SORTTPL_NAME ( sorttpl_checkWeightedSelection  ,
SORTTPL_NAMEEXT   
)
static

verifies that the partial sorting and especially the median element satisfy all properties the position of the weighted median

Definition at line 797 of file sorttpl.c.

References NULL, SCIP_Real, 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 843 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 1064 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.