Signal/Geometry Processing Library (SPL) 1.1.24 |

Sequence.hpp
Go to the documentation of this file.
1 // Copyright (c) 2011 Michael D. Adams
2 // All rights reserved.
3
4 // __START_OF_LICENSE__
5 //
6 // Copyright (c) 2015 Michael D. Adams
7 // All rights reserved.
8 //
9 // This file is part of the Signal Processing Library (SPL).
10 //
11 // This program is free software; you can redistribute it and/or
12 // modify it under the terms of the GNU General Public License as
13 // published by the Free Software Foundation; either version 3,
14 // or (at your option) any later version.
15 //
16 // This program is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU General Public
22 // License along with this program; see the file LICENSE. If not,
23 // see <http://www.gnu.org/licenses/>.
24 //
25 // __END_OF_LICENSE__
26
32 #ifndef SPL_Sequence_hpp
33 #define SPL_Sequence_hpp
34
36 //
38
39 #include <SPL/config.hpp>
40
42 //
44
45 namespace SPL {
46
48 // Constants
50
54 struct ConvolveMode
55 {
57 static const int full = 0;
58
60 static const int sameDomainZeroExt = 1;
61
63 static const int sameDomainConstExt = 3;
64
66 static const int sameDomainPerExt = 2;
67
69 static const int sameDomainSymExt0 = 4;
70 };
71
77 //
80
82
91 template <class Iterator1, class Iterator2, class T>
92 T special_inner_product(Iterator1 seqStart, Iterator2 filtStart,
93 Iterator2 filtEnd, T init)
94 {
95 T result = init;
96 while (filtStart != filtEnd) {
97 --filtEnd;
98 //std::cerr << "result " << ((*seqStart) * (*filtEnd)) << "\n";
99 result += (*seqStart) * (*filtEnd);
100 ++seqStart;
101 }
102 return result;
103 }
105
107
110 template <class T, class SeqIterator, class FiltIterator, class ResultIterator>
111 void convolveHelper(SeqIterator seqStart, SeqIterator seqEnd,
112 FiltIterator filtStart, FiltIterator filtEnd, ResultIterator resultStart,
113 T dummy)
114 {
115 if ((seqEnd - seqStart) >= (filtEnd - filtStart)) {
116
117 // The number of elements in the range [seqStart, seqEnd) is not
118 // less than the number of elements in [filtStart, filtEnd).
119
120 SeqIterator seqStartIter1 = seqStart;
121 FiltIterator filtStartIter1 = filtStart;
122 FiltIterator filtEndIter1 = filtStartIter1 + 1;
123 ResultIterator resultIter = resultStart;
124
125 // Process the left boundary.
126 int n = (filtEnd - filtStart) - 1;
127 while (--n >= 0) {
128 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
129 filtEndIter1, T(0));
130 ++filtEndIter1;
131 ++resultIter;
132 }
133
134 // Process the interior.
135 n = (seqEnd - seqStart) - (filtEnd - filtStart) + 1;
136 assert(filtStartIter1 == filtStart);
137 assert(filtEndIter1 == filtEnd);
138 while (--n >= 0) {
139 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
140 filtEndIter1, T(0));
141 ++resultIter;
142 ++seqStartIter1;
143 }
144
145 // Process the right boundary.
146 n = (filtEnd - filtStart) - 1;
147 ++filtStartIter1;
148 assert(filtStartIter1 == filtStart + 1);
149 assert(filtEndIter1 == filtEnd);
150 while (--n >= 0) {
151 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
152 filtEndIter1, T(0));
153 ++seqStartIter1;
154 ++filtStartIter1;
155 ++resultIter;
156 }
157
158 } else {
159
160 convolveHelper(filtStart, filtEnd, seqStart, seqEnd, resultStart, dummy);
161
162 #if 0
163 // The number of elements in the range [seqStart, seqEnd) is
164 // less than the number of elements in [filtStart, filtEnd).
165 // In principle, we need to swap these ranges.
166 // We cannot actually do a swap since the iterators may not be
167 // of the same type.
168 // The code in this else clause is identical to the code in the
169 // above if clause, except that we have reversed the role of
170 // the two ranges.
171
172 FiltIterator filtStartIter1 = filtStart;
173 SeqIterator seqStartIter1 = seqStart;
174 SeqIterator seqEndIter1 = seqStartIter1 + 1;
175 ResultIterator resultIter = resultStart;
176
177 // Process the left boundary.
178 int n = (seqEnd - seqStart) - 1;
179 while (--n >= 0) {
180 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
181 seqEndIter1, T(0));
182 ++seqEndIter1;
183 ++resultIter;
184 }
185
186 // Process the interior.
187 n = (filtEnd - filtStart) - (seqEnd - seqStart) + 1;
188 assert(seqStartIter1 == seqStart);
189 assert(seqEndIter1 == seqEnd);
190 while (--n >= 0) {
191 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
192 seqEndIter1, T(0));
193 ++resultIter;
194 ++filtStartIter1;
195 }
196
197 // Process the right boundary.
198 n = (seqEnd - seqStart) - 1;
199 ++seqStartIter1;
200 assert(seqStartIter1 == seqStart + 1);
201 assert(seqEndIter1 == seqEnd);
202 while (--n >= 0) {
203 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
204 seqEndIter1, T(0));
205 ++filtStartIter1;
206 ++seqStartIter1;
207 ++resultIter;
208 }
209 #endif
210 }
211
212 }
214
216
220 template <class T, class SeqIterator, class FiltIterator, class ResultIterator>
221 void convolveHelper2(SeqIterator seqStart, SeqIterator seqEnd,
222 FiltIterator filtStart, FiltIterator filtEnd, ResultIterator resultStart,
223 int skip, int count, T dummy)
224 {
225 if (count <= 0) {
226 return;
227 }
228 if ((seqEnd - seqStart) >= (filtEnd - filtStart)) {
229 assert(count >= 0 && count <= (seqEnd - seqStart));
230
231 SeqIterator seqStartIter1 = seqStart;
232 FiltIterator filtStartIter1 = filtStart;
233 FiltIterator filtEndIter1 = filtStartIter1 + 1;
234 ResultIterator resultIter = resultStart;
235
236 // Process the left boundary.
237 int n = (filtEnd - filtStart) - 1;
238 int adjust = std::min(n, skip);
239 assert(adjust >= 0);
240 skip -= adjust;
241 n -= adjust;
242 filtEndIter1 += adjust;
243 while (--n >= 0) {
244 if (--count < 0) {
245 return;
246 }
247 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
248 filtEndIter1, T(0));
249 ++filtEndIter1;
250 ++resultIter;
251 }
252
253 // Process the interior.
254 n = (seqEnd - seqStart) - (filtEnd - filtStart) + 1;
255 filtStartIter1 = filtStart;
256 filtEndIter1 = filtEnd;
257 adjust = std::min(n, skip);
258 assert(adjust >= 0);
259 skip -= adjust;
260 n -= adjust;
261 seqStartIter1 += adjust;
262 while (--n >= 0) {
263 if (--count < 0) {
264 return;
265 }
266 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
267 filtEndIter1, T(0));
268 ++resultIter;
269 ++seqStartIter1;
270 }
271
272 // Process the right boundary.
273 n = (filtEnd - filtStart) - 1;
274 filtStartIter1 = filtStart + 1;
275 filtEndIter1 = filtEnd;
276 adjust = std::min(n, skip);
277 assert(adjust >= 0);
278 skip -= adjust;
279 n -= adjust;
280 filtStartIter1 += adjust;
281 while (--n >= 0) {
282 if (--count < 0) {
283 return;
284 }
285 *resultIter = special_inner_product(seqStartIter1, filtStartIter1,
286 filtEndIter1, T(0));
287 ++seqStartIter1;
288 ++filtStartIter1;
289 ++resultIter;
290 }
291
292 } else {
293 convolveHelper2(filtStart, filtEnd, seqStart, seqEnd, resultStart,
294 skip, count, dummy);
295 #if 0
296 assert(count >= 0 && count <= (filtEnd - filtStart));
297
298 FiltIterator filtStartIter1 = filtStart;
299 SeqIterator seqStartIter1 = seqStart;
300 SeqIterator seqEndIter1 = seqStartIter1 + 1;
301 ResultIterator resultIter = resultStart;
302
303 // Process the left boundary.
304 int n = (seqEnd - seqStart) - 1;
305 int adjust = std::min(n, skip);
306 assert(adjust >= 0);
307 skip -= adjust;
308 n -= adjust;
309 seqEndIter1 += adjust;
310 while (--n >= 0) {
311 if (--count < 0) {
312 return;
313 }
314 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
315 seqEndIter1, T(0));
316 ++seqEndIter1;
317 ++resultIter;
318 }
319
320 // Process the interior.
321 n = (filtEnd - filtStart) - (seqEnd - seqStart) + 1;
322 seqStartIter1 = seqStart;
323 seqEndIter1 = seqEnd;
324 adjust = std::min(n, skip);
325 assert(adjust >= 0);
326 skip -= adjust;
327 n -= adjust;
328 filtStartIter1 += adjust;
329 while (--n >= 0) {
330 if (--count < 0) {
331 return;
332 }
333 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
334 seqEndIter1, T(0));
335 ++resultIter;
336 ++filtStartIter1;
337 }
338
339 // Process the right boundary.
340 n = (seqEnd - seqStart) - 1;
341 seqStartIter1 = seqStart + 1;
342 seqEndIter1 = seqEnd;
343 adjust = std::min(n, skip);
344 assert(adjust >= 0);
345 skip -= adjust;
346 n -= adjust;
347 seqStartIter1 += adjust;
348 while (--n >= 0) {
349 if (--count < 0) {
350 return;
351 }
352 *resultIter = special_inner_product(filtStartIter1, seqStartIter1,
353 seqEndIter1, T(0));
354 ++filtStartIter1;
355 ++seqStartIter1;
356 ++resultIter;
357 }
358 #endif
359 }
360
361 }
363
364 }
365
366 #endif
SPL
Definition: Arcball.hpp:48
SPL::ConvolveMode
Constants identifying various convolution modes.
Definition: Sequence.hpp:54
SPL::ConvolveMode::full
static const int full
The full convolution result (i.e., the same as "full" in MATLAB)
Definition: Sequence.hpp:57
SPL::ConvolveMode::sameDomainPerExt
static const int sameDomainPerExt
Periodic extension.
Definition: Sequence.hpp:66
SPL::ConvolveMode::sameDomainConstExt
static const int sameDomainConstExt
Constant extension.
Definition: Sequence.hpp:63
SPL::ConvolveMode::sameDomainSymExt0
static const int sameDomainSymExt0
Symmetric periodic extension.
Definition: Sequence.hpp:69
SPL::ConvolveMode::sameDomainZeroExt
static const int sameDomainZeroExt
The same as "same" in MATLAB.
Definition: Sequence.hpp:60