1 /* 2 * divsufsort.h for libdivsufsort 3 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person 6 * obtaining a copy of this software and associated documentation 7 * files (the "Software"), to deal in the Software without 8 * restriction, including without limitation the rights to use, 9 * copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following 12 * conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 24 * OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 27 #ifndef _DIVSUFSORT_H 28 #define _DIVSUFSORT_H 1 29 30 #ifdef __cplusplus 31 extern "C" { 32 #endif /* __cplusplus */ 33 34 #include <inttypes.h> 35 36 #ifndef DIVSUFSORT_API 37 # ifdef DIVSUFSORT_BUILD_DLL 38 # define DIVSUFSORT_API 39 # else 40 # define DIVSUFSORT_API 41 # endif 42 #endif 43 44 /*- Datatypes -*/ 45 #ifndef SAUCHAR_T 46 #define SAUCHAR_T 47 typedef uint8_t sauchar_t; 48 #endif /* SAUCHAR_T */ 49 #ifndef SAINT_T 50 #define SAINT_T 51 typedef int32_t saint_t; 52 #endif /* SAINT_T */ 53 #ifndef SAIDX_T 54 #define SAIDX_T 55 typedef int32_t saidx_t; 56 #endif /* SAIDX_T */ 57 #ifndef PRIdSAINT_T 58 #define PRIdSAINT_T PRId32 59 #endif /* PRIdSAINT_T */ 60 #ifndef PRIdSAIDX_T 61 #define PRIdSAIDX_T PRId32 62 #endif /* PRIdSAIDX_T */ 63 64 65 /*- Prototypes -*/ 66 67 /** 68 * Constructs the suffix array of a given string. 69 * @param T[0..n-1] The input string. 70 * @param SA[0..n-1] The output array of suffixes. 71 * @param n The length of the given string. 72 * @return 0 if no error occurred, -1 or -2 otherwise. 73 */ 74 DIVSUFSORT_API 75 saint_t 76 divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n); 77 78 /** 79 * Constructs the burrows-wheeler transformed string of a given string. 80 * @param T[0..n-1] The input string. 81 * @param U[0..n-1] The output string. (can be T) 82 * @param A[0..n-1] The temporary array. (can be NULL) 83 * @param n The length of the given string. 84 * @return The primary index if no error occurred, -1 or -2 otherwise. 85 */ 86 DIVSUFSORT_API 87 saidx_t 88 divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n); 89 90 /** 91 * Returns the version of the divsufsort library. 92 * @return The version number string. 93 */ 94 DIVSUFSORT_API 95 const char * 96 divsufsort_version(void); 97 98 99 /** 100 * Constructs the burrows-wheeler transformed string of a given string and suffix array. 101 * @param T[0..n-1] The input string. 102 * @param U[0..n-1] The output string. (can be T) 103 * @param SA[0..n-1] The suffix array. (can be NULL) 104 * @param n The length of the given string. 105 * @param idx The output primary index. 106 * @return 0 if no error occurred, -1 or -2 otherwise. 107 */ 108 DIVSUFSORT_API 109 saint_t 110 bw_transform(const sauchar_t *T, sauchar_t *U, 111 saidx_t *SA /* can NULL */, 112 saidx_t n, saidx_t *idx); 113 114 /** 115 * Inverse BW-transforms a given BWTed string. 116 * @param T[0..n-1] The input string. 117 * @param U[0..n-1] The output string. (can be T) 118 * @param A[0..n-1] The temporary array. (can be NULL) 119 * @param n The length of the given string. 120 * @param idx The primary index. 121 * @return 0 if no error occurred, -1 or -2 otherwise. 122 */ 123 DIVSUFSORT_API 124 saint_t 125 inverse_bw_transform(const sauchar_t *T, sauchar_t *U, 126 saidx_t *A /* can NULL */, 127 saidx_t n, saidx_t idx); 128 129 /** 130 * Checks the correctness of a given suffix array. 131 * @param T[0..n-1] The input string. 132 * @param SA[0..n-1] The input suffix array. 133 * @param n The length of the given string. 134 * @param verbose The verbose mode. 135 * @return 0 if no error occurred. 136 */ 137 DIVSUFSORT_API 138 saint_t 139 sufcheck(const sauchar_t *T, const saidx_t *SA, saidx_t n, saint_t verbose); 140 141 /** 142 * Search for the pattern P in the string T. 143 * @param T[0..Tsize-1] The input string. 144 * @param Tsize The length of the given string. 145 * @param P[0..Psize-1] The input pattern string. 146 * @param Psize The length of the given pattern string. 147 * @param SA[0..SAsize-1] The input suffix array. 148 * @param SAsize The length of the given suffix array. 149 * @param idx The output index. 150 * @return The count of matches if no error occurred, -1 otherwise. 151 */ 152 DIVSUFSORT_API 153 saidx_t 154 sa_search(const sauchar_t *T, saidx_t Tsize, 155 const sauchar_t *P, saidx_t Psize, 156 const saidx_t *SA, saidx_t SAsize, 157 saidx_t *left); 158 159 /** 160 * Search for the character c in the string T. 161 * @param T[0..Tsize-1] The input string. 162 * @param Tsize The length of the given string. 163 * @param SA[0..SAsize-1] The input suffix array. 164 * @param SAsize The length of the given suffix array. 165 * @param c The input character. 166 * @param idx The output index. 167 * @return The count of matches if no error occurred, -1 otherwise. 168 */ 169 DIVSUFSORT_API 170 saidx_t 171 sa_simplesearch(const sauchar_t *T, saidx_t Tsize, 172 const saidx_t *SA, saidx_t SAsize, 173 saint_t c, saidx_t *left); 174 175 176 #ifdef __cplusplus 177 } /* extern "C" */ 178 #endif /* __cplusplus */ 179 180 #endif /* _DIVSUFSORT_H */ 181