SeqAn-1.1/seqan/index/index_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: index_base.h,v 1.3 2009/03/13 14:34:32 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_INDEX_BASE_H
  22 #define SEQAN_HEADER_INDEX_BASE_H
  23
  24 //#define SEQAN_TEST_INDEX
  25
  26 namespace SEQAN_NAMESPACE_MAIN
  27 {
  28
  29 //////////////////////////////////////////////////////////////////////////////
  30 // needful forward declarations
  31
  32         // suffix array construction specs
  33         struct Skew3;
  34         struct Skew7;
  35         struct LarssonSadakane;
  36         struct ManberMyers;
  37         struct SAQSort;
  38         struct QGram_Alg;
  39
  40         // lcp table construction algorithms
  41         struct Kasai;
  42         struct KasaiOriginal;   // original, but more space-consuming algorithm
  43
  44         // enhanced suffix array construction algorithms
  45         struct ChildTab;
  46         struct BWT;
  47
  48         template <typename TSpec = void>
  49         struct Index_ESA;
  50
  51
  52 //////////////////////////////////////////////////////////////////////////////
  53 /**
  54 .Metafunction.DefaultIndexSpec:
  55 ..cat:Index
  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@.
  61 */
  62     template < typename TObject >
  63     struct DefaultIndexSpec {
  64         typedef Index_ESA<> Type;
  65     };
  66
  67 //////////////////////////////////////////////////////////////////////////////
  68 /**
  69 .Metafunction.DefaultIndexStringSpec:
  70 ..cat:Index
  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.
  76 */
  77     template < typename TIndex >
  78     struct DefaultIndexStringSpec {
  79         typedef Alloc<> Type;
  80     };
  81
  82 //    template < typename TValue, typename TSpec >
  83 //    struct DefaultIndexStringSpec< String<TValue, External<TSpec> > > {
  84 //        typedef External<TSpec> Type;
  85 //    };
  86
  87         template < typename TString, typename TSpec >
  88         struct DefaultIndexStringSpec< StringSet<TString, TSpec> >:
  89                 DefaultIndexStringSpec<TString> {};
  90
  91
  92 //////////////////////////////////////////////////////////////////////////////
  93 /**
  94 .Class.Index:
  95 ..summary:Contains preprocessing data of a fixed text. Allows fast dictionary look-up and advanced computations.
  96 ..cat:Index
  97 ..signature:Index<TText[, TSpec]>
  98 ..param.TText:The text type.
  99 ...type:Class.String
 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.
 106 */
 107
 108 ///.Function.setHaystack.param.haystack.type:Class.Index
 109
 110         // index as a haystack
 111         template <
 112         typename TObject,
 113         typename TSpec = typename DefaultIndexSpec<TObject>::Type >
 114         class Index;
 115
 116         template <typename TObject, typename TSpec>
 117         struct Host< Index<TObject, TSpec> > {
 118                 typedef TObject Type;
 119         };
 120
 121         template <typename TObject, typename TSpec>
 122         struct Spec< Index<TObject, TSpec> > {
 123                 typedef TSpec Type;
 124         };
 125
 126
 127 //////////////////////////////////////////////////////////////////////////////
 128 /**
 129 .Metafunction.Fibre:
 130 ..summary:Type of a specific bundle member (fibre).
 131 ..signature:Fibre<TIndex, TSpec>::Type
 132 ..cat:Index
 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@).
 138 */
 139         // meta function to get the type of a bundle fibre
 140         template < typename TIndex, typename TSpec >
 141         struct Fibre {
 142                 typedef String< typename Size<TIndex>::Type > Type;
 143         };
 144
 145         template < typename TIndex, typename TSpec >
 146         struct Fibre<TIndex const, TSpec> {
 147                 typedef typename Fibre<TIndex, TSpec>::Type const Type;
 148         };
 149
 150         struct FibreRecord {
 151                 unsigned        id;
 152                 void*           ptr;
 153                 bool            owner;
 154         };
 155
 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);
 162                 }
 163         };
 164
 165 //////////////////////////////////////////////////////////////////////////////
 166 /**
 167 .Metafunction.DefaultIndexCreator:
 168 ..cat:Index
 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.
 174 */
 175     // standard algorithm for indices creation
 176     template < typename TIndex, typename TFibre >
 177         struct DefaultIndexCreator {
 178                 typedef Default Type;
 179         };
 180
 181 //////////////////////////////////////////////////////////////////////////////
 182 /**
 183         .Class.Bundle:
 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@.
 190 */
 191 /*
 192         template < typename TSpec = void >
 193         struct Bundle {
 194                 typedef ::std::vector<FibreRecord>      TFibreRecords;
 195                 TFibreRecords                                           fibres;
 196         };
 197
 198         template < typename TBundleSpec, typename TFibreSpec >
 199         inline FibreRecord& getRecord(Bundle<TBundleSpec> &bundle, TFibreSpec const) {
 200                 unsigned id = (unsigned)_ClassIdentifier<TFibreSpec>::getID();
 201
 202                 typename Bundle<TBundleSpec>::TFibreRecords::iterator first = lower_bound(bundle.fibres.begin(), bundle.fibres.end(), id, FibreLess());
 203                 if (!first->id != id) {
 204                         FibreRecord rec;
 205                         rec.id = id;
 206                         rec.ptr = NULL;
 207                         rec.owner = true;
 208                         bundle.fibres.insert(first, rec);
 209                 } else
 210                         return *first;
 211         }
 212
 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();
 217
 218                 FibreRecord &rec = getRecord(bundle, TFibreSpec());
 219                 if (!rec.ptr)
 220                         rec.ptr = new Type();
 221                 return *reinterpret_cast<Type*>(rec.ptr);
 222         }
 223
 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();
 228
 229                 FibreRecord &rec = getRecord(bundle, TFibreSpec());
 230                 return *reinterpret_cast<Type*>(rec.ptr);
 231         }
 232 */
 233
 234 //////////////////////////////////////////////////////////////////////////////
 235 // various fibre specs for enhanced suffix arrays
 236
 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
 246
 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;
 256
 257 //////////////////////////////////////////////////////////////////////////////
 258
 259 /**
 260 .Metafunction.SAValue:
 261 ..cat:Index
 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.
 265 ...type:Class.String
 266 ...type:Class.StringSet
 267 ...type:Class.Index
 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> > {
 274         typedef Pair<
 275                 typename Size< StringSet<TString, TSpec> >::Type,
 276                 typename SAValue<TString>::Type,
 277                 Compressed
 278         > Type;
 279 };
 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@.
 285 */
 286         template <typename TObject>
 287         struct SAValue:
 288                 Size<TObject> {};
 289
 290         template <typename TObject>
 291         struct SAValue<TObject const>:
 292                 SAValue<TObject> {};
 293
 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> > {
 298                 typedef Pair<
 299                         typename Size< StringSet<TString, TSpec> >::Type,
 300                         typename SAValue<TString>::Type,
 301                         Compressed
 302                 > Type;
 303         };
 304
 305 /*
 306         template < typename TString, typename TSpec >
 307         struct SAValue< StringSet<TString, TSpec> > {
 308                 typedef Pair<
 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
 313         };
 314 */
 315         template < typename TText, typename TSpec >
 316         struct SAValue< Index<TText, TSpec> >:
 317                 SAValue<TText> {};
 318
 319         template < typename TObject, typename TSpec >
 320         struct DefaultIndexStringSpec< Index<TObject, TSpec> >:
 321                 DefaultIndexStringSpec<TObject> {};
 322
 323 //////////////////////////////////////////////////////////////////////////////
 324 // value and size type of an index
 325
 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
 330                 >::Type Type;
 331     };
 332
 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
 337                 >::Type Type;
 338     };
 339
 340         template < typename TText, typename TSpec >
 341         struct Position< Index<TText, TSpec> >:
 342                 SAValue< Index<TText, TSpec> > {};
 343
 344 //////////////////////////////////////////////////////////////////////////////
 345 // default table type
 346
 347         template < typename TObject, typename TSpec, typename TFibre >
 348         struct Fibre< Index<TObject, TSpec>, Tag<TFibre> const > {
 349                 typedef String<
 350                         typename Size< Index<TObject, TSpec> >::Type,
 351                         typename DefaultIndexStringSpec< Index<TObject, TSpec> >::Type
 352                 > Type;
 353         };
 354
 355 //////////////////////////////////////////////////////////////////////////////
 356 // original text
 357
 358         template < typename TText, typename TSpec >
 359         struct Fibre< Index<TText, TSpec>, Fibre_Text> {
 360                 typedef TText Type;
 361         };
 362
 363 //////////////////////////////////////////////////////////////////////////////
 364 // concatenated text
 365
 366         template < typename TText, typename TSpec >
 367         struct Fibre< Index<TText, TSpec>, Fibre_RawText> {
 368                 typedef typename Concatenator<TText>::Type Type;
 369         };
 370
 371 //////////////////////////////////////////////////////////////////////////////
 372 // suffix array type
 373
 374         template < typename TText, typename TSpec >
 375         struct Fibre< Index<TText, TSpec>, Fibre_SA> {
 376                 typedef String<
 377                         typename SAValue< Index<TText, TSpec> >::Type,
 378                         typename DefaultIndexStringSpec< Index<TText, TSpec> >::Type
 379                 > Type;
 380         };
 381
 382 //////////////////////////////////////////////////////////////////////////////
 383 // globalize functor
 384
 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;
 388
 389                 FunctorGlobalize() {}
 390                 FunctorGlobalize(TLimitsString const &_limits) : limits(&_limits) {}
 391         inline Result operator()(const InType& x) const
 392         {
 393                         return posGlobalize(x, *limits);
 394                 }
 395     };
 396
 397 //////////////////////////////////////////////////////////////////////////////
 398 // raw suffix array contains integer offsets relative to raw text
 399
 400         template < typename TString, typename TSSetSpec, typename TSpec >
 401         struct Fibre< Index<StringSet<TString, TSSetSpec>, TSpec>, Fibre_RawSA>
 402         {
 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 >
 409 //                      >
 410 //              > Type;
 411         };
 412
 413 //////////////////////////////////////////////////////////////////////////////
 414 // default burrows-wheeler table
 415
 416         template < typename TText, typename TSpec >
 417         struct Fibre< Index<TText, TSpec>, Fibre_BWT> {
 418                 typedef String <
 419                         typename Value< Index<TText, TSpec> >::Type,
 420                         typename DefaultIndexStringSpec< Index<TText, TSpec> >::Type
 421                 > Type;
 422         };
 423
 424
 425 //////////////////////////////////////////////////////////////////////////////
 426 // default fibre creators
 427
 428         template < typename TText, typename TSpec >
 429         struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_SA> {
 430         typedef Skew7 Type;                                                     // standard suffix array creator is skew7
 431     };
 432
 433         template < typename TText, typename TSpec >
 434         struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_LCP> {
 435         typedef Kasai Type;
 436     };
 437
 438         template < typename TText, typename TSpec >
 439         struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_BWT> {
 440         typedef BWT Type;
 441     };
 442
 443         template < typename TText, typename TSpec >
 444         struct DefaultIndexCreator<Index<TText, TSpec>, Fibre_ChildTab> {
 445         typedef ChildTab Type;
 446     };
 447
 448
 449 //////////////////////////////////////////////////////////////////////////////
 450 // fibre interface to access the enhanced suffix array tables
 451
 452 /**
 453 .Function.getFibre:
 454 ..summary:Returns a specific @Metafunction.Fibre@ of an @Class.Index@ object.
 455 ..cat:Index
 456 ..signature:getFibre(index, fibre_tag)
 457 ..param.index:The @Class.Index@ object holding the fibre.
 458 ...type:Class.Index
 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.
 461 */
 462
 463         template <typename TText, typename TSpec>
 464         inline Holder<TText> & _dataHost(Index<TText, TSpec> &index) {
 465                 return index.text;
 466         }
 467         template <typename TText, typename TSpec>
 468         inline Holder<TText> const & _dataHost(Index<TText, TSpec> const &index) {
 469                 return index.text;
 470         }
 471
 472 //////////////////////////////////////////////////////////////////////////////
 473
 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);
 478         }
 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);
 483         }
 484
 485 //////////////////////////////////////////////////////////////////////////////
 486
 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));
 491         }
 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));
 496         }
 497
 498 //////////////////////////////////////////////////////////////////////////////
 499
 500         template <typename TText, typename TSpec>
 501         inline typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type &
 502         getFibre(Index<TText, TSpec> &index, Fibre_SA) {
 503                 return index.sa;
 504         }
 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) {
 508                 return index.sa;
 509         }
 510
 511 //////////////////////////////////////////////////////////////////////////////
 512
 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);
 517         }
 518 /*
 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);
 523         }
 524 */
 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)
 528         {
 529                 typedef Index< StringSet<TString, TSSetSpec>, TSpec> TIndex;
 530
 531                 typedef FunctorGlobalize<
 532                         typename Value< typename Fibre<TIndex, Fibre_SA>::Type >::Type,
 533                         typename StringSetLimits<StringSet<TString, TSSetSpec> >::Type
 534                 > TFunctor;
 535
 536 //              typedef ModifiedString<
 537 //                      typename Fibre<Index<StringSet<TString, TSSetSpec>, TSpec>, Fibre_SA>::Type,
 538 //                      ModView< TFunctor >
 539 //              > ModString;
 540
 541                 return ModString(indexSA(index), TFunctor(stringSetLimits(indexText(index))));
 542         }
 543
 544 //////////////////////////////////////////////////////////////////////////////
 545
 546         template <typename TText, typename TSpec>
 547         inline typename Fibre<Index<TText, TSpec>, Fibre_LCP>::Type &
 548         getFibre(Index<TText, TSpec> &index, Fibre_LCP) {
 549                 return index.lcp;
 550         }
 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) {
 554                 return index.lcp;
 555         }
 556
 557 //////////////////////////////////////////////////////////////////////////////
 558
 559         template <typename TText, typename TSpec>
 560         inline typename Fibre<Index<TText, TSpec>, Fibre_LCPE>::Type &
 561         getFibre(Index<TText, TSpec> &index, Fibre_LCPE) {
 562                 return index.lcpe;
 563         }
 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) {
 567                 return index.lcpe;
 568         }
 569
 570 //////////////////////////////////////////////////////////////////////////////
 571
 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;
 576         }
 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;
 581         }
 582
 583 //////////////////////////////////////////////////////////////////////////////
 584
 585         template <typename TText, typename TSpec>
 586         inline typename Fibre<Index<TText, TSpec>, Fibre_BWT>::Type &
 587         getFibre(Index<TText, TSpec> &index, Fibre_BWT) {
 588                 return index.bwt;
 589         }
 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) {
 593                 return index.bwt;
 594         }
 595
 596 //////////////////////////////////////////////////////////////////////////////
 597 ///.Function.length.param.object.type:Class.Index
 598
 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));
 603         }
 604
 605 //////////////////////////////////////////////////////////////////////////////
 606
 607         template <typename TText, typename TSpec>
 608         inline typename Size<TText>::Type
 609         countSequences(Index<TText, TSpec> const &index) {
 610                 return countSequences(indexText(index));
 611         }
 612
 613 //////////////////////////////////////////////////////////////////////////////
 614
 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));
 619         }
 620
 621 //////////////////////////////////////////////////////////////////////////////
 622
 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));
 627         }
 628
 629
 630 //////////////////////////////////////////////////////////////////////////////
 631 // unified textAt interface
 632
 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);
 637         }
 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)));
 642         }
 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) {
 646                 Pair <
 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));
 651         }
 652
 653 //////////////////////////////////////////////////////////////////////////////
 654 /**
 655 .Function.rawtextAt:
 656 ..summary:Shortcut for $value(indexRawText(..), ..)$.
 657 ..cat:Index
 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.
 663 */
 664
 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);
 668         }
 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);
 672         }
 673
 674 //////////////////////////////////////////////////////////////////////////////
 675 /**
 676 .Function.saAt:
 677 ..summary:Shortcut for $value(indexSA(..), ..)$.
 678 ..cat:Index
 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.
 684 */
 685
 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);
 689         }
 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);
 693         }
 694
 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)));
 698         }
 699
 700
 701 //////////////////////////////////////////////////////////////////////////////
 702 /**
 703 .Function.lcpAt:
 704 ..summary:Shortcut for $value(indexLCP(..), ..)$.
 705 ..cat:Index
 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.
 711 */
 712
 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);
 716         }
 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);
 720         }
 721
 722 //////////////////////////////////////////////////////////////////////////////
 723 /**
 724 .Function.lcpeAt:
 725 ..summary:Shortcut for $value(indexLCPE(..), ..)$.
 726 ..cat:Index
 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.
 732 */
 733
 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);
 737         }
 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);
 741         }
 742
 743 //////////////////////////////////////////////////////////////////////////////
 744 /**
 745 .Function.childAt:
 746 ..summary:Shortcut for $value(indexChildTab(..), ..)$.
 747 ..cat:Index
 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.
 753 */
 754
 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);
 758         }
 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);
 762         }
 763
 764 //////////////////////////////////////////////////////////////////////////////
 765 /**
 766 .Function.bwtAt:
 767 ..summary:Shortcut for $value(indexBWT(..), ..)$.
 768 ..cat:Index
 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.
 774 */
 775
 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);
 779         }
 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);
 783         }
 784
 785 //////////////////////////////////////////////////////////////////////////////
 786 // interface for infinity/invalid values
 787
 788         template <typename TValue>
 789         inline void _setSizeInval(TValue &v) {
 790                 v = SupremumValue<TValue>::VALUE;
 791         }
 792
 793         template <typename TValue>
 794         inline bool _isSizeInval(TValue const &v) {
 795                 return v == SupremumValue<TValue>::VALUE;
 796         }
 797
 798 //////////////////////////////////////////////////////////////////////////////
 799 /**
 800 .Function.indexText:
 801 ..summary:Shortcut for $getFibre(.., ESA_Text)$.
 802 ..cat:Index
 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).
 807 */
 808
 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()); }
 813
 814 //////////////////////////////////////////////////////////////////////////////
 815
 816         template <typename TText, typename TSpec>
 817         inline typename StringSetLimits<TText const>::Type
 818         stringSetLimits(Index<TText, TSpec> &) {
 819                 return Nothing();
 820         }
 821
 822         template <typename TText, typename TSpec>
 823         inline typename StringSetLimits<TText const>::Type
 824         stringSetLimits(Index<TText, TSpec> const &) {
 825                 return Nothing();
 826         }
 827
 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));
 832         }
 833
 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));
 838         }
 839
 840 //////////////////////////////////////////////////////////////////////////////
 841 /**
 842 .Function.indexRawText:
 843 ..summary:Shortcut for $getFibre(.., ESA_RawText)$.
 844 ..cat:Index
 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).
 849 */
 850
 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()); }
 855
 856 //////////////////////////////////////////////////////////////////////////////
 857 /**
 858 .Function.indexSA:
 859 ..summary:Shortcut for $getFibre(.., ESA_SA)$.
 860 ..cat:Index
 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).
 865 */
 866
 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()); }
 871
 872 //////////////////////////////////////////////////////////////////////////////
 873 /**
 874 .Function.indexRawSA:
 875 ..summary:Shortcut for $getFibre(.., ESA_RawSA)$.
 876 ..cat:Index
 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).
 881 */
 882
 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()); }
 887
 888 //////////////////////////////////////////////////////////////////////////////
 889 /**
 890 .Function.indexLCP:
 891 ..summary:Shortcut for $getFibre(.., ESA_LCP)$.
 892 ..cat:Index
 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).
 897 */
 898
 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()); }
 903
 904 //////////////////////////////////////////////////////////////////////////////
 905 /**
 906 .Function.indexLCPE:
 907 ..summary:Shortcut for $getFibre(.., ESA_LCPE)$.
 908 ..cat:Index
 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).
 913 */
 914
 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()); }
 919
 920 //////////////////////////////////////////////////////////////////////////////
 921 /**
 922 .Function.indexBWT:
 923 ..summary:Shortcut for $getFibre(.., ESA_BWT)$.
 924 ..cat:Index
 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).
 929 */
 930
 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()); }
 935
 936 //////////////////////////////////////////////////////////////////////////////
 937 /**
 938 .Function.indexChildTab:
 939 ..summary:Shortcut for $getFibre(.., ESA_ChildTab)$.
 940 ..cat:Index
 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).
 945 */
 946
 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()); }
 951
 952 }
 953
 954 #endif