NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fmindex.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 #pragma once
29 
30 #include <nvbio/basic/types.h>
31 #include <nvbio/basic/packedstream.h>
32 #include <nvbio/fmindex/rank_dictionary.h>
33 #include <nvbio/strings/string_traits.h>
34 
35 namespace nvbio {
36 
313 
316 
341 template <
342  typename TRankDictionary,
343  typename TSuffixArray,
344  typename TL2 = null_type>
345 struct fm_index
346 {
347  typedef TRankDictionary rank_dictionary_type;
348  typedef typename TRankDictionary::text_type bwt_type;
349  typedef TSuffixArray suffix_array_type;
350 
351  typedef typename TRankDictionary::index_type index_type; // type used for indexing
352  typedef typename TRankDictionary::range_type range_type; // type used for range searches
353  typedef typename TRankDictionary::vector_type vector_type; // type used for character-wide searches
354 
355  typedef typename if_equal<TL2,null_type,const index_type*,TL2>::type L2_iterator;
356 
357  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type length() const { return m_length; }
358  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type primary() const { return m_primary; }
359  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type count(const uint32 c) const { return m_L2[c+1] - m_L2[c]; }
360  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type L2(const uint32 c) const { return m_L2[c]; }
361  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TRankDictionary rank_dict() const { return m_rank_dict; }
362  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TSuffixArray sa() const { return m_sa; }
363  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bwt_type bwt() const { return m_rank_dict.text(); }
364  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 symbol_count() const { return m_rank_dict.symbol_count(); }
365  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 symbol_size() const { return m_rank_dict.symbol_size(); }
366 
367  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index() {}
368 
369  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index(
370  const index_type length,
371  const index_type primary,
372  const L2_iterator L2,
373  const TRankDictionary rank_dict,
374  const TSuffixArray sa) :
375  m_length( length ),
376  m_primary( primary ),
377  m_L2( L2 ),
378  m_rank_dict( rank_dict ),
379  m_sa( sa )
380  {}
381 
382  index_type m_length;
383  index_type m_primary;
384  L2_iterator m_L2;
385  TRankDictionary m_rank_dict;
386  TSuffixArray m_sa;
387 };
388 
396 template <
397  typename TRankDictionary,
398  typename TSuffixArray,
399  typename TL2>
400 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
401 typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type rank(
402  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
403  typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type k,
404  uint8 c);
405 
414 template <
415  typename TRankDictionary,
416  typename TSuffixArray,
417  typename TL2>
418 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
419 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type rank(
420  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
421  typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type range,
422  uint8 c);
423 
433 template <
434  typename TRankDictionary,
435  typename TSuffixArray,
436  typename TL2>
437 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
438 typename TRankDictionary::vec4_type rank4(
439  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
440  typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type k);
441 
453 template <
454  typename TRankDictionary,
455  typename TSuffixArray,
456  typename TL2>
457 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void rank4(
458  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
459  typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type range,
460  typename TRankDictionary::vec4_type* outl,
461  typename TRankDictionary::vec4_type* outh);
462 
469 template <
470  typename TRankDictionary,
471  typename TSuffixArray,
472  typename TL2>
473 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
474 void rank_all(
475  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
476  typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type k,
477  typename fm_index<TRankDictionary,TSuffixArray,TL2>::vector_type* out);
478 
487 template <
488  typename TRankDictionary,
489  typename TSuffixArray,
490  typename TL2>
491 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void rank_all(
492  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
493  typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type range,
494  typename fm_index<TRankDictionary,TSuffixArray,TL2>::vector_type* outl,
495  typename fm_index<TRankDictionary,TSuffixArray,TL2>::vector_type* outh);
496 
504 template <
505  typename TRankDictionary,
506  typename TSuffixArray,
507  typename TL2,
508  typename Iterator>
509 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
510 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type match(
511  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
512  const Iterator pattern,
513  const uint32 pattern_len);
514 
523 template <
524  typename TRankDictionary,
525  typename TSuffixArray,
526  typename TL2,
527  typename Iterator>
528 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
529 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type match(
530  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
531  const Iterator pattern,
532  const uint32 pattern_len,
533  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type range);
534 
542 template <
543  typename TRankDictionary,
544  typename TSuffixArray,
545  typename TL2,
546  typename Iterator>
547 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
548 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type match_reverse(
549  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
550  const Iterator pattern,
551  const uint32 pattern_len);
552 
553 // \relates fm_index
554 // computes the inverse psi function at a given index, without using the reduced SA
555 //
556 // \param fmi FM-index
557 // \param i query index
558 // \return base inverse psi function value and offset
559 //
560 template <
561  typename TRankDictionary,
562  typename TSuffixArray,
563  typename TL2>
564 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
565 typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type basic_inv_psi(
566  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
567  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type i);
568 
576 template <
577  typename TRankDictionary,
578  typename TSuffixArray,
579  typename TL2>
580 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
581 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type inv_psi(
582  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
583  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type i);
584 
592 template <
593  typename TRankDictionary,
594  typename TSuffixArray,
595  typename TL2>
596 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
597 typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type locate(
598  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
599  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type i);
600 
610 template <
611  typename TRankDictionary,
612  typename TSuffixArray,
613  typename TL2>
614 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
615 typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type locate_ssa_iterator(
616  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
617  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type i);
618 
626 template <
627  typename TRankDictionary,
628  typename TSuffixArray,
629  typename TL2>
630 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
631 typename fm_index<TRankDictionary,TSuffixArray,TL2>::index_type lookup_ssa_iterator(
632  const fm_index<TRankDictionary,TSuffixArray,TL2>& fmi,
633  const typename fm_index<TRankDictionary,TSuffixArray,TL2>::range_type it);
634 
635 #ifdef __CUDACC__
636 #if defined(MOD_NAMESPACE)
637 MOD_NAMESPACE_BEGIN
638 #endif
639 
640 #if USE_TEX
641 texture<uint32> s_count_table_tex;
642 #endif
643 struct count_table_texture
647 {
650  NVBIO_FORCEINLINE NVBIO_DEVICE uint32 operator[] (const uint32 i) const;
651 
654  NVBIO_FORCEINLINE NVBIO_HOST static void bind(const uint32* count_table);
655 
658  NVBIO_FORCEINLINE NVBIO_HOST static void unbind();
659 };
660 
661 #if defined(MOD_NAMESPACE)
662 MOD_NAMESPACE_END
663 #endif
664 #endif
665 
667 
668 } // namespace nvbio
669 
670 #include <nvbio/fmindex/fmindex_inl.h>
Generated on Wed Feb 25 2015 08:32:58 for NVBIO by   doxygen 1.8.4