NCBI C++ ToolKit
lookup_util.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: lookup_util.h 73100 2016-06-20 15:45:40Z boratyng $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  */
26 
27 /** @file lookup_util.h
28  * Utility functions for lookup table generation.
29  */
30 
31 #ifndef ALGO_BLAST_CORE__LOOKUP_UTIL__H
32 #define ALGO_BLAST_CORE__LOOKUP_UTIL__H
33 
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
41 /** Integer exponentiation using right to left binary algorithm.
42  * See knuth TAOCP vol. 2, section 4.6.3.
43  *
44  * @param x x
45  * @param n n
46  * @return x to the n-th power
47  */
48 
50 Int4 iexp(Int4 x, Int4 n);
51 
52 /**
53  * Integer base two logarithm.
54  *
55  * @param x x
56  * @return lg(x)
57  */
58 
60 Int4 ilog2(Int8 x);
61 
62 /**
63  * generates a de Bruijn sequence containing all substrings
64  * of length n over an alphabet of size k.
65  * if alphabet is not NULL, use it as a translation table
66  * for the output.
67  * expects that "output" has already been allocated and is at
68  * least k^n in size.
69  *
70  * @param n the number of letters in each word
71  * @param k the size of the alphabet
72  * @param output the output sequence
73  * @param alphabet optional translation alphabet
74  */
75 
77 void debruijn(Int4 n, Int4 k, Uint1* output, Uint1* alphabet);
78 
79 /** Given a list of query locations, estimate the number of words
80  * that would need to be added to a lookup table. The estimate is
81  * currently intended for nucleotide locations, and ignores ambiguities
82  * and the actual width of a lookup table word
83  * @param location A linked list of locations to index [in]
84  * @param max_off upper bound on the largest query offset
85  * to be indexed [out]
86  * @return The approximate number of lookup table entries
87  */
88 
91 
92 #ifdef __cplusplus
93 }
94 #endif
95 
96 #endif /* !ALGO_BLAST_CORE__LOOKUP_UTIL__H */
Definitions used throughout BLAST.
#define NCBI_XBLAST_EXPORT
NULL operations for other cases.
Definition: blast_export.h:65
static SQLCHAR output[256]
Definition: print.c:5
static const char location[]
Definition: config.c:97
uint8_t Uint1
1-byte (8-bit) unsigned integer
Definition: ncbitype.h:99
int32_t Int4
4-byte (32-bit) signed integer
Definition: ncbitype.h:102
int64_t Int8
8-byte (64-bit) signed integer
Definition: ncbitype.h:104
yy_size_t n
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...
Definition: lookup_util.c:190
Int4 iexp(Int4 x, Int4 n)
Integer exponentiation using right to left binary algorithm.
Definition: lookup_util.c:47
Int4 ilog2(Int8 x)
Integer base two logarithm.
Definition: lookup_util.c:71
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.
Definition: lookup_util.c:170
Type and macro definitions from C toolkit that are not defined in C++ toolkit.
Used to hold a set of positions, mostly used for filtering.
Definition: blast_def.h:204
Modified on Wed Apr 24 14:15:58 2024 by modify_doxy.py rev. 669887