Scippy

SCIP

Solving Constraint Integer Programs

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

typedef struct stp_priority_queue_entry PQENTRY

PQ entry

Function Documentation

◆ stpprioqueue_clean()

void stpprioqueue_clean ( STP_PQ * prioqueue )

clean the priority queue

Parameters

prioqueue the 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

prioqueue the 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

scip	SCIP
capacity	initial capacity
prioqueue	the 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

scip	SCIP
prioqueue	the 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

prioqueue the 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

prioqueue the 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

data	pointer to data of minimum
key	pointer to key of minimum
prioqueue	the 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

prioqueue the 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

scip	SCIP
data	the data
newkey	the key
prioqueue	the 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().