Scippy

SCIP

Solving Constraint Integer Programs

stpprioqueue.h File Reference

Detailed Description

priority queue with integer keys

Author
Daniel Rehfeldt

Implements a (minimum) priority queue with integer keys. NOTE: for efficiency reasons we don't want to give a compare callback, as for example done in the SCIP default priority queue. Also, this implementation is faster than the SCIP default priority queue. todo: if needed for other key type, either use template pattern or intrusive design with macros...

Definition in file stpprioqueue.h.

#include "scip/scip.h"

Go to the source code of this file.

Typedefs

typedef struct stp_priority_queue STP_PQ
 

Functions

SCIP_RETCODE stpprioqueue_create (SCIP *, int, STP_PQ **)
 
void stpprioqueue_free (SCIP *, STP_PQ **)
 
void stpprioqueue_deleteMin (void **, int *, STP_PQ *)
 
void * stpprioqueue_deleteMinReturnData (STP_PQ *)
 
const void * stpprioqueue_peakMinData (const STP_PQ *)
 
int stpprioqueue_peakMinKey (const STP_PQ *)
 
SCIP_RETCODE stpprioqueue_insert (SCIP *, void *, int, STP_PQ *)
 
void stpprioqueue_clean (STP_PQ *)
 
SCIP_Bool stpprioqueue_isClean (const STP_PQ *)
 

Typedef Documentation

◆ STP_PQ

typedef struct stp_priority_queue STP_PQ

Definition at line 32 of file stpprioqueue.h.

Function Documentation

◆ stpprioqueue_create()

SCIP_RETCODE stpprioqueue_create ( SCIP scip,
int  capacity,
STP_PQ **  prioqueue 
)

creates new prioqueue. If entries array is provided, it must be of size capacity + 2

Parameters
scipSCIP
capacityinitial capacity
prioqueuethe priority queue

Definition at line 95 of file stpprioqueue.c.

References stp_priority_queue_entry::key, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocMemory, STPPQ_MIN_KEY, and stpprioqueue_clean().

Referenced by dpsolverInitData().

◆ stpprioqueue_free()

void stpprioqueue_free ( SCIP scip,
STP_PQ **  prioqueue 
)

frees the priority queue

Parameters
scipSCIP
prioqueuethe priority queue

Definition at line 121 of file stpprioqueue.c.

References SCIPfreeBlockMemoryArray, and SCIPfreeMemory.

Referenced by dpsolverFreeData().

◆ stpprioqueue_deleteMin()

void stpprioqueue_deleteMin ( void **  data,
int *  key,
STP_PQ prioqueue 
)

deletes minimum and gives key and data

Parameters
datapointer to data of minimum
keypointer to key of minimum
prioqueuethe priority queue

Definition at line 157 of file stpprioqueue.c.

References stp_priority_queue::entries, stp_priority_queue_entry::key, and stpprioqueue_deleteMinReturnData().

Referenced by dpiterPopSol().

◆ stpprioqueue_deleteMinReturnData()

void* stpprioqueue_deleteMinReturnData ( STP_PQ prioqueue)

deletes minimum and returns corresponding data

Parameters
prioqueuethe priority queue

Definition at line 171 of file stpprioqueue.c.

References stp_priority_queue_entry::data, stp_priority_queue::entries, SCIP_Real, and stp_priority_queue::size.

Referenced by stpprioqueue_deleteMin().

◆ stpprioqueue_peakMinData()

const void* stpprioqueue_peakMinData ( const STP_PQ prioqueue)

shows top data

Parameters
prioqueuethe priority queue

Definition at line 133 of file stpprioqueue.c.

References stp_priority_queue_entry::data, stp_priority_queue::entries, and stp_priority_queue::size.

◆ stpprioqueue_peakMinKey()

int stpprioqueue_peakMinKey ( const STP_PQ prioqueue)

shows top key

Parameters
prioqueuethe priority queue

Definition at line 145 of file stpprioqueue.c.

References stp_priority_queue::entries, stp_priority_queue_entry::key, and stp_priority_queue::size.

◆ stpprioqueue_insert()

SCIP_RETCODE stpprioqueue_insert ( SCIP scip,
void *  data,
int  newkey,
STP_PQ prioqueue 
)

inserts data

Parameters
scipSCIP
datathe data
newkeythe key
prioqueuethe priority queue

Definition at line 236 of file stpprioqueue.c.

References stp_priority_queue::capacity, stp_priority_queue_entry::data, stp_priority_queue::entries, stp_priority_queue_entry::key, SCIP_CALL, SCIP_OKAY, SCIPreallocBlockMemoryArray, stp_priority_queue::size, and STPPQ_MIN_KEY.

Referenced by combineWithIntersecting(), and dpsolverInitData().

◆ stpprioqueue_clean()

void stpprioqueue_clean ( STP_PQ prioqueue)

clean the priority queue

Parameters
prioqueuethe priority queue

Definition at line 66 of file stpprioqueue.c.

References stp_priority_queue::size, and stpprioqueue_isClean().

Referenced by stpprioqueue_create().

◆ stpprioqueue_isClean()

SCIP_Bool stpprioqueue_isClean ( const STP_PQ prioqueue)

is the priority queue clean?

Parameters
prioqueuethe priority queue

Definition at line 78 of file stpprioqueue.c.

References FALSE, SCIPdebugMessage, stp_priority_queue::size, and TRUE.

Referenced by dpsolverFreeData(), dpterms_coreSolve(), and stpprioqueue_clean().