Showing content from http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/compo__heap_8c.html below:
NCBI C++ ToolKit: src/algo/blast/composition_adjustment/compo_heap.c File Reference
Defines a "heap" data structure that is used to store computed alignments when composition adjustment of scoring matrices is used. More...
Go to the source code of this file.
Go to the SVN repository for this file.
#define COMPO_INTENSE_DEBUG 0 Define COMPO_INTENSE_DEBUG to be true to turn on rigorous but expensive consistency tests in the composition_adjustment module. More...
#define HEAP_INITIAL_CAPACITY 100 The initial capacity of the heap will be set to the smaller of this and the heap threshold. More...
#define HEAP_RESIZE_FACTOR 1.5 When the heap is about to exceed its capacity, it will be grown by the minimum of a multiplicative factor of HEAP_RESIZE_FACTOR and an additive factor of HEAP_MIN_RESIZE. More...
#define HEAP_MIN_RESIZE 100 #define CMP(a, b) ((a)>(b) ? 1 : ((a)<(b) ? -1 : 0)) Return -1/0/1 if a is less than/equal to/greater than b. More...
static int s_CompoHeapRecordCompare (BlastCompo_HeapRecord *place1, BlastCompo_HeapRecord *place2) Compare two records in the heap. More...
static void s_CompoHeapRecordSwap (BlastCompo_HeapRecord *record1, BlastCompo_HeapRecord *record2) Swap two records in the heap. More...
static int s_CompoHeapIsValid (BlastCompo_HeapRecord *heapArray, int i, int n) Verify that the subtree rooted at element i is ordered so as to be as to be a valid heap. More...
static void s_CompoHeapifyDown (BlastCompo_HeapRecord *heapArray, int top, int n) Relocate the top element of a subtree so that on exit the subtree is in valid heap order. More...
static void s_CompoHeapifyUp (BlastCompo_HeapRecord *heapArray, int i) Relocate a leaf in the heap so that the entire heap is in valid heap order. More...
static void s_ConvertToHeap (BlastCompo_Heap *self) Convert a BlastCompo_Heap from a representation as an unordered array to a representation as a heap-ordered array. More...
int BlastCompo_HeapWouldInsert (BlastCompo_Heap *self, double eValue, int score, int subject_index) Return true if self may insert a match that had the given eValue, score and subject_index. More...
static int s_CompHeapRecordInsertAtEnd (BlastCompo_HeapRecord **array, int *length, int *capacity, void *alignments, double eValue, int score, int subject_index) Insert a new heap record at the end of *array, possibly resizing the array to hold the new record. More...
int BlastCompo_HeapInsert (BlastCompo_Heap *self, void *alignments, double eValue, int score, int subject_index, void **discardedAlignments) Try to insert a collection of alignments into a heap. More...
int BlastCompo_HeapFilledToCutoff (const BlastCompo_Heap *self) Return true if only matches with evalue <= self->ecutoff may be inserted. More...
int BlastCompo_HeapInitialize (BlastCompo_Heap *self, int heapThreshold, double ecutoff) Initialize a new BlastCompo_Heap; parameters to this function correspond directly to fields in the BlastCompo_Heap. More...
void BlastCompo_HeapRelease (BlastCompo_Heap *self) Release the storage associated with the fields of a BlastCompo_Heap. More...
void * BlastCompo_HeapPop (BlastCompo_Heap *self) Remove and return the element in the BlastCompo_Heap with largest (worst) evalue; ties are broken according to the order specified by the s_CompoHeapRecordCompare routine. More...
Defines a "heap" data structure that is used to store computed alignments when composition adjustment of scoring matrices is used.
Definition in file compo_heap.c.
◆ CMP #define CMP ( a, b ) ((a)>(b) ? 1 : ((a)<(b) ? -1 : 0))
Return -1/0/1 if a is less than/equal to/greater than b.
Definition at line 66 of file compo_heap.c.
◆ COMPO_INTENSE_DEBUG #define COMPO_INTENSE_DEBUG 0
Define COMPO_INTENSE_DEBUG to be true to turn on rigorous but expensive consistency tests in the composition_adjustment module.
This macro is usually used as part of a C-conditional
}
#define COMPO_INTENSE_DEBUG
Define COMPO_INTENSE_DEBUG to be true to turn on rigorous but expensive consistency tests in the comp...
static DbTestEntry * tests
The C compiler will then validate the code to perform the tests, but will almost always strip the code if COMPO_INTENSE_DEBUG is false.
Definition at line 51 of file compo_heap.c.
◆ HEAP_INITIAL_CAPACITY #define HEAP_INITIAL_CAPACITY 100
The initial capacity of the heap will be set to the smaller of this and the heap threshold.
Definition at line 56 of file compo_heap.c.
◆ HEAP_MIN_RESIZE #define HEAP_MIN_RESIZE 100 ◆ HEAP_RESIZE_FACTOR #define HEAP_RESIZE_FACTOR 1.5
When the heap is about to exceed its capacity, it will be grown by the minimum of a multiplicative factor of HEAP_RESIZE_FACTOR and an additive factor of HEAP_MIN_RESIZE.
The heap never decreases in size
Definition at line 61 of file compo_heap.c.
◆ BlastCompo_HeapRecord ◆ BlastCompo_HeapFilledToCutoff() ◆ BlastCompo_HeapInitialize() ◆ BlastCompo_HeapInsert() int BlastCompo_HeapInsert ( BlastCompo_Heap * self, void * alignments, double eValue, int score, int subject_index, void ** discardedAligns )
Try to insert a collection of alignments into a heap.
-
Parameters
-
self the heap alignments a collection of alignments, in an unspecified format eValue the best evalue among the alignments score the best score among the alignments subject_index the index of the subject sequence in the database discardedAligns a collection of alignments that must be deleted (passed back to the calling routine as this routine does know how to delete them)
-
Returns
-
0 on success, -1 for out of memory
Definition at line 330 of file compo_heap.c.
References assert, BlastCompo_HeapRecord::bestEvalue, BlastCompo_HeapRecord::bestScore, COMPO_INTENSE_DEBUG, NULL, s_CompHeapRecordInsertAtEnd(), s_CompoHeapifyDown(), s_CompoHeapifyUp(), s_CompoHeapIsValid(), s_CompoHeapRecordCompare(), s_ConvertToHeap(), BlastCompo_HeapRecord::subject_index, and BlastCompo_HeapRecord::theseAlignments.
Referenced by Blast_RedoAlignmentCore_MT().
◆ BlastCompo_HeapPop() ◆ BlastCompo_HeapRelease() ◆ BlastCompo_HeapWouldInsert() ◆ s_CompHeapRecordInsertAtEnd() ◆ s_CompoHeapifyDown() ◆ s_CompoHeapifyUp() ◆ s_CompoHeapIsValid() ◆ s_CompoHeapRecordCompare() ◆ s_CompoHeapRecordSwap() ◆ s_ConvertToHeap()
RetroSearch is an open source project built by @garambo
| Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4