SeqAn-1.1/seqan/sequence/string_packed.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: string_packed.h,v 1.2 2009/02/19 01:51:23 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_SEQUENCE_PACKED_H
  22 #define SEQAN_HEADER_SEQUENCE_PACKED_H
  23
  24
  25 namespace SEQAN_NAMESPACE_MAIN
  26 {
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 // Tags
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 template <typename THostspec = Alloc<> >
  33 struct Packed;
  34
  35
  36 //////////////////////////////////////////////////////////////////////////////
  37 /**
  38 .Spec.Packed String:
  39 ..cat:Strings
  40 ..general:Class.String
  41 ..summary:A string that stores as many values in one machine word as possible.
  42 ..signature:String<TValue, Packed<THostspec> >
  43 ..param.TValue:The value type, that is the type of the items/characters stored in the string.
  44 ...remarks:Use @Metafunction.Value@ to get the value type for a given class.
  45 ..param.THostspec:The specializing type.
  46 ...remarks:This is the specialization of the host string that is used for storing the packed values.
  47 ...default:@Spec.Alloc String.Alloc<>@
  48 */
  49
  50 /*???TODO Optimierungsmöglichkeiten:
  51 - _clearSpace kopiert Zeichenweise im Packed-String, und nicht im Host-String
  52 - _clearSpace verwendet resize, um den Host zu vergrößern, d.h. der Inhalt wird eventuell doppelt kopiert.
  53 */
  54
  55 //////////////////////////////////////////////////////////////////////////////
  56 //Rooted expandable string
  57 //////////////////////////////////////////////////////////////////////////////
  58
  59 template <typename TValue, typename THostspec>
  60 class String<TValue, Packed<THostspec> >
  61 {
  62 protected:
  63         typedef typename Host<String>::Type THost;
  64         typedef typename Size<String>::Type TSize;
  65
  66         THost data_host;
  67         TSize data_length;
  68
  69 //____________________________________________________________________________
  70
  71 public:
  72         String():
  73                 data_length(0)
  74         {
  75 SEQAN_CHECKPOINT
  76         }
  77
  78         template <typename TSource>
  79         String(TSource & source):
  80                 data_length(0)
  81         {
  82 SEQAN_CHECKPOINT
  83                 assign(*this, source);
  84         }
  85         template <typename TSource>
  86         String(TSource const & source):
  87                 data_length(0)
  88         {
  89 SEQAN_CHECKPOINT
  90                 assign(*this, source);
  91         }
  92         String(String const & source):
  93                 data_length(0)
  94         {
  95 SEQAN_CHECKPOINT
  96                 assign(*this, source);
  97         }
  98
  99         template <typename TSource>
 100         String & operator =(TSource const & source)
 101         {
 102 SEQAN_CHECKPOINT
 103                 assign(*this, source);
 104                 return *this;
 105         }
 106         String & operator =(String const & source)
 107         {
 108 SEQAN_CHECKPOINT
 109                 assign(*this, source);
 110                 return *this;
 111         }
 112
 113         ~String()
 114         {
 115 SEQAN_CHECKPOINT
 116         }
 117
 118
 119 //____________________________________________________________________________
 120
 121         template <typename TPos>
 122         inline typename Reference<String>::Type
 123         operator [] (TPos pos)
 124         {
 125 SEQAN_CHECKPOINT
 126                 return value(*this, pos);
 127         }
 128
 129         template <typename TPos>
 130         inline typename Reference<String const>::Type
 131         operator [] (TPos pos) const
 132         {
 133 SEQAN_CHECKPOINT
 134                 return value(*this, pos);
 135         }
 136
 137 //____________________________________________________________________________
 138
 139 ///.Function.host.param.object.type:Spec.Packed String
 140
 141         friend inline THost &
 142         host(String & me)
 143         {
 144 SEQAN_CHECKPOINT
 145                 return me.data_host;
 146         }
 147
 148         friend inline THost const &
 149         host(String const & me)
 150         {
 151 SEQAN_CHECKPOINT
 152                 return me.data_host;
 153         }
 154
 155 //____________________________________________________________________________
 156
 157         friend inline TSize
 158         length(String & me)
 159         {
 160 SEQAN_CHECKPOINT
 161                 return me.data_length;
 162         }
 163
 164         friend inline TSize
 165         length(String const & me)
 166         {
 167 SEQAN_CHECKPOINT
 168                 return me.data_length;
 169         }
 170
 171 //____________________________________________________________________________
 172
 173         friend inline void
 174         _setLength(
 175                 String & me,
 176                 TSize new_length)
 177         {
 178 SEQAN_CHECKPOINT
 179                 me.data_length = new_length;
 180                 _setLength(host(me), _PackedConsts<String>::toHostLength(new_length));
 181         }
 182
 183 //____________________________________________________________________________
 184 };
 185
 186 //////////////////////////////////////////////////////////////////////////////
 187
 188 template <typename TValue, typename THostspec>
 189 struct DefaultOverflowImplicit<String<TValue, Packed<THostspec> > >:
 190         DefaultOverflowImplicit< typename Host<String<TValue, Packed<THostspec> > >::Type >
 191 {
 192 };
 193 template <typename TValue, typename THostspec>
 194 struct DefaultOverflowImplicit<String<TValue, Packed<THostspec> > const>:
 195         DefaultOverflowImplicit< typename Host<String<TValue, Packed<THostspec> > const>::Type >
 196 {
 197 };
 198
 199 //////////////////////////////////////////////////////////////////////////////
 200
 201 template <typename TValue, typename THostspec>
 202 struct DefaultOverflowExplicit<String<TValue, Packed<THostspec> > >:
 203         DefaultOverflowExplicit< typename Host<String<TValue, Packed<THostspec> > >::Type >
 204 {
 205 };
 206 template <typename TValue, typename THostspec>
 207 struct DefaultOverflowExplicit<String<TValue, Packed<THostspec> > const>:
 208         DefaultOverflowExplicit< typename Host<String<TValue, Packed<THostspec> > const>::Type >
 209 {
 210 };
 211
 212 //////////////////////////////////////////////////////////////////////////////
 213
 214 template <typename TValue, typename THostspec>
 215 struct IsContiguous<String<TValue, Packed<THostspec> > >
 216 {
 217     typedef False Type;
 218         enum { VALUE = false };
 219 };
 220
 221 //////////////////////////////////////////////////////////////////////////////
 222
 223 ///.Metafunction.Host.param.T.type:Spec.Packed String
 224
 225 template <typename TValue, typename THostspec>
 226 struct Host<String<TValue, Packed<THostspec> > >
 227 {
 228         typedef String<unsigned int, THostspec> Type;
 229 };
 230 template <typename TValue, typename THostspec>
 231 struct Host<String<TValue, Packed<THostspec> > const>
 232 {
 233         typedef String<unsigned int, THostspec> const Type;
 234 };
 235
 236 //////////////////////////////////////////////////////////////////////////////
 237
 238 template <typename TValue, typename THostspec>
 239 struct GetValue<String<TValue, Packed<THostspec> > >:
 240         Value<String<TValue, Packed<THostspec> > >
 241 {
 242 };
 243 template <typename TValue, typename THostspec>
 244 struct GetValue<String<TValue, Packed<THostspec> > const>:
 245         Value<String<TValue, Packed<THostspec> > const>
 246 {
 247 };
 248
 249 //////////////////////////////////////////////////////////////////////////////
 250
 251 template <typename TValue, typename THostspec>
 252 struct Reference<String<TValue, Packed<THostspec> > >
 253 {
 254         typedef typename Iterator<String<TValue, Packed<THostspec> >, Standard>::Type TIterator;
 255         typedef Proxy<IteratorProxy<TIterator> > Type;
 256 };
 257 template <typename TValue, typename THostspec>
 258 struct Reference<String<TValue, Packed<THostspec> > const>
 259 {
 260         typedef typename Iterator<String<TValue, Packed<THostspec> > const, Standard>::Type TIterator;
 261         typedef Proxy<IteratorProxy<TIterator> > Type;
 262 };
 263
 264 //////////////////////////////////////////////////////////////////////////////
 265 /*
 266 template <typename TValue, typename THostspec>
 267 struct Size<String<TValue, Packed<THostspec> > >
 268 {
 269         typedef __int64 Type;
 270 };
 271 template <typename TValue, typename THostspec>
 272 struct Size<String<TValue, Packed<THostspec> > const>
 273 {
 274         typedef __int64 Type;
 275 };
 276 //*/
 277
 278 //////////////////////////////////////////////////////////////////////////////
 279 //////////////////////////////////////////////////////////////////////////////
 280 // Compute Bit Values
 281 //////////////////////////////////////////////////////////////////////////////
 282
 283 template <typename TPackedContainer>
 284 struct _PackedConsts
 285 {
 286         typedef typename Value<TPackedContainer>::Type TValue;
 287         typedef typename Host<TPackedContainer>::Type THost;
 288         typedef typename Value<THost>::Type THostValue;
 289
 290         enum
 291         {
 292                 BITS_PER_VALUE = BitsPerValue<TValue>::VALUE,
 293                 BITS_PER_HOST_VALUE = BitsPerValue<THostValue>::VALUE,
 294                 VALUES_PER_WORD = (BITS_PER_VALUE > BITS_PER_HOST_VALUE) ? 1 : (BITS_PER_HOST_VALUE / BITS_PER_VALUE),
 295                 VALUE_MASK = (1 << BITS_PER_VALUE) - 1,
 296                 MAX_BIT_POS = (VALUES_PER_WORD - 1) * BITS_PER_VALUE
 297         };
 298
 299         static typename Size<THost>::Type
 300         toHostLength(typename Size<TPackedContainer>::Type len)
 301         {
 302                 return (len + VALUES_PER_WORD - 1) / VALUES_PER_WORD;
 303         }
 304 };
 305
 306 //////////////////////////////////////////////////////////////////////////////
 307 //////////////////////////////////////////////////////////////////////////////
 308 // Temporary Copy
 309 //////////////////////////////////////////////////////////////////////////////
 310 //note: this works only, if the copy assignment is done without using _TempCopy
 311
 312 template <typename TValue, typename THostspec>
 313 struct _TempCopy<String<TValue, Packed<THostspec> > >
 314 {
 315         typedef String<TValue, Packed<THostspec> > Type;
 316 };
 317
 318 //////////////////////////////////////////////////////////////////////////////
 319 //optimized variant for copy assignment. The host sequence is copied instead of
 320 //copying the packed string value by value
 321
 322 template <typename TTarget, typename TSource, typename TTag>
 323 inline void
 324 _assign_copy_packed_string(TTarget & target,
 325                                                    TSource & source,
 326                                                    Tag<TTag> const tag)
 327 {
 328         typedef typename Size<TTarget>::Type TSize2;
 329
 330         assign(host(target), host(source), tag);
 331         TSize2 new_length_limit = length(host(target)) * _PackedConsts<TTarget>::VALUES_PER_WORD;
 332         TSize2 new_length = length(source);
 333         if (new_length > new_length_limit)
 334         {
 335                 new_length = new_length_limit;
 336         }
 337         _setLength(target, new_length);
 338 }
 339 template <typename TTarget, typename TSource, typename TSize, typename TTag>
 340 inline void
 341 _assign_copy_packed_string(TTarget & target,
 342                                                    TSource & source,
 343                                                    TSize limit,
 344                                                    Tag<TTag> const tag)
 345 {
 346         typedef typename Size<TTarget>::Type TSize2;
 347
 348         TSize2 host_limit = _PackedConsts<TTarget>::toHostLength(limit);
 349         assign(host(target), host(source), host_limit, tag);
 350         TSize2 new_length_limit = length(host(target)) * _PackedConsts<TTarget>::VALUES_PER_WORD;
 351         TSize2 new_length = length(source);
 352         if (new_length > new_length_limit)
 353         {
 354                 new_length = new_length_limit;
 355         }
 356         if (new_length > limit)
 357         {
 358                 new_length = limit;
 359         }
 360         _setLength(target, new_length);
 361 }
 362 //____________________________________________________________________________
 363
 364 template <typename TValue, typename THostspec, typename TTag>
 365 inline void
 366 assign(String<TValue, Packed<THostspec> > & target,
 367            String<TValue, Packed<THostspec> > & source,
 368            Tag<TTag> const tag)
 369 {
 370         _assign_copy_packed_string(target, source, tag);
 371 }
 372 template <typename TValue, typename THostspec, typename TTag>
 373 inline void
 374 assign(String<TValue, Packed<THostspec> > & target,
 375            String<TValue, Packed<THostspec> > const & source,
 376            Tag<TTag> const tag)
 377 {
 378         _assign_copy_packed_string(target, source, tag);
 379 }
 380
 381 template <typename TValue, typename THostspec, typename TSize, typename TTag>
 382 void assign(String<TValue, Packed<THostspec> > & target,
 383                         String<TValue, Packed<THostspec> > & source,
 384                         TSize limit,
 385                         Tag<TTag> const tag)
 386 {
 387         _assign_copy_packed_string(target, source, limit, tag);
 388 }
 389 template <typename TValue, typename THostspec, typename TSize, typename TTag>
 390 void assign(String<TValue, Packed<THostspec> > & target,
 391                         String<TValue, Packed<THostspec> > const & source,
 392                         TSize limit,
 393                         Tag<TTag> const tag)
 394 {
 395         _assign_copy_packed_string(target, source, limit, tag);
 396 }
 397
 398 //////////////////////////////////////////////////////////////////////////////
 399 //////////////////////////////////////////////////////////////////////////////
 400 // Function
 401 //////////////////////////////////////////////////////////////////////////////
 402
 403 template <typename TValue, typename THostspec>
 404 inline void const *
 405 id(String<TValue, Packed<THostspec> > const & me)
 406 {
 407 SEQAN_CHECKPOINT
 408         return id(host(me));
 409 }
 410
 411 //////////////////////////////////////////////////////////////////////////////
 412
 413 template <typename TValue, typename THostspec, typename TPos, typename TTag>
 414 inline typename Iterator<String<TValue, Packed<THostspec> >, Tag<TTag> const>::Type
 415 iter(String<TValue, Packed<THostspec> > & me,
 416          TPos pos_,
 417          Tag<TTag> const)
 418 {
 419 SEQAN_CHECKPOINT
 420         typedef typename Iterator<String<TValue, Packed<THostspec> >, Tag<TTag> const>::Type TIterator;
 421         return TIterator(me, pos_);
 422 }
 423 template <typename TValue, typename THostspec, typename TPos, typename TTag>
 424 inline typename Iterator<String<TValue, Packed<THostspec> > const, Tag<TTag> const>::Type
 425 iter(String<TValue, Packed<THostspec> > const & me,
 426          TPos pos_,
 427          Tag<TTag> const)
 428 {
 429 SEQAN_CHECKPOINT
 430         typedef typename Iterator<String<TValue, Packed<THostspec> > const, Tag<TTag> const>::Type TIterator;
 431         return TIterator(me, pos_);
 432 }
 433
 434 //////////////////////////////////////////////////////////////////////////////
 435
 436 template <typename TValue, typename THostspec, typename TTag>
 437 inline typename Iterator<String<TValue, Packed<THostspec> >, Tag<TTag> const>::Type
 438 begin(String<TValue, Packed<THostspec> > & me,
 439           Tag<TTag> const tag_)
 440 {
 441 SEQAN_CHECKPOINT
 442         return iter(me, 0, tag_);
 443 }
 444 template <typename TValue, typename THostspec, typename TTag>
 445 inline typename Iterator<String<TValue, Packed<THostspec> > const, Tag<TTag> const>::Type
 446 begin(String<TValue, Packed<THostspec> > const & me,
 447           Tag<TTag> const tag_)
 448 {
 449 SEQAN_CHECKPOINT
 450         return iter(me, 0, tag_);
 451 }
 452
 453 //////////////////////////////////////////////////////////////////////////////
 454 // end
 455 //////////////////////////////////////////////////////////////////////////////
 456
 457 template <typename TValue, typename THostspec, typename TTag>
 458 inline typename Iterator<String<TValue, Packed<THostspec> >, Tag<TTag> const>::Type
 459 end(String<TValue, Packed<THostspec> > & me,
 460         Tag<TTag> const tag_)
 461 {
 462 SEQAN_CHECKPOINT
 463         return iter(me, length(me), tag_);
 464 }
 465 template <typename TValue, typename THostspec, typename TTag>
 466 inline typename Iterator<String<TValue, Packed<THostspec> > const, Tag<TTag> const>::Type
 467 end(String<TValue, Packed<THostspec> > const & me,
 468         Tag<TTag> const tag_)
 469 {
 470 SEQAN_CHECKPOINT
 471         return iter(me, length(me), tag_);
 472 }
 473
 474 //////////////////////////////////////////////////////////////////////////////
 475 // value
 476 //////////////////////////////////////////////////////////////////////////////
 477
 478 template <typename TValue, typename THostspec, typename TPos>
 479 inline typename Reference<String<TValue, Packed<THostspec> > >::Type
 480 value(String<TValue, Packed<THostspec> > & me,
 481           TPos pos)
 482 {
 483 SEQAN_CHECKPOINT
 484
 485         return *iter(me, pos, Standard());
 486 }
 487 template <typename TValue, typename THostspec, typename TPos>
 488 inline typename Reference<String<TValue, Packed<THostspec> > const>::Type
 489 value(String<TValue, Packed<THostspec> > const & me,
 490           TPos pos)
 491 {
 492 SEQAN_CHECKPOINT
 493
 494         return *iter(me, pos, Standard());
 495 }
 496
 497
 498 //////////////////////////////////////////////////////////////////////////////
 499 // capacity
 500 //////////////////////////////////////////////////////////////////////////////
 501
 502 template <typename TValue, typename THostspec>
 503 inline typename Size<String<TValue, Packed<THostspec> > const>::Type
 504 capacity(String<TValue, Packed<THostspec> > const & me)
 505 {
 506 SEQAN_CHECKPOINT
 507         typedef typename Size<String<TValue, Packed<THostspec> > const>::Type TSize;
 508         TSize len = capacity(host(me));
 509         len *= _PackedConsts<String<TValue, Packed<THostspec> > >::VALUES_PER_WORD;
 510         return len;
 511 }
 512
 513 //////////////////////////////////////////////////////////////////////////////
 514 // clear
 515 //////////////////////////////////////////////////////////////////////////////
 516
 517 template <typename TValue, typename THostspec>
 518 inline void
 519 clear(String<TValue, Packed<THostspec> > & me)
 520 {
 521 SEQAN_CHECKPOINT
 522         clear(host(me));
 523         _setLength(me, 0);
 524 }
 525
 526 //////////////////////////////////////////////////////////////////////////////
 527 // _clearSpace
 528 //////////////////////////////////////////////////////////////////////////////
 529
 530 //implementation for all expand tags other than "limit"
 531 template <typename TExpand>
 532 struct _ClearSpace_String_Packed_
 533 {
 534         template <typename T>
 535         static inline typename Size<T>::Type
 536         _clearSpace_(
 537                 T & seq,
 538                 typename Size<T>::Type size)
 539         {
 540 SEQAN_CHECKPOINT
 541                 typedef typename Size<T>::Type TSize;
 542                 TSize wanted_host_length = _PackedConsts<T>::toHostLength(size);
 543                 TSize new_host_length = resize(host(seq), wanted_host_length, TExpand());
 544                 if (new_host_length < wanted_host_length)
 545                 {
 546                         size = new_host_length * _PackedConsts<T>::VALUES_PER_WORD;
 547                 }
 548                 _setLength(seq, size);
 549                 return size;
 550         }
 551
 552         template <typename T>
 553         static inline typename Size<T>::Type
 554         _clearSpace_(
 555                 T & seq,
 556                 typename Size<T>::Type size,
 557                 typename Size<T>::Type limit)
 558         {
 559                 if (limit < size)
 560                 {
 561 SEQAN_CHECKPOINT
 562                         size = limit;
 563                 }
 564                 return _clearSpace_(seq, limit);
 565         }
 566
 567         template <typename T>
 568         static inline typename Size<T>::Type
 569         _clearSpace_(
 570                 T & seq,
 571                 typename Size<T>::Type size,
 572                 typename Size<T>::Type start,
 573                 typename Size<T>::Type end)
 574         {
 575 SEQAN_CHECKPOINT
 576                 return _clearSpace_(seq, size, start, end, supremumValue<typename Size<T>::Type >());
 577         }
 578
 579         template <typename T>
 580         static typename Size<T>::Type
 581         _clearSpace_(
 582                 T & seq,
 583                 typename Size<T>::Type size,
 584                 typename Size<T>::Type start,
 585                 typename Size<T>::Type end,
 586                 typename Size<T>::Type limit)
 587         {
 588 SEQAN_CHECKPOINT
 589 //??? TODO: This function can be accelerated this way:
 590 //                              - move values in host
 591 //                              - avoid double moving of the rest-part if "resize" allocates a new block
 592
 593                 typedef typename Size<T>::Type TSize;
 594                 typedef typename Iterator<T, Standard>::Type TIterator;
 595
 596                 TSize old_length = length(seq);
 597                 TSize old_size = end - start;
 598                 TSize wanted_new_length = old_length + size - old_size;
 599
 600                 if (wanted_new_length > limit)
 601                 {
 602                         wanted_new_length = limit;
 603                 }
 604
 605                 TSize wanted_host_length = _PackedConsts<T>::toHostLength(wanted_new_length);
 606                 TSize new_host_length = resize(host(seq), wanted_host_length, TExpand());
 607
 608                 TSize new_length;
 609                 if (new_host_length < wanted_host_length)
 610                 {
 611                         new_length = new_host_length * _PackedConsts<T>::VALUES_PER_WORD;
 612                         if (new_length <= start + size)
 613                         {
 614                                 goto FINISH;
 615                         }
 616                         old_length = new_length - size + old_size;
 617                 }
 618                 else
 619                 {
 620                         new_length = wanted_new_length;
 621                 }
 622
 623                 //move [end:right_end] to [start + size:..]
 624                 if (old_size > size)
 625                 {//move rest to left
 626                         ::std::copy_backward(iter(seq, end, Standard()), iter(seq, old_length, Standard()), iter(seq,  new_length, Standard()));
 627                 }
 628                 else
 629                 {//move rest to right
 630                         ::std::copy(iter(seq, end, Standard()), iter(seq, old_length, Standard()), iter(seq, end + size - old_size, Standard()));
 631                 }
 632 FINISH:
 633                 _setLength(seq, new_length);
 634                 return size;
 635         }
 636 /*
 637         template <typename T>
 638         static inline typename Size<T>::Type
 639         _clearSpace_(
 640                 T & seq,
 641                 typename Size<T>::Type size,
 642                 typename Iterator<T>::Type start,
 643                 typename Iterator<T>::Type end)
 644         {
 645 SEQAN_CHECKPOINT
 646                 typename Iterator<T>::Type seq_begin = begin(seq);
 647                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, Insist());
 648         }
 649
 650         template <typename T>
 651         static inline typename Size<T>::Type
 652         _clearSpace_(
 653                 T & seq,
 654                 typename Size<T>::Type size,
 655                 typename Iterator<T>::Type start,
 656                 typename Iterator<T>::Type end,
 657                 typename Size<T>::Type limit)
 658         {
 659 SEQAN_CHECKPOINT
 660                 typename Iterator<T>::Type seq_begin = begin(seq);
 661                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, Insist());
 662         }
 663 */
 664 };
 665
 666 //////////////////////////////////////////////////////////////////////////////
 667
 668 template<typename TValue, typename THostspec, typename TExpand>
 669 inline typename Size< String<TValue, Packed<THostspec> > >::Type
 670 _clearSpace(String<TValue, Packed<THostspec> > & me,
 671                 typename Size< String<TValue, Packed<THostspec> > >::Type size,
 672                 Tag<TExpand> const)
 673 {
 674 SEQAN_CHECKPOINT
 675         return _ClearSpace_String_Packed_<Tag<TExpand> const>::_clearSpace_(me, size);
 676 }
 677
 678 template<typename TValue, typename THostspec, typename TExpand>
 679 inline typename Size< String<TValue, Packed<THostspec> > >::Type
 680 _clearSpace(String<TValue, Packed<THostspec> > & me,
 681                 typename Size< String<TValue, Packed<THostspec> > >::Type size,
 682                 typename Size< String<TValue, Packed<THostspec> > >::Type limit,
 683                 Tag<TExpand> const)
 684 {
 685 SEQAN_CHECKPOINT
 686         return _ClearSpace_String_Packed_<Tag<TExpand> const>::_clearSpace_(me, size, limit);
 687 }
 688
 689 template<typename TValue, typename THostspec, typename TPosition, typename TExpand>
 690 inline typename Size< String<TValue, Packed<THostspec> > >::Type
 691 _clearSpace(String<TValue, Packed<THostspec> > & me,
 692                         typename Size< String<TValue, Packed<THostspec> > >::Type size,
 693                         TPosition pos_begin,
 694                         TPosition pos_end,
 695                         Tag<TExpand> const)
 696 {
 697 SEQAN_CHECKPOINT
 698         return _ClearSpace_String_Packed_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end);
 699 }
 700
 701 template<typename TValue, typename THostspec, typename TPosition, typename TExpand>
 702 inline typename Size< String<TValue, Packed<THostspec> > >::Type
 703 _clearSpace(String<TValue, Packed<THostspec> > & me,
 704                         typename Size< String<TValue, Packed<THostspec> > >::Type size,
 705                         TPosition pos_begin,
 706                         TPosition pos_end,
 707                         typename Size< String<TValue, Packed<THostspec> > >::Type limit,
 708                         Tag<TExpand> const)
 709 {
 710 SEQAN_CHECKPOINT
 711         return _ClearSpace_String_Packed_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end, limit);
 712 }
 713
 714
 715 //////////////////////////////////////////////////////////////////////////////
 716
 717
 718 ///.Function.reserve.param.object.type:Spec.Packed String
 719
 720 template <typename TValue, typename TSpec, typename _TSize, typename TExpand>
 721 inline typename Size< String<TValue, Packed<TSpec> > >::Type
 722 reserve(
 723         String<TValue, Packed<TSpec> > & seq,
 724         _TSize new_capacity,
 725         Tag<TExpand> const tag)
 726 {
 727 SEQAN_CHECKPOINT
 728
 729         typedef String<TValue, Packed<TSpec> > TString;
 730         typedef typename Size<TString>::Type TSize;
 731         TSize ret_value = reserve(host(seq), _PackedConsts<TString>::toHostLength(new_capacity), tag);
 732         return ret_value * _PackedConsts<TString>::VALUES_PER_WORD;
 733 }
 734
 735 template <typename TValue, typename TSpec, typename _TSize>
 736 inline typename Size< String<TValue, Alloc<TSpec> > >::Type
 737 reserve(
 738         String<TValue, Packed<TSpec> > & me,
 739         _TSize new_capacity,
 740         Limit)
 741 {
 742 SEQAN_CHECKPOINT
 743         typedef typename Size< String<TValue, Alloc<TSpec> > >::Type TSize;
 744
 745         TSize me_capacity = capacity(me);
 746         if (me_capacity < (TSize)new_capacity) return me_capacity;
 747         return new_capacity;
 748 }
 749
 750 template <typename TValue, typename TSpec, typename _TSize>
 751 inline typename Size< String<TValue, Alloc<TSpec> > >::Type
 752 reserve(
 753         String<TValue, Packed<TSpec> > & me,
 754         _TSize new_capacity,
 755         Insist)
 756 {
 757 SEQAN_CHECKPOINT
 758         typedef typename Size< String<TValue, Alloc<TSpec> > >::Type TSize;
 759
 760         return new_capacity;
 761 }
 762
 763
 764 //////////////////////////////////////////////////////////////////////////////
 765 //////////////////////////////////////////////////////////////////////////////
 766 // Iteration
 767 //////////////////////////////////////////////////////////////////////////////
 768
 769 template <typename TValue, typename THostspec, typename TSpec>
 770 struct Iterator<String<TValue, Packed<THostspec> >, TSpec>
 771 {
 772         typedef Iter<String<TValue, Packed<THostspec> >, Packed<THostspec> > Type;
 773 };
 774 template <typename TValue, typename THostspec, typename TSpec>
 775 struct Iterator<String<TValue, Packed<THostspec> > const, TSpec>
 776 {
 777         typedef Iter<String<TValue, Packed<THostspec> > const, Packed<THostspec> > Type;
 778 };
 779
 780 //////////////////////////////////////////////////////////////////////////////
 781 //////////////////////////////////////////////////////////////////////////////
 782 // Iterator for packed strings
 783 //////////////////////////////////////////////////////////////////////////////
 784
 785 template <typename TContainer, typename THostspec>
 786 class Iter<TContainer, Packed<THostspec> >
 787 {
 788 private:
 789         typedef typename Host<TContainer>::Type THost;
 790         typedef typename Iterator<THost, Standard>::Type THostIterator;
 791         typedef typename Position<TContainer>::Type TPosition;
 792
 793         typename _Pointer<TContainer>::Type data_container;
 794         THostIterator data_iterator;
 795         unsigned char data_bitpos;
 796
 797 //____________________________________________________________________________
 798
 799 public:
 800         Iter()
 801         {
 802 SEQAN_CHECKPOINT
 803         }
 804         Iter(typename _Parameter<TContainer>::Type container_):
 805                 data_container(_toPointer(container_)),
 806                 data_iterator(begin(host(container_))),
 807                 data_bitpos(0)
 808         {
 809 SEQAN_CHECKPOINT
 810         }
 811         Iter(typename _Parameter<TContainer>::Type container_, TPosition pos_):
 812                 data_container(_toPointer(container_))
 813         {
 814 SEQAN_CHECKPOINT
 815                 setPosition(*this, pos_);
 816         }
 817         Iter(Iter const & other_):
 818                 data_container(other_.data_container),
 819                 data_iterator(other_.data_iterator),
 820                 data_bitpos(other_.data_bitpos)
 821         {
 822 SEQAN_CHECKPOINT
 823         }
 824         ~Iter()
 825         {
 826 SEQAN_CHECKPOINT
 827         }
 828         Iter const &
 829         operator = (Iter const & other_)
 830         {
 831 SEQAN_CHECKPOINT
 832                 data_container = other_.data_container;
 833                 data_iterator = other_.data_iterator;
 834                 data_bitpos = other_.data_bitpos;
 835                 return *this;
 836         }
 837 //____________________________________________________________________________
 838
 839         friend inline typename _Parameter<TContainer>::Type
 840         container(Iter & me)
 841         {
 842 SEQAN_CHECKPOINT
 843                 return _toParameter<TContainer>(me.data_container);
 844         }
 845         friend inline typename _Parameter<TContainer>::Type
 846         container(Iter const & me)
 847         {
 848 SEQAN_CHECKPOINT
 849                 return _toParameter<TContainer>(me.data_container);
 850         }
 851 //____________________________________________________________________________
 852
 853         friend inline void
 854         setContainer(Iter & me, typename _Parameter<TContainer>::Type container_)
 855         {
 856 SEQAN_CHECKPOINT
 857                 typename Position<Iter>::Type pos = position(me);
 858                 me.data_container = _toPointer(container_);
 859                 setPosition(me, pos);
 860         }
 861
 862 //____________________________________________________________________________
 863
 864         friend inline THostIterator &
 865         hostIterator(Iter & me)
 866         {
 867 SEQAN_CHECKPOINT
 868                 return me.data_iterator;
 869         }
 870         friend inline THostIterator const &
 871         hostIterator(Iter const & me)
 872         {
 873 SEQAN_CHECKPOINT
 874                 return me.data_iterator;
 875         }
 876
 877 //____________________________________________________________________________
 878
 879         friend inline unsigned char &
 880         _bitpos(Iter & me)
 881         {
 882 SEQAN_CHECKPOINT
 883                 return me.data_bitpos;
 884         }
 885         friend inline unsigned char
 886         _bitpos(Iter const & me)
 887         {
 888 SEQAN_CHECKPOINT
 889                 return me.data_bitpos;
 890         }
 891
 892 //____________________________________________________________________________
 893 };
 894
 895 //////////////////////////////////////////////////////////////////////////////
 896 // position
 897 //////////////////////////////////////////////////////////////////////////////
 898
 899 template <typename TContainer, typename THostspec>
 900 inline typename Position<Iter<TContainer, Packed<THostspec> > const>::Type
 901 position(Iter<TContainer, Packed<THostspec> > const & me)
 902 {
 903 SEQAN_CHECKPOINT
 904         typedef typename Host<TContainer>::Type THost;
 905         THost const & host_ = host(container(me));
 906         return (hostIterator(me) - begin(host_)) * _PackedConsts<TContainer>::VALUES_PER_WORD + _bitpos(me) / _PackedConsts<TContainer>::BITS_PER_VALUE;
 907 }
 908
 909 //////////////////////////////////////////////////////////////////////////////
 910 // setPosition
 911 //////////////////////////////////////////////////////////////////////////////
 912
 913 template <typename TContainer, typename THostspec, typename TPosition>
 914 inline void
 915 setPosition(Iter<TContainer, Packed<THostspec> > & me,
 916                         TPosition pos_)
 917 {
 918 SEQAN_CHECKPOINT
 919         hostIterator(me) = begin(host(container(me))) + pos_ / _PackedConsts<TContainer>::VALUES_PER_WORD;
 920         _bitpos(me) = (pos_ % _PackedConsts<TContainer>::VALUES_PER_WORD) * _PackedConsts<TContainer>::BITS_PER_VALUE;
 921 }
 922
 923 //////////////////////////////////////////////////////////////////////////////
 924 // value
 925 //////////////////////////////////////////////////////////////////////////////
 926
 927 template <typename TContainer, typename THostspec>
 928 inline typename Reference<Iter<TContainer, Packed<THostspec> > >::Type
 929 value(Iter<TContainer, Packed<THostspec> > & me)
 930 {
 931 SEQAN_CHECKPOINT
 932         return typename Reference<Iter<TContainer, Packed<THostspec> > >::Type(me);
 933 }
 934 template <typename TContainer, typename THostspec>
 935 inline typename Reference<Iter<TContainer, Packed<THostspec> > const>::Type
 936 value(Iter<TContainer, Packed<THostspec> > const & me)
 937 {
 938 SEQAN_CHECKPOINT
 939         return typename Reference<Iter<TContainer, Packed<THostspec> > const>::Type(me);
 940 }
 941
 942 //////////////////////////////////////////////////////////////////////////////
 943 // getValue
 944 //////////////////////////////////////////////////////////////////////////////
 945
 946 template <typename TContainer, typename THostspec>
 947 inline typename GetValue<Iter<TContainer, Packed<THostspec> > >::Type
 948 getValue(Iter<TContainer, Packed<THostspec> > & me)
 949 {
 950 SEQAN_CHECKPOINT
 951         return (value(hostIterator(me)) >> _bitpos(me)) & _PackedConsts<TContainer>::VALUE_MASK;
 952 }
 953 template <typename TContainer, typename THostspec>
 954 inline typename GetValue<Iter<TContainer, Packed<THostspec> > const>::Type
 955 getValue(Iter<TContainer, Packed<THostspec> > const & me)
 956 {
 957 SEQAN_CHECKPOINT
 958         return (value(hostIterator(me)) >> _bitpos(me)) & _PackedConsts<TContainer>::VALUE_MASK;
 959 }
 960
 961 /////////////////////////////////////////////////////////////////////////////
 962 // assignValue
 963 //////////////////////////////////////////////////////////////////////////////
 964
 965 template <typename TIter, typename TValue>
 966 inline void
 967 _assignValue_packed_string_iterator(TIter & me,
 968                                                                         TValue & _value)
 969 {
 970         typedef typename Container<TIter>::Type TContainer;
 971         typedef typename Host<TContainer>::Type THost;
 972         typedef typename Value<THost>::Type THostValue;
 973         THostValue mask_ = _PackedConsts<TContainer>::VALUE_MASK << _bitpos(me);
 974         THostValue val_ = _value;
 975         val_ <<= _bitpos(me);
 976
 977         assignValue(hostIterator(me), (getValue(hostIterator(me)) & ~(mask_)) | val_);
 978 }
 979
 980
 981 template <typename TContainer, typename THostspec, typename TValue>
 982 inline void
 983 assignValue(Iter<TContainer, Packed<THostspec> > & me,
 984                         TValue const & _value)
 985 {
 986 SEQAN_CHECKPOINT
 987         typedef Iter<TContainer, Packed<THostspec> > TIterator;
 988         typename Value<TIterator>::Type _temp_value = _value; //conversion
 989         _assignValue_packed_string_iterator(me, _temp_value);
 990 }
 991 template <typename TContainer, typename THostspec, typename TValue>
 992 inline void
 993 assignValue(Iter<TContainer, Packed<THostspec> > const & me,
 994                         TValue const & _value)
 995 {
 996 SEQAN_CHECKPOINT
 997         typedef Iter<TContainer, Packed<THostspec> > const TIterator;
 998         typename Value<TIterator>::Type _temp_value = _value; //conversion
 999         _assignValue_packed_string_iterator(me, _temp_value);
1000 }
1001
1002 /////////////////////////////////////////////////////////////////////////////
1003 // moveValue
1004 //////////////////////////////////////////////////////////////////////////////
1005
1006 template <typename TContainer, typename THostspec, typename TValue>
1007 inline void
1008 moveValue(Iter<TContainer, Packed<THostspec> > & me,
1009                   TValue const & _value)
1010 {
1011 SEQAN_CHECKPOINT
1012         assignValue(me, _value);
1013 }
1014 template <typename TContainer, typename THostspec, typename TValue>
1015 inline void
1016 moveValue(Iter<TContainer, Packed<THostspec> > const & me,
1017                   TValue const & _value)
1018 {
1019 SEQAN_CHECKPOINT
1020         assignValue(me, _value);
1021 }
1022
1023 //////////////////////////////////////////////////////////////////////////////
1024 // valueConstruct
1025 //////////////////////////////////////////////////////////////////////////////
1026 //emulate construction and destruction
1027
1028 template <typename TContainer, typename THostspec>
1029 inline void
1030 valueConstruct(Iter<TContainer, Packed<THostspec> > const & /*it*/)
1031 {
1032 }
1033 template <typename TContainer, typename THostspec, typename TParam>
1034 inline void
1035 valueConstruct(Iter<TContainer, Packed<THostspec> > const & it,
1036                            TParam const & param_)
1037 {
1038         assignValue(it, param_);
1039 }
1040 template <typename TContainer, typename THostspec, typename TParam>
1041 inline void
1042 valueConstruct(Iter<TContainer, Packed<THostspec> > const & it,
1043                            TParam const & param_,
1044                            Move tag)
1045 {
1046         moveValue(it, param_);
1047 }
1048
1049 //////////////////////////////////////////////////////////////////////////////
1050 // valueDestruct
1051 //////////////////////////////////////////////////////////////////////////////
1052
1053 template <typename TContainer, typename THostspec>
1054 inline void
1055 valueDestruct(Iter<TContainer, Packed<THostspec> > const & /*it*/)
1056 {
1057 }
1058
1059 //////////////////////////////////////////////////////////////////////////////
1060 // operator ==
1061 //////////////////////////////////////////////////////////////////////////////
1062
1063 template <typename TContainer, typename THostspec>
1064 inline bool
1065 operator == (Iter<TContainer, Packed<THostspec> > const & left,
1066                          Iter<TContainer, Packed<THostspec> > const & right)
1067 {
1068 SEQAN_CHECKPOINT
1069         return (hostIterator(left) == hostIterator(right)) && (_bitpos(left) == _bitpos(right));
1070 }
1071
1072 //////////////////////////////////////////////////////////////////////////////
1073 // operator !=
1074 //////////////////////////////////////////////////////////////////////////////
1075
1076 template <typename TContainer, typename THostspec>
1077 inline bool
1078 operator != (Iter<TContainer, Packed<THostspec> > const & left,
1079                          Iter<TContainer, Packed<THostspec> > const & right)
1080 {
1081 SEQAN_CHECKPOINT
1082         return (hostIterator(left) != hostIterator(right)) || (_bitpos(left) != _bitpos(right));
1083 }
1084
1085 //////////////////////////////////////////////////////////////////////////////
1086 // operator >
1087 //////////////////////////////////////////////////////////////////////////////
1088
1089 template <typename TContainer, typename THostspec>
1090 inline bool
1091 operator > (Iter<TContainer, Packed<THostspec> > const & left,
1092                         Iter<TContainer, Packed<THostspec> > const & right)
1093 {
1094 SEQAN_CHECKPOINT
1095         return (hostIterator(left) > hostIterator(right)) || ((hostIterator(left) == hostIterator(right)) && (_bitpos(left) > _bitpos(right)));
1096 }
1097
1098 //////////////////////////////////////////////////////////////////////////////
1099 // operator >=
1100 //////////////////////////////////////////////////////////////////////////////
1101
1102 template <typename TContainer, typename THostspec>
1103 inline bool
1104 operator >= (Iter<TContainer, Packed<THostspec> > const & left,
1105                          Iter<TContainer, Packed<THostspec> > const & right)
1106 {
1107 SEQAN_CHECKPOINT
1108         return (hostIterator(left) > hostIterator(right)) || ((hostIterator(left) == hostIterator(right)) && (_bitpos(left) >= _bitpos(right)));
1109 }
1110
1111 //////////////////////////////////////////////////////////////////////////////
1112 // operator <
1113 //////////////////////////////////////////////////////////////////////////////
1114
1115 template <typename TContainer, typename THostspec>
1116 inline bool
1117 operator < (Iter<TContainer, Packed<THostspec> > const & left,
1118                         Iter<TContainer, Packed<THostspec> > const & right)
1119 {
1120 SEQAN_CHECKPOINT
1121         return (hostIterator(left) < hostIterator(right)) || ((hostIterator(left) == hostIterator(right)) && (_bitpos(left) < _bitpos(right)));
1122 }
1123
1124 //////////////////////////////////////////////////////////////////////////////
1125 // operator <=
1126 //////////////////////////////////////////////////////////////////////////////
1127
1128 template <typename TContainer, typename THostspec>
1129 inline bool
1130 operator <= (Iter<TContainer, Packed<THostspec> > const & left,
1131                          Iter<TContainer, Packed<THostspec> > const & right)
1132 {
1133 SEQAN_CHECKPOINT
1134         return (hostIterator(left) < hostIterator(right)) || ((hostIterator(left) == hostIterator(right)) && (_bitpos(left) <= _bitpos(right)));
1135 }
1136
1137 //////////////////////////////////////////////////////////////////////////////
1138 // goNext
1139 //////////////////////////////////////////////////////////////////////////////
1140
1141 template <typename TContainer, typename THostspec>
1142 inline void
1143 goNext(Iter<TContainer, Packed<THostspec> > & me)
1144 {
1145 SEQAN_CHECKPOINT
1146         int new_bitpos = _bitpos(me) + _PackedConsts<TContainer>::BITS_PER_VALUE;
1147         if (new_bitpos <= _PackedConsts<TContainer>::MAX_BIT_POS)
1148         {
1149                 _bitpos(me) = (unsigned char) new_bitpos;
1150         }
1151         else
1152         {
1153                 _bitpos(me) = 0;
1154                 goNext(hostIterator(me));
1155         }
1156 }
1157
1158 //////////////////////////////////////////////////////////////////////////////
1159 // goPrevious
1160 //////////////////////////////////////////////////////////////////////////////
1161
1162 template <typename TContainer, typename THostspec>
1163 inline void
1164 goPrevious(Iter<TContainer, Packed<THostspec> > & me)
1165 {
1166 SEQAN_CHECKPOINT
1167         int new_bitpos = _bitpos(me) - _PackedConsts<TContainer>::BITS_PER_VALUE;
1168         if (new_bitpos >= 0)
1169         {
1170                 _bitpos(me) = (unsigned char) new_bitpos;
1171         }
1172         else
1173         {
1174                 _bitpos(me) = _PackedConsts<TContainer>::MAX_BIT_POS;
1175                 goPrevious(hostIterator(me));
1176         }
1177
1178         goPrevious(hostIterator(me));
1179 }
1180
1181 //////////////////////////////////////////////////////////////////////////////
1182 // operator +
1183 //////////////////////////////////////////////////////////////////////////////
1184
1185 template <typename TContainer, typename THostspec, typename TIntegral>
1186 inline Iter<TContainer, Packed<THostspec> >
1187 operator + (Iter<TContainer, Packed<THostspec> > const & left,
1188                         TIntegral right)
1189 {
1190 SEQAN_CHECKPOINT
1191         return Iter<TContainer, Packed<THostspec> >(container(left), position(left) + right);
1192 }
1193 template <typename TContainer, typename THostspec, typename TIntegral>
1194 inline Iter<TContainer, Packed<THostspec> >
1195 operator + (TIntegral left,
1196                         Iter<TContainer, Packed<THostspec> > const & right)
1197 {
1198 SEQAN_CHECKPOINT
1199         return Iter<TContainer, Packed<THostspec> >(container(right), position(right) + left);
1200 }
1201
1202 //////////////////////////////////////////////////////////////////////////////
1203 // operator +=
1204 //////////////////////////////////////////////////////////////////////////////
1205
1206 template <typename TContainer, typename THostspec, typename TIntegral>
1207 inline Iter<TContainer, Packed<THostspec> > &
1208 operator += (Iter<TContainer, Packed<THostspec> > & left,
1209                          TIntegral right)
1210 {
1211 SEQAN_CHECKPOINT
1212         setPosition(left, position(left) + right);
1213         return left;
1214 }
1215
1216 //////////////////////////////////////////////////////////////////////////////
1217 // operator -
1218 //////////////////////////////////////////////////////////////////////////////
1219
1220 template <typename TContainer, typename THostspec, typename TIntegral>
1221 inline Iter<TContainer, Packed<THostspec> >
1222 operator - (Iter<TContainer, Packed<THostspec> > const & left,
1223                         TIntegral right)
1224 {
1225 SEQAN_CHECKPOINT
1226         return Iter<TContainer, AdaptorIterator<THostspec> >(container(left), position(left) - right);
1227 }
1228
1229 //____________________________________________________________________________
1230
1231 template <typename TContainer, typename THostspec>
1232 inline typename Difference<Iter<TContainer, Packed<THostspec> > >::Type
1233 operator - (Iter<TContainer, Packed<THostspec> > const & left,
1234                         Iter<TContainer, Packed<THostspec> > const & right)
1235 {
1236 SEQAN_CHECKPOINT
1237         return position(left) - position(right);
1238 }
1239
1240 //////////////////////////////////////////////////////////////////////////////
1241 // operator -=
1242 //////////////////////////////////////////////////////////////////////////////
1243
1244 template <typename TContainer, typename THostspec, typename TIntegral>
1245 inline Iter<TContainer, Packed<THostspec> > &
1246 operator -= (Iter<TContainer, Packed<THostspec> > & left,
1247                          TIntegral right)
1248 {
1249 SEQAN_CHECKPOINT
1250         setPosition(left, position(left) - right);
1251         return left;
1252 }
1253
1254 //////////////////////////////////////////////////////////////////////////////
1255
1256
1257
1258 //////////////////////////////////////////////////////////////////////////////
1259
1260 } //namespace SEQAN_NAMESPACE_MAIN
1261
1262 #endif //#ifndef SEQAN_HEADER_...