1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Stephan Aiche <aiche@fu-berlin.de>
33 // ==========================================================================
34
35 #ifndef SEQAN_HEADER_FIND_ABNDMALGO_H
36 #define SEQAN_HEADER_FIND_ABNDMALGO_H
37
38 // uncomment this for verbose output of the ABNDM ALGO
39 //#define SEQAN_DEBUG_ABNDM
40
41 namespace SEQAN_NAMESPACE_MAIN
42 {
43
44
45 #ifdef SEQAN_DEBUG_ABNDM
_printMask(String<unsigned> const & mask,String<char> name)46 inline void _printMask(String <unsigned> const & mask,String <char> name)
47 {
48 unsigned len = length(mask);
49 std::cout << name << ": ";
50 for(unsigned int j=0;j<len;++j) {
51 for(unsigned int bit_pos=0;bit_pos<BitsPerValue<unsigned int>::VALUE;++bit_pos) {
52 std::cout << ((mask[j] & (1<<(bit_pos % BitsPerValue<unsigned int>::VALUE))) !=0);
53 }
54 std::cout << " ";
55 }
56 std::cout << std::endl;
57 }
58
_printMask(String<unsigned> const & mask,unsigned start,unsigned len,String<char> name)59 inline void _printMask(String <unsigned> const & mask,unsigned start, unsigned len,String <char> name)
60 {
61 std::cout << name << ": ";
62 for(unsigned int j=start;j<start + len;++j) {
63 for(unsigned int bit_pos=0;bit_pos<BitsPerValue<unsigned int>::VALUE;++bit_pos) {
64 std::cout << ((mask[j] & (1<<(bit_pos % BitsPerValue<unsigned int>::VALUE))) !=0);
65 }
66 std::cout << " ";
67 }
68 std::cout << std::endl;
69 }
70
71 #endif
72
73 //////////////////////////////////////////////////////////////////////////////
74 // AbndmAlgo
75 //////////////////////////////////////////////////////////////////////////////
76
77 /*!
78 * @class AbndmAlgoPattern
79 * @extends Pattern
80 * @headerfile <seqan/find.h>
81 * @brief Approximate Backward Nondeterministic Dawg Matching algorithm.
82 *
83 * Approximate string matching using bit parallelism.
84 *
85 * @signature template <typename TNeedle>
86 * class Pattern<TNeedle, AbndmAlgo>;
87 *
88 * @tparam TNeedle The needle type. Type @link ContainerConcept @endlink.
89 *
90 * @note The types of the needle and the haystack have to match.
91 */
92
93
94 struct AbndmAlgo;
95
96 //////////////////////////////////////////////////////////////////////////////
97
98 template <typename TNeedle>
99 struct FindBeginPatternSpec< Pattern<TNeedle, AbndmAlgo> >:
100 DefaultFindBeginPatternSpec<>
101 {
102 };
103
104 //////////////////////////////////////////////////////////////////////////////
105
106 template <typename TNeedle>
107 class Pattern<TNeedle, AbndmAlgo>:
108 public FindBegin_<Pattern<TNeedle, AbndmAlgo> >
109 {
110 //////////////////////////////////////////////////////////////////////////////
111 public:
112 typedef unsigned int TWord;
113 Holder<TNeedle> data_host;
114
115 String<TWord> b_table; // called B in Navarro
116 String<TWord> r_table; // called R in Navarro
117
118 TWord blockCount;
119 TWord last;
120 TWord needleLength; // e.g., needleLength=33 --> blockCount=2 (iff w=32 bits)
121 TWord haystackLength;
122 TWord limit; // the maximal accepted error
123 TWord cP; // save current position of the nfa
124
125 bool findNext;
126
127 Pattern<TNeedle,MyersUkkonen> verifier;
128 //////////////////////////////////////////////////////////////////////////////
129
130 Pattern() :
131 blockCount(0), last(0), needleLength(0), haystackLength(0), limit(1), cP(0), findNext(false)
132 {}
133
134 template <typename TNeedle2>
135 Pattern(TNeedle2 const & ndl) :
136 blockCount(0), last(0), needleLength(0), haystackLength(0), limit(1), cP(0), findNext(false),
137 verifier(ndl,-1)
138 {
139 setHost(*this, ndl);
140 }
141
142 template <typename TNeedle2>
143 Pattern(TNeedle2 const & ndl, int _limit = -1) :
144 limit(- _limit), cP(0), verifier(ndl,_limit)
145 {
146 setHost(*this, ndl);
147 }
148 };
149
150 //////////////////////////////////////////////////////////////////////////////
151
152 template <typename TNeedle>
153 void _printR(Pattern<TNeedle, AbndmAlgo> & me)
154 {
155 std::cout << "R ----------------------------- " << std::endl;
156 for(unsigned i = 0;i <= me.limit;++i)
157 {
158 _printMask(me.r_table,me.blockCount * i, me.blockCount ," ");
159 }
160 std::cout << " ------------------------------ " << std::endl;
161 }
162
163 //////////////////////////////////////////////////////////////////////////////
164
165 template <typename TNeedle, typename TNeedle2>
166 void setHost (Pattern<TNeedle, AbndmAlgo> & me, TNeedle2 const& needle)
167 {
168 SEQAN_CHECKPOINT
169 typedef unsigned int TWord;
170 typedef typename Value<TNeedle>::Type TValue;
171
172 me.cP = 0;
173 me.findNext = false;
174
175 me.needleLength = length(needle);
176 if (me.needleLength<1)
177 me.blockCount = 1;
178 else
179 me.blockCount = ((me.needleLength-1) / BitsPerValue<TWord>::VALUE)+1;
180
181 clear(me.b_table);
182 resize(me.b_table, me.blockCount * ValueSize<TValue>::VALUE, 0, Exact());
183
184 for (TWord j = 0; j < me.needleLength; ++j) {
185 // Determine character position in array table
186 TWord pos = convert<TWord>(getValue(needle,j));
187 me.b_table[me.blockCount*pos + j / BitsPerValue<TWord>::VALUE] |= (1<<(j%BitsPerValue<TWord>::VALUE));
188 }
189
190 #ifdef SEQAN_DEBUG_ABNDM
191 std::cout << "Needle: " << needle << std::endl;
192 std::cout << "|Needle|: " << length(needle) << std::endl;
193 std::cout << "Alphabet size: " << ValueSize<TValue>::VALUE << std::endl;
194
195 for(unsigned i=0;i<ValueSize<TValue>::VALUE;++i) {
196 if (((i<97) && (4 < i) ) || (i>122)) continue;
197 std::cout << static_cast<TValue>(i) << ": ";
198 for(unsigned int j=0;j<me.blockCount;++j) {
199 for(int bit_pos=0;bit_pos<BitsPerValue<unsigned>::VALUE;++bit_pos) {
200 std::cout << ((me.b_table[me.blockCount*i+j] & (1<<(bit_pos % BitsPerValue<unsigned>::VALUE))) !=0);
201 }
202 std::cout << " ";
203 }
204 std::cout << std::endl;
205 }
206 #endif
207 clear(me.r_table); // init is only possible if we know the the error count
208
209 me.data_host = needle;
210 setHost(me.verifier,needle);
211 }
212
213 template <typename TNeedle, typename TNeedle2>
214 void setHost (Pattern<TNeedle, AbndmAlgo> & me, TNeedle2 & needle)
215 {
216 setHost(me, reinterpret_cast<TNeedle2 const &>(needle));
217 }
218
219 //////////////////////////////////////////////////////////////////////////////
220
221 template <typename TNeedle>
222 inline void _patternInit (Pattern<TNeedle, AbndmAlgo> & me)
223 {
224 SEQAN_CHECKPOINT
225 clear(me.r_table);
226 resize(me.r_table, me.blockCount * (me.limit + 1), 0, Exact());
227 me.findNext = false;
228 me.last = 0;
229 _findBeginInit(me, needle(me));
230 }
231
232 //////////////////////////////////////////////////////////////////////////////
233
234 template <typename TNeedle>
235 inline typename Host<Pattern<TNeedle, AbndmAlgo> >::Type &
236 host(Pattern<TNeedle, AbndmAlgo> & me)
237 {
238 SEQAN_CHECKPOINT
239 return value(me.data_host);
240 }
241
242 template <typename TNeedle>
243 inline typename Host<Pattern<TNeedle, AbndmAlgo> const>::Type &
244 host(Pattern<TNeedle, AbndmAlgo> const & me)
245 {
246 SEQAN_CHECKPOINT
247 return value(me.data_host);
248 }
249
250 //////////////////////////////////////////////////////////////////////////////
251 /*!
252 * @fn AbndmAlgoPattern#getScore
253 * @headerfile <seqan/find.h>
254 * @brief Score of the last found match in approximate searching.
255 *
256 * @signature TScoreValue getScore(pattern);
257 *
258 * @param[in] pattern A abndmAlgo pattern that can be used for approximate searching.
259 *
260 * @return TScoreValue The score of the last match found using <tt>pattern</tt>. If no match was found then the value
261 * is undefined.
262 */
263
264
265 template <typename TNeedle>
266 int getScore(Pattern<TNeedle, AbndmAlgo > & me)
267 {
268 SEQAN_CHECKPOINT
269 return getScore(me.verifier);
270 }
271
272 //////////////////////////////////////////////////////////////////////////////
273
274 template <typename TFinder, typename TNeedle>
275 inline bool _findAbndmSmallNeedle(TFinder & finder, Pattern<TNeedle, AbndmAlgo> & me)
276 {
277 SEQAN_CHECKPOINT
278 typedef unsigned int TWord;
279
280 typedef typename Host<TFinder>::Type THost;
281 typedef Segment<THost> THostSegment;
282 typedef Finder<THostSegment> THSFinder;
283
284 TWord j,nR,oR,i,cB;
285 TWord startPos = position(finder);
286
287 // if returned from previous search we need to check the current position for additional matches
288 if(me.findNext)
289 {
290 // reset the finder
291 TWord offset = startPos - me.cP;
292 finder -= offset;
293 int end = me.cP + me.needleLength + me.limit;
294 // adjust end if it points over the edges of host(finder)
295 end = (end > static_cast<int>(length(host(finder))) ? static_cast<int>(length(host(finder))) : end);
296
297 THostSegment s(infix(host(finder),me.cP, end));
298 THSFinder f(s);
299 #ifdef SEQAN_DEBUG_ABNDM
300 std::cout << "additional verification of current position" << std::endl;
301 std::cout << "initialized on: " << s << std::endl;
302 std::cout << "parameters are: " << me.cP << " " << (me.cP + me.needleLength + me.limit) << std::endl;
303 std::cout << "original start pos: " << startPos << std::endl;
304 #endif
305
306 while(find(f,me.verifier,- (int) me.limit)){
307 TWord newP = position(finder) + position(f);
308 #ifdef SEQAN_DEBUG_ABNDM
309 std::cout << "found on new position: " << newP << std::endl;
310 #endif
311 if(newP > startPos){
312 finder += position(f);
313 return true;
314 }
315 }
316 #ifdef SEQAN_DEBUG_ABNDM
317 std::cout << "additional verification done .. shifted by last=" << me.last << std::endl << std::endl;
318 #endif
319 finder += me.last;
320 me.cP += me.last;
321 }
322
323 me.cP = position(finder);
324 // walk on
325 while (position(finder) <= me.haystackLength - me.needleLength)
326 {
327 SEQAN_CHECKPOINT
328 j = me.needleLength - me.limit - 1;
329 me.last = j;
330
331 // init R_0
332 TWord pos = convert<TWord>(*(finder + j));
333
334 me.r_table[0] = me.b_table[pos];
335 nR = (TWord)-1;
336 for(i = 1;i <= me.limit;++i) me.r_table[i] = nR;
337
338 #ifdef SEQAN_DEBUG_ABNDM
339 std::cout << "reading " << *(finder + j) << std::endl;
340 _printMask(me.b_table[pos],"");
341 _printR(me);
342 #endif
343 // process R_1 .. R_limit
344 while((nR != 0) && (j != 0))
345 {
346 pos = convert<TWord>(*(finder + j - 1));
347 cB = me.b_table[pos];
348 oR = me.r_table[0];
349 nR = (oR >> 1) & cB;
350 me.r_table[0] = nR;
351 for(i = 1;i <= me.limit;++i)
352 {
353 nR = ((me.r_table[i] >> 1) & cB) | oR | ((oR | nR) >> 1);
354 oR = me.r_table[i];
355 me.r_table[i] = nR;
356 }
357 #ifdef SEQAN_DEBUG_ABNDM
358 std::cout << "reading " << *(finder + j - 1) << std::endl;
359 _printMask(me.b_table[pos],"");
360 _printR(me);
361 #endif
362 --j;
363 if((nR & 1) != 0){
364 if(j > 0){
365 #ifdef SEQAN_DEBUG_ABNDM
366 std::cout << "last bit is set so last is set to " << j << std::endl;
367 #endif
368 me.last = j;
369 }
370 else // verify
371 {
372 // call find
373 int end = me.cP + me.needleLength + me.limit;
374 // adjust end if it points over the edges of host(finder)
375 end = (end > static_cast<int>(length(host(finder))) ? static_cast<int>(length(host(finder))) : end);
376
377 THostSegment s(infix(host(finder),me.cP, end));
378 THSFinder f(s);
379
380 #ifdef SEQAN_DEBUG_ABNDM
381 std::cout << "found verifiable prefix" << std::endl;
382 // init finder on infix
383 std::cout << "parameters are " << me.cP << " " << (me.cP + me.needleLength + me.limit) << std::endl;
384 std::cout << "init finder on: " << s << std::endl;
385 #endif
386 // try to find the sequence
387 while(find(f,me.verifier,- (int) me.limit)){
388 TWord nP = position(finder) + position(f);
389 if(nP > startPos){
390 finder += position(f);
391 me.findNext = true;
392 return true;
393 }
394 }
395 }
396 }
397 }
398 #ifdef SEQAN_DEBUG_ABNDM
399 std::cout << "automaton runs out of active stats so window is shifted by last=" << me.last << std::endl << std::endl;
400 #endif
401
402 finder += me.last;
403 me.cP += me.last;
404 }
405 return false;
406 }
407
408 template <typename TFinder, typename TNeedle>
409 inline bool _findAbndmLargeNeedle(TFinder & finder, Pattern<TNeedle, AbndmAlgo> & me)
410 {
411 SEQAN_CHECKPOINT
412 typedef unsigned int TWord;
413 TWord carryPattern = ((TWord)1 << (BitsPerValue<TWord>::VALUE - 1));
414 typedef typename Host<TFinder>::Type THost;
415 typedef Segment<THost> THostSegment;
416 typedef Finder<THostSegment> THSFinder;
417
418 TWord j,i;
419 String<TWord> nR,oR;
420 TWord startPos = position(finder);
421
422 // if returned from previous search we need to check the current position for additional matches
423 if(me.findNext)
424 {
425 // reset the finder
426 TWord offset = startPos - me.cP;
427 finder -= offset;
428
429 int end = me.cP + me.needleLength + me.limit;
430 // adjust end if it points over the edges of host(finder)
431 end = (end > static_cast<int>(length(host(finder))) ? static_cast<int>(length(host(finder))) : end);
432
433 THostSegment s(infix(host(finder),me.cP, end));
434 THSFinder f(s);
435 #ifdef SEQAN_DEBUG_ABNDM
436 std::cout << "additional verification of current position" << std::endl;
437 std::cout << "initialized on: " << s << std::endl;
438 std::cout << "parameters are: " << me.cP << " " << (me.cP + me.needleLength + me.limit) << std::endl;
439 std::cout << "original start pos: " << startPos << std::endl;
440 #endif
441
442 while(find(f,me.verifier,- (int) me.limit)){
443 TWord newP = position(finder) + position(f);
444 #ifdef SEQAN_DEBUG_ABNDM
445 std::cout << "found on new position: " << newP << std::endl;
446 #endif
447 if(newP > startPos){
448 finder += position(f);
449 return true;
450 }
451 }
452 #ifdef SEQAN_DEBUG_ABNDM
453 std::cout << "additional verification done .. shifted by last=" << me.last << std::endl << std::endl;
454 #endif
455 finder += me.last;
456 me.cP += me.last;
457 }else me.cP = position(finder);
458 // walk on
459 while (position(finder) <= me.haystackLength - me.needleLength)
460 {
461 SEQAN_CHECKPOINT
462 j = me.needleLength - me.limit - 1;
463 me.last = j;
464
465 #ifdef SEQAN_DEBUG_ABNDM
466 std::cout << "starting new frame ending at position " << me.cP + j << std::endl;
467 #endif
468 // init R_0
469 TWord pos = convert<TWord>(*(finder + j));
470 for(int block = me.blockCount - 1;block >= 0;--block){
471 me.r_table[block] = me.b_table[pos * me.blockCount + block];
472 }
473 //me.r_table[0] = me.b_table[pos];
474
475 resize(nR,me.blockCount,0 - 1);
476 resize(oR,me.blockCount,0);
477 // nR = 0 - 1;
478 //for(i = me.blockCount;i <= me.limit * me.blockCount;++i) me.r_table[i] = 0 - 1;//set all states in r_table to 1
479 for(i = 1;i <= me.limit;++i){
480 for(int block = me.blockCount - 1;block >= 0;--block){
481 me.r_table[me.blockCount * i + block] = 0 -1 ;
482 }
483 }
484
485 // track active states in nR
486 TWord nRTrack = 1;
487
488 #ifdef SEQAN_DEBUG_ABNDM
489 std::cout << "reading " << *(finder + j) << std::endl;
490 _printMask(me.b_table,pos * me.blockCount, me.blockCount," ");
491 _printR(me);
492 #endif
493 while((nRTrack != 0) && (j != 0))
494 {
495 // get current letter
496 pos = convert<TWord>(*(finder + j - 1));
497
498 bool carry = 0;
499 for(int block = me.blockCount -1;block >= 0;--block){
500 oR[block] = me.r_table[block];
501 bool nCarry=((oR[block] & 1) != 0);
502 TWord toR = oR[block] >> 1;
503 if(carry) toR |= carryPattern;
504 carry = nCarry;
505 nR[block] = toR & me.b_table[pos*me.blockCount + block];
506 me.r_table[block] = nR[block];
507 }
508
509
510 for(i = 1;i <= me.limit;++i){
511 bool rCarry = 0;
512 bool nCarry = 0;
513 for(int block = me.blockCount - 1;block >= 0;--block){
514 bool nRCarry = ((me.r_table[i * me.blockCount + block] & 1) != 0);
515 bool nNCarry = (((oR[block] | nR[block]) & 1) != 0);
516
517 TWord rPattern = (rCarry ? carryPattern : 0);
518 TWord nPattern = (nCarry ? carryPattern : 0);
519 nR[block] = (((me.r_table[i * me.blockCount + block] >> 1) | rPattern) & me.b_table[pos*me.blockCount + block]) | (((oR[block] | nR[block]) >> 1) | nPattern) | oR[block];
520 rCarry = nRCarry;
521 nCarry = nNCarry;
522 oR[block] = me.r_table[i * me.blockCount + block];
523 me.r_table[i * me.blockCount + block] = nR[block];
524 }
525 }
526 #ifdef SEQAN_DEBUG_ABNDM
527 std::cout << "reading " << *(finder + j - 1) << std::endl;
528 _printMask(me.b_table,pos*me.blockCount, me.blockCount," ");
529 _printR(me);
530 #endif
531 --j;
532 // track active states in nR
533 nRTrack = 0;
534 for(i = 0;i < me.blockCount;++i) nRTrack |= nR[i];
535
536 if((nR[0] & 1) != 0){
537 if(j > 0){
538 #ifdef SEQAN_DEBUG_ABNDM
539 std::cout << "last bit is set so last is set to " << j << std::endl;
540 #endif
541 me.last = j;
542 }
543 else // verify
544 {
545 // call find
546 int end = me.cP + me.needleLength + me.limit;
547 // adjust end if it points over the edges of host(finder)
548 end = (end > static_cast<int>(length(host(finder))) ? static_cast<int>(length(host(finder))) : end);
549
550 THostSegment s(infix(host(finder),me.cP, end));
551 THSFinder f(s);
552
553 #ifdef SEQAN_DEBUG_ABNDM
554 std::cout << "found verifiable prefix" << std::endl;
555 // init finder on infix
556 std::cout << "parameters are " << me.cP << " " << (me.cP + me.needleLength + me.limit) << std::endl;
557 std::cout << "init finder on: " << s << std::endl;
558 #endif
559 // try to find the sequence
560 while(find(f,me.verifier,- (int) me.limit)){
561 TWord nP = position(finder) + position(f);
562 if(nP > startPos){
563 finder += position(f);
564 #ifdef SEQAN_DEBUG_ABNDM
565 std::cout << "found pattern at position " << position(finder) << std::endl;
566 #endif
567 me.findNext = true;
568 return true;
569 }
570 }
571 }
572 }
573 }
574 #ifdef SEQAN_DEBUG_ABNDM
575 std::cout << "automaton runs out of active stats so window is shifted by last=" << me.last << std::endl << std::endl;
576 #endif
577
578 finder += me.last;
579 me.cP += me.last;
580 }
581 return false;
582 }
583
584 //////////////////////////////////////////////////////////////////////////////
585 /*!
586 * @fn AbndmAlgoPattern#scoreLimit
587 * @headerfile <seqan/find.h>
588 * @brief The minimal score a match must reach in approximate searching.
589 *
590 * @signature TScoreValue scoreLimit(pattern);
591 *
592 * @param[in] pattern The AbndmAlgoPattern to query.
593 *
594 * @return TScoreValue The score limit value.
595 */
596 template <typename TNeedle>
597 inline int
598 scoreLimit(Pattern<TNeedle, AbndmAlgo > const & me)
599 {
600 SEQAN_CHECKPOINT
601 return - (int) me.limit;
602 }
603
604
605 //////////////////////////////////////////////////////////////////////////////
606 /*!
607 * @fn AbndmAlgoPattern#setSoreLimit
608 * @headerfile <seqan/find.h>
609 * @brief Set the minimal score a match must reach in approximate serach.
610 *
611 * @signature void setScoreLimit(pattern, limit);
612 *
613 * @param[in,out] pattern The AbndmAlgoPattern to set the limit for.
614 * @param[in] limit The limit score value to set.
615 *
616 * @return TScoreValue The score limit value.
617 */
618
619 template <typename TNeedle, typename TScoreValue>
620 inline void
621 setScoreLimit(Pattern<TNeedle, AbndmAlgo > & me,
622 TScoreValue _limit)
623 {
624 SEQAN_CHECKPOINT
625 setScoreLimit(me.verifier,_limit);
626 me.limit = (- _limit);
627 }
628
629 //////////////////////////////////////////////////////////////////////////////
630
631 template <typename TFinder, typename TNeedle>
632 inline bool find (TFinder & finder,
633 Pattern<TNeedle, AbndmAlgo > & me)
634 {
635 SEQAN_CHECKPOINT
636 if (empty(finder)) {
637 _patternInit(me);
638 _finderSetNonEmpty(finder);
639 me.haystackLength = length(container(finder));
640 }
641
642 bool ret;
643 if (me.blockCount == 1) {
644 ret = _findAbndmSmallNeedle(finder, me);
645 } else {
646 ret = _findAbndmLargeNeedle(finder, me);
647 }
648 if (ret)
649 {
650 _setFinderEnd(finder);
651 }
652 return ret;
653
654 }
655
656 template <typename TFinder, typename TNeedle>
657 inline bool find (TFinder & finder,
658 Pattern<TNeedle, AbndmAlgo > & me,
659 int const k)
660 {
661 SEQAN_CHECKPOINT
662 setScoreLimit(me, k);
663 return find(finder, me);
664 }
665
666 //////////////////////////////////////////////////////////////////////////////
667 }// namespace SEQAN_NAMESPACE_MAIN
668
669 #endif //#ifndef SEQAN_HEADER_FIND_ABNDMALGO_H
670