OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / core / operations.hpp
1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 //  By downloading, copying, installing or using the software you agree to this license.
6 //  If you do not agree to this license, do not download, install,
7 //  copy or use the software.
8 //
9 //
10 //                           License Agreement
11 //                For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
15 // Third party copyrights are property of their respective owners.
16 //
17 // Redistribution and use in source and binary forms, with or without modification,
18 // are permitted provided that the following conditions are met:
19 //
20 //   * Redistribution's of source code must retain the above copyright notice,
21 //     this list of conditions and the following disclaimer.
22 //
23 //   * Redistribution's in binary form must reproduce the above copyright notice,
24 //     this list of conditions and the following disclaimer in the documentation
25 //     and/or other materials provided with the distribution.
26 //
27 //   * The name of the copyright holders may not be used to endorse or promote products
28 //     derived from this software without specific prior written permission.
29 //
30 // This software is provided by the copyright holders and contributors "as is" and
31 // any express or implied warranties, including, but not limited to, the implied
32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
33 // In no event shall the Intel Corporation or contributors be liable for any direct,
34 // indirect, incidental, special, exemplary, or consequential damages
35 // (including, but not limited to, procurement of substitute goods or services;
36 // loss of use, data, or profits; or business interruption) however caused
37 // and on any theory of liability, whether in contract, strict liability,
38 // or tort (including negligence or otherwise) arising in any way out of
39 // the use of this software, even if advised of the possibility of such damage.
40 //
41 //M*/
42
43 #ifndef __OPENCV_CORE_OPERATIONS_HPP__
44 #define __OPENCV_CORE_OPERATIONS_HPP__
45
46 #ifndef SKIP_INCLUDES
47   #include <string.h>
48   #include <limits.h>
49 #endif // SKIP_INCLUDES
50
51
52 #ifdef __cplusplus
53
54 /////// exchange-add operation for atomic operations on reference counters ///////
55 #if defined __INTEL_COMPILER && !(defined WIN32 || defined _WIN32)   // atomic increment on the linux version of the Intel(tm) compiler
56   #define CV_XADD(addr,delta) _InterlockedExchangeAdd(const_cast<void*>(reinterpret_cast<volatile void*>(addr)), delta)
57 #elif defined __GNUC__
58
59   #if defined __clang__ && __clang_major__ >= 3 && !defined __ANDROID__ && !defined __EMSCRIPTEN__
60     #ifdef __ATOMIC_SEQ_CST
61         #define CV_XADD(addr, delta) __c11_atomic_fetch_add((_Atomic(int)*)(addr), (delta), __ATOMIC_SEQ_CST)
62     #else
63         #define CV_XADD(addr, delta) __atomic_fetch_add((_Atomic(int)*)(addr), (delta), 5)
64     #endif
65   #elif __GNUC__*10 + __GNUC_MINOR__ >= 42
66
67     #if !(defined WIN32 || defined _WIN32) && (defined __i486__ || defined __i586__ || \
68         defined __i686__ || defined __MMX__ || defined __SSE__  || defined __ppc__) || \
69         (defined __GNUC__ && defined _STLPORT_MAJOR) || \
70         defined __EMSCRIPTEN__
71
72       #define CV_XADD __sync_fetch_and_add
73     #else
74       #include <ext/atomicity.h>
75       #define CV_XADD __gnu_cxx::__exchange_and_add
76     #endif
77
78   #else
79     #include <bits/atomicity.h>
80     #if __GNUC__*10 + __GNUC_MINOR__ >= 34
81       #define CV_XADD __gnu_cxx::__exchange_and_add
82     #else
83       #define CV_XADD __exchange_and_add
84     #endif
85   #endif
86
87 #elif defined WIN32 || defined _WIN32 || defined WINCE
88   namespace cv { CV_EXPORTS int _interlockedExchangeAdd(int* addr, int delta); }
89   #define CV_XADD cv::_interlockedExchangeAdd
90
91 #else
92   static inline int CV_XADD(int* addr, int delta)
93   { int tmp = *addr; *addr += delta; return tmp; }
94 #endif
95
96 #include <limits>
97
98 #ifdef _MSC_VER
99 # pragma warning(push)
100 # pragma warning(disable:4127) //conditional expression is constant
101 #endif
102
103 namespace cv
104 {
105
106 using std::cos;
107 using std::sin;
108 using std::max;
109 using std::min;
110 using std::exp;
111 using std::log;
112 using std::pow;
113 using std::sqrt;
114
115
116 /////////////// saturate_cast (used in image & signal processing) ///////////////////
117
118 template<typename _Tp> static inline _Tp saturate_cast(uchar v) { return _Tp(v); }
119 template<typename _Tp> static inline _Tp saturate_cast(schar v) { return _Tp(v); }
120 template<typename _Tp> static inline _Tp saturate_cast(ushort v) { return _Tp(v); }
121 template<typename _Tp> static inline _Tp saturate_cast(short v) { return _Tp(v); }
122 template<typename _Tp> static inline _Tp saturate_cast(unsigned v) { return _Tp(v); }
123 template<typename _Tp> static inline _Tp saturate_cast(int v) { return _Tp(v); }
124 template<typename _Tp> static inline _Tp saturate_cast(float v) { return _Tp(v); }
125 template<typename _Tp> static inline _Tp saturate_cast(double v) { return _Tp(v); }
126
127 template<> inline uchar saturate_cast<uchar>(schar v)
128 { return (uchar)std::max((int)v, 0); }
129 template<> inline uchar saturate_cast<uchar>(ushort v)
130 { return (uchar)std::min((unsigned)v, (unsigned)UCHAR_MAX); }
131 template<> inline uchar saturate_cast<uchar>(int v)
132 { return (uchar)((unsigned)v <= UCHAR_MAX ? v : v > 0 ? UCHAR_MAX : 0); }
133 template<> inline uchar saturate_cast<uchar>(short v)
134 { return saturate_cast<uchar>((int)v); }
135 template<> inline uchar saturate_cast<uchar>(unsigned v)
136 { return (uchar)std::min(v, (unsigned)UCHAR_MAX); }
137 template<> inline uchar saturate_cast<uchar>(float v)
138 { int iv = cvRound(v); return saturate_cast<uchar>(iv); }
139 template<> inline uchar saturate_cast<uchar>(double v)
140 { int iv = cvRound(v); return saturate_cast<uchar>(iv); }
141
142 template<> inline schar saturate_cast<schar>(uchar v)
143 { return (schar)std::min((int)v, SCHAR_MAX); }
144 template<> inline schar saturate_cast<schar>(ushort v)
145 { return (schar)std::min((unsigned)v, (unsigned)SCHAR_MAX); }
146 template<> inline schar saturate_cast<schar>(int v)
147 {
148     return (schar)((unsigned)(v-SCHAR_MIN) <= (unsigned)UCHAR_MAX ?
149                 v : v > 0 ? SCHAR_MAX : SCHAR_MIN);
150 }
151 template<> inline schar saturate_cast<schar>(short v)
152 { return saturate_cast<schar>((int)v); }
153 template<> inline schar saturate_cast<schar>(unsigned v)
154 { return (schar)std::min(v, (unsigned)SCHAR_MAX); }
155
156 template<> inline schar saturate_cast<schar>(float v)
157 { int iv = cvRound(v); return saturate_cast<schar>(iv); }
158 template<> inline schar saturate_cast<schar>(double v)
159 { int iv = cvRound(v); return saturate_cast<schar>(iv); }
160
161 template<> inline ushort saturate_cast<ushort>(schar v)
162 { return (ushort)std::max((int)v, 0); }
163 template<> inline ushort saturate_cast<ushort>(short v)
164 { return (ushort)std::max((int)v, 0); }
165 template<> inline ushort saturate_cast<ushort>(int v)
166 { return (ushort)((unsigned)v <= (unsigned)USHRT_MAX ? v : v > 0 ? USHRT_MAX : 0); }
167 template<> inline ushort saturate_cast<ushort>(unsigned v)
168 { return (ushort)std::min(v, (unsigned)USHRT_MAX); }
169 template<> inline ushort saturate_cast<ushort>(float v)
170 { int iv = cvRound(v); return saturate_cast<ushort>(iv); }
171 template<> inline ushort saturate_cast<ushort>(double v)
172 { int iv = cvRound(v); return saturate_cast<ushort>(iv); }
173
174 template<> inline short saturate_cast<short>(ushort v)
175 { return (short)std::min((int)v, SHRT_MAX); }
176 template<> inline short saturate_cast<short>(int v)
177 {
178     return (short)((unsigned)(v - SHRT_MIN) <= (unsigned)USHRT_MAX ?
179             v : v > 0 ? SHRT_MAX : SHRT_MIN);
180 }
181 template<> inline short saturate_cast<short>(unsigned v)
182 { return (short)std::min(v, (unsigned)SHRT_MAX); }
183 template<> inline short saturate_cast<short>(float v)
184 { int iv = cvRound(v); return saturate_cast<short>(iv); }
185 template<> inline short saturate_cast<short>(double v)
186 { int iv = cvRound(v); return saturate_cast<short>(iv); }
187
188 template<> inline int saturate_cast<int>(float v) { return cvRound(v); }
189 template<> inline int saturate_cast<int>(double v) { return cvRound(v); }
190
191 // we intentionally do not clip negative numbers, to make -1 become 0xffffffff etc.
192 template<> inline unsigned saturate_cast<unsigned>(float v){ return cvRound(v); }
193 template<> inline unsigned saturate_cast<unsigned>(double v) { return cvRound(v); }
194
195 inline int fast_abs(uchar v) { return v; }
196 inline int fast_abs(schar v) { return std::abs((int)v); }
197 inline int fast_abs(ushort v) { return v; }
198 inline int fast_abs(short v) { return std::abs((int)v); }
199 inline int fast_abs(int v) { return std::abs(v); }
200 inline float fast_abs(float v) { return std::abs(v); }
201 inline double fast_abs(double v) { return std::abs(v); }
202
203 //////////////////////////////// Matx /////////////////////////////////
204
205
206 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx()
207 {
208     for(int i = 0; i < channels; i++) val[i] = _Tp(0);
209 }
210
211 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0)
212 {
213     val[0] = v0;
214     for(int i = 1; i < channels; i++) val[i] = _Tp(0);
215 }
216
217 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1)
218 {
219     assert(channels >= 2);
220     val[0] = v0; val[1] = v1;
221     for(int i = 2; i < channels; i++) val[i] = _Tp(0);
222 }
223
224 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2)
225 {
226     assert(channels >= 3);
227     val[0] = v0; val[1] = v1; val[2] = v2;
228     for(int i = 3; i < channels; i++) val[i] = _Tp(0);
229 }
230
231 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3)
232 {
233     assert(channels >= 4);
234     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
235     for(int i = 4; i < channels; i++) val[i] = _Tp(0);
236 }
237
238 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3, _Tp v4)
239 {
240     assert(channels >= 5);
241     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3; val[4] = v4;
242     for(int i = 5; i < channels; i++) val[i] = _Tp(0);
243 }
244
245 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
246                                                         _Tp v4, _Tp v5)
247 {
248     assert(channels >= 6);
249     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
250     val[4] = v4; val[5] = v5;
251     for(int i = 6; i < channels; i++) val[i] = _Tp(0);
252 }
253
254 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
255                                                         _Tp v4, _Tp v5, _Tp v6)
256 {
257     assert(channels >= 7);
258     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
259     val[4] = v4; val[5] = v5; val[6] = v6;
260     for(int i = 7; i < channels; i++) val[i] = _Tp(0);
261 }
262
263 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
264                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7)
265 {
266     assert(channels >= 8);
267     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
268     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
269     for(int i = 8; i < channels; i++) val[i] = _Tp(0);
270 }
271
272 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
273                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
274                                                         _Tp v8)
275 {
276     assert(channels >= 9);
277     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
278     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
279     val[8] = v8;
280     for(int i = 9; i < channels; i++) val[i] = _Tp(0);
281 }
282
283 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
284                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
285                                                         _Tp v8, _Tp v9)
286 {
287     assert(channels >= 10);
288     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
289     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
290     val[8] = v8; val[9] = v9;
291     for(int i = 10; i < channels; i++) val[i] = _Tp(0);
292 }
293
294
295 template<typename _Tp, int m, int n>
296 inline Matx<_Tp,m,n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
297                             _Tp v4, _Tp v5, _Tp v6, _Tp v7,
298                             _Tp v8, _Tp v9, _Tp v10, _Tp v11)
299 {
300     assert(channels == 12);
301     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
302     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
303     val[8] = v8; val[9] = v9; val[10] = v10; val[11] = v11;
304 }
305
306 template<typename _Tp, int m, int n>
307 inline Matx<_Tp,m,n>::Matx(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
308                            _Tp v4, _Tp v5, _Tp v6, _Tp v7,
309                            _Tp v8, _Tp v9, _Tp v10, _Tp v11,
310                            _Tp v12, _Tp v13, _Tp v14, _Tp v15)
311 {
312     assert(channels == 16);
313     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
314     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
315     val[8] = v8; val[9] = v9; val[10] = v10; val[11] = v11;
316     val[12] = v12; val[13] = v13; val[14] = v14; val[15] = v15;
317 }
318
319 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n>::Matx(const _Tp* values)
320 {
321     for( int i = 0; i < channels; i++ ) val[i] = values[i];
322 }
323
324 template<typename _Tp, int m, int n> inline Matx<_Tp, m, n> Matx<_Tp, m, n>::all(_Tp alpha)
325 {
326     Matx<_Tp, m, n> M;
327     for( int i = 0; i < m*n; i++ ) M.val[i] = alpha;
328     return M;
329 }
330
331 template<typename _Tp, int m, int n> inline
332 Matx<_Tp,m,n> Matx<_Tp,m,n>::zeros()
333 {
334     return all(0);
335 }
336
337 template<typename _Tp, int m, int n> inline
338 Matx<_Tp,m,n> Matx<_Tp,m,n>::ones()
339 {
340     return all(1);
341 }
342
343 template<typename _Tp, int m, int n> inline
344 Matx<_Tp,m,n> Matx<_Tp,m,n>::eye()
345 {
346     Matx<_Tp,m,n> M;
347     for(int i = 0; i < MIN(m,n); i++)
348         M(i,i) = 1;
349     return M;
350 }
351
352 template<typename _Tp, int m, int n> inline _Tp Matx<_Tp, m, n>::dot(const Matx<_Tp, m, n>& M) const
353 {
354     _Tp s = 0;
355     for( int i = 0; i < m*n; i++ ) s += val[i]*M.val[i];
356     return s;
357 }
358
359
360 template<typename _Tp, int m, int n> inline double Matx<_Tp, m, n>::ddot(const Matx<_Tp, m, n>& M) const
361 {
362     double s = 0;
363     for( int i = 0; i < m*n; i++ ) s += (double)val[i]*M.val[i];
364     return s;
365 }
366
367
368
369 template<typename _Tp, int m, int n> inline
370 Matx<_Tp,m,n> Matx<_Tp,m,n>::diag(const typename Matx<_Tp,m,n>::diag_type& d)
371 {
372     Matx<_Tp,m,n> M;
373     for(int i = 0; i < MIN(m,n); i++)
374         M(i,i) = d(i, 0);
375     return M;
376 }
377
378 template<typename _Tp, int m, int n> inline
379 Matx<_Tp,m,n> Matx<_Tp,m,n>::randu(_Tp a, _Tp b)
380 {
381     Matx<_Tp,m,n> M;
382     Mat matM(M, false);
383     cv::randu(matM, Scalar(a), Scalar(b));
384     return M;
385 }
386
387 template<typename _Tp, int m, int n> inline
388 Matx<_Tp,m,n> Matx<_Tp,m,n>::randn(_Tp a, _Tp b)
389 {
390     Matx<_Tp,m,n> M;
391     Mat matM(M, false);
392     cv::randn(matM, Scalar(a), Scalar(b));
393     return M;
394 }
395
396 template<typename _Tp, int m, int n> template<typename T2>
397 inline Matx<_Tp, m, n>::operator Matx<T2, m, n>() const
398 {
399     Matx<T2, m, n> M;
400     for( int i = 0; i < m*n; i++ ) M.val[i] = saturate_cast<T2>(val[i]);
401     return M;
402 }
403
404
405 template<typename _Tp, int m, int n> template<int m1, int n1> inline
406 Matx<_Tp, m1, n1> Matx<_Tp, m, n>::reshape() const
407 {
408     CV_DbgAssert(m1*n1 == m*n);
409     return (const Matx<_Tp, m1, n1>&)*this;
410 }
411
412
413 template<typename _Tp, int m, int n>
414 template<int m1, int n1> inline
415 Matx<_Tp, m1, n1> Matx<_Tp, m, n>::get_minor(int i, int j) const
416 {
417     CV_DbgAssert(0 <= i && i+m1 <= m && 0 <= j && j+n1 <= n);
418     Matx<_Tp, m1, n1> s;
419     for( int di = 0; di < m1; di++ )
420         for( int dj = 0; dj < n1; dj++ )
421             s(di, dj) = (*this)(i+di, j+dj);
422     return s;
423 }
424
425
426 template<typename _Tp, int m, int n> inline
427 Matx<_Tp, 1, n> Matx<_Tp, m, n>::row(int i) const
428 {
429     CV_DbgAssert((unsigned)i < (unsigned)m);
430     return Matx<_Tp, 1, n>(&val[i*n]);
431 }
432
433
434 template<typename _Tp, int m, int n> inline
435 Matx<_Tp, m, 1> Matx<_Tp, m, n>::col(int j) const
436 {
437     CV_DbgAssert((unsigned)j < (unsigned)n);
438     Matx<_Tp, m, 1> v;
439     for( int i = 0; i < m; i++ )
440         v.val[i] = val[i*n + j];
441     return v;
442 }
443
444
445 template<typename _Tp, int m, int n> inline
446 typename Matx<_Tp, m, n>::diag_type Matx<_Tp, m, n>::diag() const
447 {
448     diag_type d;
449     for( int i = 0; i < MIN(m, n); i++ )
450         d.val[i] = val[i*n + i];
451     return d;
452 }
453
454
455 template<typename _Tp, int m, int n> inline
456 const _Tp& Matx<_Tp, m, n>::operator ()(int i, int j) const
457 {
458     CV_DbgAssert( (unsigned)i < (unsigned)m && (unsigned)j < (unsigned)n );
459     return this->val[i*n + j];
460 }
461
462
463 template<typename _Tp, int m, int n> inline
464 _Tp& Matx<_Tp, m, n>::operator ()(int i, int j)
465 {
466     CV_DbgAssert( (unsigned)i < (unsigned)m && (unsigned)j < (unsigned)n );
467     return val[i*n + j];
468 }
469
470
471 template<typename _Tp, int m, int n> inline
472 const _Tp& Matx<_Tp, m, n>::operator ()(int i) const
473 {
474     CV_DbgAssert( (m == 1 || n == 1) && (unsigned)i < (unsigned)(m+n-1) );
475     return val[i];
476 }
477
478
479 template<typename _Tp, int m, int n> inline
480 _Tp& Matx<_Tp, m, n>::operator ()(int i)
481 {
482     CV_DbgAssert( (m == 1 || n == 1) && (unsigned)i < (unsigned)(m+n-1) );
483     return val[i];
484 }
485
486
487 template<typename _Tp1, typename _Tp2, int m, int n> static inline
488 Matx<_Tp1, m, n>& operator += (Matx<_Tp1, m, n>& a, const Matx<_Tp2, m, n>& b)
489 {
490     for( int i = 0; i < m*n; i++ )
491         a.val[i] = saturate_cast<_Tp1>(a.val[i] + b.val[i]);
492     return a;
493 }
494
495
496 template<typename _Tp1, typename _Tp2, int m, int n> static inline
497 Matx<_Tp1, m, n>& operator -= (Matx<_Tp1, m, n>& a, const Matx<_Tp2, m, n>& b)
498 {
499     for( int i = 0; i < m*n; i++ )
500         a.val[i] = saturate_cast<_Tp1>(a.val[i] - b.val[i]);
501     return a;
502 }
503
504
505 template<typename _Tp, int m, int n> inline
506 Matx<_Tp,m,n>::Matx(const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b, Matx_AddOp)
507 {
508     for( int i = 0; i < m*n; i++ )
509         val[i] = saturate_cast<_Tp>(a.val[i] + b.val[i]);
510 }
511
512
513 template<typename _Tp, int m, int n> inline
514 Matx<_Tp,m,n>::Matx(const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b, Matx_SubOp)
515 {
516     for( int i = 0; i < m*n; i++ )
517         val[i] = saturate_cast<_Tp>(a.val[i] - b.val[i]);
518 }
519
520
521 template<typename _Tp, int m, int n> template<typename _T2> inline
522 Matx<_Tp,m,n>::Matx(const Matx<_Tp, m, n>& a, _T2 alpha, Matx_ScaleOp)
523 {
524     for( int i = 0; i < m*n; i++ )
525         val[i] = saturate_cast<_Tp>(a.val[i] * alpha);
526 }
527
528
529 template<typename _Tp, int m, int n> inline
530 Matx<_Tp,m,n>::Matx(const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b, Matx_MulOp)
531 {
532     for( int i = 0; i < m*n; i++ )
533         val[i] = saturate_cast<_Tp>(a.val[i] * b.val[i]);
534 }
535
536
537 template<typename _Tp, int m, int n> template<int l> inline
538 Matx<_Tp,m,n>::Matx(const Matx<_Tp, m, l>& a, const Matx<_Tp, l, n>& b, Matx_MatMulOp)
539 {
540     for( int i = 0; i < m; i++ )
541         for( int j = 0; j < n; j++ )
542         {
543             _Tp s = 0;
544             for( int k = 0; k < l; k++ )
545                 s += a(i, k) * b(k, j);
546             val[i*n + j] = s;
547         }
548 }
549
550
551 template<typename _Tp, int m, int n> inline
552 Matx<_Tp,m,n>::Matx(const Matx<_Tp, n, m>& a, Matx_TOp)
553 {
554     for( int i = 0; i < m; i++ )
555         for( int j = 0; j < n; j++ )
556             val[i*n + j] = a(j, i);
557 }
558
559
560 template<typename _Tp, int m, int n> static inline
561 Matx<_Tp, m, n> operator + (const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b)
562 {
563     return Matx<_Tp, m, n>(a, b, Matx_AddOp());
564 }
565
566
567 template<typename _Tp, int m, int n> static inline
568 Matx<_Tp, m, n> operator - (const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b)
569 {
570     return Matx<_Tp, m, n>(a, b, Matx_SubOp());
571 }
572
573
574 template<typename _Tp, int m, int n> static inline
575 Matx<_Tp, m, n>& operator *= (Matx<_Tp, m, n>& a, int alpha)
576 {
577     for( int i = 0; i < m*n; i++ )
578         a.val[i] = saturate_cast<_Tp>(a.val[i] * alpha);
579     return a;
580 }
581
582 template<typename _Tp, int m, int n> static inline
583 Matx<_Tp, m, n>& operator *= (Matx<_Tp, m, n>& a, float alpha)
584 {
585     for( int i = 0; i < m*n; i++ )
586         a.val[i] = saturate_cast<_Tp>(a.val[i] * alpha);
587     return a;
588 }
589
590 template<typename _Tp, int m, int n> static inline
591 Matx<_Tp, m, n>& operator *= (Matx<_Tp, m, n>& a, double alpha)
592 {
593     for( int i = 0; i < m*n; i++ )
594         a.val[i] = saturate_cast<_Tp>(a.val[i] * alpha);
595     return a;
596 }
597
598 template<typename _Tp, int m, int n> static inline
599 Matx<_Tp, m, n> operator * (const Matx<_Tp, m, n>& a, int alpha)
600 {
601     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
602 }
603
604 template<typename _Tp, int m, int n> static inline
605 Matx<_Tp, m, n> operator * (const Matx<_Tp, m, n>& a, float alpha)
606 {
607     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
608 }
609
610 template<typename _Tp, int m, int n> static inline
611 Matx<_Tp, m, n> operator * (const Matx<_Tp, m, n>& a, double alpha)
612 {
613     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
614 }
615
616 template<typename _Tp, int m, int n> static inline
617 Matx<_Tp, m, n> operator * (int alpha, const Matx<_Tp, m, n>& a)
618 {
619     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
620 }
621
622 template<typename _Tp, int m, int n> static inline
623 Matx<_Tp, m, n> operator * (float alpha, const Matx<_Tp, m, n>& a)
624 {
625     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
626 }
627
628 template<typename _Tp, int m, int n> static inline
629 Matx<_Tp, m, n> operator * (double alpha, const Matx<_Tp, m, n>& a)
630 {
631     return Matx<_Tp, m, n>(a, alpha, Matx_ScaleOp());
632 }
633
634 template<typename _Tp, int m, int n> static inline
635 Matx<_Tp, m, n> operator - (const Matx<_Tp, m, n>& a)
636 {
637     return Matx<_Tp, m, n>(a, -1, Matx_ScaleOp());
638 }
639
640
641 template<typename _Tp, int m, int n, int l> static inline
642 Matx<_Tp, m, n> operator * (const Matx<_Tp, m, l>& a, const Matx<_Tp, l, n>& b)
643 {
644     return Matx<_Tp, m, n>(a, b, Matx_MatMulOp());
645 }
646
647
648 template<typename _Tp, int m, int n> static inline
649 Vec<_Tp, m> operator * (const Matx<_Tp, m, n>& a, const Vec<_Tp, n>& b)
650 {
651     Matx<_Tp, m, 1> c(a, b, Matx_MatMulOp());
652     return reinterpret_cast<const Vec<_Tp, m>&>(c);
653 }
654
655
656 template<typename _Tp> static inline
657 Point_<_Tp> operator * (const Matx<_Tp, 2, 2>& a, const Point_<_Tp>& b)
658 {
659     Matx<_Tp, 2, 1> tmp = a*Vec<_Tp,2>(b.x, b.y);
660     return Point_<_Tp>(tmp.val[0], tmp.val[1]);
661 }
662
663
664 template<typename _Tp> static inline
665 Point3_<_Tp> operator * (const Matx<_Tp, 3, 3>& a, const Point3_<_Tp>& b)
666 {
667     Matx<_Tp, 3, 1> tmp = a*Vec<_Tp,3>(b.x, b.y, b.z);
668     return Point3_<_Tp>(tmp.val[0], tmp.val[1], tmp.val[2]);
669 }
670
671
672 template<typename _Tp> static inline
673 Point3_<_Tp> operator * (const Matx<_Tp, 3, 3>& a, const Point_<_Tp>& b)
674 {
675     Matx<_Tp, 3, 1> tmp = a*Vec<_Tp,3>(b.x, b.y, 1);
676     return Point3_<_Tp>(tmp.val[0], tmp.val[1], tmp.val[2]);
677 }
678
679
680 template<typename _Tp> static inline
681 Matx<_Tp, 4, 1> operator * (const Matx<_Tp, 4, 4>& a, const Point3_<_Tp>& b)
682 {
683     return a*Matx<_Tp, 4, 1>(b.x, b.y, b.z, 1);
684 }
685
686
687 template<typename _Tp> static inline
688 Scalar operator * (const Matx<_Tp, 4, 4>& a, const Scalar& b)
689 {
690     Matx<double, 4, 1> c(Matx<double, 4, 4>(a), b, Matx_MatMulOp());
691     return static_cast<const Scalar&>(c);
692 }
693
694
695 static inline
696 Scalar operator * (const Matx<double, 4, 4>& a, const Scalar& b)
697 {
698     Matx<double, 4, 1> c(a, b, Matx_MatMulOp());
699     return static_cast<const Scalar&>(c);
700 }
701
702
703 template<typename _Tp, int m, int n> inline
704 Matx<_Tp, m, n> Matx<_Tp, m, n>::mul(const Matx<_Tp, m, n>& a) const
705 {
706     return Matx<_Tp, m, n>(*this, a, Matx_MulOp());
707 }
708
709
710 CV_EXPORTS int LU(float* A, size_t astep, int m, float* b, size_t bstep, int n);
711 CV_EXPORTS int LU(double* A, size_t astep, int m, double* b, size_t bstep, int n);
712 CV_EXPORTS bool Cholesky(float* A, size_t astep, int m, float* b, size_t bstep, int n);
713 CV_EXPORTS bool Cholesky(double* A, size_t astep, int m, double* b, size_t bstep, int n);
714
715
716 template<typename _Tp, int m> struct Matx_DetOp
717 {
718     double operator ()(const Matx<_Tp, m, m>& a) const
719     {
720         Matx<_Tp, m, m> temp = a;
721         double p = LU(temp.val, m*sizeof(_Tp), m, 0, 0, 0);
722         if( p == 0 )
723             return p;
724         for( int i = 0; i < m; i++ )
725             p *= temp(i, i);
726         return 1./p;
727     }
728 };
729
730
731 template<typename _Tp> struct Matx_DetOp<_Tp, 1>
732 {
733     double operator ()(const Matx<_Tp, 1, 1>& a) const
734     {
735         return a(0,0);
736     }
737 };
738
739
740 template<typename _Tp> struct Matx_DetOp<_Tp, 2>
741 {
742     double operator ()(const Matx<_Tp, 2, 2>& a) const
743     {
744         return a(0,0)*a(1,1) - a(0,1)*a(1,0);
745     }
746 };
747
748
749 template<typename _Tp> struct Matx_DetOp<_Tp, 3>
750 {
751     double operator ()(const Matx<_Tp, 3, 3>& a) const
752     {
753         return a(0,0)*(a(1,1)*a(2,2) - a(2,1)*a(1,2)) -
754             a(0,1)*(a(1,0)*a(2,2) - a(2,0)*a(1,2)) +
755             a(0,2)*(a(1,0)*a(2,1) - a(2,0)*a(1,1));
756     }
757 };
758
759 template<typename _Tp, int m> static inline
760 double determinant(const Matx<_Tp, m, m>& a)
761 {
762     return Matx_DetOp<_Tp, m>()(a);
763 }
764
765
766 template<typename _Tp, int m, int n> static inline
767 double trace(const Matx<_Tp, m, n>& a)
768 {
769     _Tp s = 0;
770     for( int i = 0; i < std::min(m, n); i++ )
771         s += a(i,i);
772     return s;
773 }
774
775
776 template<typename _Tp, int m, int n> inline
777 Matx<_Tp, n, m> Matx<_Tp, m, n>::t() const
778 {
779     return Matx<_Tp, n, m>(*this, Matx_TOp());
780 }
781
782
783 template<typename _Tp, int m> struct Matx_FastInvOp
784 {
785     bool operator()(const Matx<_Tp, m, m>& a, Matx<_Tp, m, m>& b, int method) const
786     {
787         Matx<_Tp, m, m> temp = a;
788
789         // assume that b is all 0's on input => make it a unity matrix
790         for( int i = 0; i < m; i++ )
791             b(i, i) = (_Tp)1;
792
793         if( method == DECOMP_CHOLESKY )
794             return Cholesky(temp.val, m*sizeof(_Tp), m, b.val, m*sizeof(_Tp), m);
795
796         return LU(temp.val, m*sizeof(_Tp), m, b.val, m*sizeof(_Tp), m) != 0;
797     }
798 };
799
800
801 template<typename _Tp> struct Matx_FastInvOp<_Tp, 2>
802 {
803     bool operator()(const Matx<_Tp, 2, 2>& a, Matx<_Tp, 2, 2>& b, int) const
804     {
805         _Tp d = determinant(a);
806         if( d == 0 )
807             return false;
808         d = 1/d;
809         b(1,1) = a(0,0)*d;
810         b(0,0) = a(1,1)*d;
811         b(0,1) = -a(0,1)*d;
812         b(1,0) = -a(1,0)*d;
813         return true;
814     }
815 };
816
817
818 template<typename _Tp> struct Matx_FastInvOp<_Tp, 3>
819 {
820     bool operator()(const Matx<_Tp, 3, 3>& a, Matx<_Tp, 3, 3>& b, int) const
821     {
822         _Tp d = (_Tp)determinant(a);
823         if( d == 0 )
824             return false;
825         d = 1/d;
826         b(0,0) = (a(1,1) * a(2,2) - a(1,2) * a(2,1)) * d;
827         b(0,1) = (a(0,2) * a(2,1) - a(0,1) * a(2,2)) * d;
828         b(0,2) = (a(0,1) * a(1,2) - a(0,2) * a(1,1)) * d;
829
830         b(1,0) = (a(1,2) * a(2,0) - a(1,0) * a(2,2)) * d;
831         b(1,1) = (a(0,0) * a(2,2) - a(0,2) * a(2,0)) * d;
832         b(1,2) = (a(0,2) * a(1,0) - a(0,0) * a(1,2)) * d;
833
834         b(2,0) = (a(1,0) * a(2,1) - a(1,1) * a(2,0)) * d;
835         b(2,1) = (a(0,1) * a(2,0) - a(0,0) * a(2,1)) * d;
836         b(2,2) = (a(0,0) * a(1,1) - a(0,1) * a(1,0)) * d;
837         return true;
838     }
839 };
840
841
842 template<typename _Tp, int m, int n> inline
843 Matx<_Tp, n, m> Matx<_Tp, m, n>::inv(int method) const
844 {
845     Matx<_Tp, n, m> b;
846     bool ok;
847     if( method == DECOMP_LU || method == DECOMP_CHOLESKY )
848         ok = Matx_FastInvOp<_Tp, m>()(*this, b, method);
849     else
850     {
851         Mat A(*this, false), B(b, false);
852         ok = (invert(A, B, method) != 0);
853     }
854     return ok ? b : Matx<_Tp, n, m>::zeros();
855 }
856
857
858 template<typename _Tp, int m, int n> struct Matx_FastSolveOp
859 {
860     bool operator()(const Matx<_Tp, m, m>& a, const Matx<_Tp, m, n>& b,
861                     Matx<_Tp, m, n>& x, int method) const
862     {
863         Matx<_Tp, m, m> temp = a;
864         x = b;
865         if( method == DECOMP_CHOLESKY )
866             return Cholesky(temp.val, m*sizeof(_Tp), m, x.val, n*sizeof(_Tp), n);
867
868         return LU(temp.val, m*sizeof(_Tp), m, x.val, n*sizeof(_Tp), n) != 0;
869     }
870 };
871
872
873 template<typename _Tp> struct Matx_FastSolveOp<_Tp, 2, 1>
874 {
875     bool operator()(const Matx<_Tp, 2, 2>& a, const Matx<_Tp, 2, 1>& b,
876                     Matx<_Tp, 2, 1>& x, int) const
877     {
878         _Tp d = determinant(a);
879         if( d == 0 )
880             return false;
881         d = 1/d;
882         x(0) = (b(0)*a(1,1) - b(1)*a(0,1))*d;
883         x(1) = (b(1)*a(0,0) - b(0)*a(1,0))*d;
884         return true;
885     }
886 };
887
888
889 template<typename _Tp> struct Matx_FastSolveOp<_Tp, 3, 1>
890 {
891     bool operator()(const Matx<_Tp, 3, 3>& a, const Matx<_Tp, 3, 1>& b,
892                     Matx<_Tp, 3, 1>& x, int) const
893     {
894         _Tp d = (_Tp)determinant(a);
895         if( d == 0 )
896             return false;
897         d = 1/d;
898         x(0) = d*(b(0)*(a(1,1)*a(2,2) - a(1,2)*a(2,1)) -
899                 a(0,1)*(b(1)*a(2,2) - a(1,2)*b(2)) +
900                 a(0,2)*(b(1)*a(2,1) - a(1,1)*b(2)));
901
902         x(1) = d*(a(0,0)*(b(1)*a(2,2) - a(1,2)*b(2)) -
903                 b(0)*(a(1,0)*a(2,2) - a(1,2)*a(2,0)) +
904                 a(0,2)*(a(1,0)*b(2) - b(1)*a(2,0)));
905
906         x(2) = d*(a(0,0)*(a(1,1)*b(2) - b(1)*a(2,1)) -
907                 a(0,1)*(a(1,0)*b(2) - b(1)*a(2,0)) +
908                 b(0)*(a(1,0)*a(2,1) - a(1,1)*a(2,0)));
909         return true;
910     }
911 };
912
913
914 template<typename _Tp, int m, int n> template<int l> inline
915 Matx<_Tp, n, l> Matx<_Tp, m, n>::solve(const Matx<_Tp, m, l>& rhs, int method) const
916 {
917     Matx<_Tp, n, l> x;
918     bool ok;
919     if( method == DECOMP_LU || method == DECOMP_CHOLESKY )
920         ok = Matx_FastSolveOp<_Tp, m, l>()(*this, rhs, x, method);
921     else
922     {
923         Mat A(*this, false), B(rhs, false), X(x, false);
924         ok = cv::solve(A, B, X, method);
925     }
926
927     return ok ? x : Matx<_Tp, n, l>::zeros();
928 }
929
930 template<typename _Tp, int m, int n> inline
931 Vec<_Tp, n> Matx<_Tp, m, n>::solve(const Vec<_Tp, m>& rhs, int method) const
932 {
933     Matx<_Tp, n, 1> x = solve(reinterpret_cast<const Matx<_Tp, m, 1>&>(rhs), method);
934     return reinterpret_cast<Vec<_Tp, n>&>(x);
935 }
936
937 template<typename _Tp, typename _AccTp> static inline
938 _AccTp normL2Sqr(const _Tp* a, int n)
939 {
940     _AccTp s = 0;
941     int i=0;
942  #if CV_ENABLE_UNROLLED
943     for( ; i <= n - 4; i += 4 )
944     {
945         _AccTp v0 = a[i], v1 = a[i+1], v2 = a[i+2], v3 = a[i+3];
946         s += v0*v0 + v1*v1 + v2*v2 + v3*v3;
947     }
948 #endif
949     for( ; i < n; i++ )
950     {
951         _AccTp v = a[i];
952         s += v*v;
953     }
954     return s;
955 }
956
957
958 template<typename _Tp, typename _AccTp> static inline
959 _AccTp normL1(const _Tp* a, int n)
960 {
961     _AccTp s = 0;
962     int i = 0;
963 #if CV_ENABLE_UNROLLED
964     for(; i <= n - 4; i += 4 )
965     {
966         s += (_AccTp)fast_abs(a[i]) + (_AccTp)fast_abs(a[i+1]) +
967             (_AccTp)fast_abs(a[i+2]) + (_AccTp)fast_abs(a[i+3]);
968     }
969 #endif
970     for( ; i < n; i++ )
971         s += fast_abs(a[i]);
972     return s;
973 }
974
975
976 template<typename _Tp, typename _AccTp> static inline
977 _AccTp normInf(const _Tp* a, int n)
978 {
979     _AccTp s = 0;
980     for( int i = 0; i < n; i++ )
981         s = std::max(s, (_AccTp)fast_abs(a[i]));
982     return s;
983 }
984
985
986 template<typename _Tp, typename _AccTp> static inline
987 _AccTp normL2Sqr(const _Tp* a, const _Tp* b, int n)
988 {
989     _AccTp s = 0;
990     int i= 0;
991 #if CV_ENABLE_UNROLLED
992     for(; i <= n - 4; i += 4 )
993     {
994         _AccTp v0 = _AccTp(a[i] - b[i]), v1 = _AccTp(a[i+1] - b[i+1]), v2 = _AccTp(a[i+2] - b[i+2]), v3 = _AccTp(a[i+3] - b[i+3]);
995         s += v0*v0 + v1*v1 + v2*v2 + v3*v3;
996     }
997 #endif
998     for( ; i < n; i++ )
999     {
1000         _AccTp v = _AccTp(a[i] - b[i]);
1001         s += v*v;
1002     }
1003     return s;
1004 }
1005
1006 CV_EXPORTS float normL2Sqr_(const float* a, const float* b, int n);
1007 CV_EXPORTS float normL1_(const float* a, const float* b, int n);
1008 CV_EXPORTS int normL1_(const uchar* a, const uchar* b, int n);
1009 CV_EXPORTS int normHamming(const uchar* a, const uchar* b, int n);
1010 CV_EXPORTS int normHamming(const uchar* a, const uchar* b, int n, int cellSize);
1011
1012 template<> inline float normL2Sqr(const float* a, const float* b, int n)
1013 {
1014     if( n >= 8 )
1015         return normL2Sqr_(a, b, n);
1016     float s = 0;
1017     for( int i = 0; i < n; i++ )
1018     {
1019         float v = a[i] - b[i];
1020         s += v*v;
1021     }
1022     return s;
1023 }
1024
1025
1026 template<typename _Tp, typename _AccTp> static inline
1027 _AccTp normL1(const _Tp* a, const _Tp* b, int n)
1028 {
1029     _AccTp s = 0;
1030     int i= 0;
1031 #if CV_ENABLE_UNROLLED
1032     for(; i <= n - 4; i += 4 )
1033     {
1034         _AccTp v0 = _AccTp(a[i] - b[i]), v1 = _AccTp(a[i+1] - b[i+1]), v2 = _AccTp(a[i+2] - b[i+2]), v3 = _AccTp(a[i+3] - b[i+3]);
1035         s += std::abs(v0) + std::abs(v1) + std::abs(v2) + std::abs(v3);
1036     }
1037 #endif
1038     for( ; i < n; i++ )
1039     {
1040         _AccTp v = _AccTp(a[i] - b[i]);
1041         s += std::abs(v);
1042     }
1043     return s;
1044 }
1045
1046 template<> inline float normL1(const float* a, const float* b, int n)
1047 {
1048     if( n >= 8 )
1049         return normL1_(a, b, n);
1050     float s = 0;
1051     for( int i = 0; i < n; i++ )
1052     {
1053         float v = a[i] - b[i];
1054         s += std::abs(v);
1055     }
1056     return s;
1057 }
1058
1059 template<> inline int normL1(const uchar* a, const uchar* b, int n)
1060 {
1061     return normL1_(a, b, n);
1062 }
1063
1064 template<typename _Tp, typename _AccTp> static inline
1065 _AccTp normInf(const _Tp* a, const _Tp* b, int n)
1066 {
1067     _AccTp s = 0;
1068     for( int i = 0; i < n; i++ )
1069     {
1070         _AccTp v0 = a[i] - b[i];
1071         s = std::max(s, std::abs(v0));
1072     }
1073     return s;
1074 }
1075
1076
1077 template<typename _Tp, int m, int n> static inline
1078 double norm(const Matx<_Tp, m, n>& M)
1079 {
1080     return std::sqrt(normL2Sqr<_Tp, double>(M.val, m*n));
1081 }
1082
1083
1084 template<typename _Tp, int m, int n> static inline
1085 double norm(const Matx<_Tp, m, n>& M, int normType)
1086 {
1087     return normType == NORM_INF ? (double)normInf<_Tp, typename DataType<_Tp>::work_type>(M.val, m*n) :
1088         normType == NORM_L1 ? (double)normL1<_Tp, typename DataType<_Tp>::work_type>(M.val, m*n) :
1089         std::sqrt((double)normL2Sqr<_Tp, typename DataType<_Tp>::work_type>(M.val, m*n));
1090 }
1091
1092
1093 template<typename _Tp, int m, int n> static inline
1094 bool operator == (const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b)
1095 {
1096     for( int i = 0; i < m*n; i++ )
1097         if( a.val[i] != b.val[i] ) return false;
1098     return true;
1099 }
1100
1101 template<typename _Tp, int m, int n> static inline
1102 bool operator != (const Matx<_Tp, m, n>& a, const Matx<_Tp, m, n>& b)
1103 {
1104     return !(a == b);
1105 }
1106
1107
1108 template<typename _Tp, typename _T2, int m, int n> static inline
1109 MatxCommaInitializer<_Tp, m, n> operator << (const Matx<_Tp, m, n>& mtx, _T2 val)
1110 {
1111     MatxCommaInitializer<_Tp, m, n> commaInitializer((Matx<_Tp, m, n>*)&mtx);
1112     return (commaInitializer, val);
1113 }
1114
1115 template<typename _Tp, int m, int n> inline
1116 MatxCommaInitializer<_Tp, m, n>::MatxCommaInitializer(Matx<_Tp, m, n>* _mtx)
1117     : dst(_mtx), idx(0)
1118 {}
1119
1120 template<typename _Tp, int m, int n> template<typename _T2> inline
1121 MatxCommaInitializer<_Tp, m, n>& MatxCommaInitializer<_Tp, m, n>::operator , (_T2 value)
1122 {
1123     CV_DbgAssert( idx < m*n );
1124     dst->val[idx++] = saturate_cast<_Tp>(value);
1125     return *this;
1126 }
1127
1128 template<typename _Tp, int m, int n> inline
1129 Matx<_Tp, m, n> MatxCommaInitializer<_Tp, m, n>::operator *() const
1130 {
1131     CV_DbgAssert( idx == n*m );
1132     return *dst;
1133 }
1134
1135 /////////////////////////// short vector (Vec) /////////////////////////////
1136
1137 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec()
1138 {}
1139
1140 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0)
1141     : Matx<_Tp, cn, 1>(v0)
1142 {}
1143
1144 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1)
1145     : Matx<_Tp, cn, 1>(v0, v1)
1146 {}
1147
1148 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2)
1149     : Matx<_Tp, cn, 1>(v0, v1, v2)
1150 {}
1151
1152 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3)
1153     : Matx<_Tp, cn, 1>(v0, v1, v2, v3)
1154 {}
1155
1156 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3, _Tp v4)
1157     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4)
1158 {}
1159
1160 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3, _Tp v4, _Tp v5)
1161     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4, v5)
1162 {}
1163
1164 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
1165                                                         _Tp v4, _Tp v5, _Tp v6)
1166     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4, v5, v6)
1167 {}
1168
1169 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
1170                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7)
1171     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4, v5, v6, v7)
1172 {}
1173
1174 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
1175                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
1176                                                         _Tp v8)
1177     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4, v5, v6, v7, v8)
1178 {}
1179
1180 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
1181                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
1182                                                         _Tp v8, _Tp v9)
1183     : Matx<_Tp, cn, 1>(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9)
1184 {}
1185
1186 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(const _Tp* values)
1187     : Matx<_Tp, cn, 1>(values)
1188 {}
1189
1190
1191 template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(const Vec<_Tp, cn>& m)
1192     : Matx<_Tp, cn, 1>(m.val)
1193 {}
1194
1195 template<typename _Tp, int cn> inline
1196 Vec<_Tp, cn>::Vec(const Matx<_Tp, cn, 1>& a, const Matx<_Tp, cn, 1>& b, Matx_AddOp op)
1197 : Matx<_Tp, cn, 1>(a, b, op)
1198 {}
1199
1200 template<typename _Tp, int cn> inline
1201 Vec<_Tp, cn>::Vec(const Matx<_Tp, cn, 1>& a, const Matx<_Tp, cn, 1>& b, Matx_SubOp op)
1202 : Matx<_Tp, cn, 1>(a, b, op)
1203 {}
1204
1205 template<typename _Tp, int cn> template<typename _T2> inline
1206 Vec<_Tp, cn>::Vec(const Matx<_Tp, cn, 1>& a, _T2 alpha, Matx_ScaleOp op)
1207 : Matx<_Tp, cn, 1>(a, alpha, op)
1208 {}
1209
1210 template<typename _Tp, int cn> inline Vec<_Tp, cn> Vec<_Tp, cn>::all(_Tp alpha)
1211 {
1212     Vec v;
1213     for( int i = 0; i < cn; i++ ) v.val[i] = alpha;
1214     return v;
1215 }
1216
1217 template<typename _Tp, int cn> inline Vec<_Tp, cn> Vec<_Tp, cn>::mul(const Vec<_Tp, cn>& v) const
1218 {
1219     Vec<_Tp, cn> w;
1220     for( int i = 0; i < cn; i++ ) w.val[i] = saturate_cast<_Tp>(this->val[i]*v.val[i]);
1221     return w;
1222 }
1223
1224 template<typename _Tp> Vec<_Tp, 2> conjugate(const Vec<_Tp, 2>& v)
1225 {
1226     return Vec<_Tp, 2>(v[0], -v[1]);
1227 }
1228
1229 template<typename _Tp> Vec<_Tp, 4> conjugate(const Vec<_Tp, 4>& v)
1230 {
1231     return Vec<_Tp, 4>(v[0], -v[1], -v[2], -v[3]);
1232 }
1233
1234 template<> inline Vec<float, 2> Vec<float, 2>::conj() const
1235 {
1236     return conjugate(*this);
1237 }
1238
1239 template<> inline Vec<double, 2> Vec<double, 2>::conj() const
1240 {
1241     return conjugate(*this);
1242 }
1243
1244 template<> inline Vec<float, 4> Vec<float, 4>::conj() const
1245 {
1246     return conjugate(*this);
1247 }
1248
1249 template<> inline Vec<double, 4> Vec<double, 4>::conj() const
1250 {
1251     return conjugate(*this);
1252 }
1253
1254 template<typename _Tp, int cn> inline Vec<_Tp, cn> Vec<_Tp, cn>::cross(const Vec<_Tp, cn>&) const
1255 {
1256     CV_Error(CV_StsError, "for arbitrary-size vector there is no cross-product defined");
1257     return Vec<_Tp, cn>();
1258 }
1259
1260 template<typename _Tp, int cn> template<typename T2>
1261 inline Vec<_Tp, cn>::operator Vec<T2, cn>() const
1262 {
1263     Vec<T2, cn> v;
1264     for( int i = 0; i < cn; i++ ) v.val[i] = saturate_cast<T2>(this->val[i]);
1265     return v;
1266 }
1267
1268 template<typename _Tp, int cn> inline Vec<_Tp, cn>::operator CvScalar() const
1269 {
1270     CvScalar s = {{0,0,0,0}};
1271     int i;
1272     for( i = 0; i < std::min(cn, 4); i++ ) s.val[i] = this->val[i];
1273     for( ; i < 4; i++ ) s.val[i] = 0;
1274     return s;
1275 }
1276
1277 template<typename _Tp, int cn> inline const _Tp& Vec<_Tp, cn>::operator [](int i) const
1278 {
1279     CV_DbgAssert( (unsigned)i < (unsigned)cn );
1280     return this->val[i];
1281 }
1282
1283 template<typename _Tp, int cn> inline _Tp& Vec<_Tp, cn>::operator [](int i)
1284 {
1285     CV_DbgAssert( (unsigned)i < (unsigned)cn );
1286     return this->val[i];
1287 }
1288
1289 template<typename _Tp, int cn> inline const _Tp& Vec<_Tp, cn>::operator ()(int i) const
1290 {
1291     CV_DbgAssert( (unsigned)i < (unsigned)cn );
1292     return this->val[i];
1293 }
1294
1295 template<typename _Tp, int cn> inline _Tp& Vec<_Tp, cn>::operator ()(int i)
1296 {
1297     CV_DbgAssert( (unsigned)i < (unsigned)cn );
1298     return this->val[i];
1299 }
1300
1301 template<typename _Tp1, typename _Tp2, int cn> static inline Vec<_Tp1, cn>&
1302 operator += (Vec<_Tp1, cn>& a, const Vec<_Tp2, cn>& b)
1303 {
1304     for( int i = 0; i < cn; i++ )
1305         a.val[i] = saturate_cast<_Tp1>(a.val[i] + b.val[i]);
1306     return a;
1307 }
1308
1309 template<typename _Tp1, typename _Tp2, int cn> static inline Vec<_Tp1, cn>&
1310 operator -= (Vec<_Tp1, cn>& a, const Vec<_Tp2, cn>& b)
1311 {
1312     for( int i = 0; i < cn; i++ )
1313         a.val[i] = saturate_cast<_Tp1>(a.val[i] - b.val[i]);
1314     return a;
1315 }
1316
1317 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1318 operator + (const Vec<_Tp, cn>& a, const Vec<_Tp, cn>& b)
1319 {
1320     return Vec<_Tp, cn>(a, b, Matx_AddOp());
1321 }
1322
1323 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1324 operator - (const Vec<_Tp, cn>& a, const Vec<_Tp, cn>& b)
1325 {
1326     return Vec<_Tp, cn>(a, b, Matx_SubOp());
1327 }
1328
1329 template<typename _Tp, int cn> static inline
1330 Vec<_Tp, cn>& operator *= (Vec<_Tp, cn>& a, int alpha)
1331 {
1332     for( int i = 0; i < cn; i++ )
1333         a[i] = saturate_cast<_Tp>(a[i]*alpha);
1334     return a;
1335 }
1336
1337 template<typename _Tp, int cn> static inline
1338 Vec<_Tp, cn>& operator *= (Vec<_Tp, cn>& a, float alpha)
1339 {
1340     for( int i = 0; i < cn; i++ )
1341         a[i] = saturate_cast<_Tp>(a[i]*alpha);
1342     return a;
1343 }
1344
1345 template<typename _Tp, int cn> static inline
1346 Vec<_Tp, cn>& operator *= (Vec<_Tp, cn>& a, double alpha)
1347 {
1348     for( int i = 0; i < cn; i++ )
1349         a[i] = saturate_cast<_Tp>(a[i]*alpha);
1350     return a;
1351 }
1352
1353 template<typename _Tp, int cn> static inline
1354 Vec<_Tp, cn>& operator /= (Vec<_Tp, cn>& a, int alpha)
1355 {
1356     double ialpha = 1./alpha;
1357     for( int i = 0; i < cn; i++ )
1358         a[i] = saturate_cast<_Tp>(a[i]*ialpha);
1359     return a;
1360 }
1361
1362 template<typename _Tp, int cn> static inline
1363 Vec<_Tp, cn>& operator /= (Vec<_Tp, cn>& a, float alpha)
1364 {
1365     float ialpha = 1.f/alpha;
1366     for( int i = 0; i < cn; i++ )
1367         a[i] = saturate_cast<_Tp>(a[i]*ialpha);
1368     return a;
1369 }
1370
1371 template<typename _Tp, int cn> static inline
1372 Vec<_Tp, cn>& operator /= (Vec<_Tp, cn>& a, double alpha)
1373 {
1374     double ialpha = 1./alpha;
1375     for( int i = 0; i < cn; i++ )
1376         a[i] = saturate_cast<_Tp>(a[i]*ialpha);
1377     return a;
1378 }
1379
1380 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1381 operator * (const Vec<_Tp, cn>& a, int alpha)
1382 {
1383     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1384 }
1385
1386 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1387 operator * (int alpha, const Vec<_Tp, cn>& a)
1388 {
1389     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1390 }
1391
1392 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1393 operator * (const Vec<_Tp, cn>& a, float alpha)
1394 {
1395     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1396 }
1397
1398 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1399 operator * (float alpha, const Vec<_Tp, cn>& a)
1400 {
1401     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1402 }
1403
1404 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1405 operator * (const Vec<_Tp, cn>& a, double alpha)
1406 {
1407     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1408 }
1409
1410 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1411 operator * (double alpha, const Vec<_Tp, cn>& a)
1412 {
1413     return Vec<_Tp, cn>(a, alpha, Matx_ScaleOp());
1414 }
1415
1416 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1417 operator / (const Vec<_Tp, cn>& a, int alpha)
1418 {
1419     return Vec<_Tp, cn>(a, 1./alpha, Matx_ScaleOp());
1420 }
1421
1422 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1423 operator / (const Vec<_Tp, cn>& a, float alpha)
1424 {
1425     return Vec<_Tp, cn>(a, 1.f/alpha, Matx_ScaleOp());
1426 }
1427
1428 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1429 operator / (const Vec<_Tp, cn>& a, double alpha)
1430 {
1431     return Vec<_Tp, cn>(a, 1./alpha, Matx_ScaleOp());
1432 }
1433
1434 template<typename _Tp, int cn> static inline Vec<_Tp, cn>
1435 operator - (const Vec<_Tp, cn>& a)
1436 {
1437     Vec<_Tp,cn> t;
1438     for( int i = 0; i < cn; i++ ) t.val[i] = saturate_cast<_Tp>(-a.val[i]);
1439     return t;
1440 }
1441
1442 template<typename _Tp> inline Vec<_Tp, 4> operator * (const Vec<_Tp, 4>& v1, const Vec<_Tp, 4>& v2)
1443 {
1444     return Vec<_Tp, 4>(saturate_cast<_Tp>(v1[0]*v2[0] - v1[1]*v2[1] - v1[2]*v2[2] - v1[3]*v2[3]),
1445                        saturate_cast<_Tp>(v1[0]*v2[1] + v1[1]*v2[0] + v1[2]*v2[3] - v1[3]*v2[2]),
1446                        saturate_cast<_Tp>(v1[0]*v2[2] - v1[1]*v2[3] + v1[2]*v2[0] + v1[3]*v2[1]),
1447                        saturate_cast<_Tp>(v1[0]*v2[3] + v1[1]*v2[2] - v1[2]*v2[1] + v1[3]*v2[0]));
1448 }
1449
1450 template<typename _Tp> inline Vec<_Tp, 4>& operator *= (Vec<_Tp, 4>& v1, const Vec<_Tp, 4>& v2)
1451 {
1452     v1 = v1 * v2;
1453     return v1;
1454 }
1455
1456 template<> inline Vec<float, 3> Vec<float, 3>::cross(const Vec<float, 3>& v) const
1457 {
1458     return Vec<float,3>(val[1]*v.val[2] - val[2]*v.val[1],
1459                      val[2]*v.val[0] - val[0]*v.val[2],
1460                      val[0]*v.val[1] - val[1]*v.val[0]);
1461 }
1462
1463 template<> inline Vec<double, 3> Vec<double, 3>::cross(const Vec<double, 3>& v) const
1464 {
1465     return Vec<double,3>(val[1]*v.val[2] - val[2]*v.val[1],
1466                      val[2]*v.val[0] - val[0]*v.val[2],
1467                      val[0]*v.val[1] - val[1]*v.val[0]);
1468 }
1469
1470 template<typename _Tp, int cn> inline Vec<_Tp, cn> normalize(const Vec<_Tp, cn>& v)
1471 {
1472     double nv = norm(v);
1473     return v * (nv ? 1./nv : 0.);
1474 }
1475
1476 template<typename _Tp, typename _T2, int cn> static inline
1477 VecCommaInitializer<_Tp, cn> operator << (const Vec<_Tp, cn>& vec, _T2 val)
1478 {
1479     VecCommaInitializer<_Tp, cn> commaInitializer((Vec<_Tp, cn>*)&vec);
1480     return (commaInitializer, val);
1481 }
1482
1483 template<typename _Tp, int cn> inline
1484 VecCommaInitializer<_Tp, cn>::VecCommaInitializer(Vec<_Tp, cn>* _vec)
1485     : MatxCommaInitializer<_Tp, cn, 1>(_vec)
1486 {}
1487
1488 template<typename _Tp, int cn> template<typename _T2> inline
1489 VecCommaInitializer<_Tp, cn>& VecCommaInitializer<_Tp, cn>::operator , (_T2 value)
1490 {
1491     CV_DbgAssert( this->idx < cn );
1492     this->dst->val[this->idx++] = saturate_cast<_Tp>(value);
1493     return *this;
1494 }
1495
1496 template<typename _Tp, int cn> inline
1497 Vec<_Tp, cn> VecCommaInitializer<_Tp, cn>::operator *() const
1498 {
1499     CV_DbgAssert( this->idx == cn );
1500     return *this->dst;
1501 }
1502
1503 //////////////////////////////// Complex //////////////////////////////
1504
1505 template<typename _Tp> inline Complex<_Tp>::Complex() : re(0), im(0) {}
1506 template<typename _Tp> inline Complex<_Tp>::Complex( _Tp _re, _Tp _im ) : re(_re), im(_im) {}
1507 template<typename _Tp> template<typename T2> inline Complex<_Tp>::operator Complex<T2>() const
1508 { return Complex<T2>(saturate_cast<T2>(re), saturate_cast<T2>(im)); }
1509 template<typename _Tp> inline Complex<_Tp> Complex<_Tp>::conj() const
1510 { return Complex<_Tp>(re, -im); }
1511
1512 template<typename _Tp> static inline
1513 bool operator == (const Complex<_Tp>& a, const Complex<_Tp>& b)
1514 { return a.re == b.re && a.im == b.im; }
1515
1516 template<typename _Tp> static inline
1517 bool operator != (const Complex<_Tp>& a, const Complex<_Tp>& b)
1518 { return a.re != b.re || a.im != b.im; }
1519
1520 template<typename _Tp> static inline
1521 Complex<_Tp> operator + (const Complex<_Tp>& a, const Complex<_Tp>& b)
1522 { return Complex<_Tp>( a.re + b.re, a.im + b.im ); }
1523
1524 template<typename _Tp> static inline
1525 Complex<_Tp>& operator += (Complex<_Tp>& a, const Complex<_Tp>& b)
1526 { a.re += b.re; a.im += b.im; return a; }
1527
1528 template<typename _Tp> static inline
1529 Complex<_Tp> operator - (const Complex<_Tp>& a, const Complex<_Tp>& b)
1530 { return Complex<_Tp>( a.re - b.re, a.im - b.im ); }
1531
1532 template<typename _Tp> static inline
1533 Complex<_Tp>& operator -= (Complex<_Tp>& a, const Complex<_Tp>& b)
1534 { a.re -= b.re; a.im -= b.im; return a; }
1535
1536 template<typename _Tp> static inline
1537 Complex<_Tp> operator - (const Complex<_Tp>& a)
1538 { return Complex<_Tp>(-a.re, -a.im); }
1539
1540 template<typename _Tp> static inline
1541 Complex<_Tp> operator * (const Complex<_Tp>& a, const Complex<_Tp>& b)
1542 { return Complex<_Tp>( a.re*b.re - a.im*b.im, a.re*b.im + a.im*b.re ); }
1543
1544 template<typename _Tp> static inline
1545 Complex<_Tp> operator * (const Complex<_Tp>& a, _Tp b)
1546 { return Complex<_Tp>( a.re*b, a.im*b ); }
1547
1548 template<typename _Tp> static inline
1549 Complex<_Tp> operator * (_Tp b, const Complex<_Tp>& a)
1550 { return Complex<_Tp>( a.re*b, a.im*b ); }
1551
1552 template<typename _Tp> static inline
1553 Complex<_Tp> operator + (const Complex<_Tp>& a, _Tp b)
1554 { return Complex<_Tp>( a.re + b, a.im ); }
1555
1556 template<typename _Tp> static inline
1557 Complex<_Tp> operator - (const Complex<_Tp>& a, _Tp b)
1558 { return Complex<_Tp>( a.re - b, a.im ); }
1559
1560 template<typename _Tp> static inline
1561 Complex<_Tp> operator + (_Tp b, const Complex<_Tp>& a)
1562 { return Complex<_Tp>( a.re + b, a.im ); }
1563
1564 template<typename _Tp> static inline
1565 Complex<_Tp> operator - (_Tp b, const Complex<_Tp>& a)
1566 { return Complex<_Tp>( b - a.re, -a.im ); }
1567
1568 template<typename _Tp> static inline
1569 Complex<_Tp>& operator += (Complex<_Tp>& a, _Tp b)
1570 { a.re += b; return a; }
1571
1572 template<typename _Tp> static inline
1573 Complex<_Tp>& operator -= (Complex<_Tp>& a, _Tp b)
1574 { a.re -= b; return a; }
1575
1576 template<typename _Tp> static inline
1577 Complex<_Tp>& operator *= (Complex<_Tp>& a, _Tp b)
1578 { a.re *= b; a.im *= b; return a; }
1579
1580 template<typename _Tp> static inline
1581 double abs(const Complex<_Tp>& a)
1582 { return std::sqrt( (double)a.re*a.re + (double)a.im*a.im); }
1583
1584 template<typename _Tp> static inline
1585 Complex<_Tp> operator / (const Complex<_Tp>& a, const Complex<_Tp>& b)
1586 {
1587     double t = 1./((double)b.re*b.re + (double)b.im*b.im);
1588     return Complex<_Tp>( (_Tp)((a.re*b.re + a.im*b.im)*t),
1589                         (_Tp)((-a.re*b.im + a.im*b.re)*t) );
1590 }
1591
1592 template<typename _Tp> static inline
1593 Complex<_Tp>& operator /= (Complex<_Tp>& a, const Complex<_Tp>& b)
1594 {
1595     return (a = a / b);
1596 }
1597
1598 template<typename _Tp> static inline
1599 Complex<_Tp> operator / (const Complex<_Tp>& a, _Tp b)
1600 {
1601     _Tp t = (_Tp)1/b;
1602     return Complex<_Tp>( a.re*t, a.im*t );
1603 }
1604
1605 template<typename _Tp> static inline
1606 Complex<_Tp> operator / (_Tp b, const Complex<_Tp>& a)
1607 {
1608     return Complex<_Tp>(b)/a;
1609 }
1610
1611 template<typename _Tp> static inline
1612 Complex<_Tp> operator /= (const Complex<_Tp>& a, _Tp b)
1613 {
1614     _Tp t = (_Tp)1/b;
1615     a.re *= t; a.im *= t; return a;
1616 }
1617
1618 //////////////////////////////// 2D Point ////////////////////////////////
1619
1620 template<typename _Tp> inline Point_<_Tp>::Point_() : x(0), y(0) {}
1621 template<typename _Tp> inline Point_<_Tp>::Point_(_Tp _x, _Tp _y) : x(_x), y(_y) {}
1622 template<typename _Tp> inline Point_<_Tp>::Point_(const Point_& pt) : x(pt.x), y(pt.y) {}
1623 template<typename _Tp> inline Point_<_Tp>::Point_(const CvPoint& pt) : x((_Tp)pt.x), y((_Tp)pt.y) {}
1624 template<typename _Tp> inline Point_<_Tp>::Point_(const CvPoint2D32f& pt)
1625     : x(saturate_cast<_Tp>(pt.x)), y(saturate_cast<_Tp>(pt.y)) {}
1626 template<typename _Tp> inline Point_<_Tp>::Point_(const Size_<_Tp>& sz) : x(sz.width), y(sz.height) {}
1627 template<typename _Tp> inline Point_<_Tp>::Point_(const Vec<_Tp,2>& v) : x(v[0]), y(v[1]) {}
1628 template<typename _Tp> inline Point_<_Tp>& Point_<_Tp>::operator = (const Point_& pt)
1629 { x = pt.x; y = pt.y; return *this; }
1630
1631 template<typename _Tp> template<typename _Tp2> inline Point_<_Tp>::operator Point_<_Tp2>() const
1632 { return Point_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y)); }
1633 template<typename _Tp> inline Point_<_Tp>::operator CvPoint() const
1634 { return cvPoint(saturate_cast<int>(x), saturate_cast<int>(y)); }
1635 template<typename _Tp> inline Point_<_Tp>::operator CvPoint2D32f() const
1636 { return cvPoint2D32f((float)x, (float)y); }
1637 template<typename _Tp> inline Point_<_Tp>::operator Vec<_Tp, 2>() const
1638 { return Vec<_Tp, 2>(x, y); }
1639
1640 template<typename _Tp> inline _Tp Point_<_Tp>::dot(const Point_& pt) const
1641 { return saturate_cast<_Tp>(x*pt.x + y*pt.y); }
1642 template<typename _Tp> inline double Point_<_Tp>::ddot(const Point_& pt) const
1643 { return (double)x*pt.x + (double)y*pt.y; }
1644
1645 template<typename _Tp> inline double Point_<_Tp>::cross(const Point_& pt) const
1646 { return (double)x*pt.y - (double)y*pt.x; }
1647
1648 template<typename _Tp> static inline Point_<_Tp>&
1649 operator += (Point_<_Tp>& a, const Point_<_Tp>& b)
1650 {
1651     a.x = saturate_cast<_Tp>(a.x + b.x);
1652     a.y = saturate_cast<_Tp>(a.y + b.y);
1653     return a;
1654 }
1655
1656 template<typename _Tp> static inline Point_<_Tp>&
1657 operator -= (Point_<_Tp>& a, const Point_<_Tp>& b)
1658 {
1659     a.x = saturate_cast<_Tp>(a.x - b.x);
1660     a.y = saturate_cast<_Tp>(a.y - b.y);
1661     return a;
1662 }
1663
1664 template<typename _Tp> static inline Point_<_Tp>&
1665 operator *= (Point_<_Tp>& a, int b)
1666 {
1667     a.x = saturate_cast<_Tp>(a.x*b);
1668     a.y = saturate_cast<_Tp>(a.y*b);
1669     return a;
1670 }
1671
1672 template<typename _Tp> static inline Point_<_Tp>&
1673 operator *= (Point_<_Tp>& a, float b)
1674 {
1675     a.x = saturate_cast<_Tp>(a.x*b);
1676     a.y = saturate_cast<_Tp>(a.y*b);
1677     return a;
1678 }
1679
1680 template<typename _Tp> static inline Point_<_Tp>&
1681 operator *= (Point_<_Tp>& a, double b)
1682 {
1683     a.x = saturate_cast<_Tp>(a.x*b);
1684     a.y = saturate_cast<_Tp>(a.y*b);
1685     return a;
1686 }
1687
1688 template<typename _Tp> static inline double norm(const Point_<_Tp>& pt)
1689 { return std::sqrt((double)pt.x*pt.x + (double)pt.y*pt.y); }
1690
1691 template<typename _Tp> static inline bool operator == (const Point_<_Tp>& a, const Point_<_Tp>& b)
1692 { return a.x == b.x && a.y == b.y; }
1693
1694 template<typename _Tp> static inline bool operator != (const Point_<_Tp>& a, const Point_<_Tp>& b)
1695 { return a.x != b.x || a.y != b.y; }
1696
1697 template<typename _Tp> static inline Point_<_Tp> operator + (const Point_<_Tp>& a, const Point_<_Tp>& b)
1698 { return Point_<_Tp>( saturate_cast<_Tp>(a.x + b.x), saturate_cast<_Tp>(a.y + b.y) ); }
1699
1700 template<typename _Tp> static inline Point_<_Tp> operator - (const Point_<_Tp>& a, const Point_<_Tp>& b)
1701 { return Point_<_Tp>( saturate_cast<_Tp>(a.x - b.x), saturate_cast<_Tp>(a.y - b.y) ); }
1702
1703 template<typename _Tp> static inline Point_<_Tp> operator - (const Point_<_Tp>& a)
1704 { return Point_<_Tp>( saturate_cast<_Tp>(-a.x), saturate_cast<_Tp>(-a.y) ); }
1705
1706 template<typename _Tp> static inline Point_<_Tp> operator * (const Point_<_Tp>& a, int b)
1707 { return Point_<_Tp>( saturate_cast<_Tp>(a.x*b), saturate_cast<_Tp>(a.y*b) ); }
1708
1709 template<typename _Tp> static inline Point_<_Tp> operator * (int a, const Point_<_Tp>& b)
1710 { return Point_<_Tp>( saturate_cast<_Tp>(b.x*a), saturate_cast<_Tp>(b.y*a) ); }
1711
1712 template<typename _Tp> static inline Point_<_Tp> operator * (const Point_<_Tp>& a, float b)
1713 { return Point_<_Tp>( saturate_cast<_Tp>(a.x*b), saturate_cast<_Tp>(a.y*b) ); }
1714
1715 template<typename _Tp> static inline Point_<_Tp> operator * (float a, const Point_<_Tp>& b)
1716 { return Point_<_Tp>( saturate_cast<_Tp>(b.x*a), saturate_cast<_Tp>(b.y*a) ); }
1717
1718 template<typename _Tp> static inline Point_<_Tp> operator * (const Point_<_Tp>& a, double b)
1719 { return Point_<_Tp>( saturate_cast<_Tp>(a.x*b), saturate_cast<_Tp>(a.y*b) ); }
1720
1721 template<typename _Tp> static inline Point_<_Tp> operator * (double a, const Point_<_Tp>& b)
1722 { return Point_<_Tp>( saturate_cast<_Tp>(b.x*a), saturate_cast<_Tp>(b.y*a) ); }
1723
1724 //////////////////////////////// 3D Point ////////////////////////////////
1725
1726 template<typename _Tp> inline Point3_<_Tp>::Point3_() : x(0), y(0), z(0) {}
1727 template<typename _Tp> inline Point3_<_Tp>::Point3_(_Tp _x, _Tp _y, _Tp _z) : x(_x), y(_y), z(_z) {}
1728 template<typename _Tp> inline Point3_<_Tp>::Point3_(const Point3_& pt) : x(pt.x), y(pt.y), z(pt.z) {}
1729 template<typename _Tp> inline Point3_<_Tp>::Point3_(const Point_<_Tp>& pt) : x(pt.x), y(pt.y), z(_Tp()) {}
1730 template<typename _Tp> inline Point3_<_Tp>::Point3_(const CvPoint3D32f& pt) :
1731     x(saturate_cast<_Tp>(pt.x)), y(saturate_cast<_Tp>(pt.y)), z(saturate_cast<_Tp>(pt.z)) {}
1732 template<typename _Tp> inline Point3_<_Tp>::Point3_(const Vec<_Tp, 3>& v) : x(v[0]), y(v[1]), z(v[2]) {}
1733
1734 template<typename _Tp> template<typename _Tp2> inline Point3_<_Tp>::operator Point3_<_Tp2>() const
1735 { return Point3_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y), saturate_cast<_Tp2>(z)); }
1736
1737 template<typename _Tp> inline Point3_<_Tp>::operator CvPoint3D32f() const
1738 { return cvPoint3D32f((float)x, (float)y, (float)z); }
1739
1740 template<typename _Tp> inline Point3_<_Tp>::operator Vec<_Tp, 3>() const
1741 { return Vec<_Tp, 3>(x, y, z); }
1742
1743 template<typename _Tp> inline Point3_<_Tp>& Point3_<_Tp>::operator = (const Point3_& pt)
1744 { x = pt.x; y = pt.y; z = pt.z; return *this; }
1745
1746 template<typename _Tp> inline _Tp Point3_<_Tp>::dot(const Point3_& pt) const
1747 { return saturate_cast<_Tp>(x*pt.x + y*pt.y + z*pt.z); }
1748 template<typename _Tp> inline double Point3_<_Tp>::ddot(const Point3_& pt) const
1749 { return (double)x*pt.x + (double)y*pt.y + (double)z*pt.z; }
1750
1751 template<typename _Tp> inline Point3_<_Tp> Point3_<_Tp>::cross(const Point3_<_Tp>& pt) const
1752 {
1753     return Point3_<_Tp>(y*pt.z - z*pt.y, z*pt.x - x*pt.z, x*pt.y - y*pt.x);
1754 }
1755
1756 template<typename _Tp> static inline Point3_<_Tp>&
1757 operator += (Point3_<_Tp>& a, const Point3_<_Tp>& b)
1758 {
1759     a.x = saturate_cast<_Tp>(a.x + b.x);
1760     a.y = saturate_cast<_Tp>(a.y + b.y);
1761     a.z = saturate_cast<_Tp>(a.z + b.z);
1762     return a;
1763 }
1764
1765 template<typename _Tp> static inline Point3_<_Tp>&
1766 operator -= (Point3_<_Tp>& a, const Point3_<_Tp>& b)
1767 {
1768     a.x = saturate_cast<_Tp>(a.x - b.x);
1769     a.y = saturate_cast<_Tp>(a.y - b.y);
1770     a.z = saturate_cast<_Tp>(a.z - b.z);
1771     return a;
1772 }
1773
1774 template<typename _Tp> static inline Point3_<_Tp>&
1775 operator *= (Point3_<_Tp>& a, int b)
1776 {
1777     a.x = saturate_cast<_Tp>(a.x*b);
1778     a.y = saturate_cast<_Tp>(a.y*b);
1779     a.z = saturate_cast<_Tp>(a.z*b);
1780     return a;
1781 }
1782
1783 template<typename _Tp> static inline Point3_<_Tp>&
1784 operator *= (Point3_<_Tp>& a, float b)
1785 {
1786     a.x = saturate_cast<_Tp>(a.x*b);
1787     a.y = saturate_cast<_Tp>(a.y*b);
1788     a.z = saturate_cast<_Tp>(a.z*b);
1789     return a;
1790 }
1791
1792 template<typename _Tp> static inline Point3_<_Tp>&
1793 operator *= (Point3_<_Tp>& a, double b)
1794 {
1795     a.x = saturate_cast<_Tp>(a.x*b);
1796     a.y = saturate_cast<_Tp>(a.y*b);
1797     a.z = saturate_cast<_Tp>(a.z*b);
1798     return a;
1799 }
1800
1801 template<typename _Tp> static inline double norm(const Point3_<_Tp>& pt)
1802 { return std::sqrt((double)pt.x*pt.x + (double)pt.y*pt.y + (double)pt.z*pt.z); }
1803
1804 template<typename _Tp> static inline bool operator == (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
1805 { return a.x == b.x && a.y == b.y && a.z == b.z; }
1806
1807 template<typename _Tp> static inline bool operator != (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
1808 { return a.x != b.x || a.y != b.y || a.z != b.z; }
1809
1810 template<typename _Tp> static inline Point3_<_Tp> operator + (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
1811 { return Point3_<_Tp>( saturate_cast<_Tp>(a.x + b.x),
1812                       saturate_cast<_Tp>(a.y + b.y),
1813                       saturate_cast<_Tp>(a.z + b.z)); }
1814
1815 template<typename _Tp> static inline Point3_<_Tp> operator - (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
1816 { return Point3_<_Tp>( saturate_cast<_Tp>(a.x - b.x),
1817                         saturate_cast<_Tp>(a.y - b.y),
1818                         saturate_cast<_Tp>(a.z - b.z)); }
1819
1820 template<typename _Tp> static inline Point3_<_Tp> operator - (const Point3_<_Tp>& a)
1821 { return Point3_<_Tp>( saturate_cast<_Tp>(-a.x),
1822                       saturate_cast<_Tp>(-a.y),
1823                       saturate_cast<_Tp>(-a.z) ); }
1824
1825 template<typename _Tp> static inline Point3_<_Tp> operator * (const Point3_<_Tp>& a, int b)
1826 { return Point3_<_Tp>( saturate_cast<_Tp>(a.x*b),
1827                       saturate_cast<_Tp>(a.y*b),
1828                       saturate_cast<_Tp>(a.z*b) ); }
1829
1830 template<typename _Tp> static inline Point3_<_Tp> operator * (int a, const Point3_<_Tp>& b)
1831 { return Point3_<_Tp>( saturate_cast<_Tp>(b.x*a),
1832                       saturate_cast<_Tp>(b.y*a),
1833                       saturate_cast<_Tp>(b.z*a) ); }
1834
1835 template<typename _Tp> static inline Point3_<_Tp> operator * (const Point3_<_Tp>& a, float b)
1836 { return Point3_<_Tp>( saturate_cast<_Tp>(a.x*b),
1837                       saturate_cast<_Tp>(a.y*b),
1838                       saturate_cast<_Tp>(a.z*b) ); }
1839
1840 template<typename _Tp> static inline Point3_<_Tp> operator * (float a, const Point3_<_Tp>& b)
1841 { return Point3_<_Tp>( saturate_cast<_Tp>(b.x*a),
1842                       saturate_cast<_Tp>(b.y*a),
1843                       saturate_cast<_Tp>(b.z*a) ); }
1844
1845 template<typename _Tp> static inline Point3_<_Tp> operator * (const Point3_<_Tp>& a, double b)
1846 { return Point3_<_Tp>( saturate_cast<_Tp>(a.x*b),
1847                       saturate_cast<_Tp>(a.y*b),
1848                       saturate_cast<_Tp>(a.z*b) ); }
1849
1850 template<typename _Tp> static inline Point3_<_Tp> operator * (double a, const Point3_<_Tp>& b)
1851 { return Point3_<_Tp>( saturate_cast<_Tp>(b.x*a),
1852                       saturate_cast<_Tp>(b.y*a),
1853                       saturate_cast<_Tp>(b.z*a) ); }
1854
1855 //////////////////////////////// Size ////////////////////////////////
1856
1857 template<typename _Tp> inline Size_<_Tp>::Size_()
1858     : width(0), height(0) {}
1859 template<typename _Tp> inline Size_<_Tp>::Size_(_Tp _width, _Tp _height)
1860     : width(_width), height(_height) {}
1861 template<typename _Tp> inline Size_<_Tp>::Size_(const Size_& sz)
1862     : width(sz.width), height(sz.height) {}
1863 template<typename _Tp> inline Size_<_Tp>::Size_(const CvSize& sz)
1864     : width(saturate_cast<_Tp>(sz.width)), height(saturate_cast<_Tp>(sz.height)) {}
1865 template<typename _Tp> inline Size_<_Tp>::Size_(const CvSize2D32f& sz)
1866     : width(saturate_cast<_Tp>(sz.width)), height(saturate_cast<_Tp>(sz.height)) {}
1867 template<typename _Tp> inline Size_<_Tp>::Size_(const Point_<_Tp>& pt) : width(pt.x), height(pt.y) {}
1868
1869 template<typename _Tp> template<typename _Tp2> inline Size_<_Tp>::operator Size_<_Tp2>() const
1870 { return Size_<_Tp2>(saturate_cast<_Tp2>(width), saturate_cast<_Tp2>(height)); }
1871 template<typename _Tp> inline Size_<_Tp>::operator CvSize() const
1872 { return cvSize(saturate_cast<int>(width), saturate_cast<int>(height)); }
1873 template<typename _Tp> inline Size_<_Tp>::operator CvSize2D32f() const
1874 { return cvSize2D32f((float)width, (float)height); }
1875
1876 template<typename _Tp> inline Size_<_Tp>& Size_<_Tp>::operator = (const Size_<_Tp>& sz)
1877 { width = sz.width; height = sz.height; return *this; }
1878 template<typename _Tp> static inline Size_<_Tp> operator * (const Size_<_Tp>& a, _Tp b)
1879 { return Size_<_Tp>(a.width * b, a.height * b); }
1880 template<typename _Tp> static inline Size_<_Tp> operator + (const Size_<_Tp>& a, const Size_<_Tp>& b)
1881 { return Size_<_Tp>(a.width + b.width, a.height + b.height); }
1882 template<typename _Tp> static inline Size_<_Tp> operator - (const Size_<_Tp>& a, const Size_<_Tp>& b)
1883 { return Size_<_Tp>(a.width - b.width, a.height - b.height); }
1884 template<typename _Tp> inline _Tp Size_<_Tp>::area() const { return width*height; }
1885
1886 template<typename _Tp> static inline Size_<_Tp>& operator += (Size_<_Tp>& a, const Size_<_Tp>& b)
1887 { a.width += b.width; a.height += b.height; return a; }
1888 template<typename _Tp> static inline Size_<_Tp>& operator -= (Size_<_Tp>& a, const Size_<_Tp>& b)
1889 { a.width -= b.width; a.height -= b.height; return a; }
1890
1891 template<typename _Tp> static inline bool operator == (const Size_<_Tp>& a, const Size_<_Tp>& b)
1892 { return a.width == b.width && a.height == b.height; }
1893 template<typename _Tp> static inline bool operator != (const Size_<_Tp>& a, const Size_<_Tp>& b)
1894 { return a.width != b.width || a.height != b.height; }
1895
1896 //////////////////////////////// Rect ////////////////////////////////
1897
1898
1899 template<typename _Tp> inline Rect_<_Tp>::Rect_() : x(0), y(0), width(0), height(0) {}
1900 template<typename _Tp> inline Rect_<_Tp>::Rect_(_Tp _x, _Tp _y, _Tp _width, _Tp _height) : x(_x), y(_y), width(_width), height(_height) {}
1901 template<typename _Tp> inline Rect_<_Tp>::Rect_(const Rect_<_Tp>& r) : x(r.x), y(r.y), width(r.width), height(r.height) {}
1902 template<typename _Tp> inline Rect_<_Tp>::Rect_(const CvRect& r) : x((_Tp)r.x), y((_Tp)r.y), width((_Tp)r.width), height((_Tp)r.height) {}
1903 template<typename _Tp> inline Rect_<_Tp>::Rect_(const Point_<_Tp>& org, const Size_<_Tp>& sz) :
1904     x(org.x), y(org.y), width(sz.width), height(sz.height) {}
1905 template<typename _Tp> inline Rect_<_Tp>::Rect_(const Point_<_Tp>& pt1, const Point_<_Tp>& pt2)
1906 {
1907     x = std::min(pt1.x, pt2.x); y = std::min(pt1.y, pt2.y);
1908     width = std::max(pt1.x, pt2.x) - x; height = std::max(pt1.y, pt2.y) - y;
1909 }
1910 template<typename _Tp> inline Rect_<_Tp>& Rect_<_Tp>::operator = ( const Rect_<_Tp>& r )
1911 { x = r.x; y = r.y; width = r.width; height = r.height; return *this; }
1912
1913 template<typename _Tp> inline Point_<_Tp> Rect_<_Tp>::tl() const { return Point_<_Tp>(x,y); }
1914 template<typename _Tp> inline Point_<_Tp> Rect_<_Tp>::br() const { return Point_<_Tp>(x+width, y+height); }
1915
1916 template<typename _Tp> static inline Rect_<_Tp>& operator += ( Rect_<_Tp>& a, const Point_<_Tp>& b )
1917 { a.x += b.x; a.y += b.y; return a; }
1918 template<typename _Tp> static inline Rect_<_Tp>& operator -= ( Rect_<_Tp>& a, const Point_<_Tp>& b )
1919 { a.x -= b.x; a.y -= b.y; return a; }
1920
1921 template<typename _Tp> static inline Rect_<_Tp>& operator += ( Rect_<_Tp>& a, const Size_<_Tp>& b )
1922 { a.width += b.width; a.height += b.height; return a; }
1923
1924 template<typename _Tp> static inline Rect_<_Tp>& operator -= ( Rect_<_Tp>& a, const Size_<_Tp>& b )
1925 { a.width -= b.width; a.height -= b.height; return a; }
1926
1927 template<typename _Tp> static inline Rect_<_Tp>& operator &= ( Rect_<_Tp>& a, const Rect_<_Tp>& b )
1928 {
1929     _Tp x1 = std::max(a.x, b.x), y1 = std::max(a.y, b.y);
1930     a.width = std::min(a.x + a.width, b.x + b.width) - x1;
1931     a.height = std::min(a.y + a.height, b.y + b.height) - y1;
1932     a.x = x1; a.y = y1;
1933     if( a.width <= 0 || a.height <= 0 )
1934         a = Rect();
1935     return a;
1936 }
1937
1938 template<typename _Tp> static inline Rect_<_Tp>& operator |= ( Rect_<_Tp>& a, const Rect_<_Tp>& b )
1939 {
1940     _Tp x1 = std::min(a.x, b.x), y1 = std::min(a.y, b.y);
1941     a.width = std::max(a.x + a.width, b.x + b.width) - x1;
1942     a.height = std::max(a.y + a.height, b.y + b.height) - y1;
1943     a.x = x1; a.y = y1;
1944     return a;
1945 }
1946
1947 template<typename _Tp> inline Size_<_Tp> Rect_<_Tp>::size() const { return Size_<_Tp>(width, height); }
1948 template<typename _Tp> inline _Tp Rect_<_Tp>::area() const { return width*height; }
1949
1950 template<typename _Tp> template<typename _Tp2> inline Rect_<_Tp>::operator Rect_<_Tp2>() const
1951 { return Rect_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y),
1952                      saturate_cast<_Tp2>(width), saturate_cast<_Tp2>(height)); }
1953 template<typename _Tp> inline Rect_<_Tp>::operator CvRect() const
1954 { return cvRect(saturate_cast<int>(x), saturate_cast<int>(y),
1955                 saturate_cast<int>(width), saturate_cast<int>(height)); }
1956
1957 template<typename _Tp> inline bool Rect_<_Tp>::contains(const Point_<_Tp>& pt) const
1958 { return x <= pt.x && pt.x < x + width && y <= pt.y && pt.y < y + height; }
1959
1960 template<typename _Tp> static inline bool operator == (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
1961 {
1962     return a.x == b.x && a.y == b.y && a.width == b.width && a.height == b.height;
1963 }
1964
1965 template<typename _Tp> static inline bool operator != (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
1966 {
1967     return a.x != b.x || a.y != b.y || a.width != b.width || a.height != b.height;
1968 }
1969
1970 template<typename _Tp> static inline Rect_<_Tp> operator + (const Rect_<_Tp>& a, const Point_<_Tp>& b)
1971 {
1972     return Rect_<_Tp>( a.x + b.x, a.y + b.y, a.width, a.height );
1973 }
1974
1975 template<typename _Tp> static inline Rect_<_Tp> operator - (const Rect_<_Tp>& a, const Point_<_Tp>& b)
1976 {
1977     return Rect_<_Tp>( a.x - b.x, a.y - b.y, a.width, a.height );
1978 }
1979
1980 template<typename _Tp> static inline Rect_<_Tp> operator + (const Rect_<_Tp>& a, const Size_<_Tp>& b)
1981 {
1982     return Rect_<_Tp>( a.x, a.y, a.width + b.width, a.height + b.height );
1983 }
1984
1985 template<typename _Tp> static inline Rect_<_Tp> operator & (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
1986 {
1987     Rect_<_Tp> c = a;
1988     return c &= b;
1989 }
1990
1991 template<typename _Tp> static inline Rect_<_Tp> operator | (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
1992 {
1993     Rect_<_Tp> c = a;
1994     return c |= b;
1995 }
1996
1997 template<typename _Tp> inline bool Point_<_Tp>::inside( const Rect_<_Tp>& r ) const
1998 {
1999     return r.contains(*this);
2000 }
2001
2002 inline RotatedRect::RotatedRect() { angle = 0; }
2003 inline RotatedRect::RotatedRect(const Point2f& _center, const Size2f& _size, float _angle)
2004     : center(_center), size(_size), angle(_angle) {}
2005 inline RotatedRect::RotatedRect(const CvBox2D& box)
2006     : center(box.center), size(box.size), angle(box.angle) {}
2007 inline RotatedRect::operator CvBox2D() const
2008 {
2009     CvBox2D box; box.center = center; box.size = size; box.angle = angle;
2010     return box;
2011 }
2012
2013 //////////////////////////////// Scalar_ ///////////////////////////////
2014
2015 template<typename _Tp> inline Scalar_<_Tp>::Scalar_()
2016 { this->val[0] = this->val[1] = this->val[2] = this->val[3] = 0; }
2017
2018 template<typename _Tp> inline Scalar_<_Tp>::Scalar_(_Tp v0, _Tp v1, _Tp v2, _Tp v3)
2019 { this->val[0] = v0; this->val[1] = v1; this->val[2] = v2; this->val[3] = v3; }
2020
2021 template<typename _Tp> inline Scalar_<_Tp>::Scalar_(const CvScalar& s)
2022 {
2023     this->val[0] = saturate_cast<_Tp>(s.val[0]);
2024     this->val[1] = saturate_cast<_Tp>(s.val[1]);
2025     this->val[2] = saturate_cast<_Tp>(s.val[2]);
2026     this->val[3] = saturate_cast<_Tp>(s.val[3]);
2027 }
2028
2029 template<typename _Tp> inline Scalar_<_Tp>::Scalar_(_Tp v0)
2030 { this->val[0] = v0; this->val[1] = this->val[2] = this->val[3] = 0; }
2031
2032 template<typename _Tp> inline Scalar_<_Tp> Scalar_<_Tp>::all(_Tp v0)
2033 { return Scalar_<_Tp>(v0, v0, v0, v0); }
2034 template<typename _Tp> inline Scalar_<_Tp>::operator CvScalar() const
2035 { return cvScalar(this->val[0], this->val[1], this->val[2], this->val[3]); }
2036
2037 template<typename _Tp> template<typename T2> inline Scalar_<_Tp>::operator Scalar_<T2>() const
2038 {
2039     return Scalar_<T2>(saturate_cast<T2>(this->val[0]),
2040                   saturate_cast<T2>(this->val[1]),
2041                   saturate_cast<T2>(this->val[2]),
2042                   saturate_cast<T2>(this->val[3]));
2043 }
2044
2045 template<typename _Tp> static inline Scalar_<_Tp>& operator += (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2046 {
2047     a.val[0] = saturate_cast<_Tp>(a.val[0] + b.val[0]);
2048     a.val[1] = saturate_cast<_Tp>(a.val[1] + b.val[1]);
2049     a.val[2] = saturate_cast<_Tp>(a.val[2] + b.val[2]);
2050     a.val[3] = saturate_cast<_Tp>(a.val[3] + b.val[3]);
2051     return a;
2052 }
2053
2054 template<typename _Tp> static inline Scalar_<_Tp>& operator -= (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2055 {
2056     a.val[0] = saturate_cast<_Tp>(a.val[0] - b.val[0]);
2057     a.val[1] = saturate_cast<_Tp>(a.val[1] - b.val[1]);
2058     a.val[2] = saturate_cast<_Tp>(a.val[2] - b.val[2]);
2059     a.val[3] = saturate_cast<_Tp>(a.val[3] - b.val[3]);
2060     return a;
2061 }
2062
2063 template<typename _Tp> static inline Scalar_<_Tp>& operator *= ( Scalar_<_Tp>& a, _Tp v )
2064 {
2065     a.val[0] = saturate_cast<_Tp>(a.val[0] * v);
2066     a.val[1] = saturate_cast<_Tp>(a.val[1] * v);
2067     a.val[2] = saturate_cast<_Tp>(a.val[2] * v);
2068     a.val[3] = saturate_cast<_Tp>(a.val[3] * v);
2069     return a;
2070 }
2071
2072 template<typename _Tp> inline Scalar_<_Tp> Scalar_<_Tp>::mul(const Scalar_<_Tp>& t, double scale ) const
2073 {
2074     return Scalar_<_Tp>( saturate_cast<_Tp>(this->val[0]*t.val[0]*scale),
2075                        saturate_cast<_Tp>(this->val[1]*t.val[1]*scale),
2076                        saturate_cast<_Tp>(this->val[2]*t.val[2]*scale),
2077                        saturate_cast<_Tp>(this->val[3]*t.val[3]*scale));
2078 }
2079
2080 template<typename _Tp> static inline bool operator == ( const Scalar_<_Tp>& a, const Scalar_<_Tp>& b )
2081 {
2082     return a.val[0] == b.val[0] && a.val[1] == b.val[1] &&
2083         a.val[2] == b.val[2] && a.val[3] == b.val[3];
2084 }
2085
2086 template<typename _Tp> static inline bool operator != ( const Scalar_<_Tp>& a, const Scalar_<_Tp>& b )
2087 {
2088     return a.val[0] != b.val[0] || a.val[1] != b.val[1] ||
2089         a.val[2] != b.val[2] || a.val[3] != b.val[3];
2090 }
2091
2092 template<typename _Tp> static inline Scalar_<_Tp> operator + (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2093 {
2094     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] + b.val[0]),
2095                       saturate_cast<_Tp>(a.val[1] + b.val[1]),
2096                       saturate_cast<_Tp>(a.val[2] + b.val[2]),
2097                       saturate_cast<_Tp>(a.val[3] + b.val[3]));
2098 }
2099
2100 template<typename _Tp> static inline Scalar_<_Tp> operator - (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2101 {
2102     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] - b.val[0]),
2103                       saturate_cast<_Tp>(a.val[1] - b.val[1]),
2104                       saturate_cast<_Tp>(a.val[2] - b.val[2]),
2105                       saturate_cast<_Tp>(a.val[3] - b.val[3]));
2106 }
2107
2108 template<typename _Tp> static inline Scalar_<_Tp> operator * (const Scalar_<_Tp>& a, _Tp alpha)
2109 {
2110     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] * alpha),
2111                       saturate_cast<_Tp>(a.val[1] * alpha),
2112                       saturate_cast<_Tp>(a.val[2] * alpha),
2113                       saturate_cast<_Tp>(a.val[3] * alpha));
2114 }
2115
2116 template<typename _Tp> static inline Scalar_<_Tp> operator * (_Tp alpha, const Scalar_<_Tp>& a)
2117 {
2118     return a*alpha;
2119 }
2120
2121 template<typename _Tp> static inline Scalar_<_Tp> operator - (const Scalar_<_Tp>& a)
2122 {
2123     return Scalar_<_Tp>(saturate_cast<_Tp>(-a.val[0]), saturate_cast<_Tp>(-a.val[1]),
2124                       saturate_cast<_Tp>(-a.val[2]), saturate_cast<_Tp>(-a.val[3]));
2125 }
2126
2127
2128 template<typename _Tp> static inline Scalar_<_Tp>
2129 operator * (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2130 {
2131     return Scalar_<_Tp>(saturate_cast<_Tp>(a[0]*b[0] - a[1]*b[1] - a[2]*b[2] - a[3]*b[3]),
2132                         saturate_cast<_Tp>(a[0]*b[1] + a[1]*b[0] + a[2]*b[3] - a[3]*b[2]),
2133                         saturate_cast<_Tp>(a[0]*b[2] - a[1]*b[3] + a[2]*b[0] + a[3]*b[1]),
2134                         saturate_cast<_Tp>(a[0]*b[3] + a[1]*b[2] - a[2]*b[1] + a[3]*b[0]));
2135 }
2136
2137 template<typename _Tp> static inline Scalar_<_Tp>&
2138 operator *= (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2139 {
2140     a = a*b;
2141     return a;
2142 }
2143
2144 template<typename _Tp> inline Scalar_<_Tp> Scalar_<_Tp>::conj() const
2145 {
2146     return Scalar_<_Tp>(saturate_cast<_Tp>(this->val[0]),
2147                         saturate_cast<_Tp>(-this->val[1]),
2148                         saturate_cast<_Tp>(-this->val[2]),
2149                         saturate_cast<_Tp>(-this->val[3]));
2150 }
2151
2152 template<typename _Tp> inline bool Scalar_<_Tp>::isReal() const
2153 {
2154     return this->val[1] == 0 && this->val[2] == 0 && this->val[3] == 0;
2155 }
2156
2157 template<typename _Tp> static inline
2158 Scalar_<_Tp> operator / (const Scalar_<_Tp>& a, _Tp alpha)
2159 {
2160     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] / alpha),
2161                         saturate_cast<_Tp>(a.val[1] / alpha),
2162                         saturate_cast<_Tp>(a.val[2] / alpha),
2163                         saturate_cast<_Tp>(a.val[3] / alpha));
2164 }
2165
2166 template<typename _Tp> static inline
2167 Scalar_<float> operator / (const Scalar_<float>& a, float alpha)
2168 {
2169     float s = 1/alpha;
2170     return Scalar_<float>(a.val[0]*s, a.val[1]*s, a.val[2]*s, a.val[3]*s);
2171 }
2172
2173 template<typename _Tp> static inline
2174 Scalar_<double> operator / (const Scalar_<double>& a, double alpha)
2175 {
2176     double s = 1/alpha;
2177     return Scalar_<double>(a.val[0]*s, a.val[1]*s, a.val[2]*s, a.val[3]*s);
2178 }
2179
2180 template<typename _Tp> static inline
2181 Scalar_<_Tp>& operator /= (Scalar_<_Tp>& a, _Tp alpha)
2182 {
2183     a = a/alpha;
2184     return a;
2185 }
2186
2187 template<typename _Tp> static inline
2188 Scalar_<_Tp> operator / (_Tp a, const Scalar_<_Tp>& b)
2189 {
2190     _Tp s = a/(b[0]*b[0] + b[1]*b[1] + b[2]*b[2] + b[3]*b[3]);
2191     return b.conj()*s;
2192 }
2193
2194 template<typename _Tp> static inline
2195 Scalar_<_Tp> operator / (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2196 {
2197     return a*((_Tp)1/b);
2198 }
2199
2200 template<typename _Tp> static inline
2201 Scalar_<_Tp>& operator /= (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
2202 {
2203     a = a/b;
2204     return a;
2205 }
2206
2207 //////////////////////////////// Range /////////////////////////////////
2208
2209 inline Range::Range() : start(0), end(0) {}
2210 inline Range::Range(int _start, int _end) : start(_start), end(_end) {}
2211 inline Range::Range(const CvSlice& slice) : start(slice.start_index), end(slice.end_index)
2212 {
2213     if( start == 0 && end == CV_WHOLE_SEQ_END_INDEX )
2214         *this = Range::all();
2215 }
2216
2217 inline int Range::size() const { return end - start; }
2218 inline bool Range::empty() const { return start == end; }
2219 inline Range Range::all() { return Range(INT_MIN, INT_MAX); }
2220
2221 static inline bool operator == (const Range& r1, const Range& r2)
2222 { return r1.start == r2.start && r1.end == r2.end; }
2223
2224 static inline bool operator != (const Range& r1, const Range& r2)
2225 { return !(r1 == r2); }
2226
2227 static inline bool operator !(const Range& r)
2228 { return r.start == r.end; }
2229
2230 static inline Range operator & (const Range& r1, const Range& r2)
2231 {
2232     Range r(std::max(r1.start, r2.start), std::min(r1.end, r2.end));
2233     r.end = std::max(r.end, r.start);
2234     return r;
2235 }
2236
2237 static inline Range& operator &= (Range& r1, const Range& r2)
2238 {
2239     r1 = r1 & r2;
2240     return r1;
2241 }
2242
2243 static inline Range operator + (const Range& r1, int delta)
2244 {
2245     return Range(r1.start + delta, r1.end + delta);
2246 }
2247
2248 static inline Range operator + (int delta, const Range& r1)
2249 {
2250     return Range(r1.start + delta, r1.end + delta);
2251 }
2252
2253 static inline Range operator - (const Range& r1, int delta)
2254 {
2255     return r1 + (-delta);
2256 }
2257
2258 inline Range::operator CvSlice() const
2259 { return *this != Range::all() ? cvSlice(start, end) : CV_WHOLE_SEQ; }
2260
2261
2262
2263 //////////////////////////////// Vector ////////////////////////////////
2264
2265 // template vector class. It is similar to STL's vector,
2266 // with a few important differences:
2267 //   1) it can be created on top of user-allocated data w/o copying it
2268 //   2) vector b = a means copying the header,
2269 //      not the underlying data (use clone() to make a deep copy)
2270 template <typename _Tp> class Vector
2271 {
2272 public:
2273     typedef _Tp value_type;
2274     typedef _Tp* iterator;
2275     typedef const _Tp* const_iterator;
2276     typedef _Tp& reference;
2277     typedef const _Tp& const_reference;
2278
2279     struct Hdr
2280     {
2281         Hdr() : data(0), datastart(0), refcount(0), size(0), capacity(0) {};
2282         _Tp* data;
2283         _Tp* datastart;
2284         int* refcount;
2285         size_t size;
2286         size_t capacity;
2287     };
2288
2289     Vector() {}
2290     Vector(size_t _size)  { resize(_size); }
2291     Vector(size_t _size, const _Tp& val)
2292     {
2293         resize(_size);
2294         for(size_t i = 0; i < _size; i++)
2295             hdr.data[i] = val;
2296     }
2297     Vector(_Tp* _data, size_t _size, bool _copyData=false)
2298     { set(_data, _size, _copyData); }
2299
2300     template<int n> Vector(const Vec<_Tp, n>& vec)
2301     { set((_Tp*)&vec.val[0], n, true); }
2302
2303     Vector(const std::vector<_Tp>& vec, bool _copyData=false)
2304     { set(!vec.empty() ? (_Tp*)&vec[0] : 0, vec.size(), _copyData); }
2305
2306     Vector(const Vector& d) { *this = d; }
2307
2308     Vector(const Vector& d, const Range& r_)
2309     {
2310         Range r = r_ == Range::all() ? Range(0, d.size()) : r_;
2311         /*if( r == Range::all() )
2312             r = Range(0, d.size());*/
2313         if( r.size() > 0 && r.start >= 0 && r.end <= d.size() )
2314         {
2315             if( d.hdr.refcount )
2316                 CV_XADD(d.hdr.refcount, 1);
2317             hdr.refcount = d.hdr.refcount;
2318             hdr.datastart = d.hdr.datastart;
2319             hdr.data = d.hdr.data + r.start;
2320             hdr.capacity = hdr.size = r.size();
2321         }
2322     }
2323
2324     Vector<_Tp>& operator = (const Vector& d)
2325     {
2326         if( this != &d )
2327         {
2328             if( d.hdr.refcount )
2329                 CV_XADD(d.hdr.refcount, 1);
2330             release();
2331             hdr = d.hdr;
2332         }
2333         return *this;
2334     }
2335
2336     ~Vector()  { release(); }
2337
2338     Vector<_Tp> clone() const
2339     { return hdr.data ? Vector<_Tp>(hdr.data, hdr.size, true) : Vector<_Tp>(); }
2340
2341     void copyTo(Vector<_Tp>& vec) const
2342     {
2343         size_t i, sz = size();
2344         vec.resize(sz);
2345         const _Tp* src = hdr.data;
2346         _Tp* dst = vec.hdr.data;
2347         for( i = 0; i < sz; i++ )
2348             dst[i] = src[i];
2349     }
2350
2351     void copyTo(std::vector<_Tp>& vec) const
2352     {
2353         size_t i, sz = size();
2354         vec.resize(sz);
2355         const _Tp* src = hdr.data;
2356         _Tp* dst = sz ? &vec[0] : 0;
2357         for( i = 0; i < sz; i++ )
2358             dst[i] = src[i];
2359     }
2360
2361     operator CvMat() const
2362     { return cvMat((int)size(), 1, type(), (void*)hdr.data); }
2363
2364     _Tp& operator [] (size_t i) { CV_DbgAssert( i < size() ); return hdr.data[i]; }
2365     const _Tp& operator [] (size_t i) const { CV_DbgAssert( i < size() ); return hdr.data[i]; }
2366     Vector operator() (const Range& r) const { return Vector(*this, r); }
2367     _Tp& back() { CV_DbgAssert(!empty()); return hdr.data[hdr.size-1]; }
2368     const _Tp& back() const { CV_DbgAssert(!empty()); return hdr.data[hdr.size-1]; }
2369     _Tp& front() { CV_DbgAssert(!empty()); return hdr.data[0]; }
2370     const _Tp& front() const { CV_DbgAssert(!empty()); return hdr.data[0]; }
2371
2372     _Tp* begin() { return hdr.data; }
2373     _Tp* end() { return hdr.data + hdr.size; }
2374     const _Tp* begin() const { return hdr.data; }
2375     const _Tp* end() const { return hdr.data + hdr.size; }
2376
2377     void addref() { if( hdr.refcount ) CV_XADD(hdr.refcount, 1); }
2378     void release()
2379     {
2380         if( hdr.refcount && CV_XADD(hdr.refcount, -1) == 1 )
2381         {
2382             delete[] hdr.datastart;
2383             delete hdr.refcount;
2384         }
2385         hdr = Hdr();
2386     }
2387
2388     void set(_Tp* _data, size_t _size, bool _copyData=false)
2389     {
2390         if( !_copyData )
2391         {
2392             release();
2393             hdr.data = hdr.datastart = _data;
2394             hdr.size = hdr.capacity = _size;
2395             hdr.refcount = 0;
2396         }
2397         else
2398         {
2399             reserve(_size);
2400             for( size_t i = 0; i < _size; i++ )
2401                 hdr.data[i] = _data[i];
2402             hdr.size = _size;
2403         }
2404     }
2405
2406     void reserve(size_t newCapacity)
2407     {
2408         _Tp* newData;
2409         int* newRefcount;
2410         size_t i, oldSize = hdr.size;
2411         if( (!hdr.refcount || *hdr.refcount == 1) && hdr.capacity >= newCapacity )
2412             return;
2413         newCapacity = std::max(newCapacity, oldSize);
2414         newData = new _Tp[newCapacity];
2415         newRefcount = new int(1);
2416         for( i = 0; i < oldSize; i++ )
2417             newData[i] = hdr.data[i];
2418         release();
2419         hdr.data = hdr.datastart = newData;
2420         hdr.capacity = newCapacity;
2421         hdr.size = oldSize;
2422         hdr.refcount = newRefcount;
2423     }
2424
2425     void resize(size_t newSize)
2426     {
2427         size_t i;
2428         newSize = std::max(newSize, (size_t)0);
2429         if( (!hdr.refcount || *hdr.refcount == 1) && hdr.size == newSize )
2430             return;
2431         if( newSize > hdr.capacity )
2432             reserve(std::max(newSize, std::max((size_t)4, hdr.capacity*2)));
2433         for( i = hdr.size; i < newSize; i++ )
2434             hdr.data[i] = _Tp();
2435         hdr.size = newSize;
2436     }
2437
2438     Vector<_Tp>& push_back(const _Tp& elem)
2439     {
2440         if( hdr.size == hdr.capacity )
2441             reserve( std::max((size_t)4, hdr.capacity*2) );
2442         hdr.data[hdr.size++] = elem;
2443         return *this;
2444     }
2445
2446     Vector<_Tp>& pop_back()
2447     {
2448         if( hdr.size > 0 )
2449             --hdr.size;
2450         return *this;
2451     }
2452
2453     size_t size() const { return hdr.size; }
2454     size_t capacity() const { return hdr.capacity; }
2455     bool empty() const { return hdr.size == 0; }
2456     void clear() { resize(0); }
2457     int type() const { return DataType<_Tp>::type; }
2458
2459 protected:
2460     Hdr hdr;
2461 };
2462
2463
2464 template<typename _Tp> inline typename DataType<_Tp>::work_type
2465 dot(const Vector<_Tp>& v1, const Vector<_Tp>& v2)
2466 {
2467     typedef typename DataType<_Tp>::work_type _Tw;
2468     size_t i = 0, n = v1.size();
2469     assert(v1.size() == v2.size());
2470
2471     _Tw s = 0;
2472     const _Tp *ptr1 = &v1[0], *ptr2 = &v2[0];
2473     for( ; i < n; i++ )
2474         s += (_Tw)ptr1[i]*ptr2[i];
2475
2476     return s;
2477 }
2478
2479 // Multiply-with-Carry RNG
2480 inline RNG::RNG() { state = 0xffffffff; }
2481 inline RNG::RNG(uint64 _state) { state = _state ? _state : 0xffffffff; }
2482 inline unsigned RNG::next()
2483 {
2484     state = (uint64)(unsigned)state*CV_RNG_COEFF + (unsigned)(state >> 32);
2485     return (unsigned)state;
2486 }
2487
2488 inline RNG::operator uchar() { return (uchar)next(); }
2489 inline RNG::operator schar() { return (schar)next(); }
2490 inline RNG::operator ushort() { return (ushort)next(); }
2491 inline RNG::operator short() { return (short)next(); }
2492 inline RNG::operator unsigned() { return next(); }
2493 inline unsigned RNG::operator ()(unsigned N) {return (unsigned)uniform(0,N);}
2494 inline unsigned RNG::operator ()() {return next();}
2495 inline RNG::operator int() { return (int)next(); }
2496 // * (2^32-1)^-1
2497 inline RNG::operator float() { return next()*2.3283064365386962890625e-10f; }
2498 inline RNG::operator double()
2499 {
2500     unsigned t = next();
2501     return (((uint64)t << 32) | next())*5.4210108624275221700372640043497e-20;
2502 }
2503 inline int RNG::uniform(int a, int b) { return a == b ? a : (int)(next()%(b - a) + a); }
2504 inline float RNG::uniform(float a, float b) { return ((float)*this)*(b - a) + a; }
2505 inline double RNG::uniform(double a, double b) { return ((double)*this)*(b - a) + a; }
2506
2507 inline TermCriteria::TermCriteria() : type(0), maxCount(0), epsilon(0) {}
2508 inline TermCriteria::TermCriteria(int _type, int _maxCount, double _epsilon)
2509     : type(_type), maxCount(_maxCount), epsilon(_epsilon) {}
2510 inline TermCriteria::TermCriteria(const CvTermCriteria& criteria)
2511     : type(criteria.type), maxCount(criteria.max_iter), epsilon(criteria.epsilon) {}
2512 inline TermCriteria::operator CvTermCriteria() const
2513 { return cvTermCriteria(type, maxCount, epsilon); }
2514
2515 inline uchar* LineIterator::operator *() { return ptr; }
2516 inline LineIterator& LineIterator::operator ++()
2517 {
2518     int mask = err < 0 ? -1 : 0;
2519     err += minusDelta + (plusDelta & mask);
2520     ptr += minusStep + (plusStep & mask);
2521     return *this;
2522 }
2523 inline LineIterator LineIterator::operator ++(int)
2524 {
2525     LineIterator it = *this;
2526     ++(*this);
2527     return it;
2528 }
2529 inline Point LineIterator::pos() const
2530 {
2531     Point p;
2532     p.y = (int)((ptr - ptr0)/step);
2533     p.x = (int)(((ptr - ptr0) - p.y*step)/elemSize);
2534     return p;
2535 }
2536
2537 /////////////////////////////// AutoBuffer ////////////////////////////////////////
2538
2539 template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::AutoBuffer()
2540 {
2541     ptr = buf;
2542     size = fixed_size;
2543 }
2544
2545 template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::AutoBuffer(size_t _size)
2546 {
2547     ptr = buf;
2548     size = fixed_size;
2549     allocate(_size);
2550 }
2551
2552 template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::~AutoBuffer()
2553 { deallocate(); }
2554
2555 template<typename _Tp, size_t fixed_size> inline void AutoBuffer<_Tp, fixed_size>::allocate(size_t _size)
2556 {
2557     if(_size <= size)
2558         return;
2559     deallocate();
2560     if(_size > fixed_size)
2561     {
2562         ptr = cv::allocate<_Tp>(_size);
2563         size = _size;
2564     }
2565 }
2566
2567 template<typename _Tp, size_t fixed_size> inline void AutoBuffer<_Tp, fixed_size>::deallocate()
2568 {
2569     if( ptr != buf )
2570     {
2571         cv::deallocate<_Tp>(ptr, size);
2572         ptr = buf;
2573         size = fixed_size;
2574     }
2575 }
2576
2577 template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::operator _Tp* ()
2578 { return ptr; }
2579
2580 template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::operator const _Tp* () const
2581 { return ptr; }
2582
2583
2584 /////////////////////////////////// Ptr ////////////////////////////////////////
2585
2586 template<typename _Tp> inline Ptr<_Tp>::Ptr() : obj(0), refcount(0) {}
2587 template<typename _Tp> inline Ptr<_Tp>::Ptr(_Tp* _obj) : obj(_obj)
2588 {
2589     if(obj)
2590     {
2591         refcount = (int*)fastMalloc(sizeof(*refcount));
2592         *refcount = 1;
2593     }
2594     else
2595         refcount = 0;
2596 }
2597
2598 template<typename _Tp> inline void Ptr<_Tp>::addref()
2599 { if( refcount ) CV_XADD(refcount, 1); }
2600
2601 template<typename _Tp> inline void Ptr<_Tp>::release()
2602 {
2603     if( refcount && CV_XADD(refcount, -1) == 1 )
2604     {
2605         delete_obj();
2606         fastFree(refcount);
2607     }
2608     refcount = 0;
2609     obj = 0;
2610 }
2611
2612 template<typename _Tp> inline void Ptr<_Tp>::delete_obj()
2613 {
2614     if( obj ) delete obj;
2615 }
2616
2617 template<typename _Tp> inline Ptr<_Tp>::~Ptr() { release(); }
2618
2619 template<typename _Tp> inline Ptr<_Tp>::Ptr(const Ptr<_Tp>& _ptr)
2620 {
2621     obj = _ptr.obj;
2622     refcount = _ptr.refcount;
2623     addref();
2624 }
2625
2626 template<typename _Tp> inline Ptr<_Tp>& Ptr<_Tp>::operator = (const Ptr<_Tp>& _ptr)
2627 {
2628     int* _refcount = _ptr.refcount;
2629     if( _refcount )
2630         CV_XADD(_refcount, 1);
2631     release();
2632     obj = _ptr.obj;
2633     refcount = _refcount;
2634     return *this;
2635 }
2636
2637 template<typename _Tp> inline _Tp* Ptr<_Tp>::operator -> () { return obj; }
2638 template<typename _Tp> inline const _Tp* Ptr<_Tp>::operator -> () const { return obj; }
2639
2640 template<typename _Tp> inline Ptr<_Tp>::operator _Tp* () { return obj; }
2641 template<typename _Tp> inline Ptr<_Tp>::operator const _Tp*() const { return obj; }
2642
2643 template<typename _Tp> inline bool Ptr<_Tp>::empty() const { return obj == 0; }
2644
2645 template<typename _Tp> template<typename _Tp2> Ptr<_Tp>::Ptr(const Ptr<_Tp2>& p)
2646     : obj(0), refcount(0)
2647 {
2648     if (p.empty())
2649         return;
2650
2651     _Tp* p_casted = dynamic_cast<_Tp*>(p.obj);
2652     if (!p_casted)
2653         return;
2654
2655     obj = p_casted;
2656     refcount = p.refcount;
2657     addref();
2658 }
2659
2660 template<typename _Tp> template<typename _Tp2> inline Ptr<_Tp2> Ptr<_Tp>::ptr()
2661 {
2662     Ptr<_Tp2> p;
2663     if( !obj )
2664         return p;
2665
2666     _Tp2* obj_casted = dynamic_cast<_Tp2*>(obj);
2667     if (!obj_casted)
2668         return p;
2669
2670     if( refcount )
2671         CV_XADD(refcount, 1);
2672
2673     p.obj = obj_casted;
2674     p.refcount = refcount;
2675     return p;
2676 }
2677
2678 template<typename _Tp> template<typename _Tp2> inline const Ptr<_Tp2> Ptr<_Tp>::ptr() const
2679 {
2680     Ptr<_Tp2> p;
2681     if( !obj )
2682         return p;
2683
2684     _Tp2* obj_casted = dynamic_cast<_Tp2*>(obj);
2685     if (!obj_casted)
2686         return p;
2687
2688     if( refcount )
2689         CV_XADD(refcount, 1);
2690
2691     p.obj = obj_casted;
2692     p.refcount = refcount;
2693     return p;
2694 }
2695
2696 //// specializied implementations of Ptr::delete_obj() for classic OpenCV types
2697
2698 template<> CV_EXPORTS void Ptr<CvMat>::delete_obj();
2699 template<> CV_EXPORTS void Ptr<IplImage>::delete_obj();
2700 template<> CV_EXPORTS void Ptr<CvMatND>::delete_obj();
2701 template<> CV_EXPORTS void Ptr<CvSparseMat>::delete_obj();
2702 template<> CV_EXPORTS void Ptr<CvMemStorage>::delete_obj();
2703 template<> CV_EXPORTS void Ptr<CvFileStorage>::delete_obj();
2704
2705 //////////////////////////////////////// XML & YAML I/O ////////////////////////////////////
2706
2707 CV_EXPORTS_W void write( FileStorage& fs, const string& name, int value );
2708 CV_EXPORTS_W void write( FileStorage& fs, const string& name, float value );
2709 CV_EXPORTS_W void write( FileStorage& fs, const string& name, double value );
2710 CV_EXPORTS_W void write( FileStorage& fs, const string& name, const string& value );
2711
2712 template<typename _Tp> inline void write(FileStorage& fs, const _Tp& value)
2713 { write(fs, string(), value); }
2714
2715 CV_EXPORTS void writeScalar( FileStorage& fs, int value );
2716 CV_EXPORTS void writeScalar( FileStorage& fs, float value );
2717 CV_EXPORTS void writeScalar( FileStorage& fs, double value );
2718 CV_EXPORTS void writeScalar( FileStorage& fs, const string& value );
2719
2720 template<> inline void write( FileStorage& fs, const int& value )
2721 {
2722     writeScalar(fs, value);
2723 }
2724
2725 template<> inline void write( FileStorage& fs, const float& value )
2726 {
2727     writeScalar(fs, value);
2728 }
2729
2730 template<> inline void write( FileStorage& fs, const double& value )
2731 {
2732     writeScalar(fs, value);
2733 }
2734
2735 template<> inline void write( FileStorage& fs, const string& value )
2736 {
2737     writeScalar(fs, value);
2738 }
2739
2740 template<typename _Tp> inline void write(FileStorage& fs, const Point_<_Tp>& pt )
2741 {
2742     write(fs, pt.x);
2743     write(fs, pt.y);
2744 }
2745
2746 template<typename _Tp> inline void write(FileStorage& fs, const Point3_<_Tp>& pt )
2747 {
2748     write(fs, pt.x);
2749     write(fs, pt.y);
2750     write(fs, pt.z);
2751 }
2752
2753 template<typename _Tp> inline void write(FileStorage& fs, const Size_<_Tp>& sz )
2754 {
2755     write(fs, sz.width);
2756     write(fs, sz.height);
2757 }
2758
2759 template<typename _Tp> inline void write(FileStorage& fs, const Complex<_Tp>& c )
2760 {
2761     write(fs, c.re);
2762     write(fs, c.im);
2763 }
2764
2765 template<typename _Tp> inline void write(FileStorage& fs, const Rect_<_Tp>& r )
2766 {
2767     write(fs, r.x);
2768     write(fs, r.y);
2769     write(fs, r.width);
2770     write(fs, r.height);
2771 }
2772
2773 template<typename _Tp, int cn> inline void write(FileStorage& fs, const Vec<_Tp, cn>& v )
2774 {
2775     for(int i = 0; i < cn; i++)
2776         write(fs, v.val[i]);
2777 }
2778
2779 template<typename _Tp> inline void write(FileStorage& fs, const Scalar_<_Tp>& s )
2780 {
2781     write(fs, s.val[0]);
2782     write(fs, s.val[1]);
2783     write(fs, s.val[2]);
2784     write(fs, s.val[3]);
2785 }
2786
2787 inline void write(FileStorage& fs, const Range& r )
2788 {
2789     write(fs, r.start);
2790     write(fs, r.end);
2791 }
2792
2793 class CV_EXPORTS WriteStructContext
2794 {
2795 public:
2796     WriteStructContext(FileStorage& _fs, const string& name,
2797         int flags, const string& typeName=string());
2798     ~WriteStructContext();
2799     FileStorage* fs;
2800 };
2801
2802 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Point_<_Tp>& pt )
2803 {
2804     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2805     write(fs, pt.x);
2806     write(fs, pt.y);
2807 }
2808
2809 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Point3_<_Tp>& pt )
2810 {
2811     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2812     write(fs, pt.x);
2813     write(fs, pt.y);
2814     write(fs, pt.z);
2815 }
2816
2817 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Size_<_Tp>& sz )
2818 {
2819     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2820     write(fs, sz.width);
2821     write(fs, sz.height);
2822 }
2823
2824 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Complex<_Tp>& c )
2825 {
2826     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2827     write(fs, c.re);
2828     write(fs, c.im);
2829 }
2830
2831 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Rect_<_Tp>& r )
2832 {
2833     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2834     write(fs, r.x);
2835     write(fs, r.y);
2836     write(fs, r.width);
2837     write(fs, r.height);
2838 }
2839
2840 template<typename _Tp, int cn> inline void write(FileStorage& fs, const string& name, const Vec<_Tp, cn>& v )
2841 {
2842     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2843     for(int i = 0; i < cn; i++)
2844         write(fs, v.val[i]);
2845 }
2846
2847 template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Scalar_<_Tp>& s )
2848 {
2849     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2850     write(fs, s.val[0]);
2851     write(fs, s.val[1]);
2852     write(fs, s.val[2]);
2853     write(fs, s.val[3]);
2854 }
2855
2856 inline void write(FileStorage& fs, const string& name, const Range& r )
2857 {
2858     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
2859     write(fs, r.start);
2860     write(fs, r.end);
2861 }
2862
2863 template<typename _Tp, int numflag> class VecWriterProxy
2864 {
2865 public:
2866     VecWriterProxy( FileStorage* _fs ) : fs(_fs) {}
2867     void operator()(const vector<_Tp>& vec) const
2868     {
2869         size_t i, count = vec.size();
2870         for( i = 0; i < count; i++ )
2871             write( *fs, vec[i] );
2872     }
2873     FileStorage* fs;
2874 };
2875
2876 template<typename _Tp> class VecWriterProxy<_Tp,1>
2877 {
2878 public:
2879     VecWriterProxy( FileStorage* _fs ) : fs(_fs) {}
2880     void operator()(const vector<_Tp>& vec) const
2881     {
2882         int _fmt = DataType<_Tp>::fmt;
2883         char fmt[] = { (char)((_fmt>>8)+'1'), (char)_fmt, '\0' };
2884         fs->writeRaw( string(fmt), !vec.empty() ? (uchar*)&vec[0] : 0, vec.size()*sizeof(_Tp) );
2885     }
2886     FileStorage* fs;
2887 };
2888
2889 template<typename _Tp> static inline void write( FileStorage& fs, const vector<_Tp>& vec )
2890 {
2891     VecWriterProxy<_Tp, DataType<_Tp>::fmt != 0> w(&fs);
2892     w(vec);
2893 }
2894
2895 template<typename _Tp> static inline void write( FileStorage& fs, const string& name,
2896                                                 const vector<_Tp>& vec )
2897 {
2898     WriteStructContext ws(fs, name, CV_NODE_SEQ+(DataType<_Tp>::fmt != 0 ? CV_NODE_FLOW : 0));
2899     write(fs, vec);
2900 }
2901
2902 CV_EXPORTS_W void write( FileStorage& fs, const string& name, const Mat& value );
2903 CV_EXPORTS void write( FileStorage& fs, const string& name, const SparseMat& value );
2904
2905 template<typename _Tp> static inline FileStorage& operator << (FileStorage& fs, const _Tp& value)
2906 {
2907     if( !fs.isOpened() )
2908         return fs;
2909     if( fs.state == FileStorage::NAME_EXPECTED + FileStorage::INSIDE_MAP )
2910         CV_Error( CV_StsError, "No element name has been given" );
2911     write( fs, fs.elname, value );
2912     if( fs.state & FileStorage::INSIDE_MAP )
2913         fs.state = FileStorage::NAME_EXPECTED + FileStorage::INSIDE_MAP;
2914     return fs;
2915 }
2916
2917 CV_EXPORTS FileStorage& operator << (FileStorage& fs, const string& str);
2918
2919 static inline FileStorage& operator << (FileStorage& fs, const char* str)
2920 { return (fs << string(str)); }
2921
2922 static inline FileStorage& operator << (FileStorage& fs, char* value)
2923 { return (fs << string(value)); }
2924
2925 inline FileNode::FileNode() : fs(0), node(0) {}
2926 inline FileNode::FileNode(const CvFileStorage* _fs, const CvFileNode* _node)
2927     : fs(_fs), node(_node) {}
2928
2929 inline FileNode::FileNode(const FileNode& _node) : fs(_node.fs), node(_node.node) {}
2930
2931 inline int FileNode::type() const { return !node ? NONE : (node->tag & TYPE_MASK); }
2932 inline bool FileNode::empty() const { return node == 0; }
2933 inline bool FileNode::isNone() const { return type() == NONE; }
2934 inline bool FileNode::isSeq() const { return type() == SEQ; }
2935 inline bool FileNode::isMap() const { return type() == MAP; }
2936 inline bool FileNode::isInt() const { return type() == INT; }
2937 inline bool FileNode::isReal() const { return type() == REAL; }
2938 inline bool FileNode::isString() const { return type() == STR; }
2939 inline bool FileNode::isNamed() const { return !node ? false : (node->tag & NAMED) != 0; }
2940 inline size_t FileNode::size() const
2941 {
2942     int t = type();
2943     return t == MAP ? (size_t)((CvSet*)node->data.map)->active_count :
2944         t == SEQ ? (size_t)node->data.seq->total : (size_t)!isNone();
2945 }
2946
2947 inline CvFileNode* FileNode::operator *() { return (CvFileNode*)node; }
2948 inline const CvFileNode* FileNode::operator* () const { return node; }
2949
2950 static inline void read(const FileNode& node, int& value, int default_value)
2951 {
2952     value = !node.node ? default_value :
2953     CV_NODE_IS_INT(node.node->tag) ? node.node->data.i :
2954     CV_NODE_IS_REAL(node.node->tag) ? cvRound(node.node->data.f) : 0x7fffffff;
2955 }
2956
2957 static inline void read(const FileNode& node, bool& value, bool default_value)
2958 {
2959     int temp; read(node, temp, (int)default_value);
2960     value = temp != 0;
2961 }
2962
2963 static inline void read(const FileNode& node, uchar& value, uchar default_value)
2964 {
2965     int temp; read(node, temp, (int)default_value);
2966     value = saturate_cast<uchar>(temp);
2967 }
2968
2969 static inline void read(const FileNode& node, schar& value, schar default_value)
2970 {
2971     int temp; read(node, temp, (int)default_value);
2972     value = saturate_cast<schar>(temp);
2973 }
2974
2975 static inline void read(const FileNode& node, ushort& value, ushort default_value)
2976 {
2977     int temp; read(node, temp, (int)default_value);
2978     value = saturate_cast<ushort>(temp);
2979 }
2980
2981 static inline void read(const FileNode& node, short& value, short default_value)
2982 {
2983     int temp; read(node, temp, (int)default_value);
2984     value = saturate_cast<short>(temp);
2985 }
2986
2987 static inline void read(const FileNode& node, float& value, float default_value)
2988 {
2989     value = !node.node ? default_value :
2990         CV_NODE_IS_INT(node.node->tag) ? (float)node.node->data.i :
2991         CV_NODE_IS_REAL(node.node->tag) ? (float)node.node->data.f : 1e30f;
2992 }
2993
2994 static inline void read(const FileNode& node, double& value, double default_value)
2995 {
2996     value = !node.node ? default_value :
2997         CV_NODE_IS_INT(node.node->tag) ? (double)node.node->data.i :
2998         CV_NODE_IS_REAL(node.node->tag) ? node.node->data.f : 1e300;
2999 }
3000
3001 static inline void read(const FileNode& node, string& value, const string& default_value)
3002 {
3003     value = !node.node ? default_value : CV_NODE_IS_STRING(node.node->tag) ? string(node.node->data.str.ptr) : string("");
3004 }
3005
3006 template<typename _Tp> static inline void read(const FileNode& node, Point_<_Tp>& value, const Point_<_Tp>& default_value)
3007 {
3008     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3009     value = temp.size() != 2 ? default_value : Point_<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]));
3010 }
3011
3012 template<typename _Tp> static inline void read(const FileNode& node, Point3_<_Tp>& value, const Point3_<_Tp>& default_value)
3013 {
3014     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3015     value = temp.size() != 3 ? default_value : Point3_<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]),
3016                                                             saturate_cast<_Tp>(temp[2]));
3017 }
3018
3019 template<typename _Tp> static inline void read(const FileNode& node, Size_<_Tp>& value, const Size_<_Tp>& default_value)
3020 {
3021     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3022     value = temp.size() != 2 ? default_value : Size_<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]));
3023 }
3024
3025 template<typename _Tp> static inline void read(const FileNode& node, Complex<_Tp>& value, const Complex<_Tp>& default_value)
3026 {
3027     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3028     value = temp.size() != 2 ? default_value : Complex<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]));
3029 }
3030
3031 template<typename _Tp> static inline void read(const FileNode& node, Rect_<_Tp>& value, const Rect_<_Tp>& default_value)
3032 {
3033     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3034     value = temp.size() != 4 ? default_value : Rect_<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]),
3035                                                           saturate_cast<_Tp>(temp[2]), saturate_cast<_Tp>(temp[3]));
3036 }
3037
3038 template<typename _Tp, int cn> static inline void read(const FileNode& node, Vec<_Tp, cn>& value, const Vec<_Tp, cn>& default_value)
3039 {
3040     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3041     value = temp.size() != cn ? default_value : Vec<_Tp, cn>(&temp[0]);
3042 }
3043
3044 template<typename _Tp> static inline void read(const FileNode& node, Scalar_<_Tp>& value, const Scalar_<_Tp>& default_value)
3045 {
3046     vector<_Tp> temp; FileNodeIterator it = node.begin(); it >> temp;
3047     value = temp.size() != 4 ? default_value : Scalar_<_Tp>(saturate_cast<_Tp>(temp[0]), saturate_cast<_Tp>(temp[1]),
3048                                                             saturate_cast<_Tp>(temp[2]), saturate_cast<_Tp>(temp[3]));
3049 }
3050
3051 static inline void read(const FileNode& node, Range& value, const Range& default_value)
3052 {
3053     Point2i temp(value.start, value.end); const Point2i default_temp = Point2i(default_value.start, default_value.end);
3054     read(node, temp, default_temp);
3055     value.start = temp.x; value.end = temp.y;
3056 }
3057
3058 CV_EXPORTS_W void read(const FileNode& node, Mat& mat, const Mat& default_mat=Mat() );
3059 CV_EXPORTS void read(const FileNode& node, SparseMat& mat, const SparseMat& default_mat=SparseMat() );
3060
3061 inline FileNode::operator int() const
3062 {
3063     int value;
3064     read(*this, value, 0);
3065     return value;
3066 }
3067 inline FileNode::operator float() const
3068 {
3069     float value;
3070     read(*this, value, 0.f);
3071     return value;
3072 }
3073 inline FileNode::operator double() const
3074 {
3075     double value;
3076     read(*this, value, 0.);
3077     return value;
3078 }
3079 inline FileNode::operator string() const
3080 {
3081     string value;
3082     read(*this, value, value);
3083     return value;
3084 }
3085
3086 inline void FileNode::readRaw( const string& fmt, uchar* vec, size_t len ) const
3087 {
3088     begin().readRaw( fmt, vec, len );
3089 }
3090
3091 template<typename _Tp, int numflag> class VecReaderProxy
3092 {
3093 public:
3094     VecReaderProxy( FileNodeIterator* _it ) : it(_it) {}
3095     void operator()(vector<_Tp>& vec, size_t count) const
3096     {
3097         count = std::min(count, it->remaining);
3098         vec.resize(count);
3099         for( size_t i = 0; i < count; i++, ++(*it) )
3100             read(**it, vec[i], _Tp());
3101     }
3102     FileNodeIterator* it;
3103 };
3104
3105 template<typename _Tp> class VecReaderProxy<_Tp,1>
3106 {
3107 public:
3108     VecReaderProxy( FileNodeIterator* _it ) : it(_it) {}
3109     void operator()(vector<_Tp>& vec, size_t count) const
3110     {
3111         size_t remaining = it->remaining, cn = DataType<_Tp>::channels;
3112         int _fmt = DataType<_Tp>::fmt;
3113         char fmt[] = { (char)((_fmt>>8)+'1'), (char)_fmt, '\0' };
3114         size_t remaining1 = remaining/cn;
3115         count = count < remaining1 ? count : remaining1;
3116         vec.resize(count);
3117         it->readRaw( string(fmt), !vec.empty() ? (uchar*)&vec[0] : 0, count*sizeof(_Tp) );
3118     }
3119     FileNodeIterator* it;
3120 };
3121
3122 template<typename _Tp> static inline void
3123 read( FileNodeIterator& it, vector<_Tp>& vec, size_t maxCount=(size_t)INT_MAX )
3124 {
3125     VecReaderProxy<_Tp, DataType<_Tp>::fmt != 0> r(&it);
3126     r(vec, maxCount);
3127 }
3128
3129 template<typename _Tp> static inline void
3130 read( const FileNode& node, vector<_Tp>& vec, const vector<_Tp>& default_value=vector<_Tp>() )
3131 {
3132     if(!node.node)
3133         vec = default_value;
3134     else
3135     {
3136         FileNodeIterator it = node.begin();
3137         read( it, vec );
3138     }
3139 }
3140
3141 inline FileNodeIterator FileNode::begin() const
3142 {
3143     return FileNodeIterator(fs, node);
3144 }
3145
3146 inline FileNodeIterator FileNode::end() const
3147 {
3148     return FileNodeIterator(fs, node, size());
3149 }
3150
3151 inline FileNode FileNodeIterator::operator *() const
3152 { return FileNode(fs, (const CvFileNode*)(void*)reader.ptr); }
3153
3154 inline FileNode FileNodeIterator::operator ->() const
3155 { return FileNode(fs, (const CvFileNode*)(void*)reader.ptr); }
3156
3157 template<typename _Tp> static inline FileNodeIterator& operator >> (FileNodeIterator& it, _Tp& value)
3158 { read( *it, value, _Tp()); return ++it; }
3159
3160 template<typename _Tp> static inline
3161 FileNodeIterator& operator >> (FileNodeIterator& it, vector<_Tp>& vec)
3162 {
3163     VecReaderProxy<_Tp, DataType<_Tp>::fmt != 0> r(&it);
3164     r(vec, (size_t)INT_MAX);
3165     return it;
3166 }
3167
3168 template<typename _Tp> static inline void operator >> (const FileNode& n, _Tp& value)
3169 { read( n, value, _Tp()); }
3170
3171 template<typename _Tp> static inline void operator >> (const FileNode& n, vector<_Tp>& vec)
3172 { FileNodeIterator it = n.begin(); it >> vec; }
3173
3174 static inline bool operator == (const FileNodeIterator& it1, const FileNodeIterator& it2)
3175 {
3176     return it1.fs == it2.fs && it1.container == it2.container &&
3177         it1.reader.ptr == it2.reader.ptr && it1.remaining == it2.remaining;
3178 }
3179
3180 static inline bool operator != (const FileNodeIterator& it1, const FileNodeIterator& it2)
3181 {
3182     return !(it1 == it2);
3183 }
3184
3185 static inline ptrdiff_t operator - (const FileNodeIterator& it1, const FileNodeIterator& it2)
3186 {
3187     return it2.remaining - it1.remaining;
3188 }
3189
3190 static inline bool operator < (const FileNodeIterator& it1, const FileNodeIterator& it2)
3191 {
3192     return it1.remaining > it2.remaining;
3193 }
3194
3195 inline FileNode FileStorage::getFirstTopLevelNode() const
3196 {
3197     FileNode r = root();
3198     FileNodeIterator it = r.begin();
3199     return it != r.end() ? *it : FileNode();
3200 }
3201
3202 //////////////////////////////////////// Various algorithms ////////////////////////////////////
3203
3204 template<typename _Tp> static inline _Tp gcd(_Tp a, _Tp b)
3205 {
3206     if( a < b )
3207         std::swap(a, b);
3208     while( b > 0 )
3209     {
3210         _Tp r = a % b;
3211         a = b;
3212         b = r;
3213     }
3214     return a;
3215 }
3216
3217 /****************************************************************************************\
3218
3219   Generic implementation of QuickSort algorithm
3220   Use it as: vector<_Tp> a; ... sort(a,<less_than_predictor>);
3221
3222   The current implementation was derived from *BSD system qsort():
3223
3224     * Copyright (c) 1992, 1993
3225     *  The Regents of the University of California.  All rights reserved.
3226     *
3227     * Redistribution and use in source and binary forms, with or without
3228     * modification, are permitted provided that the following conditions
3229     * are met:
3230     * 1. Redistributions of source code must retain the above copyright
3231     *    notice, this list of conditions and the following disclaimer.
3232     * 2. Redistributions in binary form must reproduce the above copyright
3233     *    notice, this list of conditions and the following disclaimer in the
3234     *    documentation and/or other materials provided with the distribution.
3235     * 3. All advertising materials mentioning features or use of this software
3236     *    must display the following acknowledgement:
3237     *  This product includes software developed by the University of
3238     *  California, Berkeley and its contributors.
3239     * 4. Neither the name of the University nor the names of its contributors
3240     *    may be used to endorse or promote products derived from this software
3241     *    without specific prior written permission.
3242     *
3243     * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
3244     * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
3245     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3246     * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
3247     * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3248     * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
3249     * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3250     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3251     * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3252     * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3253     * SUCH DAMAGE.
3254
3255 \****************************************************************************************/
3256
3257 template<typename _Tp, class _LT> void sort( vector<_Tp>& vec, _LT LT=_LT() )
3258 {
3259     int isort_thresh = 7;
3260     int sp = 0;
3261
3262     struct
3263     {
3264         _Tp *lb;
3265         _Tp *ub;