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 // Author: Enrico Siragusa <enrico.siragusa@fu-berlin.de> 33 // ========================================================================== 34 35 #ifndef SEQAN_INDEX_QGRAM_BUCKETREFINEMENT_H_ 36 #define SEQAN_INDEX_QGRAM_BUCKETREFINEMENT_H_ 37 38 //#define SEQAN_DEBUG 39 40 namespace seqan { 41 42 // ============================================================================ 43 // Tags, Classes, Enums 44 // ============================================================================ 45 46 template <typename TText> 47 class Index<TText, IndexSa<InfixSegment> > 48 { 49 public: 50 typename Member<Index, FibreText>::Type text; 51 Holder<typename Fibre<Index, FibreSA>::Type> sa; 52 Index()53 Index() {} 54 Index(Index & other)55 Index(Index & other) : 56 text(other.text), 57 sa(other.sa) 58 {} 59 Index(Index const & other)60 Index(Index const & other) : 61 text(other.text), 62 sa(other.sa) 63 {} 64 65 template <typename TText_> Index(TText_ & _text)66 Index(TText_ & _text) : 67 text(_text) 68 {} 69 70 template <typename TText_> Index(TText_ const & _text)71 Index(TText_ const & _text) : 72 text(_text) 73 {} 74 }; 75 76 struct BucketRefinement_; 77 typedef Tag<BucketRefinement_> BucketRefinement; 78 79 template <typename TText, typename TShapeSpec> 80 class Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >: 81 public Index<TText, IndexQGram<TShapeSpec> > 82 { 83 public: 84 typedef Index<TText, IndexQGram<TShapeSpec> > TBase; 85 typedef Index<TText, IndexSa<InfixSegment> > TIndexSa; 86 87 TIndexSa _indexSa; 88 Index()89 Index() : 90 TBase() 91 { 92 _setHost(*this); 93 } 94 Index(Index & other)95 Index(Index & other) : 96 TBase(static_cast<TBase &>(other)), 97 _indexSa(other._indexSA) 98 { 99 _setHost(*this); 100 } 101 Index(Index const & other)102 Index(Index const & other) : 103 TBase(static_cast<TBase const &>(other)), 104 _indexSa(other._indexSa) 105 { 106 _setHost(*this); 107 } 108 109 template <typename TText_> Index(TText_ & _text)110 Index(TText_ & _text) : 111 TBase(_text), 112 _indexSa(_text) 113 { 114 _setHost(*this); 115 } 116 117 template <typename TText_> Index(TText_ const & _text)118 Index(TText_ const & _text) : 119 TBase(_text), 120 _indexSa(_text) 121 { 122 _setHost(*this); 123 } 124 125 template <typename TText_, typename TShape_> Index(TText_ & _text,TShape_ const & _shape)126 Index(TText_ & _text, TShape_ const & _shape) : 127 TBase(_text, _shape), 128 _indexSa(_text) 129 { 130 _setHost(*this); 131 } 132 133 template <typename TText_, typename TShape_> Index(TText_ const & _text,TShape_ const & _shape)134 Index(TText_ const & _text, TShape_ const & _shape) : 135 TBase(_text, _shape), 136 _indexSa(_text) 137 { 138 _setHost(*this); 139 } 140 }; 141 142 // ============================================================================ 143 144 template <typename TText, typename TShapeSpec, typename TSpec> 145 class Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > 146 { 147 public: 148 typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 149 typedef Iter<TIndex, VSTree<TopDown<ParentLinks<TSpec> > > > TParentLinksIter; 150 151 typedef Index<TText, IndexQGram<TShapeSpec> > TTopIndex; 152 typedef typename Iterator<TTopIndex, TopDown<TSpec> >::Type TTopIterator; 153 154 typedef Index<TText, IndexSa<InfixSegment> > TBottomIndex; 155 typedef typename Iterator<TBottomIndex, TopDown<TSpec> >::Type TBottomIterator; 156 157 TTopIterator _topIterator; 158 TBottomIterator _bottomIterator; 159 Iter()160 Iter() {} 161 Iter(TIndex & _index)162 Iter(TIndex & _index) : 163 _topIterator(), 164 _bottomIterator(_index._indexSa) 165 { 166 _indexRequireTopDownIteration(_index); 167 _topIterator = TTopIterator(static_cast<TTopIndex &>(_index)); 168 goRoot(_topIterator); 169 goRoot(_bottomIterator); 170 } 171 Iter(Iter const & _origin)172 Iter(Iter const & _origin) : 173 _topIterator(_origin._topIterator), 174 _bottomIterator(_origin._bottomIterator) 175 {} 176 Iter(TParentLinksIter const & _origin)177 Iter(TParentLinksIter const & _origin) : 178 _topIterator(_origin._topIterator), 179 _bottomIterator(_origin._bottomIterator) 180 {} 181 182 inline Iter const & 183 operator=(Iter const & _origin) 184 { 185 _bottomIterator = _origin._bottomIterator; 186 _topIterator = _origin._topIterator; 187 return *this; 188 } 189 }; 190 191 // ============================================================================ 192 193 template <typename TText, typename TShapeSpec, typename TSpec> 194 class Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<ParentLinks<TSpec> > > > 195 { 196 public: 197 typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 198 typedef Iter<TIndex, VSTree<TopDown<TSpec> > > TBase; 199 200 typedef Index<TText, IndexQGram<TShapeSpec> > TTopIndex; 201 typedef typename Iterator<TTopIndex, TopDown<ParentLinks<TSpec> > >::Type TTopIterator; 202 203 typedef Index<TText, IndexSa<InfixSegment> > TBottomIndex; 204 typedef typename Iterator<TBottomIndex, TopDown<ParentLinks<TSpec> > >::Type TBottomIterator; 205 206 TTopIterator _topIterator; 207 TBottomIterator _bottomIterator; 208 Iter()209 Iter() {} 210 Iter(TIndex & _index)211 Iter(TIndex & _index) : 212 _topIterator(), 213 _bottomIterator(_index._indexSa) 214 { 215 _indexRequireTopDownIteration(_index); 216 _topIterator = TTopIterator(static_cast<TTopIndex &>(_index)); 217 goRoot(_topIterator); 218 goRoot(_bottomIterator); 219 } 220 Iter(Iter const & _origin)221 Iter(Iter const & _origin) : 222 _topIterator(_origin._topIterator), 223 _bottomIterator(_origin._bottomIterator) 224 {} 225 226 inline Iter const & 227 operator=(Iter const & _origin) 228 { 229 _bottomIterator = _origin._bottomIterator; 230 _topIterator = _origin._topIterator; 231 return *this; 232 } 233 }; 234 235 // ============================================================================ 236 // Metafunctions 237 // ============================================================================ 238 239 template <typename TText, typename TShapeSpec> 240 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreText>: 241 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreText> 242 {}; 243 244 template <typename TText, typename TShapeSpec> 245 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreRawText>: 246 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreRawText> 247 {}; 248 249 template <typename TText, typename TShapeSpec> 250 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreSA>: 251 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreSA> 252 {}; 253 254 template <typename TText, typename TShapeSpec> 255 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreRawSA>: 256 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreRawSA> 257 {}; 258 259 template <typename TText, typename TShapeSpec> 260 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreDir>: 261 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreDir> 262 {}; 263 264 template <typename TText, typename TShapeSpec> 265 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreSADir>: 266 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreSADir> 267 {}; 268 269 template <typename TText, typename TShapeSpec> 270 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreShape>: 271 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreShape> 272 {}; 273 274 template <typename TText, typename TShapeSpec> 275 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreCounts>: 276 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreCounts> 277 {}; 278 279 template <typename TText, typename TShapeSpec> 280 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreCountsDir>: 281 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreCountsDir> 282 {}; 283 284 template <typename TText, typename TShapeSpec> 285 struct Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreBucketMap>: 286 public Fibre<Index<TText, IndexQGram<TShapeSpec> >, FibreBucketMap> 287 {}; 288 289 // ============================================================================ 290 291 template <typename TText, typename TShapeSpec> 292 struct DefaultIndexCreator<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreSA>: 293 public DefaultIndexCreator<Index<TText, IndexSa<InfixSegment> >, FibreSA> 294 {}; 295 296 // ============================================================================ 297 298 template <typename TText, typename TShapeSpec, typename TSpec> 299 struct EdgeLabel<Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > > : 300 EdgeLabel<Iter<Index<TText, IndexQGram<TShapeSpec> >, VSTree<TSpec> > > {}; 301 302 // ============================================================================ 303 304 template <typename TText, typename TShapeSpec, typename TSpec> 305 struct Iterator<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > 306 { 307 typedef Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > Type; 308 }; 309 310 // ============================================================================ 311 // Functions 312 // ============================================================================ 313 314 template <typename TText> 315 inline typename Fibre<Index<TText, IndexSa<InfixSegment> >, FibreSA>::Type & 316 getFibre(Index<TText, IndexSa<InfixSegment> > & index, FibreSA) 317 { 318 return value(index.sa); 319 } 320 321 template <typename TText> 322 inline typename Fibre<Index<TText, IndexSa<InfixSegment> > const, FibreSA>::Type & 323 getFibre(Index<TText, IndexSa<InfixSegment> > const & index, FibreSA) 324 { 325 return value(index.sa); 326 } 327 328 // Works by creating the full SA and removing the suffixes of length < q. 329 template <typename TText, typename TShapeSpec> 330 inline bool indexCreate(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index, FibreSADir, Default const) 331 { 332 // Create QGram directory. 333 resize(indexDir(index), _fullDirLength(index), Exact()); 334 createQGramIndexDirOnly(indexDir(index), indexBucketMap(index), indexText(index), indexShape(index), getStepSize(index)); 335 336 // Create full SA. 337 indexCreate(index, FibreSA()); 338 339 // Remove too short suffixes from SA. 340 _pruneSA(index); 341 342 // Update indexSA host. 343 _setHost(index); 344 345 return true; 346 } 347 348 // Works by creating the q-gram directory and quick-sorting the SA bucket-wise. 349 //template <typename TText, typename TShapeSpec> 350 //inline bool indexCreate(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index, FibreSADir, Default const) 351 //{ 352 // typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 353 // typedef Index<TText, IndexQGram<TShapeSpec> > TTopIndex; 354 // 355 //// // Create QGram directory and refine suffix array. 356 // indexCreate(static_cast<TTopIndex &>(index), FibreSADir(), Default()); 357 // _refineQGramIndex(indexSA(index), indexDir(index), indexText(index), 358 // weight(indexShape(index)), lengthSum(indexText(index))); 359 // 360 // // Update indexSA host. 361 // _setHost(index); 362 // 363 // return true; 364 //} 365 366 template <typename TText, typename TShapeSpec> 367 void _setHost(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index) 368 { 369 setValue(index._indexSa.sa, indexSA(index)); 370 } 371 372 template <typename TText, typename TShapeSpec> 373 void _pruneSA(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index) 374 { 375 typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 376 typedef typename Fibre<TIndex, FibreSA>::Type TSA; 377 typedef typename Iterator<TSA, Standard>::Type TSAIterator; 378 379 TSA & sa = indexSA(index); 380 381 TSAIterator saBegin = begin(sa, Standard()); 382 TSAIterator saEnd = end(sa, Standard()); 383 384 TSAIterator saOld = saBegin; 385 TSAIterator saNew = saOld; 386 387 while (saOld != saEnd) 388 { 389 if (suffixLength(*saOld, index) < weight(indexShape(index))) 390 { 391 ++saOld; 392 } 393 else 394 { 395 *saNew = *saOld; 396 ++saOld; 397 ++saNew; 398 } 399 } 400 401 resize(sa, saNew - saBegin, Exact()); 402 } 403 404 template <typename TText, typename TShapeSpec, typename TSpec> 405 inline bool _implantSa(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > & it) 406 { 407 //typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 408 //typedef typename Value<TIndex>::Type TAlphabet; 409 410 if (repLength(it._topIterator) < weight(indexShape(container(it._topIterator)))) 411 return false; 412 413 SEQAN_ASSERT_EQ(repLength(it._bottomIterator), 0u); 414 SEQAN_ASSERT(isRoot(it._bottomIterator)); 415 416 _historyPush(it._bottomIterator); 417 418 value(it._bottomIterator).repLen = value(it._topIterator).repLen; 419 value(it._bottomIterator).range = value(it._topIterator).range; 420 value(it._bottomIterator).lastChar = value(it._topIterator).lastChar; 421 422 return true; 423 } 424 425 template <typename TText, typename TShapeSpec, typename TSpec> 426 inline bool _atTop(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 427 { 428 return isRoot(it._bottomIterator); 429 } 430 431 template <typename TText, typename TShapeSpec, typename TSpec> 432 inline bool isRoot(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 433 { 434 return isRoot(it._topIterator); 435 } 436 437 template <typename TText, typename TShapeSpec, typename TSpec> 438 inline bool isLeaf(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 439 { 440 // TODO(esiragusa): Fix isLeaf: last qgram is a top leaf but there is no subtree attached 441 return isLeaf(it._topIterator) && isLeaf(it._bottomIterator); 442 } 443 444 template <typename TText, typename TShapeSpec, typename TSpec> 445 inline void goRoot(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > & it) 446 { 447 goRoot(it._bottomIterator); 448 goRoot(it._topIterator); 449 } 450 451 template <typename TText, typename TShapeSpec, typename TSpec> 452 inline bool goDown(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > & it) 453 { 454 //typedef Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > TIndex; 455 //typedef Pair<typename Size<TIndex>::Type> TSARange; 456 457 if (_atTop(it)) 458 { 459 if (goDown(it._topIterator)) 460 return true; 461 462 if (!_implantSa(it)) 463 return false; 464 } 465 466 return goDown(it._bottomIterator); 467 } 468 469 // NOTE(esiragusa): I should have overloaded _goDownChar() instead. 470 template <typename TText, typename TShapeSpec, typename TSpec, typename TObject> 471 inline bool _goDownObject(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > & it, 472 TObject const & obj, 473 False const & /* tag */) 474 { 475 if (_atTop(it)) 476 { 477 if (_goDownObject(it._topIterator, obj, False())) 478 return true; 479 480 if (!_implantSa(it)) 481 return false; 482 } 483 484 return _goDownObject(it._bottomIterator, obj, False()); 485 } 486 487 template <typename TText, typename TShapeSpec, typename TSpec, typename TString, typename TSize> 488 inline bool _goDownString(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > & it, 489 TString const & pattern, 490 TSize & lcp) 491 { 492 TSize topLcp = 0; 493 494 if (_atTop(it)) 495 { 496 if (_goDownString(it._topIterator, pattern, lcp)) 497 return true; 498 499 if (!_implantSa(it)) 500 return false; 501 502 topLcp = lcp; 503 } 504 505 bool wentDown = _goDownString(it._bottomIterator, suffix(pattern, topLcp), lcp); 506 507 lcp += topLcp; 508 509 return wentDown; 510 } 511 512 template <typename TText, typename TShapeSpec, typename TSpec> 513 inline bool goRight(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > & it) 514 { 515 return _atTop(it) ? goRight(it._topIterator) : goRight(it._bottomIterator); 516 } 517 518 template <typename TText, typename TShapeSpec, typename TSpec> 519 inline bool 520 goUp(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<ParentLinks<TSpec> > > > & it) 521 { 522 if (repLength(it._bottomIterator) > repLength(it._topIterator)) 523 { 524 SEQAN_ASSERT_NOT(isRoot(it._bottomIterator)); 525 526 goUp(it._bottomIterator); 527 528 SEQAN_ASSERT_NOT(isRoot(it._bottomIterator)); 529 530 if (repLength(it._bottomIterator) <= repLength(it._topIterator)) 531 goRoot(it._bottomIterator); 532 533 return true; 534 } 535 536 return goUp(it._topIterator); 537 } 538 539 template <typename TText, typename TShapeSpec, typename TSpec> 540 inline typename Size<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 541 countOccurrences(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 542 { 543 return _atTop(it) ? countOccurrences(it._topIterator) : countOccurrences(it._bottomIterator); 544 } 545 546 template <typename TText, typename TShapeSpec, typename TSpec> 547 inline typename SAValue<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 548 getOccurrence(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 549 { 550 return _atTop(it) ? getOccurrence(it._topIterator) : getOccurrence(it._bottomIterator); 551 } 552 553 template <typename TText, typename TShapeSpec, typename TSpec> 554 inline typename Infix<typename Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreSA>::Type const>::Type 555 getOccurrences(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 556 { 557 return _atTop(it) ? getOccurrences(it._topIterator) : getOccurrences(it._bottomIterator); 558 } 559 560 template <typename TText, typename TShapeSpec, typename TSpec> 561 inline typename Size<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 562 repLength(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 563 { 564 return _atTop(it) ? repLength(it._topIterator) : repLength(it._bottomIterator); 565 } 566 567 template <typename TText, typename TShapeSpec, typename TSpec> 568 inline typename Infix<typename Fibre<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, FibreText>::Type const>::Type 569 representative(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 570 { 571 return _atTop(it) ? representative(it._topIterator) : representative(it._bottomIterator); 572 } 573 574 template <typename TText, typename TShapeSpec, typename TSpec> 575 inline typename Size<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 576 parentRepLength(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 577 { 578 return _atTop(it) ? parentRepLength(it._topIterator) : parentRepLength(it._bottomIterator); 579 } 580 581 template <typename TText, typename TShapeSpec, typename TSpec> 582 inline typename Size<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 583 parentEdgeLength(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 584 { 585 return _atTop(it) ? parentEdgeLength(it._topIterator) : parentEdgeLength(it._bottomIterator); 586 } 587 588 template <typename TText, typename TShapeSpec, typename TSpec> 589 inline typename EdgeLabel<Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > >::Type 590 parentEdgeLabel(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 591 { 592 return _atTop(it) ? parentEdgeLabel(it._topIterator) : parentEdgeLabel(it._bottomIterator); 593 } 594 595 template <typename TText, typename TShapeSpec, typename TSpec> 596 inline typename Value<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type 597 parentEdgeFirstChar(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TopDown<TSpec> > > const & it) 598 { 599 return _atTop(it) ? parentEdgeFirstChar(it._topIterator) : parentEdgeFirstChar(it._bottomIterator); 600 } 601 602 template <typename TText, typename TShapeSpec, typename TSpec> 603 inline Pair<typename Size<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > >::Type> 604 range(Iter<Index<TText, IndexQGram<TShapeSpec, BucketRefinement> >, VSTree<TSpec> > const & it) 605 { 606 return _atTop(it) ? range(it._topIterator) : range(it._bottomIterator); 607 } 608 609 template <typename TText, typename TShapeSpec> 610 inline bool open(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index, const char * fileName) 611 { 612 typedef Index<TText, IndexQGram<TShapeSpec> > TBaseIndex; 613 614 if (open(static_cast<TBaseIndex &>(index), fileName)) 615 { 616 setHost(index._indexSa, indexText(index)); 617 _setHost(index); 618 return true; 619 } 620 621 return false; 622 } 623 624 template <typename TText, typename TShapeSpec> 625 inline bool save(Index<TText, IndexQGram<TShapeSpec, BucketRefinement> > & index, const char * fileName) 626 { 627 typedef Index<TText, IndexQGram<TShapeSpec> > TBaseIndex; 628 629 return save(static_cast<TBaseIndex &>(index), fileName); 630 } 631 632 } // namespace seqan 633 634 #endif // #ifndef SEQAN_INDEX_QGRAM_BUCKETREFINEMENT_H_ 635