NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
rank_dictionary.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/numbers.h>
32 #include <nvbio/basic/popcount.h>
33 #include <nvbio/basic/packedstream.h>
34 #include <nvbio/basic/iterator.h>
35 #include <nvbio/basic/static_vector.h>
36 #include <vector_types.h>
37 #include <vector_functions.h>
38 
39 namespace nvbio {
40 
43 
58 
61 
82 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
83 struct rank_dictionary
84 {
85  static const uint32 BLOCK_INTERVAL = K;
86  static const uint32 SYMBOL_SIZE = SYMBOL_SIZE_T;
87  static const uint32 SYMBOL_COUNT = 1u << SYMBOL_SIZE;
88 
89  typedef TextString text_type;
90  typedef OccIterator occ_iterator;
91  typedef CountTable count_table_type;
92 
93  // the indexing type of this container is determined by the value_type of the occurrence table
94  typedef typename vector_traits<
95  typename std::iterator_traits<occ_iterator>::value_type>::value_type index_type;
96 
97  typedef typename vector_type<index_type,2>::type range_type;
98  typedef typename vector_type<index_type,2>::type vec2_type;
99  typedef typename vector_type<index_type,4>::type vec4_type;
100  typedef StaticVector<index_type,SYMBOL_COUNT> vector_type;
101 
104  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
105  rank_dictionary() {}
106 
109  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
110  rank_dictionary(
111  const TextString _text,
112  const OccIterator _occ,
113  const CountTable _count_table) :
114  m_text( _text ),
115  m_occ( _occ ),
116  m_count_table( _count_table ) {}
117 
118  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 symbol_count() const { return 1u << SYMBOL_SIZE_T; }
119  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 symbol_size() const { return SYMBOL_SIZE_T; }
120 
121  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type text() { return m_text; }
122  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type text() const { return m_text; }
123 
124  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE occ_iterator occ() { return m_occ; }
125  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE occ_iterator occ() const { return m_occ; }
126 
127  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE count_table_type count_table() { return m_count_table; }
128  NVBIO_FORCEINLINE NVBIO_HOST_DEVICE count_table_type count_table() const { return m_count_table; }
129 
130  TextString m_text;
131  OccIterator m_occ;
132  CountTable m_count_table;
133 };
135 
155 template <uint32 SYMBOL_SIZE, uint32 K, typename SymbolIterator, typename IndexType>
156 void build_occurrence_table(
157  SymbolIterator begin,
158  SymbolIterator end,
159  IndexType* occ,
160  IndexType* cnt = NULL);
161 
165 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
166 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint8 text(const rank_dictionary<SYMBOL_SIZE_T,K,TextString,OccIterator,CountTable>& dict, const uint32 i);
167 
171 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
172 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint8 text(const rank_dictionary<SYMBOL_SIZE_T,K,TextString,OccIterator,CountTable>& dict, const uint64 i);
173 
181 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
182 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexType rank(
183  const rank_dictionary<SYMBOL_SIZE_T,K,TextString,OccIterator,CountTable>& dict, const IndexType i, const uint32 c);
184 
192 template <uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
193 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE typename vector_type<IndexType,2>::type rank(
194  const rank_dictionary<SYMBOL_SIZE_T,K,TextString,OccIterator,CountTable>& dict, const typename vector_type<IndexType,2>::type range, const uint32 c);
195 
204 template <uint32 K, typename TextString, typename OccIterator, typename CountTable, typename IndexType>
205 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE typename vector_type<IndexType,4>::type rank4(
206  const rank_dictionary<2,K,TextString,OccIterator,CountTable>& dict, const IndexType i);
207 
218 template <uint32 K, typename TextString, typename OccIterator, typename CountTable>
219 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void rank4(
220  const rank_dictionary<2,K,TextString,OccIterator,CountTable>& dict, const uint2 range, uint4* outl, uint4* outh);
221 
232 template <uint32 K, typename TextString, typename OccIterator, typename CountTable>
233 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void rank4(
234  const rank_dictionary<2,K,TextString,OccIterator,CountTable>& dict, const uint64_2 range, uint64_4* outl, uint64_4* outh);
235 
242 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
243 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
244 typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::vector_type
245 rank_all(
246  const rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>& dict,
247  const typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::index_type i);
248 
256 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
257 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
258 void rank_all(
259  const rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>& dict,
260  const typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::index_type i,
261  typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::vector_type* out);
262 
271 template <uint32 SYMBOL_SIZE, uint32 K, typename TextString, typename OccIterator, typename CountTable>
272 NVBIO_FORCEINLINE NVBIO_HOST_DEVICE
273 void rank_all(
274  const rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>& dict,
275  const typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::range_type range,
276  typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::vector_type* outl,
277  typename rank_dictionary<SYMBOL_SIZE,K,TextString,OccIterator,CountTable>::vector_type* outh);
278 
281 
282 } // namespace nvbio
283 
284 #include <nvbio/fmindex/rank_dictionary_inl.h>
Generated on Wed Feb 25 2015 08:32:59 for NVBIO by   doxygen 1.8.4