wimlib.net Git - wimlib/blob - src/divsufsort/divsufsort.h

   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  * @param bucket_A Temporary space (size >= 256)
  73  * @param bucket_B Temporary space (size >= 256 * 256)
  74  *
  75  * @return 0
  76  */
  77 DIVSUFSORT_API
  78 saint_t
  79 divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n,
  80      saidx_t *bucket_A, saidx_t *bucket_B);
  81
  82 #if 0
  83
  84 /**
  85  * Constructs the burrows-wheeler transformed string of a given string.
  86  * @param T[0..n-1] The input string.
  87  * @param U[0..n-1] The output string. (can be T)
  88  * @param A[0..n-1] The temporary array. (can be NULL)
  89  * @param n The length of the given string.
  90  * @return The primary index if no error occurred, -1 or -2 otherwise.
  91  */
  92 DIVSUFSORT_API
  93 saidx_t
  94 divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);
  95
  96 /**
  97  * Returns the version of the divsufsort library.
  98  * @return The version number string.
  99  */
 100 DIVSUFSORT_API
 101 const char *
 102 divsufsort_version(void);
 103
 104
 105 /**
 106  * Constructs the burrows-wheeler transformed string of a given string and suffix array.
 107  * @param T[0..n-1] The input string.
 108  * @param U[0..n-1] The output string. (can be T)
 109  * @param SA[0..n-1] The suffix array. (can be NULL)
 110  * @param n The length of the given string.
 111  * @param idx The output primary index.
 112  * @return 0 if no error occurred, -1 or -2 otherwise.
 113  */
 114 DIVSUFSORT_API
 115 saint_t
 116 bw_transform(const sauchar_t *T, sauchar_t *U,
 117              saidx_t *SA /* can NULL */,
 118              saidx_t n, saidx_t *idx);
 119
 120 /**
 121  * Inverse BW-transforms a given BWTed string.
 122  * @param T[0..n-1] The input string.
 123  * @param U[0..n-1] The output string. (can be T)
 124  * @param A[0..n-1] The temporary array. (can be NULL)
 125  * @param n The length of the given string.
 126  * @param idx The primary index.
 127  * @return 0 if no error occurred, -1 or -2 otherwise.
 128  */
 129 DIVSUFSORT_API
 130 saint_t
 131 inverse_bw_transform(const sauchar_t *T, sauchar_t *U,
 132                      saidx_t *A /* can NULL */,
 133                      saidx_t n, saidx_t idx);
 134
 135 /**
 136  * Checks the correctness of a given suffix array.
 137  * @param T[0..n-1] The input string.
 138  * @param SA[0..n-1] The input suffix array.
 139  * @param n The length of the given string.
 140  * @param verbose The verbose mode.
 141  * @return 0 if no error occurred.
 142  */
 143 DIVSUFSORT_API
 144 saint_t
 145 sufcheck(const sauchar_t *T, const saidx_t *SA, saidx_t n, saint_t verbose);
 146
 147 /**
 148  * Search for the pattern P in the string T.
 149  * @param T[0..Tsize-1] The input string.
 150  * @param Tsize The length of the given string.
 151  * @param P[0..Psize-1] The input pattern string.
 152  * @param Psize The length of the given pattern string.
 153  * @param SA[0..SAsize-1] The input suffix array.
 154  * @param SAsize The length of the given suffix array.
 155  * @param idx The output index.
 156  * @return The count of matches if no error occurred, -1 otherwise.
 157  */
 158 DIVSUFSORT_API
 159 saidx_t
 160 sa_search(const sauchar_t *T, saidx_t Tsize,
 161           const sauchar_t *P, saidx_t Psize,
 162           const saidx_t *SA, saidx_t SAsize,
 163           saidx_t *left);
 164
 165 /**
 166  * Search for the character c in the string T.
 167  * @param T[0..Tsize-1] The input string.
 168  * @param Tsize The length of the given string.
 169  * @param SA[0..SAsize-1] The input suffix array.
 170  * @param SAsize The length of the given suffix array.
 171  * @param c The input character.
 172  * @param idx The output index.
 173  * @return The count of matches if no error occurred, -1 otherwise.
 174  */
 175 DIVSUFSORT_API
 176 saidx_t
 177 sa_simplesearch(const sauchar_t *T, saidx_t Tsize,
 178                 const saidx_t *SA, saidx_t SAsize,
 179                 saint_t c, saidx_t *left);
 180 #endif
 181
 182
 183 #ifdef __cplusplus
 184 } /* extern "C" */
 185 #endif /* __cplusplus */
 186
 187 #endif /* _DIVSUFSORT_H */