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_base.h,v 1.3 2009/03/13 14:34:32 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_INDEX_BASE_H
22 #define SEQAN_HEADER_INDEX_BASE_H
24 //#define SEQAN_TEST_INDEX
26 namespace SEQAN_NAMESPACE_MAIN
29 //////////////////////////////////////////////////////////////////////////////
30 // needful forward declarations
32 // suffix array construction specs
35 struct LarssonSadakane;
40 // lcp table construction algorithms
42 struct KasaiOriginal; // original, but more space-consuming algorithm
44 // enhanced suffix array construction algorithms
48 template <typename TSpec = void>
52 //////////////////////////////////////////////////////////////////////////////
54 .Metafunction.DefaultIndexSpec:
56 ..summary:Default @Class.Index@ specialization type.
57 ..signature:DefaultIndexSpec<TText>::Type
58 ..param.TText:The given text type.
59 ..returns:Can be @Spec.Index_ESA@ or $Index_QGram$, etc.
60 ..remarks:Currently @Spec.Index_ESA@ is default if $TText$ is a @Class.String@.
62 template < typename TObject >
63 struct DefaultIndexSpec {
64 typedef Index_ESA<> Type;
67 //////////////////////////////////////////////////////////////////////////////
69 .Metafunction.DefaultIndexStringSpec:
71 ..summary:Default @Class.String@ specialization type of the @Metafunction.Fibre@ of an @Class.Index@.
72 ..signature:DefaultIndexStringSpec<TIndex>::Type
73 ..param.TIndex:An @Class.Index@ Type.
74 ..returns:If the underlying text is a @Class.String@ or a set of Strings (see @Class.StringSet@) the String's spec. type is returned.
75 ..remarks:Most of the @Class.Index@ fibres are strings. The @Class.String@ specialization type is chosen by this meta-function.
77 template < typename TIndex >
78 struct DefaultIndexStringSpec {
82 // template < typename TValue, typename TSpec >
83 // struct DefaultIndexStringSpec< String<TValue, External<TSpec> > > {
84 // typedef External<TSpec> Type;
87 template < typename TString, typename TSpec >
88 struct DefaultIndexStringSpec< StringSet<TString, TSpec> >:
89 DefaultIndexStringSpec<TString> {};
92 //////////////////////////////////////////////////////////////////////////////
95 ..summary:Contains preprocessing data of a fixed text. Allows fast dictionary look-up and advanced computations.
97 ..signature:Index<TText[, TSpec]>
98 ..param.TText:The text type.
100 ...metafunction:Metafunction.Host
101 ..param.TSpec:The index type.
102 ...default:The result of @Metafunction.DefaultIndexSpec@
103 ...metafunction:Metafunction.Spec
104 ..remarks:An index contains various arrays or objects, also called fibres (see @Metafunction.Fibre@).
105 ..remarks:These fibres are created on demand depending on the requirements of an algorithm.
108 ///.Function.setHaystack.param.haystack.type:Class.Index
110 // index as a haystack
113 typename TSpec = typename DefaultIndexSpec<TObject>::Type >
116 template <typename TObject, typename TSpec>
117 struct Host< Index<TObject, TSpec> > {
118 typedef TObject Type;
121 template <typename TObject, typename TSpec>
122 struct Spec< Index<TObject, TSpec> > {
127 //////////////////////////////////////////////////////////////////////////////
130 ..summary:Type of a specific bundle member (fibre).
131 ..signature:Fibre<TIndex, TSpec>::Type
133 ..param.TIndex:The fibre container type.
134 ..param.TSpec:Type to specify the fibre.
135 ..returns:Fibre type.
136 ..remarks:An @Class.Index@ can be seen as a bundle consisting of various fibres. In most cases this type is $String<Size<TIndex>::Type>$.
137 ..remarks:A @Metafunction.Fibre@ need not to be a real container. It can also be view (see @Tag.ESA Index Fibres.ESA_RawText@).
139 // meta function to get the type of a bundle fibre
140 template < typename TIndex, typename TSpec >
142 typedef String< typename Size<TIndex>::Type > Type;
145 template < typename TIndex, typename TSpec >
146 struct Fibre<TIndex const, TSpec> {
147 typedef typename Fibre<TIndex, TSpec>::Type const Type;
156 // less function to search in sorted list for fibre id
157 struct FibreLess: public ::std::binary_function<FibreRecord, unsigned, bool>
158 { // functor for operator>
159 inline bool operator()(FibreRecord const & _Left, unsigned const _Right) const
160 { // apply operator> to operands
161 return (_Left.id < _Right);
165 //////////////////////////////////////////////////////////////////////////////
167 .Metafunction.DefaultIndexCreator:
169 ..summary:Default algorithm to create a demanded and not yet existing @Metafunction.Fibre@.
170 ..signature:DefaultIndexCreator<TIndex, TFibre>::Type
171 ..param.TIndex:An @Class.Index@ Type.
172 ..param.TFibre:A tag specifying the fibre (e.g. @Tag.ESA Index Fibres.ESA_SA@).
173 ..returns:A tag specifying the default algorithm to create the fibre with.
175 // standard algorithm for indices creation
176 template < typename TIndex, typename TFibre >
177 struct DefaultIndexCreator {
178 typedef Default Type;
181 //////////////////////////////////////////////////////////////////////////////
184 ..summary:General purpose container of various members.
185 ..signature:Bundle<TValue, TSize>
186 ..param.TValue:The value type, that is the type of the items/characters stored in the string.
187 ...remarks:Use @Metafunction.Value@ to get the value type for a given class.
188 ..param.TSpec:The specializing type.
189 ...default:$Alloc<>$, see @Spec.Alloc String@.
192 template < typename TSpec = void >
194 typedef ::std::vector<FibreRecord> TFibreRecords;
195 TFibreRecords fibres;
198 template < typename TBundleSpec, typename TFibreSpec >
199 inline FibreRecord& getRecord(Bundle<TBundleSpec> &bundle, TFibreSpec const) {
200 unsigned id = (unsigned)_ClassIdentifier<TFibreSpec>::getID();
202 typename Bundle<TBundleSpec>::TFibreRecords::iterator first = lower_bound(bundle.fibres.begin(), bundle.fibres.end(), id, FibreLess());
203 if (!first->id != id) {
208 bundle.fibres.insert(first, rec);
213 template < typename TBundleSpec, typename TFibreSpec >
214 inline typename Fibre<Bundle<TBundleSpec>, TFibreSpec>::Type & getFibre(Bundle<TBundleSpec> &bundle, TFibreSpec const) {
215 typedef typename Fibre<Bundle<TBundleSpec>, TFibreSpec>::Type Type;
216 unsigned id = (unsigned)_ClassIdentifier<TFibreSpec>::getID();
218 FibreRecord &rec = getRecord(bundle, TFibreSpec());
220 rec.ptr = new Type();
221 return *reinterpret_cast<Type*>(rec.ptr);
224 template < typename TBundleSpec, typename TFibreSpec >
225 inline typename Fibre<Bundle<TBundleSpec>, TFibreSpec>::Type const & getFibre(Bundle<TBundleSpec> const &bundle, TFibreSpec const) {
226 typedef typename Fibre<Bundle<TBundleSpec>, TFibreSpec>::Type Type;
227 unsigned id = (unsigned)_ClassIdentifier<TFibreSpec>::getID();
229 FibreRecord &rec = getRecord(bundle, TFibreSpec());
230 return *reinterpret_cast<Type*>(rec.ptr);
234 //////////////////////////////////////////////////////////////////////////////
235 // various fibre specs for enhanced suffix arrays
237 struct _Fibre_Text; // Original text. Can be a String or a StringSet
238 struct _Fibre_RawText; // Concatenation of the strings above
239 struct _Fibre_SA; // suffix array (of raw text with virtual $-delimiters) with Pair entries
240 struct _Fibre_RawSA; // suffix array with integer entries
241 struct _Fibre_SAE; // suffix array reordered in a b-tree
242 struct _Fibre_LCP; // lcp table of raw text
243 struct _Fibre_LCPE; // lcp interval tree
244 struct _Fibre_ChildTab; // childtab (Kurtz et al.) of raw text
245 struct _Fibre_BWT; // burrows wheeler table of raw text
247 typedef Tag<_Fibre_Text> const Fibre_Text;
248 typedef Tag<_Fibre_RawText> const Fibre_RawText;
249 typedef Tag<_Fibre_SA> const Fibre_SA;
250 typedef Tag<_Fibre_RawSA> const Fibre_RawSA;
251 typedef Tag<_Fibre_SAE> const Fibre_SAE;
252 typedef Tag<_Fibre_LCP> const Fibre_LCP;
253 typedef Tag<_Fibre_LCPE> const Fibre_LCPE;
254 typedef Tag<_Fibre_ChildTab> const Fibre_ChildTab;
255 typedef Tag<_Fibre_BWT> const Fibre_BWT;
257 //////////////////////////////////////////////////////////////////////////////
260 .Metafunction.SAValue:
262 ..summary:The default alphabet type of a suffix array, i.e. the type to store a position of a string or string set.
263 ..signature:SAValue<TObject>::Type
264 ..param.TObject:A string, string set, or index type.
266 ...type:Class.StringSet
268 ..returns:A type to store a position.
269 ...text:If $TObject$ is a @Class.String@, it is a single integer value. By default this is the @Metafunction.Size@ type of $TObject$.
270 ...text:If $TObject$ is a @Class.StringSet@, it could be a single integer too (called global position, see @Spec.ConcatDirect@) or a @Class.Pair@ (called local position, see @Spec.Owner@).
271 Currently SeqAn defaults to a local position for @Class.StringSet@ classes (index_base.h):
272 ...code:template < typename TString, typename TSpec >
273 struct SAValue< StringSet<TString, TSpec> > {
275 typename Size< StringSet<TString, TSpec> >::Type,
276 typename SAValue<TString>::Type,
280 ..note:SAValue is the return type of various function, e.g. @Function.position@ for the @Class.Index@ @Class.Finder@ class, @Function.getOccurrence@, @Function.getOccurrences@ etc.
281 You should always use the type of this meta-function to store the return values.
282 If you want to write algorithms for both variants (local and global positions) you
283 should use the functions @Function.posLocalize@, @Function.posGlobalize@, @Function.getSeqNo@ and @Function.getSeqOffset@.
284 ..note:If $TObject$ is an @Class.Index@, @Metafunction.Position@ returns the same value as $SAValue$. You can change the position type of an index by overloading $SAValue$, not @Metafunction.Position@.
286 template <typename TObject>
290 template <typename TObject>
291 struct SAValue<TObject const>:
294 // to speed up sequence number computation
295 // we use a pair of seqNo and localPosition
296 template < typename TString, typename TSpec >
297 struct SAValue< StringSet<TString, TSpec> > {
299 typename Size< StringSet<TString, TSpec> >::Type,
300 typename SAValue<TString>::Type,
306 template < typename TString, typename TSpec >
307 struct SAValue< StringSet<TString, TSpec> > {
309 typename Size< StringSet<TString, TSpec> >::Type,
310 typename SAValue<TString>::Type,
311 CutCompressed<4> // max. 4 sequences
312 > Type; // max. 2^30 characters each
315 template < typename TText, typename TSpec >
316 struct SAValue< Index<TText, TSpec> >:
319 template < typename TObject, typename TSpec >
320 struct DefaultIndexStringSpec< Index<TObject, TSpec> >:
321 DefaultIndexStringSpec<TObject> {};
323 //////////////////////////////////////////////////////////////////////////////
324 // value and size type of an index
326 template < typename TText, typename TSpec >
327 struct Value< Index<TText, TSpec> > {
328 typedef typename Value<
329 typename Fibre< Index<TText, TSpec>, Fibre_RawText>::Type
333 template < typename TText, typename TSpec >
334 struct Size< Index<TText, TSpec> > {
335 typedef typename Size<
336 typename Fibre< Index<TText, TSpec>, Fibre_RawText>::Type
340 template < typename TText, typename TSpec >
341 struct Position< Index<TText, TSpec> >:
342 SAValue< Index<TText, TSpec> > {};
344 //////////////////////////////////////////////////////////////////////////////
345 // default table type
347 template < typename TObject, typename TSpec, typename TFibre >
348 struct Fibre< Index<TObject, TSpec>, Tag<TFibre> const > {
350 typename Size< Index<TObject, TSpec> >::Type,
351 typename DefaultIndexStringSpec< Index<TObject, TSpec> >::Type
355 //////////////////////////////////////////////////////////////////////////////
358 template < typename TText, typename TSpec >
359 struct Fibre< Index<TText, TSpec>, Fibre_Text> {
363 //////////////////////////////////////////////////////////////////////////////
366 template < typename TText, typename TSpec >
367 struct Fibre< Index<TText, TSpec>, Fibre_RawText> {
368 typedef typename Concatenator<TText>::Type Type;
371 //////////////////////////////////////////////////////////////////////////////
374 template < typename TText, typename TSpec >
375 struct Fibre< Index<TText, TSpec>, Fibre_SA> {
377 typename SAValue< Index<TText, TSpec> >::Type,
378 typename DefaultIndexStringSpec< Index<TText, TSpec> >::Type
382 //////////////////////////////////////////////////////////////////////////////
385 template <typename InType, typename TLimitsString, typename Result = typename Value<TLimitsString>::Type>
386 struct FunctorGlobalize : public ::std::unary_function<InType,Result> {
387 TLimitsString const *limits;
389 FunctorGlobalize() {}
390 FunctorGlobalize(TLimitsString const &_limits) : limits(&_limits) {}
391 inline Result operator()(const InType& x) const
393 return posGlobalize(x, *limits);
397 //////////////////////////////////////////////////////////////////////////////
398 // raw suffix array contains integer offsets relative to raw text
400 template < typename TString, typename TSSetSpec, typename TSpec >
401 struct Fibre< Index<StringSet<TString, TSSetSpec>, TSpec>, Fibre_RawSA>
403 typedef Index< StringSet<TString, TSSetSpec>, TSpec> TIndex;
404 // typedef ModifiedString<
405 // typename Fibre<TIndex, Fibre_SA>::Type,
406 // ModView< FunctorGlobalize<
407 // typename Value< typename Fibre<TIndex, Fibre_SA>::Type >::Type,
408 // typename StringSetLimits<StringSet<TString, TSSetSpec> >::Type >
413 //////////////////////////////////////////////////////////////////////////////
414 // default burrows-wheeler table
416 template < typename TText, typename TSpec >
417 struct Fibre< Index<TText, TSpec>, Fibre_BWT> {
419 typename Value< Index<TText, TSpec> >::Type,
420 typename DefaultIndexStringSpec< Index<TText, TSpec> >::Type
425 //////////////////////////////////////////////////////////////////////////////
426 // default fibre creators
428 template < typename TText, typename TSpec >
429 struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_SA> {
430 typedef Skew7 Type; // standard suffix array creator is skew7
433 template < typename TText, typename TSpec >
434 struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_LCP> {
438 template < typename TText, typename TSpec >
439 struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_BWT> {
443 template < typename TText, typename TSpec >
444 struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_ChildTab> {
445 typedef ChildTab Type;
449 //////////////////////////////////////////////////////////////////////////////
450 // fibre interface to access the enhanced suffix array tables
454 ..summary:Returns a specific @Metafunction.Fibre@ of an @Class.Index@ object.
456 ..signature:getFibre(index, fibre_tag)
457 ..param.index:The @Class.Index@ object holding the fibre.
459 ..param.fibre_tag:A tag that identifies the @Metafunction.Fibre@ (e.g. @Tag.ESA Index Fibres.ESA_SA@).
460 ..returns:A reference to the @Metafunction.Fibre@ object.
463 template <typename TText, typename TSpec>
464 inline Holder<TText> & _dataHost(Index<TText, TSpec> &index) {
467 template <typename TText, typename TSpec>
468 inline Holder<TText> const & _dataHost(Index<TText, TSpec> const &index) {
472 //////////////////////////////////////////////////////////////////////////////
474 template <typename TText, typename TSpec>
475 inline typename Fibre<Index<TText, TSpec>, Fibre_Text>::Type &
476 getFibre(Index<TText, TSpec> &index, Fibre_Text) {
477 return value(index.text);
479 template <typename TText, typename TSpec>
480 inline typename Fibre<Index<TText, TSpec> const, Fibre_Text>::Type &
481 getFibre(Index<TText, TSpec> const &index, Fibre_Text) {
482 return value(index.text);
485 //////////////////////////////////////////////////////////////////////////////
487 template <typename TText, typename TSpec>
488 inline typename Fibre<Index<TText, TSpec>, Fibre_RawText>::Type &
489 getFibre(Index<TText, TSpec> &index, Fibre_RawText) {
490 return concat(value(index.text));
492 template <typename TText, typename TSpec>
493 inline typename Fibre<Index<TText, TSpec> const, Fibre_RawText>::Type &
494 getFibre(Index<TText, TSpec> const &index, Fibre_RawText) {
495 return concat(value(index.text));
498 //////////////////////////////////////////////////////////////////////////////
500 template <typename TText, typename TSpec>
501 inline typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type &
502 getFibre(Index<TText, TSpec> &index, Fibre_SA) {
505 template <typename TText, typename TSpec>
506 inline typename Fibre<Index<TText, TSpec> const, Fibre_SA>::Type &
507 getFibre(Index<TText, TSpec> const &index, Fibre_SA) {
511 //////////////////////////////////////////////////////////////////////////////
513 template <typename TText, typename TSpec>
514 inline typename Fibre<Index<TText, TSpec> const, Fibre_SA>::Type &
515 getFibre(Index<TText, TSpec> &index, Fibre_RawSA) {
516 return indexSA(index);
519 template <typename TText, typename TSpec>
520 inline typename Fibre<Index<TText, TSpec> const, Fibre_SA>::Type &
521 getFibre(Index<TText, TSpec> const &index, Fibre_RawSA) {
522 return indexSA(index);
525 template <typename TString, typename TSSetSpec, typename TSpec>
526 inline typename Fibre<Index<StringSet<TString, TSSetSpec>, TSpec>, Fibre_RawSA>::Type
527 getFibre(Index<StringSet<TString, TSSetSpec>, TSpec> &index, Fibre_RawSA)
529 typedef Index< StringSet<TString, TSSetSpec>, TSpec> TIndex;
531 typedef FunctorGlobalize<
532 typename Value< typename Fibre<TIndex, Fibre_SA>::Type >::Type,
533 typename StringSetLimits<StringSet<TString, TSSetSpec> >::Type
536 // typedef ModifiedString<
537 // typename Fibre<Index<StringSet<TString, TSSetSpec>, TSpec>, Fibre_SA>::Type,
538 // ModView< TFunctor >
541 return ModString(indexSA(index), TFunctor(stringSetLimits(indexText(index))));
544 //////////////////////////////////////////////////////////////////////////////
546 template <typename TText, typename TSpec>
547 inline typename Fibre<Index<TText, TSpec>, Fibre_LCP>::Type &
548 getFibre(Index<TText, TSpec> &index, Fibre_LCP) {
551 template <typename TText, typename TSpec>
552 inline typename Fibre<Index<TText, TSpec> const, Fibre_LCP>::Type &
553 getFibre(Index<TText, TSpec> const &index, Fibre_LCP) {
557 //////////////////////////////////////////////////////////////////////////////
559 template <typename TText, typename TSpec>
560 inline typename Fibre<Index<TText, TSpec>, Fibre_LCPE>::Type &
561 getFibre(Index<TText, TSpec> &index, Fibre_LCPE) {
564 template <typename TText, typename TSpec>
565 inline typename Fibre<Index<TText, TSpec> const, Fibre_LCPE>::Type &
566 getFibre(Index<TText, TSpec> const &index, Fibre_LCPE) {
570 //////////////////////////////////////////////////////////////////////////////
572 template <typename TText, typename TSpec>
573 inline typename Fibre<Index<TText, TSpec>, Fibre_ChildTab>::Type &
574 getFibre(Index<TText, TSpec> &index, Fibre_ChildTab) {
575 return index.childtab;
577 template <typename TText, typename TSpec>
578 inline typename Fibre<Index<TText, TSpec> const, Fibre_ChildTab>::Type &
579 getFibre(Index<TText, TSpec> const &index, Fibre_ChildTab) {
580 return index.childtab;
583 //////////////////////////////////////////////////////////////////////////////
585 template <typename TText, typename TSpec>
586 inline typename Fibre<Index<TText, TSpec>, Fibre_BWT>::Type &
587 getFibre(Index<TText, TSpec> &index, Fibre_BWT) {
590 template <typename TText, typename TSpec>
591 inline typename Fibre<Index<TText, TSpec> const, Fibre_BWT>::Type &
592 getFibre(Index<TText, TSpec> const &index, Fibre_BWT) {
596 //////////////////////////////////////////////////////////////////////////////
597 ///.Function.length.param.object.type:Class.Index
599 template <typename TText, typename TSpec>
600 inline typename Size<Index<TText, TSpec> >::Type
601 length(Index<TText, TSpec> const &index) {
602 return length(indexRawText(index));
605 //////////////////////////////////////////////////////////////////////////////
607 template <typename TText, typename TSpec>
608 inline typename Size<TText>::Type
609 countSequences(Index<TText, TSpec> const &index) {
610 return countSequences(indexText(index));
613 //////////////////////////////////////////////////////////////////////////////
615 template <typename TSeqNo, typename TText, typename TSpec>
616 inline typename Size<Index<TText, TSpec> >::Type
617 sequenceLength(TSeqNo seqNo, Index<TText, TSpec> const &index) {
618 return sequenceLength(seqNo, indexText(index));
621 //////////////////////////////////////////////////////////////////////////////
623 template <typename TPos, typename TText, typename TSpec>
624 inline typename Size<Index<TText, TSpec> >::Type
625 suffixLength(TPos pos, Index<TText, TSpec> const &index) {
626 return sequenceLength(getSeqNo(pos, stringSetLimits(index)), index) - getSeqOffset(pos, stringSetLimits(index));
630 //////////////////////////////////////////////////////////////////////////////
631 // unified textAt interface
633 template <typename TPos, typename TIndex>
634 inline typename Reference<typename Fibre<TIndex, Fibre_RawText>::Type>::Type
635 textAt(TPos i, TIndex &index) {
636 return value(getFibre(index, Fibre_RawText()), i);
638 template <typename TPos, typename TString, typename TSSetSpec, typename TSpec>
639 inline typename Reference<typename Fibre< Index< StringSet<TString, TSSetSpec>, TSpec>, Fibre_RawText>::Type>::Type
640 textAt(TPos i, Index< StringSet<TString, TSSetSpec>, TSpec> &index) {
641 return value(getFibre(index, Fibre_RawText()), posGlobalize(i, stringSetLimits(index)));
643 template <typename TPos, typename TString, typename TSpec>
644 inline typename Reference<typename Fibre< Index< StringSet<TString, Owner<Default> >, TSpec>, Fibre_RawText>::Type>::Type
645 textAt(TPos i, Index< StringSet<TString, Owner<Default> >, TSpec> &index) {
647 typename Size< StringSet<TString, Owner<Default> > >::Type,
648 typename Size< TString >::Type > locPos;
649 posLocalize(locPos, i, stringSetLimits(index));
650 return value(value(getFibre(index, Fibre_Text()), getValueI1(locPos)), getValueI2(locPos));
653 //////////////////////////////////////////////////////////////////////////////
656 ..summary:Shortcut for $value(indexRawText(..), ..)$.
658 ..signature:rawtextAt(position, index)
659 ..param.position:A position in the array on which the value should be accessed.
660 ..param.index:The @Class.Index@ object holding the fibre.
661 ...type:Spec.Index_ESA
662 ..returns:A reference or proxy to the value.
665 template <typename TPos, typename TIndex>
666 inline typename Reference<typename Fibre<TIndex, Fibre_RawText>::Type>::Type rawtextAt(TPos i, TIndex &index) {
667 return value(getFibre(index, Fibre_RawText()), i);
669 template <typename TPos, typename TIndex>
670 inline typename Reference<typename Fibre<TIndex const, Fibre_RawText>::Type>::Type rawtextAt(TPos i, TIndex const &index) {
671 return value(getFibre(index, Fibre_RawText()), i);
674 //////////////////////////////////////////////////////////////////////////////
677 ..summary:Shortcut for $value(indexSA(..), ..)$.
679 ..signature:saAt(position, index)
680 ..param.position:A position in the array on which the value should be accessed.
681 ..param.index:The @Class.Index@ object holding the fibre.
682 ...type:Spec.Index_ESA
683 ..returns:A reference or proxy to the value.
686 template <typename TPos, typename TIndex>
687 inline typename Reference<typename Fibre<TIndex, Fibre_SA>::Type>::Type saAt(TPos i, TIndex &index) {
688 return value(getFibre(index, Fibre_SA()), i);
690 template <typename TPos, typename TIndex>
691 inline typename Reference<typename Fibre<TIndex const, Fibre_SA>::Type>::Type saAt(TPos i, TIndex const &index) {
692 return value(getFibre(index, Fibre_SA()), i);
695 template <typename TPos, typename TIndex>
696 inline typename Value<typename Fibre<TIndex const, Fibre_RawSA>::Type>::Type rawsaAt(TPos i, TIndex const &index) {
697 return posGlobalize(saAt(i, index), stringSetLimits(indexText(index)));
701 //////////////////////////////////////////////////////////////////////////////
704 ..summary:Shortcut for $value(indexLCP(..), ..)$.
706 ..signature:lcpAt(position, index)
707 ..param.position:A position in the array on which the value should be accessed.
708 ..param.index:The @Class.Index@ object holding the fibre.
709 ...type:Spec.Index_ESA
710 ..returns:A reference or proxy to the value.
713 template <typename TPos, typename TIndex>
714 inline typename Reference<typename Fibre<TIndex, Fibre_LCP>::Type>::Type lcpAt(TPos i, TIndex &index) {
715 return value(getFibre(index, Fibre_LCP()), i);
717 template <typename TPos, typename TIndex>
718 inline typename Reference<typename Fibre<TIndex const, Fibre_LCP>::Type>::Type lcpAt(TPos i, TIndex const &index) {
719 return value(getFibre(index, Fibre_LCP()), i);
722 //////////////////////////////////////////////////////////////////////////////
725 ..summary:Shortcut for $value(indexLCPE(..), ..)$.
727 ..signature:lcpeAt(position, index)
728 ..param.position:A position in the array on which the value should be accessed.
729 ..param.index:The @Class.Index@ object holding the fibre.
730 ...type:Spec.Index_ESA
731 ..returns:A reference or proxy to the value.
734 template <typename TPos, typename TIndex>
735 inline typename Reference<typename Fibre<TIndex, Fibre_LCPE>::Type>::Type lcpeAt(TPos i, TIndex &index) {
736 return value(getFibre(index, Fibre_LCPE()), i);
738 template <typename TPos, typename TIndex>
739 inline typename Reference<typename Fibre<TIndex const, Fibre_LCPE>::Type>::Type lcpeAt(TPos i, TIndex const &index) {
740 return value(getFibre(index, Fibre_LCPE()), i);
743 //////////////////////////////////////////////////////////////////////////////
746 ..summary:Shortcut for $value(indexChildTab(..), ..)$.
748 ..signature:childAt(position, index)
749 ..param.position:A position in the array on which the value should be accessed.
750 ..param.index:The @Class.Index@ object holding the fibre.
751 ...type:Spec.Index_ESA
752 ..returns:A reference or proxy to the value.
755 template <typename TPos, typename TIndex>
756 inline typename Reference<typename Fibre<TIndex, Fibre_ChildTab>::Type>::Type childAt(TPos i, TIndex &index) {
757 return value(getFibre(index, Fibre_ChildTab()), i);
759 template <typename TPos, typename TIndex>
760 inline typename Reference<typename Fibre<TIndex const, Fibre_ChildTab>::Type>::Type childAt(TPos i, TIndex const &index) {
761 return value(getFibre(index, Fibre_ChildTab()), i);
764 //////////////////////////////////////////////////////////////////////////////
767 ..summary:Shortcut for $value(indexBWT(..), ..)$.
769 ..signature:bwtAt(position, index)
770 ..param.position:A position in the array on which the value should be accessed.
771 ..param.index:The @Class.Index@ object holding the fibre.
772 ...type:Spec.Index_ESA
773 ..returns:A reference or proxy to the value.
776 template <typename TPos, typename TIndex>
777 inline typename Reference<typename Fibre<TIndex, Fibre_BWT>::Type>::Type bwtAt(TPos i, TIndex &index) {
778 return value(getFibre(index, Fibre_BWT()), i);
780 template <typename TPos, typename TIndex>
781 inline typename Reference<typename Fibre<TIndex const, Fibre_BWT>::Type>::Type bwtAt(TPos i, TIndex const &index) {
782 return value(getFibre(index, Fibre_BWT()), i);
785 //////////////////////////////////////////////////////////////////////////////
786 // interface for infinity/invalid values
788 template <typename TValue>
789 inline void _setSizeInval(TValue &v) {
790 v = SupremumValue<TValue>::VALUE;
793 template <typename TValue>
794 inline bool _isSizeInval(TValue const &v) {
795 return v == SupremumValue<TValue>::VALUE;
798 //////////////////////////////////////////////////////////////////////////////
801 ..summary:Shortcut for $getFibre(.., ESA_Text)$.
803 ..signature:indexText(index)
804 ..param.index:The @Class.Index@ object holding the fibre.
805 ...type:Spec.Index_ESA
806 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_Text@ fibre (original text).
809 template <typename TText, typename TSpec>
810 inline typename Fibre<Index<TText, TSpec>, Fibre_Text>::Type & indexText(Index<TText, TSpec> &index) { return getFibre(index, Fibre_Text()); }
811 template <typename TText, typename TSpec>
812 inline typename Fibre<Index<TText, TSpec> const, Fibre_Text>::Type & indexText(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_Text()); }
814 //////////////////////////////////////////////////////////////////////////////
816 template <typename TText, typename TSpec>
817 inline typename StringSetLimits<TText const>::Type
818 stringSetLimits(Index<TText, TSpec> &) {
822 template <typename TText, typename TSpec>
823 inline typename StringSetLimits<TText const>::Type
824 stringSetLimits(Index<TText, TSpec> const &) {
828 template <typename TString, typename TSSetSpec, typename TSpec>
829 inline typename StringSetLimits< StringSet<TString, TSSetSpec> const >::Type &
830 stringSetLimits(Index<StringSet<TString, TSSetSpec>, TSpec> &index) {
831 return stringSetLimits(indexText(index));
834 template <typename TString, typename TSSetSpec, typename TSpec>
835 inline typename StringSetLimits< StringSet<TString, TSSetSpec> const >::Type &
836 stringSetLimits(Index<StringSet<TString, TSSetSpec>, TSpec> const &index) {
837 return stringSetLimits(indexText(index));
840 //////////////////////////////////////////////////////////////////////////////
842 .Function.indexRawText:
843 ..summary:Shortcut for $getFibre(.., ESA_RawText)$.
845 ..signature:indexRawText(index)
846 ..param.index:The @Class.Index@ object holding the fibre.
847 ...type:Spec.Index_ESA
848 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_RawText@ fibre (concatenated input text).
851 template <typename TText, typename TSpec>
852 inline typename Fibre<Index<TText, TSpec>, Fibre_RawText>::Type & indexRawText(Index<TText, TSpec> &index) { return getFibre(index, Fibre_RawText()); }
853 template <typename TText, typename TSpec>
854 inline typename Fibre<Index<TText, TSpec> const, Fibre_RawText>::Type & indexRawText(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_RawText()); }
856 //////////////////////////////////////////////////////////////////////////////
859 ..summary:Shortcut for $getFibre(.., ESA_SA)$.
861 ..signature:indexSA(index)
862 ..param.index:The @Class.Index@ object holding the fibre.
863 ...type:Spec.Index_ESA
864 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_SA@ fibre (suffix array).
867 template <typename TText, typename TSpec>
868 inline typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type & indexSA(Index<TText, TSpec> &index) { return getFibre(index, Fibre_SA()); }
869 template <typename TText, typename TSpec>
870 inline typename Fibre<Index<TText, TSpec> const, Fibre_SA>::Type & indexSA(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_SA()); }
872 //////////////////////////////////////////////////////////////////////////////
874 .Function.indexRawSA:
875 ..summary:Shortcut for $getFibre(.., ESA_RawSA)$.
877 ..signature:indexRawSA(index)
878 ..param.index:The @Class.Index@ object holding the fibre.
879 ...type:Spec.Index_ESA
880 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_RawSA@ fibre (suffix array).
883 template <typename TText, typename TSpec>
884 inline typename Fibre<Index<TText, TSpec>, Fibre_RawSA>::Type indexRawSA(Index<TText, TSpec> &index) { return getFibre(index, Fibre_RawSA()); }
885 template <typename TText, typename TSpec>
886 inline typename Fibre<Index<TText, TSpec> const, Fibre_RawSA>::Type indexRawSA(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_RawSA()); }
888 //////////////////////////////////////////////////////////////////////////////
891 ..summary:Shortcut for $getFibre(.., ESA_LCP)$.
893 ..signature:indexLCP(index)
894 ..param.index:The @Class.Index@ object holding the fibre.
895 ...type:Spec.Index_ESA
896 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_LCP@ fibre (lcp table).
899 template <typename TText, typename TSpec>
900 inline typename Fibre<Index<TText, TSpec>, Fibre_LCP>::Type & indexLCP(Index<TText, TSpec> &index) { return getFibre(index, Fibre_LCP()); }
901 template <typename TText, typename TSpec>
902 inline typename Fibre<Index<TText, TSpec> const, Fibre_LCP>::Type & indexLCP(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_LCP()); }
904 //////////////////////////////////////////////////////////////////////////////
907 ..summary:Shortcut for $getFibre(.., ESA_LCPE)$.
909 ..signature:indexLCPE(index)
910 ..param.index:The @Class.Index@ object holding the fibre.
911 ...type:Spec.Index_ESA
912 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_LCPE@ fibre (enhanced lcp table).
915 template <typename TText, typename TSpec>
916 inline typename Fibre<Index<TText, TSpec>, Fibre_LCPE>::Type & indexLCPE(Index<TText, TSpec> &index) { return getFibre(index, Fibre_LCPE()); }
917 template <typename TText, typename TSpec>
918 inline typename Fibre<Index<TText, TSpec> const, Fibre_LCPE>::Type & indexLCPE(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_LCPE()); }
920 //////////////////////////////////////////////////////////////////////////////
923 ..summary:Shortcut for $getFibre(.., ESA_BWT)$.
925 ..signature:indexBWT(index)
926 ..param.index:The @Class.Index@ object holding the fibre.
927 ...type:Spec.Index_ESA
928 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_BWT@ fibre (Burrows-Wheeler table).
931 template <typename TText, typename TSpec>
932 inline typename Fibre<Index<TText, TSpec>, Fibre_BWT>::Type & indexBWT(Index<TText, TSpec> &index) { return getFibre(index, Fibre_BWT()); }
933 template <typename TText, typename TSpec>
934 inline typename Fibre<Index<TText, TSpec> const, Fibre_BWT>::Type & indexBWT(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_BWT()); }
936 //////////////////////////////////////////////////////////////////////////////
938 .Function.indexChildTab:
939 ..summary:Shortcut for $getFibre(.., ESA_ChildTab)$.
941 ..signature:indexChildTab(index)
942 ..param.index:The @Class.Index@ object holding the fibre.
943 ...type:Spec.Index_ESA
944 ..returns:A reference to the @Tag.ESA Index Fibres.ESA_ChildTab@ fibre (child table).
947 template <typename TText, typename TSpec>
948 inline typename Fibre<Index<TText, TSpec>, Fibre_ChildTab>::Type & indexChildTab(Index<TText, TSpec> &index) { return getFibre(index, Fibre_ChildTab()); }
949 template <typename TText, typename TSpec>
950 inline typename Fibre<Index<TText, TSpec> const, Fibre_ChildTab>::Type & indexChildTab(Index<TText, TSpec> const &index) { return getFibre(index, Fibre_ChildTab()); }