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: Christopher Pockrandt <christopher.pockrandt@fu-berlin.de>
33 // ==========================================================================
34
35 //SEQAN_NO_DDDOC:do not generate documentation for this file
36
37 #ifndef INDEX_BIFM_STREE_H_
38 #define INDEX_BIFM_STREE_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Functions
44 // ============================================================================
45
46 template <typename TText, typename TOccSpec, typename TIndexSpec, typename TSpec, typename TDirection>
_update(Iter<Index<TText,BidirectionalIndex<FMIndex<TOccSpec,TIndexSpec>>>,VSTree<TopDown<TSpec>>> & it,TDirection)47 inline void _update(Iter<Index<TText, BidirectionalIndex<FMIndex<TOccSpec, TIndexSpec> > >, VSTree<TopDown<TSpec> > > & it, TDirection)
48 {
49 typedef typename IfC<IsSameType<TDirection, Tag<BidirectionalFwd_> >::VALUE, Rev, Fwd>::Type TOppositeDirection;
50
51 _historyPush(_iter(it, TOppositeDirection()));
52
53 auto & dirIter = _iter(it, TDirection());
54 auto & oppDirIter = _iter(it, TOppositeDirection());
55
56 value(oppDirIter).range.i1 += value(dirIter).smaller;
57 value(oppDirIter).range.i2 = value(oppDirIter).range.i1 + value(dirIter).range.i2 - value(dirIter).range.i1;
58
59 value(oppDirIter).repLen = value(dirIter).repLen;
60 }
61
62 template <typename TText, typename TOccSpec, typename TIndexSpec, typename TSpec, typename TDirection>
_updateOnGoRight(Iter<Index<TText,BidirectionalIndex<FMIndex<TOccSpec,TIndexSpec>>>,VSTree<TopDown<TSpec>>> & it,TDirection)63 inline void _updateOnGoRight(Iter<Index<TText, BidirectionalIndex<FMIndex<TOccSpec, TIndexSpec> > >, VSTree<TopDown<TSpec> > > & it, TDirection)
64 {
65 typedef typename IfC<IsSameType<TDirection, Tag<BidirectionalFwd_> >::VALUE, Rev, Fwd>::Type TOppositeDirection;
66
67 auto & dirIter = _iter(it, TDirection());
68 auto & oppDirIter = _iter(it, TOppositeDirection());
69
70 value(oppDirIter).range.i1 = nodeUp(oppDirIter).range.i1 + value(dirIter).smaller;
71 value(oppDirIter).range.i2 = value(oppDirIter).range.i1 + value(dirIter).range.i2 - value(dirIter).range.i1;
72 }
73
74 template <typename TText, typename TOccSpec, typename TIndexSpec, typename TSpec, typename TString, typename TSize, typename TDirection>
75 inline bool
_goDownString(Iter<Index<TText,BidirectionalIndex<FMIndex<TOccSpec,TIndexSpec>>>,VSTree<TopDown<TSpec>>> & it,TString const & string,TSize & lcp,TDirection)76 _goDownString(Iter<Index<TText, BidirectionalIndex<FMIndex<TOccSpec, TIndexSpec> > >, VSTree<TopDown<TSpec> > > &it,
77 TString const & string,
78 TSize & lcp,
79 TDirection)
80 {
81 typedef Index<TText, FMIndex<TOccSpec, TIndexSpec> > TIndex;
82 typedef typename Size<TIndex>::Type TSize2;
83 typedef Pair<TSize2> TRange;
84 typedef typename Iterator<TString const, Standard>::Type TStringIter;
85
86 TStringIter stringIt = begin(string, Standard());
87 TStringIter stringEnd = end(string, Standard());
88
89 if (SEQAN_UNLIKELY(stringIt == stringEnd))
90 return true;
91
92 _historyPush(_iter(it, TDirection()));
93
94 for (lcp = 0; stringIt != stringEnd; ++stringIt, ++lcp)
95 {
96 TRange _range;
97 TSize2 _smaller = 0;
98
99 // NOTE(esiragusa): this should be faster only for texts over small alphabets consisting of few/long sequences.
100 if (isLeaf(_iter(it, TDirection())) || !_getNodeByChar(_iter(it, TDirection()), value(_iter(it, TDirection())), _range, _smaller, value(stringIt))) break;
101
102 value(_iter(it, TDirection())).range = _range;
103 value(_iter(it, TDirection())).smaller = _smaller;
104 _update(it, TDirection());
105 }
106
107 value(_iter(it, Fwd())).repLen += lcp;
108 value(_iter(it, Rev())).repLen += lcp;
109
110 if (lcp) value(_iter(it, TDirection())).lastChar = value(stringIt - 1);
111
112 return stringIt == stringEnd;
113 }
114
115 }
116
117 #endif /* INDEX_BIFM_STREE_H_ */
118