Scippy

SCIP

Solving Constraint Integer Programs

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

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

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