priority queue with O(1) access to the minimum element
Functions | |
SCIP_RETCODE | SCIPpqueueCreate (SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)),) |
void | SCIPpqueueFree (SCIP_PQUEUE **pqueue) |
void | SCIPpqueueClear (SCIP_PQUEUE *pqueue) |
SCIP_RETCODE | SCIPpqueueInsert (SCIP_PQUEUE *pqueue, void *elem) |
void | SCIPpqueueDelPos (SCIP_PQUEUE *pqueue, int pos) |
void * | SCIPpqueueRemove (SCIP_PQUEUE *pqueue) |
void * | SCIPpqueueFirst (SCIP_PQUEUE *pqueue) |
int | SCIPpqueueNElems (SCIP_PQUEUE *pqueue) |
void ** | SCIPpqueueElems (SCIP_PQUEUE *pqueue) |
int | SCIPpqueueFind (SCIP_PQUEUE *pqueue, void *elem) |
SCIP_RETCODE SCIPpqueueCreate | ( | SCIP_PQUEUE ** | pqueue, |
int | initsize, | ||
SCIP_Real | sizefac, | ||
SCIP_DECL_SORTPTRCOMP((*ptrcomp)) | ) |
creates priority queue
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 1298 of file misc.c.
References assert(), BMSallocMemory, MAX, NULL, pqueueResize(), SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, and SCIP_Real.
Referenced by initData(), initProblem(), nodepairqueueCreate(), SCIPbendersActivate(), SCIPconflictCreate(), and subtreeSumGapStoreNode().
void SCIPpqueueFree | ( | SCIP_PQUEUE ** | pqueue | ) |
frees priority queue, but not the data elements themselves
pqueue | pointer to a priority queue |
Definition at line 1325 of file misc.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArray, and NULL.
Referenced by freeProblem(), nodepairqueueFree(), SCIP_DECL_PROPEXITSOL(), SCIPbendersDeactivate(), SCIPconflictFree(), and subtreeSumGapDelSubtrees().
void SCIPpqueueClear | ( | SCIP_PQUEUE * | pqueue | ) |
clears the priority queue, but doesn't free the data elements themselves
pqueue | priority queue |
Definition at line 1336 of file misc.c.
References assert(), SCIP_PQueue::len, and NULL.
Referenced by conflictClear().
SCIP_RETCODE SCIPpqueueInsert | ( | SCIP_PQUEUE * | pqueue, |
void * | elem ) |
inserts element into priority queue
pqueue | priority queue |
elem | element to be inserted |
Definition at line 1397 of file misc.c.
References assert(), SCIP_PQueue::len, NULL, PQ_PARENT, pqueueElemChgPos(), pqueueResize(), SCIP_CALL, SCIP_OKAY, and SCIP_PQueue::slots.
Referenced by conflictQueueBound(), createAndSplitProblem(), nodepairqueueCreate(), propagateVbounds(), SCIP_DECL_EVENTEXEC(), SCIPbendersActivate(), solveProblem(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().
void SCIPpqueueDelPos | ( | SCIP_PQUEUE * | pqueue, |
int | pos ) |
delete element at specified position, maintaining the heap property
pqueue | priority queue |
pos | position of element that should be deleted |
Definition at line 1436 of file misc.c.
References assert(), SCIP_PQueue::len, NULL, PQ_LEFTCHILD, PQ_PARENT, PQ_RIGHTCHILD, pqueueElemChgPos(), SCIPpqueueNElems(), and SCIP_PQueue::slots.
Referenced by SCIPpqueueRemove(), and subtreeSumGapRemoveNode().
void * SCIPpqueueRemove | ( | SCIP_PQUEUE * | pqueue | ) |
removes and returns best element from the priority queue
pqueue | priority queue |
Definition at line 1496 of file misc.c.
References assert(), SCIP_PQueue::len, NULL, SCIPpqueueDelPos(), and SCIP_PQueue::slots.
Referenced by conflictFirstCand(), conflictRemoveCand(), createSolveSubproblemIndexList(), nodepairqueueRemove(), propagateVbounds(), and solveProblem().
void * SCIPpqueueFirst | ( | SCIP_PQUEUE * | pqueue | ) |
returns the best element of the queue without removing it
pqueue | priority queue |
Definition at line 1516 of file misc.c.
References assert(), SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.
Referenced by conflictFirstCand(), nodepairqueueIsEmpty(), subtreeSumGapComputeFromScratchEfficiently(), and subtreeSumGapRemoveNode().
int SCIPpqueueNElems | ( | SCIP_PQUEUE * | pqueue | ) |
returns the number of elements in the queue
pqueue | priority queue |
Definition at line 1530 of file misc.c.
References assert(), SCIP_PQueue::len, and NULL.
Referenced by conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), createSolveSubproblemIndexList(), propagateVbounds(), SCIP_DECL_EVENTEXEC(), SCIPconflictAnalyze(), SCIPisPropagatedVbounds(), SCIPpqueueDelPos(), SCIPpqueueFind(), solveProblem(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().
void ** SCIPpqueueElems | ( | SCIP_PQUEUE * | pqueue | ) |
returns the elements of the queue; changing the returned array may destroy the queue's ordering!
pqueue | priority queue |
Definition at line 1541 of file misc.c.
References assert(), SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.
Referenced by conflictAddConflictset(), conflictResolveBound(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), and subtreeSumGapStoreNode().
int SCIPpqueueFind | ( | SCIP_PQUEUE * | pqueue, |
void * | elem ) |
return the position of elem
in the priority queue, or -1 if element is not found
pqueue | priority queue |
elem | element to be inserted |
Definition at line 1552 of file misc.c.
References SCIPpqueueNElems(), and SCIP_PQueue::slots.
Referenced by propagateVbounds().