1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2018, 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 33 #ifndef SEQAN_HEADER_INDEX_ESA_ALGS_MULTI_H 34 #define SEQAN_HEADER_INDEX_ESA_ALGS_MULTI_H 35 36 namespace seqan 37 { 38 39 ////////////////////////////////////////////////////////////////////////////// 40 // more sophisticated algorithms on suffix trees of 41 // multiple sequences (generalized suffix tree) 42 ////////////////////////////////////////////////////////////////////////////// 43 44 45 /*! 46 * @class MumsIterator Mums Iterator 47 * @extends BottomUpIterator 48 * @headerfile <seqan/index.h> 49 * 50 * @brief Iterator to search for all maximum unique matches. 51 * 52 * @signature Iterator<TContainer, Mums>::Type; 53 * @signature template <typename TContainer> 54 * class Iter<TContainer, VSTree< BottomUp<Mums> > >; 55 * 56 * @tparam TContainer Type of an index that can be iterated with a bottom-up 57 * iterator. Types: @link IndexEsa @endlink 58 * 59 * @note Instead of using the class Iter directly we recommend to use the result of the metafunction 60 * Iterator<TContainer, Mums>::Type (which is Iter<TContainer, VSTree< BottomUp<Mums> > >). 61 */ 62 /*! 63 * @fn MumsIterator::Iter 64 * 65 * @brief The constructor. 66 * 67 * @signature Iter::Iter(index[, minLength]); 68 * @signature Iter::Iter(iterator); 69 * 70 * @param[in] index The index to be used for the iteration. Types: @link IndexEsa @endlink 71 * @param[in] minLength Minimum length of the supermaximal repeats, default value is 1. 72 * @param[in] iterator Another MultiMems iterator. Types: @link MultiMemsIterator @endlink 73 */ 74 75 ////////////////////////////////////////////////////////////////////////////// 76 // Mums - generalized suffix tree version 77 ////////////////////////////////////////////////////////////////////////////// 78 79 template < typename TSTree > 80 struct GetVSTreeIteratorTraits< Iter< TSTree, VSTree< BottomUp<Mums> > > > { 81 typedef PostorderEmptyEdges Type; 82 }; 83 84 template < typename TSTree > 85 class Iter< TSTree, VSTree< BottomUp<Mums> > >: 86 public Iter< TSTree, VSTree< BottomUp<> > > 87 { 88 public: 89 typedef Iter< TSTree, VSTree< BottomUp<> > > TBase; 90 typedef typename Size<TSTree>::Type TSize; 91 typedef VectorSet_<TSize, Alloc<> > TSeqSet; 92 //____________________________________________________________________________ 93 94 TSize minLength; 95 TSize seqCount; 96 TSeqSet seqSet; 97 //____________________________________________________________________________ 98 99 Iter() : 100 TBase(), 101 minLength(0), 102 seqCount(0) 103 {} 104 105 Iter(TSTree &_tree): 106 TBase(_tree), 107 minLength(1), 108 seqCount(countSequences(_tree)), 109 seqSet(countSequences(_tree)) 110 { 111 indexRequire(_tree, EsaBwt()); 112 goNext(*this); // the iterator starts in a suffix, i.e. not a MUM node (length(occ)<2<=seqCount) 113 } 114 115 Iter(TSTree &_tree, MinimalCtor): 116 TBase(_tree, MinimalCtor()) {} 117 118 Iter(TSTree &_tree, TSize _minLength): 119 TBase(_tree), 120 minLength(_minLength), 121 seqCount(countSequences(_tree)), 122 seqSet(countSequences(_tree)) 123 { 124 indexRequire(_tree, EsaBwt()); 125 goNext(*this); // the iterator starts in a suffix, i.e. not a MUM node (length(occ)<2<=seqCount) 126 } 127 128 Iter(Iter const &_origin): 129 TBase((TBase const &)_origin), 130 minLength(_origin.minLength), 131 seqCount(countSequences(container(_origin))), 132 seqSet(countSequences(container(_origin))) {} 133 }; 134 135 template < typename TSTree > 136 inline void goNext(Iter< TSTree, VSTree< BottomUp<Mums> > > &it) { 137 do { 138 goNext(it, PostorderEmptyEdges()); 139 } while (!atEnd(it) && 140 !( (countOccurrences(it) == it.seqCount) && 141 (repLength(it) >= it.minLength) && 142 isUnique(it, it.seqSet) && 143 isLeftMaximal(it)) ); 144 } 145 146 147 148 149 /*! 150 * @class MultiMemsIterator Multi Mems Iterator 151 * @extends BottomUpIterator 152 * @headerfile <seqan/index.h> 153 * 154 * @brief Iterator to search for MultiMems. 155 * 156 * @signature Iterator<TContainer, MultiMems>::Type; 157 * @signature template <typename TContainer> 158 * class Iter<TContainer, VSTree< BottomUp<MultiMems> > >; 159 * 160 * @tparam TContainer Type of an index that can be iterated with a bottom-up 161 * iterator. Types: IndexEsa 162 * 163 * @note Instead of using the class Iter directly we recommend to use the result of the metafunction 164 * Iterator<TContainer, MultiMems>::Type (which is Iter<TContainer, VSTree< BottomUp<MultiMems> > >). 165 */ 166 /*! 167 * @fn MultiMemsIterator::Iter 168 * @brief The constructor 169 * 170 * @signature Iter::Iter(index[, minLength]); 171 * @signature Iter::Iter(iterator); 172 * 173 * @param[in] index The index to be used for the iteration. Types: @link IndexEsa @endlink 174 * @param[in] minLength Minimum length of the supermaximal repeats, default value is 1. 175 * @param[in] iterator Another MultiMemsIterator iterator. Types: @link MultiMemsIterator @endlink 176 */ 177 178 ////////////////////////////////////////////////////////////////////////////// 179 // MultiMems 180 ////////////////////////////////////////////////////////////////////////////// 181 182 // contains a set of fraction compounds 183 // one compound for each sequence 184 template <typename TValue, typename TSize> 185 struct FractionMultiCompound_ { 186 typedef FractionCompound_<TValue, TSize> TCompound; 187 typedef String<TCompound> TSet; // seqNo..unsigned, compound: bwt character->suffixes 188 189 TSet set; 190 }; 191 192 193 template < typename TSTree > 194 class Iter< TSTree, VSTree< BottomUp<MultiMems> > >: 195 public Iter< TSTree, VSTree< BottomUp<> > > 196 { 197 public: 198 typedef Iter< TSTree, VSTree< BottomUp<> > > TBase; 199 typedef typename Value<TSTree>::Type TValue; 200 typedef typename Size<TSTree>::Type TSize; 201 202 typedef FractionMultiCompound_<TValue, TSize> TMultiCompound; 203 typedef String<TMultiCompound, Block<> > TSetStack; 204 typedef String<TSize> TPositionList; 205 206 typedef typename TMultiCompound::TSet TSet; 207 typedef typename Iterator<TSet>::Type TSetIterator; 208 209 typedef typename HistoryStackEntry_<TBase>::Type TStackEntry; 210 211 //____________________________________________________________________________ 212 213 TSize minLength; 214 unsigned minSupport; // the support is the number of distinct sequences 215 unsigned maxSupport; // a repeat/match occurs in 216 TSetStack setStack; 217 TPositionList posList; // this list is indexed just as SA is and contains the next entry's index 218 bool canMerge; // is false, if parent node appears after its first child on stack 219 //____________________________________________________________________________ 220 221 Iter() : 222 TBase(), 223 minLength(0), 224 minSupport(0), 225 maxSupport(0), 226 canMerge(0) 227 {} 228 229 Iter(TSTree &_index): 230 TBase(_index, MinimalCtor()), 231 minSupport(countSequences(_index)), 232 maxSupport(countSequences(_index)), 233 canMerge(true) 234 { 235 indexRequire(_index, EsaSA()); 236 indexRequire(_index, EsaLcp()); 237 indexRequire(_index, EsaBwt()); 238 resize(posList, length(_index)); 239 240 if (!empty(indexSA(_index))) 241 { 242 TStackEntry e; 243 e.range.i1 = 0; 244 e.range.i2 = 0; 245 _dfsOnPush(*this, e); 246 goNext(*this); 247 } 248 } 249 250 Iter(TSTree &_tree, MinimalCtor): 251 TBase(_tree, MinimalCtor()) {} 252 253 Iter(TSTree &_index, TSize _minLength): 254 TBase(_index, MinimalCtor()), 255 minLength(_minLength), 256 minSupport(countSequences(_index)), 257 maxSupport(countSequences(_index)), 258 canMerge(true) 259 { 260 indexRequire(_index, EsaSA()); 261 indexRequire(_index, EsaLcp()); 262 indexRequire(_index, EsaBwt()); 263 resize(posList, length(_index)); 264 265 if (!empty(indexSA(_index))) 266 { 267 TStackEntry e; 268 e.range.i1 = 0; 269 e.range.i2 = 0; 270 _dfsOnPush(*this, e); 271 goNext(*this); 272 } 273 } 274 275 Iter(Iter const &_origin): 276 TBase((TBase const &)_origin), 277 minLength(_origin.minLength), 278 minSupport(_origin.minSupport), 279 maxSupport(_origin.maxSupport), 280 setStack(_origin.setStack), 281 posList(_origin.posList), 282 canMerge(_origin.canMerge) {} 283 284 //____________________________________________________________________________ 285 286 inline bool hasRepeats() 287 { 288 if (length(setStack) < 2) return false; 289 290 TMultiCompound &child = back(setStack); 291 TMultiCompound &parent = backPrev(setStack); 292 293 TValue prevKey = TValue(); 294 TValue equalKey = TValue(); 295 296 unsigned distinctSeqs = 0; 297 bool distinctKeys = false; 298 299 TSetIterator parentCompound = begin(parent.set); 300 TSetIterator parentEnd = end(parent.set); 301 TSetIterator childCompound = begin(child.set); 302 TSetIterator childEnd = end(child.set); 303 304 while (childCompound != childEnd && parentCompound != parentEnd) 305 { 306 int result = _haveMaximalRepeats(*childCompound, *parentCompound, equalKey); 307 if (result > 0) { 308 if (!distinctKeys && result == 1) { 309 if (distinctSeqs > 0 && prevKey != equalKey) 310 distinctKeys = true; // there is a left maximal repeat 311 prevKey = equalKey; 312 } else 313 distinctKeys = true; 314 315 if (++distinctSeqs > minSupport && distinctKeys) // if it is also a repeat in at least 316 return true; // minSequences distinct sequences then 317 } // we have at least one repeat 318 ++childCompound; 319 ++parentCompound; 320 } 321 return false; 322 } 323 /* 324 inline TSize countRepeats() 325 { 326 if (length(setStack) < 2) return 0; 327 328 TFractionCompound &child = back(setStack); 329 TFractionCompound &parent = backPrev(setStack); 330 331 TSetIterator childFraction = begin(child.set); 332 TSetIterator childEnd = end(child.set); 333 TSetIterator parentFraction = begin(parent.set); 334 TSetIterator parentEnd = end(parent.set); 335 336 TSize sum = 0; 337 for(; childFraction != childEnd; ++childFraction) { 338 for(; parentFraction != parentEnd; ++parentFraction) { 339 if (keyOf(childFraction) != keyOf(parentFraction)) 340 sum += (*childFraction).size * (*parentFraction).size; 341 342 sum += child.leftmost.size * (*parentFraction).size; 343 } 344 sum += (*childFraction).size * parent.leftmost.size; 345 } 346 sum += child.leftmost.size * parent.leftmost.size; 347 return sum; 348 } 349 */ 350 //____________________________________________________________________________ 351 /* 352 inline void _dump() const { 353 std::cerr << "SETSTACK of " << representative(*this) << ":" << std::endl; 354 typename Iterator<TSetStack const>::Type it = begin(setStack), itEnd = end(setStack); 355 while (it != itEnd) { 356 TSet const &set = (*it).set; 357 typename Iterator<TSet const>::Type sit = begin(set), sitEnd = end(set); 358 359 while (sit != sitEnd) { 360 std::cerr << keyOf(sit) << "::"; 361 typename TFractionCompound::TFractionHeader head = objectOf(sit); 362 TSize i = head.begin; 363 while (!_isSizeInval(i)) { 364 std::cerr << i << " "; 365 i = posList[i]; 366 } 367 std::cerr << std::endl; 368 ++sit; 369 } 370 371 std::cerr << "_________________________" << std::endl; 372 ++it; 373 } 374 } 375 */ 376 }; 377 378 // add bwt partitions of child to parent node 379 template < typename TSTree, typename TSpec, typename TValue, typename TSize > 380 inline void _fractionMerge( 381 Iter<TSTree, VSTree< BottomUp<TSpec> > > &it, 382 FractionMultiCompound_<TValue, TSize> &parent, 383 FractionMultiCompound_<TValue, TSize> &child) 384 { 385 typedef FractionMultiCompound_<TValue, TSize> TCompound; 386 typedef typename TCompound::TSet TSet; 387 typedef typename Iterator<TSet, Standard>::Type TSetIterator; 388 389 TSetIterator parentCompound = begin(parent.set, Standard()); 390 TSetIterator parentEnd = end(parent.set, Standard()); 391 TSetIterator childCompound = begin(child.set, Standard()); 392 TSetIterator childEnd = end(child.set, Standard()); 393 394 while (childCompound != childEnd && parentCompound != parentEnd) 395 { 396 // append child compound to parent compound 397 _fractionMerge(it, *parentCompound, *childCompound); 398 ++childCompound; 399 ++parentCompound; 400 } 401 } 402 403 template < typename TSTree > 404 inline void _dfsOnLeaf(Iter<TSTree, VSTree< BottomUp<MultiMems> > > &it) 405 { 406 typedef Iter<TSTree, VSTree< BottomUp<> > > TBase; 407 _dfsOnLeaf((TBase&)it); 408 409 typedef typename Value<TSTree>::Type TValue; 410 typedef typename Size<TSTree>::Type TSize; 411 typedef typename SAValue<TSTree>::Type TSAValue; 412 typedef FractionHeader_<TSize> TFractionHeader; 413 typedef Pair<TValue, TFractionHeader> TFraction; 414 //typedef typename Set<TFraction>::Type TFractionSet; 415 416 typedef FractionCompound_<TValue, TSize> TCompound; 417 //typedef Pair<unsigned, TCompound> TCompoundPair; 418 //typedef typename Set<TCompoundPair>::Type TSet; 419 420 push(it.setStack); 421 422 TSTree &index = container(it); 423 424 TSize gPos = posGlobalize(_dfsRange(it).i1, stringSetLimits(index)); 425 TSAValue lPos; 426 posLocalize(lPos, _dfsRange(it).i1, stringSetLimits(index)); 427 428 TCompound &compound = back(it.setStack).set[getValueI1(lPos)]; 429 if (!posAtFirstLocal(lPos)) 430 insert( 431 TFraction( 432 bwtAt(gPos, container(it)), 433 TFractionHeader(gPos, gPos, 1)), 434 compound.set); 435 else 436 compound.leftmost = TFractionHeader(gPos, gPos, 1); 437 438 _setSizeInval(it.posList[gPos]); 439 /* 440 std::cerr << "LEAF "; 441 _dumpHistoryStack(it); 442 it._dump(); 443 */ } 444 445 446 447 ////////////////////////////////////////////////////////////////////////////// 448 // maximal repeat representation 449 ////////////////////////////////////////////////////////////////////////////// 450 451 template <typename TSTree> 452 struct MultiMem { 453 // Iter< TSTree, VSTree<BottomUp<MultiMems> > > ⁢ 454 }; 455 456 template <typename TSTree> 457 struct Value< MultiMem<TSTree> > { 458 typedef Pair< typename SAValue<TSTree>::Type > Type; 459 }; 460 461 template <typename TSTree> 462 struct Size< MultiMem<TSTree> > { 463 typedef typename Size<TSTree>::Type Type; 464 }; 465 466 467 template <typename TSTree> 468 inline typename Size< MultiMem<TSTree> >::Type 469 length(MultiMem<TSTree> const &repeat) { 470 return repeat.it.countRepeats(); 471 } 472 473 /* 474 template <typename TSTree> 475 inline typename Iterator< MultiMem<TSTree> >::Type 476 begin(MultiMem<TSTree> &repeat) { 477 return Iterator< MultiMem<TSTree> >::Type(repeat.it); 478 } 479 480 template <typename TSTree> 481 inline typename Iterator< MultiMem<TSTree> const >::Type 482 begin(MultiMem<TSTree> const &repeat) { 483 return Iterator< MultiMem<TSTree> >::Type(repeat.it); 484 } 485 */ 486 487 488 template <typename TSTree> 489 class Iter< MultiMem<TSTree>, MultiMemOccurrences > { 490 public: 491 492 typedef typename Value<TSTree>::Type TValue; 493 typedef typename Size<TSTree>::Type TSize; 494 typedef typename SAValue<TSTree>::Type TSAValue; 495 typedef Pair<TSAValue> TPair; 496 497 typedef FractionCompound_<TValue, TSize> const TFractionCompound; 498 typedef typename TFractionCompound::TSet const TSet; 499 typedef typename Iterator<TSet>::Type TSetIterator; 500 501 typedef Iter<TSTree, VSTree<BottomUp<MultiMems> > > const TIterator; 502 typedef typename TIterator::TPositionList const TPositionList; 503 504 TIterator *mmemIt; 505 bool _atEnd; 506 unsigned seqCount; 507 TPair tmp; 508 509 510 // for every sequence there is a SubState stucture 511 // storing the current enumeration state 512 // that is necessary to enumerate every combination 513 // of left maximal multi match 514 515 struct SubState 516 { 517 SubState *prevState; 518 TPositionList *posList; 519 TFractionCompound *child, *parent; 520 TSize childPtr, parentPtr; // per seq. suffix iterators 521 TSetIterator childFraction, childBegin, childEnd; 522 TSetIterator parentFraction, parentBegin, parentEnd; 523 bool leftmostChild, leftmostParent; // use undef. bwt (leftmost) set 524 TValue leftChar; // are the keys of seq[1..i] equal? 525 bool charsEqual; 526 527 inline void _updateLeftMaximality() { 528 if (prevState) 529 charsEqual = prevState->charsEqual && (leftChar == keyOf(childFraction)); 530 } 531 532 inline bool _innerStep() 533 { 534 if (_isSizeInval(childPtr = ((*posList)[childPtr]))) { 535 if (_isSizeInval(parentPtr = (*posList)[parentPtr])) { 536 parentPtr = objectOf(parentFraction).begin; 537 return false; 538 } 539 childPtr = objectOf(childFraction).begin; 540 } 541 return true; 542 } 543 544 inline void _firstParentFraction() 545 { 546 parentBegin = parentFraction = begin(parent->set); 547 parentEnd = end(parent->set); 548 549 if (parentFraction != parentEnd) { 550 leftmostParent = false; 551 parentPtr = objectOf(parentFraction).begin; 552 } else { 553 leftmostParent = true; 554 parentPtr = parent->leftmost.begin; 555 } 556 557 leftChar = keyOf(parentFraction); 558 } 559 560 inline void _firstChildFraction() 561 { 562 childBegin = childFraction = begin(child->set); 563 childEnd = end(child->set); 564 565 if (childFraction != childEnd) { 566 leftmostChild = false; 567 childPtr = objectOf(childFraction).begin; 568 } else { 569 leftmostChild = true; 570 childPtr = child->leftmost.begin; 571 } 572 } 573 574 inline bool _nextParentFraction() 575 { 576 if (leftmostParent) return false; 577 578 if (++parentFraction == parentEnd) { 579 if (parent->leftmost.size > 0) { 580 leftmostParent = true; 581 parentPtr = parent->leftmost.begin; 582 } else 583 return false; 584 } else 585 parentPtr = objectOf(parentFraction).begin; 586 587 return true; 588 } 589 590 inline bool _nextChildFraction() 591 { 592 if (leftmostChild) return false; 593 594 if (++childFraction == childEnd) { 595 if (child->leftmost.size > 0) { 596 leftmostChild = true; 597 childPtr = child->leftmost.begin; 598 } else 599 return false; 600 } else 601 childPtr = objectOf(childFraction).begin; 602 603 return true; 604 } 605 606 // single per-sequence enumeration step 607 inline bool _outerStep() 608 { 609 if (!_nextChildFraction()) { 610 _firstChildFraction(); 611 if (!_nextParentFraction()) { 612 _firstParentFraction(); 613 return false; 614 } 615 } 616 return true; 617 } 618 619 }; 620 621 String<SubState> subState; 622 623 Iter() : 624 mmemIt(), 625 _atEnd(true), 626 seqCount(0) 627 {} 628 629 inline Iter(Iter<TSTree, VSTree<BottomUp<MultiMems> > > const &_maxIt): 630 mmemIt(&_maxIt), 631 seqCount(countSequences(container(_maxIt))) 632 { 633 _init(); 634 } 635 636 inline bool _isLeftMaximal() { 637 return !subState[seqCount - 1].charsEqual; 638 } 639 640 // inner enumeration 641 inline bool _innerStep() { 642 for(unsigned seq = 0; seq < seqCount; ++seq) 643 if (subState[seq]._innerStep()) return true; 644 return false; 645 } 646 647 inline bool _outerStepNoCheck() { 648 for(unsigned seq = 0; seq < seqCount; ++seq) 649 if (subState[seq]._outerStep()) return true; 650 return false; 651 } 652 653 // outer enumeration 654 inline bool _outerStep() { 655 while (!((_atEnd = !_outerStepNoCheck()) || _isLeftMaximal())) ; 656 return !_atEnd; 657 } 658 659 inline void _init() 660 { 661 if (length(mmemIt->setStack) < 2) { 662 _atEnd = true; 663 return; 664 } 665 666 resize(subState, seqCount); 667 SubState *prev = NULL; 668 for(unsigned seq = 0; seq < seqCount; ++seq) 669 { 670 SubState &state = subState[seq]; 671 672 state.prevState = prev; 673 state.posList = &(mmemIt->posList); 674 state.parent = &(backPrev(mmemIt->setStack).set[seq]); 675 state.child = &(back(mmemIt->setStack).set[seq]); 676 677 state._firstChildFraction(); 678 state._firstParentFraction(); 679 680 prev = &state; 681 } 682 683 _atEnd = false; 684 while (!(_isLeftMaximal() || (_atEnd = !_outerStep()))) ; 685 } 686 }; 687 688 689 template < typename TRepeat > 690 inline typename Value< Iter<TRepeat, MultiMemOccurrences> >::Type & 691 value(Iter<TRepeat, MultiMemOccurrences> const &it) { 692 return it.tmp; 693 } 694 695 template < typename TRepeat > 696 inline typename Value< Iter<TRepeat, MultiMemOccurrences> >::Type & 697 value(Iter<TRepeat, MultiMemOccurrences> &it) { 698 return it.tmp; 699 } 700 701 //TODO:fix me 702 template < typename TRepeat > 703 inline Iter<TRepeat, MultiMemOccurrences> & 704 goNext(Iter<TRepeat, MultiMemOccurrences> &it) { 705 if (it._innerStep()) { 706 // it.tmp.i1 = saAt(it.subState.parentPtr, container(*it.mmemIt)); 707 // it.tmp.i2 = saAt(it.subState.childPtr, container(*it.mmemIt)); 708 return it; 709 } 710 if (it._outerStep()) { 711 // it.tmp.i1 = saAt(it.subState.parentPtr, container(*it.mmemIt)); 712 // it.tmp.i2 = saAt(it.subState.childPtr, container(*it.mmemIt)); 713 } 714 return it; 715 } 716 717 template < typename TRepeat > 718 inline bool atEnd(Iter<TRepeat, MultiMemOccurrences> const &it) { 719 return it._atEnd; 720 } 721 722 template < typename TRepeat > 723 inline bool atEnd(Iter<TRepeat, MultiMemOccurrences> &it) { 724 return it._atEnd; 725 } 726 727 728 template <typename TSTree> 729 struct Iterator< MultiMem<TSTree> > { 730 typedef Iter<MultiMem<TSTree>, MultiMemOccurrences> Type; 731 }; 732 733 template <typename TSTree> 734 struct Size< Iter<MultiMem<TSTree>, MultiMemOccurrences> > { 735 typedef typename Size<TSTree>::Type Type; 736 }; 737 738 739 ////////////////////////////////////////////////////////////////////////////// 740 // Iterator wrappers 741 ////////////////////////////////////////////////////////////////////////////// 742 743 template <typename TObject> 744 struct Iterator< TObject, Mums > { 745 typedef Iter< TObject, VSTree< BottomUp<Mums> > > Type; 746 }; 747 748 //} 749 750 } 751 752 #endif 753