NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
rank_dictionary_inl.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 namespace nvbio {
29 
30 //
31 // Build the occurrence table for a given string, packing a set of counters
32 // every K elements.
33 // The table must contain ((n+K-1)/K)*4 entries.
34 //
35 // Optionally save the table of the global counters as well.
36 //
37 // \param begin symbol sequence begin
38 // \param end symbol sequence end
39 // \param occ output occurrence map
40 // \param cnt optional table of the global counters
41 //
42 template <uint32 SYMBOL_SIZE, uint32 K, typename SymbolIterator, typename IndexType>
44  SymbolIterator begin,
45  SymbolIterator end,
46  IndexType* occ,
47  IndexType* cnt)
48 {
49  const uint32 N_SYMBOLS = 1u << SYMBOL_SIZE;
50 
51  IndexType counters[N_SYMBOLS] = { 0u };
52 
53  const IndexType n = end - begin;
54 
55  for (IndexType i = 0; i < n; ++i)
56  {
57  const IndexType i_mod_K = i & (K-1);
58 
59  if (i_mod_K == 0)
60  {
61  // save the counters
62  const uint32 k = i / K;
63  for (uint32 c = 0; c < N_SYMBOLS; ++c)
64  occ[ k*N_SYMBOLS + c ] = counters[c];
65  }
66 
67  // update counters
68  ++counters[ begin[i] ];
69  }
70 
71  if (cnt)
72  {
73  // build a cumulative table of the final counters
74  for (uint32 i = 0; i < N_SYMBOLS; ++i)
75  cnt[i] = counters[i];
76  }
77 }
78 
79 //
80 // TODO: CUDA build_occurrence_table
81 //
82 // 1. load 4 * 128 ints per cta in smem
83 // have each thread reduce/scan 4 ints (=64bps)
84 // have each warp do 2 2-short packed warp reduction/scans
85 // have 1 warp do the final block-wide reduction
86 // save block counters
87 //
88 // 2. scan blocks
89 //
90 // 3. redo 1. using block values
91 //
92 
93 // sum a uint4 and a uchar4 packed into a uint32.
94 //
96 void unpack_add(uint4* op1, const uint32 op2)
97 {
98  op1->x += (op2 & 0xff);
99  op1->y += (op2 >> 8 & 0xff);
100  op1->z += (op2 >> 16 & 0xff);
101  op1->w += (op2 >> 24);
102 }
104 void unpack_add(uint64_4* op1, const uint32 op2)
105 {
106  op1->x += (op2 & 0xff);
107  op1->y += (op2 >> 8 & 0xff);
108  op1->z += (op2 >> 16 & 0xff);
109  op1->w += (op2 >> 24);
110 }
111 
112 namespace occ {
113 
114 // overload popc_nbit and popc_nbit_all so that they look the same
115 template <uint32 N, typename T> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint32 mask, const T c) { return nvbio::popc_2bit_all( mask, c ); }
116 template <uint32 N, typename T> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint32 mask, const T c, const uint32 i) { return nvbio::popc_2bit_all( mask, c, i ); }
117 template <uint32 N> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint32 mask, const uint32 c) { return nvbio::popc_nbit<N>( mask, c ); }
118 template <uint32 N> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint32 mask, const uint32 c, const uint32 i) { return nvbio::popc_nbit<N>( mask, c, i ); }
119 
120 // overload popc_nbit and popc_nbit_all so that they look the same
121 template <uint32 N, typename T> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint64 mask, const T c) { return nvbio::popc_2bit_all( mask, c ); }
122 template <uint32 N, typename T> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint64 mask, const T c, const uint32 i) { return nvbio::popc_2bit_all( mask, c, i ); }
123 template <uint32 N> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint64 mask, const uint32 c) { return nvbio::popc_nbit<N>( mask, c ); }
124 template <uint32 N> NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 popc_nbit(const uint64 mask, const uint32 c, const uint32 i) { return nvbio::popc_nbit<N>( mask, c, i ); }
125 
126 // pop-count all the occurrences of c in each of the 32-bit masks in text[begin, end],
127 // where the last mask is truncated to i.
128 //
129 template <uint32 N, typename TextString, typename T>
131  const TextString text,
132  const T c,
133  const uint32 begin,
134  const uint32 end)
135 {
136  uint32 x = 0;
137  for (uint32 j = begin; j < end; ++j)
138  x += occ::popc_nbit<N>( text[j], c );
139 
140  return x;
141 }
142 // pop-count all the occurrences of c in each of the 32-bit masks in text[begin, end],
143 // where the last mask is truncated to i.
144 //
145 template <uint32 N, typename TextString, typename T>
147  const TextString text,
148  const T c,
149  const uint32 begin,
150  const uint32 end,
151  const uint32 i)
152 {
153  uint32 x = 0;
154  for (uint32 j = begin; j < end; ++j)
155  x += occ::popc_nbit<N>( text[j], c );
156 
157  return x + occ::popc_nbit<N>( text[ end ], c, i );
158 }
159 
160 // pop-count all the occurrences of c in each of the 32-bit masks in text[begin, end],
161 // where the last mask is truncated to i.
162 //
163 template <uint32 N, typename TextString, typename T, typename W>
165  const TextString text,
166  const T c,
167  const uint32 begin,
168  const uint32 end,
169  const uint32 i,
170  W& last_mask)
171 {
172  uint32 x = 0;
173  for (uint32 j = begin; j < end; ++j)
174  x += occ::popc_nbit<N>( text[j], c );
175 
176  last_mask = text[ end ];
177  return x + occ::popc_nbit<N>( last_mask, c, i );
178 }
179 
180 } // namespace occ
181 
182 // fetch the text character at position i in the rank dictionary
183 //
184 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
186 {
187  return dict.m_text[i];
188 }
189 
190 // fetch the text character at position i in the rank dictionary
191 //
192 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
194 {
195  return dict.m_text[i];
196 }
197 
198 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable, typename WordType, typename OccType>
199 struct dispatch_rank {};
200 
201 template <uint32 N, typename T>
203 
204 template <>
206 {
207  static const uint32 LOG_SYMS_PER_WORD = 4;
208  static const uint32 SYMS_PER_WORD = 16;
209 };
210 template <>
212 {
213  static const uint32 LOG_SYMS_PER_WORD = 5;
214  static const uint32 SYMS_PER_WORD = 32;
215 };
216 
217 template <>
219 {
220  static const uint32 LOG_SYMS_PER_WORD = 3;
221  static const uint32 SYMS_PER_WORD = 8;
222 };
223 template <>
225 {
226  static const uint32 LOG_SYMS_PER_WORD = 4;
227  static const uint32 SYMS_PER_WORD = 16;
228 };
229 
230 template <>
232 {
233  static const uint32 LOG_SYMS_PER_WORD = 2;
234  static const uint32 SYMS_PER_WORD = 4;
235 };
236 template <>
238 {
239  static const uint32 LOG_SYMS_PER_WORD = 3;
240  static const uint32 SYMS_PER_WORD = 8;
241 };
242 
243 template <uint32 SYMBOL_SIZE, uint32 K, typename TextStorage, typename OccIterator, typename CountTable, typename word_type, typename index_type>
244 struct dispatch_rank<SYMBOL_SIZE,K,PackedStream<TextStorage,uint8,SYMBOL_SIZE,true,index_type>,OccIterator,CountTable,word_type,index_type>
245 {
248 
251  static const uint32 SYMBOL_COUNT = 1u << SYMBOL_SIZE;
252 
257 
258  // pop-count the occurrences of symbols in two given text blocks, switching
259  // between pop-counting a single symbol if T is a uint32, or all 4 symbols
260  // if T is the count-table.
261  template <typename T>
263  const TextStorage text,
264  const range_type range,
265  const uint32 kl,
266  const uint32 kh,
267  const T c)
268  {
269  const uint32 ml = (range.x - kl*K) >> LOG_SYMS_PER_WORD;
270  const uint32 mh = (range.y - kh*K) >> LOG_SYMS_PER_WORD;
271 
272  const word_type l_mod = ~word_type(range.x) & (SYMS_PER_WORD-1);
273  const word_type h_mod = ~word_type(range.y) & (SYMS_PER_WORD-1);
274 
275  const uint32 offl = kl*(K >> LOG_SYMS_PER_WORD);
276 
277  // sum up all the pop-counts of the relevant masks, up to ml-1
278  uint32 xl = occ::popc_nbit<SYMBOL_SIZE>( text, c, offl, offl + ml );
279 
280  // check whether we can share the base value for the entire range
281  uint32 xh = (kl == kh) ? xl : 0u;
282  uint32 startm = (kl == kh) ? ml+1 : 0u;
283 
284  const word_type mask = text[ offl + ml ];
285  xl += occ::popc_nbit<SYMBOL_SIZE>( mask, c, l_mod );
286 
287  // if the range fits in a single block, add the last mask to xh
288  if (kl == kh)
289  xh += occ::popc_nbit<SYMBOL_SIZE>( mask, c, (mh == ml) ? h_mod : 0u );
290 
291  // finish computing the end of the range
292  if (kl != kh || mh > ml)
293  {
294  const uint32 offh = kh*(K >> LOG_SYMS_PER_WORD);
295  xh += occ::popc_nbit<SYMBOL_SIZE>( text, c, offh + startm, offh + mh, h_mod );
296  }
297  return make_uint2( xl, xh );
298  }
299 
300  // fetch the number of occurrences of character c in the substring [0,i]
301  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type run(const dictionary_type& dict, const index_type i, const uint32 c)
302  {
303  if (i == index_type(-1))
304  return 0u;
305 
306  const uint32 k = uint32( i / K );
307  const uint32 m = (i - k*K) >> LOG_SYMS_PER_WORD;
308  const word_type i_mod = ~word_type(i) & (SYMS_PER_WORD-1);
309 
310  // fetch base occurrence counter
311  const index_type out = dict.m_occ[ k*SYMBOL_COUNT + c ];
312 
313  const uint32 off = k*(K >> LOG_SYMS_PER_WORD);
314 
315  // sum up all the pop-counts of the relevant masks
316  return out + occ::popc_nbit<SYMBOL_SIZE>( dict.m_text.stream(), c, off, off + m, i_mod );
317  }
318  // fetch the number of occurrences of character c in the substring [0,i]
320  {
321  // check whether we're searching the empty range
322  if (range.x == index_type(-1) && range.y == index_type(-1))
323  return make_vector( index_type(0), index_type(0) );
324 
325  // check whether we're searching for one index only
326  if (range.x == index_type(-1) || range.x == range.y)
327  {
328  const index_type r = run( dict, range.y, c );
329  return make_vector( r, r );
330  }
331 
332  const uint32 kl = uint32( range.x / K );
333  const uint32 kh = uint32( range.y / K );
334 
335  // fetch base occurrence counters for the respective blocks
336  const index_type outl = dict.m_occ[ kl*SYMBOL_COUNT + c ];
337  const index_type outh = (kl == kh) ? outl : dict.m_occ[ kh*SYMBOL_COUNT + c ];
338 
339  const uint2 r = popcN( dict.m_text.stream(), range, kl, kh, c );
340 
341  return make_vector( outl + r.x, outh + r.y );
342  }
343 
344  //
345  // NOTICE: the run4 methods are ONLY valid when SYMBOL_SIZE == 2
346  //
347 
348  // fetch the number of occurrences of character c in the substring [0,i]
349  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE vec4_type run4(const dictionary_type& dict, const index_type i)
350  {
351  const uint32 k = uint32( i / K );
352  const uint32 m = (i - k*K) >> LOG_SYMS_PER_WORD;
353 
354  // fetch base occurrence counters for all symbols in the respective block
355  vec4_type r = make_vector( dict.m_occ[k*4+0], dict.m_occ[k*4+1], dict.m_occ[k*4+2], dict.m_occ[k*4+3] );
356 
357  const uint32 off = k*(K >> LOG_SYMS_PER_WORD);
358  const uint32 x = occ::popc_nbit<2>( dict.m_text.stream(), dict.m_count_table, off, off + m, ~word_type(i) & (SYMS_PER_WORD-1) );
359 
360  // add the packed counters to the output result
361  unpack_add( &r, x );
362  return r;
363  }
364  // fetch the number of occurrences of character c in the substring [0,i]
365  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void run4(const dictionary_type& dict, const index_type i, vec4_type* out)
366  {
367  *out = run4( dict, i );
368  }
369  // fetch the number of occurrences of character c in the substring [0,i]
370  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void run4(const dictionary_type& dict, const range_type range, vec4_type* outl, vec4_type* outh)
371  {
372  const uint32 kl = uint32( range.x / K );
373  const uint32 kh = uint32( range.y / K );
374 
375  // fetch base occurrence counters for for all symbols in the respective blocks
376  *outl = make_vector( dict.m_occ[kl*4+0], dict.m_occ[kl*4+1], dict.m_occ[kl*4+2], dict.m_occ[kl*4+3] );
377  *outh = (kl == kh) ? *outl : make_vector( dict.m_occ[kh*4+0], dict.m_occ[kh*4+1], dict.m_occ[kh*4+2], dict.m_occ[kh*4+3] );
378 
379  const uint2 r = popcN( dict.m_text.stream(), range, kl, kh, dict.m_count_table );
380 
381  // add the packed counters to the output result
382  unpack_add( outl, r.x );
383  unpack_add( outh, r.y );
384  }
385 
386  // fetch the number of occurrences of character c in the substring [0,i]
387  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void run_all(const dictionary_type& dict, const index_type i, vector_type* out)
388  {
389  if (SYMBOL_SIZE == 4)
390  {
391  const vec4_type r = run4( dict, i );
392  (*out)[0] = r.x; (*out)[1] = r.y; (*out)[2] = r.z; (*out)[3] = r.w;
393  }
394  else
395  {
396  for (uint32 s = 0; s < SYMBOL_COUNT; ++s)
397  (*out)[s] = rank( dict, i, s );
398  }
399  }
400  // fetch the number of occurrences of character c in the substring [0,i]
402  {
403  if (SYMBOL_SIZE == 4)
404  {
405  vec4_type l, h;
406 
407  run4( dict, range, &l, &h );
408 
409  (*outl)[0] = l.x; (*outl)[1] = l.y; (*outl)[2] = l.z; (*outl)[3] = l.w;
410  (*outh)[0] = h.x; (*outh)[1] = h.y; (*outh)[2] = h.z; (*outh)[3] = h.w;
411  }
412  else
413  {
414  for (uint32 s = 0; s < SYMBOL_COUNT; ++s)
415  {
416  const vec2_type r = rank( dict, range, s );
417  (*outl)[s] = r.x;
418  (*outh)[s] = r.y;
419  }
420  }
421  }
422 };
423 
424 template <typename TextStorage, typename OccIterator, typename CountTable>
425 struct dispatch_rank<2,64,PackedStream<TextStorage,uint8,2u,true>,OccIterator,CountTable,uint4,uint4>
426 {
427  static const uint32 LOG_K = 6;
428  static const uint32 K = 64;
429 
432 
434  typedef uint2 range_type;
436 
437  // pop-count the occurrences of symbols in a given text block, switching
438  // between pop-counting a single symbol if T is a uint32, or all 4 symbols
439  // if T is the count-table.
440  template <typename T>
442  const TextStorage text,
443  const uint32 i,
444  const uint32 k,
445  const T c)
446  {
447  const uint32 m = (i - k*K) >> 4u;
448  const uint32 i_16 = ~i&15;
449 
450  // sum up all the pop-counts of the relevant masks
451  const uint4 masks = text[ k ];
452  uint32 x = 0;
453  if (m > 0) x += occ::popc_nbit<2>( masks.x, c );
454  if (m > 1) x += occ::popc_nbit<2>( masks.y, c );
455  if (m > 2) x += occ::popc_nbit<2>( masks.z, c );
456 
457  // fetch the m-th mask and pop-count its nucleotides only up to i_mod_16
458  return x + occ::popc_nbit<2>( comp( masks, m ), c, i_16 );
459  }
460 
461  // pop-count the occurrences of symbols in two given text blocks, switching
462  // between pop-counting a single symbol if T is a uint32, or all 4 symbols
463  // if T is the count-table.
464  template <typename T>
466  const TextStorage text,
467  const uint2 range,
468  const uint32 kl,
469  const uint32 kh,
470  const T c)
471  {
472  const uint32 ml = (range.x - kl*K) >> 4u;
473  const uint32 mh = (range.y - kh*K) >> 4u;
474 
475  const uint32 l_16 = ~range.x & 15;
476  const uint32 h_16 = ~range.y & 15;
477 
478  // fetch the 128-bit text masks for the respective blocks
479  const uint4 masks_l = text[ kl ];
480  const uint4 masks_h = (kl == kh) ? masks_l : text[ kh ];
481 
482  // sum up all the pop-counts of the relevant masks
483  uint32 xl = 0u;
484  if (ml > 0) xl += occ::popc_nbit<2>( masks_l.x, c );
485  if (ml > 1) xl += occ::popc_nbit<2>( masks_l.y, c );
486  if (ml > 2) xl += occ::popc_nbit<2>( masks_l.z, c );
487 
488  uint32 xh = (kl == kh) ? xl : 0u;
489  uint32 startm = (kl == kh) ? ml : 0u;
490 
491  // sum up all the pop-counts of the relevant masks
492  if (mh > 0 && startm == 0) xh += occ::popc_nbit<2>( masks_h.x, c );
493  if (mh > 1 && startm <= 1) xh += occ::popc_nbit<2>( masks_h.y, c );
494  if (mh > 2 && startm <= 2) xh += occ::popc_nbit<2>( masks_h.z, c );
495 
496  xl += occ::popc_nbit<2>( comp( masks_l, ml ), c, l_16 );
497  xh += occ::popc_nbit<2>( comp( masks_h, mh ), c, h_16 );
498  return make_uint2( xl, xh );
499  }
500 
501  // fetch the number of occurrences of character c in the substring [0,i]
503  {
504  if (i == uint32(-1))
505  return 0u;
506 
507  const uint32 k = i >> LOG_K;
508 
509  // fetch base occurrence counter
510  const uint32 out = comp( dict.m_occ[ k ], c );
511 
512  return out + popc( dict.m_text.stream(), i, k, c );
513  }
514  // fetch the number of occurrences of character c in the substring [0,i]
515  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint2 run(const dictionary_type& dict, const uint2 range, const uint32 c)
516  {
517  // check whether we're searching the empty range
518  if (range.x == uint32(-1) && range.y == uint32(-1))
519  return make_uint2(0u,0u);
520 
521  // check whether we're searching for one index only
522  if (range.x == uint32(-1) || range.x == range.y)
523  {
524  const uint32 r = run( dict, range.y, c );
525  return make_uint2( range.x == uint32(-1) ? 0u : r, r );
526  }
527 
528  const uint32 kl = range.x >> LOG_K;
529  const uint32 kh = range.y >> LOG_K;
530 
531  // fetch the base occurrence counter at the beginning of the low block
532  const uint32 outl = comp( dict.m_occ[ kl ], c );
533  const uint32 outh = (kl == kh) ? outl : comp( dict.m_occ[ kh ], c );
534 
535  const uint2 r = popc2( dict.m_text.stream(), range, kl, kh, c );
536 
537  return make_uint2( outl + r.x, outh + r.y );
538  }
539  // fetch the number of occurrences of character c in the substring [0,i]
540  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint4 run4(const dictionary_type& dict, const uint32 i)
541  {
542  const uint32 k = i >> LOG_K;
543 
544  // fetch the base occurrence counter at the beginning of the block
545  uint4 r = dict.m_occ[k];
546 
547  const uint32 x = popc( dict.m_text.stream(), i, k, dict.m_count_table );
548 
549  // add the packed counters to the output result
550  unpack_add( &r, x );
551  return r;
552  }
553  // fetch the number of occurrences of character c in the substring [0,i]
554  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void run4(const dictionary_type& dict, const uint32 i, uint4* out)
555  {
556  *out = run4( dict, i );
557  }
558  // fetch the number of occurrences of character c in the substring [0,i]
559  static NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void run4(const dictionary_type& dict, const uint2 range, uint4* outl, uint4* outh)
560  {
561  const uint32 kl = range.x >> LOG_K;
562  const uint32 kh = range.y >> LOG_K;
563 
564  // fetch the base occurrence counters at the beginning of the respective blocks
565  *outl = dict.m_occ[kl];
566  *outh = (kl == kh) ? *outl : dict.m_occ[kh];
567 
568  const uint2 r = popc2( dict.m_text.stream(), range, kl, kh, dict.m_count_table );
569 
570  // add the packed counters to the output result
571  unpack_add( outl, r.x );
572  unpack_add( outh, r.y );
573  }
574 
575  // fetch the number of occurrences of character c in the substring [0,i]
577  {
578  *out = run4( dict, i );
579  }
580  // fetch the number of occurrences of character c in the substring [0,i]
582  {
583  run4( dict, range, &outl->data, &outh->data );
584  }
585 };
586 
587 // fetch the number of occurrences of character c in the substring [0,i]
588 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
590  const rank_dictionary<SYMBOL_SIZE_T,K,TextString,OccIterator,CountTable>& dict, const IndexType i, const uint32 c)
591 {
592  typedef typename TextString::storage_type word_type;
593  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
594 
596  dict, i, c );
597 }
598 
599 // fetch the number of occurrences of character c in the substring [0,i]
600 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
603 {
604  typedef typename TextString::storage_type word_type;
605  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
606 
608  dict, range, c );
609 }
610 
611 // fetch the number of occurrences of character c in the substring [0,i]
612 template <uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
615  const rank_dictionary<2,K,TextString,OccIterator,CountTable>& dict, const IndexType i)
616 {
617  typedef typename TextString::storage_type word_type;
618  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
619 
621  dict, i );
622 }
623 
624 // fetch the number of occurrences of character c in the substring [0,i]
625 template <uint32 K, typename TextString, typename OccIterator, typename CountTable>
627 void rank4(
628  const rank_dictionary<2,K,TextString,OccIterator,CountTable>& dict, const uint2 range, uint4* outl, uint4* outh)
629 {
630  typedef typename TextString::storage_type word_type;
631  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
632 
634  dict, range, outl, outh );
635 }
636 
637 // fetch the number of occurrences of character c in the substring [0,i]
638 template <uint32 K, typename TextString, typename OccIterator, typename CountTable>
640 void rank4(
642 {
643  typedef typename TextString::storage_type word_type;
644  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
645 
647  dict, range, outl, outh );
648 }
649 
650 // fetch the number of occurrences of character c in the substring [0,i]
651 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
653 typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::vector_type
657 {
658  typedef typename TextString::storage_type word_type;
659  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
660 
662 
664  dict, i, &out );
665 
666  return out;
667 }
668 
669 // fetch the number of occurrences of character c in the substring [0,i]
670 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
672 void rank_all(
676 {
677  typedef typename TextString::storage_type word_type;
678  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
679 
681  dict, i, out );
682 }
683 
684 // fetch the number of occurrences of character c in the substring [0,i]
685 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
687 void rank_all(
692 {
693  typedef typename TextString::storage_type word_type;
694  typedef typename std::iterator_traits<OccIterator>::value_type occ_type;
695 
697  dict, range, outl, outh );
698 }
699 
700 
701 } // namespace nvbio