SeqAn-1.1/seqan/find/find_base.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   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.
  11
  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.
  16
  17  ============================================================================
  18   $Id: find_base.h,v 1.1 2008/08/25 16:20:07 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_FIND_BASE_H
  22 #define SEQAN_HEADER_FIND_BASE_H
  23
  24
  25 //////////////////////////////////////////////////////////////////////////////
  26
  27 namespace SEQAN_NAMESPACE_MAIN
  28 {
  29
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 /**
  33 .Metafunction.DefaultFinder:
  34 ..cat:Searching
  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@.
  39 */
  40         template < typename TObject >
  41         struct DefaultFinder {
  42                 typedef void Type;
  43         };
  44
  45 /**
  46 .Metafunction.DefaultPattern:
  47 ..cat:Searching
  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.
  52 */
  53         template < typename TObject >
  54         struct DefaultPattern {
  55                 typedef void Type;
  56         };
  57
  58 /**
  59 .Metafunction.Haystack:
  60 ..summary:Returns the haystack type of a @Class.Finder@ type.
  61 ..cat:Searching
  62 ..signature:Haystack<TFinder>::Type
  63 ..param.TFinder:A @Class.Finder@ type.
  64 ...type:Class.Finder
  65 ..returns:The haystack type of $TFinder$, i.e. $THaystack$ for $Finder<THaystack, TSpec>$.
  66 */
  67
  68         template <typename TFinder>
  69         struct Haystack {
  70                 typedef typename Container<TFinder>::Type Type;
  71         };
  72
  73 /**
  74 .Metafunction.Needle:
  75 ..summary:Returns the needle type of a @Class.Pattern@ type.
  76 ..cat:Searching
  77 ..signature:Needle<TPattern>::Type
  78 ..param.TPattern:A @Class.Pattern@ type.
  79 ...type:Class.Pattern
  80 ..returns:The needle type of $TPattern$, i.e. $TNeedle$ for $Pattern<TNeedle, TSpec>$.
  81 */
  82
  83         template <typename TPattern>
  84         struct Needle {
  85                 typedef typename Host<TPattern>::Type Type;
  86         };
  87
  88         template <typename THost, typename TSpec>
  89         struct Needle<Segment<THost, TSpec> > {
  90                 typedef Segment<THost, TSpec> Type;
  91         };
  92
  93         template <typename THost, typename TSpec>
  94         struct Needle<Segment<THost, TSpec> const> {
  95                 typedef Segment<THost, TSpec> const Type;
  96         };
  97
  98 //////////////////////////////////////////////////////////////////////////////
  99
 100 /**
 101 .Class.Pattern:
 102 ..summary:Holds the needle and preprocessing data (depends on algorithm).
 103 ..cat:Searching
 104 ..signature:Pattern<TNeedle[, TSpec]>
 105 ..param.TNeedle:The needle type.
 106 ...type:Class.String
 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.
 111 */
 112
 113 template < typename TNeedle, typename TSpec = typename DefaultPattern<TNeedle>::Type >
 114 class Pattern;
 115
 116 //default implementation
 117 template < typename TNeedle >
 118 class Pattern<TNeedle, void>
 119 {
 120 public:
 121         typedef typename Position<TNeedle>::Type TNeedlePosition;
 122
 123         Holder<TNeedle> data_host;
 124         TNeedlePosition data_begin_position;
 125         TNeedlePosition data_end_position;
 126
 127         Pattern() {}
 128
 129         template <typename _TNeedle>
 130         Pattern(_TNeedle & ndl):
 131                 data_host(ndl) {}
 132
 133         template <typename _TNeedle>
 134         Pattern(_TNeedle const & ndl):
 135                 data_host(ndl) {}
 136
 137 };
 138 //////////////////////////////////////////////////////////////////////////////
 139
 140 template <typename TNeedle, typename TSpec>
 141 inline Holder<TNeedle> &
 142 _dataHost(Pattern<TNeedle, TSpec> & me)
 143 {
 144         return me.data_host;
 145 }
 146 template <typename TNeedle, typename TSpec>
 147 inline Holder<TNeedle> &
 148 _dataHost(Pattern<TNeedle, TSpec> const & me)
 149 {
 150         return const_cast<Holder<TNeedle> &>(me.data_host);
 151 }
 152
 153 //host access: see basic_host.h
 154
 155
 156 //???TODO: Diese Funktion entfernen! (sobald setHost bei anderen pattern nicht mehr eine Art "assignHost" ist)
 157 template <typename TNeedle, typename TSpec, typename TNeedle2>
 158 inline void
 159 setHost(Pattern<TNeedle, TSpec> & me,
 160                 TNeedle2 const & ndl)
 161 {
 162          me.data_host = ndl; //assign => Pattern haelt eine Kopie => doof!
 163 }
 164 template <typename TNeedle, typename TSpec, typename TNeedle2>
 165 inline void
 166 setHost(Pattern<TNeedle, TSpec> & me,
 167                 TNeedle2 & ndl)
 168 {
 169          me.data_host = ndl; //assign => Pattern haelt eine Kopie => doof!
 170 }
 171 //////////////////////////////////////////////////////////////////////////////
 172
 173 template <typename TNeedle, typename TSpec>
 174 inline typename Position<Pattern<TNeedle, TSpec> >::Type &
 175 beginPosition(Pattern<TNeedle, TSpec> & me)
 176 {
 177         return me.data_begin_position;
 178 }
 179 template <typename TNeedle, typename TSpec>
 180 inline typename Position<Pattern<TNeedle, TSpec> const >::Type &
 181 beginPosition(Pattern<TNeedle, TSpec> const & me)
 182 {
 183         return me.data_begin_position;
 184 }
 185
 186
 187 template <typename TNeedle, typename TSpec, typename TPosition>
 188 inline void
 189 setBeginPosition(Pattern<TNeedle, TSpec> & me,
 190                                  TPosition _pos)
 191 {
 192         me.data_begin_position = _pos;
 193 }
 194
 195 //////////////////////////////////////////////////////////////////////////////
 196
 197 template <typename TNeedle, typename TSpec>
 198 inline typename Position<Pattern<TNeedle, TSpec> >::Type &
 199 endPosition(Pattern<TNeedle, TSpec> & me)
 200 {
 201         return me.data_end_position;
 202 }
 203 template <typename TNeedle, typename TSpec>
 204 inline typename Position<Pattern<TNeedle, TSpec> const >::Type &
 205 endPosition(Pattern<TNeedle, TSpec> const & me)
 206 {
 207         return me.data_end_position;
 208 }
 209
 210 template <typename TNeedle, typename TSpec, typename TPosition>
 211 inline void
 212 setEndPosition(Pattern<TNeedle, TSpec> & me,
 213                            TPosition _pos)
 214 {
 215         me.data_end_position = _pos;
 216 }
 217
 218 //////////////////////////////////////////////////////////////////////////////
 219
 220 template <typename TNeedle, typename TSpec>
 221 inline typename Infix<TNeedle>::Type
 222 segment(Pattern<TNeedle, TSpec> & me)
 223 {
 224         typedef typename Infix<TNeedle>::Type TInfix;
 225         return TInfix(host(me), me.data_begin_position, me.data_end_position);
 226 }
 227 template <typename TNeedle, typename TSpec>
 228 inline typename Infix<TNeedle>::Type
 229 segment(Pattern<TNeedle, TSpec> const & me)
 230 {
 231         typedef typename Infix<TNeedle>::Type TInfix;
 232         return TInfix(host(me), me.data_begin_position, me.data_end_position);
 233 }
 234
 235 //////////////////////////////////////////////////////////////////////////////
 236
 237
 238 /**
 239 .Function.needle:
 240 ..summary:Returns the needle of a @Class.Pattern@ object (not implemented for some online-algorithms).
 241 ..cat:Searching
 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$.
 247 */
 248
 249 template < typename TObject >
 250 inline typename Needle<TObject>::Type &
 251 needle(TObject &obj)
 252 {
 253         return obj;
 254 }
 255
 256 template < typename TObject >
 257 inline typename Needle<TObject const>::Type &
 258 needle(TObject const &obj)
 259 {
 260         return obj;
 261 }
 262
 263
 264 ///.Function.position.param.iterator.type:Class.Pattern
 265
 266 template < typename TNeedle, typename TSpec >
 267 inline typename Needle< Pattern<TNeedle, TSpec> >::Type &
 268 needle(Pattern<TNeedle, TSpec> & obj)
 269 {
 270         return host(obj);
 271 }
 272
 273 template < typename TNeedle, typename TSpec >
 274 inline typename Needle< Pattern<TNeedle, TSpec> const>::Type &
 275 needle(Pattern<TNeedle, TSpec> const & obj)
 276 {
 277         return host(obj);
 278 }
 279
 280 /**
 281 .Function.setNeedle:
 282 ..summary:Sets the needle of a @Class.Pattern@ object and optionally induces preprocessing.
 283 ..cat:Searching
 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.
 288 ...type:Class.String
 289 */
 290
 291         template < typename TNeedle, typename TSpec >
 292         inline void
 293         setNeedle(Pattern<TNeedle, TSpec> &obj, TNeedle const &ndl) {
 294                 setHost(obj, ndl);
 295         }
 296
 297
 298 //////////////////////////////////////////////////////////////////////////////
 299
 300 /**
 301 .Function.find:
 302 ..summary:Search for a @Class.Pattern@ in a @Class.Finder@ object.
 303 ..cat:Searching
 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@.
 308 ...type:Class.Finder
 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$.
 318 */
 319
 320 /**
 321 .Class.Finder:
 322 ..summary:Holds the haystack and a current search context.
 323 ..cat:Searching
 324 ..signature:Finder<THaystack[, TSpec]>
 325 ..param.THaystack:The haystack type.
 326 ...type:Class.String
 327 ...type:Class.Index
 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.
 336 */
 337
 338 ///.Function.clear.param.object.type:Class.Finder
 339 ///.Function.position.param.iterator.type:Class.Finder
 340
 341         template < typename THaystack, typename TSpec = typename DefaultFinder<THaystack>::Type >
 342         class Finder
 343         {
 344                 typedef typename Iterator<THaystack, Rooted>::Type TIterator;
 345
 346         public:
 347                 TIterator data_iterator;
 348                 bool _needReinit;                                       // if true, the Pattern needs to be reinitialized
 349
 350                 Finder():
 351                         _needReinit(true) {}
 352
 353                 Finder(THaystack &haystack):
 354                         data_iterator(begin(haystack, Rooted())),
 355                         _needReinit(true) {}
 356
 357                 Finder(TIterator &iter):
 358                         data_iterator(iter),
 359                         _needReinit(true) {}
 360
 361                 Finder(TIterator const &iter):
 362                         data_iterator(iter),
 363                         _needReinit(true) {}
 364
 365                 Finder(Finder const &orig):
 366                         data_iterator(orig.data_iterator),
 367                         _needReinit(orig._needReinit) {};
 368
 369 //____________________________________________________________________________
 370
 371                 inline typename Reference<TIterator>::Type
 372                 operator* ()
 373                 {
 374 SEQAN_CHECKPOINT
 375                         return value(hostIterator(*this));
 376                 }
 377
 378                 inline typename Reference<TIterator const>::Type
 379                 operator* () const
 380                 {
 381 SEQAN_CHECKPOINT
 382                         return value(hostIterator(*this));
 383                 }
 384
 385 //____________________________________________________________________________
 386
 387                 operator TIterator () const
 388                 {
 389 SEQAN_CHECKPOINT
 390                         return data_iterator;
 391                 }
 392
 393 //____________________________________________________________________________
 394
 395         };
 396
 397
 398
 399 //____________________________________________________________________________
 400
 401         template <typename THaystack, typename TSpec>
 402         inline typename _Parameter<THaystack>::Type
 403         host(Finder<THaystack, TSpec> & me)
 404         {
 405 SEQAN_CHECKPOINT
 406                 return container(hostIterator(me));
 407         }
 408
 409         template <typename THaystack, typename TSpec>
 410         inline typename _Parameter<THaystack>::Type
 411         host(Finder<THaystack, TSpec> const & me)
 412         {
 413 SEQAN_CHECKPOINT
 414                 return container(hostIterator(me));
 415         }
 416
 417         template <typename THaystack, typename TSpec>
 418         inline typename _Parameter<THaystack>::Type
 419         container(Finder<THaystack, TSpec> & me)
 420         {
 421 SEQAN_CHECKPOINT
 422                 return container(hostIterator(me));
 423         }
 424
 425         template <typename THaystack, typename TSpec>
 426         inline typename _Parameter<THaystack>::Type
 427         container(Finder<THaystack, TSpec> const & me)
 428         {
 429 SEQAN_CHECKPOINT
 430                 return container(hostIterator(me));
 431         }
 432
 433 //____________________________________________________________________________
 434
 435         template <typename THaystack, typename TSpec>
 436         inline void
 437         setHost(Finder<THaystack, TSpec> & me, typename _Parameter<THaystack>::Type container_)
 438         {
 439 SEQAN_CHECKPOINT
 440                 setContainer(hostIterator(me), container_);
 441                 goBegin(me);
 442         }
 443
 444         template <typename THaystack, typename TSpec>
 445         inline void
 446         setContainer(Finder<THaystack, TSpec> & me, typename _Parameter<THaystack>::Type container_)
 447         {
 448 SEQAN_CHECKPOINT
 449                 setContainer(hostIterator(me), container_);
 450                 goBegin(me);
 451         }
 452
 453 //____________________________________________________________________________
 454
 455         template <typename THaystack, typename TSpec>
 456         inline typename Iterator<THaystack, Rooted>::Type &
 457         hostIterator(Finder<THaystack, TSpec> & me)
 458         {
 459 SEQAN_CHECKPOINT
 460                 return me.data_iterator;
 461         }
 462
 463         template <typename THaystack, typename TSpec>
 464         inline typename Iterator<THaystack, Rooted>::Type const &
 465         hostIterator(Finder<THaystack, TSpec> const & me)
 466         {
 467 SEQAN_CHECKPOINT
 468                 return me.data_iterator;
 469         }
 470
 471 //____________________________________________________________________________
 472
 473         template <typename THaystack, typename TSpec>
 474         inline bool
 475         empty(Finder<THaystack, TSpec> & me)
 476         {
 477 SEQAN_CHECKPOINT
 478                 return me._needReinit;
 479         }
 480
 481         template <typename THaystack, typename TSpec>
 482         inline void
 483         clear(Finder<THaystack, TSpec> & me)
 484         {
 485 SEQAN_CHECKPOINT
 486                 me._needReinit = true;
 487         }
 488
 489 //____________________________________________________________________________
 490
 491         template <typename T>
 492         inline void
 493         _finderSetNonEmpty(T & me)
 494         {
 495 SEQAN_CHECKPOINT
 496                 goBegin(me);
 497         }
 498
 499
 500         template <typename THaystack, typename TSpec>
 501         inline void
 502         _finderSetNonEmpty(Finder<THaystack, TSpec> & me)
 503         {
 504 SEQAN_CHECKPOINT
 505                 me._needReinit = false;
 506         }
 507
 508 //____________________________________________________________________________
 509
 510         template <typename THaystack, typename TSpec>
 511         inline bool
 512         atBegin(Finder<THaystack, TSpec> & me)
 513         {
 514 SEQAN_CHECKPOINT
 515                 return (!empty(me) && atBegin(hostIterator(me)));
 516         }
 517
 518         template <typename THaystack, typename TSpec>
 519         inline bool
 520         atEnd(Finder<THaystack, TSpec> & me)
 521         {
 522 SEQAN_CHECKPOINT
 523                 return (!empty(me) && atEnd(hostIterator(me)));
 524         }
 525
 526 //____________________________________________________________________________
 527
 528         template <typename THaystack, typename TSpec>
 529         inline void
 530         goBegin(Finder<THaystack, TSpec> & me)
 531         {
 532 SEQAN_CHECKPOINT
 533                 //_finderSetNonEmpty(me);
 534                 goBegin(hostIterator(me));
 535         }
 536
 537         template <typename THaystack, typename TSpec>
 538         inline void
 539         goEnd(Finder<THaystack, TSpec> & me)
 540         {
 541 SEQAN_CHECKPOINT
 542                 //_finderSetNonEmpty(me);
 543                 goEnd(hostIterator(me));
 544         }
 545
 546 //____________________________________________________________________________
 547
 548         template <typename THaystack, typename TSpec>
 549         inline typename Position<Finder<THaystack, TSpec> >::Type
 550         position(Finder<THaystack, TSpec> & me)
 551         {
 552 SEQAN_CHECKPOINT
 553                 if (empty(me)) return 0;
 554                 return position(hostIterator(me));
 555         }
 556
 557         template <typename THaystack, typename TSpec>
 558         inline typename Position<Finder<THaystack, TSpec> >::Type
 559         position(Finder<THaystack, TSpec> const & me)
 560         {
 561 SEQAN_CHECKPOINT
 562                 if (empty(me)) return 0;
 563                 return position(hostIterator(me));
 564         }
 565
 566 //____________________________________________________________________________
 567 /**
 568 .Function.setPosition:
 569 ..cat:Searching
 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
 577 */
 578
 579         template <typename THaystack, typename TSpec, typename TPosition>
 580         inline void
 581         setPosition(Finder<THaystack, TSpec> & me, TPosition pos_)
 582         {
 583 SEQAN_CHECKPOINT
 584                 setPosition(hostIterator(me), pos_);
 585         }
 586
 587 //____________________________________________________________________________
 588
 589         template <typename THaystack, typename TSpec>
 590         inline Finder<THaystack, TSpec> &
 591         operator--(Finder<THaystack, TSpec> & me)
 592         {
 593 SEQAN_CHECKPOINT
 594                 --hostIterator(me);
 595                 return me;
 596         }
 597
 598         template <typename THaystack, typename TSpec>
 599         inline Finder<THaystack, TSpec> &
 600         operator++(Finder<THaystack, TSpec> & me)
 601         {
 602 SEQAN_CHECKPOINT
 603 /*                      if (beforeBegin()) {
 604                         goBegin(hostIterator(me));
 605                 } else*/
 606                         ++hostIterator(me);
 607                 return me;
 608         }
 609
 610 //////////////////////////////////////////////////////////////////////////////
 611 // operator +
 612 //////////////////////////////////////////////////////////////////////////////
 613
 614         template <typename THaystack, typename TSpec, typename TIntegral>
 615         inline Finder<THaystack, TSpec> const
 616         operator + (Finder<THaystack, TSpec> const & left, TIntegral right)
 617         {
 618 SEQAN_CHECKPOINT
 619                 return Finder<THaystack, TSpec>(hostIterator(left) + right);
 620         }
 621
 622 //////////////////////////////////////////////////////////////////////////////
 623 // operator +=
 624 //////////////////////////////////////////////////////////////////////////////
 625
 626         template <typename THaystack, typename TSpec, typename TIntegral>
 627         inline Finder<THaystack, TSpec> &
 628         operator += (Finder<THaystack, TSpec> & left,
 629                                         TIntegral right)
 630         {
 631 SEQAN_CHECKPOINT
 632                 hostIterator(left) += right;
 633                 return left;
 634         }
 635
 636 //////////////////////////////////////////////////////////////////////////////
 637 // operator -
 638 //////////////////////////////////////////////////////////////////////////////
 639
 640         template <typename THaystack, typename TSpec, typename TIntegral>
 641         inline Finder<THaystack, TSpec> const
 642         operator - (Finder<THaystack, TSpec> const & left, TIntegral right)
 643         {
 644 SEQAN_CHECKPOINT
 645                 return Finder<THaystack, TSpec>(hostIterator(left) - right);
 646         }
 647
 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)
 651         {
 652 SEQAN_CHECKPOINT
 653                 return hostIterator(left) - hostIterator(right);
 654         }
 655
 656 //////////////////////////////////////////////////////////////////////////////
 657 // operator -=
 658 //////////////////////////////////////////////////////////////////////////////
 659
 660         template <typename THaystack, typename TSpec, typename TIntegral>
 661         inline Finder<THaystack, TSpec> &
 662         operator -= (Finder<THaystack, TSpec> & left,
 663                                         TIntegral right)
 664         {
 665 SEQAN_CHECKPOINT
 666                 hostIterator(left) -= right;
 667                 return left;
 668         }
 669
 670 //____________________________________________________________________________
 671
 672
 673 /**
 674 .Function.setHaystack:
 675 ..summary:Sets the haystack of a @Class.Finder@ object.
 676 ..cat:Searching
 677 ..signature:setHaystack(finder, haystack)
 678 ..param.finder:The @Class.Finder@ object to search with.
 679 ...type:Class.Finder
 680 ..param.haystack:The haystack object the finder searches through.
 681 ...type:Class.String
 682 */
 683
 684         template < typename THaystack, typename TSpec >
 685         inline void
 686         setHaystack(Finder<THaystack, TSpec> &obj, THaystack const &hstk) {
 687                 setHost(obj, hstk);
 688         }
 689
 690 /**
 691 .Function.haystack:
 692 ..summary:Returns the haystack of a @Class.Finder@ object.
 693 ..cat:Searching
 694 ..signature:haystack(finder)
 695 ..param.finder:The @Class.Finder@ object to search through.
 696 ...type:Class.Finder
 697 ..returns:The haystack object.
 698 ..remarks:The result type is @Metafunction.Haystack@$<TFinder>::Type$ for finder of type $TFinder$.
 699 */
 700
 701         template < typename TObject >
 702         inline typename Haystack<TObject>::Type &
 703         haystack(TObject &obj) {
 704                 return container(obj);
 705         }
 706
 707         template < typename TObject >
 708         inline typename Haystack<TObject const>::Type &
 709         haystack(TObject const &obj) {
 710                 return container(obj);
 711         }
 712
 713
 714 //////////////////////////////////////////////////////////////////////////////
 715
 716
 717         template <typename THaystack, typename TSpec>
 718         struct Container< Finder<THaystack, TSpec> > {
 719                 typedef THaystack Type;
 720         };
 721
 722         template <typename THaystack, typename TSpec>
 723         struct Container< Finder<THaystack, TSpec> const> {
 724                 typedef THaystack const Type;
 725         };
 726
 727         template <typename THaystack, typename TSpec>
 728         struct Host< Finder<THaystack, TSpec> > {
 729                 typedef THaystack Type;
 730         };
 731
 732         template <typename THaystack, typename TSpec>
 733         struct Host< Finder<THaystack, TSpec> const> {
 734                 typedef THaystack const Type;
 735         };
 736
 737
 738         template <typename THaystack, typename TSpec>
 739         struct Value< Finder<THaystack, TSpec> > {
 740                 typedef typename Value<THaystack>::Type Type;
 741         };
 742
 743         template <typename THaystack, typename TSpec>
 744         struct Position< Finder<THaystack, TSpec> >:
 745                 Position<THaystack> {};
 746
 747         template <typename THaystack, typename TSpec>
 748         struct Difference< Finder<THaystack, TSpec> > {
 749                 typedef typename Difference<THaystack>::Type Type;
 750         };
 751
 752         template <typename THaystack, typename TSpec>
 753         struct Size< Finder<THaystack, TSpec> > {
 754                 typedef typename Size<THaystack>::Type Type;
 755         };
 756
 757 //____________________________________________________________________________
 758
 759
 760         template <typename TNeedle, typename TSpec>
 761         struct Container< Pattern<TNeedle, TSpec> > {
 762                 typedef TNeedle Type;
 763         };
 764
 765         template <typename TNeedle, typename TSpec>
 766         struct Container< Pattern<TNeedle, TSpec> const > {
 767                 typedef TNeedle const Type;
 768         };
 769
 770         template <typename TNeedle, typename TSpec>
 771         struct Host< Pattern<TNeedle, TSpec> > {
 772                 typedef TNeedle Type;
 773         };
 774
 775         template <typename TNeedle, typename TSpec>
 776         struct Host< Pattern<TNeedle, TSpec> const > {
 777                 typedef TNeedle const Type;
 778         };
 779
 780
 781         template <typename TPattern, typename TSpec>
 782         struct Value< Pattern<TPattern, TSpec> > {
 783                 typedef typename Value<TPattern>::Type Type;
 784         };
 785
 786         template <typename TPattern, typename TSpec>
 787         struct Position< Pattern<TPattern, TSpec> > {
 788                 typedef typename Position<TPattern>::Type Type;
 789         };
 790
 791         template <typename TPattern, typename TSpec>
 792         struct Difference< Pattern<TPattern, TSpec> > {
 793                 typedef typename Difference<TPattern>::Type Type;
 794         };
 795
 796         template <typename TPattern, typename TSpec>
 797         struct Size< Pattern<TPattern, TSpec> > {
 798                 typedef typename Size<TPattern>::Type Type;
 799         };
 800
 801
 802 //////////////////////////////////////////////////////////////////////////////
 803
 804 }// namespace SEQAN_NAMESPACE_MAIN
 805
 806 #endif //#ifndef SEQAN_HEADER_...