1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de> 33 // ========================================================================== 34 // Journaled String implementation. 35 // ========================================================================== 36 37 // TODO(holtgrew): Journaled strings will probably not work for non-POD alphabets! 38 39 #ifndef SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_H_ 40 #define SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_H_ 41 42 namespace seqan { 43 44 // ============================================================================ 45 // Forwards 46 // ============================================================================ 47 48 // ============================================================================ 49 // Tags, Classes 50 // ============================================================================ 51 52 // ---------------------------------------------------------------------------- 53 // Specialization Journaled String 54 // ---------------------------------------------------------------------------- 55 56 /*! 57 * @class JournaledString 58 * @extends String 59 * @headerfile <seqan/sequence_journaled.h> 60 * @brief Journaled versions of arbitrary underlying strings. 61 * 62 * @signature template <typename TValue, typename THostSpec[, typename TJournalSpec[, typename TBufferSpec]]> 63 * class String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >; 64 * 65 * @tparam TValue The element type of the string. 66 * @tparam THostSpec Specialization type for the host string. 67 * @tparam TJournalSpec Specialization type for the journal. Default: <tt>SortedArray</tt>. 68 * @tparam TBufferSpec Specialization type for the buffer string. Default: <tt>Alloc<></tt>. 69 */ 70 71 template <typename THostSpec, typename TJournalSpec = SortedArray, typename TBufferSpec = Alloc<void> > 72 struct Journaled {}; 73 74 template <typename TValue_, typename THostSpec_, typename TJournalSpec_, typename TBufferSpec_> 75 class String<TValue_, Journaled<THostSpec_, TJournalSpec_, TBufferSpec_> > 76 { 77 public: 78 typedef String<TValue_, Journaled<THostSpec_, TJournalSpec_, TBufferSpec_> > TThis_; 79 80 typedef TValue_ TValue; 81 typedef THostSpec_ THostSpec; 82 typedef TJournalSpec_ TJournalSpec; 83 typedef TBufferSpec_ TBufferSpec; 84 85 typedef String<TValue, THostSpec> THost; 86 typedef typename Size<THost>::Type TSize; 87 typedef typename Position<THost>::Type TPosition; 88 typedef String<TValue, TBufferSpec> TInsertionBuffer; 89 typedef JournalEntry<TSize, TPosition> TJournalEntry; 90 typedef JournalEntries<TJournalEntry, TJournalSpec> TJournalEntries; 91 92 // The underlying host string. 93 Holder<THost> _holder; 94 // A buffer for inserted strings. 95 TInsertionBuffer _insertionBuffer; 96 // The journal is a sorted set of TJournalEntry objects, the exact types 97 // depends on TJournalSpec. Note that the entries resemble a partial 98 // sum datastructure. 99 TJournalEntries _journalEntries; 100 // The journaled string's size. 101 TSize _length; 102 String()103 String() : _length(0) 104 {} 105 106 // Note: Defining both, constructors from same type and other for clarity. 107 String(THost & host)108 String(THost & host) : _length(0) 109 { 110 SEQAN_CHECKPOINT; 111 setHost(*this, host); 112 } 113 String(String const & other)114 String(String const & other) : _length(0) 115 { 116 SEQAN_CHECKPOINT; 117 set(*this, other); 118 } 119 120 template <typename TString> String(TString const & other)121 String(TString const & other) : _length(0) 122 { 123 SEQAN_CHECKPOINT; 124 assign(*this, other); 125 } 126 127 String & operator=(String const & other) 128 { 129 if (this != &other) 130 set(*this, other); 131 return *this; 132 } 133 134 template <typename TString> 135 String & operator=(TString const & other) 136 { 137 SEQAN_CHECKPOINT; 138 assign(*this, other); 139 return *this; 140 } 141 142 typename Reference<String>::Type 143 operator[](TPosition pos) 144 { 145 SEQAN_CHECKPOINT; 146 return value(*this, pos); 147 } 148 149 typename Reference<String const>::Type 150 operator[](TPosition pos) const 151 { 152 SEQAN_CHECKPOINT; 153 return value(*this, pos); 154 } 155 }; 156 157 // ============================================================================ 158 // Metafunctions 159 // ============================================================================ 160 161 // ---------------------------------------------------------------------------- 162 // Metafunction StringSpec 163 // ---------------------------------------------------------------------------- 164 165 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 166 struct Spec<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 167 { 168 typedef TJournalSpec Type; 169 }; 170 171 // ---------------------------------------------------------------------------- 172 // Metafunction StringSpec 173 // ---------------------------------------------------------------------------- 174 175 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 176 struct StringSpec<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 177 { 178 typedef TBufferSpec Type; 179 }; 180 181 // ---------------------------------------------------------------------------- 182 // Metafunction Host 183 // ---------------------------------------------------------------------------- 184 185 /*! 186 * @mfn JournaledString#Host 187 * @brief The host type. 188 * 189 * @signature Host<TJournaledString>::Type; 190 * 191 * @tparam TJournaledString The JournaldString to get the host type for. 192 * 193 * @return Type The host type. 194 */ 195 196 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 197 struct Host<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 198 { 199 typedef String<TValue, THostSpec> Type; 200 }; 201 202 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 203 struct Host<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 204 { 205 typedef String<TValue, THostSpec> const Type; 206 }; 207 208 // ---------------------------------------------------------------------------- 209 // Metafunction InsertionBuffer 210 // ---------------------------------------------------------------------------- 211 212 /*! 213 * @mfn JournaledString#InsertionBuffer 214 * @brief Return type of insertion buffer string for a journaled string. 215 * 216 * @signature InsertionBuffer<TJournaledString>::Type; 217 * 218 * @tparam TJournaledString The journaled string to get the insertion buffer type for. 219 * 220 * @return Type The insertion buffer type. 221 */ 222 223 template <typename T> 224 struct InsertionBuffer; 225 226 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 227 struct InsertionBuffer<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 228 { 229 typedef String<TValue, TBufferSpec> Type; 230 }; 231 232 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 233 struct InsertionBuffer<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 234 { 235 typedef String<TValue, TBufferSpec> const Type; 236 }; 237 238 // ---------------------------------------------------------------------------- 239 // Metafunction Size 240 // ---------------------------------------------------------------------------- 241 242 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 243 struct Size<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 244 { 245 typedef typename String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >::TSize Type; 246 }; 247 248 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 249 struct Size<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 250 : Size<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > {}; 251 252 // ---------------------------------------------------------------------------- 253 // Metafunction Position 254 // ---------------------------------------------------------------------------- 255 256 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 257 struct Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 258 { 259 typedef typename String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >::TPosition Type; 260 }; 261 262 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 263 struct Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 264 : Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > {}; 265 266 // ---------------------------------------------------------------------------- 267 // Metafunction Reference 268 // ---------------------------------------------------------------------------- 269 270 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 271 struct Reference<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 272 { 273 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TJournaledString; 274 typedef typename Iterator<TJournaledString>::Type TIterator_; 275 typedef Proxy<IteratorProxy<TIterator_> > TProxy_; 276 typedef TProxy_ Type; 277 }; 278 279 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 280 struct Reference<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 281 { 282 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const TJournaledString; 283 typedef typename Iterator<TJournaledString>::Type TIterator_; 284 typedef Proxy<IteratorProxy<TIterator_> > TProxy_; 285 typedef TProxy_ Type; 286 }; 287 288 // ---------------------------------------------------------------------------- 289 // Metafunction GetValue 290 // ---------------------------------------------------------------------------- 291 292 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 293 struct GetValue<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 294 { 295 typedef TValue Type; 296 }; 297 298 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 299 struct GetValue<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 300 { 301 typedef TValue Type; 302 }; 303 304 // ---------------------------------------------------------------------------- 305 // Metafunction Value 306 // ---------------------------------------------------------------------------- 307 308 // TODO(holtgrew): Does Value have to be overwritten? Is not for packed strings! 309 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 310 struct Value<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 311 { 312 typedef TValue Type; 313 }; 314 315 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 316 struct Value<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 317 { 318 typedef TValue const Type; 319 }; 320 321 // ---------------------------------------------------------------------------- 322 // Metafunction JournalType 323 // ---------------------------------------------------------------------------- 324 325 /*! 326 * @mfn JournaledString#JournalType 327 * @brief Query a JournaledString for its journal type. 328 * 329 * @signature JournalType<TJournaledString>::Type; 330 * 331 * @tparam TJournaledString The JournaledString to query. 332 * 333 * @return Type the journal type. 334 */ 335 336 template <typename T> 337 struct JournalType; 338 339 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 340 struct JournalType<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > > 341 { 342 typedef typename Size<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type TSize_; 343 typedef typename Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type TPosition_; 344 typedef JournalEntry<TSize_, TPosition_> TJournalEntry_; 345 346 typedef JournalEntries<TJournalEntry_, TJournalSpec> Type; 347 }; 348 349 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 350 struct JournalType<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const> 351 { 352 typedef typename JournalType<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type const Type; 353 }; 354 355 // ============================================================================ 356 // Functions 357 // ============================================================================ 358 359 // ---------------------------------------------------------------------------- 360 // Function empty() 361 // ---------------------------------------------------------------------------- 362 363 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 364 inline bool 365 empty(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & target) 366 { 367 if (empty(target._holder) || empty(target._journalEntries)) 368 return true; 369 370 return begin(target, Standard()) == end(target, Standard()); 371 } 372 373 // ---------------------------------------------------------------------------- 374 // Function operator<< 375 // ---------------------------------------------------------------------------- 376 377 template <typename TStream, typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 378 inline 379 TStream & 380 operator<<(TStream & stream, String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & s) 381 { 382 SEQAN_CHECKPOINT; 383 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TString; 384 typedef typename TString::TJournalEntries TJournalEntries; 385 typedef typename Iterator<TJournalEntries const, Standard>::Type TIterator; 386 387 for (TIterator it = begin(s._journalEntries), itend = end(s._journalEntries); it != itend; ++it) { 388 if (value(it).segmentSource == SOURCE_ORIGINAL) { 389 stream << infix(value(s._holder), value(it).physicalPosition, value(it).physicalPosition + value(it).length); 390 } else { 391 SEQAN_ASSERT_EQ(value(it).segmentSource, SOURCE_PATCH); 392 stream << infix(s._insertionBuffer, value(it).physicalPosition, value(it).physicalPosition + value(it).length); 393 } 394 } 395 return stream; 396 } 397 398 // ---------------------------------------------------------------------------- 399 // Function assign 400 // ---------------------------------------------------------------------------- 401 402 // Assignment of two identical journaled strings. 403 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, 404 typename TExpand> 405 inline void 406 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 407 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & source, 408 Tag<TExpand> /*tag*/) 409 { 410 set(target, source); 411 } 412 413 414 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 415 inline void 416 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 417 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & source) 418 { 419 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TTarget; 420 assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type()); 421 } 422 423 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, 424 typename TExpand> 425 inline void 426 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 427 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & source, 428 Tag<TExpand>) 429 { 430 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TSource; 431 assign(target, static_cast<TSource const &>(source), Tag<TExpand>()); 432 } 433 434 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 435 inline void 436 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 437 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & source) 438 { 439 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TTarget; 440 assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type()); 441 } 442 443 // Assignment of a journaled string with another string type always resizes the 444 // insertion buffer and copies the contents of source into the insertion buffer. 445 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TSource> 446 inline void 447 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 448 TSource const & source) 449 { 450 SEQAN_CHECKPOINT; 451 clear(target); 452 replace(target, 0, length(target), source); 453 } 454 455 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TSource> 456 inline void 457 assign(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 458 TSource & source) 459 { 460 SEQAN_CHECKPOINT; 461 assign(target, static_cast<TSource const &>(source)); 462 } 463 464 // ---------------------------------------------------------------------------- 465 // Function set 466 // ---------------------------------------------------------------------------- 467 468 // Setting a journaled string to another journaled string copies over the deep 469 // structure. For all other cases, it is assign(). 470 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 471 inline 472 void 473 set(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 474 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & source) 475 { 476 SEQAN_CHECKPOINT; 477 assign(target._holder, source._holder); 478 assign(target._insertionBuffer, source._insertionBuffer); 479 assign(target._journalEntries, source._journalEntries); 480 assign(target._length, source._length); 481 } 482 483 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 484 inline 485 void 486 set(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 487 String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & source) 488 { 489 SEQAN_CHECKPOINT; 490 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TJournaledString; 491 set(target, static_cast<TJournaledString const &>(source)); 492 } 493 494 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TSource> 495 inline 496 void 497 set(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & target, 498 TSource const & source) 499 { 500 SEQAN_CHECKPOINT; 501 assign(target, source); 502 } 503 504 // ---------------------------------------------------------------------------- 505 // Function setHost 506 // ---------------------------------------------------------------------------- 507 508 /*! 509 * @fn JournaledString#setHost 510 * @brief Set the host of a JournaledString. 511 * 512 * @signature void setHost(js, str); 513 * 514 * @param[in,out] js The JournaledString to set the host for. 515 * @param[in] str The string to set as the host. 516 */ 517 518 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TSequence2> 519 inline 520 void 521 setHost(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, TSequence2 & str) 522 { 523 SEQAN_CHECKPOINT; 524 setValue(journaledString._holder, str); 525 journaledString._length = length(str); 526 reinit(journaledString._journalEntries, length(str)); 527 } 528 529 // ---------------------------------------------------------------------------- 530 // Function host 531 // ---------------------------------------------------------------------------- 532 533 /*! 534 * @fn JournaledString#host 535 * @brief Return the host of a JournaledString. 536 * 537 * @signature THost host(js); 538 * 539 * @param[in] js The JournaledString to query. 540 * 541 * @return THost Reference to the host of <tt>js</tt>. 542 */ 543 544 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 545 inline 546 typename Host<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type & 547 host(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 548 { 549 SEQAN_CHECKPOINT; 550 return value(journaledString._holder); 551 } 552 553 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 554 inline 555 typename Host<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type const & 556 host(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString) 557 { 558 SEQAN_CHECKPOINT; 559 return value(journaledString._holder); 560 } 561 562 // ---------------------------------------------------------------------------- 563 // Function clear 564 // ---------------------------------------------------------------------------- 565 566 /*! 567 * @fn JournaledString#clear 568 * @brief Remove all changes from the journal, resetting the JournaledString to its state after construction. 569 * 570 * @signature void clear(js); 571 * 572 * @param[in,out] js The JournaledString to clear. 573 */ 574 575 // TODO(holtgrew): Behaviour is to clear the journal, not the string! 576 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 577 inline void 578 clear(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 579 { 580 SEQAN_CHECKPOINT; 581 reinit(journaledString._journalEntries, length(host(journaledString))); 582 clear(journaledString._insertionBuffer); 583 _setLength(journaledString, length(host(journaledString))); 584 } 585 586 // ---------------------------------------------------------------------------- 587 // Function reset 588 // ---------------------------------------------------------------------------- 589 590 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 591 inline void 592 reset(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 593 { 594 clear(journaledString._holder); 595 clear(journaledString._insertionBuffer); 596 clear(journaledString._journalEntries); 597 _setLength(journaledString, 0u); 598 } 599 600 // ---------------------------------------------------------------------------- 601 // Function flatten 602 // ---------------------------------------------------------------------------- 603 604 /*! 605 * @fn JournaledString#flatten 606 * @brief Apply the journal to the underlying string, modifying the underlying string. 607 * 608 * @signature void flatten(js); 609 * 610 * @param[in,out] js The JournaledString to flatten. 611 */ 612 613 // TODO(holtgrew): What about non-destructive version that creates a new copy and sets holder to it? 614 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 615 inline void 616 flatten(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 617 { 618 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > TJournalString; 619 typedef typename Host<TJournalString>::Type THost; 620 typedef typename Position<TJournalString>::Type TPosition; 621 typedef typename JournalType<TJournalString>::Type TJournalEntries; 622 typedef typename Iterator<TJournalEntries>::Type TEntriesIterator; 623 624 TEntriesIterator it = end(journaledString._journalEntries); 625 TEntriesIterator itBegin = begin(journaledString._journalEntries); 626 627 TPosition lastRefPos = length(host(journaledString)); 628 while (it != itBegin) 629 { 630 --it; 631 if (value(it).segmentSource == SOURCE_ORIGINAL) 632 { 633 // Check for a deletion and if there is one then erase this part from reference. 634 if ((value(it).physicalPosition + value(it).length) < lastRefPos) 635 erase(host(journaledString), value(it).physicalPosition + value(it).length, lastRefPos); 636 lastRefPos = value(it).physicalPosition; 637 } 638 else if (value(it).segmentSource == SOURCE_PATCH) 639 { 640 insert(host(journaledString), 641 lastRefPos, 642 THost(infix(journaledString._insertionBuffer, value(it).physicalPosition, 643 value(it).physicalPosition + value(it).length))); 644 } 645 } 646 // Handle deletion at beginning of reference. 647 SEQAN_ASSERT_GEQ(lastRefPos, (TPosition) 0); 648 if (0 != lastRefPos) 649 erase(host(journaledString), (TPosition) 0, lastRefPos); 650 // After transmitting the journaled differences to the reference clear the insertion buffer and reset everything. 651 clear(journaledString); 652 } 653 654 655 // ---------------------------------------------------------------------------- 656 // Function erase 657 // ---------------------------------------------------------------------------- 658 659 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TBeginPos, typename TEndPos> 660 inline void 661 erase(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 662 TBeginPos pos, 663 TEndPos posEnd) 664 { 665 SEQAN_CHECKPOINT; 666 SEQAN_ASSERT_GEQ(static_cast<TBeginPos>(journaledString._length), pos); 667 SEQAN_ASSERT_GEQ(static_cast<TEndPos>(journaledString._length), posEnd); 668 SEQAN_ASSERT_GEQ(static_cast<TBeginPos>(journaledString._length), static_cast<TBeginPos>(posEnd - pos)); 669 journaledString._length -= posEnd - pos; 670 recordErase(journaledString._journalEntries, pos, posEnd); 671 if (length(journaledString._journalEntries) == 0) 672 clear(journaledString._insertionBuffer); 673 } 674 675 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 676 inline void 677 erase(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 678 TPos pos) 679 { 680 SEQAN_CHECKPOINT; 681 SEQAN_ASSERT_GEQ(journaledString._length, 1u); 682 erase(journaledString, pos, pos + 1); 683 } 684 685 // ---------------------------------------------------------------------------- 686 // Function insert 687 // ---------------------------------------------------------------------------- 688 689 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TString, typename TPos> 690 inline void 691 insert(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 692 TPos pos, 693 TString const & seq) 694 { 695 SEQAN_CHECKPOINT; 696 journaledString._length += length(seq); 697 TPos beginPos = length(journaledString._insertionBuffer); 698 append(journaledString._insertionBuffer, seq); 699 recordInsertion(journaledString._journalEntries, pos, beginPos, length(seq)); 700 } 701 702 // ---------------------------------------------------------------------------- 703 // Function insertValue 704 // ---------------------------------------------------------------------------- 705 706 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos, typename TValue2> 707 inline void 708 insertValue(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 709 TPos pos, 710 TValue2 const & value) 711 { 712 SEQAN_CHECKPOINT; 713 journaledString._length += 1; 714 TPos beginPos = length(journaledString._insertionBuffer); 715 appendValue(journaledString._insertionBuffer, value); 716 recordInsertion(journaledString._journalEntries, pos, beginPos, 1u); 717 } 718 719 // ---------------------------------------------------------------------------- 720 // Function assignInfix 721 // ---------------------------------------------------------------------------- 722 723 // TODO(holtgrew): More of an undescore function. 724 725 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TBeginPos, typename TEndPos, typename TSequence2> 726 inline void 727 assignInfix(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 728 TBeginPos beginPos, 729 TEndPos endPos, 730 TSequence2 const & valueString) 731 { 732 SEQAN_CHECKPOINT; 733 erase(journaledString, beginPos, endPos); 734 insert(journaledString, beginPos, valueString); 735 } 736 737 // ---------------------------------------------------------------------------- 738 // Function assignValue 739 // ---------------------------------------------------------------------------- 740 741 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos, typename TValue2> 742 inline void 743 assignValue(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 744 TPos pos, 745 TValue2 const & value) 746 { 747 SEQAN_CHECKPOINT; 748 erase(journaledString, pos); 749 insertValue(journaledString, pos, value); 750 } 751 752 753 // TODO(holtgrew): Batch-Assignment of values through segments? 754 755 // TODO(holtgrew): begin 756 // TODO(holtgrew): empty 757 // TODO(holtgrew): end 758 // TODO(holtgrew): flatten 759 // TODO(holtgrew): fill 760 // TODO(holtgrew): getValue 761 762 // TODO(holtgrew): Unused, remove? 763 /* 764 template <typename TSequence, typename TJournalSpec> 765 inline 766 typename Value<TSequence>::Type const & 767 front(String...<TSequence, TJournalSpec> const & journaledString) 768 { 769 SEQAN_XXXCHECKPOINT; 770 typedef SequenceJournal<TSequence, TJournalSpec> TString; 771 typedef typename TString::TNode TNode; 772 TNode frontNode = front(journaledString._journalEntries); 773 if (frontNode->segmentSource == SOURCE_ORIGINAL) { 774 return getValue(value(journaledString._holder), frontNode->virtualPosition + frontNode->length - 1); 775 } else { 776 SEQAN_ASSERT_EQ(frontNode->segmentSource, SOURCE_PATCH); 777 return getValue(journaledString._insertionBuffer, frontNode->virtualPosition + frontNode->length - 1); 778 } 779 } 780 781 // front/back clash with general sequence definitions. 782 template <typename TSequence, typename TJournalSpec> 783 inline 784 TValue const & 785 back(SequenceJournal<TSequence, TJournalSpec> const & journaledString) 786 { 787 SEQAN_XXXCHECKPOINT; 788 typedef SequenceJournal<TSequence, TJournalSpec> TString; 789 typedef typename TString::TNode TNode; 790 TNode backNode = back(journaledString._journalEntries); 791 if (backNode->segmentSource == SOURCE_ORIGINAL) { 792 return getValue(value(journaledString._holder), backNode->virtualPosition + backNode->length - 1); 793 } else { 794 SEQAN_ASSERT_EQ(backNode->segmentSource, SOURCE_PATCH); 795 return getValue(journaledString._insertionBuffer, backNode->virtualPosition + backNode->length - 1); 796 } 797 } 798 */ 799 800 // ---------------------------------------------------------------------------- 801 // Function length 802 // ---------------------------------------------------------------------------- 803 804 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 805 inline 806 typename Size<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type 807 length(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString) 808 { 809 SEQAN_CHECKPOINT; 810 return journaledString._length; 811 } 812 813 // ---------------------------------------------------------------------------- 814 // Function toCString 815 // ---------------------------------------------------------------------------- 816 817 // TODO(holtgrew): toCString 818 819 // ---------------------------------------------------------------------------- 820 // Function value 821 // ---------------------------------------------------------------------------- 822 823 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 824 inline 825 typename Reference<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type 826 value(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & me, 827 TPos pos) 828 { 829 SEQAN_CHECKPOINT; 830 831 return *iter(me, pos, Standard()); 832 } 833 834 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 835 inline 836 typename Reference<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const>::Type 837 value(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & me, 838 TPos pos) 839 { 840 SEQAN_CHECKPOINT; 841 842 return *iter(me, pos, Standard()); 843 } 844 845 846 // TODO(holtgrew): Maybe better use template parameter TPos? 847 // TOOD(holtgrew): operator< 848 // TOOD(holtgrew): operator> 849 // TOOD(holtgrew): operator<= 850 // TOOD(holtgrew): operator>= 851 // TOOD(holtgrew): operator== 852 // TOOD(holtgrew): operator!= 853 854 // ---------------------------------------------------------------------------- 855 // Function getValue 856 // ---------------------------------------------------------------------------- 857 858 // TODO(holtgrew): Maybe better use template parameter TPos? 859 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 860 inline 861 typename GetValue<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const>::Type 862 getValue(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString, 863 typename Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type pos) 864 { 865 SEQAN_CHECKPOINT; 866 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const TJournaledString; 867 typedef typename TJournaledString::TJournalEntry TJournalEntry; 868 typedef typename Position<TJournaledString>::Type TPos; 869 870 TJournalEntry entry = findJournalEntry(journaledString._journalEntries, pos); 871 TPos relativePos = pos - entry.virtualPosition; 872 873 if (entry.segmentSource == SOURCE_ORIGINAL) { 874 return getValue(value(journaledString._holder), entry.physicalPosition + relativePos); 875 } else { 876 return getValue(journaledString._insertionBuffer, entry.physicalPosition + relativePos); 877 } 878 } 879 880 // -------------------------------------------------------------------------- 881 // Function virtualToHostPosition() 882 // -------------------------------------------------------------------------- 883 884 /*! 885 * @fn JournaledString#virtualToHostPosition 886 * @brief Translates virtual (view) position to position in host. 887 * 888 * @signature TPos virtualToHostPosition(js, pos); 889 * 890 * @param[in] js The JournaledString to translate the position for. 891 * @param[in] pos The virtual position to translate. 892 * 893 * @return TPos Position in the host. 894 */ 895 896 // Note that if pos is in a gap, we return the position of the entry 897 // after the gap in the host. 898 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 899 inline 900 typename Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type 901 virtualToHostPosition(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString, 902 TPos pos) 903 { 904 SEQAN_CHECKPOINT; 905 // TODO(holtgrew): With a better journal entries datastructure, we could solve the main problem here. At the moment, we delegate completely. 906 return virtualToHostPosition(journaledString._journalEntries, pos); 907 } 908 909 //--------------------------------------------------- 910 // function hostToVirtualPosition() 911 //--------------------------------------------------- 912 913 /*! 914 * @fn JournaledString#hostToVirtualPosition 915 * @brief Translates host position to virtual position. 916 * 917 * @signature TPos hostToVirtualPosition(js, pos); 918 * 919 * @param[in] js The JournaledString to translate the position for. 920 * @param[in] pos The host position to translate. 921 * 922 * @return TPos The virtual view position. Note the returned position equates to length of the journaled string 923 * if <tt>pos</tt> is greater or equal the length of the underlying host. 924 */ 925 926 template<typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 927 inline 928 typename Position<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type 929 hostToVirtualPosition(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journalString, 930 TPos const & pos) 931 { 932 if (pos < (TPos) length(host(journalString))) 933 return hostToVirtualPosition(journalString._journalEntries, pos); 934 return length(journalString); 935 } 936 937 // -------------------------------------------------------------------------- 938 // Function isGapInHost() 939 // -------------------------------------------------------------------------- 940 941 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec, typename TPos> 942 inline 943 bool 944 isGapInHost(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString, 945 TPos pos) 946 { 947 SEQAN_CHECKPOINT; 948 // TODO(holtgrew): With a better journal entries datastructure, we could solve the main problem here. At the moment, we delegate completely. 949 return isGapInHost(journaledString._journalEntries, pos); 950 } 951 952 // -------------------------------------------------------------------------- 953 // Function _setLength() 954 // -------------------------------------------------------------------------- 955 956 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 957 inline 958 void 959 _setLength(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString, 960 size_t newLength) 961 { 962 SEQAN_CHECKPOINT; 963 journaledString._length = newLength; 964 } 965 966 // ---------------------------------------------------------------------------- 967 // Function _journalEntries 968 // ---------------------------------------------------------------------------- 969 970 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 971 inline typename JournalType<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > >::Type & 972 _journalEntries(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 973 { 974 return journaledString._journalEntries; 975 } 976 977 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 978 inline typename JournalType<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const>::Type & 979 _journalEntries(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString) 980 { 981 return journaledString._journalEntries; 982 } 983 984 // -------------------------------------------------------------------------- 985 // Function replace() 986 // -------------------------------------------------------------------------- 987 988 template <typename TTargetValue, typename TTargetHostSpec, typename TTargetJournalSpec, typename TTargetBufferSpec, typename TPositionBegin, typename TPositionEnd, typename TSource, typename TExpand> 989 inline void 990 replace(String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > & target, 991 TPositionBegin posBegin, 992 TPositionEnd posEnd, 993 TSource const & source, 994 Tag<TExpand> /*tag*/) 995 { 996 SEQAN_CHECKPOINT; 997 assignInfix(target, posBegin, posEnd, source); 998 } 999 1000 template <typename TTargetValue, typename TTargetHostSpec, typename TTargetJournalSpec, typename TTargetBufferSpec, typename TPositionBegin, typename TPositionEnd, typename TSource, typename TExpand> 1001 inline void 1002 replace(String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > & target, 1003 TPositionBegin posBegin, 1004 TPositionEnd posEnd, 1005 TSource const & source, 1006 typename Size<String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > >::Type limit, 1007 Tag<TExpand> tag) 1008 { 1009 // Possibly only shorten target if limit is too small. 1010 if (posBegin > static_cast<TPositionBegin>(limit)) { 1011 assignInfix(target, limit, length(target), infix(source, 0, 0)); 1012 return; 1013 } 1014 1015 // Replace range in target and afterwards, limit length of target. 1016 replace(target, posBegin, posEnd, source, tag); 1017 assignInfix(target, limit, length(target), infix(source, 0, 0)); 1018 } 1019 1020 // This variant is a workaround for the "const array"-bug of VC++. 1021 template <typename TTargetValue, typename TTargetHostSpec, typename TTargetJournalSpec, typename TTargetBufferSpec, typename TPositionBegin, typename TPositionEnd, typename TSourceValue, typename TExpand> 1022 inline void 1023 replace(String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > & target, 1024 TPositionBegin posBegin, 1025 TPositionEnd posEnd, 1026 TSourceValue const * source, 1027 Tag<TExpand> /*tag*/) 1028 { 1029 SEQAN_CHECKPOINT; 1030 assignInfix(target, posBegin, posEnd, source); 1031 } 1032 1033 // This variant is a workaround for the "const array"-bug of VC++. 1034 template <typename TTargetValue, typename TTargetHostSpec, typename TTargetJournalSpec, typename TTargetBufferSpec, typename TPositionBegin, typename TPositionEnd, typename TSourceValue, typename TExpand> 1035 inline void 1036 replace(String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > & target, 1037 TPositionBegin posBegin, 1038 TPositionEnd posEnd, 1039 TSourceValue const * source, 1040 typename Size<String<TTargetValue, Journaled<TTargetHostSpec, TTargetJournalSpec, TTargetBufferSpec> > >::Type limit, 1041 Tag<TExpand> tag) 1042 { 1043 // Possibly only shorten target if limit is too small. 1044 if (posBegin > static_cast<TPositionBegin>(limit)) { 1045 assignInfix(target, limit, length(target), infix(source, 0, 0)); 1046 return; 1047 } 1048 1049 // Replace range in target and afterwards, limit length of target. 1050 replace(target, posBegin, posEnd, source, tag); 1051 assignInfix(target, limit, length(target), infix(source, 0, 0)); 1052 } 1053 1054 // -------------------------------------------------------------------------- 1055 // Function getObjectId() 1056 // -------------------------------------------------------------------------- 1057 1058 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 1059 inline 1060 const void * 1061 getObjectId(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journaledString) 1062 { 1063 SEQAN_CHECKPOINT; 1064 return getObjectId(value(journaledString._holder)); 1065 } 1066 1067 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec> 1068 inline 1069 const void * 1070 getObjectId(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journaledString) 1071 { 1072 SEQAN_CHECKPOINT; 1073 return getObjectId(value(journaledString._holder)); 1074 } 1075 1076 // -------------------------------------------------------------------------- 1077 // Function isFlat() 1078 // -------------------------------------------------------------------------- 1079 1080 /*! 1081 * @fn JournaledString#isFlat 1082 * @brief Returns whether a JournaledString has modifications. 1083 * @signature bool isFlat(js); 1084 * 1085 * @param[in] js The JournaledString to query. 1086 * 1087 * @return bool Indicates whether the string has been modified. 1088 */ 1089 1090 // TODO(holtgrew): Is the non-const version necessary? 1091 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBuffSpec> 1092 inline bool 1093 isFlat(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & journaledString) 1094 { 1095 SEQAN_CHECKPOINT; 1096 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > TJournalString; 1097 typedef typename JournalType<TJournalString>::Type TJournalEntries; 1098 typedef typename Iterator<TJournalEntries const, Standard>::Type TIteraror; 1099 1100 TIteraror it = begin(journaledString._journalEntries); 1101 if ((*it).segmentSource == SOURCE_ORIGINAL) 1102 { 1103 if (((*it).physicalPosition == (*it).virtualPosition) && ((*it).length == length(host(journaledString)))) 1104 { 1105 return true; 1106 } 1107 } 1108 return false; 1109 } 1110 1111 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBuffSpec> 1112 inline bool 1113 isFlat(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > const & journaledString) 1114 { 1115 SEQAN_CHECKPOINT; 1116 typedef String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > TJournalString; 1117 typedef typename JournalType<TJournalString>::Type TJournalEntries; 1118 typedef typename Iterator<TJournalEntries const, Standard>::Type TIteraror; 1119 1120 TIteraror it = begin(journaledString._journalEntries); 1121 if ((*it).segmentSource == SOURCE_ORIGINAL) 1122 { 1123 if (((*it).physicalPosition == (*it).virtualPosition) && ((*it).length == length(host(journaledString)))) 1124 { 1125 return true; 1126 } 1127 } 1128 return false; 1129 } 1130 1131 // template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBuffSpec> 1132 // void 1133 // _deallocateStorage(String<TValue, Journaled<THostSpec, TJournalSpec, TBuffSpec> > & string, 1134 // size_t const & newCapacity) 1135 // { 1136 // std::cout << "Now he is here but does not actually delete the contents." << std::endl; 1137 // } 1138 1139 } // namespace seqan 1140 1141 #endif // SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_H_ 1142