cxoperations.hpp
上传用户:soukeisyuu
上传日期:2022-07-03
资源大小:5943k
文件大小:84k
源码类别:

波变换

开发平台:

Visual C++

  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. #ifndef _OPENCV_CORE_OPERATIONS_H_
  43. #define _OPENCV_CORE_OPERATIONS_H_
  44. #ifndef SKIP_INCLUDES
  45.   #include <string.h>
  46.   #include <limits.h>
  47. #endif // SKIP_INCLUDES
  48. #ifdef __cplusplus
  49. /////// exchange-add operation for atomic operations on reference counters ///////
  50. #ifdef __GNUC__
  51.     
  52.   #if __GNUC__*10 + __GNUC_MINOR__ >= 42
  53.     #if !defined WIN32 && (defined __i486__ || defined __i586__ || 
  54.         defined __i686__ || defined __MMX__ || defined __SSE__  || defined __ppc__)
  55.       #define CV_XADD __sync_fetch_and_add
  56.     #else
  57.       #include <ext/atomicity.h>
  58.       #define CV_XADD __gnu_cxx::__exchange_and_add
  59.     #endif
  60.   #else
  61.     #include <bits/atomicity.h>
  62.     #if __GNUC__ >= 4 || __MINGW32__
  63.       #define CV_XADD __gnu_cxx::__exchange_and_add
  64.     #else
  65.       #define CV_XADD __exchange_and_add
  66.     #endif
  67.   #endif
  68.     
  69. #elif defined WIN32 || defined _WIN32
  70.   #if defined _MSC_VER && !defined WIN64 && !defined _WIN64
  71.     static inline int CV_XADD( int* addr, int delta )
  72.     {
  73.         int tmp;
  74.         __asm
  75.         {
  76.             mov edx, addr
  77.             mov eax, delta
  78.             lock xadd [edx], eax
  79.             mov tmp, eax
  80.         }
  81.         return tmp;
  82.     }
  83.   #else
  84.     #include "windows.h"
  85.     #undef min
  86.     #undef max
  87.     #define CV_XADD(addr,delta) InterlockedExchangeAdd((LONG volatile*)(addr), (delta))
  88.   #endif
  89.       
  90. #else
  91.   template<typename _Tp> static inline _Tp CV_XADD(_Tp* addr, _Tp delta)
  92.   { int tmp = *addr; *addr += delta; return tmp; }
  93.     
  94. #endif
  95. namespace cv
  96. {
  97. using std::cos;
  98. using std::sin;
  99. using std::max;
  100. using std::min;
  101. using std::exp;
  102. using std::log;
  103. using std::pow;
  104. using std::sqrt;
  105.     
  106. /////////////// saturate_cast (used in image & signal processing) ///////////////////
  107. template<typename _Tp> static inline _Tp saturate_cast(uchar v) { return _Tp(v); }
  108. template<typename _Tp> static inline _Tp saturate_cast(schar v) { return _Tp(v); }
  109. template<typename _Tp> static inline _Tp saturate_cast(ushort v) { return _Tp(v); }
  110. template<typename _Tp> static inline _Tp saturate_cast(short v) { return _Tp(v); }
  111. template<typename _Tp> static inline _Tp saturate_cast(unsigned v) { return _Tp(v); }
  112. template<typename _Tp> static inline _Tp saturate_cast(int v) { return _Tp(v); }
  113. template<typename _Tp> static inline _Tp saturate_cast(float v) { return _Tp(v); }
  114. template<typename _Tp> static inline _Tp saturate_cast(double v) { return _Tp(v); }
  115. template<> inline uchar saturate_cast<uchar>(schar v)
  116. { return (uchar)std::max((int)v, 0); }
  117. template<> inline uchar saturate_cast<uchar>(ushort v)
  118. { return (uchar)std::min((unsigned)v, (unsigned)UCHAR_MAX); }
  119. template<> inline uchar saturate_cast<uchar>(int v)
  120. { return (uchar)((unsigned)v <= UCHAR_MAX ? v : v > 0 ? UCHAR_MAX : 0); }
  121. template<> inline uchar saturate_cast<uchar>(short v)
  122. { return saturate_cast<uchar>((int)v); }
  123. template<> inline uchar saturate_cast<uchar>(unsigned v)
  124. { return (uchar)std::min(v, (unsigned)UCHAR_MAX); }
  125. template<> inline uchar saturate_cast<uchar>(float v)
  126. { int iv = cvRound(v); return saturate_cast<uchar>(iv); }
  127. template<> inline uchar saturate_cast<uchar>(double v)
  128. { int iv = cvRound(v); return saturate_cast<uchar>(iv); }
  129. template<> inline schar saturate_cast<schar>(uchar v)
  130. { return (schar)std::min((int)v, SCHAR_MAX); }
  131. template<> inline schar saturate_cast<schar>(ushort v)
  132. { return (schar)std::min((unsigned)v, (unsigned)SCHAR_MAX); }
  133. template<> inline schar saturate_cast<schar>(int v)
  134. {
  135.     return (schar)((unsigned)(v-SCHAR_MIN) <= (unsigned)UCHAR_MAX ?
  136.                 v : v > 0 ? SCHAR_MAX : SCHAR_MIN);
  137. }
  138. template<> inline schar saturate_cast<schar>(short v)
  139. { return saturate_cast<schar>((int)v); }
  140. template<> inline schar saturate_cast<schar>(unsigned v)
  141. { return (schar)std::min(v, (unsigned)SCHAR_MAX); }
  142. template<> inline schar saturate_cast<schar>(float v)
  143. { int iv = cvRound(v); return saturate_cast<schar>(iv); }
  144. template<> inline schar saturate_cast<schar>(double v)
  145. { int iv = cvRound(v); return saturate_cast<schar>(iv); }
  146. template<> inline ushort saturate_cast<ushort>(schar v)
  147. { return (ushort)std::max((int)v, 0); }
  148. template<> inline ushort saturate_cast<ushort>(short v)
  149. { return (ushort)std::max((int)v, 0); }
  150. template<> inline ushort saturate_cast<ushort>(int v)
  151. { return (ushort)((unsigned)v <= (unsigned)USHRT_MAX ? v : v > 0 ? USHRT_MAX : 0); }
  152. template<> inline ushort saturate_cast<ushort>(unsigned v)
  153. { return (ushort)std::min(v, (unsigned)USHRT_MAX); }
  154. template<> inline ushort saturate_cast<ushort>(float v)
  155. { int iv = cvRound(v); return saturate_cast<ushort>(iv); }
  156. template<> inline ushort saturate_cast<ushort>(double v)
  157. { int iv = cvRound(v); return saturate_cast<ushort>(iv); }
  158. template<> inline short saturate_cast<short>(ushort v)
  159. { return (short)std::min((int)v, SHRT_MAX); }
  160. template<> inline short saturate_cast<short>(int v)
  161. {
  162.     return (short)((unsigned)(v - SHRT_MIN) <= (unsigned)USHRT_MAX ?
  163.             v : v > 0 ? SHRT_MAX : SHRT_MIN);
  164. }
  165. template<> inline short saturate_cast<short>(unsigned v)
  166. { return (short)std::min(v, (unsigned)SHRT_MAX); }
  167. template<> inline short saturate_cast<short>(float v)
  168. { int iv = cvRound(v); return saturate_cast<short>(iv); }
  169. template<> inline short saturate_cast<short>(double v)
  170. { int iv = cvRound(v); return saturate_cast<short>(iv); }
  171. template<> inline int saturate_cast<int>(float v) { return cvRound(v); }
  172. template<> inline int saturate_cast<int>(double v) { return cvRound(v); }
  173. // we intentionally do not clip negative numbers, to make -1 become 0xffffffff etc.
  174. template<> inline unsigned saturate_cast<unsigned>(float v){ return cvRound(v); }
  175. template<> inline unsigned saturate_cast<unsigned>(double v) { return cvRound(v); }
  176. /////////////////////////// short vector (Vec) /////////////////////////////
  177. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec() {}
  178. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0)
  179. {
  180.     val[0] = v0;
  181.     for(int i = 1; i < cn; i++) val[i] = _Tp();
  182. }
  183. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1)
  184. {
  185.     assert(cn >= 2);
  186.     val[0] = v0; val[1] = v1;
  187.     for(int i = 2; i < cn; i++) val[i] = _Tp(0);
  188. }
  189. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2)
  190. {
  191.     assert(cn >= 3);
  192.     val[0] = v0; val[1] = v1; val[2] = v2;
  193.     for(int i = 3; i < cn; i++) val[i] = _Tp(0);
  194. }
  195. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3)
  196. {
  197.     assert(cn >= 4);
  198.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  199.     for(int i = 4; i < cn; i++) val[i] = _Tp(0);
  200. }
  201. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3, _Tp v4)
  202. {
  203.     assert(cn >= 5);
  204.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3; val[4] = v4;
  205.     for(int i = 5; i < cn; i++) val[i] = _Tp(0);
  206. }
  207. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
  208.                                                         _Tp v4, _Tp v5)
  209. {
  210.     assert(cn >= 6);
  211.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  212.     val[4] = v4; val[5] = v5;
  213.     for(int i = 6; i < cn; i++) val[i] = _Tp(0);
  214. }
  215. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
  216.                                                         _Tp v4, _Tp v5, _Tp v6)
  217. {
  218.     assert(cn >= 7);
  219.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  220.     val[4] = v4; val[5] = v5; val[6] = v6;
  221.     for(int i = 7; i < cn; i++) val[i] = _Tp(0);
  222. }
  223. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
  224.                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7)
  225. {
  226.     assert(cn >= 8);
  227.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  228.     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
  229.     for(int i = 8; i < cn; i++) val[i] = _Tp(0);
  230. }
  231. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
  232.                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
  233.                                                         _Tp v8)
  234. {
  235.     assert(cn >= 9);
  236.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  237.     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
  238.     val[8] = v8;
  239.     for(int i = 9; i < cn; i++) val[i] = _Tp(0);
  240. }
  241. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(_Tp v0, _Tp v1, _Tp v2, _Tp v3,
  242.                                                         _Tp v4, _Tp v5, _Tp v6, _Tp v7,
  243.                                                         _Tp v8, _Tp v9)
  244. {
  245.     assert(cn >= 10);
  246.     val[0] = v0; val[1] = v1; val[2] = v2; val[3] = v3;
  247.     val[4] = v4; val[5] = v5; val[6] = v6; val[7] = v7;
  248.     val[8] = v8; val[9] = v9;
  249.     for(int i = 10; i < cn; i++) val[i] = _Tp(0);
  250. }
  251. template<typename _Tp, int cn> inline Vec<_Tp, cn>::Vec(const Vec<_Tp, cn>& v)
  252. {
  253.     for( int i = 0; i < cn; i++ ) val[i] = v.val[i];
  254. }
  255. template<typename _Tp, int cn> inline Vec<_Tp, cn> Vec<_Tp, cn>::all(_Tp alpha)
  256. {
  257.     Vec v;
  258.     for( int i = 0; i < cn; i++ ) v.val[i] = alpha;
  259.     return v;
  260. }
  261. template<typename _Tp, int cn> inline _Tp Vec<_Tp, cn>::dot(const Vec<_Tp, cn>& v) const
  262. {
  263.     _Tp s = 0;
  264.     for( int i = 0; i < cn; i++ ) s += val[i]*v.val[i];
  265.     return s;
  266. }
  267. template<typename _Tp, int cn> inline double Vec<_Tp, cn>::ddot(const Vec<_Tp, cn>& v) const
  268. {
  269.     double s = 0;
  270.     for( int i = 0; i < cn; i++ ) s += (double)val[i]*v.val[i];
  271.     return s;
  272. }
  273. template<typename _Tp, int cn> inline Vec<_Tp, cn> Vec<_Tp, cn>::cross(const Vec<_Tp, cn>& v) const
  274. {
  275.     return Vec<_Tp, cn>(); // for arbitrary-size vector there is no cross-product defined
  276. }
  277. template<typename _Tp, int cn> template<typename T2>
  278. inline Vec<_Tp, cn>::operator Vec<T2, cn>() const
  279. {
  280.     Vec<T2, cn> v;
  281.     for( int i = 0; i < cn; i++ ) v.val[i] = saturate_cast<T2>(val[i]);
  282.     return v;
  283. }
  284. template<typename _Tp, int cn> inline Vec<_Tp, cn>::operator CvScalar() const
  285. {
  286.     CvScalar s = {{0,0,0,0}};
  287.     int i;
  288.     for( i = 0; i < std::min(cn, 4); i++ ) s.val[i] = val[i];
  289.     for( ; i < 4; i++ ) s.val[i] = 0;
  290.     return s;
  291. }
  292. template<typename _Tp, int cn> inline _Tp Vec<_Tp, cn>::operator [](int i) const { return val[i]; }
  293. template<typename _Tp, int cn> inline _Tp& Vec<_Tp, cn>::operator[](int i) { return val[i]; }
  294. template<typename _Tp1, typename _Tp2, int cn> static inline Vec<_Tp1, cn>&
  295. operator += (Vec<_Tp1, cn>& a, const Vec<_Tp2, cn>& b)
  296. {
  297.     for( int i = 0; i < cn; i++ )
  298.         a.val[i] = saturate_cast<_Tp1>(a.val[i] + b.val[i]);
  299.     return a;
  300. }    
  301. template<typename _Tp1, typename _Tp2, int cn> static inline Vec<_Tp1, cn>&
  302. operator -= (Vec<_Tp1, cn>& a, const Vec<_Tp2, cn>& b)
  303. {
  304.     for( int i = 0; i < cn; i++ )
  305.         a.val[i] = saturate_cast<_Tp1>(a.val[i] - b.val[i]);
  306.     return a;
  307. }        
  308.     
  309. template<typename _Tp, int cn> static inline Vec<_Tp, cn>
  310. operator + (const Vec<_Tp, cn>& a, const Vec<_Tp, cn>& b)
  311. {
  312.     Vec<_Tp, cn> c = a;
  313.     return c += b;
  314. }
  315. template<typename _Tp, int cn> static inline Vec<_Tp, cn>
  316. operator - (const Vec<_Tp, cn>& a, const Vec<_Tp, cn>& b)
  317. {
  318.     Vec<_Tp, cn> c = a;
  319.     return c -= b;
  320. }
  321. template<typename _Tp> static inline
  322. Vec<_Tp, 2>& operator *= (Vec<_Tp, 2>& a, _Tp alpha)
  323. {
  324.     a[0] *= alpha; a[1] *= alpha;
  325.     return a;
  326. }
  327. template<typename _Tp> static inline
  328. Vec<_Tp, 3>& operator *= (Vec<_Tp, 3>& a, _Tp alpha)
  329. {
  330.     a[0] *= alpha; a[1] *= alpha; a[2] *= alpha;
  331.     return a;
  332. }
  333. template<typename _Tp> static inline
  334. Vec<_Tp, 4>& operator *= (Vec<_Tp, 4>& a, _Tp alpha)
  335. {
  336.     a[0] *= alpha; a[1] *= alpha; a[2] *= alpha; a[3] *= alpha;
  337.     return a;
  338. }
  339. template<typename _Tp, int cn> static inline Vec<_Tp, cn>
  340. operator * (const Vec<_Tp, cn>& a, _Tp alpha)
  341. {
  342.     Vec<_Tp, cn> c = a;
  343.     return c *= alpha;
  344. }
  345. template<typename _Tp, int cn> static inline Vec<_Tp, cn>
  346. operator * (_Tp alpha, const Vec<_Tp, cn>& a)
  347. {
  348.     return a * alpha;
  349. }
  350. template<typename _Tp, int cn> static inline Vec<_Tp, cn>
  351. operator - (const Vec<_Tp, cn>& a)
  352. {
  353.     Vec<_Tp,cn> t;
  354.     for( int i = 0; i < cn; i++ ) t.val[i] = saturate_cast<_Tp>(-a.val[i]);
  355.     return t;
  356. }
  357. template<> inline Vec<float, 3> Vec<float, 3>::cross(const Vec<float, 3>& v) const
  358. {
  359.     return Vec<float,3>(val[1]*v.val[2] - val[2]*v.val[1],
  360.                      val[2]*v.val[0] - val[0]*v.val[2],
  361.                      val[0]*v.val[1] - val[1]*v.val[0]);
  362. }
  363. template<> inline Vec<double, 3> Vec<double, 3>::cross(const Vec<double, 3>& v) const
  364. {
  365.     return Vec<double,3>(val[1]*v.val[2] - val[2]*v.val[1],
  366.                      val[2]*v.val[0] - val[0]*v.val[2],
  367.                      val[0]*v.val[1] - val[1]*v.val[0]);
  368. }
  369. template<typename T1, typename T2> static inline
  370. Vec<T1, 2>& operator += (Vec<T1, 2>& a, const Vec<T2, 2>& b)
  371. {
  372.     a[0] = saturate_cast<T1>(a[0] + b[0]);
  373.     a[1] = saturate_cast<T1>(a[1] + b[1]);
  374.     return a;
  375. }
  376. template<typename T1, typename T2> static inline
  377. Vec<T1, 3>& operator += (Vec<T1, 3>& a, const Vec<T2, 3>& b)
  378. {
  379.     a[0] = saturate_cast<T1>(a[0] + b[0]);
  380.     a[1] = saturate_cast<T1>(a[1] + b[1]);
  381.     a[2] = saturate_cast<T1>(a[2] + b[2]);
  382.     return a;
  383. }
  384. template<typename T1, typename T2> static inline
  385. Vec<T1, 4>& operator += (Vec<T1, 4>& a, const Vec<T2, 4>& b)
  386. {
  387.     a[0] = saturate_cast<T1>(a[0] + b[0]);
  388.     a[1] = saturate_cast<T1>(a[1] + b[1]);
  389.     a[2] = saturate_cast<T1>(a[2] + b[2]);
  390.     a[3] = saturate_cast<T1>(a[3] + b[3]);
  391.     return a;
  392. }
  393. template<typename T1, int n> static inline
  394. double norm(const Vec<T1, n>& a)
  395. {
  396.     double s = 0;
  397.     for( int i = 0; i < n; i++ )
  398.         s += (double)a.val[i]*a.val[i];
  399.     return std::sqrt(s);
  400. }
  401.     
  402. template<typename T1, int n> static inline
  403. bool operator == (const Vec<T1, n>& a, const Vec<T1, n>& b)
  404. {
  405.     for( int i = 0; i < n; i++ )
  406.         if( a[i] != b[i] ) return false;
  407.     return true;
  408. }
  409.     
  410. template<typename T1, int n> static inline
  411. bool operator != (const Vec<T1, n>& a, const Vec<T1, n>& b)
  412. {
  413.     return !(a == b);
  414. }
  415. //////////////////////////////// Complex //////////////////////////////
  416. template<typename _Tp> inline Complex<_Tp>::Complex() : re(0), im(0) {}
  417. template<typename _Tp> inline Complex<_Tp>::Complex( _Tp _re, _Tp _im ) : re(_re), im(_im) {}
  418. template<typename _Tp> template<typename T2> inline Complex<_Tp>::operator Complex<T2>() const
  419. { return Complex<T2>(saturate_cast<T2>(re), saturate_cast<T2>(im)); }
  420. template<typename _Tp> inline Complex<_Tp> Complex<_Tp>::conj() const
  421. { return Complex<_Tp>(re, -im); }
  422. template<typename _Tp> static inline
  423. bool operator == (const Complex<_Tp>& a, const Complex<_Tp>& b)
  424. { return a.re == b.re && a.im == b.im; }
  425. template<typename _Tp> static inline
  426. Complex<_Tp> operator + (const Complex<_Tp>& a, const Complex<_Tp>& b)
  427. { return Complex<_Tp>( a.re + b.re, a.im + b.im ); }
  428. template<typename _Tp> static inline
  429. Complex<_Tp>& operator += (Complex<_Tp>& a, const Complex<_Tp>& b)
  430. { a.re += b.re; a.im += b.im; return a; }
  431. template<typename _Tp> static inline
  432. Complex<_Tp> operator - (const Complex<_Tp>& a, const Complex<_Tp>& b)
  433. { return Complex<_Tp>( a.re - b.re, a.im - b.im ); }
  434. template<typename _Tp> static inline
  435. Complex<_Tp>& operator -= (Complex<_Tp>& a, const Complex<_Tp>& b)
  436. { a.re -= b.re; a.im -= b.im; return a; }
  437. template<typename _Tp> static inline
  438. Complex<_Tp> operator - (const Complex<_Tp>& a)
  439. { return Complex<_Tp>(-a.re, -a.im); }
  440. template<typename _Tp> static inline
  441. Complex<_Tp> operator * (const Complex<_Tp>& a, const Complex<_Tp>& b)
  442. { return Complex<_Tp>( a.re*b.re - a.im*b.im, a.re*b.im + a.im*b.re ); }
  443. template<typename _Tp> static inline
  444. Complex<_Tp> operator * (const Complex<_Tp>& a, _Tp b)
  445. { return Complex<_Tp>( a.re*b, a.im*b ); }
  446. template<typename _Tp> static inline
  447. Complex<_Tp> operator * (_Tp b, const Complex<_Tp>& a)
  448. { return Complex<_Tp>( a.re*b, a.im*b ); }
  449. template<typename _Tp> static inline
  450. Complex<_Tp> operator + (const Complex<_Tp>& a, _Tp b)
  451. { return Complex<_Tp>( a.re + b, a.im ); }
  452. template<typename _Tp> static inline
  453. Complex<_Tp> operator - (const Complex<_Tp>& a, _Tp b)
  454. { return Complex<_Tp>( a.re - b, a.im ); }
  455. template<typename _Tp> static inline
  456. Complex<_Tp> operator + (_Tp b, const Complex<_Tp>& a)
  457. { return Complex<_Tp>( a.re + b, a.im ); }
  458. template<typename _Tp> static inline
  459. Complex<_Tp> operator - (_Tp b, const Complex<_Tp>& a)
  460. { return Complex<_Tp>( b - a.re, -a.im ); }
  461. template<typename _Tp> static inline
  462. Complex<_Tp>& operator += (Complex<_Tp>& a, _Tp b)
  463. { a.re += b; return a; }
  464. template<typename _Tp> static inline
  465. Complex<_Tp>& operator -= (Complex<_Tp>& a, _Tp b)
  466. { a.re -= b; return a; }
  467. template<typename _Tp> static inline
  468. Complex<_Tp>& operator *= (Complex<_Tp>& a, _Tp b)
  469. { a.re *= b; a.im *= b; return a; }
  470. template<typename _Tp> static inline
  471. double abs(const Complex<_Tp>& a)
  472. { return std::sqrt( (double)a.re*a.re + (double)a.im*a.im); }
  473. template<typename _Tp> static inline
  474. Complex<_Tp> operator / (const Complex<_Tp>& a, const Complex<_Tp>& b)
  475. {
  476.     double t = 1./((double)b.re*b.re + (double)b.im*b.im);
  477.     return Complex<_Tp>( (_Tp)((a.re*b.re + a.im*b.im)*t),
  478.                         (_Tp)((-a.re*b.im + a.im*b.re)*t) );
  479. }
  480. template<typename _Tp> static inline
  481. Complex<_Tp>& operator /= (Complex<_Tp>& a, const Complex<_Tp>& b)
  482. {
  483.     return (a = a / b);
  484. }
  485. template<typename _Tp> static inline
  486. Complex<_Tp> operator / (const Complex<_Tp>& a, _Tp b)
  487. {
  488.     _Tp t = (_Tp)1/b;
  489.     return Complex<_Tp>( a.re*t, a.im*t );
  490. }
  491. template<typename _Tp> static inline
  492. Complex<_Tp> operator / (_Tp b, const Complex<_Tp>& a)
  493. {
  494.     return Complex<_Tp>(b)/a;
  495. }
  496. template<typename _Tp> static inline
  497. Complex<_Tp> operator /= (const Complex<_Tp>& a, _Tp b)
  498. {
  499.     _Tp t = (_Tp)1/b;
  500.     a.re *= t; a.im *= t; return a;
  501. }
  502. //////////////////////////////// 2D Point ////////////////////////////////
  503. template<typename _Tp> inline Point_<_Tp>::Point_() : x(0), y(0) {}
  504. template<typename _Tp> inline Point_<_Tp>::Point_(_Tp _x, _Tp _y) : x(_x), y(_y) {}
  505. template<typename _Tp> inline Point_<_Tp>::Point_(const Point_& pt) : x(pt.x), y(pt.y) {}
  506. template<typename _Tp> inline Point_<_Tp>::Point_(const CvPoint& pt) : x((_Tp)pt.x), y((_Tp)pt.y) {}
  507. template<typename _Tp> inline Point_<_Tp>::Point_(const CvPoint2D32f& pt)
  508.     : x(saturate_cast<_Tp>(pt.x)), y(saturate_cast<_Tp>(pt.y)) {}
  509. template<typename _Tp> inline Point_<_Tp>::Point_(const Size_<_Tp>& sz) : x(sz.width), y(sz.height) {}
  510. template<typename _Tp> inline Point_<_Tp>::Point_(const Vec<_Tp,2>& v) : x(v[0]), y(v[1]) {}
  511. template<typename _Tp> inline Point_<_Tp>& Point_<_Tp>::operator = (const Point_& pt)
  512. { x = pt.x; y = pt.y; return *this; }
  513. template<typename _Tp> template<typename _Tp2> inline Point_<_Tp>::operator Point_<_Tp2>() const
  514. { return Point_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y)); }
  515. template<typename _Tp> inline Point_<_Tp>::operator CvPoint() const
  516. { return cvPoint(saturate_cast<int>(x), saturate_cast<int>(y)); }
  517. template<typename _Tp> inline Point_<_Tp>::operator CvPoint2D32f() const
  518. { return cvPoint2D32f((float)x, (float)y); }
  519. template<typename _Tp> inline Point_<_Tp>::operator Vec<_Tp, 2>() const
  520. { return Vec<_Tp, 2>(x, y); }
  521. template<typename _Tp> inline _Tp Point_<_Tp>::dot(const Point_& pt) const
  522. { return x*pt.x + y*pt.y; }
  523. template<typename _Tp> inline double Point_<_Tp>::ddot(const Point_& pt) const
  524. { return (double)x*pt.x + (double)y*pt.y; }
  525. template<typename _Tp> static inline Point_<_Tp>&
  526. operator += (Point_<_Tp>& a, const Point_<_Tp>& b) { a.x += b.x; a.y += b.y; return a; }
  527. template<typename _Tp> static inline Point_<_Tp>&
  528. operator -= (Point_<_Tp>& a, const Point_<_Tp>& b) { a.x -= b.x; a.y -= b.y; return a; }
  529. template<typename _Tp> static inline Point_<_Tp>&
  530. operator *= (Point_<_Tp>& a, _Tp b) { a.x *= b; a.y *= b; return a; }
  531. template<typename _Tp> static inline double norm(const Point_<_Tp>& pt)
  532. { return std::sqrt((double)pt.x*pt.x + (double)pt.y*pt.y); }
  533. template<typename _Tp> static inline bool operator == (const Point_<_Tp>& a, const Point_<_Tp>& b)
  534. { return a.x == b.x && a.y == b.y; }
  535. template<typename _Tp> static inline bool operator != (const Point_<_Tp>& a, const Point_<_Tp>& b)
  536. { return !(a == b); }
  537. template<typename _Tp> static inline Point_<_Tp> operator + (const Point_<_Tp>& a, const Point_<_Tp>& b)
  538. { return Point_<_Tp>( a.x + b.x, a.y + b.y ); }
  539. template<typename _Tp> static inline Point_<_Tp> operator - (const Point_<_Tp>& a, const Point_<_Tp>& b)
  540. { return Point_<_Tp>( a.x - b.x, a.y - b.y ); }
  541. template<typename _Tp> static inline Point_<_Tp> operator - (const Point_<_Tp>& a)
  542. { return Point_<_Tp>( -a.x, -a.y ); }
  543. template<typename _Tp> static inline Point_<_Tp> operator * (const Point_<_Tp>& a, _Tp b)
  544. { return Point_<_Tp>( a.x*b, a.y*b ); }
  545. template<typename _Tp> static inline Point_<_Tp> operator * (_Tp a, const Point_<_Tp>& b)
  546. { return Point_<_Tp>( a*b.x, a*b.y ); }
  547. //////////////////////////////// 3D Point ////////////////////////////////
  548. template<typename _Tp> inline Point3_<_Tp>::Point3_() : x(0), y(0), z(0) {}
  549. template<typename _Tp> inline Point3_<_Tp>::Point3_(_Tp _x, _Tp _y, _Tp _z) : x(_x), y(_y), z(_z) {}
  550. template<typename _Tp> inline Point3_<_Tp>::Point3_(const Point3_& pt) : x(pt.x), y(pt.y), z(pt.z) {}
  551. template<typename _Tp> inline Point3_<_Tp>::Point3_(const Point_<_Tp>& pt) : x(pt.x), y(pt.y), z(_Tp()) {}
  552. template<typename _Tp> inline Point3_<_Tp>::Point3_(const CvPoint3D32f& pt) :
  553.     x(saturate_cast<_Tp>(pt.x)), y(saturate_cast<_Tp>(pt.y)), z(saturate_cast<_Tp>(pt.z)) {}
  554. template<typename _Tp> inline Point3_<_Tp>::Point3_(const Vec<_Tp, 3>& v) : x(v[0]), y(v[1]), z(v[2]) {}
  555. template<typename _Tp> template<typename _Tp2> inline Point3_<_Tp>::operator Point3_<_Tp2>() const
  556. { return Point3_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y), saturate_cast<_Tp2>(z)); }
  557. template<typename _Tp> inline Point3_<_Tp>::operator CvPoint3D32f() const
  558. { return cvPoint3D32f((float)x, (float)y, (float)z); }
  559. template<typename _Tp> inline Point3_<_Tp>::operator Vec<_Tp, 3>() const
  560. { return Vec<_Tp, 3>(x, y, z); }
  561. template<typename _Tp> inline Point3_<_Tp>& Point3_<_Tp>::operator = (const Point3_& pt)
  562. { x = pt.x; y = pt.y; z = pt.z; return *this; }
  563. template<typename _Tp> inline _Tp Point3_<_Tp>::dot(const Point3_& pt) const
  564. { return x*pt.x + y*pt.y + z*pt.z; }
  565. template<typename _Tp> inline double Point3_<_Tp>::ddot(const Point3_& pt) const
  566. { return (double)x*pt.x + (double)y*pt.y + (double)z*pt.z; }
  567. template<typename _Tp> static inline Point3_<_Tp>&
  568. operator += (Point3_<_Tp>& a, const Point3_<_Tp>& b) { a.x += b.x; a.y += b.y; a.z += b.z; return a; }
  569. template<typename _Tp> static inline Point3_<_Tp>&
  570. operator -= (Point3_<_Tp>& a, const Point3_<_Tp>& b) { a.x -= b.x; a.y -= b.y; a.z -= b.z; return a; }
  571. template<typename _Tp> static inline double norm(const Point3_<_Tp>& pt)
  572. { return std::sqrt((double)pt.x*pt.x + (double)pt.y*pt.y + (double)pt.z*pt.z); }
  573. template<typename _Tp> static inline bool operator == (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
  574. { return a.x == b.x && a.y == b.y && a.z == b.z; }
  575. template<typename _Tp> static inline Point3_<_Tp> operator + (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
  576. { return Point3_<_Tp>( a.x + b.x, a.y + b.y, a.z + b.z ); }
  577. template<typename _Tp> static inline Point3_<_Tp> operator - (const Point3_<_Tp>& a, const Point3_<_Tp>& b)
  578. { return Point3_<_Tp>( a.x - b.x, a.y - b.y, a.z - b.z ); }
  579. template<typename _Tp> static inline Point3_<_Tp> operator - (const Point3_<_Tp>& a)
  580. { return Point3_<_Tp>( -a.x, -a.y, -a.z ); }
  581. template<typename _Tp> static inline Point3_<_Tp> operator * (const Point3_<_Tp>& a, _Tp b)
  582. { return Point3_<_Tp>( a.x*b, a.y*b, a.z*b ); }
  583. template<typename _Tp> static inline Point3_<_Tp> operator * (_Tp a, const Point3_<_Tp>& b)
  584. { return Point3_<_Tp>( a*b.x, a*b.y, a*b.z ); }
  585. //////////////////////////////// Size ////////////////////////////////
  586. template<typename _Tp> inline Size_<_Tp>::Size_()
  587.     : width(0), height(0) {}
  588. template<typename _Tp> inline Size_<_Tp>::Size_(_Tp _width, _Tp _height)
  589.     : width(_width), height(_height) {}
  590. template<typename _Tp> inline Size_<_Tp>::Size_(const Size_& sz)
  591.     : width(sz.width), height(sz.height) {}
  592. template<typename _Tp> inline Size_<_Tp>::Size_(const CvSize& sz)
  593.     : width(saturate_cast<_Tp>(sz.width)), height(saturate_cast<_Tp>(sz.height)) {}
  594. template<typename _Tp> inline Size_<_Tp>::Size_(const CvSize2D32f& sz)
  595.     : width(saturate_cast<_Tp>(sz.width)), height(saturate_cast<_Tp>(sz.height)) {}
  596. template<typename _Tp> inline Size_<_Tp>::Size_(const Point_<_Tp>& pt) : width(pt.x), height(pt.y) {}
  597. template<typename _Tp> template<typename _Tp2> inline Size_<_Tp>::operator Size_<_Tp2>() const
  598. { return Size_<_Tp2>(saturate_cast<_Tp2>(width), saturate_cast<_Tp2>(height)); }
  599. template<typename _Tp> inline Size_<_Tp>::operator CvSize() const
  600. { return cvSize(saturate_cast<int>(width), saturate_cast<int>(height)); }
  601. template<typename _Tp> inline Size_<_Tp>::operator CvSize2D32f() const
  602. { return cvSize2D32f((float)width, (float)height); }
  603. template<typename _Tp> inline Size_<_Tp>& Size_<_Tp>::operator = (const Size_<_Tp>& sz)
  604. { width = sz.width; height = sz.height; return *this; }
  605. template<typename _Tp> static inline Size_<_Tp> operator * (const Size_<_Tp>& a, _Tp b)
  606. { return Size_<_Tp>(a.width * b, a.height * b); }
  607. template<typename _Tp> static inline Size_<_Tp> operator + (const Size_<_Tp>& a, const Size_<_Tp>& b)
  608. { return Size_<_Tp>(a.width + b.width, a.height + b.height); }
  609. template<typename _Tp> static inline Size_<_Tp> operator - (const Size_<_Tp>& a, const Size_<_Tp>& b)
  610. { return Size_<_Tp>(a.width - b.width, a.height - b.height); }
  611. template<typename _Tp> inline _Tp Size_<_Tp>::area() const { return width*height; }
  612. template<typename _Tp> static inline Size_<_Tp>& operator += (Size_<_Tp>& a, const Size_<_Tp>& b)
  613. { a.width += b.width; a.height += b.height; return a; }
  614. template<typename _Tp> static inline Size_<_Tp>& operator -= (Size_<_Tp>& a, const Size_<_Tp>& b)
  615. { a.width -= b.width; a.height -= b.height; return a; }
  616. template<typename _Tp> static inline bool operator == (const Size_<_Tp>& a, const Size_<_Tp>& b)
  617. { return a.width == b.width && a.height == b.height; }
  618. template<typename _Tp> static inline bool operator != (const Size_<_Tp>& a, const Size_<_Tp>& b)
  619. { return a.width != b.width || a.height != b.height; }
  620. //////////////////////////////// Rect ////////////////////////////////
  621. template<typename _Tp> inline Rect_<_Tp>::Rect_() : x(0), y(0), width(0), height(0) {}
  622. template<typename _Tp> inline Rect_<_Tp>::Rect_(_Tp _x, _Tp _y, _Tp _width, _Tp _height) : x(_x), y(_y), width(_width), height(_height) {}
  623. template<typename _Tp> inline Rect_<_Tp>::Rect_(const Rect_<_Tp>& r) : x(r.x), y(r.y), width(r.width), height(r.height) {}
  624. 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) {}
  625. template<typename _Tp> inline Rect_<_Tp>::Rect_(const Point_<_Tp>& org, const Size_<_Tp>& sz) :
  626.     x(org.x), y(org.y), width(sz.width), height(sz.height) {}
  627. template<typename _Tp> inline Rect_<_Tp>::Rect_(const Point_<_Tp>& pt1, const Point_<_Tp>& pt2)
  628. {
  629.     x = std::min(pt1.x, pt2.x); y = std::min(pt1.y, pt2.y);
  630.     width = std::max(pt1.x, pt2.x) - x; height = std::max(pt1.y, pt2.y) - y;
  631. }
  632. template<typename _Tp> inline Rect_<_Tp>& Rect_<_Tp>::operator = ( const Rect_<_Tp>& r )
  633. { x = r.x; y = r.y; width = r.width; height = r.height; return *this; }
  634. template<typename _Tp> inline Point_<_Tp> Rect_<_Tp>::tl() const { return Point_<_Tp>(x,y); }
  635. template<typename _Tp> inline Point_<_Tp> Rect_<_Tp>::br() const { return Point_<_Tp>(x+width, y+height); }
  636. template<typename _Tp> static inline Rect_<_Tp>& operator += ( Rect_<_Tp>& a, const Point_<_Tp>& b )
  637. { a.x += b.x; a.y += b.y; return a; }
  638. template<typename _Tp> static inline Rect_<_Tp>& operator -= ( Rect_<_Tp>& a, const Point_<_Tp>& b )
  639. { a.x -= b.x; a.y -= b.y; return a; }
  640. template<typename _Tp> static inline Rect_<_Tp>& operator += ( Rect_<_Tp>& a, const Size_<_Tp>& b )
  641. { a.width += b.width; a.height += b.height; return a; }
  642. template<typename _Tp> static inline Rect_<_Tp>& operator -= ( Rect_<_Tp>& a, const Size_<_Tp>& b )
  643. { a.width -= b.width; a.height -= b.height; return a; }
  644. template<typename _Tp> static inline Rect_<_Tp>& operator &= ( Rect_<_Tp>& a, const Rect_<_Tp>& b )
  645. {
  646.     _Tp x1 = std::max(a.x, b.x), y1 = std::max(a.y, b.y);
  647.     a.width = std::min(a.x + a.width, b.x + b.width) - x1;
  648.     a.height = std::min(a.y + a.height, b.y + b.height) - y1;
  649.     a.x = x1; a.y = y1;
  650.     if( a.width <= 0 || a.height <= 0 )
  651.         a = Rect();
  652.     return a;
  653. }
  654. template<typename _Tp> static inline Rect_<_Tp>& operator |= ( Rect_<_Tp>& a, const Rect_<_Tp>& b )
  655. {
  656.     _Tp x1 = std::min(a.x, b.x), y1 = std::min(a.y, b.y);
  657.     a.width = std::max(a.x + a.width, b.x + b.width) - x1;
  658.     a.height = std::max(a.y + a.height, b.y + b.height) - y1;
  659.     a.x = x1; a.y = y1;
  660.     return a;
  661. }
  662. template<typename _Tp> inline Size_<_Tp> Rect_<_Tp>::size() const { return Size_<_Tp>(width, height); }
  663. template<typename _Tp> inline _Tp Rect_<_Tp>::area() const { return width*height; }
  664. template<typename _Tp> template<typename _Tp2> inline Rect_<_Tp>::operator Rect_<_Tp2>() const
  665. { return Rect_<_Tp2>(saturate_cast<_Tp2>(x), saturate_cast<_Tp2>(y),
  666.                      saturate_cast<_Tp2>(width), saturate_cast<_Tp2>(height)); }
  667. template<typename _Tp> inline Rect_<_Tp>::operator CvRect() const
  668. { return cvRect(saturate_cast<int>(x), saturate_cast<int>(y),
  669.                 saturate_cast<int>(width), saturate_cast<int>(height)); }
  670. template<typename _Tp> inline bool Rect_<_Tp>::contains(const Point_<_Tp>& pt) const
  671. { return x <= pt.x && pt.x < x + width && y <= pt.y && pt.y < y + height; }
  672. template<typename _Tp> static inline bool operator == (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
  673. {
  674.     return a.x == b.x && a.y == b.y && a.width == b.width && a.height == b.height;
  675. }
  676. template<typename _Tp> static inline Rect_<_Tp> operator + (const Rect_<_Tp>& a, const Point_<_Tp>& b)
  677. {
  678.     return Rect_<_Tp>( a.x + b.x, a.y + b.y, a.width, a.height );
  679. }
  680. template<typename _Tp> static inline Rect_<_Tp> operator - (const Rect_<_Tp>& a, const Point_<_Tp>& b)
  681. {
  682.     return Rect_<_Tp>( a.x - b.x, a.y - b.y, a.width, a.height );
  683. }
  684. template<typename _Tp> static inline Rect_<_Tp> operator + (const Rect_<_Tp>& a, const Size_<_Tp>& b)
  685. {
  686.     return Rect_<_Tp>( a.x, a.y, a.width + b.width, a.height + b.height );
  687. }
  688. template<typename _Tp> static inline Rect_<_Tp> operator & (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
  689. {
  690.     Rect_<_Tp> c = a;
  691.     return c &= b;
  692. }
  693. template<typename _Tp> static inline Rect_<_Tp> operator | (const Rect_<_Tp>& a, const Rect_<_Tp>& b)
  694. {
  695.     Rect_<_Tp> c = a;
  696.     return c |= b;
  697. }
  698. template<typename _Tp> inline bool Point_<_Tp>::inside( const Rect_<_Tp>& r ) const
  699. {
  700.     return r.contains(*this);
  701. }
  702. inline RotatedRect::RotatedRect() { angle = 0; }
  703. inline RotatedRect::RotatedRect(const Point2f& _center, const Size2f& _size, float _angle)
  704.     : center(_center), size(_size), angle(_angle) {}
  705. inline RotatedRect::RotatedRect(const CvBox2D& box)
  706.     : center(box.center), size(box.size), angle(box.angle) {}
  707. inline RotatedRect::operator CvBox2D() const
  708. {
  709.     CvBox2D box; box.center = center; box.size = size; box.angle = angle;
  710.     return box;
  711. }
  712. inline void RotatedRect::points(Point2f pt[]) const
  713. {
  714.     double _angle = angle*CV_PI/180.;
  715.     float a = (float)cos(_angle)*0.5f;
  716.     float b = (float)sin(_angle)*0.5f;
  717.     
  718.     pt[0].x = center.x - a*size.height - b*size.width;
  719.     pt[0].y = center.y + b*size.height - a*size.width;
  720.     pt[1].x = center.x + a*size.height - b*size.width;
  721.     pt[1].y = center.y - b*size.height - a*size.width;
  722.     pt[2].x = 2*center.x - pt[0].x;
  723.     pt[2].y = 2*center.y - pt[0].y;
  724.     pt[3].x = 2*center.x - pt[1].x;
  725.     pt[3].y = 2*center.y - pt[1].y;
  726. }
  727. inline Rect RotatedRect::boundingRect() const
  728. {
  729.     Point2f pt[4];
  730.     points(pt);
  731.     Rect r(cvFloor(min(min(min(pt[0].x, pt[1].x), pt[2].x), pt[3].x)),
  732.            cvFloor(min(min(min(pt[0].y, pt[1].y), pt[2].y), pt[3].y)),
  733.            cvCeil(max(max(max(pt[0].x, pt[1].x), pt[2].x), pt[3].x)),
  734.            cvCeil(max(max(max(pt[0].y, pt[1].y), pt[2].y), pt[3].y)));
  735.     r.width -= r.x - 1;
  736.     r.height -= r.y - 1;
  737.     return r;
  738. }    
  739.     
  740. //////////////////////////////// Scalar_ ///////////////////////////////
  741. template<typename _Tp> inline Scalar_<_Tp>::Scalar_()
  742. { this->val[0] = this->val[1] = this->val[2] = this->val[3] = 0; }
  743. template<typename _Tp> inline Scalar_<_Tp>::Scalar_(_Tp v0, _Tp v1, _Tp v2, _Tp v3)
  744. { this->val[0] = v0; this->val[1] = v1; this->val[2] = v2; this->val[3] = v3; }
  745. template<typename _Tp> inline Scalar_<_Tp>::Scalar_(const CvScalar& s)
  746. {
  747.     this->val[0] = saturate_cast<_Tp>(s.val[0]);
  748.     this->val[1] = saturate_cast<_Tp>(s.val[1]);
  749.     this->val[2] = saturate_cast<_Tp>(s.val[2]);
  750.     this->val[3] = saturate_cast<_Tp>(s.val[3]);
  751. }
  752. template<typename _Tp> inline Scalar_<_Tp>::Scalar_(_Tp v0)
  753. { this->val[0] = v0; this->val[1] = this->val[2] = this->val[3] = 0; }
  754. template<typename _Tp> inline Scalar_<_Tp> Scalar_<_Tp>::all(_Tp v0)
  755. { return Scalar_<_Tp>(v0, v0, v0, v0); }
  756. template<typename _Tp> inline Scalar_<_Tp>::operator CvScalar() const
  757. { return cvScalar(this->val[0], this->val[1], this->val[2], this->val[3]); }
  758. template<typename _Tp> template<typename T2> inline Scalar_<_Tp>::operator Scalar_<T2>() const
  759. {
  760.     return Scalar_<T2>(saturate_cast<T2>(this->val[0]),
  761.                   saturate_cast<T2>(this->val[1]),
  762.                   saturate_cast<T2>(this->val[2]),
  763.                   saturate_cast<T2>(this->val[3]));
  764. }
  765. template<typename _Tp> static inline Scalar_<_Tp>& operator += (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
  766. {
  767.     a.val[0] = saturate_cast<_Tp>(a.val[0] + b.val[0]);
  768.     a.val[1] = saturate_cast<_Tp>(a.val[1] + b.val[1]);
  769.     a.val[2] = saturate_cast<_Tp>(a.val[2] + b.val[2]);
  770.     a.val[3] = saturate_cast<_Tp>(a.val[3] + b.val[3]);
  771.     return a;
  772. }
  773. template<typename _Tp> static inline Scalar_<_Tp>& operator -= (Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
  774. {
  775.     a.val[0] = saturate_cast<_Tp>(a.val[0] - b.val[0]);
  776.     a.val[1] = saturate_cast<_Tp>(a.val[1] - b.val[1]);
  777.     a.val[2] = saturate_cast<_Tp>(a.val[2] - b.val[2]);
  778.     a.val[3] = saturate_cast<_Tp>(a.val[3] - b.val[3]);
  779.     return a;
  780. }
  781. template<typename _Tp> static inline Scalar_<_Tp>& operator *= ( Scalar_<_Tp>& a, _Tp v )
  782. {
  783.     a.val[0] = saturate_cast<_Tp>(a.val[0] * v);
  784.     a.val[1] = saturate_cast<_Tp>(a.val[1] * v);
  785.     a.val[2] = saturate_cast<_Tp>(a.val[2] * v);
  786.     a.val[3] = saturate_cast<_Tp>(a.val[3] * v);
  787.     return a;
  788. }
  789. template<typename _Tp> inline Scalar_<_Tp> Scalar_<_Tp>::mul(const Scalar_<_Tp>& t, double scale ) const
  790. {
  791.     return Scalar_<_Tp>( saturate_cast<_Tp>(this->val[0]*t.val[0]*scale),
  792.                        saturate_cast<_Tp>(this->val[1]*t.val[1]*scale),
  793.                        saturate_cast<_Tp>(this->val[2]*t.val[2]*scale),
  794.                        saturate_cast<_Tp>(this->val[3]*t.val[3]*scale));
  795. }
  796. template<typename _Tp> static inline bool operator == ( const Scalar_<_Tp>& a, const Scalar_<_Tp>& b )
  797. {
  798.     return a.val[0] == b.val[0] && a.val[1] == b.val[1] &&
  799.         a.val[2] == b.val[2] && a.val[3] == b.val[3];
  800. }
  801. template<typename _Tp> static inline bool operator != ( const Scalar_<_Tp>& a, const Scalar_<_Tp>& b )
  802. {
  803.     return a.val[0] != b.val[0] || a.val[1] != b.val[1] ||
  804.         a.val[2] != b.val[2] || a.val[3] != b.val[3];
  805. }
  806. template<typename _Tp> template<typename T2> inline void Scalar_<_Tp>::convertTo(T2* buf, int cn, int unroll_to) const
  807. {
  808.     int i;
  809.     CV_Assert(cn <= 4);
  810.     for( i = 0; i < cn; i++ )
  811.         buf[i] = saturate_cast<T2>(this->val[i]);
  812.     for( ; i < unroll_to; i++ )
  813.         buf[i] = buf[i-cn];
  814. }
  815. static inline void scalarToRawData(const Scalar& s, void* buf, int type, int unroll_to=0)
  816. {
  817.     int depth = CV_MAT_DEPTH(type), cn = CV_MAT_CN(type);
  818.     switch(depth)
  819.     {
  820.     case CV_8U:
  821.         s.convertTo((uchar*)buf, cn, unroll_to);
  822.         break;
  823.     case CV_8S:
  824.         s.convertTo((schar*)buf, cn, unroll_to);
  825.         break;
  826.     case CV_16U:
  827.         s.convertTo((ushort*)buf, cn, unroll_to);
  828.         break;
  829.     case CV_16S:
  830.         s.convertTo((short*)buf, cn, unroll_to);
  831.         break;
  832.     case CV_32S:
  833.         s.convertTo((int*)buf, cn, unroll_to);
  834.         break;
  835.     case CV_32F:
  836.         s.convertTo((float*)buf, cn, unroll_to);
  837.         break;
  838.     case CV_64F:
  839.         s.convertTo((double*)buf, cn, unroll_to);
  840.         break;
  841.     default:
  842.         CV_Error(CV_StsUnsupportedFormat,"");
  843.     }
  844. }
  845. template<typename _Tp> static inline Scalar_<_Tp> operator + (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
  846. {
  847.     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] + b.val[0]),
  848.                       saturate_cast<_Tp>(a.val[1] + b.val[1]),
  849.                       saturate_cast<_Tp>(a.val[2] + b.val[2]),
  850.                       saturate_cast<_Tp>(a.val[3] + b.val[3]));
  851. }
  852. template<typename _Tp> static inline Scalar_<_Tp> operator - (const Scalar_<_Tp>& a, const Scalar_<_Tp>& b)
  853. {
  854.     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] - b.val[0]),
  855.                       saturate_cast<_Tp>(a.val[1] - b.val[1]),
  856.                       saturate_cast<_Tp>(a.val[2] - b.val[2]),
  857.                       saturate_cast<_Tp>(a.val[3] - b.val[3]));
  858. }
  859. template<typename _Tp> static inline Scalar_<_Tp> operator * (const Scalar_<_Tp>& a, _Tp alpha)
  860. {
  861.     return Scalar_<_Tp>(saturate_cast<_Tp>(a.val[0] * alpha),
  862.                       saturate_cast<_Tp>(a.val[1] * alpha),
  863.                       saturate_cast<_Tp>(a.val[2] * alpha),
  864.                       saturate_cast<_Tp>(a.val[3] * alpha));
  865. }
  866. template<typename _Tp> static inline Scalar_<_Tp> operator * (_Tp alpha, const Scalar_<_Tp>& a)
  867. {
  868.     return a*alpha;
  869. }
  870. template<typename _Tp> static inline Scalar_<_Tp> operator - (const Scalar_<_Tp>& a)
  871. {
  872.     return Scalar_<_Tp>(saturate_cast<_Tp>(-a.val[0]), saturate_cast<_Tp>(-a.val[1]),
  873.                       saturate_cast<_Tp>(-a.val[2]), saturate_cast<_Tp>(-a.val[3]));
  874. }
  875. //////////////////////////////// Range /////////////////////////////////
  876. inline Range::Range() : start(0), end(0) {}
  877. inline Range::Range(int _start, int _end) : start(_start), end(_end) {}
  878. inline Range::Range(const CvSlice& slice) : start(slice.start_index), end(slice.end_index)
  879. {
  880.     if( start == 0 && end == CV_WHOLE_SEQ_END_INDEX )
  881.         *this = Range::all();
  882. }
  883. inline int Range::size() const { return end - start; }
  884. inline bool Range::empty() const { return start == end; }
  885. inline Range Range::all() { return Range(INT_MIN, INT_MAX); }
  886. static inline bool operator == (const Range& r1, const Range& r2)
  887. { return r1.start == r2.start && r1.end == r2.end; }
  888. static inline bool operator != (const Range& r1, const Range& r2)
  889. { return !(r1 == r2); }
  890. static inline bool operator !(const Range& r)
  891. { return r.start == r.end; }
  892. static inline Range operator & (const Range& r1, const Range& r2)
  893. {
  894.     Range r(std::max(r1.start, r2.start), std::min(r2.start, r2.end));
  895.     r.end = std::max(r.end, r.start);
  896.     return r;
  897. }
  898. static inline Range& operator &= (Range& r1, const Range& r2)
  899. {
  900.     r1 = r1 & r2;
  901.     return r1;
  902. }
  903. static inline Range operator + (const Range& r1, int delta)
  904. {
  905.     return Range(r1.start + delta, r1.end + delta);
  906. }
  907. static inline Range operator + (int delta, const Range& r1)
  908. {
  909.     return Range(r1.start + delta, r1.end + delta);
  910. }
  911. static inline Range operator - (const Range& r1, int delta)
  912. {
  913.     return r1 + (-delta);
  914. }
  915. inline Range::operator CvSlice() const
  916. { return *this != Range::all() ? cvSlice(start, end) : CV_WHOLE_SEQ; }
  917.     
  918.     
  919. //////////////////////////////// Vector ////////////////////////////////
  920. // template vector class. It is similar to STL's vector,
  921. // with a few important differences:
  922. //   1) it can be created on top of user-allocated data w/o copying it
  923. //   2) vector b = a means copying the header,
  924. //      not the underlying data (use clone() to make a deep copy)
  925. template <typename _Tp> class CV_EXPORTS Vector
  926. {
  927. public:
  928.     typedef _Tp value_type;
  929.     typedef _Tp* iterator;
  930.     typedef const _Tp* const_iterator;
  931.     typedef _Tp& reference;
  932.     typedef const _Tp& const_reference;
  933.     
  934.     struct CV_EXPORTS Hdr
  935.     {
  936.         Hdr() : data(0), datastart(0), refcount(0), size(0), capacity(0) {};
  937.         _Tp* data;
  938.         _Tp* datastart;
  939.         int* refcount;
  940.         size_t size;
  941.         size_t capacity;
  942.     };
  943.     
  944.     Vector() {}
  945.     Vector(size_t _size)  { resize(_size); }
  946.     Vector(size_t _size, const _Tp& val)
  947.     {
  948.         resize(_size);
  949.         for(size_t i = 0; i < _size; i++)
  950.             hdr.data[i] = val;
  951.     }
  952.     Vector(_Tp* _data, size_t _size, bool _copyData=false)
  953.     { set(_data, _size, _copyData); }
  954.     
  955.     template<int n> Vector(const Vec<_Tp, n>& vec)
  956.     { set((_Tp*)&vec.val[0], n, true); }    
  957.     
  958.     Vector(const std::vector<_Tp>& vec, bool _copyData=false)
  959.     { set((_Tp*)&vec[0], vec.size(), _copyData); }    
  960.     
  961.     Vector(const Vector& d) { *this = d; }
  962.     
  963.     Vector(const Vector& d, const Range& r)
  964.     {
  965.         if( r == Range::all() )
  966.             r = Range(0, d.size());
  967.         if( r.size() > 0 && r.start >= 0 && r.end <= d.size() )
  968.         {
  969.             if( d.hdr.refcount )
  970.                 CV_XADD(d.hdr.refcount, 1);
  971.             hdr.refcount = d.hdr.refcount;
  972.             hdr.datastart = d.hdr.datastart;
  973.             hdr.data = d.hdr.data + r.start;
  974.             hdr.capacity = hdr.size = r.size();
  975.         }
  976.     }
  977.     
  978.     Vector<_Tp>& operator = (const Vector& d)
  979.     {
  980.         if( this != &d )
  981.         {
  982.             if( d.hdr.refcount )
  983.                 CV_XADD(d.hdr.refcount, 1);
  984.             release();
  985.             hdr = d.hdr;
  986.         }
  987.         return *this;
  988.     }
  989.     
  990.     ~Vector()  { release(); }
  991.     
  992.     Vector<_Tp> clone() const
  993.     { return hdr.data ? Vector<_Tp>(hdr.data, hdr.size, true) : Vector<_Tp>(); }
  994.     
  995.     void copyTo(Vector<_Tp>& vec) const
  996.     {
  997.         size_t i, sz = size();
  998.         vec.resize(sz);
  999.         const _Tp* src = hdr.data;
  1000.         _Tp* dst = vec.hdr.data;
  1001.         for( i = 0; i < sz; i++ )
  1002.             dst[i] = src[i];
  1003.     }
  1004.     
  1005.     void copyTo(std::vector<_Tp>& vec) const
  1006.     {
  1007.         size_t i, sz = size();
  1008.         vec.resize(sz);
  1009.         const _Tp* src = hdr.data;
  1010.         _Tp* dst = sz ? &vec[0] : 0;
  1011.         for( i = 0; i < sz; i++ )
  1012.             dst[i] = src[i];
  1013.     }
  1014.     
  1015.     operator CvMat() const
  1016.     { return cvMat((int)size(), 1, type(), (void*)hdr.data); }
  1017.     
  1018.     _Tp& operator [] (size_t i) { CV_DbgAssert( i < size() ); return hdr.data[i]; }
  1019.     const _Tp& operator [] (size_t i) const { CV_DbgAssert( i < size() ); return hdr.data[i]; }
  1020.     Vector operator() (const Range& r) const { return Vector(*this, r); }
  1021.     _Tp& back() { CV_DbgAssert(!empty()); return hdr.data[hdr.size-1]; }
  1022.     const _Tp& back() const { CV_DbgAssert(!empty()); return hdr.data[hdr.size-1]; }
  1023.     _Tp& front() { CV_DbgAssert(!empty()); return hdr.data[0]; }
  1024.     const _Tp& front() const { CV_DbgAssert(!empty()); return hdr.data[0]; }
  1025.     
  1026.     _Tp* begin() { return hdr.data; }
  1027.     _Tp* end() { return hdr.data + hdr.size; }
  1028.     const _Tp* begin() const { return hdr.data; }
  1029.     const _Tp* end() const { return hdr.data + hdr.size; }
  1030.     
  1031.     void addref() { if( hdr.refcount ) CV_XADD(hdr.refcount, 1); }
  1032.     void release()
  1033.     {
  1034.         if( hdr.refcount && CV_XADD(hdr.refcount, -1) == 1 )
  1035.             deallocate<_Tp>(hdr.datastart, hdr.capacity);
  1036.         hdr = Hdr();
  1037.     }
  1038.     
  1039.     void set(_Tp* _data, size_t _size, bool _copyData=false)
  1040.     {
  1041.         if( !_copyData )
  1042.         {
  1043.             release();
  1044.             hdr.data = hdr.datastart = _data;
  1045.             hdr.size = hdr.capacity = _size;
  1046.             hdr.refcount = 0;
  1047.         }
  1048.         else
  1049.         {
  1050.             reserve(_size);
  1051.             for( size_t i = 0; i < _size; i++ )
  1052.                 hdr.data[i] = _data[i];
  1053.             hdr.size = _size;
  1054.         }
  1055.     }
  1056.     
  1057.     void reserve(size_t newCapacity)
  1058.     {
  1059.         _Tp* newData;
  1060.         int* newRefcount;
  1061.         size_t i, oldSize = hdr.size;
  1062.         if( (!hdr.refcount || *hdr.refcount == 1) && hdr.capacity >= newCapacity )
  1063.             return;
  1064.         newCapacity = std::max(newCapacity, oldSize);
  1065.         size_t datasize = alignSize(newCapacity*sizeof(_Tp), (size_t)sizeof(*newRefcount));
  1066.         newData = (_Tp*)fastMalloc(datasize + sizeof(*newRefcount));
  1067.         for( i = 0; i < oldSize; i++ )
  1068.             ::new(newData + i) _Tp(hdr.data[i]);
  1069.         _Tp dummy = _Tp();
  1070.         for( ; i < newCapacity; i++ )
  1071.             ::new(newData + i) _Tp(dummy);
  1072.         newRefcount = (int*)((uchar*)newData + datasize);
  1073.         *newRefcount = 1;
  1074.         release();
  1075.         hdr.data = hdr.datastart = newData;
  1076.         hdr.capacity = newCapacity;
  1077.         hdr.size = oldSize;
  1078.         hdr.refcount = newRefcount;
  1079.     }
  1080.     
  1081.     void resize(size_t newSize)
  1082.     {
  1083.         size_t i;
  1084.         newSize = std::max(newSize, (size_t)0);
  1085.         if( (!hdr.refcount || *hdr.refcount == 1) && hdr.size == newSize )
  1086.             return;
  1087.         if( newSize > hdr.capacity )
  1088.             reserve(std::max(newSize, std::max((size_t)4, hdr.capacity*2)));
  1089.         for( i = hdr.size; i < newSize; i++ )
  1090.             hdr.data[i] = _Tp();
  1091.         hdr.size = newSize;
  1092.     }
  1093.     
  1094.     Vector<_Tp>& push_back(const _Tp& elem)
  1095.     {
  1096.         if( hdr.size == hdr.capacity )
  1097.             reserve( std::max((size_t)4, hdr.capacity*2) );
  1098.         hdr.data[hdr.size++] = elem;
  1099.         return *this;
  1100.     }
  1101.     
  1102.     Vector<_Tp>& pop_back()
  1103.     {
  1104.         if( hdr.size > 0 )
  1105.             --hdr.size;
  1106.         return *this;
  1107.     }
  1108.     
  1109.     size_t size() const { return hdr.size; }
  1110.     size_t capacity() const { return hdr.capacity; }
  1111.     bool empty() const { return hdr.size == 0; }
  1112.     void clear() { resize(0); }
  1113.     int type() const { return DataType<_Tp>::type; }
  1114.     
  1115. protected:
  1116.     Hdr hdr;
  1117. };    
  1118.     
  1119. template<typename _Tp> inline typename DataType<_Tp>::work_type
  1120. dot(const Vector<_Tp>& v1, const Vector<_Tp>& v2)
  1121. {
  1122.     typedef typename DataType<_Tp>::work_type _Tw;
  1123.     size_t i, n = v1.size();
  1124.     assert(v1.size() == v2.size());
  1125.     _Tw s = 0;
  1126.     const _Tp *ptr1 = &v1[0], *ptr2 = &v2[0];
  1127.     for( i = 0; i <= n - 4; i += 4 )
  1128.         s += (_Tw)ptr1[i]*ptr2[i] + (_Tw)ptr1[i+1]*ptr2[i+1] +
  1129.             (_Tw)ptr1[i+2]*ptr2[i+2] + (_Tw)ptr1[i+3]*ptr2[i+3];
  1130.     for( ; i < n; i++ )
  1131.         s += (_Tw)ptr1[i]*ptr2[i];
  1132.     return s;
  1133. }
  1134.     
  1135. // Multiply-with-Carry RNG
  1136. inline RNG::RNG() { state = 0xffffffff; }
  1137. inline RNG::RNG(uint64 _state) { state = _state ? _state : 0xffffffff; }
  1138. inline unsigned RNG::next()
  1139. {
  1140.     state = (uint64)(unsigned)state*A + (unsigned)(state >> 32);
  1141.     return (unsigned)state;
  1142. }
  1143. inline RNG::operator uchar() { return (uchar)next(); }
  1144. inline RNG::operator schar() { return (schar)next(); }
  1145. inline RNG::operator ushort() { return (ushort)next(); }
  1146. inline RNG::operator short() { return (short)next(); }
  1147. inline RNG::operator unsigned() { return next(); }
  1148. inline RNG::operator int() { return (int)next(); }
  1149. // * (2^32-1)^-1
  1150. inline RNG::operator float() { return next()*2.3283064365386962890625e-10f; }
  1151. inline RNG::operator double()
  1152. {
  1153.     unsigned t = next();
  1154.     return (((uint64)t << 32) | next())*5.4210108624275221700372640043497e-20;
  1155. }
  1156. inline int RNG::uniform(int a, int b) { return a == b ? a : next()%(b - a) + a; }
  1157. inline float RNG::uniform(float a, float b) { return ((float)*this)*(b - a) + a; }
  1158. inline double RNG::uniform(double a, double b) { return ((float)*this)*(b - a) + a; }
  1159. inline TermCriteria::TermCriteria() : type(0), maxCount(0), epsilon(0) {}
  1160. inline TermCriteria::TermCriteria(int _type, int _maxCount, double _epsilon)
  1161.     : type(_type), maxCount(_maxCount), epsilon(_epsilon) {}
  1162. inline TermCriteria::TermCriteria(const CvTermCriteria& criteria)
  1163.     : type(criteria.type), maxCount(criteria.max_iter), epsilon(criteria.epsilon) {}
  1164. inline TermCriteria::operator CvTermCriteria() const
  1165. { return cvTermCriteria(type, maxCount, epsilon); }
  1166. inline uchar* LineIterator::operator *() { return ptr; }
  1167. inline LineIterator& LineIterator::operator ++()
  1168. {
  1169.     int mask = err < 0 ? -1 : 0;
  1170.     err += minusDelta + (plusDelta & mask);
  1171.     ptr += minusStep + (plusStep & mask);
  1172.     return *this;
  1173. }
  1174. inline LineIterator LineIterator::operator ++(int)
  1175. {
  1176.     LineIterator it = *this;
  1177.     ++(*this);
  1178.     return it;
  1179. }
  1180. #if 0
  1181.   template<typename _Tp> inline VectorCommaInitializer_<_Tp>::
  1182.   VectorCommaInitializer_(vector<_Tp>* _vec) : vec(_vec), idx(0) {}
  1183.   template<typename _Tp> template<typename T2> inline VectorCommaInitializer_<_Tp>&
  1184.   VectorCommaInitializer_<_Tp>::operator , (T2 val)
  1185.   {
  1186.       if( (size_t)idx < vec->size() )
  1187.           (*vec)[idx] = _Tp(val);
  1188.       else
  1189.           vec->push_back(_Tp(val));
  1190.       idx++;
  1191.       return *this;
  1192.   }
  1193.   template<typename _Tp> inline VectorCommaInitializer_<_Tp>::operator vector<_Tp>() const
  1194.   { return *vec; }
  1195.   template<typename _Tp> inline vector<_Tp> VectorCommaInitializer_<_Tp>::operator *() const
  1196.   { return *vec; }
  1197.   template<typename _Tp, typename T2> static inline VectorCommaInitializer_<_Tp>
  1198.   operator << (const vector<_Tp>& vec, T2 val)
  1199.   {
  1200.       VectorCommaInitializer_<_Tp> commaInitializer((vector<_Tp>*)&vec);
  1201.       return (commaInitializer, val);
  1202.   }
  1203. #endif
  1204.     
  1205. /////////////////////////////// AutoBuffer ////////////////////////////////////////
  1206. template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::AutoBuffer()
  1207. : ptr(buf), size(fixed_size) {}
  1208. template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::AutoBuffer(size_t _size)
  1209. : ptr(buf), size(fixed_size) { allocate(_size); }
  1210. template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::~AutoBuffer()
  1211. { deallocate(); }
  1212. template<typename _Tp, size_t fixed_size> inline void AutoBuffer<_Tp, fixed_size>::allocate(size_t _size)
  1213. {
  1214.     if(_size <= size)
  1215.         return;
  1216.     deallocate();
  1217.     if(_size > fixed_size)
  1218.     {
  1219.         ptr = cv::allocate<_Tp>(_size);
  1220.         size = _size;
  1221.     }
  1222. }
  1223. template<typename _Tp, size_t fixed_size> inline void AutoBuffer<_Tp, fixed_size>::deallocate()
  1224. {
  1225.     if( ptr != buf )
  1226.     {
  1227.         cv::deallocate<_Tp>(ptr, size);
  1228.         ptr = buf;
  1229.         size = fixed_size;
  1230.     }
  1231. }
  1232. template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::operator _Tp* ()
  1233. { return ptr; }
  1234. template<typename _Tp, size_t fixed_size> inline AutoBuffer<_Tp, fixed_size>::operator const _Tp* () const
  1235. { return ptr; }
  1236. /////////////////////////////////// Ptr ////////////////////////////////////////
  1237. template<typename _Tp> inline Ptr<_Tp>::Ptr() : obj(0), refcount(0) {}
  1238. template<typename _Tp> inline Ptr<_Tp>::Ptr(_Tp* _obj) : obj(_obj)
  1239. {
  1240.     if(obj)
  1241.     {
  1242.         refcount = (int*)fastMalloc(sizeof(*refcount));
  1243.         *refcount = 1;
  1244.     }
  1245.     else
  1246.         refcount = 0;
  1247. }
  1248. template<typename _Tp> inline void Ptr<_Tp>::addref()
  1249. { if( refcount ) CV_XADD(refcount, 1); }
  1250. template<typename _Tp> inline void Ptr<_Tp>::release()
  1251. {
  1252.     if( refcount && CV_XADD(refcount, -1) == 1 )
  1253.     {
  1254.         delete_obj();
  1255.         fastFree(refcount);
  1256.     }
  1257.     refcount = 0;
  1258.     obj = 0;
  1259. }
  1260. template<typename _Tp> inline void Ptr<_Tp>::delete_obj()
  1261. {
  1262.     if( obj ) delete obj;
  1263. }
  1264. template<typename _Tp> inline Ptr<_Tp>::~Ptr() { release(); }
  1265. template<typename _Tp> inline Ptr<_Tp>::Ptr(const Ptr<_Tp>& ptr)
  1266. {
  1267.     obj = ptr.obj;
  1268.     refcount = ptr.refcount;
  1269.     addref();
  1270. }
  1271. template<typename _Tp> inline Ptr<_Tp>& Ptr<_Tp>::operator = (const Ptr<_Tp>& ptr)
  1272. {
  1273.     int* _refcount = ptr.refcount;
  1274.     if( _refcount )
  1275.         CV_XADD(_refcount, 1);
  1276.     release();
  1277.     obj = ptr.obj;
  1278.     refcount = _refcount;
  1279.     return *this;
  1280. }
  1281. template<typename _Tp> inline _Tp* Ptr<_Tp>::operator -> () { return obj; }
  1282. template<typename _Tp> inline const _Tp* Ptr<_Tp>::operator -> () const { return obj; }
  1283. template<typename _Tp> inline Ptr<_Tp>::operator _Tp* () { return obj; }
  1284. template<typename _Tp> inline Ptr<_Tp>::operator const _Tp*() const { return obj; }
  1285. template<typename _Tp> inline bool Ptr<_Tp>::empty() const { return obj == 0; }
  1286. //// specializied implementations of Ptr::delete_obj() for classic OpenCV types
  1287. template<> inline void Ptr<CvMat>::delete_obj()
  1288. { cvReleaseMat(&obj); }   
  1289. template<> inline void Ptr<IplImage>::delete_obj()
  1290. { cvReleaseImage(&obj); }
  1291.     
  1292. template<> inline void Ptr<CvMatND>::delete_obj()
  1293. { cvReleaseMatND(&obj); }
  1294.     
  1295. template<> inline void Ptr<CvSparseMat>::delete_obj()
  1296. { cvReleaseSparseMat(&obj); }
  1297.     
  1298. template<> inline void Ptr<CvMemStorage>::delete_obj()
  1299. { cvReleaseMemStorage(&obj); }
  1300. template<> inline void Ptr<CvFileStorage>::delete_obj()
  1301. { cvReleaseFileStorage(&obj); }
  1302.     
  1303. //////////////////////////////////////// XML & YAML I/O ////////////////////////////////////
  1304. static inline void write( FileStorage& fs, const string& name, int value )
  1305. { cvWriteInt( *fs, name.size() ? name.c_str() : 0, value ); }
  1306. static inline void write( FileStorage& fs, const string& name, float value )
  1307. { cvWriteReal( *fs, name.size() ? name.c_str() : 0, value ); }
  1308. static inline void write( FileStorage& fs, const string& name, double value )
  1309. { cvWriteReal( *fs, name.size() ? name.c_str() : 0, value ); }
  1310. static inline void write( FileStorage& fs, const string& name, const string& value )
  1311. { cvWriteString( *fs, name.size() ? name.c_str() : 0, value.c_str() ); }
  1312. template<typename _Tp> static inline void write(FileStorage& fs, const _Tp& value)
  1313. { write(fs, string(), value); }
  1314. template<> inline void write(FileStorage& fs, const int& value )
  1315. { cvWriteInt( *fs, 0, value ); }
  1316. template<> inline void write(FileStorage& fs, const float& value )
  1317. { cvWriteReal( *fs, 0, value ); }
  1318. template<> inline void write(FileStorage& fs, const double& value )
  1319. { cvWriteReal( *fs, 0, value ); }
  1320. template<> inline void write(FileStorage& fs, const string& value )
  1321. { cvWriteString( *fs, 0, value.c_str() ); }
  1322. template<typename _Tp> inline void write(FileStorage& fs, const Point_<_Tp>& pt )
  1323. {
  1324.     write(fs, pt.x);
  1325.     write(fs, pt.y);
  1326. }
  1327. template<typename _Tp> inline void write(FileStorage& fs, const Point3_<_Tp>& pt )
  1328. {
  1329.     write(fs, pt.x);
  1330.     write(fs, pt.y);
  1331.     write(fs, pt.z);
  1332. }
  1333. template<typename _Tp> inline void write(FileStorage& fs, const Size_<_Tp>& sz )
  1334. {
  1335.     write(fs, sz.width);
  1336.     write(fs, sz.height);
  1337. }
  1338. template<typename _Tp> inline void write(FileStorage& fs, const Complex<_Tp>& c )
  1339. {
  1340.     write(fs, c.re);
  1341.     write(fs, c.im);
  1342. }
  1343. template<typename _Tp> inline void write(FileStorage& fs, const Rect_<_Tp>& r )
  1344. {
  1345.     write(fs, r.x);
  1346.     write(fs, r.y);
  1347.     write(fs, r.width);
  1348.     write(fs, r.height);
  1349. }
  1350. template<typename _Tp, int cn> inline void write(FileStorage& fs, const Vec<_Tp, cn>& v )
  1351. {
  1352.     for(int i = 0; i < cn; i++)
  1353.         write(fs, v.val[i]);
  1354. }
  1355. template<typename _Tp> inline void write(FileStorage& fs, const Scalar_<_Tp>& s )
  1356. {
  1357.     write(fs, s.val[0]);
  1358.     write(fs, s.val[1]);
  1359.     write(fs, s.val[2]);
  1360.     write(fs, s.val[3]);
  1361. }
  1362. inline void write(FileStorage& fs, const Range& r )
  1363. {
  1364.     write(fs, r.start);
  1365.     write(fs, r.end);
  1366. }
  1367. class CV_EXPORTS WriteStructContext
  1368. {
  1369. public:
  1370.     WriteStructContext(FileStorage& _fs, const string& name,
  1371.         int flags, const string& typeName=string()) : fs(&_fs)
  1372.     {
  1373.         cvStartWriteStruct(**fs, !name.empty() ? name.c_str() : 0, flags,
  1374.             !typeName.empty() ? typeName.c_str() : 0);
  1375.     }
  1376.     ~WriteStructContext() { cvEndWriteStruct(**fs); }
  1377.     FileStorage* fs;
  1378. };
  1379. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Point_<_Tp>& pt )
  1380. {
  1381.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1382.     write(fs, pt.x);
  1383.     write(fs, pt.y);
  1384. }
  1385. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Point3_<_Tp>& pt )
  1386. {
  1387.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1388.     write(fs, pt.x);
  1389.     write(fs, pt.y);
  1390.     write(fs, pt.z);
  1391. }
  1392. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Size_<_Tp>& sz )
  1393. {
  1394.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1395.     write(fs, sz.width);
  1396.     write(fs, sz.height);
  1397. }
  1398. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Complex<_Tp>& c )
  1399. {
  1400.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1401.     write(fs, c.re);
  1402.     write(fs, c.im);
  1403. }
  1404. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Rect_<_Tp>& r )
  1405. {
  1406.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1407.     write(fs, r.x);
  1408.     write(fs, r.y);
  1409.     write(fs, r.width);
  1410.     write(fs, r.height);
  1411. }
  1412. template<typename _Tp, int cn> inline void write(FileStorage& fs, const string& name, const Vec<_Tp, cn>& v )
  1413. {
  1414.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1415.     for(int i = 0; i < cn; i++)
  1416.         write(fs, v.val[i]);
  1417. }
  1418. template<typename _Tp> inline void write(FileStorage& fs, const string& name, const Scalar_<_Tp>& s )
  1419. {
  1420.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1421.     write(fs, s.val[0]);
  1422.     write(fs, s.val[1]);
  1423.     write(fs, s.val[2]);
  1424.     write(fs, s.val[3]);
  1425. }
  1426. inline void write(FileStorage& fs, const string& name, const Range& r )
  1427. {
  1428.     WriteStructContext ws(fs, name, CV_NODE_SEQ+CV_NODE_FLOW);
  1429.     write(fs, r.start);
  1430.     write(fs, r.end);
  1431. }
  1432. template<typename _Tp, int numflag> class CV_EXPORTS VecWriterProxy
  1433. {
  1434. public:
  1435.     VecWriterProxy( FileStorage* _fs ) : fs(_fs) {}
  1436.     void operator()(const vector<_Tp>& vec) const
  1437.     {
  1438.         size_t i, count = vec.size();
  1439.         for( i = 0; i < count; i++ )
  1440.             write( *fs, vec[i] );
  1441.     }
  1442.     FileStorage* fs;
  1443. };
  1444. template<typename _Tp> class CV_EXPORTS VecWriterProxy<_Tp,1>
  1445. {
  1446. public:
  1447.     VecWriterProxy( FileStorage* _fs ) : fs(_fs) {}
  1448.     void operator()(const vector<_Tp>& vec) const
  1449.     {
  1450.         int _fmt = DataType<_Tp>::fmt;
  1451.         char fmt[] = { (char)((_fmt>>8)+'1'), (char)_fmt, '' };
  1452.         fs->writeRaw( string(fmt), (uchar*)&vec[0], vec.size()*sizeof(_Tp) );
  1453.     }
  1454.     FileStorage* fs;
  1455. };
  1456. template<typename _Tp> static inline void write( FileStorage& fs, const vector<_Tp>& vec )
  1457. {
  1458.     VecWriterProxy<_Tp, DataType<_Tp>::fmt != 0> w(&fs);
  1459.     w(vec);
  1460. }
  1461. template<typename _Tp> static inline FileStorage&
  1462. operator << ( FileStorage& fs, const vector<_Tp>& vec )
  1463. {
  1464.     VecWriterProxy<_Tp, DataType<_Tp>::fmt != 0> w(&fs);
  1465.     w(vec);
  1466.     return fs;
  1467. }
  1468. CV_EXPORTS void write( FileStorage& fs, const string& name, const Mat& value );
  1469. CV_EXPORTS void write( FileStorage& fs, const string& name, const MatND& value );
  1470. CV_EXPORTS void write( FileStorage& fs, const string& name, const SparseMat& value );
  1471. template<typename _Tp> static inline FileStorage& operator << (FileStorage& fs, const _Tp& value)
  1472. {
  1473.     if( !fs.isOpened() )
  1474.         return fs;
  1475.     if( fs.state == FileStorage::NAME_EXPECTED + FileStorage::INSIDE_MAP )
  1476.         CV_Error( CV_StsError, "No element name has been given" );
  1477.     write( fs, fs.elname, value );
  1478.     if( fs.state & FileStorage::INSIDE_MAP )
  1479.         fs.state = FileStorage::NAME_EXPECTED + FileStorage::INSIDE_MAP;
  1480.     return fs;
  1481. }
  1482. CV_EXPORTS FileStorage& operator << (FileStorage& fs, const string& str);
  1483. static inline FileStorage& operator << (FileStorage& fs, const char* str)
  1484. { return (fs << string(str)); }
  1485. inline FileNode FileStorage::operator[](const string& nodename) const
  1486. {
  1487.     return FileNode(fs, cvGetFileNodeByName(fs, 0, nodename.c_str()));
  1488. }
  1489. inline FileNode FileStorage::operator[](const char* nodename) const
  1490. {
  1491.     return FileNode(fs, cvGetFileNodeByName(fs, 0, nodename));
  1492. }
  1493. inline FileNode::FileNode() : fs(0), node(0) {}
  1494. inline FileNode::FileNode(const CvFileStorage* _fs, const CvFileNode* _node)
  1495.     : fs(_fs), node(_node) {}
  1496. inline FileNode::FileNode(const FileNode& _node) : fs(_node.fs), node(_node.node) {}
  1497. inline FileNode FileNode::operator[](const string& nodename) const
  1498. {
  1499.     return FileNode(fs, cvGetFileNodeByName(fs, node, nodename.c_str()));
  1500. }
  1501. inline FileNode FileNode::operator[](const char* nodename) const
  1502. {
  1503.     return FileNode(fs, cvGetFileNodeByName(fs, node, nodename));
  1504. }
  1505. inline FileNode FileNode::operator[](int i) const
  1506. {
  1507.     return isSeq() ? FileNode(fs, (CvFileNode*)cvGetSeqElem(node->data.seq, i)) :
  1508.         i == 0 ? *this : FileNode();
  1509. }
  1510. inline int FileNode::type() const { return !node ? NONE : (node->tag & TYPE_MASK); }
  1511. inline bool FileNode::empty() const { return node == 0; }
  1512. inline bool FileNode::isNone() const { return type() == NONE; }
  1513. inline bool FileNode::isSeq() const { return type() == SEQ; }
  1514. inline bool FileNode::isMap() const { return type() == MAP; }
  1515. inline bool FileNode::isInt() const { return type() == INT; }
  1516. inline bool FileNode::isReal() const { return type() == REAL; }
  1517. inline bool FileNode::isString() const { return type() == STR; }
  1518. inline bool FileNode::isNamed() const { return !node ? false : (node->tag & NAMED) != 0; }
  1519. inline string FileNode::name() const
  1520. {
  1521.     const char* str;
  1522.     return !node || (str = cvGetFileNodeName(node)) == 0 ? string() : string(str);
  1523. }
  1524. inline size_t FileNode::size() const
  1525. {
  1526.     int t = type();
  1527.     return t == MAP ? ((CvSet*)node->data.map)->active_count :
  1528.         t == SEQ ? node->data.seq->total : node != 0;
  1529. }
  1530. inline CvFileNode* FileNode::operator *() { return (CvFileNode*)node; }
  1531. inline const CvFileNode* FileNode::operator* () const { return node; }
  1532. static inline void read(const FileNode& node, bool& value, bool default_value)
  1533. { value = cvReadInt(node.node, default_value) != 0; }
  1534. static inline void read(const FileNode& node, uchar& value, uchar default_value)
  1535. { value = saturate_cast<uchar>(cvReadInt(node.node, default_value)); }
  1536. static inline void read(const FileNode& node, schar& value, schar default_value)
  1537. { value = saturate_cast<schar>(cvReadInt(node.node, default_value)); }
  1538. static inline void read(const FileNode& node, ushort& value, ushort default_value)
  1539. { value = saturate_cast<ushort>(cvReadInt(node.node, default_value)); }
  1540. static inline void read(const FileNode& node, short& value, short default_value)
  1541. { value = saturate_cast<short>(cvReadInt(node.node, default_value)); }
  1542. static inline void read(const FileNode& node, int& value, int default_value)
  1543. { value = cvReadInt(node.node, default_value); }
  1544. static inline void read(const FileNode& node, float& value, float default_value)
  1545. { value = (float)cvReadReal(node.node, default_value); }
  1546. static inline void read(const FileNode& node, double& value, double default_value)
  1547. { value = cvReadReal(node.node, default_value); }
  1548. static inline void read(const FileNode& node, string& value, const string& default_value)
  1549. { value = string(cvReadString(node.node, default_value.c_str())); }
  1550. CV_EXPORTS void read(const FileNode& node, Mat& mat, const Mat& default_mat=Mat() );
  1551. CV_EXPORTS void read(const FileNode& node, MatND& mat, const MatND& default_mat=MatND() );
  1552. CV_EXPORTS void read(const FileNode& node, SparseMat& mat, const SparseMat& default_mat=SparseMat() );    
  1553.     
  1554. inline FileNode::operator int() const
  1555. {
  1556.     return cvReadInt(node, 0);
  1557. }
  1558. inline FileNode::operator float() const
  1559. {
  1560.     return (float)cvReadReal(node, 0);
  1561. }
  1562. inline FileNode::operator double() const
  1563. {
  1564.     return cvReadReal(node, 0);
  1565. }
  1566. inline FileNode::operator string() const
  1567. {
  1568.     return string(cvReadString(node, ""));
  1569. }
  1570. inline void FileNode::readRaw( const string& fmt, uchar* vec, size_t len ) const
  1571. {
  1572.     begin().readRaw( fmt, vec, len );
  1573. }
  1574. template<typename _Tp, int numflag> class CV_EXPORTS VecReaderProxy
  1575. {
  1576. public:
  1577.     VecReaderProxy( FileNodeIterator* _it ) : it(_it) {}
  1578.     void operator()(vector<_Tp>& vec, size_t count) const
  1579.     {
  1580.         count = std::min(count, it->remaining);
  1581.         vec.resize(count);
  1582.         for( size_t i = 0; i < count; i++, ++(*it) )
  1583.             read(**it, vec[i], _Tp());
  1584.     }
  1585.     FileNodeIterator* it;
  1586. };
  1587.     
  1588. template<typename _Tp> class CV_EXPORTS VecReaderProxy<_Tp,1>
  1589. {
  1590. public:
  1591.     VecReaderProxy( FileNodeIterator* _it ) : it(_it) {}
  1592.     void operator()(vector<_Tp>& vec, size_t count) const
  1593.     {
  1594.         size_t remaining = it->remaining, cn = DataType<_Tp>::channels;
  1595.         int _fmt = DataType<_Tp>::fmt;
  1596.         char fmt[] = { (char)((_fmt>>8)+'1'), (char)_fmt, '' };
  1597.         count = std::min(count, remaining/cn);
  1598.         vec.resize(count);
  1599.         it->readRaw( string(fmt), (uchar*)&vec[0], count*sizeof(_Tp) );
  1600.     }
  1601.     FileNodeIterator* it;
  1602. };
  1603. template<typename _Tp> static inline void
  1604. read( FileNodeIterator& it, vector<_Tp>& vec, size_t maxCount=(size_t)INT_MAX )
  1605. {
  1606.     VecReaderProxy<_Tp, DataType<_Tp>::fmt != 0> r(&it);
  1607.     r(vec, maxCount);
  1608. }
  1609. template<typename _Tp> static inline void
  1610. read( FileNode& node, vector<_Tp>& vec, const vector<_Tp>& default_value=vector<_Tp>() )
  1611. {
  1612.     read( node.begin(), vec );
  1613. }
  1614.     
  1615. inline FileNodeIterator FileNode::begin() const
  1616. {
  1617.     return FileNodeIterator(fs, node);
  1618. }
  1619. inline FileNodeIterator FileNode::end() const
  1620. {
  1621.     return FileNodeIterator(fs, node, size());
  1622. }
  1623. inline FileNode FileNodeIterator::operator *() const
  1624. { return FileNode(fs, (const CvFileNode*)reader.ptr); }
  1625. inline FileNode FileNodeIterator::operator ->() const
  1626. { return FileNode(fs, (const CvFileNode*)reader.ptr); }
  1627. template<typename _Tp> static inline FileNodeIterator& operator >> (FileNodeIterator& it, _Tp& value)
  1628. { read( *it, value, _Tp()); return ++it; }
  1629. template<typename _Tp> static inline
  1630. FileNodeIterator& operator >> (FileNodeIterator& it, vector<_Tp>& vec)
  1631. {
  1632.     VecReaderProxy<_Tp, DataType<_Tp>::fmt != 0> r(&it);
  1633.     r(vec, (size_t)INT_MAX);
  1634.     return it;
  1635. }
  1636. template<typename _Tp> static inline void operator >> (const FileNode& n, _Tp& value)
  1637. { FileNodeIterator it = n.begin(); it >> value; }
  1638. static inline bool operator == (const FileNodeIterator& it1, const FileNodeIterator& it2)
  1639. {
  1640.     return it1.fs == it2.fs && it1.container == it2.container &&
  1641.         it1.reader.ptr == it2.reader.ptr && it1.remaining == it2.remaining;
  1642. }
  1643. static inline bool operator != (const FileNodeIterator& it1, const FileNodeIterator& it2)
  1644. {
  1645.     return !(it1 == it2);
  1646. }
  1647. static inline ptrdiff_t operator - (const FileNodeIterator& it1, const FileNodeIterator& it2)
  1648. {
  1649.     return it2.remaining - it1.remaining;
  1650. }
  1651. static inline bool operator < (const FileNodeIterator& it1, const FileNodeIterator& it2)
  1652. {
  1653.     return it1.remaining > it2.remaining;
  1654. }
  1655. inline FileNode FileStorage::getFirstTopLevelNode() const
  1656. {
  1657.     FileNode r = root();
  1658.     FileNodeIterator it = r.begin();
  1659.     return it != r.end() ? *it : FileNode();
  1660. }
  1661. //////////////////////////////////////// Various algorithms ////////////////////////////////////
  1662. template<typename _Tp> static inline _Tp gcd(_Tp a, _Tp b)
  1663. {
  1664.     if( a < b )
  1665.         std::swap(a, b);
  1666.     while( b > 0 )
  1667.     {
  1668.         _Tp r = a % b;
  1669.         a = b;
  1670.         b = r;
  1671.     }
  1672.     return a;
  1673. }
  1674. /****************************************************************************************
  1675.   Generic implementation of QuickSort algorithm
  1676.   Use it as: vector<_Tp> a; ... sort(a,<less_than_predictor>);
  1677.   The current implementation was derived from *BSD system qsort():
  1678.     * Copyright (c) 1992, 1993
  1679.     *  The Regents of the University of California.  All rights reserved.
  1680.     *
  1681.     * Redistribution and use in source and binary forms, with or without
  1682.     * modification, are permitted provided that the following conditions
  1683.     * are met:
  1684.     * 1. Redistributions of source code must retain the above copyright
  1685.     *    notice, this list of conditions and the following disclaimer.
  1686.     * 2. Redistributions in binary form must reproduce the above copyright
  1687.     *    notice, this list of conditions and the following disclaimer in the
  1688.     *    documentation and/or other materials provided with the distribution.
  1689.     * 3. All advertising materials mentioning features or use of this software
  1690.     *    must display the following acknowledgement:
  1691.     *  This product includes software developed by the University of
  1692.     *  California, Berkeley and its contributors.
  1693.     * 4. Neither the name of the University nor the names of its contributors
  1694.     *    may be used to endorse or promote products derived from this software
  1695.     *    without specific prior written permission.
  1696.     *
  1697.     * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  1698.     * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  1699.     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  1700.     * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  1701.     * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  1702.     * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  1703.     * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  1704.     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  1705.     * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  1706.     * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  1707.     * SUCH DAMAGE.
  1708. ****************************************************************************************/
  1709. template<typename _Tp, class _LT> void sort( vector<_Tp>& vec, _LT LT=_LT() )
  1710. {
  1711.     int isort_thresh = 7;
  1712.     int sp = 0;
  1713.     struct
  1714.     {
  1715.         _Tp *lb;
  1716.         _Tp *ub;
  1717.     }
  1718.     stack[48];
  1719.     size_t total = vec.size();
  1720.     if( total <= 1 )
  1721.         return;
  1722.     _Tp* arr = &vec[0];
  1723.     stack[0].lb = arr;
  1724.     stack[0].ub = arr + (total - 1);
  1725.     while( sp >= 0 )
  1726.     {
  1727.         _Tp* left = stack[sp].lb;
  1728.         _Tp* right = stack[sp--].ub;
  1729.         for(;;)
  1730.         {
  1731.             int i, n = (int)(right - left) + 1, m;
  1732.             _Tp* ptr;
  1733.             _Tp* ptr2;
  1734.             if( n <= isort_thresh )
  1735.             {
  1736.             insert_sort:
  1737.                 for( ptr = left + 1; ptr <= right; ptr++ )
  1738.                 {
  1739.                     for( ptr2 = ptr; ptr2 > left && LT(ptr2[0],ptr2[-1]); ptr2--)
  1740.                         std::swap( ptr2[0], ptr2[-1] );
  1741.                 }
  1742.                 break;
  1743.             }
  1744.             else
  1745.             {
  1746.                 _Tp* left0;
  1747.                 _Tp* left1;
  1748.                 _Tp* right0;
  1749.                 _Tp* right1;
  1750.                 _Tp* pivot;
  1751.                 _Tp* a;
  1752.                 _Tp* b;
  1753.                 _Tp* c;
  1754.                 int swap_cnt = 0;
  1755.                 left0 = left;
  1756.                 right0 = right;
  1757.                 pivot = left + (n/2);
  1758.                 if( n > 40 )
  1759.                 {
  1760.                     int d = n / 8;
  1761.                     a = left, b = left + d, c = left + 2*d;
  1762.                     left = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))
  1763.                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));
  1764.                     a = pivot - d, b = pivot, c = pivot + d;
  1765.                     pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))
  1766.                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));
  1767.                     a = right - 2*d, b = right - d, c = right;
  1768.                     right = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))
  1769.                                       : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));
  1770.                 }
  1771.                 a = left, b = pivot, c = right;
  1772.                 pivot = LT(*a, *b) ? (LT(*b, *c) ? b : (LT(*a, *c) ? c : a))
  1773.                                    : (LT(*c, *b) ? b : (LT(*a, *c) ? a : c));
  1774.                 if( pivot != left0 )
  1775.                 {
  1776.                     std::swap( *pivot, *left0 );
  1777.                     pivot = left0;
  1778.                 }
  1779.                 left = left1 = left0 + 1;
  1780.                 right = right1 = right0;
  1781.                 for(;;)
  1782.                 {
  1783.                     while( left <= right && !LT(*pivot, *left) )
  1784.                     {
  1785.                         if( !LT(*left, *pivot) )
  1786.                         {
  1787.                             if( left > left1 )
  1788.                                 std::swap( *left1, *left );
  1789.                             swap_cnt = 1;
  1790.                             left1++;
  1791.                         }
  1792.                         left++;
  1793.                     }
  1794.                     while( left <= right && !LT(*right, *pivot) )
  1795.                     {
  1796.                         if( !LT(*pivot, *right) )
  1797.                         {
  1798.                             if( right < right1 )
  1799.                                 std::swap( *right1, *right );
  1800.                             swap_cnt = 1;
  1801.                             right1--;
  1802.                         }
  1803.                         right--;
  1804.                     }
  1805.                     if( left > right )
  1806.                         break;
  1807.                     std::swap( *left, *right );
  1808.                     swap_cnt = 1;
  1809.                     left++;
  1810.                     right--;
  1811.                 }
  1812.                 if( swap_cnt == 0 )
  1813.                 {
  1814.                     left = left0, right = right0;
  1815.                     goto insert_sort;
  1816.                 }
  1817.                 n = std::min( (int)(left1 - left0), (int)(left - left1) );
  1818.                 for( i = 0; i < n; i++ )
  1819.                     std::swap( left0[i], left[i-n] );
  1820.                 n = std::min( (int)(right0 - right1), (int)(right1 - right) );
  1821.                 for( i = 0; i < n; i++ )
  1822.                     std::swap( left[i], right0[i-n+1] );
  1823.                 n = (int)(left - left1);
  1824.                 m = (int)(right1 - right);
  1825.                 if( n > 1 )
  1826.                 {
  1827.                     if( m > 1 )
  1828.                     {
  1829.                         if( n > m )
  1830.                         {
  1831.                             stack[++sp].lb = left0;
  1832.                             stack[sp].ub = left0 + n - 1;
  1833.                             left = right0 - m + 1, right = right0;
  1834.                         }
  1835.                         else
  1836.                         {
  1837.                             stack[++sp].lb = right0 - m + 1;
  1838.                             stack[sp].ub = right0;
  1839.                             left = left0, right = left0 + n - 1;
  1840.                         }
  1841.                     }
  1842.                     else
  1843.                         left = left0, right = left0 + n - 1;
  1844.                 }
  1845.                 else if( m > 1 )
  1846.                     left = right0 - m + 1, right = right0;
  1847.                 else
  1848.                     break;
  1849.             }
  1850.         }
  1851.     }
  1852. }
  1853. template<typename _Tp> class CV_EXPORTS LessThan
  1854. {
  1855. public:
  1856.     bool operator()(const _Tp& a, const _Tp& b) const { return a < b; }
  1857. };
  1858. template<typename _Tp> class CV_EXPORTS GreaterEq
  1859. {
  1860. public:
  1861.     bool operator()(const _Tp& a, const _Tp& b) const { return a >= b; }
  1862. };
  1863. template<typename _Tp> class CV_EXPORTS LessThanIdx
  1864. {
  1865. public:
  1866.     LessThanIdx( const _Tp* _arr ) : arr(_arr) {}
  1867.     bool operator()(int a, int b) const { return arr[a] < arr[b]; }
  1868.     const _Tp* arr;
  1869. };
  1870. template<typename _Tp> class CV_EXPORTS GreaterEqIdx
  1871. {
  1872. public:
  1873.     GreaterEqIdx( const _Tp* _arr ) : arr(_arr) {}
  1874.     bool operator()(int a, int b) const { return arr[a] >= arr[b]; }
  1875.     const _Tp* arr;
  1876. };
  1877. // This function splits the input sequence or set into one or more equivalence classes and
  1878. // returns the vector of labels - 0-based class indexes for each element.
  1879. // predicate(a,b) returns true if the two sequence elements certainly belong to the same class.
  1880. //
  1881. // The algorithm is described in "Introduction to Algorithms"
  1882. // by Cormen, Leiserson and Rivest, the chapter "Data structures for disjoint sets"
  1883. template<typename _Tp, class _EqPredicate> int
  1884. partition( const vector<_Tp>& _vec, vector<int>& labels,
  1885.            _EqPredicate predicate=_EqPredicate())
  1886. {
  1887.     int i, j, N = (int)_vec.size();
  1888.     const _Tp* vec = &_vec[0];
  1889.     const int PARENT=0;
  1890.     const int RANK=1;
  1891.     vector<int> _nodes(N*2);
  1892.     int (*nodes)[2] = (int(*)[2])&_nodes[0];
  1893.     // The first O(N) pass: create N single-vertex trees
  1894.     for(i = 0; i < N; i++)
  1895.     {
  1896.         nodes[i][PARENT]=-1;
  1897.         nodes[i][RANK] = 0;
  1898.     }
  1899.     // The main O(N^2) pass: merge connected components
  1900.     for( i = 0; i < N; i++ )
  1901.     {
  1902.         int root = i;
  1903.         // find root
  1904.         while( nodes[root][PARENT] >= 0 )
  1905.             root = nodes[root][PARENT];
  1906.         for( j = 0; j < N; j++ )
  1907.         {
  1908.             if( i == j || !predicate(vec[i], vec[j]))
  1909.                 continue;
  1910.             int root2 = j;
  1911.             while( nodes[root2][PARENT] >= 0 )
  1912.                 root2 = nodes[root2][PARENT];
  1913.             if( root2 != root )
  1914.             {
  1915.                 // unite both trees
  1916.                 int rank = nodes[root][RANK], rank2 = nodes[root2][RANK];
  1917.                 if( rank > rank2 )
  1918.                     nodes[root2][PARENT] = root;
  1919.                 else
  1920.                 {
  1921.                     nodes[root][PARENT] = root2;
  1922.                     nodes[root2][RANK] += rank == rank2;
  1923.                     root = root2;
  1924.                 }
  1925.                 assert( nodes[root][PARENT] < 0 );
  1926.                 int k = j, parent;
  1927.                 // compress the path from node2 to root
  1928.                 while( (parent = nodes[k][PARENT]) >= 0 )
  1929.                 {
  1930.                     nodes[k][PARENT] = root;
  1931.                     k = parent;
  1932.                 }
  1933.                 // compress the path from node to root
  1934.                 k = i;
  1935.                 while( (parent = nodes[k][PARENT]) >= 0 )
  1936.                 {
  1937.                     nodes[k][PARENT] = root;
  1938.                     k = parent;
  1939.                 }
  1940.             }
  1941.         }
  1942.     }
  1943.     // Final O(N) pass: enumerate classes
  1944.     labels.resize(N);
  1945.     int nclasses = 0;
  1946.     for( i = 0; i < N; i++ )
  1947.     {
  1948.         int root = i;
  1949.         while( nodes[root][PARENT] >= 0 )
  1950.             root = nodes[root][PARENT];
  1951.         // re-use the rank as the class label
  1952.         if( nodes[root][RANK] >= 0 )
  1953.             nodes[root][RANK] = ~nclasses++;
  1954.         labels[i] = ~nodes[root][RANK];
  1955.     }
  1956.     return nclasses;
  1957. }
  1958. //////////////////////////////////////////////////////////////////////////////
  1959. template<typename _Tp> inline Seq<_Tp>::Seq() : seq(0) {}
  1960. template<typename _Tp> inline Seq<_Tp>::Seq( const CvSeq* _seq ) : seq((CvSeq*)_seq)
  1961. {
  1962.     CV_Assert(!_seq || _seq->elem_size == sizeof(_Tp));
  1963. }
  1964. template<typename _Tp> inline Seq<_Tp>::Seq( MemStorage& storage,
  1965.                                              int headerSize )
  1966. {
  1967.     CV_Assert(headerSize >= (int)sizeof(CvSeq));
  1968.     seq = cvCreateSeq(DataType<_Tp>::type, headerSize, sizeof(_Tp), storage);
  1969. }
  1970. template<typename _Tp> inline _Tp& Seq<_Tp>::operator [](int idx)
  1971. { return *(_Tp*)cvGetSeqElem(seq, idx); }
  1972. template<typename _Tp> inline const _Tp& Seq<_Tp>::operator [](int idx) const
  1973. { return *(_Tp*)cvGetSeqElem(seq, idx); }
  1974. template<typename _Tp> inline SeqIterator<_Tp> Seq<_Tp>::begin() const
  1975. { return SeqIterator<_Tp>(*this); }
  1976. template<typename _Tp> inline SeqIterator<_Tp> Seq<_Tp>::end() const
  1977. { return SeqIterator<_Tp>(*this, true); }
  1978. template<typename _Tp> inline size_t Seq<_Tp>::size() const
  1979. { return seq ? seq->total : 0; }
  1980. template<typename _Tp> inline int Seq<_Tp>::type() const
  1981. { return seq ? CV_MAT_TYPE(seq->flags) : 0; }
  1982. template<typename _Tp> inline int Seq<_Tp>::depth() const
  1983. { return seq ? CV_MAT_DEPTH(seq->flags) : 0; }
  1984. template<typename _Tp> inline int Seq<_Tp>::channels() const
  1985. { return seq ? CV_MAT_CN(seq->flags) : 0; }
  1986. template<typename _Tp> inline size_t Seq<_Tp>::elemSize() const
  1987. { return seq ? seq->elem_size : 0; }
  1988. template<typename _Tp> inline size_t Seq<_Tp>::index(const _Tp& elem) const
  1989. { return cvSeqElemIdx(seq, &elem); }
  1990. template<typename _Tp> inline void Seq<_Tp>::push_back(const _Tp& elem)
  1991. { cvSeqPush(seq, &elem); }
  1992. template<typename _Tp> inline void Seq<_Tp>::push_front(const _Tp& elem)
  1993. { cvSeqPushFront(seq, &elem); }
  1994. template<typename _Tp> inline void Seq<_Tp>::push_back(const _Tp* elem, size_t count)
  1995. { cvSeqPushMulti(seq, elem, (int)count, 0); }
  1996. template<typename _Tp> inline void Seq<_Tp>::push_front(const _Tp* elem, size_t count)
  1997. { cvSeqPushMulti(seq, elem, (int)count, 1); }    
  1998.     
  1999. template<typename _Tp> inline _Tp& Seq<_Tp>::back()
  2000. { return *(_Tp*)cvGetSeqElem(seq, -1); }
  2001. template<typename _Tp> inline const _Tp& Seq<_Tp>::back() const
  2002. { return *(const _Tp*)cvGetSeqElem(seq, -1); }
  2003. template<typename _Tp> inline _Tp& Seq<_Tp>::front()
  2004. { return *(_Tp*)cvGetSeqElem(seq, 0); }
  2005. template<typename _Tp> inline const _Tp& Seq<_Tp>::front() const
  2006. { return *(const _Tp*)cvGetSeqElem(seq, 0); }
  2007. template<typename _Tp> inline bool Seq<_Tp>::empty() const
  2008. { return !seq || seq->total == 0; }
  2009. template<typename _Tp> inline void Seq<_Tp>::clear()
  2010. { if(seq) cvClearSeq(seq); }
  2011. template<typename _Tp> inline void Seq<_Tp>::pop_back()
  2012. { cvSeqPop(seq); }
  2013. template<typename _Tp> inline void Seq<_Tp>::pop_front()
  2014. { cvSeqPopFront(seq); }
  2015. template<typename _Tp> inline void Seq<_Tp>::pop_back(_Tp* elem, size_t count)
  2016. { cvSeqPopMulti(seq, elem, (int)count, 0); }
  2017. template<typename _Tp> inline void Seq<_Tp>::pop_front(_Tp* elem, size_t count)
  2018. { cvSeqPopMulti(seq, elem, (int)count, 1); }    
  2019. template<typename _Tp> inline void Seq<_Tp>::insert(int idx, const _Tp& elem)
  2020. { cvSeqInsert(seq, idx, &elem); }
  2021.     
  2022. template<typename _Tp> inline void Seq<_Tp>::insert(int idx, const _Tp* elems, size_t count)
  2023. {
  2024.     CvMat m = cvMat(1, count, DataType<_Tp>::type, elems);
  2025.     cvSeqInsertSlice(seq, idx, &m);
  2026. }
  2027.     
  2028. template<typename _Tp> inline void Seq<_Tp>::remove(int idx)
  2029. { cvSeqRemove(seq, idx); }
  2030.     
  2031. template<typename _Tp> inline void Seq<_Tp>::remove(const Range& r)
  2032. { cvSeqRemoveSlice(seq, r); }
  2033.     
  2034. template<typename _Tp> inline void Seq<_Tp>::copyTo(vector<_Tp>& vec, const Range& range) const
  2035. {
  2036.     size_t len = !seq ? 0 : range == Range::all() ? seq->total : range.end - range.start;
  2037.     vec.resize(len);
  2038.     if( seq && len )
  2039.         cvCvtSeqToArray(seq, &vec[0], range);
  2040. }
  2041. template<typename _Tp> inline Seq<_Tp>::operator vector<_Tp>() const
  2042. {
  2043.     vector<_Tp> vec;
  2044.     copyTo(vec);
  2045.     return vec;
  2046. }
  2047. template<typename _Tp> inline SeqIterator<_Tp>::SeqIterator()
  2048. { memset(this, 0, sizeof(*this)); }
  2049. template<typename _Tp> inline SeqIterator<_Tp>::SeqIterator(const Seq<_Tp>& seq, bool seekEnd)
  2050. {
  2051.     cvStartReadSeq(seq.seq, this);
  2052.     if( seekEnd )
  2053.         index = seq.seq->total;
  2054. }
  2055. template<typename _Tp> inline void SeqIterator<_Tp>::seek(size_t pos)
  2056. {
  2057.     cvSetSeqReaderPos(this, (int)pos, false);
  2058.     index = pos;
  2059. }
  2060. template<typename _Tp> inline size_t SeqIterator<_Tp>::tell() const
  2061. { return index; }
  2062. template<typename _Tp> inline _Tp& SeqIterator<_Tp>::operator *()
  2063. { return *(_Tp*)ptr; }
  2064. template<typename _Tp> inline const _Tp& SeqIterator<_Tp>::operator *() const
  2065. { return *(const _Tp*)ptr; }
  2066. template<typename _Tp> inline SeqIterator<_Tp>& SeqIterator<_Tp>::operator ++()
  2067. {
  2068.     CV_NEXT_SEQ_ELEM(sizeof(_Tp), *this);
  2069.     if( ++index >= seq->total*2 )
  2070.         index = 0;
  2071.     return *this;
  2072. }
  2073. template<typename _Tp> inline SeqIterator<_Tp> SeqIterator<_Tp>::operator ++(int) const
  2074. {
  2075.     SeqIterator<_Tp> it = *this;
  2076.     ++*this;
  2077.     return it;
  2078. }
  2079. template<typename _Tp> inline SeqIterator<_Tp>& SeqIterator<_Tp>::operator --()
  2080. {
  2081.     CV_PREV_SEQ_ELEM(sizeof(_Tp), *this);
  2082.     if( --index < 0 )
  2083.         index = seq->total*2-1;
  2084.     return *this;
  2085. }
  2086. template<typename _Tp> inline SeqIterator<_Tp> SeqIterator<_Tp>::operator --(int) const
  2087. {
  2088.     SeqIterator<_Tp> it = *this;
  2089.     --*this;
  2090.     return it;
  2091. }
  2092. template<typename _Tp> inline SeqIterator<_Tp>& SeqIterator<_Tp>::operator +=(int delta)
  2093. {
  2094.     cvSetSeqReaderPos(this, delta, 1);
  2095.     index += delta;
  2096.     int n = seq->total*2;
  2097.     if( index < 0 )
  2098.         index += n;
  2099.     if( index >= n )
  2100.         index -= n;
  2101.     return *this;
  2102. }
  2103. template<typename _Tp> inline SeqIterator<_Tp>& SeqIterator<_Tp>::operator -=(int delta)
  2104. {
  2105.     return (*this += -delta);
  2106. }
  2107. template<typename _Tp> inline ptrdiff_t operator - (const SeqIterator<_Tp>& a,
  2108.                                                     const SeqIterator<_Tp>& b)
  2109. {
  2110.     ptrdiff_t delta = a.index - b.index, n = a.seq->total;
  2111.     if( std::abs(delta) > n )
  2112.         delta += delta < 0 ? n : -n;
  2113.     return delta;
  2114. }
  2115. template<typename _Tp> inline bool operator == (const SeqIterator<_Tp>& a,
  2116.                                                 const SeqIterator<_Tp>& b)
  2117. {
  2118.     return a.seq == b.seq && a.index == b.index;
  2119. }
  2120. template<typename _Tp> inline bool operator != (const SeqIterator<_Tp>& a,
  2121.                                                 const SeqIterator<_Tp>& b)
  2122. {
  2123.     return !(a == b);
  2124. }
  2125. }
  2126. #endif // __cplusplus
  2127. #endif // _OPENCV_CORE_OPERATIONS_H_