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 1295 of file misc.c.
References assert(), BMSallocMemory, MAX, NULL, pqueueResize(), SCIP_ALLOC, SCIP_CALL, and SCIP_OKAY.
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 1322 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 1333 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 1394 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 1433 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 1493 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 1513 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 1527 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 1538 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 1549 of file misc.c.
References SCIPpqueueNElems(), and SCIP_PQueue::slots.
Referenced by propagateVbounds().