NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
filter.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/fmindex/fmindex.h>
31 #include <nvbio/basic/types.h>
32 #include <nvbio/basic/numbers.h>
33 #include <nvbio/basic/algorithms.h>
34 #include <nvbio/basic/exceptions.h>
35 #include <nvbio/basic/vector.h>
36 #include <nvbio/basic/cuda/sort.h>
38 #include <nvbio/strings/string.h>
39 #include <thrust/sort.h>
40 #include <thrust/scan.h>
41 #include <thrust/iterator/constant_iterator.h>
42 #include <thrust/iterator/counting_iterator.h>
43 
44 namespace nvbio {
45 
48 
60 template <typename system_tag, typename fm_index_type>
61 struct FMIndexFilter {};
62 
74 template <typename fm_index_type>
75 struct FMIndexFilter<host_tag, fm_index_type>
76 {
77  typedef host_tag system_tag;
78  typedef fm_index_type index_type;
79 
80  typedef typename index_type::index_type coord_type;
81  static const uint32 coord_dim = vector_traits<coord_type>::DIM;
82 
84 
85  static const uint32 hit_dim = coord_dim*2;
87 
95  template <typename string_set_type>
96  uint64 rank(
97  const fm_index_type& index,
98  const string_set_type& string_set);
99 
107  template <typename hits_iterator>
108  void locate(
109  const uint64 begin,
110  const uint64 end,
111  hits_iterator hits);
112 
115  uint64 n_hits() const { return m_n_occurrences; }
116 
119  const range_type* ranges() const { return nvbio::plain_view( m_ranges ); }
120 
124  const uint64* ranks() const { return nvbio::plain_view( m_slots ); }
125 
129  thrust::host_vector<range_type> m_ranges;
130  thrust::host_vector<uint64> m_slots;
131 };
132 
144 template <typename fm_index_type>
145 struct FMIndexFilter<device_tag, fm_index_type>
146 {
148  typedef fm_index_type index_type;
149 
150  typedef typename index_type::index_type coord_type;
151  static const uint32 coord_dim = vector_traits<coord_type>::DIM;
152 
154 
155  static const uint32 hit_dim = coord_dim*2;
157 
165  template <typename string_set_type>
166  uint64 rank(
167  const fm_index_type& index,
168  const string_set_type& string_set);
169 
177  template <typename hits_iterator>
178  void locate(
179  const uint64 begin,
180  const uint64 end,
181  hits_iterator hits);
182 
185  uint64 n_hits() const { return m_n_occurrences; }
186 
189  const range_type* ranges() const { return nvbio::plain_view( m_ranges ); }
190 
194  const uint64* ranks() const { return nvbio::plain_view( m_slots ); }
195 
199  thrust::device_vector<range_type> m_ranges;
200  thrust::device_vector<uint64> m_slots;
201  thrust::device_vector<hit_type> m_hits;
202  thrust::device_vector<uint8> d_temp_storage;
203 };
204 
216 template <typename fm_index_type>
217 struct FMIndexFilterHost : public FMIndexFilter<host_tag, fm_index_type>
218 {
222 
225  typedef typename core_type::hit_type hit_type;
226 };
227 
239 template <typename fm_index_type>
240 struct FMIndexFilterDevice : public FMIndexFilter<device_tag, fm_index_type>
241 {
245 
248  typedef typename core_type::hit_type hit_type;
249 };
250 
252 
253 } // namespace nvbio
254