1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2010, 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: David Weese <david.weese@fu-berlin.de> 33 // ========================================================================== 34 35 #ifndef SEQAN_HEADER_STORE_ANNOTATION_H 36 #define SEQAN_HEADER_STORE_ANNOTATION_H 37 38 namespace SEQAN_NAMESPACE_MAIN 39 { 40 41 ////////////////////////////////////////////////////////////////////////////// 42 // Annotation Store 43 ////////////////////////////////////////////////////////////////////////////// 44 45 template <typename TPos_, typename TSpec = void> 46 struct AnnotationStoreElement 47 { 48 typedef typename Id<AnnotationStoreElement>::Type TId; 49 typedef TPos_ TPos; 50 typedef StringSet<CharString, Owner< ConcatDirect<> > > TValues; 51 52 static const TId INVALID_ID; 53 static const TPos INVALID_POS; 54 55 TId parentId; 56 TId contigId; 57 TId countId; 58 TId typeId; // gene, intron, ... 59 60 TPos beginPos; // begin position of the gapped sequence in gapped contig sequence 61 TPos endPos; // end position of ..., for reverse aligned reads holds end < begin 62 63 TId lastChildId; // generated back links to child 64 TId nextSiblingId; // and sibling 65 66 TValues values; // stores values for each keyId of (key,value) pairs 67 AnnotationStoreElementAnnotationStoreElement68 AnnotationStoreElement() : 69 parentId(INVALID_ID), contigId(INVALID_ID), countId(INVALID_ID), typeId(INVALID_ID), 70 beginPos(INVALID_POS), endPos(INVALID_POS), 71 lastChildId(INVALID_ID), nextSiblingId(INVALID_ID) {} 72 }; 73 74 ////////////////////////////////////////////////////////////////////////////// 75 76 template <typename TPos, typename TSpec> 77 const typename Id<AnnotationStoreElement<TPos, TSpec> >::Type 78 AnnotationStoreElement<TPos, TSpec>::INVALID_ID = MaxValue<typename Id<AnnotationStoreElement<TPos, TSpec> >::Type>::VALUE; 79 80 template <typename TPos, typename TSpec> 81 const TPos 82 AnnotationStoreElement<TPos, TSpec>::INVALID_POS = MaxValue<TPos>::VALUE; 83 84 ////////////////////////////////////////////////////////////////////////////// 85 86 template <typename TSpec = void> 87 struct AnnotationTree {}; 88 89 template <typename TFragmentStore, typename TSpec> 90 class Iter<TFragmentStore, AnnotationTree<TSpec> > 91 { 92 public: 93 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 94 typedef typename Value<TAnnotationStore>::Type TAnnotation; 95 typedef typename TAnnotation::TId TId; 96 97 TFragmentStore *store; 98 TId id; 99 Iter()100 Iter(): 101 store(NULL), 102 id(TAnnotation::INVALID_ID) {} 103 Iter(TFragmentStore & _store)104 Iter(TFragmentStore &_store): 105 store(&_store), 106 id(0) {} 107 Iter(TFragmentStore & _store,MinimalCtor)108 Iter(TFragmentStore &_store, MinimalCtor): 109 store(&_store), 110 id(TAnnotation::INVALID_ID) {} 111 112 inline Iter const & 113 operator = (Iter const &_origin) 114 { 115 store = &container(_origin); 116 id = _origin.id; 117 return *this; 118 } 119 }; 120 121 ////////////////////////////////////////////////////////////////////////////// 122 123 template <typename TFragmentStore, typename TSpec> 124 struct Iterator< TFragmentStore, AnnotationTree<TSpec> > { 125 typedef Iter< TFragmentStore, AnnotationTree<TSpec> > Type; 126 }; 127 128 ////////////////////////////////////////////////////////////////////////////// 129 130 template <typename TFragmentStore, typename TSpec> 131 struct Value< Iter< TFragmentStore, AnnotationTree<TSpec> > >: 132 VertexDescriptor<TFragmentStore> {}; 133 134 template <typename TFragmentStore, typename TSpec> 135 struct Size< Iter< TFragmentStore, AnnotationTree<TSpec> > > : 136 Size<TFragmentStore> {}; 137 138 template <typename TFragmentStore, typename TSpec> 139 struct Position< Iter< TFragmentStore, AnnotationTree<TSpec> > > : 140 Position<TFragmentStore> {}; 141 142 ////////////////////////////////////////////////////////////////////////////// 143 144 template <typename TFragmentStore, typename TSpec> 145 inline typename VertexDescriptor<TFragmentStore>::Type & 146 value(Iter< TFragmentStore, AnnotationTree<TSpec> > &it) { 147 return it.id; 148 } 149 150 template <typename TFragmentStore, typename TSpec> 151 inline typename VertexDescriptor<TFragmentStore>::Type const & 152 value(Iter< TFragmentStore, AnnotationTree<TSpec> > const &it) { 153 return it.id; 154 } 155 156 ////////////////////////////////////////////////////////////////////////////// 157 158 template <typename TFragmentStore, typename TSpec> 159 inline TFragmentStore & 160 container(Iter< TFragmentStore, AnnotationTree<TSpec> > &it) { 161 return *it.store; 162 } 163 164 template <typename TFragmentStore, typename TSpec> 165 inline TFragmentStore & 166 container(Iter< TFragmentStore, AnnotationTree<TSpec> > const &it) { 167 return *it.store; 168 } 169 170 ////////////////////////////////////////////////////////////////////////////// 171 172 template <typename TFragmentStore, typename TSpec> 173 inline typename Reference<typename TFragmentStore::TAnnotationStore>::Type 174 getAnnotation(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 175 { 176 return it.store->annotationStore[it.id]; 177 } 178 179 template <typename TFragmentStore, typename TSpec> 180 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type 181 getName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 182 { 183 return getAnnoName(*it.store, it.id); 184 } 185 186 template <typename TFragmentStore, typename TSpec, typename TName> 187 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type 188 setName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, TName & name) 189 { 190 if (length(it.store->annotationNameStore) <= it.id) 191 resize(it.store->annotationNameStore, it.id + 1); 192 it.store->annotationNameStore[it.id] = name; 193 } 194 195 template <typename TFragmentStore, typename TSpec> 196 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type 197 getParentName(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 198 { 199 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 200 typedef typename Value<TAnnotationStore>::Type TAnnotation; 201 typedef typename TAnnotation::TId TId; 202 203 TId parentId = it.store->annotationStore[it.id].parentId; 204 if (parentId == TAnnotation::INVALID_ID) parentId = it.id; 205 return getAnnoName(*it.store, parentId); 206 } 207 208 ////////////////////////////////////////////////////////////////////////////// 209 210 template <typename TFragmentStore, typename TSpec> 211 inline typename GetValue<typename TFragmentStore::TAnnotationTypeStore>::Type 212 getType(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 213 { 214 return getAnnoType(*it.store, it.id); 215 } 216 217 template <typename TFragmentStore, typename TSpec, typename TTypeName> 218 inline void 219 setType(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, TTypeName & typeName) 220 { 221 _storeAppendType(*it.store, getAnnotation(it).typeId, typeName); 222 } 223 224 ////////////////////////////////////////////////////////////////////////////// 225 226 template <typename TFragmentStore, typename TSpec> 227 inline CharString 228 getUniqueName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 229 { 230 return getAnnoUniqueName(*it.store, it.id); 231 } 232 233 ////////////////////////////////////////////////////////////////////////////// 234 235 template <typename TFragmentStore, typename TSpec> 236 inline void 237 clearValues(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 238 { 239 clear(getAnnotation(it).values); 240 } 241 242 template <typename TFragmentStore, typename TSpec, typename TKey, typename TValue> 243 inline void 244 assignValueByKey( 245 Iter<TFragmentStore, AnnotationTree<TSpec> > & it, 246 TKey const & key, 247 TValue const & value) 248 { 249 annotationAssignValueByKey(*it.store, getAnnotation(it), key, value); 250 } 251 252 template <typename TFragmentStore, typename TSpec, typename TKey, typename TValue> 253 inline bool 254 getValueByKey( 255 Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, 256 TKey const & key, 257 TValue & value) 258 { 259 return annotationGetValueByKey(*it.store, getAnnotation(it), key, value); 260 } 261 262 template <typename TFragmentStore, typename TSpec, typename TKey> 263 inline CharString 264 getValueByKey( 265 Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, 266 TKey const & key) 267 { 268 return annotationGetValueByKey(*it.store, getAnnotation(it), key); 269 } 270 271 ////////////////////////////////////////////////////////////////////////////// 272 273 template <typename TFragmentStore, typename TSpec> 274 inline void 275 goBegin(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 276 { 277 it.id = 0; 278 } 279 280 template <typename TFragmentStore, typename TSpec> 281 inline void 282 goEnd(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 283 { 284 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 285 typedef typename Value<TAnnotationStore>::Type TAnnotation; 286 287 it.id = TAnnotation::INVALID_ID; 288 } 289 290 template <typename TFragmentStore, typename TSpec> 291 inline void 292 clear(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 293 { 294 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 295 typedef typename Value<TAnnotationStore>::Type TAnnotation; 296 297 it.id = TAnnotation::INVALID_ID; 298 } 299 300 ////////////////////////////////////////////////////////////////////////////// 301 302 template <typename TFragmentStore, typename TSpec> 303 inline bool 304 atBegin(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 305 { 306 return it.id == 0; 307 } 308 309 template <typename TFragmentStore, typename TSpec> 310 inline bool 311 atEnd(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 312 { 313 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 314 typedef typename Value<TAnnotationStore>::Type TAnnotation; 315 316 return it.id == TAnnotation::INVALID_ID; 317 } 318 319 ////////////////////////////////////////////////////////////////////////////// 320 321 template <typename TFragmentStore, typename TSpec> 322 inline void 323 goNext(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 324 { 325 // preorder dfs 326 if (!goDown(it) && !goRight(it)) 327 while (goUp(it) && !goRight(it)) ; 328 if (isRoot(it)) { 329 clear(it); 330 return; 331 } 332 } 333 334 template <typename TFragmentStore, typename TSpec> 335 inline void 336 goNextRight(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 337 { 338 // preorder dfs 339 if (!goRight(it)) 340 while (goUp(it) && !goRight(it)) ; 341 if (isRoot(it)) { 342 clear(it); 343 return; 344 } 345 } 346 347 template <typename TFragmentStore, typename TSpec> 348 inline void 349 goNextUp(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 350 { 351 // preorder dfs 352 while (goUp(it) && !goRight(it)) ; 353 if (isRoot(it)) { 354 clear(it); 355 return; 356 } 357 } 358 359 ////////////////////////////////////////////////////////////////////////////// 360 361 template <typename TFragmentStore, typename TSpec> 362 inline void 363 goRoot(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 364 { 365 it.id = 0; 366 } 367 368 template <typename TFragmentStore, typename TSpec> 369 inline bool 370 goUp(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 371 { 372 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 373 typedef typename Value<TAnnotationStore>::Type TAnnotation; 374 typedef typename TAnnotation::TId TId; 375 376 TId parentId = getAnnotation(it).parentId; 377 if (parentId != TAnnotation::INVALID_ID) 378 { 379 it.id = parentId; 380 return true; 381 } 382 return false; 383 } 384 385 template <typename TFragmentStore, typename TSpec> 386 inline bool 387 goDown(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 388 { 389 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 390 typedef typename Value<TAnnotationStore>::Type TAnnotation; 391 typedef typename TAnnotation::TId TId; 392 393 TId lastChildId = getAnnotation(it).lastChildId; 394 if (lastChildId != TAnnotation::INVALID_ID) 395 { 396 it.id = it.store->annotationStore[lastChildId].nextSiblingId; 397 return true; 398 } 399 return false; 400 } 401 402 template <typename TFragmentStore, typename TSpec> 403 inline bool 404 goRight(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 405 { 406 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 407 typedef typename Value<TAnnotationStore>::Type TAnnotation; 408 typedef typename TAnnotation::TId TId; 409 410 TAnnotation &anno = getAnnotation(it); 411 TId nextSiblingId = anno.nextSiblingId; 412 if (nextSiblingId != TAnnotation::INVALID_ID) 413 { 414 TId lastChildId = it.store->annotationStore[anno.parentId].lastChildId; 415 if (it.id != lastChildId) 416 { 417 it.id = nextSiblingId; 418 return true; 419 } 420 } 421 return false; 422 } 423 424 ////////////////////////////////////////////////////////////////////////////// 425 426 template <typename TFragmentStore, typename TSpec> 427 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 428 nodeUp(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 429 { 430 Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it); 431 goUp(tmp); 432 return tmp; 433 } 434 435 template <typename TFragmentStore, typename TSpec> 436 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 437 nodeDown(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 438 { 439 Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it); 440 goDown(tmp); 441 return tmp; 442 } 443 444 template <typename TFragmentStore, typename TSpec> 445 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 446 nodeRight(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 447 { 448 Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it); 449 goRight(tmp); 450 return tmp; 451 } 452 453 ////////////////////////////////////////////////////////////////////////////// 454 455 // insert a new id into a cyclic list and returns new last child id 456 template <typename TAnnotationStore, typename TId> 457 inline TId 458 _cyclicListFrontInsert(TAnnotationStore & annotationStore, TId newId, TId lastChildId) 459 { 460 typedef typename Value<TAnnotationStore>::Type TAnnotation; 461 462 TId nextId, newLastId; 463 if (lastChildId != TAnnotation::INVALID_ID) 464 { 465 // get last node in the cycle 466 TAnnotation &lastChild = annotationStore[lastChildId]; 467 // last child points to first child 468 nextId = lastChild.nextSiblingId; 469 // insert new node between last and first 470 lastChild.nextSiblingId = newId; 471 // last child remains the same 472 newLastId = lastChildId; 473 } else 474 // cyclic list was empty 475 newLastId = nextId = newId; 476 477 // link new node to former first node 478 annotationStore[newId].nextSiblingId = nextId; 479 480 return newLastId; 481 } 482 483 // delete an id from a cyclic list and returns new last child id 484 template <typename TAnnotationStore, typename TId> 485 inline TId 486 _cyclicListSearchPrev(TAnnotationStore & annotationStore, TId id, TId lastChildId) 487 { 488 typedef typename Value<TAnnotationStore>::Type TAnnotation; 489 490 if (lastChildId == TAnnotation::INVALID_ID) 491 return TAnnotation::INVALID_ID; 492 493 TId prevId, i = lastChildId; 494 do { 495 prevId = i; 496 i = annotationStore[i].nextSiblingId; 497 if (i == id) break; 498 } while (i != lastChildId); 499 500 if (i == id) 501 return prevId; 502 else 503 return TAnnotation::INVALID_ID; 504 } 505 506 // delete an id from a cyclic list and returns new last child id 507 template <typename TAnnotationStore, typename TId> 508 inline TId 509 _cyclicListRemove(TAnnotationStore & annotationStore, TId id, TId lastChildId) 510 { 511 typedef typename Value<TAnnotationStore>::Type TAnnotation; 512 513 TId prevId = _cyclicListSearchPrev(annotationStore, id, lastChildId); 514 515 if (prevId != TAnnotation::INVALID_ID) 516 { 517 annotationStore[prevId].nextSiblingId = annotationStore[id].nextSiblingId; 518 519 if (id == lastChildId) 520 { 521 if (prevId != id) 522 return prevId; 523 else 524 return TAnnotation::INVALID_ID; 525 } else 526 return lastChildId; 527 } 528 return lastChildId; 529 } 530 531 template <typename TFragmentStore, typename TSpec> 532 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 533 createLeftChild(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 534 { 535 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 536 typedef typename Value<TAnnotationStore>::Type TAnnotation; 537 typedef typename TAnnotation::TId TId; 538 539 appendValue(it.store->annotationStore, getAnnotation(it)); 540 TAnnotation &parentAnno = getAnnotation(it); 541 542 TId childId = length(it.store->annotationStore) - 1; 543 TAnnotation &childAnno = it.store->annotationStore[childId]; 544 545 parentAnno.lastChildId = _cyclicListFrontInsert(it.store->annotationStore, childId, parentAnno.lastChildId); 546 childAnno.parentId = it.id; 547 childAnno.lastChildId = TAnnotation::INVALID_ID; 548 549 Iter<TFragmentStore, AnnotationTree<TSpec> > childIter(it); 550 childIter.id = childId; 551 return childIter; 552 } 553 554 template <typename TFragmentStore, typename TSpec> 555 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 556 createRightChild(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 557 { 558 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 559 typedef typename Value<TAnnotationStore>::Type TAnnotation; 560 typedef typename TAnnotation::TId TId; 561 562 appendValue(it.store->annotationStore, getAnnotation(it)); 563 TAnnotation &parentAnno = getAnnotation(it); 564 565 TId childId = length(it.store->annotationStore) - 1; 566 TAnnotation &childAnno = it.store->annotationStore[childId]; 567 568 _cyclicListFrontInsert(it.store->annotationStore, childId, parentAnno.lastChildId); 569 parentAnno.lastChildId = childId; 570 childAnno.parentId = it.id; 571 childAnno.lastChildId = TAnnotation::INVALID_ID; 572 573 Iter<TFragmentStore, AnnotationTree<TSpec> > childIter(it); 574 childIter.id = childId; 575 return childIter; 576 } 577 578 template <typename TFragmentStore, typename TSpec> 579 inline Iter<TFragmentStore, AnnotationTree<TSpec> > 580 createSibling(Iter<TFragmentStore, AnnotationTree<TSpec> > & it) 581 { 582 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 583 typedef typename Value<TAnnotationStore>::Type TAnnotation; 584 typedef typename TAnnotation::TId TId; 585 586 appendValue(it.store->annotationStore, getAnnotation(it)); 587 TAnnotation &anno = getAnnotation(it); 588 589 TId siblingId = length(it.store->annotationStore) - 1; 590 591 TAnnotation &parentAnno = it.store->annotationStore[anno.parentId]; 592 if (parentAnno.lastChildId == it.id) 593 parentAnno.lastChildId = siblingId; 594 595 TAnnotation &siblingAnno = it.store->annotationStore[siblingId]; 596 siblingAnno.nextSiblingId = anno.nextSiblingId; 597 siblingAnno.parentId = anno.parentId; 598 siblingAnno.lastChildId = TAnnotation::INVALID_ID; 599 anno.nextSiblingId = siblingId; 600 601 Iter<TFragmentStore, AnnotationTree<TSpec> > siblingIter(it); 602 siblingIter.id = siblingId; 603 return siblingIter; 604 } 605 606 ////////////////////////////////////////////////////////////////////////////// 607 608 template <typename TFragmentStore, typename TSpec> 609 inline bool 610 isRoot(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 611 { 612 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 613 typedef typename Value<TAnnotationStore>::Type TAnnotation; 614 615 // if (it.id >= length(it.store->annotationStore)) return false; 616 return it.store->annotationStore[it.id].parentId == TAnnotation::INVALID_ID; 617 } 618 619 template <typename TFragmentStore, typename TSpec> 620 inline bool 621 isLeaf(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 622 { 623 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 624 typedef typename Value<TAnnotationStore>::Type TAnnotation; 625 626 // if (it.id >= length(it.store->annotationStore)) return false; 627 return it.store->annotationStore[it.id].lastChildId == TAnnotation::INVALID_ID; 628 } 629 630 template <typename TFragmentStore, typename TSpec> 631 inline bool 632 isLastChild(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it) 633 { 634 typedef typename TFragmentStore::TAnnotationStore TAnnotationStore; 635 typedef typename Value<TAnnotationStore>::Type TAnnotation; 636 typedef typename TAnnotation::TId TId; 637 638 TAnnotation &anno = getAnnotation(it); 639 TId nextSiblingId = anno.nextSiblingId; 640 if (nextSiblingId != TAnnotation::INVALID_ID) 641 { 642 TId lastChildId = it.store->annotationStore[anno.parentId].lastChildId; 643 return it.id == lastChildId; 644 } 645 return true; 646 } 647 648 ////////////////////////////////////////////////////////////////////////////// 649 650 template <typename TAnnotationStore> 651 inline void 652 _storeClearAnnoBackLinks(TAnnotationStore & me) 653 { 654 typedef typename Value<TAnnotationStore>::Type TAnnotation; 655 typedef typename Iterator<TAnnotationStore, Standard>::Type TAnnoIter; 656 657 TAnnoIter it = begin(me, Standard()); 658 TAnnoIter itEnd = end(me, Standard()); 659 660 for (; it != itEnd; ++it) 661 { 662 (*it).lastChildId = TAnnotation::INVALID_ID; 663 (*it).nextSiblingId = TAnnotation::INVALID_ID; 664 } 665 } 666 667 template <typename TAnnotationStore> 668 inline void 669 _storeCreateAnnoBackLinks(TAnnotationStore & me) 670 { 671 typedef typename Value<TAnnotationStore>::Type TAnnotation; 672 typedef typename TAnnotation::TId TId; 673 typedef typename Iterator<TAnnotationStore, Standard>::Type TAnnoIter; 674 675 TAnnoIter itBegin = begin(me, Standard()); 676 TAnnoIter itEnd = end(me, Standard()); 677 TId id = (itEnd - itBegin) - 1; 678 TAnnoIter it = itBegin + id; 679 680 for (; itBegin <= it; --it, --id) 681 { 682 if ((*it).parentId != TAnnotation::INVALID_ID) 683 { 684 TAnnoIter parent = itBegin + (*it).parentId; 685 if ((*parent).lastChildId == TAnnotation::INVALID_ID) 686 { 687 (*parent).lastChildId = id; 688 (*it).nextSiblingId = id; 689 } 690 691 if ((*it).nextSiblingId == TAnnotation::INVALID_ID) 692 { 693 TAnnoIter lastChild = itBegin + (*parent).lastChildId; 694 (*it).nextSiblingId = (*lastChild).nextSiblingId; 695 (*lastChild).nextSiblingId = id; 696 } 697 } 698 else 699 (*it).nextSiblingId = TAnnotation::INVALID_ID; 700 } 701 } 702 703 }// namespace SEQAN_NAMESPACE_MAIN 704 705 #endif //#ifndef SEQAN_HEADER_... 706