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: Enrico Siragusa <enrico.siragusa@fu-berlin.de>
33 // ==========================================================================
34
35 #ifndef SEQAN_FIND_LAMBDA_H
36 #define SEQAN_FIND_LAMBDA_H
37
38 namespace seqan {
39
40 // ============================================================================
41 // Metafunctions
42 // ============================================================================
43
44 // ----------------------------------------------------------------------------
45 // Metafunction DefaultFind<>
46 // ----------------------------------------------------------------------------
47
48 template <typename TText, typename TPattern>
49 struct DefaultFind
50 {
51 typedef void Type;
52 };
53
54 // ----------------------------------------------------------------------------
55 // Metafunction FindState_<>
56 // ----------------------------------------------------------------------------
57
58 template <typename TText, typename TPattern, typename TAlgorithm>
59 struct FindState_
60 {
61 typedef Nothing Type;
62 };
63
64 // ----------------------------------------------------------------------------
65 // Metafunction HasStatesPool_<>
66 // ----------------------------------------------------------------------------
67
68 template <typename TState, typename TThreading>
69 struct HasStatesPool_
70 {
71 typedef typename IsSameType<TThreading, Parallel>::Type IsParallel;
72 typedef typename Not<IsSameType<TState, Nothing> >::Type IsStateful;
73 typedef typename And<IsParallel, IsStateful>::Type Type;
74 };
75
76 // ----------------------------------------------------------------------------
77 // Metafunction StatesPool_<>
78 // ----------------------------------------------------------------------------
79
80 template <typename TState, typename TThreading>
81 struct StatesPool_
82 {
83 typedef typename HasStatesPool_<TState, TThreading>::Type HasStatesPool;
84 typedef typename If<HasStatesPool, String<TState>, TState>::Type Type;
85 };
86
87 // ============================================================================
88 // Classes
89 // ============================================================================
90
91 // ----------------------------------------------------------------------------
92 // Class FindDelegator_
93 // ----------------------------------------------------------------------------
94
95 template <typename TDelegate, typename TNeedlesIt>
96 struct FindDelegator_
97 {
98 TDelegate & delegate;
99 TNeedlesIt & needlesIt;
100
FindDelegator_FindDelegator_101 FindDelegator_(TDelegate & delegate, TNeedlesIt & needlesIt) :
102 delegate(delegate),
103 needlesIt(needlesIt)
104 {}
105
106 template <typename TTextIt, typename TScore>
operatorFindDelegator_107 void operator()(TTextIt & textIt, TScore score)
108 {
109 delegate(textIt, needlesIt, score);
110 }
111 };
112
113 // ============================================================================
114 // Functions
115 // ============================================================================
116
117 // ----------------------------------------------------------------------------
118 // Function find(text, pattern, errors, [](...){}, Algorithm());
119 // ----------------------------------------------------------------------------
120
121 template <typename TText, typename TPattern, typename TThreshold, typename TDelegate, typename TAlgorithm>
find(TText & text,TPattern const & pattern,TThreshold threshold,TDelegate && delegate,TAlgorithm)122 inline void find(TText & text, TPattern const & pattern, TThreshold threshold, TDelegate && delegate, TAlgorithm)
123 {
124 typedef typename FindState_<TText, TPattern const, TAlgorithm>::Type TState;
125
126 TState state;
127 _findStateInit(state, text, pattern, threshold, TAlgorithm());
128 _findImpl(state, text, pattern, threshold, delegate, TAlgorithm());
129 }
130
131 // ----------------------------------------------------------------------------
132 // Function find(text, pattern, [](...){});
133 // ----------------------------------------------------------------------------
134
135 template <typename TText, typename TPattern, typename TDelegate>
find(TText & text,TPattern const & pattern,TDelegate && delegate)136 inline void find(TText & text, TPattern const & pattern, TDelegate && delegate)
137 {
138 typedef typename DefaultFind<TText, TPattern const>::Type TAlgorithm;
139
140 find(text, pattern, unsigned(), delegate, TAlgorithm());
141 }
142
143 // ----------------------------------------------------------------------------
144 // Function _findStateInit()
145 // ----------------------------------------------------------------------------
146 // Stateless algorithm.
147
148 template <typename TState, typename TText, typename TPattern, typename TThreshold, typename TAlgorithm>
149 inline void
_findStateInit(TState &,TText const &,TPattern const &,TThreshold,TAlgorithm)150 _findStateInit(TState & /* s */, TText const & /* t */, TPattern const & /* p */, TThreshold /* t */, TAlgorithm) {}
151
152 // ----------------------------------------------------------------------------
153 // Function _findStatesPoolInit()
154 // ----------------------------------------------------------------------------
155
156 template <typename TState>
_findStatesPoolInit(TState &,False)157 inline void _findStatesPoolInit(TState & /* pool */, False) {}
158
159 template <typename TStates>
_findStatesPoolInit(TStates & pool,True)160 inline void _findStatesPoolInit(TStates & pool, True)
161 {
162 resize(pool, omp_get_num_threads(), Exact());
163 }
164
165 // ----------------------------------------------------------------------------
166 // Function _findPickState()
167 // ----------------------------------------------------------------------------
168
169 template <typename TState>
170 inline TState &
_findPickState(TState & state,False)171 _findPickState(TState & state, False)
172 {
173 return state;
174 }
175
176 template <typename TStates>
177 inline typename Value<TStates>::Type &
_findPickState(TStates & pool,True)178 _findPickState(TStates & pool, True)
179 {
180 return pool[omp_get_thread_num()];
181 }
182
183 // ----------------------------------------------------------------------------
184 // Function find(text, needles, errors, [](...){}, Algorithm(), Parallel());
185 // ----------------------------------------------------------------------------
186
187 template <typename TText, typename TNeedle_, typename TSSetSpec,
188 typename TThreshold, typename TDelegate, typename TAlgorithm, typename TThreading>
find(TText & text,StringSet<TNeedle_,TSSetSpec> const & needles,TThreshold threshold,TDelegate && delegate,TAlgorithm,TThreading)189 inline void find(TText & text,
190 StringSet<TNeedle_, TSSetSpec> const & needles,
191 TThreshold threshold,
192 TDelegate && delegate,
193 TAlgorithm,
194 TThreading)
195 {
196 typedef StringSet<TNeedle_, TSSetSpec> const TNeedles;
197 typedef typename Value<TNeedles>::Type TNeedle;
198 typedef typename Iterator<TNeedles, Rooted>::Type TNeedlesIt;
199 typedef typename Reference<TNeedlesIt>::Type TNeedleRef;
200
201 typedef typename FindState_<TText, TNeedle, TAlgorithm>::Type TState;
202 typedef typename StatesPool_<TState, TThreading>::Type TStatesPool;
203 typedef typename HasStatesPool_<TState, TThreading>::Type HasStatesPool;
204
205 typedef FindDelegator_<TDelegate, TNeedlesIt const> TDelegator;
206
207 TStatesPool pool;
208 _findStatesPoolInit(pool, HasStatesPool());
209
210 iterate(needles, [&](TNeedlesIt const & needlesIt)
211 {
212 TState & state = _findPickState(pool, HasStatesPool());
213 TNeedleRef needle = value(needlesIt);
214 TDelegator delegator(delegate, needlesIt);
215
216 _findStateInit(state, text, needle, threshold, TAlgorithm());
217 _findImpl(state, text, needle, threshold, delegator, TAlgorithm());
218 },
219 Rooted(), TThreading());
220 }
221
222 // ----------------------------------------------------------------------------
223 // Function find(text, needles, errors, [](...){}, Algorithm());
224 // ----------------------------------------------------------------------------
225
226 template <typename TText, typename TNeedle, typename TSSetSpec,
227 typename TThreshold, typename TDelegate, typename TAlgorithm>
find(TText & text,StringSet<TNeedle,TSSetSpec> const & needles,TThreshold threshold,TDelegate && delegate,TAlgorithm)228 inline void find(TText & text,
229 StringSet<TNeedle, TSSetSpec> const & needles,
230 TThreshold threshold,
231 TDelegate && delegate,
232 TAlgorithm)
233 {
234 find(text, needles, threshold, delegate, TAlgorithm(), Serial());
235 }
236
237 }
238
239 #endif // #ifndef SEQAN_FIND_LAMBDA_H
240