NCBI C++ ToolKit
Functions
lookup_util.h File Reference

Utility functions for lookup table generation. More...

#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/blast_def.h>
+ Include dependency graph for lookup_util.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Go to the SVN repository for this file.

Functions

Int4 iexp (Int4 x, Int4 n)
 Integer exponentiation using right to left binary algorithm. More...
 
Int4 ilog2 (Int8 x)
 Integer base two logarithm. More...
 
void debruijn (Int4 n, Int4 k, Uint1 *output, Uint1 *alphabet)
 generates a de Bruijn sequence containing all substrings of length n over an alphabet of size k. More...
 
Int4 EstimateNumTableEntries (BlastSeqLoc *location, Int4 *max_off)
 Given a list of query locations, estimate the number of words that would need to be added to a lookup table. More...
 

Detailed Description

Utility functions for lookup table generation.

Definition in file lookup_util.h.

Function Documentation

◆ debruijn()

void debruijn ( Int4  n,
Int4  k,
Uint1 output,
Uint1 alphabet 
)

generates a de Bruijn sequence containing all substrings of length n over an alphabet of size k.

if alphabet is not NULL, use it as a translation table for the output. expects that "output" has already been allocated and is at least k^n in size.

Parameters
nthe number of letters in each word
kthe size of the alphabet
outputthe output sequence
alphabetoptional translation alphabet

Definition at line 170 of file lookup_util.c.

References a, calloc(), fkm(), n, output, and sfree.

Referenced by NtlookupTestFixture::debruijnInit(), and AalookupTestFixture::GetSeqBlk().

◆ EstimateNumTableEntries()

Int4 EstimateNumTableEntries ( BlastSeqLoc location,
Int4 max_off 
)

Given a list of query locations, estimate the number of words that would need to be added to a lookup table.

The estimate is currently intended for nucleotide locations, and ignores ambiguities and the actual width of a lookup table word

Parameters
locationA linked list of locations to index [in]
max_offupper bound on the largest query offset to be indexed [out]
Returns
The approximate number of lookup table entries

Definition at line 190 of file lookup_util.c.

References SSeqRange::left, location, MAX, BlastSeqLoc::next, SSeqRange::right, and BlastSeqLoc::ssr.

Referenced by LookupTableWrapInit_MT().

◆ iexp()

Int4 iexp ( Int4  x,
Int4  n 
)

Integer exponentiation using right to left binary algorithm.

See knuth TAOCP vol. 2, section 4.6.3.

Parameters
xx
nn
Returns
x to the n-th power

Definition at line 47 of file lookup_util.c.

References n, and r().

Referenced by BlastCompressedAaLookupTableNew(), NtlookupTestFixture::debruijnInit(), and AalookupTestFixture::GetSeqBlk().

◆ ilog2()

Int4 ilog2 ( Int8  x)

Integer base two logarithm.

Parameters
xx
Returns
lg(x)

Definition at line 71 of file lookup_util.c.

Referenced by BlastAaLookupTableNew(), BlastMBLookupTableNew(), CCachedSeqDataForRemote::GetSeqDataChunk(), RPSLookupTableNew(), and s_CompressedLookupFinalize().

Modified on Sun Apr 21 03:44:00 2024 by modify_doxy.py rev. 669887