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: find_base.h,v 1.1 2008/08/25 16:20:07 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_FIND_BASE_H
22 #define SEQAN_HEADER_FIND_BASE_H
25 //////////////////////////////////////////////////////////////////////////////
27 namespace SEQAN_NAMESPACE_MAIN
30 //////////////////////////////////////////////////////////////////////////////
33 .Metafunction.DefaultFinder:
35 ..summary:Default @Class.Finder@ specialization type.
36 ..signature:DefaultFinder<THaystack>::Type
37 ..param.THaystack:The given haystack type.
38 ..returns:Is $void$ by default and @Tag.Index Find Algorithm.ESA_FIND_MLR@ if $THaystack$ is an @Class.Index@.
40 template < typename TObject >
41 struct DefaultFinder {
46 .Metafunction.DefaultPattern:
48 ..summary:Default @Class.Pattern@ specialization type.
49 ..signature:DefaultPattern<TNeedle>::Type
50 ..param.TNeedle:The given needle type.
51 ..returns:Is $void$ by default.
53 template < typename TObject >
54 struct DefaultPattern {
59 .Metafunction.Haystack:
60 ..summary:Returns the haystack type of a @Class.Finder@ type.
62 ..signature:Haystack<TFinder>::Type
63 ..param.TFinder:A @Class.Finder@ type.
65 ..returns:The haystack type of $TFinder$, i.e. $THaystack$ for $Finder<THaystack, TSpec>$.
68 template <typename TFinder>
70 typedef typename Container<TFinder>::Type Type;
75 ..summary:Returns the needle type of a @Class.Pattern@ type.
77 ..signature:Needle<TPattern>::Type
78 ..param.TPattern:A @Class.Pattern@ type.
80 ..returns:The needle type of $TPattern$, i.e. $TNeedle$ for $Pattern<TNeedle, TSpec>$.
83 template <typename TPattern>
85 typedef typename Host<TPattern>::Type Type;
88 template <typename THost, typename TSpec>
89 struct Needle<Segment<THost, TSpec> > {
90 typedef Segment<THost, TSpec> Type;
93 template <typename THost, typename TSpec>
94 struct Needle<Segment<THost, TSpec> const> {
95 typedef Segment<THost, TSpec> const Type;
98 //////////////////////////////////////////////////////////////////////////////
102 ..summary:Holds the needle and preprocessing data (depends on algorithm).
104 ..signature:Pattern<TNeedle[, TSpec]>
105 ..param.TNeedle:The needle type.
107 ..param.TSpec:The online-algorithm to search with.
108 ...remarks:Leave empty for index-based pattern matching (see @Class.Index@).
109 ...default:The result of @Metafunction.DefaultPattern@
110 ..remarks:If $TNeedle$ is a set of strings, then $position(pattern)$ returns the index of the currently matching needle.
113 template < typename TNeedle, typename TSpec = typename DefaultPattern<TNeedle>::Type >
116 //default implementation
117 template < typename TNeedle >
118 class Pattern<TNeedle, void>
121 typedef typename Position<TNeedle>::Type TNeedlePosition;
123 Holder<TNeedle> data_host;
124 TNeedlePosition data_begin_position;
125 TNeedlePosition data_end_position;
129 template <typename _TNeedle>
130 Pattern(_TNeedle & ndl):
133 template <typename _TNeedle>
134 Pattern(_TNeedle const & ndl):
138 //////////////////////////////////////////////////////////////////////////////
140 template <typename TNeedle, typename TSpec>
141 inline Holder<TNeedle> &
142 _dataHost(Pattern<TNeedle, TSpec> & me)
146 template <typename TNeedle, typename TSpec>
147 inline Holder<TNeedle> &
148 _dataHost(Pattern<TNeedle, TSpec> const & me)
150 return const_cast<Holder<TNeedle> &>(me.data_host);
153 //host access: see basic_host.h
156 //???TODO: Diese Funktion entfernen! (sobald setHost bei anderen pattern nicht mehr eine Art "assignHost" ist)
157 template <typename TNeedle, typename TSpec, typename TNeedle2>
159 setHost(Pattern<TNeedle, TSpec> & me,
160 TNeedle2 const & ndl)
162 me.data_host = ndl; //assign => Pattern haelt eine Kopie => doof!
164 template <typename TNeedle, typename TSpec, typename TNeedle2>
166 setHost(Pattern<TNeedle, TSpec> & me,
169 me.data_host = ndl; //assign => Pattern haelt eine Kopie => doof!
171 //////////////////////////////////////////////////////////////////////////////
173 template <typename TNeedle, typename TSpec>
174 inline typename Position<Pattern<TNeedle, TSpec> >::Type &
175 beginPosition(Pattern<TNeedle, TSpec> & me)
177 return me.data_begin_position;
179 template <typename TNeedle, typename TSpec>
180 inline typename Position<Pattern<TNeedle, TSpec> const >::Type &
181 beginPosition(Pattern<TNeedle, TSpec> const & me)
183 return me.data_begin_position;
187 template <typename TNeedle, typename TSpec, typename TPosition>
189 setBeginPosition(Pattern<TNeedle, TSpec> & me,
192 me.data_begin_position = _pos;
195 //////////////////////////////////////////////////////////////////////////////
197 template <typename TNeedle, typename TSpec>
198 inline typename Position<Pattern<TNeedle, TSpec> >::Type &
199 endPosition(Pattern<TNeedle, TSpec> & me)
201 return me.data_end_position;
203 template <typename TNeedle, typename TSpec>
204 inline typename Position<Pattern<TNeedle, TSpec> const >::Type &
205 endPosition(Pattern<TNeedle, TSpec> const & me)
207 return me.data_end_position;
210 template <typename TNeedle, typename TSpec, typename TPosition>
212 setEndPosition(Pattern<TNeedle, TSpec> & me,
215 me.data_end_position = _pos;
218 //////////////////////////////////////////////////////////////////////////////
220 template <typename TNeedle, typename TSpec>
221 inline typename Infix<TNeedle>::Type
222 segment(Pattern<TNeedle, TSpec> & me)
224 typedef typename Infix<TNeedle>::Type TInfix;
225 return TInfix(host(me), me.data_begin_position, me.data_end_position);
227 template <typename TNeedle, typename TSpec>
228 inline typename Infix<TNeedle>::Type
229 segment(Pattern<TNeedle, TSpec> const & me)
231 typedef typename Infix<TNeedle>::Type TInfix;
232 return TInfix(host(me), me.data_begin_position, me.data_end_position);
235 //////////////////////////////////////////////////////////////////////////////
240 ..summary:Returns the needle of a @Class.Pattern@ object (not implemented for some online-algorithms).
242 ..signature:needle(pattern)
243 ..param.pattern:The @Class.Pattern@ object to search with.
244 ...type:Class.Pattern
245 ..returns:The needle object to search for.
246 ..remarks:The result type is @Metafunction.Needle@$<TPattern>::Type$ for pattern of type $TPattern$.
249 template < typename TObject >
250 inline typename Needle<TObject>::Type &
256 template < typename TObject >
257 inline typename Needle<TObject const>::Type &
258 needle(TObject const &obj)
264 ///.Function.position.param.iterator.type:Class.Pattern
266 template < typename TNeedle, typename TSpec >
267 inline typename Needle< Pattern<TNeedle, TSpec> >::Type &
268 needle(Pattern<TNeedle, TSpec> & obj)
273 template < typename TNeedle, typename TSpec >
274 inline typename Needle< Pattern<TNeedle, TSpec> const>::Type &
275 needle(Pattern<TNeedle, TSpec> const & obj)
282 ..summary:Sets the needle of a @Class.Pattern@ object and optionally induces preprocessing.
284 ..signature:setNeedle(pattern, needle)
285 ..param.pattern:The @Class.Pattern@ object to search with.
286 ...type:Class.Pattern
287 ..param.needle:The needle object to search for.
291 template < typename TNeedle, typename TSpec >
293 setNeedle(Pattern<TNeedle, TSpec> &obj, TNeedle const &ndl) {
298 //////////////////////////////////////////////////////////////////////////////
302 ..summary:Search for a @Class.Pattern@ in a @Class.Finder@ object.
304 ..signature:find(finder, pattern)
305 ..signature:find(finder, pattern, k)
306 ..param.finder:The @Class.Finder@ object to search through.
307 ...remarks:For online-algorithm $patterns$, finder can also be an arbitrary @Concept.Rooted Iterator@.
309 ...type:Concept.Rooted Iterator
310 ..param.pattern:The @Class.Pattern@ object to search for.
311 ...remarks:For index $finders$, pattern can also be a Sequence.
312 ...type:Class.Pattern
313 ..param.k:Desired minimal score (for approximate matching).
314 ...remarks:$k$ has to be a number <= 0.
315 ...remarks:Differences are deletions, insertions and substitutions.
316 ..returns:$boolean$ that indicates whether an occurence of $pattern$ was found or not.
317 ..remarks:Repeated calls of this function iterate through all occurences of $pattern$.
322 ..summary:Holds the haystack and a current search context.
324 ..signature:Finder<THaystack[, TSpec]>
325 ..param.THaystack:The haystack type.
328 ..param.TSpec:The index-algorithm to search with (Optional).
329 ...default:The result of @Metafunction.DefaultFinder@
330 ...remarks:Leave empty for online pattern matching (see @Class.Pattern@).
331 ...remarks:If $THaystack$ is an @Class.Index@, then $TSpec$ specifies the index search algorithm.
332 ..remarks:$position(finder)$ returns the position of the current hit in the haystack.
333 If $THaystack$ is a set of strings or an index of a set of strings, then $position(finder)$ returns a @Class.Pair@ $(hayNo, pos)$,
334 in which $hayNo$ is the haystack index and $pos$ the local position of the hit.
335 ..remarks:Use $clear(finder)$ to reset a finder object and search from the beginning.
338 ///.Function.clear.param.object.type:Class.Finder
339 ///.Function.position.param.iterator.type:Class.Finder
341 template < typename THaystack, typename TSpec = typename DefaultFinder<THaystack>::Type >
344 typedef typename Iterator<THaystack, Rooted>::Type TIterator;
347 TIterator data_iterator;
348 bool _needReinit; // if true, the Pattern needs to be reinitialized
353 Finder(THaystack &haystack):
354 data_iterator(begin(haystack, Rooted())),
357 Finder(TIterator &iter):
361 Finder(TIterator const &iter):
365 Finder(Finder const &orig):
366 data_iterator(orig.data_iterator),
367 _needReinit(orig._needReinit) {};
369 //____________________________________________________________________________
371 inline typename Reference<TIterator>::Type
375 return value(hostIterator(*this));
378 inline typename Reference<TIterator const>::Type
382 return value(hostIterator(*this));
385 //____________________________________________________________________________
387 operator TIterator () const
390 return data_iterator;
393 //____________________________________________________________________________
399 //____________________________________________________________________________
401 template <typename THaystack, typename TSpec>
402 inline typename _Parameter<THaystack>::Type
403 host(Finder<THaystack, TSpec> & me)
406 return container(hostIterator(me));
409 template <typename THaystack, typename TSpec>
410 inline typename _Parameter<THaystack>::Type
411 host(Finder<THaystack, TSpec> const & me)
414 return container(hostIterator(me));
417 template <typename THaystack, typename TSpec>
418 inline typename _Parameter<THaystack>::Type
419 container(Finder<THaystack, TSpec> & me)
422 return container(hostIterator(me));
425 template <typename THaystack, typename TSpec>
426 inline typename _Parameter<THaystack>::Type
427 container(Finder<THaystack, TSpec> const & me)
430 return container(hostIterator(me));
433 //____________________________________________________________________________
435 template <typename THaystack, typename TSpec>
437 setHost(Finder<THaystack, TSpec> & me, typename _Parameter<THaystack>::Type container_)
440 setContainer(hostIterator(me), container_);
444 template <typename THaystack, typename TSpec>
446 setContainer(Finder<THaystack, TSpec> & me, typename _Parameter<THaystack>::Type container_)
449 setContainer(hostIterator(me), container_);
453 //____________________________________________________________________________
455 template <typename THaystack, typename TSpec>
456 inline typename Iterator<THaystack, Rooted>::Type &
457 hostIterator(Finder<THaystack, TSpec> & me)
460 return me.data_iterator;
463 template <typename THaystack, typename TSpec>
464 inline typename Iterator<THaystack, Rooted>::Type const &
465 hostIterator(Finder<THaystack, TSpec> const & me)
468 return me.data_iterator;
471 //____________________________________________________________________________
473 template <typename THaystack, typename TSpec>
475 empty(Finder<THaystack, TSpec> & me)
478 return me._needReinit;
481 template <typename THaystack, typename TSpec>
483 clear(Finder<THaystack, TSpec> & me)
486 me._needReinit = true;
489 //____________________________________________________________________________
491 template <typename T>
493 _finderSetNonEmpty(T & me)
500 template <typename THaystack, typename TSpec>
502 _finderSetNonEmpty(Finder<THaystack, TSpec> & me)
505 me._needReinit = false;
508 //____________________________________________________________________________
510 template <typename THaystack, typename TSpec>
512 atBegin(Finder<THaystack, TSpec> & me)
515 return (!empty(me) && atBegin(hostIterator(me)));
518 template <typename THaystack, typename TSpec>
520 atEnd(Finder<THaystack, TSpec> & me)
523 return (!empty(me) && atEnd(hostIterator(me)));
526 //____________________________________________________________________________
528 template <typename THaystack, typename TSpec>
530 goBegin(Finder<THaystack, TSpec> & me)
533 //_finderSetNonEmpty(me);
534 goBegin(hostIterator(me));
537 template <typename THaystack, typename TSpec>
539 goEnd(Finder<THaystack, TSpec> & me)
542 //_finderSetNonEmpty(me);
543 goEnd(hostIterator(me));
546 //____________________________________________________________________________
548 template <typename THaystack, typename TSpec>
549 inline typename Position<Finder<THaystack, TSpec> >::Type
550 position(Finder<THaystack, TSpec> & me)
553 if (empty(me)) return 0;
554 return position(hostIterator(me));
557 template <typename THaystack, typename TSpec>
558 inline typename Position<Finder<THaystack, TSpec> >::Type
559 position(Finder<THaystack, TSpec> const & me)
562 if (empty(me)) return 0;
563 return position(hostIterator(me));
566 //____________________________________________________________________________
568 .Function.setPosition:
570 ..summary:Sets the position of a finder.
571 ..signature:setPosition(finder, pos)
572 ..param.finder:A finder.
573 ...class:Class.Finder
574 ..param.pos:A position.
575 ...metafunction:Metafunction.Position
576 ..see:Function.position
579 template <typename THaystack, typename TSpec, typename TPosition>
581 setPosition(Finder<THaystack, TSpec> & me, TPosition pos_)
584 setPosition(hostIterator(me), pos_);
587 //____________________________________________________________________________
589 template <typename THaystack, typename TSpec>
590 inline Finder<THaystack, TSpec> &
591 operator--(Finder<THaystack, TSpec> & me)
598 template <typename THaystack, typename TSpec>
599 inline Finder<THaystack, TSpec> &
600 operator++(Finder<THaystack, TSpec> & me)
603 /* if (beforeBegin()) {
604 goBegin(hostIterator(me));
610 //////////////////////////////////////////////////////////////////////////////
612 //////////////////////////////////////////////////////////////////////////////
614 template <typename THaystack, typename TSpec, typename TIntegral>
615 inline Finder<THaystack, TSpec> const
616 operator + (Finder<THaystack, TSpec> const & left, TIntegral right)
619 return Finder<THaystack, TSpec>(hostIterator(left) + right);
622 //////////////////////////////////////////////////////////////////////////////
624 //////////////////////////////////////////////////////////////////////////////
626 template <typename THaystack, typename TSpec, typename TIntegral>
627 inline Finder<THaystack, TSpec> &
628 operator += (Finder<THaystack, TSpec> & left,
632 hostIterator(left) += right;
636 //////////////////////////////////////////////////////////////////////////////
638 //////////////////////////////////////////////////////////////////////////////
640 template <typename THaystack, typename TSpec, typename TIntegral>
641 inline Finder<THaystack, TSpec> const
642 operator - (Finder<THaystack, TSpec> const & left, TIntegral right)
645 return Finder<THaystack, TSpec>(hostIterator(left) - right);
648 template <typename THaystack, typename TSpec, typename TIntegral>
649 inline typename Difference<Finder<THaystack, TSpec> const>::Type
650 operator - (Finder<THaystack, TSpec> const & left, Finder<THaystack, TSpec> const & right)
653 return hostIterator(left) - hostIterator(right);
656 //////////////////////////////////////////////////////////////////////////////
658 //////////////////////////////////////////////////////////////////////////////
660 template <typename THaystack, typename TSpec, typename TIntegral>
661 inline Finder<THaystack, TSpec> &
662 operator -= (Finder<THaystack, TSpec> & left,
666 hostIterator(left) -= right;
670 //____________________________________________________________________________
674 .Function.setHaystack:
675 ..summary:Sets the haystack of a @Class.Finder@ object.
677 ..signature:setHaystack(finder, haystack)
678 ..param.finder:The @Class.Finder@ object to search with.
680 ..param.haystack:The haystack object the finder searches through.
684 template < typename THaystack, typename TSpec >
686 setHaystack(Finder<THaystack, TSpec> &obj, THaystack const &hstk) {
692 ..summary:Returns the haystack of a @Class.Finder@ object.
694 ..signature:haystack(finder)
695 ..param.finder:The @Class.Finder@ object to search through.
697 ..returns:The haystack object.
698 ..remarks:The result type is @Metafunction.Haystack@$<TFinder>::Type$ for finder of type $TFinder$.
701 template < typename TObject >
702 inline typename Haystack<TObject>::Type &
703 haystack(TObject &obj) {
704 return container(obj);
707 template < typename TObject >
708 inline typename Haystack<TObject const>::Type &
709 haystack(TObject const &obj) {
710 return container(obj);
714 //////////////////////////////////////////////////////////////////////////////
717 template <typename THaystack, typename TSpec>
718 struct Container< Finder<THaystack, TSpec> > {
719 typedef THaystack Type;
722 template <typename THaystack, typename TSpec>
723 struct Container< Finder<THaystack, TSpec> const> {
724 typedef THaystack const Type;
727 template <typename THaystack, typename TSpec>
728 struct Host< Finder<THaystack, TSpec> > {
729 typedef THaystack Type;
732 template <typename THaystack, typename TSpec>
733 struct Host< Finder<THaystack, TSpec> const> {
734 typedef THaystack const Type;
738 template <typename THaystack, typename TSpec>
739 struct Value< Finder<THaystack, TSpec> > {
740 typedef typename Value<THaystack>::Type Type;
743 template <typename THaystack, typename TSpec>
744 struct Position< Finder<THaystack, TSpec> >:
745 Position<THaystack> {};
747 template <typename THaystack, typename TSpec>
748 struct Difference< Finder<THaystack, TSpec> > {
749 typedef typename Difference<THaystack>::Type Type;
752 template <typename THaystack, typename TSpec>
753 struct Size< Finder<THaystack, TSpec> > {
754 typedef typename Size<THaystack>::Type Type;
757 //____________________________________________________________________________
760 template <typename TNeedle, typename TSpec>
761 struct Container< Pattern<TNeedle, TSpec> > {
762 typedef TNeedle Type;
765 template <typename TNeedle, typename TSpec>
766 struct Container< Pattern<TNeedle, TSpec> const > {
767 typedef TNeedle const Type;
770 template <typename TNeedle, typename TSpec>
771 struct Host< Pattern<TNeedle, TSpec> > {
772 typedef TNeedle Type;
775 template <typename TNeedle, typename TSpec>
776 struct Host< Pattern<TNeedle, TSpec> const > {
777 typedef TNeedle const Type;
781 template <typename TPattern, typename TSpec>
782 struct Value< Pattern<TPattern, TSpec> > {
783 typedef typename Value<TPattern>::Type Type;
786 template <typename TPattern, typename TSpec>
787 struct Position< Pattern<TPattern, TSpec> > {
788 typedef typename Position<TPattern>::Type Type;
791 template <typename TPattern, typename TSpec>
792 struct Difference< Pattern<TPattern, TSpec> > {
793 typedef typename Difference<TPattern>::Type Type;
796 template <typename TPattern, typename TSpec>
797 struct Size< Pattern<TPattern, TSpec> > {
798 typedef typename Size<TPattern>::Type Type;
802 //////////////////////////////////////////////////////////////////////////////
804 }// namespace SEQAN_NAMESPACE_MAIN
806 #endif //#ifndef SEQAN_HEADER_...