SeqAn-1.1/seqan/sequence/sequence_multiple.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: sequence_multiple.h,v 1.2 2009/02/19 01:51:23 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_STRING_SET_H
  22 #define SEQAN_HEADER_STRING_SET_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26
  27         //////////////////////////////////////////////////////////////////////////////
  28         // StringSet specs
  29         //////////////////////////////////////////////////////////////////////////////
  30
  31         //struct Generous;                                              // large string-string, large id-string
  32         //struct Tight;                                                 // small string-string, small id-string
  33         //struct Optimal??                                              // small string-string, large id-string
  34
  35 /**
  36 .Spec.Dependent:
  37 ..summary:A string set storing references of the strings.
  38 ..cat:Sequences
  39 ..general:Class.StringSet
  40 ..signature:StringSet<TString, Dependent<TSpec> >
  41 ..param.TString:The string type.
  42 ...type:Class.String
  43 ..param.TSpec:The specializing type for the dependent string set.
  44 ...remarks:Possible values are $Tight$ or $Generous$
  45 ...remarks:$Tight$ is very space efficient whereas $Generous$ provides fast access to the strings in the container via ids.
  46 */
  47
  48         // Default id holder string set
  49         template<typename TSpec = Generous >
  50         struct Dependent;                                               // holds references of its elements
  51
  52
  53 /**
  54 .Spec.ConcatDirect:
  55 ..summary:A string set storing the concatenation of all strings within one string.
  56 ..cat:Sequences
  57 ..general:Spec.Owner
  58 ..signature:StringSet<TString, Owner<ConcatDirect<> > >
  59 ..param.TString:The string type.
  60 ...type:Class.String
  61 ..remarks:The strings are internally stored in a $TString$ object and the character position type is a
  62 a single integer value between 0 and the sum of string lengths minus 1.
  63 ..remarks:The position type can be returned or modified by the meta-function @Metafunction.SAValue@ called with the @Class.StringSet@ type.
  64 */
  65
  66         template < typename TDelimiter = void >
  67         struct ConcatDirect;                                    // contains 1 string (the concatenation of n strings)
  68         //struct Default;                                                       // contains n strings in a string
  69
  70 /**
  71 .Spec.Owner:
  72 ..summary:A string set storing the strings as members.
  73 ..cat:Sequences
  74 ..general:Class.StringSet
  75 ..signature:StringSet<TString, Owner<> >
  76 ..signature:StringSet<TString, Owner<Default> >
  77 ..param.TString:The string type.
  78 ...type:Class.String
  79 ..remarks:The strings are internally stored in a $String<TString>$ object and the character position type is a
  80 @Class.Pair@ $(seqNo,seqOfs)$ where seqNo identifies the string within the stringset and seqOfs identifies the position within this string.
  81 ..remarks:The position type can be returned or modified by the meta-function @Metafunction.SAValue@ called with the @Class.StringSet@ type.
  82 */
  83         template < typename TSpec = Default >
  84         struct Owner;                                                   // owns its elements
  85
  86
  87     //////////////////////////////////////////////////////////////////////////////
  88         // Forwards
  89         //////////////////////////////////////////////////////////////////////////////
  90
  91         template < typename TString, typename TSpec = Owner<> >
  92         class StringSet;
  93
  94     template <typename TObject>
  95         struct Concatenator {
  96                 typedef TObject Type;
  97         };
  98
  99     template <typename TObject>
 100         struct Concatenator<TObject const> {
 101                 typedef typename Concatenator<TObject>::Type const Type;
 102         };
 103
 104
 105         //////////////////////////////////////////////////////////////////////////////
 106         // StringSet limits
 107         //////////////////////////////////////////////////////////////////////////////
 108
 109         template <typename TString>
 110         struct StringSetLimits {
 111                 typedef Nothing Type;
 112         };
 113
 114         template <typename TString>
 115         struct StringSetLimits<TString const> {
 116                 typedef typename StringSetLimits<TString>::Type const Type;
 117         };
 118
 119         template <typename TString>
 120         struct StringSetPosition {
 121                 typedef typename Size<TString>::Type    Type;
 122         };
 123
 124         template <typename TString, typename TSpec>
 125         struct StringSetLimits< StringSet<TString, TSpec> > {
 126                 typedef typename Size<TString>::Type    TSize;
 127                 typedef String<TSize>                                   Type;
 128         };
 129
 130         template <typename TString, typename TSpec>
 131         struct StringSetPosition< StringSet<TString, TSpec> > {
 132                 typedef typename Size<TString>::Type    TSize;
 133                 typedef Pair<TSize>                                             Type;
 134         };
 135
 136
 137
 138         //////////////////////////////////////////////////////////////////////////////
 139         // get StringSet limits
 140         //////////////////////////////////////////////////////////////////////////////
 141
 142 /**
 143 .Function.stringSetLimits:
 144 ..cat:Sequences
 145 ..summary:Retrieves a string of delimiter positions of a @Class.StringSet@ which is needed for local<->global position conversions.
 146 ..signature:stringSetLimits(me)
 147 ..param.me:A string or string set.
 148 ...type:Class.String
 149 ...type:Class.StringSet
 150 ..returns:A reference to a string.
 151 ...remarks:If $me$ is a @Class.StringSet@ then the returned string is of size $length(me)+1$ and contains the ascending (virtual) delimiter positions of the concatenation of all strings in the string set.
 152 ...remarks:If $me$ is a @Class.String@, @Tag.Nothing@ is returned.
 153 */
 154
 155     template <typename TStringSet>
 156         inline typename StringSetLimits<TStringSet>::Type
 157         stringSetLimits(TStringSet &) {
 158                 return typename StringSetLimits<TStringSet>::Type();
 159         }
 160
 161     template <typename TString, typename TSpec>
 162         inline typename StringSetLimits< StringSet<TString, TSpec> >::Type &
 163         stringSetLimits(StringSet<TString, TSpec> &stringSet) {
 164                 if (!_validStringSetLimits(stringSet))
 165                         _refreshStringSetLimits(stringSet);
 166                 return stringSet.limits;
 167         }
 168
 169     template <typename TString, typename TSpec>
 170         inline typename StringSetLimits< StringSet<TString, TSpec> const>::Type &
 171         stringSetLimits(StringSet<TString, TSpec> const &stringSet) {
 172                 if (!_validStringSetLimits(stringSet))
 173                         _refreshStringSetLimits(const_cast< StringSet<TString, TSpec>& >(stringSet));
 174                 return stringSet.limits;
 175         }
 176
 177         //////////////////////////////////////////////////////////////////////////////
 178         // accessing local positions
 179         //////////////////////////////////////////////////////////////////////////////
 180
 181 /**
 182 .Function.getSeqNo:
 183 ..cat:Sequences
 184 ..summary:Returns the sequence number of a position.
 185 ..signature:getSeqNo(pos[, limits])
 186 ..param.pos:A position.
 187 ...type:Class.Pair
 188 ..param.limits:The limits string returned by @Function.stringSetLimits@.
 189 ..returns:A single integer value that identifies the string within the stringset $pos$ points at.
 190 ...remarks:If $limits$ is omitted or @Tag.Nothing@ $getSeqNo$ returns 0.
 191 ...remarks:If $pos$ is a local position (of class @Class.Pair@) then $i1$ is returned.
 192 ...remarks:If $pos$ is a global position (integer type and $limits$ is a @Class.String@) then $pos$ is converted to a local position and $i1$ is returned.
 193 */
 194
 195 /**
 196 .Function.getSeqOffset:
 197 ..cat:Sequences
 198 ..summary:Returns the local sequence offset of a position.
 199 ..signature:getSeqOffset(pos[, limits])
 200 ..param.pos:A position.
 201 ...type:Class.Pair
 202 ..param.limits:The limits string returned by @Function.stringSetLimits@.
 203 ..returns:A single integer value that identifies the position within the string $pos$ points at.
 204 ...remarks:If $limits$ is omitted or @Tag.Nothing@ $getSeqNo$ returns $pos$.
 205 ...remarks:If $pos$ is a local position (of class @Class.Pair@) then $i2$ is returned.
 206 ...remarks:If $pos$ is a global position (integer type and $limits$ is a @Class.String@) then $pos$ is converted to a local position and $i2$ is returned.
 207 */
 208
 209         //////////////////////////////////////////////////////////////////////////////
 210         // 1 sequence
 211         //////////////////////////////////////////////////////////////////////////////
 212
 213         template <typename TPosition>
 214         inline TPosition getSeqNo(TPosition const &, Nothing const &) {
 215                 return 0;
 216         }
 217
 218         template <typename TPosition>
 219         inline TPosition getSeqOffset(TPosition const &pos, Nothing const &) {
 220                 return pos;
 221         }
 222 //____________________________________________________________________________
 223
 224         template <typename TPosition>
 225         inline TPosition getSeqNo(TPosition const &) {
 226                 return 0;
 227         }
 228
 229         template <typename TPosition>
 230         inline TPosition getSeqOffset(TPosition const &pos) {
 231                 return pos;
 232         }
 233
 234         //////////////////////////////////////////////////////////////////////////////
 235         // n sequences (position type is Pair)
 236         //////////////////////////////////////////////////////////////////////////////
 237
 238         template <typename T1, typename T2, typename TCompression, typename TLimitsString>
 239         inline T1 getSeqNo(Pair<T1, T2, TCompression> const &pos, TLimitsString const &) {
 240                 return getValueI1(pos);
 241         }
 242
 243         template <typename T1, typename T2, typename TCompression>
 244         inline T1 getSeqNo(Pair<T1, T2, TCompression> const &pos) {
 245                 return getValueI1(pos);
 246         }
 247 //____________________________________________________________________________
 248
 249         template <typename T1, typename T2, typename TCompression, typename TLimitsString>
 250         inline T2 getSeqOffset(Pair<T1, T2, TCompression> const &pos, TLimitsString const &) {
 251                 return getValueI2(pos);
 252         }
 253
 254         template <typename T1, typename T2, typename TCompression>
 255         inline T1 getSeqOffset(Pair<T1, T2, TCompression> const &pos) {
 256                 return getValueI2(pos);
 257         }
 258
 259         //////////////////////////////////////////////////////////////////////////////
 260         // n sequences (position type is an integral type)
 261         //////////////////////////////////////////////////////////////////////////////
 262
 263         template <typename TPos, typename TLimitsString>
 264         inline TPos getSeqNo(TPos const &pos, TLimitsString const &limits) {
 265                 typedef typename Iterator<TLimitsString const, Standard>::Type TIter;
 266                 typedef typename Value<TLimitsString>::Type TSize;
 267         TIter _begin = begin(limits, Standard());
 268         TIter _upper = ::std::upper_bound(_begin, end(limits, Standard()), (TSize)pos) - 1;
 269         return difference(_begin, _upper);
 270         }
 271
 272         template <typename TPos, typename TLimitsString>
 273         inline TPos getSeqOffset(TPos const &pos, TLimitsString const &limits) {
 274                 typedef typename Iterator<TLimitsString const, Standard>::Type TIter;
 275                 typedef typename Value<TLimitsString>::Type TSize;
 276         TIter _begin = begin(limits, Standard());
 277         TIter _upper = ::std::upper_bound(_begin, end(limits, Standard()), (TSize)pos) - 1;
 278         return pos - *_upper;
 279         }
 280
 281         //////////////////////////////////////////////////////////////////////////////
 282         // local -> global conversions
 283         //////////////////////////////////////////////////////////////////////////////
 284
 285 /**
 286 .Function.posGlobalize:
 287 ..cat:Sequences
 288 ..summary:Converts a local/global to a global position.
 289 ..signature:posGlobalize(pos, limits)
 290 ..param.pos:A local or global position (pair or integer value).
 291 ...type:Class.Pair
 292 ..param.limits:The limits string returned by @Function.stringSetLimits@.
 293 ..returns:The corresponding global position of $pos$.
 294 ...remarks:If $pos$ is an integral type $pos$ is returned.
 295 ...remarks:If not, $limits[getSeqNo(pos, limits)] + getSeqOffset(pos, limits)$ is returned.
 296 */
 297
 298         // any_position and no limits_string -> any_position
 299         template <typename TPosition>
 300         inline TPosition posGlobalize(TPosition const &pos, Nothing const &) {
 301                 return pos;
 302         }
 303
 304         // local_position (0,x) and no limits_string -> global_position x
 305         template <typename T1, typename T2, typename TCompression>
 306         inline T2 posGlobalize(Pair<T1, T2, TCompression> const &pos, Nothing const &) {
 307                 return getSeqOffset(pos);
 308         }
 309
 310         // any_position and no limits_string -> any_position
 311         template <typename TLimitsString, typename TPosition>
 312         inline TPosition posGlobalize(TPosition const &pos, TLimitsString const &) {
 313                 return pos;
 314         }
 315
 316         // local_position and limits_string -> global_position
 317         template <typename TLimitsString, typename T1, typename T2, typename TCompression>
 318         inline typename Value<TLimitsString>::Type
 319         posGlobalize(Pair<T1, T2, TCompression> const &pos, TLimitsString const &limits) {
 320                 return limits[getSeqNo(pos, limits)] + getSeqOffset(pos, limits);
 321         }
 322
 323         //////////////////////////////////////////////////////////////////////////////
 324         // global -> local position
 325         //////////////////////////////////////////////////////////////////////////////
 326
 327 /**
 328 .Function.posLocalize:
 329 ..cat:Sequences
 330 ..summary:Converts a local/global to a local position.
 331 ..signature:posLocalize(result, pos, limits)
 332 ..param.pos:A local or global position (pair or integer value).
 333 ...type:Class.Pair
 334 ..param.limits:The limits string returned by @Function.stringSetLimits@.
 335 ..param.result:Reference to the resulting corresponding local position of $pos$.
 336 ...remarks:If $pos$ is an integral type and $limits$ is omitted or @Tag.Nothing@, $pos$ is returned.
 337 ...remarks:If $pos$ is a local position (of class @Class.Pair@) then $pos$ is returned.
 338 ...remarks:If $pos$ is a global position (integer type and $limits$ is a @Class.String@) then $pos$ is converted to a local position.
 339 */
 340
 341         // any_position and no limits_string -> any_position
 342         template <typename TResult, typename TPosition>
 343         inline void posLocalize(TResult &result, TPosition const &pos, Nothing const &) {
 344                 result = pos;
 345         }
 346
 347         template <typename T1, typename T2, typename TCompression, typename TPosition>
 348         inline void posLocalize(Pair<T1, T2, TCompression> &result, TPosition const &pos, Nothing const &) {
 349                 result.i1 = 0;
 350                 result.i2 = pos;
 351         }
 352
 353         // global_position and limits_string -> local_position
 354         template <typename TResult, typename TSize, typename TSpec, typename TPosition>
 355         inline void posLocalize(TResult &result, TPosition const &pos, String<TSize, TSpec> const &limits) {
 356                 typedef typename Iterator<String<TSize> const, Standard>::Type TIter;
 357         TIter _begin = begin(limits, Standard());
 358                 TIter _upper = ::std::upper_bound(_begin, end(limits, Standard()), (TSize)pos) - 1;
 359         result.i1 = difference(_begin, _upper);
 360         result.i2 = pos - *_upper;
 361         }
 362
 363         // local_position -> local_position
 364         template <typename TResult, typename TSize, typename TSpec, typename T1, typename T2, typename TCompression>
 365         inline void posLocalize(TResult &result, Pair<T1, T2, TCompression> const &pos, String<TSize, TSpec> const &/*limits*/) {
 366                 result = pos;
 367         }
 368
 369         //////////////////////////////////////////////////////////////////////////////
 370         // prefix
 371         //////////////////////////////////////////////////////////////////////////////
 372
 373         template < typename TString, typename TSpec, typename TPosition >
 374         inline typename Prefix<TString>::Type
 375         prefix(StringSet< TString, TSpec > &me, TPosition pos)
 376         {
 377                 typedef StringSet<TString, TSpec>                               TStringSet;
 378                 typedef typename Size<TStringSet>::Type                 TSetSize;
 379                 typedef typename Size<TString>::Type                    TStringSize;
 380                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 381
 382                 TPair lPos;
 383                 posLocalize(lPos, pos, stringSetLimits(me));
 384                 return prefix(me[getSeqNo(lPos)], getSeqOffset(lPos));
 385         }
 386
 387         template < typename TString, typename TSpec, typename TPosition >
 388         inline typename Prefix<TString const>::Type
 389         prefix(StringSet< TString, TSpec > const &me, TPosition pos)
 390         {
 391                 typedef StringSet<TString, TSpec>                               TStringSet;
 392                 typedef typename Size<TStringSet>::Type                 TSetSize;
 393                 typedef typename Size<TString>::Type                    TStringSize;
 394                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 395
 396                 TPair lPos;
 397                 posLocalize(lPos, pos, stringSetLimits(me));
 398                 return prefix(me[getSeqNo(lPos)], getSeqOffset(lPos));
 399         }
 400
 401         template < typename TString, typename TDelimiter, typename TPosition >
 402         inline typename Infix<TString>::Type
 403         prefix(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > &me, TPosition pos)
 404         {
 405                 return infix(me.concat, stringSetLimits(me)[getSeqNo(pos, stringSetLimits(me))], posGlobalize(pos, stringSetLimits(me)));
 406         }
 407
 408         template < typename TString, typename TDelimiter, typename TPosition >
 409         inline typename Infix<TString const>::Type
 410         prefix(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > const &me, TPosition pos)
 411         {
 412                 return infix(me.concat, stringSetLimits(me)[getSeqNo(pos, stringSetLimits(me))], posGlobalize(pos, stringSetLimits(me)));
 413         }
 414
 415         //////////////////////////////////////////////////////////////////////////////
 416         // suffix
 417         //////////////////////////////////////////////////////////////////////////////
 418
 419         template < typename TString, typename TSpec, typename TPosition >
 420         inline typename Suffix<TString>::Type
 421         suffix(StringSet< TString, TSpec > &me, TPosition pos)
 422         {
 423                 typedef StringSet<TString, TSpec>                               TStringSet;
 424                 typedef typename Size<TStringSet>::Type                 TSetSize;
 425                 typedef typename Size<TString>::Type                    TStringSize;
 426                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 427
 428                 TPair lPos;
 429                 posLocalize(lPos, pos, stringSetLimits(me));
 430                 return suffix(me[getSeqNo(lPos)], getSeqOffset(lPos));
 431         }
 432
 433         template < typename TString, typename TSpec, typename TPosition >
 434         inline typename Suffix<TString const>::Type
 435         suffix(StringSet< TString, TSpec > const &me, TPosition pos)
 436         {
 437                 typedef StringSet<TString, TSpec>                               TStringSet;
 438                 typedef typename Size<TStringSet>::Type                 TSetSize;
 439                 typedef typename Size<TString>::Type                    TStringSize;
 440                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 441
 442                 TPair lPos;
 443                 posLocalize(lPos, pos, stringSetLimits(me));
 444                 return suffix(me[getSeqNo(lPos)], getSeqOffset(lPos));
 445         }
 446
 447         template < typename TString, typename TDelimiter, typename TPosition >
 448         inline typename Infix<TString>::Type
 449         suffix(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > &me, TPosition pos)
 450         {
 451                 return infix(me.concat, posGlobalize(pos, stringSetLimits(me)), stringSetLimits(me)[getSeqNo(pos, stringSetLimits(me)) + 1]);
 452         }
 453
 454         template < typename TString, typename TDelimiter, typename TPosition >
 455         inline typename Infix<TString const>::Type
 456         suffix(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > const &me, TPosition pos)
 457         {
 458                 return infix(me.concat, posGlobalize(pos, stringSetLimits(me)), stringSetLimits(me)[getSeqNo(pos, stringSetLimits(me)) + 1]);
 459         }
 460
 461         //////////////////////////////////////////////////////////////////////////////
 462         // infixWithLength
 463         //////////////////////////////////////////////////////////////////////////////
 464
 465         template < typename TString, typename TSpec, typename TPosition, typename TSize >
 466         inline typename Infix<TString>::Type
 467         infixWithLength(StringSet< TString, TSpec > &me, TPosition pos, TSize length)
 468         {
 469                 typedef StringSet<TString, TSpec>                               TStringSet;
 470                 typedef typename Size<TStringSet>::Type                 TSetSize;
 471                 typedef typename Size<TString>::Type                    TStringSize;
 472                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 473
 474                 TPair lPos;
 475                 posLocalize(lPos, pos, stringSetLimits(me));
 476                 return infixWithLength(me[getSeqNo(lPos)], getSeqOffset(lPos), length);
 477         }
 478
 479         template < typename TString, typename TSpec, typename TPosition, typename TSize >
 480         inline typename Infix<TString const>::Type
 481         infixWithLength(StringSet< TString, TSpec > const &me, TPosition pos, TSize length)
 482         {
 483                 typedef StringSet<TString, TSpec>                               TStringSet;
 484                 typedef typename Size<TStringSet>::Type                 TSetSize;
 485                 typedef typename Size<TString>::Type                    TStringSize;
 486                 typedef Pair<TSetSize, TStringSize, Compressed> TPair;
 487
 488                 TPair lPos;
 489                 posLocalize(lPos, pos, stringSetLimits(me));
 490                 return infixWithLength(me[getSeqNo(lPos)], getSeqOffset(lPos), length);
 491         }
 492
 493         template < typename TString, typename TDelimiter, typename TPosition, typename TSize >
 494         inline typename Infix<TString>::Type
 495         infixWithLength(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > &me, TPosition pos, TSize length)
 496         {
 497                 return infixWithLength(me.concat, posGlobalize(pos, stringSetLimits(me)), length);
 498         }
 499
 500         template < typename TString, typename TDelimiter, typename TPosition, typename TSize >
 501         inline typename Infix<TString const>::Type
 502         infixWithLength(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > const &me, TPosition pos, TSize length)
 503         {
 504                 return infixWithLength(me.concat, posGlobalize(pos, stringSetLimits(me)), length);
 505         }
 506
 507         //////////////////////////////////////////////////////////////////////////////
 508         // position arithmetics
 509         //////////////////////////////////////////////////////////////////////////////
 510
 511         // posAtFirstLocal
 512         template <typename TPos, typename TLimitsString>
 513         inline bool posAtFirstLocal(TPos pos, TLimitsString const &limits) {
 514                 return getSeqOffset(pos, limits) == 0;
 515         }
 516         template <typename TPos>
 517         inline bool posAtFirstLocal(TPos pos) {
 518                 return getSeqOffset(pos) == 0;
 519         }
 520
 521
 522         // posPrev
 523         template <typename TPos>
 524         inline TPos posPrev(TPos pos) {
 525                 return pos - 1;
 526         }
 527
 528         template <typename T1, typename T2, typename TCompression>
 529         inline Pair<T1, T2, TCompression> posPrev(Pair<T1, T2, TCompression> const &pos) {
 530                 return Pair<T1, T2, TCompression>(getValueI1(pos), getValueI2(pos) - 1);
 531         }
 532
 533         // posNext
 534         template <typename TPos>
 535         inline TPos posNext(TPos pos) {
 536                 return pos + 1;
 537         }
 538
 539         template <typename T1, typename T2, typename TCompression>
 540         inline Pair<T1, T2, TCompression>
 541         posNext(Pair<T1, T2, TCompression> const &pos) {
 542                 return Pair<T1, T2, TCompression>(getValueI1(pos), getValueI2(pos) + 1);
 543         }
 544
 545         // posAdd
 546         template <typename TPos, typename TDelta>
 547         inline TPos posAdd(TPos pos, TDelta delta) {
 548                 return pos + delta;
 549         }
 550
 551         template <typename T1, typename T2, typename TCompression, typename TDelta>
 552         inline Pair<T1, T2, TCompression>
 553         posAdd(Pair<T1, T2, TCompression> const &pos, TDelta delta) {
 554                 return Pair<T1, T2, TCompression>(getValueI1(pos), getValueI2(pos) + delta);
 555         }
 556
 557         // posSub
 558         template <typename TA, typename TB>
 559         inline TA posSub(TA a, TB b) {
 560                 return a - b;
 561         }
 562
 563         template <
 564                 typename TA1, typename TA2, typename TACompression,
 565                 typename TB1, typename TB2, typename TBCompression
 566         >
 567         inline TA2
 568         posSub(Pair<TA1, TA2, TACompression> const &a, Pair<TB1, TB2, TBCompression> const &b) {
 569                 return getValueI2(a) - getValueI2(b);
 570         }
 571
 572         //////////////////////////////////////////////////////////////////////////////
 573         // position relations
 574         //////////////////////////////////////////////////////////////////////////////
 575
 576         template <typename TPos>
 577         inline bool posLess(TPos const &a, TPos const &b) {
 578                 return a < b;
 579         }
 580
 581         template <typename T1, typename T2, typename TCompression>
 582         inline bool posLess(Pair<T1, T2, TCompression> const &a, Pair<T1, T2, TCompression> const &b) {
 583                 return
 584                          (getValueI1(a) <  getValueI1(b)) ||
 585                         ((getValueI1(a) == getValueI1(b)) && (getValueI2(a) < getValueI2(b)));
 586         }
 587
 588         template <typename TPos>
 589         inline int posCompare(TPos const &a, TPos const &b) {
 590                 if (a < b) return -1;
 591                 if (a > b) return 1;
 592                 return 0;
 593         }
 594
 595         template <typename T1, typename T2, typename TCompression>
 596         inline int posCompare(Pair<T1, T2, TCompression> const &a, Pair<T1, T2, TCompression> const &b) {
 597                 if (getValueI1(a) < getValueI1(b)) return -1;
 598                 if (getValueI1(a) > getValueI1(b)) return 1;
 599                 return posCompare(getValueI2(a), getValueI2(b));
 600         }
 601
 602         //////////////////////////////////////////////////////////////////////////////
 603
 604         template <typename TPos, typename TString>
 605         inline typename Size<TString>::Type
 606         suffixLength(TPos pos, TString const &string) {
 607                 return length(string) - pos;
 608         }
 609
 610         template <typename TPos, typename TString, typename TSpec>
 611         inline typename Size<TString>::Type
 612         suffixLength(TPos pos, StringSet<TString, TSpec> const &stringSet) {
 613                 return length(stringSet[getSeqNo(pos, stringSetLimits(stringSet))]) - getSeqOffset(pos, stringSetLimits(stringSet));
 614         }
 615
 616         //////////////////////////////////////////////////////////////////////////////
 617
 618         template <typename TString>
 619         inline unsigned
 620         countSequences(TString const &) {
 621                 return 1;
 622         }
 623
 624         template <typename TString, typename TSpec>
 625         inline typename Size<StringSet<TString, TSpec> >::Type
 626         countSequences(StringSet<TString, TSpec> const &stringSet) {
 627                 return length(stringSet);
 628         }
 629
 630         //////////////////////////////////////////////////////////////////////////////
 631
 632         template <typename TSeqNo, typename TString>
 633         inline typename Size<TString>::Type
 634         sequenceLength(TSeqNo /*seqNo*/, TString const &string) {
 635                 return length(string);
 636         }
 637
 638         template <typename TSeqNo, typename TString, typename TSpec>
 639         inline typename Size<StringSet<TString, TSpec> >::Type
 640         sequenceLength(TSeqNo seqNo, StringSet<TString, TSpec> const &stringSet) {
 641                 return length(stringSet[seqNo]);
 642         }
 643
 644         //////////////////////////////////////////////////////////////////////////////
 645     // StringSet Container
 646     //////////////////////////////////////////////////////////////////////////////
 647
 648 /**
 649 .Class.StringSet:
 650 ..cat:Sequences
 651 ..summary:A container class for a set of strings.
 652 ..signature:StringSet<TString, TSpec>
 653 ..param.TString:The string type.
 654 ...type:Class.String
 655 ..param.TSpec:The specializing type for the StringSet.
 656 ...metafunction:Metafunction.Spec
 657 ...default:$Generous$.
 658 ..include:sequence.h
 659 */
 660
 661         //////////////////////////////////////////////////////////////////////////////
 662     // StringSet with individual sequences in a tight string of string pointers and corr. IDs
 663         template <typename TString>
 664         class StringSet<TString, Dependent<Tight> >
 665         {
 666                 public:
 667                         typedef String<TString*>                                                        TStrings;
 668                         typedef typename Id<StringSet>::Type                            TIdType;
 669                         typedef String<TIdType>                                                         TIds;
 670                         typedef typename StringSetLimits<StringSet>::Type       TLimits;
 671                         typedef typename Concatenator<StringSet>::Type          TConcatenator;
 672         //____________________________________________________________________________
 673
 674                         TStrings                strings;
 675                         TIds                    ids;
 676                         TLimits                 limits;
 677                         bool                    limitsValid;            // is true if limits contains the cumulative sum of the sequence lengths
 678                         TConcatenator   concat;
 679         //____________________________________________________________________________
 680
 681                         StringSet():
 682                                 limitsValid(true)
 683                         {
 684                         SEQAN_CHECKPOINT
 685                                 appendValue(limits, 0);
 686                                 concat.set = this;
 687                         }
 688
 689                         template <typename TDefault>
 690                         StringSet(StringSet<TString, Owner<TDefault> > const& _other) :
 691                                 limitsValid(true)
 692                         {
 693                                 SEQAN_CHECKPOINT
 694                                 appendValue(limits, 0);
 695                                 concat.set = this;
 696                                 for(unsigned int i = 0; i<length(_other); ++i) appendValue(*this, _other[i]);
 697                         }
 698
 699                         template <typename TPos>
 700                         inline typename Reference<StringSet>::Type
 701                         operator [] (TPos pos)
 702                         {
 703                 SEQAN_CHECKPOINT
 704                                 return value(*this, pos);
 705                         }
 706
 707                         template <typename TPos>
 708                         inline typename Reference<StringSet const>::Type
 709                         operator [] (TPos pos) const
 710                         {
 711                                 return value(*this, pos);
 712                         }
 713         };
 714
 715         //////////////////////////////////////////////////////////////////////////////
 716     // StringSet with individual sequences in a string of string pointers
 717         template <typename TString>
 718         class StringSet<TString, Dependent<Generous> >
 719         {
 720                 public:
 721                         typedef String<TString*>                                                        TStrings;
 722                         typedef typename Size<StringSet>::Type                          TSize;
 723                         typedef typename StringSetLimits<StringSet>::Type       TLimits;
 724                         typedef typename Concatenator<StringSet>::Type          TConcatenator;
 725         //____________________________________________________________________________
 726
 727                         TStrings                strings;
 728                         TLimits                 limits;
 729                         bool                    limitsValid;            // is true if limits contains the cumulative sum of the sequence lengths
 730                         TConcatenator   concat;
 731         //____________________________________________________________________________
 732
 733                         StringSet():
 734                                 limitsValid(true)
 735                         {
 736                         SEQAN_CHECKPOINT
 737                                 appendValue(limits, 0);
 738                                 concat.set = this;
 739                         }
 740
 741                         template <typename TDefault>
 742                         StringSet(StringSet<TString, Owner<TDefault> > const& _other) :
 743                                 limitsValid(true)
 744                         {
 745                                 SEQAN_CHECKPOINT
 746                                 appendValue(limits, 0);
 747                                 concat.set = this;
 748                                 for(unsigned int i = 0; i<length(_other); ++i) appendValue(*this, _other[i]);
 749                         }
 750
 751                         template <typename TPos>
 752                         inline typename Reference<StringSet>::Type
 753                         operator [] (TPos pos)
 754                         {
 755                                 return value(*this, pos);
 756                         }
 757
 758                         template <typename TPos>
 759                         inline typename Reference<StringSet const>::Type
 760                         operator [] (TPos pos) const
 761                         {
 762                                 return value(*this, pos);
 763                         }
 764         };
 765
 766         //////////////////////////////////////////////////////////////////////////////
 767     // StringSet with individual sequences in a string of strings
 768     template < typename TString >
 769     class StringSet< TString, Owner<Default> >
 770     {
 771         public:
 772
 773         typedef String<TString>                                                         TStrings;
 774                 typedef typename StringSetLimits<StringSet>::Type       TLimits;
 775                 typedef typename Concatenator<StringSet>::Type          TConcatenator;
 776 //____________________________________________________________________________
 777
 778                 TStrings                strings;
 779         TLimits                 limits;
 780                 bool                    limitsValid;            // is true if limits contains the cumulative sum of the sequence lengths
 781                 TConcatenator   concat;
 782 //____________________________________________________________________________
 783
 784                 StringSet():
 785                         limitsValid(true)
 786                 {
 787                         appendValue(limits, 0);
 788                         concat.set = this;
 789                 };
 790 //____________________________________________________________________________
 791
 792                 template <typename TPos>
 793                 inline typename Reference<StringSet>::Type
 794                 operator [] (TPos pos)
 795                 {
 796                         return value(*this, pos);
 797                 }
 798
 799                 template <typename TPos>
 800                 inline typename Reference<StringSet const>::Type
 801                 operator [] (TPos pos) const
 802                 {
 803                         return value(*this, pos);
 804                 }
 805         };
 806
 807
 808         //////////////////////////////////////////////////////////////////////////////
 809     // StringSet with directly concatenated sequences
 810     template < typename TString, typename TDelimiter >
 811     class StringSet< TString, Owner<ConcatDirect<TDelimiter> > >
 812     {
 813         public:
 814                 typedef typename StringSetLimits<StringSet>::Type       TLimits;
 815                 typedef typename Concatenator<StringSet>::Type          TConcatenator;
 816 //____________________________________________________________________________
 817
 818                 TLimits                 limits;
 819                 TConcatenator   concat;
 820 //____________________________________________________________________________
 821
 822                 StringSet()     {
 823                         appendValue(limits, 0);
 824                 }
 825 //____________________________________________________________________________
 826
 827                 template <typename TPos>
 828                 inline typename Reference<StringSet>::Type
 829                 operator [] (TPos pos)
 830                 {
 831                 SEQAN_CHECKPOINT
 832                         return value(*this, pos);
 833                 }
 834
 835                 template <typename TPos>
 836                 inline typename Reference<StringSet const>::Type
 837                 operator [] (TPos pos) const
 838                 {
 839                 SEQAN_CHECKPOINT
 840                         return value(*this, pos);
 841                 }
 842         };
 843
 844
 845 //////////////////////////////////////////////////////////////////////////////
 846 // meta functions
 847
 848         template < typename TString, typename TSpec >
 849     struct Value< StringSet< TString, TSpec > > {
 850         typedef TString Type;
 851     };
 852
 853         template < typename TString, typename TSpec >
 854     struct Value< StringSet< TString, TSpec > const> {
 855         typedef TString Type;
 856     };
 857
 858         template < typename TString, typename TSpec >
 859         struct Size< StringSet< TString, TSpec > >:
 860                 Size< typename StringSetLimits< StringSet<TString, TSpec> >::Type > {};
 861
 862         template < typename TString, typename TSpec >
 863         struct Prefix< StringSet< TString, TSpec > >:
 864                 Prefix< TString > {};
 865
 866         template < typename TString, typename TSpec >
 867         struct Prefix< StringSet< TString, TSpec > const >:
 868                 Prefix< TString const > {};
 869
 870         template < typename TString, typename TSpec >
 871         struct Suffix< StringSet< TString, TSpec > >:
 872                 Suffix< TString > {};
 873
 874         template < typename TString, typename TSpec >
 875         struct Suffix< StringSet< TString, TSpec > const >:
 876                 Suffix< TString const > {};
 877
 878         template < typename TString, typename TSpec >
 879         struct Infix< StringSet< TString, TSpec > >:
 880                 Infix< TString > {};
 881
 882         template < typename TString, typename TSpec >
 883         struct Infix< StringSet< TString, TSpec > const >:
 884                 Infix< TString const > {};
 885
 886
 887         // direct concatenation
 888         template < typename TString, typename TSpec >
 889         struct Value< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 890                 Infix<TString> {};
 891
 892     template < typename TString, typename TSpec >
 893         struct GetValue< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 894                 Infix<TString> {};
 895
 896     template < typename TString, typename TSpec >
 897         struct GetValue< StringSet< TString, Owner<ConcatDirect<TSpec> > > const >:
 898                 Infix<TString const> {};
 899
 900     template < typename TString, typename TSpec >
 901         struct Reference< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 902                 Infix<TString> {};
 903
 904     template < typename TString, typename TSpec >
 905         struct Reference< StringSet< TString, Owner<ConcatDirect<TSpec> > > const >:
 906                 Infix<TString const> {};
 907
 908     template <typename TString, typename TSpec>
 909         struct AllowsFastRandomAccess< StringSet< TString, TSpec > >:
 910                 AllowsFastRandomAccess<TString> {};
 911
 912         template < typename TString, typename TSpec >
 913         struct Prefix< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 914                 Infix< TString > {};
 915
 916         template < typename TString, typename TSpec >
 917         struct Prefix< StringSet< TString, Owner<ConcatDirect<TSpec> > > const >:
 918                 Infix< TString const > {};
 919
 920         template < typename TString, typename TSpec >
 921         struct Suffix< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 922                 Infix< TString > {};
 923
 924         template < typename TString, typename TSpec >
 925         struct Suffix< StringSet< TString, Owner<ConcatDirect<TSpec> > > const >:
 926                 Infix< TString const > {};
 927
 928         template < typename TString, typename TSpec >
 929         struct Infix< StringSet< TString, Owner<ConcatDirect<TSpec> > > >:
 930                 Infix< TString > {};
 931
 932         template < typename TString, typename TSpec >
 933         struct Infix< StringSet< TString, Owner<ConcatDirect<TSpec> > > const >:
 934                 Infix< TString const > {};
 935
 936
 937 //////////////////////////////////////////////////////////////////////////////
 938 // validStringSetLimits
 939
 940         template < typename T >
 941     inline bool _validStringSetLimits(T const &) {
 942         return true;
 943     }
 944
 945         template < typename TString, typename TSpec >
 946     inline bool _validStringSetLimits(StringSet< TString, TSpec > const &me) {
 947         return me.limitsValid;
 948     }
 949
 950         template < typename TString, typename TSpec >
 951     inline bool _validStringSetLimits(StringSet< TString, Owner<ConcatDirect<TSpec> > > const &) {
 952         return true;
 953     }
 954
 955 //////////////////////////////////////////////////////////////////////////////
 956 // _refreshStringSetLimits
 957
 958         template < typename T >
 959         inline void _refreshStringSetLimits(T &) {}
 960
 961         template < typename TString, typename TSpec >
 962     inline void _refreshStringSetLimits(StringSet< TString, Owner<ConcatDirect<TSpec> > > &) {}
 963
 964         template < typename TString, typename TSpec >
 965     inline void _refreshStringSetLimits(StringSet< TString, TSpec > &me)
 966         {
 967                 typedef StringSet< TString, TSpec >                                     TStringSet;
 968                 typedef typename StringSetLimits<TStringSet>::Type      TLimits;
 969
 970                 typename Value<TLimits>::Type   sum = 0;
 971                 typename Size<TStringSet>::Type len = length(me);
 972                 typename Size<TStringSet>::Type i = 0;
 973
 974 //              SEQAN_ASSERT(length(me.limits) == len + 1);
 975 //              resize(me.limits, len + 1);
 976                 for(; i < len; ++i) {
 977                         me.limits[i] = sum;
 978                         sum += length(me[i]);
 979                 }
 980                 me.limits[i] = sum;
 981                 me.limitsValid = true;
 982     }
 983
 984 //////////////////////////////////////////////////////////////////////////////
 985 // find the i-th non-zero value of a string me
 986
 987         template < typename TValue, typename TSpec, typename TPos >
 988         inline typename Size< String<TValue, TSpec> >::Type
 989         _findIthNonZeroValue(String<TValue, TSpec> const &me, TPos i)
 990         {
 991                 typename Iterator< String<TValue, TSpec> const, Standard >::Type it = begin(me, Standard());
 992                 typename Iterator< String<TValue, TSpec> const, Standard >::Type itEnd = end(me, Standard());
 993
 994                 for(; it != itEnd; ++it)
 995                         if (*it) {
 996                                 if (i) {
 997                                         --i;
 998                                 }
 999                                 else {
1000                                         return position(it, me);
1001                                 }
1002                         }
1003                 return length(me);
1004         }
1005
1006 //////////////////////////////////////////////////////////////////////////////
1007 // count non-zero values before position i
1008
1009         template < typename TValue, typename TSpec, typename TPos >
1010         inline typename Size< String<TValue, TSpec> >::Type
1011         _countNonZeroValues(String<TValue, TSpec> const &me, TPos i)
1012         {
1013                 typename Iterator< String<TValue, TSpec> const, Standard >::Type it = begin(me, Standard());
1014                 typename Iterator< String<TValue, TSpec> const, Standard >::Type itEnd = begin(me, Standard()) + i;
1015                 typename Size< String<TValue, TSpec> >::Type counter = 0;
1016
1017                 for(; it != itEnd; ++it)
1018                         if (*it) ++counter;
1019                 return counter;
1020         }
1021
1022 //////////////////////////////////////////////////////////////////////////////
1023 // lengthSum
1024
1025         template < typename TString >
1026     inline typename Size<TString>::Type lengthSum(TString const &me) {
1027         return length(me);
1028     }
1029
1030         template < typename TString, typename TSpec >
1031     inline typename Size<TString>::Type lengthSum(StringSet< TString, TSpec > const &me) {
1032         return back(stringSetLimits(me));
1033     }
1034
1035 ///.Function.appendValue.param.target.type:Class.StringSet
1036 //////////////////////////////////////////////////////////////////////////////
1037 // appendValue
1038
1039         // Default
1040         template < typename TString, typename TString2, typename TExpand >
1041     inline void appendValue(
1042                 StringSet< TString, Owner<Default> > &me,
1043                 TString2 const &obj,
1044                 Tag<TExpand> const)
1045         {
1046         appendValue(me.strings, obj);
1047         appendValue(me.limits, lengthSum(me) + length(obj));
1048     }
1049
1050         // ConcatDirect
1051         template < typename TString, typename TString2, typename TExpand >
1052     inline void appendValue(
1053                 StringSet< TString, Owner<ConcatDirect<void> > > &me,
1054                 TString2 const &obj,
1055                 Tag<TExpand> const)
1056         {
1057         append(me.concat, obj);
1058         appendValue(me.limits, lengthSum(me) + length(obj));
1059     }
1060
1061     template < typename TString, typename TDelimiter, typename TString2, typename TExpand >
1062     inline void appendValue(
1063                 StringSet< TString, Owner<ConcatDirect<TDelimiter> > > &me,
1064                 TString2 const &obj,
1065                 Tag<TExpand> const)
1066         {
1067         append(me.concat, obj);
1068         appendValue(me.concat, TDelimiter());
1069         appendValue(me.limits, lengthSum(me) + length(obj) + 1);
1070     }
1071
1072         // Generous
1073         template < typename TString, typename TExpand >
1074         inline void appendValue(
1075                 StringSet<TString, Dependent<Generous> > &me,
1076                 TString const &obj,
1077                 Tag<TExpand> const)
1078         {
1079                 SEQAN_CHECKPOINT
1080                 appendValue(me.strings, const_cast<TString*>(&obj));
1081         appendValue(me.limits, lengthSum(me) + length(obj));
1082         }
1083
1084         // Tight
1085         template < typename TString, typename TExpand >
1086         inline void appendValue(
1087                 StringSet<TString, Dependent<Tight> > &me,
1088                 TString const &obj,
1089                 Tag<TExpand> const)
1090         {
1091                 SEQAN_CHECKPOINT
1092                 appendValue(me.strings, const_cast<TString*>(&obj));
1093                 appendValue(me.ids, length(me.strings) - 1);
1094         appendValue(me.limits, lengthSum(me) + length(obj));
1095         }
1096
1097 /*
1098     inline void append(TString *_objs[], unsigned count) {
1099         for(unsigned i = 0; i < count; ++i)
1100             add(_objs[i]);
1101     }
1102 */
1103
1104 ///.Function.clear.param.object.type:Class.StringSet
1105 //////////////////////////////////////////////////////////////////////////////
1106 // clear
1107
1108         template < typename TString >
1109     inline void clear(StringSet< TString, Owner<Default> > &me)
1110         {
1111         SEQAN_CHECKPOINT
1112                 clear(me.strings);
1113                 resize(me.limits, 1);
1114                 me.limitsValid = true;
1115     }
1116
1117     template < typename TString, typename TDelimiter >
1118     inline void clear(StringSet< TString, Owner<ConcatDirect<TDelimiter> > > &me)
1119         {
1120         SEQAN_CHECKPOINT
1121                 clear(me.concat);
1122                 resize(me.limits, 1);
1123     }
1124
1125     template < typename TString >
1126         inline void     clear(StringSet< TString, Dependent<Generous> > & me)
1127         {
1128         SEQAN_CHECKPOINT
1129                 clear(me.strings);
1130                 resize(me.limits, 1);
1131                 me.limitsValid = true;
1132         }
1133
1134     template < typename TString >
1135         inline void     clear(StringSet<TString, Dependent<Tight> >& me)
1136         {
1137         SEQAN_CHECKPOINT
1138                 clear(me.strings);
1139                 resize(me.limits, 1);
1140                 me.limitsValid = true;
1141
1142                 clear(me.ids);
1143         }
1144
1145 ///.Function.length.param.object.type:Class.StringSet
1146 //////////////////////////////////////////////////////////////////////////////
1147 // length
1148
1149     template < typename TString, typename TSpec >
1150     inline typename Size< StringSet< TString, TSpec > >::Type
1151         length(StringSet< TString, TSpec > const &me) {
1152         return length(me.limits) - 1;
1153     }
1154
1155         template <typename TString>
1156         inline typename Size<StringSet<TString, Dependent<Tight> > >::Type
1157         length(StringSet<TString, Dependent<Tight> > const &me)
1158         {
1159                 return length(me.strings);
1160         }
1161
1162 ///.Function.resize.param.object.type:Class.StringSet
1163 //////////////////////////////////////////////////////////////////////////////
1164 // resize
1165
1166         template < typename TString, typename TSpec, typename TSize >
1167     inline typename Size< StringSet< TString, TSpec > >::Type
1168         resize(StringSet< TString, TSpec > &me, TSize new_size) {
1169                 resize(me.limits, new_size + 1);
1170                 me.limitsValid = (new_size == 0);
1171                 return resize(me.strings, new_size);
1172     }
1173
1174         template < typename TString, typename TSpec, typename TSize >
1175     inline typename Size< StringSet< TString, Owner<ConcatDirect<TSpec> > > >::Type
1176         resize(StringSet< TString, Owner<ConcatDirect<TSpec> > > &me, TSize new_size) {
1177                 return resize(me.limits, new_size + 1) - 1;
1178     }
1179
1180 ///.Function.value.param.object.type:Class.StringSet
1181 //////////////////////////////////////////////////////////////////////////////
1182 // value
1183
1184         // Default
1185         template < typename TString, typename TPos >
1186         inline typename Reference< StringSet< TString, Owner<Default> > >::Type
1187         value(StringSet< TString, Owner<Default> > & me, TPos pos)
1188         {
1189                 return me.strings[pos];
1190         }
1191
1192         template < typename TString, typename TPos >
1193         inline typename Reference< StringSet< TString, Owner<Default> > const >::Type
1194         value(StringSet< TString, Owner<Default> > const & me, TPos pos)
1195         {
1196                 return me.strings[pos];
1197         }
1198
1199         // ConcatDirect
1200         template < typename TString, typename TSpec, typename TPos >
1201         inline typename Infix<TString>::Type
1202         value(StringSet< TString, Owner<ConcatDirect<TSpec> > > & me, TPos pos)
1203         {
1204                 return infix(me.concat, me.limits[pos], me.limits[pos + 1]);
1205         }
1206
1207         template < typename TString, typename TSpec, typename TPos >
1208         inline typename Infix<TString const>::Type
1209         value(StringSet< TString, Owner<ConcatDirect<TSpec> > > const & me, TPos pos)
1210         {
1211                 return infix(me.concat, me.limits[pos], me.limits[pos + 1]);
1212         }
1213
1214         // Tight
1215         template < typename TString, typename TPos >
1216         inline typename Reference<StringSet< TString, Dependent<Tight> > >::Type
1217         value(StringSet< TString, Dependent<Tight> >& me, TPos pos)
1218         {
1219         SEQAN_CHECKPOINT
1220                 if (me.strings[pos])
1221                         return *me.strings[pos];
1222                 static TString tmp = "";
1223                 return tmp;
1224         }
1225
1226         template < typename TString, typename TPos >
1227         inline typename Reference<StringSet< TString, Dependent<Tight> > const >::Type
1228         value(StringSet< TString, Dependent<Tight> >const & me, TPos pos)
1229         {
1230                 if (me.strings[pos])
1231                         return *me.strings[pos];
1232                 static TString tmp = "";
1233                 return tmp;
1234         }
1235
1236         // Generous
1237         template < typename TString, typename TPos >
1238         inline typename Reference<StringSet< TString, Dependent<Generous> > >::Type
1239         value(StringSet< TString, Dependent<Generous> >& me, TPos pos)
1240         {
1241         SEQAN_CHECKPOINT
1242                 unsigned i = _findIthNonZeroValue(me.strings, pos);
1243                 if (i < length(me.strings))
1244                         return *me.strings[i];
1245                 static TString tmp = "";
1246                 return tmp;
1247         }
1248
1249         template < typename TString, typename TPos >
1250         inline typename Reference< StringSet< TString, Dependent<Generous> > const >::Type
1251         value(StringSet< TString, Dependent<Generous> > const & me, TPos pos)
1252         {
1253         SEQAN_CHECKPOINT
1254                 unsigned i = _findIthNonZeroValue(me.strings, pos);
1255                 if (i < length(me.strings))
1256                         return *me.strings[i];
1257                 static TString tmp = "";
1258                 return tmp;
1259         }
1260
1261 //////////////////////////////////////////////////////////////////////////////
1262 // getValueById
1263
1264 /**
1265 .Function.getValueById:
1266 ..cat:Sequences
1267 ..summary:Retrieves a string from the StringSet given an id.
1268 ..signature:getValueById(me, id)
1269 ..param.me:A StringSet.
1270 ...type:Class.StringSet
1271 ..param.id:An id.
1272 ...type:Metafunction.Id
1273 ..returns:A reference to a string.
1274 ..see:Function.assignValueById
1275 ..see:Function.valueById
1276 */
1277
1278         template <typename TString, typename TSpec, typename TId>
1279         inline typename Reference<StringSet<TString, Owner<TSpec> > >::Type
1280         getValueById(StringSet<TString, Owner<TSpec> >& me,
1281                                 TId const id)
1282         {
1283         SEQAN_CHECKPOINT
1284                 if (id < (TId) length(me)) return value(me, id);
1285                 static TString tmp = "";
1286                 return tmp;
1287         }
1288
1289         template <typename TString, typename TId>
1290         inline typename Reference<StringSet<TString, Dependent<Generous> > >::Type
1291         getValueById(StringSet<TString, Dependent<Generous> >& me,
1292                                 TId const id)
1293         {
1294         SEQAN_CHECKPOINT
1295                 if (me.strings[id])
1296                         return *me.strings[id];
1297                 static TString tmp = "";
1298                 return tmp;
1299         }
1300
1301         template <typename TString, typename TId>
1302         inline typename Reference<StringSet<TString, Dependent<Tight> > >::Type
1303         getValueById(StringSet<TString, Dependent<Tight> >&me,
1304                                 TId const id)
1305         {
1306         SEQAN_CHECKPOINT
1307                 for(unsigned i = 0; i < length(me.strings); ++i)
1308                         if ((TId) me.ids[i] == id)
1309                                 return value(me, i);
1310                 static TString tmp = "";
1311                 return tmp;
1312         }
1313
1314
1315 //////////////////////////////////////////////////////////////////////////////
1316 // valueById
1317
1318 /**
1319 .Function.valueById:
1320 ..cat:Sequences
1321 ..summary:Retrieves a string from the StringSet given an id.
1322 ..signature:valueById(me, id)
1323 ..param.me:A StringSet.
1324 ...type:Class.StringSet
1325 ..param.id:An id.
1326 ...type:Metafunction.Id
1327 ..returns:A reference to a string.
1328 ..see:Function.assignValueById
1329 ..see:Function.getValueById
1330 */
1331
1332         template<typename TString, typename TSpec, typename TId>
1333         inline typename Reference<StringSet<TString, TSpec> >::Type
1334         valueById(StringSet<TString, TSpec>& me,
1335                         TId const id)
1336         {
1337         SEQAN_CHECKPOINT
1338                 return getValueById(me, id);
1339         }
1340
1341
1342 //////////////////////////////////////////////////////////////////////////////
1343 // assignValueById
1344
1345 /**
1346 .Function.assignValueById:
1347 ..cat:Sequences
1348 ..summary:Adds a new string to the StringSet and returns an id.
1349 ..signature:assignValueById(dest, str, [id])
1350 ..signature:assignValueById(dest, source, id)
1351 ..param.dest:A StringSet.
1352 ...type:Class.StringSet
1353 ..param.source:A StringSet.
1354 ...type:Class.StringSet
1355 ..param.str:A new string.
1356 ...type:Metafunction.Value
1357 ..param.id:An associated id.
1358 ...type:Metafunction.Id
1359 ..returns:A new id
1360 ...type:Metafunction.Id
1361 ..see:Function.getValueById
1362 ..see:Function.valueById
1363 */
1364
1365         template<typename TString, typename TSpec, typename TString2>
1366         inline typename Id<StringSet<TString, TSpec> >::Type
1367         assignValueById(StringSet<TString, TSpec>& me,
1368                                         TString2& obj)
1369         {
1370         SEQAN_CHECKPOINT
1371                 appendValue(me, obj);
1372                 SEQAN_ASSERT(length(me.limits) == length(me) + 1);
1373                 return length(me.strings) - 1;
1374         }
1375
1376         template <typename TString, typename TSpec, typename TId>
1377         inline typename Id<StringSet<TString, Owner<TSpec> > >::Type
1378         assignValueById(StringSet<TString, Owner<TSpec> >& me,
1379                                         TString& obj,
1380                                         TId id)
1381         {
1382         SEQAN_CHECKPOINT
1383                 if (id >= (TId) length(me.strings)) {
1384                         fill(me.strings, id+1, TString());
1385                         resize(me.limits, length(me.limits) + 1);
1386                 }
1387                 assignValue(me, id, obj);
1388                 me.limitsValid = false;
1389                 return id;
1390         }
1391
1392         template<typename TString, typename TId>
1393         inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
1394         assignValueById(StringSet<TString, Dependent<Generous> >& me,
1395                                         TString& obj,
1396                                         TId id)
1397         {
1398         SEQAN_CHECKPOINT
1399                 SEQAN_ASSERT(length(me.limits) == length(me) + 1);
1400                 if (id >= (TId) length(me.strings)) fill(me.strings, id+1, (TString*) 0);
1401                 if ((TString*) me.strings[id] == (TString*) 0)
1402                         resize(me.limits, length(me.limits) + 1);
1403                 me.strings[id] = &obj;
1404                 me.limitsValid = false;
1405                 SEQAN_ASSERT(length(me.limits) == length(me) + 1);
1406                 return id;
1407         }
1408
1409         //////////////////////////////////////////////////////////////////////////////
1410
1411         template<typename TString, typename TId>
1412         inline typename Id<StringSet<TString, Dependent<Tight> > >::Type
1413         assignValueById(StringSet<TString, Dependent<Tight> >& me,
1414                                         TString& obj,
1415                                         TId id)
1416         {
1417         SEQAN_CHECKPOINT
1418                 typedef StringSet<TString, Dependent<Tight> > TStringSet;
1419                 typedef typename Size<TStringSet>::Type TSize;
1420
1421                 for(TSize i = 0; i < length(me.ids); ++i)
1422                         if ((TId) me.ids[i] == id) {
1423                                 me.strings[i] = &obj;
1424                                 me.limitsValid = false;
1425                                 return id;
1426                         }
1427                 appendValue(me.strings, &obj);
1428                 appendValue(me.ids, id);
1429                 return id;
1430         }
1431
1432         template<typename TString, typename TSpec1, typename TSpec2, typename TId>
1433         inline typename Id<StringSet<TString, TSpec1> >::Type
1434         assignValueById(StringSet<TString, TSpec1>& dest,
1435                                         StringSet<TString, TSpec2>& source,
1436                                         TId id)
1437         {
1438         SEQAN_CHECKPOINT
1439                 return assignValueById(dest, getValueById(source, id), id);
1440         }
1441
1442 //////////////////////////////////////////////////////////////////////////////
1443 // removeValueById
1444
1445 /**
1446 .Function.removeValueById:
1447 ..cat:Sequences
1448 ..summary:Removes a string from the StringSet given an id.
1449 ..signature:removeValueById(me, id)
1450 ..param.me:A StringSet.
1451 ...type:Class.StringSet
1452 ..param.id:An id.
1453 ...type:Metafunction.Id
1454 ..returns:void
1455 ..see:Function.assignValueById
1456 */
1457
1458         template<typename TString, typename TSpec, typename TId>
1459         inline void
1460         removeValueById(StringSet<TString, Owner<TSpec> >& me, TId const id)
1461         {
1462         SEQAN_CHECKPOINT
1463                 erase(me.strings, id);
1464                 resize(me.limits, length(me.limits) - 1);
1465                 me.limitsValid = empty(me);
1466         }
1467
1468         template<typename TString, typename TId>
1469         inline void
1470         removeValueById(StringSet<TString, Dependent<Generous> >& me, TId const id)
1471         {
1472         SEQAN_CHECKPOINT
1473                 if (me.strings[id] != (TString*) 0) {
1474                         resize(me.limits, length(me.limits) - 1);
1475                         me.limitsValid = empty(me);
1476                 }
1477                 me.strings[id] = 0;
1478                 while (!empty(me.strings) && !me.strings[length(me.strings) - 1])
1479                         resize(me.strings, length(me.strings) - 1);
1480         }
1481
1482         template<typename TString, typename TId>
1483         inline void
1484         removeValueById(StringSet<TString, Dependent<Tight> >& me, TId const id)
1485         {
1486         SEQAN_CHECKPOINT
1487                 typedef StringSet<TString, Dependent<Tight> > TStringSet;
1488                 typedef typename Size<TStringSet>::Type TSize;
1489
1490                 SEQAN_ASSERT(length(me.limits) == length(me) + 1);
1491                 for(TSize i = 0; i < length(me.strings); ++i)
1492                         if (me.ids[i] == id) {
1493                                 erase(me.strings, i);
1494                                 erase(me.ids, i);
1495                                 resize(me.limits, length(me.limits) - 1);
1496                                 me.limitsValid = empty(me);
1497                         }
1498                 SEQAN_ASSERT(length(me.limits) == length(me) + 1);
1499         }
1500
1501 //////////////////////////////////////////////////////////////////////////////
1502 //
1503
1504 /**
1505 .Function.positionToId:
1506 ..cat:Sequences
1507 ..summary:Retrieves the id of a string in the StringSet given a position.
1508 ..signature:positionToId(string_set, pos)
1509 ..param.string_set:A StringSet.
1510 ...type:Class.StringSet
1511 ..param.pos:A position that is transfored into an id.
1512 ..returns:An id that corresponds to $pos$ within $string_set$
1513 ..see:Function.assignValueById
1514 ..see:Function.valueById
1515 */
1516
1517         template <typename TString, typename TSpec, typename TPos>
1518         inline typename Id<StringSet<TString, Owner<TSpec> > >::Type
1519         positionToId(StringSet<TString, Owner<TSpec> >&,
1520                                 TPos const pos)
1521         {
1522         SEQAN_CHECKPOINT
1523                 return pos;
1524         }
1525
1526         template <typename TString, typename TPos>
1527         inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
1528         positionToId(StringSet<TString, Dependent<Generous> >& me,
1529                         TPos const pos)
1530         {
1531         SEQAN_CHECKPOINT
1532                 return _findIthNonZeroValue(me.strings,pos);
1533         }
1534
1535         template <typename TString, typename TPos>
1536         inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
1537         positionToId(StringSet<TString, Dependent<Generous> > const& me,
1538                                 TPos const pos)
1539         {
1540         SEQAN_CHECKPOINT
1541                 return _findIthNonZeroValue(me.strings,pos);
1542         }
1543
1544         template <typename TString, typename TPos>
1545         inline typename Id<StringSet<TString, Dependent<Tight> > >::Type
1546         positionToId(StringSet<TString, Dependent<Tight> >&me,
1547                                 TPos const pos)
1548         {
1549         SEQAN_CHECKPOINT
1550                 return me.ids[pos];
1551         }
1552
1553         template <typename TString, typename TPos>
1554         inline typename Id<StringSet<TString, Dependent<Tight> > >::Type
1555         positionToId(StringSet<TString, Dependent<Tight> > const&me,
1556                                 TPos const pos)
1557         {
1558         SEQAN_CHECKPOINT
1559                 return me.ids[pos];
1560         }
1561
1562
1563 /**
1564 .Function.idToPosition:
1565 ..cat:Sequences
1566 ..summary:Retrieves the position of a string in the StringSet given an id.
1567 ..signature:idToPosition(me, id)
1568 ..param.me:A StringSet.
1569 ...type:Class.StringSet
1570 ..param.id:An id.
1571 ...type:Metafunction.Id
1572 ..returns:A reference to a string.
1573 ..see:Function.assignValueById
1574 ..see:Function.valueById
1575 */
1576
1577         template <typename TString, typename TSpec, typename TId>
1578         inline typename Id<StringSet<TString, Owner<TSpec> > >::Type
1579         idToPosition(StringSet<TString, Owner<TSpec> >&,
1580                                 TId const id)
1581         {
1582         SEQAN_CHECKPOINT
1583                 return id;
1584         }
1585
1586         template <typename TString, typename TId>
1587         inline typename Id<StringSet<TString, Dependent<Generous> > >::Type
1588         idToPosition(StringSet<TString, Dependent<Generous> >& me,
1589                                 TId const id)
1590         {
1591         SEQAN_CHECKPOINT
1592                 return _countNonZeroValues(me.strings,id);
1593         }
1594
1595         template <typename TString, typename TId>
1596         inline typename Id<StringSet<TString, Dependent<Tight> > >::Type
1597         idToPosition(StringSet<TString, Dependent<Tight> >&me,
1598                                 TId const id)
1599         {
1600         SEQAN_CHECKPOINT
1601                 for(unsigned i = 0; i < length(me.ids); ++i)
1602                         if ((TId) me.ids[i] == id)
1603                                 return i;
1604                 return 0;
1605         }
1606
1607
1608
1609
1610 //////////////////////////////////////////////////////////////////////////////
1611 // subset
1612
1613 /**
1614 .Function.subset:
1615 ..cat:Sequences
1616 ..summary:Creates a subset of a given StringSet.
1617 ..signature:subset(source, dest, id_array [, len])
1618 ..param.source:In-parameter:The source StringSet.
1619 ...type:Class.StringSet
1620 ..param.dest:Out-parameter:The destination StringSet (the subset).
1621 ...type:Class.StringSet
1622 ..param.id_array:In-parameter:An array of ids. Each id corresponds to a sequence that is supposed to be in the subset.
1623 ..param.len:In-parameter:Optional length of the id array.
1624 ...remarks:If len is not defined the length function must be valid for this array or string type.
1625 ..returns:void
1626 */
1627
1628         template <typename TString, typename TSpec, typename TDestSpec, typename TIds, typename TLength>
1629         inline void
1630         subset(StringSet<TString, Owner<TSpec> >& source,
1631                 StringSet<TString, TDestSpec>& dest,
1632                 TIds ids,
1633                 TLength len)
1634         {
1635         SEQAN_CHECKPOINT
1636         }
1637
1638         template <typename TString, typename TIds, typename TLength>
1639         inline void
1640         subset(StringSet<TString, Dependent<Generous> >& source,
1641                 StringSet<TString, Dependent<Generous> >& dest,
1642                 TIds ids,
1643                 TLength len)
1644         {
1645         SEQAN_CHECKPOINT
1646                 typedef StringSet<TString, Dependent<Generous> > TStringSet;
1647                 typedef typename Id<TStringSet>::Type TId;
1648                 typedef typename Size<TStringSet>::Type TSize;
1649
1650                 clear(dest);
1651                 resize(dest.limits, len + 1);
1652                 dest.limitsValid = (len == 0);
1653                 fill(dest.strings, length(source.strings), (TString*) 0);
1654                 for(TSize i = 0; i < len; ++i)
1655                         dest.strings[ids[i]] = source.strings[ids[i]];
1656         }
1657
1658         template <typename TString, typename TIds, typename TLength>
1659         inline void
1660         subset(StringSet<TString, Dependent<Tight> >& source,
1661                 StringSet<TString, Dependent<Tight> >& dest,
1662                 TIds ids,
1663                 TLength len)
1664         {
1665         SEQAN_CHECKPOINT
1666                 typedef StringSet<TString, Dependent<Tight> > TStringSet;
1667                 typedef typename Id<TStringSet>::Type TId;
1668                 typedef typename Size<TStringSet>::Type TSize;
1669
1670                 clear(dest);
1671                 resize(dest.limits, len + 1);
1672                 dest.limitsValid = (len == 0);
1673                 TLength upperBound = length(source.ids);
1674                 for(TSize i=0;i<len;++i) {
1675                         TId id = ids[i];
1676                         if ((upperBound > id) &&
1677                                 (source.ids[id] == id)) {
1678                                         appendValue(dest.strings, source.strings[id]);
1679                                         appendValue(dest.ids, id);
1680                         } else {
1681                                 typedef String<TId> TIdString;
1682                                 typedef typename Iterator<TIdString, Rooted>::Type TIter;
1683                                 TIter it = begin(source.ids);
1684                                 for(;!atEnd(it);goNext(it)) {
1685                                         if (*it == id) {
1686                                                 appendValue(dest.strings, source.strings[position(it)]);
1687                                                 appendValue(dest.ids, id);
1688                                         }
1689                                 }
1690                         }
1691                 }
1692         }
1693
1694         template <typename TString, typename TSpec, typename TIds>
1695         inline void
1696         subset(StringSet<TString, TSpec>& source,
1697                 StringSet<TString, TSpec>& dest,
1698                 TIds ids)
1699         {
1700         SEQAN_CHECKPOINT
1701                 subset(source, dest, ids, length(ids));
1702         }
1703
1704 //////////////////////////////////////////////////////////////////////////////
1705
1706
1707
1708
1709         //////////////////////////////////////////////////////////////////////////////
1710         // ConcatenatorNto1 - a StringSet to String converter
1711         //////////////////////////////////////////////////////////////////////////////
1712
1713     template <typename TStringSet>
1714         struct ConcatenatorNto1 {
1715                 TStringSet *set;
1716                 ConcatenatorNto1 () {}
1717                 ConcatenatorNto1 (TStringSet &_set): set(&_set) {}
1718
1719 //____________________________________________________________________________
1720 // WARNING:
1721 // operator[] conducts a binary search and should be avoided
1722 // you better use StringSet<.., Owner<ConcatDirect<..> > > for random access
1723 // or ConcatenatorNto1's iterators for sequential access
1724
1725                 template <typename TPos>
1726                 inline typename Reference<ConcatenatorNto1>::Type
1727                 operator [] (TPos pos)
1728                 {
1729         SEQAN_CHECKPOINT
1730                         return value(*this, pos);
1731                 }
1732
1733                 template <typename TPos>
1734                 inline typename Reference<ConcatenatorNto1 const>::Type
1735                 operator [] (TPos pos) const
1736                 {
1737         SEQAN_CHECKPOINT
1738                         return value(*this, pos);
1739                 }
1740         };
1741 //____________________________________________________________________________
1742
1743     template <typename TStringSet>
1744         struct Value< ConcatenatorNto1<TStringSet> > {
1745                 typedef typename Value< typename Value<TStringSet>::Type >::Type Type;
1746         };
1747
1748     template <typename TStringSet>
1749         struct Value< ConcatenatorNto1<TStringSet> const >:
1750                 Value< ConcatenatorNto1<TStringSet> > {};
1751 //____________________________________________________________________________
1752
1753     template <typename TStringSet>
1754     struct Size< ConcatenatorNto1<TStringSet> > {
1755                 typedef typename Size< typename Value<TStringSet>::Type >::Type Type;
1756     };
1757 //____________________________________________________________________________
1758
1759     template <typename TStringSet>
1760         struct AllowsFastRandomAccess< ConcatenatorNto1<TStringSet> >
1761         {
1762                 typedef False Type;
1763                 enum { VALUE = false };
1764         };
1765
1766 //////////////////////////////////////////////////////////////////////////////
1767 // value
1768
1769         template < typename TStringSet, typename TPos >
1770         inline typename Reference< ConcatenatorNto1<TStringSet> >::Type
1771         value(ConcatenatorNto1<TStringSet> &me, TPos globalPos)
1772         {
1773                 Pair<unsigned, typename Size< typename Value<TStringSet>::Type >::Type> localPos;
1774                 posLocalize(localPos, globalPos, stringSetLimits(*me.set));
1775         return value(value(*me.set, getValueI1(localPos)), getValueI2(localPos));
1776         }
1777
1778         template < typename TStringSet, typename TPos >
1779         inline typename Reference< ConcatenatorNto1<TStringSet> const >::Type
1780         value(ConcatenatorNto1<TStringSet> const &me, TPos globalPos)
1781         {
1782                 typedef typename Value<TStringSet>::Type TString;
1783                 Pair<unsigned, typename Size<TString>::Type> localPos;
1784                 posLocalize(localPos, globalPos, stringSetLimits(*me.set));
1785         return value(value(*(TStringSet const*)me.set, getValueI1(localPos)), getValueI2(localPos));
1786         }
1787
1788 //////////////////////////////////////////////////////////////////////////////
1789 // length
1790
1791         template < typename TStringSet >
1792     inline typename Size< ConcatenatorNto1<TStringSet> >::Type
1793         length(ConcatenatorNto1<TStringSet> const &me) {
1794         return lengthSum(*me.set);
1795     }
1796
1797 //////////////////////////////////////////////////////////////////////////////
1798 // begin
1799
1800         template < typename TStringSet, typename TSpec >
1801         inline typename Iterator< ConcatenatorNto1<TStringSet const>, Tag<TSpec> const >::Type
1802         begin(ConcatenatorNto1<TStringSet const> concat, Tag<TSpec> const)
1803         {
1804                 return typename Iterator< ConcatenatorNto1<TStringSet const>, Tag<TSpec> const >::Type (*concat.set);
1805         }
1806
1807         template < typename TStringSet, typename TSpec >
1808         inline typename Iterator< ConcatenatorNto1<TStringSet>, Tag<TSpec> const >::Type
1809         begin(ConcatenatorNto1<TStringSet> concat, Tag<TSpec> const)
1810         {
1811                 return typename Iterator< ConcatenatorNto1<TStringSet>, Tag<TSpec> const >::Type (*concat.set);
1812         }
1813
1814 //////////////////////////////////////////////////////////////////////////////
1815 // end
1816
1817         template < typename TStringSet, typename TSpec >
1818         inline typename Iterator< ConcatenatorNto1<TStringSet const>, Tag<TSpec> const >::Type
1819         end(ConcatenatorNto1<TStringSet const> concat, Tag<TSpec> const)
1820         {
1821                 return typename Iterator< ConcatenatorNto1<TStringSet>, Tag<TSpec> const >::Type
1822                         (*concat.set, length(*concat.set), 0);
1823         }
1824
1825         template < typename TStringSet, typename TSpec >
1826         inline typename Iterator< ConcatenatorNto1<TStringSet>, Tag<TSpec> const >::Type
1827         end(ConcatenatorNto1<TStringSet> concat, Tag<TSpec> const)
1828         {
1829                 return typename Iterator< ConcatenatorNto1<TStringSet>, Tag<TSpec> const >::Type
1830                         (*concat.set, length(*concat.set), 0);
1831         }
1832
1833 //////////////////////////////////////////////////////////////////////////////
1834 // Concatenator metafunction
1835
1836         template < typename TString, typename TSpec >
1837         struct Concatenator< StringSet<TString, TSpec> > {
1838                 typedef ConcatenatorNto1< StringSet<TString, TSpec> > Type;
1839         };
1840
1841         template < typename TString, typename TSpec >
1842         struct Concatenator< StringSet<TString, Owner<ConcatDirect<TSpec> > > > {
1843                 typedef TString Type;
1844         };
1845
1846 //////////////////////////////////////////////////////////////////////////////
1847 // concat
1848
1849         template <typename TString>
1850         inline typename Concatenator<TString>::Type &
1851         concat(TString &string) {
1852                 return string;
1853         }
1854
1855         template <typename TString, typename TSpec>
1856         inline typename Concatenator< StringSet<TString, TSpec> >::Type &
1857         concat(StringSet<TString, TSpec> &set) {
1858                 return set.concat;
1859         }
1860
1861         template <typename TString, typename TSpec>
1862         inline typename Concatenator< StringSet<TString, TSpec> const>::Type &
1863         concat(StringSet<TString, TSpec> const &set) {
1864                 return set.concat;
1865         }
1866
1867
1868         //////////////////////////////////////////////////////////////////////////////
1869         // This iterator sequentially iterates through the elements of TStringSet
1870         // as if they were directly concatenated (compare StringSet<.., Owner<ConcatDirect<> > >
1871     //////////////////////////////////////////////////////////////////////////////
1872
1873         template < typename TDelimiter = void >
1874         struct ConcatVirtual;
1875
1876     template < typename TStringSet, typename TSpec >
1877         class Iter< TStringSet, ConcatVirtual<TSpec> >
1878         {
1879         public:
1880                 typedef typename Value<TStringSet>::Type                TString;
1881                 typedef typename Value<TString>::Type                   TValue;
1882         typedef typename Size<TString>::Type                    TSize;
1883 //____________________________________________________________________________
1884
1885         public:
1886         typedef typename Iterator<TString, Standard>::Type                      obj_iterator;
1887         typedef typename Iterator<TString const, Standard>::Type        const_obj_iterator;
1888
1889                 //////////////////////////////////////////////////////////////////////////////
1890                 // STL compatible public iterator interface
1891
1892         typedef Iter                                                            iterator;
1893                 typedef ::std::bidirectional_iterator_tag       iterator_category;
1894         typedef TValue                                                          value_type;
1895                 typedef TValue &                                                        reference;
1896                 typedef TValue const &                                          const_reference;
1897                 typedef TValue*                                                         pointer;
1898                 typedef TSize                                                           size_type;
1899                 typedef typename Difference<TString>::Type      difference_type;
1900 //____________________________________________________________________________
1901
1902                 TStringSet              *host;
1903         unsigned                objNo;
1904         obj_iterator    _begin, _cur, _end;
1905 //____________________________________________________________________________
1906
1907                 inline Iter() {}
1908
1909         inline Iter(TStringSet &_host):
1910             host(&_host)
1911         {
1912             objNo = 0;
1913             _begin = _cur = begin(_host[objNo]);
1914             _end = end(_host[objNo]);
1915             _testEnd();
1916         }
1917
1918         inline Iter(TStringSet &_host, unsigned _objNo, difference_type _offset):
1919             host(&_host)
1920         {
1921             if (_objNo < length(_host)) {
1922                     objNo = _objNo;
1923                                 _begin = _cur = begin(_host[objNo]);
1924                                 _end = end(_host[objNo]);
1925                 goFurther(_cur, _offset);
1926                 _testEnd();
1927             } else {
1928                                 objNo = length(_host) - 1;
1929                                 _begin = _cur = _end = end(_host[objNo]);
1930             }
1931         }
1932
1933         inline operator obj_iterator() {
1934             return _cur;
1935         }
1936 //____________________________________________________________________________
1937
1938                 inline bool _atEndOfSequence() {
1939                         if (_cur == _begin && objNo > 0) return true;
1940                         if (_cur == _end) return true;
1941                         return false;
1942                 }
1943
1944                 inline void _testBegin() {
1945             while (_cur == _begin && objNo > 0) {
1946                 --objNo;
1947                                 _begin = host->_begin(objNo);
1948                                 _end = _cur = host->_end(objNo);
1949             }
1950         }
1951
1952         inline void _testEnd() {
1953                         while (_cur == _end && objNo < (length(*host) - 1)) {
1954                                 ++objNo;
1955                                 _begin = _cur = begin((*host)[objNo]);
1956                                 _end = end((*host)[objNo]);
1957             };
1958         }
1959
1960         inline TSize _tell() const {
1961                         typedef Pair<unsigned, TSize> TPair;
1962                         return posGlobalize(TPair(objNo, difference(_begin, _cur)), stringSetLimits(*host));
1963         }
1964     };
1965
1966         //////////////////////////////////////////////////////////////////////////////
1967         // ConcatenatorNto1 meta functions
1968         //////////////////////////////////////////////////////////////////////////////
1969 //____________________________________________________________________________
1970 // default concatenator iterators
1971
1972     template <typename TString, typename TSpec >
1973     struct Iterator< ConcatenatorNto1< StringSet<TString, TSpec> >, Standard > {
1974         typedef Iter<StringSet<TString, TSpec>, ConcatVirtual<> > Type;
1975     };
1976
1977     template <typename TString, typename TSpec >
1978     struct Iterator< ConcatenatorNto1< StringSet<TString, TSpec> const >, Standard > {
1979         typedef Iter<StringSet<TString, TSpec> const, ConcatVirtual<> > Type;
1980     };
1981
1982     template <typename TString, typename TSpec >
1983     struct Iterator< ConcatenatorNto1< StringSet<TString, TSpec> >, Rooted > {
1984         typedef Iter<StringSet<TString, TSpec>, ConcatVirtual<> > Type;
1985     };
1986
1987     template <typename TString, typename TSpec >
1988     struct Iterator< ConcatenatorNto1< StringSet<TString, TSpec> const >, Rooted > {
1989         typedef Iter<StringSet<TString, TSpec> const, ConcatVirtual<> > Type;
1990     };
1991 //____________________________________________________________________________
1992
1993         template <typename TStringSet >
1994     struct Iterator< ConcatenatorNto1<TStringSet> const, Standard > {
1995                 typedef typename Iterator< ConcatenatorNto1<TStringSet>, Standard >::Type Type;
1996     };
1997
1998     template <typename TStringSet >
1999     struct Iterator< ConcatenatorNto1<TStringSet> const, Rooted > {
2000                 typedef typename Iterator< ConcatenatorNto1<TStringSet>, Rooted >::Type Type;
2001     };
2002
2003         //////////////////////////////////////////////////////////////////////////////
2004         // meta functions
2005         //////////////////////////////////////////////////////////////////////////////
2006
2007         template <typename TStringSet, typename TSpec>
2008         struct Value< Iter< TStringSet, ConcatVirtual<TSpec> > >:
2009                 Value< typename Value<TStringSet>::Type > {};
2010
2011         template <typename TStringSet, typename TSpec>
2012         struct Value< Iter< TStringSet, ConcatVirtual<TSpec> > const >:
2013                 Value< typename Value<TStringSet>::Type > {};
2014
2015         template <typename TStringSet, typename TSpec>
2016         struct GetValue< Iter< TStringSet, ConcatVirtual<TSpec> > >:
2017                 GetValue< typename Value<TStringSet>::Type > {};
2018
2019         template <typename TStringSet, typename TSpec>
2020         struct GetValue< Iter< TStringSet, ConcatVirtual<TSpec> > const >:
2021                 GetValue< typename Value<TStringSet>::Type > {};
2022
2023         template <typename TStringSet, typename TSpec>
2024         struct Size< Iter< TStringSet, ConcatVirtual<TSpec> > >:
2025                 Size< typename Value<TStringSet>::Type > {};
2026
2027         template <typename TStringSet, typename TSpec>
2028         struct Reference< Iter< TStringSet, ConcatVirtual<TSpec> > >:
2029                 Reference< typename Value<TStringSet>::Type > {};
2030
2031         template <typename TStringSet, typename TSpec>
2032         struct Reference< Iter< TStringSet, ConcatVirtual<TSpec> > const >:
2033                 Reference< typename Value<TStringSet>::Type > {};
2034
2035
2036         //////////////////////////////////////////////////////////////////////////////
2037         // operator *
2038         //////////////////////////////////////////////////////////////////////////////
2039
2040         template <typename TStringSet, typename TSpec>
2041         inline typename Reference< Iter< TStringSet, ConcatVirtual<TSpec> > const>::Type
2042         value(Iter<TStringSet, ConcatVirtual<TSpec> > const & me) {
2043         return *me._cur;
2044     }
2045
2046         template <typename TStringSet, typename TSpec>
2047         inline typename Reference< Iter< TStringSet, ConcatVirtual<TSpec> > >::Type
2048         value(Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2049         return *me._cur;
2050     }
2051
2052         template <typename TStringSet, typename TSpec>
2053         inline typename Reference< Iter< TStringSet, ConcatVirtual<TSpec> > const>::Type
2054         operator * (Iter<TStringSet, ConcatVirtual<TSpec> > const & me) {
2055         return *me._cur;
2056     }
2057
2058         template <typename TStringSet, typename TSpec>
2059         inline typename Reference< Iter< TStringSet, ConcatVirtual<TSpec> > >::Type
2060         operator * (Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2061         return *me._cur;
2062     }
2063
2064         //////////////////////////////////////////////////////////////////////////////
2065         // operator ++
2066         //////////////////////////////////////////////////////////////////////////////
2067
2068         template <typename TStringSet, typename TSpec>
2069         inline void
2070         goNext(Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2071         ++me._cur;
2072         me._testEnd();
2073     }
2074
2075         template <typename TStringSet, typename TSpec>
2076         inline Iter<TStringSet, ConcatVirtual<TSpec> > const &
2077         operator ++ (Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2078         goNext(me);
2079                 return me;
2080     }
2081
2082         template <typename TStringSet, typename TSpec>
2083         inline Iter<TStringSet, ConcatVirtual<TSpec> > const &
2084         operator ++ (Iter<TStringSet, ConcatVirtual<TSpec> > & me, int) {
2085                 Iter<TStringSet, ConcatVirtual<TSpec> > before = me;
2086         goNext(me);
2087                 return before;
2088         }
2089
2090         //////////////////////////////////////////////////////////////////////////////
2091         // operator --
2092         //////////////////////////////////////////////////////////////////////////////
2093
2094         template <typename TStringSet, typename TSpec>
2095         inline void
2096         goPrevious(Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2097         me._testBegin();
2098         --me._cur;
2099     }
2100
2101         template <typename TStringSet, typename TSpec>
2102         inline Iter<TStringSet, ConcatVirtual<TSpec> > const &
2103         operator -- (Iter<TStringSet, ConcatVirtual<TSpec> > & me) {
2104         goPrevious(me);
2105                 return me;
2106     }
2107
2108         template <typename TStringSet, typename TSpec>
2109         inline Iter<TStringSet, ConcatVirtual<TSpec> > const &
2110         operator -- (Iter<TStringSet, ConcatVirtual<TSpec> > & me, int) {
2111                 Iter<TStringSet, ConcatVirtual<TSpec> > before = me;
2112         goPrevious(me);
2113                 return before;
2114         }
2115
2116         //////////////////////////////////////////////////////////////////////////////
2117         // operator +
2118         //////////////////////////////////////////////////////////////////////////////
2119
2120         template <typename TStringSet, typename TSpec, typename TDelta>
2121         inline Iter<TStringSet, ConcatVirtual<TSpec> >
2122         operator + (Iter<TStringSet, ConcatVirtual<TSpec> > const & me, TDelta delta) {
2123                 Pair<unsigned, typename Size< typename Value<TStringSet>::Type >::Type> pos;
2124                 posLocalize(pos, me._tell() + delta, stringSetLimits(*me.host));
2125         return Iter<TStringSet, ConcatVirtual<TSpec> > (*me.host, getValueI1(pos), getValueI2(pos));
2126     }
2127
2128         template <typename TStringSet, typename TSpec, typename T1, typename T2, typename TCompression>
2129         inline Iter<TStringSet, ConcatVirtual<TSpec> >
2130         operator + (Iter<TStringSet, ConcatVirtual<TSpec> > const & me, Pair<T1, T2, TCompression> delta) {
2131                 Pair<unsigned, typename Size< typename Value<TStringSet>::Type >::Type> pos;
2132                 posLocalize(pos, me._tell() + delta, stringSetLimits(*me.host));
2133         return Iter<TStringSet, ConcatVirtual<TSpec> > (*me.host, getValueI1(pos), getValueI2(pos));
2134     }
2135
2136         //////////////////////////////////////////////////////////////////////////////
2137         // operator -
2138         //////////////////////////////////////////////////////////////////////////////
2139
2140         template <typename TSSetL, typename TSpecL, typename TSSetR, typename TSpecR>
2141         typename Difference<Iter<TSSetL, ConcatVirtual<TSpecL> > >::Type
2142         operator - (
2143                 Iter<TSSetL, ConcatVirtual<TSpecL> > const &L,
2144                 Iter<TSSetR, ConcatVirtual<TSpecR> > const &R)
2145         {
2146         return L._tell() - R._tell();
2147     }
2148
2149         template <typename TStringSet, typename TSpec, typename TDelta>
2150         inline Iter<TStringSet, ConcatVirtual<TSpec> >
2151         operator - (Iter<TStringSet, ConcatVirtual<TSpec> > const & me, TDelta delta) {
2152                 Pair<unsigned, typename Size< typename Value<TStringSet>::Type >::Type> pos;
2153                 posLocalize(pos, me._tell() - delta, stringSetLimits(*me.host));
2154         return Iter<TStringSet, ConcatVirtual<TSpec> > (*me.host, getValueI1(pos), getValueI2(pos));
2155     }
2156
2157         //////////////////////////////////////////////////////////////////////////////
2158         // operator ==
2159         //////////////////////////////////////////////////////////////////////////////
2160
2161         template <typename TSSetL, typename TSpecL, typename TSSetR, typename TSpecR>
2162         inline bool
2163         operator == (
2164                 Iter<TSSetL, ConcatVirtual<TSpecL> > const &L,
2165                 Iter<TSSetR, ConcatVirtual<TSpecR> > const &R)
2166         {
2167                 SEQAN_ASSERT(L.host == R.host);
2168                 return L.objNo == R.objNo && L._cur == R._cur;
2169         }
2170
2171         template <typename TSSetL, typename TSpecL, typename TSSetR, typename TSpecR>
2172         inline bool
2173         operator != (
2174                 Iter<TSSetL, ConcatVirtual<TSpecL> > const &L,
2175                 Iter<TSSetR, ConcatVirtual<TSpecR> > const &R)
2176         {
2177                 SEQAN_ASSERT(L.host == R.host);
2178                 return L.objNo != R.objNo || L._cur != R._cur;
2179         }
2180
2181         //////////////////////////////////////////////////////////////////////////////
2182         // operator <
2183         //////////////////////////////////////////////////////////////////////////////
2184
2185         template <typename TSSetL, typename TSpecL, typename TSSetR, typename TSpecR>
2186         inline bool
2187         operator < (
2188                 Iter<TSSetL, ConcatVirtual<TSpecL> > const &L,
2189                 Iter<TSSetR, ConcatVirtual<TSpecR> > const &R)
2190         {
2191                 SEQAN_ASSERT(L.host == R.host);
2192                 return L.objNo < R.objNo || (L.objNo == R.objNo && L._cur < R._cur);
2193         }
2194
2195         template <typename TSSetL, typename TSpecL, typename TSSetR, typename TSpecR>
2196         inline bool
2197         operator > (
2198                 Iter<TSSetL, ConcatVirtual<TSpecL> > const &L,
2199                 Iter<TSSetR, ConcatVirtual<TSpecR> > const &R)
2200         {
2201                 SEQAN_ASSERT(L.host == R.host);
2202                 return L.objNo > R.objNo || (L.objNo == R.objNo && L._cur > R._cur);
2203         }
2204
2205         //////////////////////////////////////////////////////////////////////////////
2206         // container
2207         //////////////////////////////////////////////////////////////////////////////
2208
2209         template <typename TSSet, typename TSpec>
2210         inline typename Concatenator<TSSet>::Type
2211         container(Iter<TSSet, ConcatVirtual<TSpec> > &me)
2212         {
2213                 return concat(*me.host);
2214         }
2215
2216         template <typename TSSet, typename TSpec>
2217         inline typename Concatenator<TSSet>::Type
2218         container(Iter<TSSet, ConcatVirtual<TSpec> > const &me)
2219         {
2220                 return concat(*me.host);
2221         }
2222
2223         //////////////////////////////////////////////////////////////////////////////
2224         // atBegin
2225         //////////////////////////////////////////////////////////////////////////////
2226
2227         template <typename TSSet, typename TSpec>
2228         inline bool
2229         atBegin(Iter<TSSet, ConcatVirtual<TSpec> > &me)
2230         {
2231                 return me._cur == me._begin && me.objNo == 0;
2232         }
2233
2234         template <typename TSSet, typename TSpec>
2235         inline bool
2236         atBegin(Iter<TSSet, ConcatVirtual<TSpec> > const &me)
2237         {
2238                 return me._cur == me._begin && me.objNo == 0;
2239         }
2240
2241         //////////////////////////////////////////////////////////////////////////////
2242         // atEnd
2243         //////////////////////////////////////////////////////////////////////////////
2244
2245         template <typename TSSet, typename TSpec>
2246         inline bool
2247         atEnd(Iter<TSSet, ConcatVirtual<TSpec> > &me)
2248         {
2249                 return me._cur == me._end && me.objNo == (length(*me.host) - 1);
2250         }
2251
2252         template <typename TSSet, typename TSpec>
2253         inline bool
2254         atEnd(Iter<TSSet, ConcatVirtual<TSpec> > const &me)
2255         {
2256                 return me._cur == me._end && me.objNo == (length(*me.host) - 1);
2257         }
2258
2259         //////////////////////////////////////////////////////////////////////////////
2260         // atEndOfSequence
2261         //////////////////////////////////////////////////////////////////////////////
2262
2263         template <typename TIterator>
2264         inline bool
2265         atEndOfSequence(TIterator const &me)
2266         {
2267                 return atEnd(me);
2268         }
2269
2270         template <typename TSSet, typename TSpec>
2271         inline bool
2272         atEndOfSequence(Iter<TSSet, ConcatVirtual<TSpec> > const &me)
2273         {
2274                 return me._atEndOfSequence();
2275         }
2276
2277         template <typename TIterator>
2278         inline bool
2279         atEndOfSequence(TIterator &me)
2280         {
2281                 return atEndOfSequence(reinterpret_cast<TIterator const &>(me));
2282         }
2283
2284 }
2285
2286 #endif