Priority Queue

Detailed Description

priority queue with O(1) access to the minimum element

Functions
SCIP_EXPORT SCIP_RETCODE	SCIPpqueueCreate (SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
SCIP_EXPORT void	SCIPpqueueFree (SCIP_PQUEUE **pqueue)
SCIP_EXPORT void	SCIPpqueueClear (SCIP_PQUEUE *pqueue)
SCIP_EXPORT SCIP_RETCODE	SCIPpqueueInsert (SCIP_PQUEUE *pqueue, void *elem)
SCIP_EXPORT void *	SCIPpqueueRemove (SCIP_PQUEUE *pqueue)
SCIP_EXPORT void *	SCIPpqueueFirst (SCIP_PQUEUE *pqueue)
SCIP_EXPORT int	SCIPpqueueNElems (SCIP_PQUEUE *pqueue)
SCIP_EXPORT void **	SCIPpqueueElems (SCIP_PQUEUE *pqueue)

Function Documentation

SCIPpqueueCreate()

SCIP_EXPORT SCIP_RETCODE SCIPpqueueCreate	(	SCIP_PQUEUE **	pqueue,
		int	initsize,
		SCIP_Real	sizefac,
		SCIP_DECL_SORTPTRCOMP((*ptrcomp))
	)

creates priority queue

Parameters

pqueue	pointer to a priority queue
initsize	initial number of available element slots
sizefac	memory growing factor applied, if more element slots are needed

Definition at line 1234 of file misc.c.

References BMSallocMemory, MAX, NULL, pqueueResize(), SCIP_ALLOC, SCIP_CALL, and SCIP_OKAY.

Referenced by initData(), initProblem(), nodepairqueueCreate(), SCIPconflictCreate(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

SCIPpqueueFree()

SCIP_EXPORT void SCIPpqueueFree

(

SCIP_PQUEUE **

pqueue

)

frees priority queue, but not the data elements themselves

Parameters

pqueue

pointer to a priority queue

Definition at line 1259 of file misc.c.

References BMSfreeMemory, BMSfreeMemoryArray, and NULL.

Referenced by freeProblem(), nodepairqueueFree(), SCIPconflictFree(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

SCIPpqueueClear()

SCIP_EXPORT void SCIPpqueueClear

(

SCIP_PQUEUE *

pqueue

)

clears the priority queue, but doesn't free the data elements themselves

Parameters

pqueue

priority queue

Definition at line 1270 of file misc.c.

References SCIP_PQueue::len, and NULL.

Referenced by conflictClear().

SCIPpqueueInsert()

SCIP_EXPORT SCIP_RETCODE SCIPpqueueInsert	(	SCIP_PQUEUE *	pqueue,
		void *	elem
	)

inserts element into priority queue

Parameters

pqueue	priority queue
elem	element to be inserted

Definition at line 1280 of file misc.c.

References SCIP_PQueue::len, NULL, PQ_PARENT, pqueueResize(), SCIP_CALL, SCIP_OKAY, and SCIP_PQueue::slots.

Referenced by computeSteinerTreeVnoi(), conflictQueueBound(), createAndSplitProblem(), dualascent_init(), nodepairqueueCreate(), propagateVbounds(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and solveProblem().

SCIPpqueueRemove()

SCIP_EXPORT void* SCIPpqueueRemove

(

SCIP_PQUEUE *

pqueue

)

removes and returns best element from the priority queue

Parameters

pqueue

priority queue

Definition at line 1307 of file misc.c.

References SCIP_PQueue::len, NULL, PQ_LEFTCHILD, PQ_PARENT, PQ_RIGHTCHILD, and SCIP_PQueue::slots.

Referenced by computeSteinerTreeVnoi(), conflictFirstCand(), conflictRemoveCand(), nodepairqueueRemove(), propagateVbounds(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and solveProblem().

SCIPpqueueFirst()

SCIP_EXPORT void* SCIPpqueueFirst

(

SCIP_PQUEUE *

pqueue

)

returns the best element of the queue without removing it

Parameters

pqueue

priority queue

Definition at line 1348 of file misc.c.

References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.

Referenced by conflictFirstCand(), nodepairqueueIsEmpty(), SCIPStpDualAscent(), and SCIPStpHeurLocalExtendPcMw().

SCIPpqueueNElems()

SCIP_EXPORT int SCIPpqueueNElems

(

SCIP_PQUEUE *

pqueue

)

returns the number of elements in the queue

Parameters

pqueue

priority queue

Definition at line 1362 of file misc.c.

References SCIP_PQueue::len, and NULL.

Referenced by computeSteinerTreeVnoi(), conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), propagateVbounds(), SCIPconflictAnalyze(), SCIPisPropagatedVbounds(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and solveProblem().

SCIPpqueueElems()

SCIP_EXPORT void** SCIPpqueueElems

(

SCIP_PQUEUE *

pqueue

)

returns the elements of the queue; changing the returned array may destroy the queue's ordering!

Parameters

pqueue

priority queue

Definition at line 1373 of file misc.c.

References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.

Referenced by conflictAddConflictset(), and conflictResolveBound().