3  * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
30 /*- Private Function -*/
36   saidx_t half, i;  in binarysearch_lower()  local
37   for(i = 0, half = size >> 1;  in binarysearch_lower()
39       size = half, half >>= 1) {  in binarysearch_lower()
40     if(A[i + half] < value) {  in binarysearch_lower()
41       i += half + 1;  in binarysearch_lower()
42       half -= (size & 1) ^ 1;  in binarysearch_lower()
49 /*- Functions -*/
51 /* Burrows-Wheeler transform. */
59   if((T == NULL) || (U == NULL) || (n < 0) || (idx == NULL)) { return -1; }  in bw_transform()
76       p = t - 1;  in bw_transform()
87     p = t - 1;  in bw_transform()
96     U[0] = T[n - 1];  in bw_transform()
97     for(i = 0; A[i] != 0; ++i) { U[i + 1] = T[A[i] - 1]; }  in bw_transform()
99     for(++i; i < n; ++i) { U[i] = T[A[i] - 1]; }  in bw_transform()
110 /* Inverse Burrows-Wheeler transform. */
123     return -1;  in inverse_bw_transform()
129     if((B = (saidx_t *)malloc((size_t)n * sizeof(saidx_t))) == NULL) { return -2; }  in inverse_bw_transform()
148     p = B[p - 1];  in inverse_bw_transform()
172     return -1;  in sufcheck()
179   /* check range: [0..n-1] */  in sufcheck()
185                         n - 1, i, SA[i]);  in sufcheck()
187       return -2;  in sufcheck()
193     if(T[SA[i - 1]] > T[SA[i]]) {  in sufcheck()
198                         i - 1, SA[i - 1], T[SA[i - 1]], i, SA[i], T[SA[i]]);  in sufcheck()
200       return -3;  in sufcheck()
213   q = C[T[n - 1]];  in sufcheck()
214   C[T[n - 1]] += 1;  in sufcheck()
218       c = T[--p];  in sufcheck()
221       c = T[p = n - 1];  in sufcheck()
229                         t, (0 <= t) ? SA[t] : -1, i, SA[i]);  in sufcheck()
231       return -4;  in sufcheck()
235       if((n <= C[c]) || (T[SA[C[c]]] != c)) { C[c] = -1; }  in sufcheck()
252       (i < Tsize) && (j < Psize) && ((r = T[i] - P[j]) == 0); ++i, ++j) { }  in _compare()
254   return (r == 0) ? -(j != Psize) : r;  in _compare()
263   saidx_t size, lsize, rsize, half;  in sa_search()  local
269   if(idx != NULL) { *idx = -1; }  in sa_search()
271      (Tsize < 0) || (Psize < 0) || (SAsize < 0)) { return -1; }  in sa_search()
275   for(i = j = k = 0, lmatch = rmatch = 0, size = SAsize, half = size >> 1;  in sa_search()
277       size = half, half >>= 1) {  in sa_search()
279     r = _compare(T, Tsize, P, Psize, SA[i + half], &match);  in sa_search()
281       i += half + 1;  in sa_search()
282       half -= (size & 1) ^ 1;  in sa_search()
287       lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;  in sa_search()
290       for(llmatch = lmatch, lrmatch = match, half = lsize >> 1;  in sa_search()
292           lsize = half, half >>= 1) {  in sa_search()
294         r = _compare(T, Tsize, P, Psize, SA[j + half], &lmatch);  in sa_search()
296           j += half + 1;  in sa_search()
297           half -= (lsize & 1) ^ 1;  in sa_search()
305       for(rlmatch = match, rrmatch = rmatch, half = rsize >> 1;  in sa_search()
307           rsize = half, half >>= 1) {  in sa_search()
309         r = _compare(T, Tsize, P, Psize, SA[k + half], &rmatch);  in sa_search()
311           k += half + 1;  in sa_search()
312           half -= (rsize & 1) ^ 1;  in sa_search()
323   if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }  in sa_search()
324   return k - j;  in sa_search()
332   saidx_t size, lsize, rsize, half;  in sa_simplesearch()  local
336   if(idx != NULL) { *idx = -1; }  in sa_simplesearch()
337   if((T == NULL) || (SA == NULL) || (Tsize < 0) || (SAsize < 0)) { return -1; }  in sa_simplesearch()
340   for(i = j = k = 0, size = SAsize, half = size >> 1;  in sa_simplesearch()
342       size = half, half >>= 1) {  in sa_simplesearch()
343     p = SA[i + half];  in sa_simplesearch()
344     r = (p < Tsize) ? T[p] - c : -1;  in sa_simplesearch()
346       i += half + 1;  in sa_simplesearch()
347       half -= (size & 1) ^ 1;  in sa_simplesearch()
349       lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;  in sa_simplesearch()
352       for(half = lsize >> 1;  in sa_simplesearch()
354           lsize = half, half >>= 1) {  in sa_simplesearch()
355         p = SA[j + half];  in sa_simplesearch()
356         r = (p < Tsize) ? T[p] - c : -1;  in sa_simplesearch()
358           j += half + 1;  in sa_simplesearch()
359           half -= (lsize & 1) ^ 1;  in sa_simplesearch()
364       for(half = rsize >> 1;  in sa_simplesearch()
366           rsize = half, half >>= 1) {  in sa_simplesearch()
367         p = SA[k + half];  in sa_simplesearch()
368         r = (p < Tsize) ? T[p] - c : -1;  in sa_simplesearch()
370           k += half + 1;  in sa_simplesearch()
371           half -= (rsize & 1) ^ 1;  in sa_simplesearch()
379   if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }  in sa_simplesearch()
380   return k - j;  in sa_simplesearch()