1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 3 of the License, or (at your option) any later version.
12 This library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 ============================================================================
18 $Id: index_qgram_find.h,v 1.1 2008/08/25 16:20:05 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_INDEX_QGRAM_FIND_H
22 #define SEQAN_HEADER_INDEX_QGRAM_FIND_H
24 namespace SEQAN_NAMESPACE_MAIN
27 //////////////////////////////////////////////////////////////////////////////
30 struct _Finder_QGramLookup; //Finder that simply looks up the q-gram in the hash table
33 .Tag.Index Find Algorithm
34 ..tag.QGram_FIND_Lookup:q-gram search.
35 Finds q-grams in a @Spec.Index_QGram@ index using the hash table.
38 typedef Tag<_Finder_QGramLookup> const QGram_FIND_Lookup;
40 //____________________________________________________________________________
43 template < typename TText, typename TShapeSpec, typename TSpec >
44 struct DefaultFinder<Index<TText, Index_QGram<TShapeSpec, TSpec> > > {
45 typedef QGram_FIND_Lookup Type;
49 //////////////////////////////////////////////////////////////////////////////
50 // _findFirstIndex implementation
52 template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
53 inline void _findFirstIndex(
54 Finder< Index<TText, TSpec>, TSpecFinder > &finder,
55 TPattern const &pattern,
56 QGram_FIND_Lookup const)
58 typedef Index<TText, TSpec> TIndex;
59 typedef typename Fibre<TIndex, QGram_SA>::Type TSA;
60 typedef typename Fibre<TIndex, QGram_Shape>::Type TShape;
61 typedef typename Fibre<TIndex, QGram_Dir>::Type TDir;
62 typedef typename Iterator<TSA const, Standard>::Type TSAIterator;
63 typedef typename Iterator<TPattern const, Standard>::Type TPatternIterator;
65 TIndex &index = haystack(finder);
66 indexRequire(index, QGram_SADir());
68 TSAIterator saIt = begin(indexSA(index), Standard());
69 TPatternIterator pIt = begin(pattern, Standard());
70 TDir const &dir = indexDir(index);
71 TShape &shape = indexShape(index);
73 finder.range.i1 = saIt + dir[hash(shape, pIt, length(pattern))];
74 finder.range.i2 = saIt + dir[hashUpper(shape, pIt, length(pattern))];
78 //////////////////////////////////////////////////////////////////////////////
80 } //namespace SEQAN_NAMESPACE_MAIN
82 #endif //#ifndef SEQAN_HEADER_