Home | History | Annotate | Download | only in android_include
      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