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_DECL_PQUEUEELEMCHGPOS((*elemchgpos))) |
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 | SCIPpqueueDelPos (SCIP_PQUEUE *pqueue, int pos) |
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) |
SCIP_EXPORT int | SCIPpqueueFind (SCIP_PQUEUE *pqueue, void *elem) |
Function Documentation
◆ SCIPpqueueCreate()
SCIP_EXPORT SCIP_RETCODE SCIPpqueueCreate | ( | SCIP_PQUEUE ** | pqueue, |
int | initsize, | ||
SCIP_Real | sizefac, | ||
SCIP_DECL_SORTPTRCOMP((*ptrcomp)) | , | ||
SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) | |||
) |
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 1235 of file misc.c.
References BMSallocMemory, MAX, NULL, pqueueResize(), SCIP_ALLOC, SCIP_CALL, and SCIP_OKAY.
Referenced by initData(), initProblem(), nodepairqueueCreate(), SCIPbendersActivate(), SCIPconflictCreate(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurTMRun(), and subtreeSumGapStoreNode().
◆ 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 1262 of file misc.c.
References BMSfreeMemory, BMSfreeMemoryArray, and NULL.
Referenced by freeProblem(), nodepairqueueFree(), SCIPbendersDeactivate(), SCIPconflictFree(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurTMRun(), and subtreeSumGapDelSubtrees().
◆ 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 1273 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 1334 of file misc.c.
References SCIP_PQueue::len, NULL, PQ_PARENT, pqueueElemChgPos(), pqueueResize(), SCIP_CALL, SCIP_OKAY, and SCIP_PQueue::slots.
Referenced by computeSteinerTreeVnoi(), conflictQueueBound(), createAndSplitProblem(), dualascent_init(), nodepairqueueCreate(), propagateVbounds(), SCIPbendersActivate(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), solveProblem(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().
◆ SCIPpqueueDelPos()
SCIP_EXPORT void SCIPpqueueDelPos | ( | SCIP_PQUEUE * | pqueue, |
int | pos | ||
) |
delete element at specified position, maintaining the heap property
- Parameters
-
pqueue priority queue pos position of element that should be deleted
Definition at line 1373 of file misc.c.
References SCIP_PQueue::len, NULL, PQ_LEFTCHILD, PQ_PARENT, PQ_RIGHTCHILD, pqueueElemChgPos(), SCIPpqueueNElems(), and SCIP_PQueue::slots.
Referenced by SCIPpqueueRemove(), and subtreeSumGapRemoveNode().
◆ SCIPpqueueRemove()
SCIP_EXPORT void* SCIPpqueueRemove | ( | SCIP_PQUEUE * | pqueue | ) |
removes and returns best element from the priority queue
- Parameters
-
pqueue priority queue
Definition at line 1433 of file misc.c.
References SCIP_PQueue::len, NULL, SCIPpqueueDelPos(), and SCIP_PQueue::slots.
Referenced by computeSteinerTreeVnoi(), conflictFirstCand(), conflictRemoveCand(), createSolveSubproblemIndexList(), 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 1453 of file misc.c.
References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.
Referenced by conflictFirstCand(), nodepairqueueIsEmpty(), SCIPStpDualAscent(), SCIPStpHeurLocalExtendPcMw(), subtreeSumGapComputeFromScratchEfficiently(), and subtreeSumGapRemoveNode().
◆ SCIPpqueueNElems()
SCIP_EXPORT int SCIPpqueueNElems | ( | SCIP_PQUEUE * | pqueue | ) |
returns the number of elements in the queue
- Parameters
-
pqueue priority queue
Definition at line 1467 of file misc.c.
References SCIP_PQueue::len, and NULL.
Referenced by computeSteinerTreeVnoi(), conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), createSolveSubproblemIndexList(), pqueueElemChgPos(), propagateVbounds(), SCIPconflictAnalyze(), SCIPisPropagatedVbounds(), SCIPpqueueDelPos(), SCIPpqueueFind(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), solveProblem(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().
◆ 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 1478 of file misc.c.
References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.
Referenced by conflictAddConflictset(), conflictResolveBound(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), and subtreeSumGapStoreNode().
◆ SCIPpqueueFind()
SCIP_EXPORT int SCIPpqueueFind | ( | SCIP_PQUEUE * | pqueue, |
void * | elem | ||
) |
return the position of elem
in the priority queue, or -1 if element is not found
- Parameters
-
pqueue priority queue elem element to be inserted
Definition at line 1489 of file misc.c.
References SCIPpqueueNElems(), and SCIP_PQueue::slots.