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

n	the number of letters in each word
k	the size of the alphabet
output	the output sequence
alphabet	optional 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

location	A linked list of locations to index [in]
max_off	upper 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

x	x
n	n

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

x

x

Returns

lg(x)

Definition at line 71 of file lookup_util.c.

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