Scippy

SCIP

Solving Constraint Integer Programs

stpprioqueue.c File Reference

Detailed Description

priority queue with integer keys

Author
Daniel Rehfeldt

Implements a (minimum) priority queue with integer keys. A list of all interface methods can be found in stpprioqueue.h todo: if needed for other key type, either use template pattern or intrusive design with macros...

Definition in file stpprioqueue.c.

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "stpprioqueue.h"

Go to the source code of this file.

Data Structures

struct  stp_priority_queue_entry
 
struct  stp_priority_queue
 

Macros

#define STPPQ_MIN_KEY   INT_MIN
 

Typedefs

typedef struct stp_priority_queue_entry PQENTRY
 

Functions

void stpprioqueue_clean (STP_PQ *prioqueue)
 
SCIP_Bool stpprioqueue_isClean (const STP_PQ *prioqueue)
 
SCIP_RETCODE stpprioqueue_create (SCIP *scip, int capacity, STP_PQ **prioqueue)
 
void stpprioqueue_free (SCIP *scip, STP_PQ **prioqueue)
 
const void * stpprioqueue_peakMinData (const STP_PQ *prioqueue)
 
int stpprioqueue_peakMinKey (const STP_PQ *prioqueue)
 
void stpprioqueue_deleteMin (void **data, int *key, STP_PQ *prioqueue)
 
void * stpprioqueue_deleteMinReturnData (STP_PQ *prioqueue)
 
SCIP_RETCODE stpprioqueue_insert (SCIP *scip, void *data, int newkey, STP_PQ *prioqueue)
 

Macro Definition Documentation

◆ STPPQ_MIN_KEY

#define STPPQ_MIN_KEY   INT_MIN

Definition at line 35 of file stpprioqueue.c.

Referenced by stpprioqueue_create(), and stpprioqueue_insert().

Typedef Documentation

◆ PQENTRY

PQ entry

Function Documentation

◆ 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().

◆ 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_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_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_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().