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_find.h,v 1.1 2008/08/25 16:20:05 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_INDEX_FIND_H
22 #define SEQAN_HEADER_INDEX_FIND_H
24 namespace SEQAN_NAMESPACE_MAIN
27 //////////////////////////////////////////////////////////////////////////////
29 template < typename TText, typename TSpec, typename TSpecFinder >
30 struct Position< Finder< Index<TText, TSpec>, TSpecFinder > >:
31 SAValue< Index<TText, TSpec> > {};
34 //////////////////////////////////////////////////////////////////////////////
35 // generic Finder class for all indices containing a suffix array or
36 // similar table, where a query result is an interval in this table
38 // your index must specialize the function _findFirstIndex and set
39 // finder.range to the interval containing the query hits. See:
41 // template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
42 // inline void _findFirstIndex(
43 // Finder< Index<TText, TSpec>, TSpecFinder > &finder,
44 // TPattern const &pattern,
45 // ESA_FIND_MLR const)
47 // Index<TText, TSpec> &index = haystack(finder);
48 // indexRequire(index, ESA_SA());
49 // finder.range = equalRangeSAIterator(indexText(index), indexSA(index), pattern);
52 template < typename TText, typename TSpec, typename TSpecFinder >
53 class Finder< Index<TText, TSpec>, TSpecFinder >
56 typedef Index<TText, TSpec> TIndex;
57 typedef typename Fibre<TIndex, Fibre_SA>::Type TSA;
58 typedef typename Iterator<TSA const, Standard>::Type TIterator;
62 Pair<TIterator> range;
63 TIterator data_iterator;
69 Finder(TIndex &_index): index(_index)
73 Finder(TIndex const &_index): index(_index)
79 //____________________________________________________________________________
81 template < typename TText, typename TSpec, typename TSpecFinder >
82 inline typename _Parameter< Index<TText, TSpec> >::Type
83 host(Finder< Index<TText, TSpec>, TSpecFinder > & me)
86 return value(me.index);
89 template < typename TText, typename TSpec, typename TSpecFinder >
90 inline typename _Parameter< Index<TText, TSpec> >::Type
91 host(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
94 return value(me.index);
97 template < typename TText, typename TSpec, typename TSpecFinder >
98 inline typename _Parameter< Index<TText, TSpec> >::Type
99 container(Finder< Index<TText, TSpec>, TSpecFinder > & me)
102 return value(me.index);
105 template < typename TText, typename TSpec, typename TSpecFinder >
106 inline typename _Parameter< Index<TText, TSpec> >::Type
107 container(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
110 return value(me.index);
113 //____________________________________________________________________________
115 template < typename TText, typename TSpec, typename TSpecFinder >
118 Finder< Index<TText, TSpec>, TSpecFinder > & me,
119 typename _Parameter<Index<TText, TSpec> >::Type container_)
122 me.index = container;
125 template < typename TText, typename TSpec, typename TSpecFinder >
128 Finder< Index<TText, TSpec>, TSpecFinder > & me,
129 typename _Parameter<Index<TText, TSpec> >::Type container_)
132 me.index = container;
135 //____________________________________________________________________________
137 template < typename TText, typename TSpec, typename TSpecFinder >
138 inline typename Iterator< typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type, Standard>::Type &
139 hostIterator(Finder< Index<TText, TSpec>, TSpecFinder > & me)
142 return me.data_iterator;
145 template < typename TText, typename TSpec, typename TSpecFinder >
146 inline typename Iterator< typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type, Standard>::Type const &
147 hostIterator(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
150 return me.data_iterator;
154 //____________________________________________________________________________
156 template < typename TText, typename TSpec, typename TSpecFinder >
158 empty(Finder< Index<TText, TSpec>, TSpecFinder > & me)
161 return me.range.i1 == me.range.i2;
164 template < typename TText, typename TSpec, typename TSpecFinder >
166 clear(Finder< Index<TText, TSpec>, TSpecFinder > & me)
169 typedef Index<TText, TSpec> TIndex;
170 typedef typename Fibre<TIndex, Fibre_SA>::Type TSA;
171 typedef typename Iterator<TSA, Standard>::Type TIterator;
172 me.range.i1 = me.range.i2 = TIterator();
175 //____________________________________________________________________________
177 template < typename TText, typename TSpec, typename TSpecFinder >
179 atBegin(Finder< Index<TText, TSpec>, TSpecFinder > & me)
182 return (empty(me) || hostIterator(me) == me.range.i1);
185 template < typename TText, typename TSpec, typename TSpecFinder >
187 atEnd(Finder< Index<TText, TSpec>, TSpecFinder > & me)
190 return (empty(me) || hostIterator(me) == me.range.i2);
193 //____________________________________________________________________________
195 template < typename TText, typename TSpec, typename TSpecFinder >
197 goBegin(Finder< Index<TText, TSpec>, TSpecFinder > & me)
200 hostIterator(me) = me.range.i1;
203 template < typename TText, typename TSpec, typename TSpecFinder >
205 goEnd(Finder< Index<TText, TSpec>, TSpecFinder > & me)
208 hostIterator(me) = me.range.i2;
211 //____________________________________________________________________________
213 template < typename TText, typename TSpec, typename TSpecFinder, typename TPosition >
215 setPosition(Finder< Index<TText, TSpec>, TSpecFinder > & me, TPosition pos_)
218 hostIterator(me) = me.range.i1 + pos_;
221 //____________________________________________________________________________
223 template < typename TText, typename TSpec, typename TSpecFinder >
224 inline typename Position< Finder< Index<TText, TSpec>, TSpecFinder > >::Type
225 position(Finder< Index<TText, TSpec>, TSpecFinder > & me)
228 SEQAN_ASSERT(!empty(me))
229 return *me.data_iterator;
232 template < typename TText, typename TSpec, typename TSpecFinder >
233 inline typename Position< Finder< Index<TText, TSpec>, TSpecFinder > >::Type
234 position(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
237 SEQAN_ASSERT(!empty(me))
238 return hostIterator(me) - begin(container(me), Rooted());
242 //////////////////////////////////////////////////////////////////////////////
245 template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
247 Finder<Index<TText, TSpec>, TSpecFinder> &finder,
248 TPattern const &pattern)
251 _findFirstIndex(finder, needle(pattern), TSpecFinder());
252 hostIterator(finder) = finder.range.i1;
254 ++hostIterator(finder);
255 return !atEnd(finder);
258 template < typename TText, typename TSpec, typename TSpecFinder >
259 inline bool find(Finder<Index<TText, TSpec>, TSpecFinder> &finder)
261 if (empty(finder)) return false;
262 ++hostIterator(finder);
263 return !atEnd(finder);