Point Cloud Library (PCL)
1.7.0
|
00001 /* $NoKeywords: $ */ 00002 /* 00003 // 00004 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved. 00005 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert 00006 // McNeel & Associates. 00007 // 00008 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY. 00009 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF 00010 // MERCHANTABILITY ARE HEREBY DISCLAIMED. 00011 // 00012 // For complete openNURBS copyright information see <http://www.opennurbs.org>. 00013 // 00014 //////////////////////////////////////////////////////////////// 00015 */ 00016 00017 #if !defined(ON_ARRAY_DEFS_INC_) 00018 #define ON_ARRAY_DEFS_INC_ 00019 00020 #if defined(ON_COMPILER_MSC) 00021 00022 // When this file is parsed with /W4 warnings, two bogus warnings 00023 // are generated. 00024 #pragma warning(push) 00025 00026 // The ON_ClassArray<T>::DestroyElement template function generates a 00027 // C4100: 'x' : unreferenced formal parameter 00028 // warning. 00029 // This appears to be caused by a bug in the compiler warning code 00030 // or the way templates are expanded. This pragma is needed squelch the 00031 // bogus warning. 00032 #pragma warning(disable:4100) 00033 00034 // The ON_CompareIncreasing and ON_CompareDecreasing templates generate a 00035 // C4211: nonstandard extension used : redefined extern to static 00036 // warning. Microsoft's compiler appears to have a little trouble 00037 // when static functions are declared before they are defined in a 00038 // single .cpp file. This pragma is needed squelch the bogus warning. 00039 #pragma warning(disable:4211) 00040 #endif 00041 00042 // The main reason the definitions of the functions for the 00043 // ON_SimpleArray and ON_ClassArray templates are in this separate 00044 // file is so that the Microsoft developer studio autocomplete 00045 // functions will work on these classes. 00046 // 00047 // This file is included by opennurbs_array.h in the appropriate 00048 // spot. If you need the definitions in the file, then you 00049 // should include opennurbs_array.h and let it take care of 00050 // including this file. 00051 00052 ///////////////////////////////////////////////////////////////////////////////////// 00053 // Class ON_SimpleArray<> 00054 ///////////////////////////////////////////////////////////////////////////////////// 00055 00056 // construction //////////////////////////////////////////////////////// 00057 00058 template <class T> 00059 T* ON_SimpleArray<T>::Realloc(T* ptr,int capacity) 00060 { 00061 return (T*)onrealloc(ptr,capacity*sizeof(T)); 00062 } 00063 00064 template <class T> 00065 ON_SimpleArray<T>::ON_SimpleArray() 00066 : m_a(0), 00067 m_count(0), 00068 m_capacity(0) 00069 {} 00070 00071 template <class T> 00072 ON_SimpleArray<T>::ON_SimpleArray( int c ) 00073 : m_a(0), 00074 m_count(0), 00075 m_capacity(0) 00076 { 00077 if ( c > 0 ) 00078 SetCapacity( c ); 00079 } 00080 00081 // Copy constructor 00082 template <class T> 00083 ON_SimpleArray<T>::ON_SimpleArray( const ON_SimpleArray<T>& src ) 00084 : m_a(0), 00085 m_count(0), 00086 m_capacity(0) 00087 { 00088 *this = src; // operator= defined below 00089 } 00090 00091 template <class T> 00092 ON_SimpleArray<T>::~ON_SimpleArray() 00093 { 00094 SetCapacity(0); 00095 } 00096 00097 template <class T> 00098 ON_SimpleArray<T>& ON_SimpleArray<T>::operator=( const ON_SimpleArray<T>& src ) 00099 { 00100 if( &src != this ) { 00101 if ( src.m_count <= 0 ) { 00102 m_count = 0; 00103 } 00104 else { 00105 if ( m_capacity < src.m_count ) { 00106 SetCapacity( src.m_count ); 00107 } 00108 if ( m_a ) { 00109 m_count = src.m_count; 00110 memcpy( m_a, src.m_a, m_count*sizeof(T) ); 00111 } 00112 } 00113 } 00114 return *this; 00115 } 00116 00117 // emergency destroy /////////////////////////////////////////////////// 00118 00119 template <class T> 00120 void ON_SimpleArray<T>::EmergencyDestroy(void) 00121 { 00122 m_count = 0; 00123 m_capacity = 0; 00124 m_a = 0; 00125 } 00126 00127 // query /////////////////////////////////////////////////////////////// 00128 00129 template <class T> 00130 int ON_SimpleArray<T>::Count() const 00131 { 00132 return m_count; 00133 } 00134 00135 template <class T> 00136 unsigned int ON_SimpleArray<T>::UnsignedCount() const 00137 { 00138 return ((unsigned int)m_count); 00139 } 00140 00141 template <class T> 00142 int ON_SimpleArray<T>::Capacity() const 00143 { 00144 return m_capacity; 00145 } 00146 00147 template <class T> 00148 unsigned int ON_SimpleArray<T>::SizeOfArray() const 00149 { 00150 return ((unsigned int)(m_capacity*sizeof(T))); 00151 } 00152 00153 template <class T> 00154 unsigned int ON_SimpleArray<T>::SizeOfElement() const 00155 { 00156 return ((unsigned int)(sizeof(T))); 00157 } 00158 00159 00160 template <class T> 00161 ON__UINT32 ON_SimpleArray<T>::DataCRC(ON__UINT32 current_remainder) const 00162 { 00163 return ON_CRC32(current_remainder,m_count*sizeof(m_a[0]),m_a); 00164 } 00165 00166 template <class T> 00167 T& ON_SimpleArray<T>::operator[]( int i ) 00168 { 00169 #if defined(ON_DEBUG) 00170 if ( i < 0 || i > m_capacity ) 00171 { 00172 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00173 } 00174 #endif 00175 return m_a[i]; 00176 } 00177 00178 template <class T> 00179 T& ON_SimpleArray<T>::operator[]( unsigned int i ) 00180 { 00181 #if defined(ON_DEBUG) 00182 if ( i > (unsigned int)m_capacity ) 00183 { 00184 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00185 } 00186 #endif 00187 return m_a[i]; 00188 } 00189 00190 00191 template <class T> 00192 T& ON_SimpleArray<T>::operator[]( ON__INT64 i ) 00193 { 00194 #if defined(ON_DEBUG) 00195 if ( i < 0 || i > (ON__INT64)m_capacity ) 00196 { 00197 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00198 } 00199 #endif 00200 return m_a[i]; 00201 } 00202 00203 template <class T> 00204 T& ON_SimpleArray<T>::operator[]( ON__UINT64 i ) 00205 { 00206 #if defined(ON_DEBUG) 00207 if ( i > (ON__UINT64)m_capacity ) 00208 { 00209 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00210 } 00211 #endif 00212 return m_a[i]; 00213 } 00214 00215 template <class T> 00216 const T& ON_SimpleArray<T>::operator[](int i) const 00217 { 00218 #if defined(ON_DEBUG) 00219 if ( i < 0 || i > m_capacity ) 00220 { 00221 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00222 } 00223 #endif 00224 return m_a[i]; 00225 } 00226 00227 template <class T> 00228 const T& ON_SimpleArray<T>::operator[](unsigned int i) const 00229 { 00230 #if defined(ON_DEBUG) 00231 if ( i > (unsigned int)m_capacity ) 00232 { 00233 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00234 } 00235 #endif 00236 return m_a[i]; 00237 } 00238 00239 00240 template <class T> 00241 const T& ON_SimpleArray<T>::operator[](ON__INT64 i) const 00242 { 00243 #if defined(ON_DEBUG) 00244 if ( i < 0 || i > ((ON__INT64)m_capacity) ) 00245 { 00246 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00247 } 00248 #endif 00249 return m_a[i]; 00250 } 00251 00252 template <class T> 00253 const T& ON_SimpleArray<T>::operator[](ON__UINT64 i) const 00254 { 00255 #if defined(ON_DEBUG) 00256 if ( i > (ON__UINT64)m_capacity ) 00257 { 00258 ON_ERROR("ON_SimpleArray[i]: i out of range."); 00259 } 00260 #endif 00261 return m_a[i]; 00262 } 00263 00264 00265 template <class T> 00266 ON_SimpleArray<T>::operator T*() 00267 { 00268 return (m_count > 0) ? m_a : 0; 00269 } 00270 00271 template <class T> 00272 ON_SimpleArray<T>::operator const T*() const 00273 { 00274 return (m_count > 0) ? m_a : 0; 00275 } 00276 00277 template <class T> 00278 T* ON_SimpleArray<T>::Array() 00279 { 00280 return m_a; 00281 } 00282 00283 template <class T> 00284 const T* ON_SimpleArray<T>::Array() const 00285 { 00286 return m_a; 00287 } 00288 00289 template <class T> 00290 T* ON_SimpleArray<T>::KeepArray() 00291 { 00292 T* p = m_a; 00293 m_a = 0; 00294 m_count = 0; 00295 m_capacity = 0; 00296 return p; 00297 } 00298 00299 template <class T> 00300 void ON_SimpleArray<T>::SetArray(T* p) 00301 { 00302 if ( m_a && m_a != p ) 00303 onfree(m_a); 00304 m_a = p; 00305 } 00306 00307 template <class T> 00308 void ON_SimpleArray<T>::SetArray(T* p, int count, int capacity) 00309 { 00310 if ( m_a && m_a != p ) 00311 onfree(m_a); 00312 m_a = p; 00313 m_count = count; 00314 m_capacity = capacity; 00315 } 00316 00317 template <class T> 00318 T* ON_SimpleArray<T>::First() 00319 { 00320 return (m_count > 0) ? m_a : 0; 00321 } 00322 00323 template <class T> 00324 const T* ON_SimpleArray<T>::First() const 00325 { 00326 return (m_count > 0) ? m_a : 0; 00327 } 00328 00329 template <class T> 00330 T* ON_SimpleArray<T>::At( int i ) 00331 { 00332 return (i >= 0 && i < m_count) ? m_a+i : 0; 00333 } 00334 00335 template <class T> 00336 T* ON_SimpleArray<T>::At( unsigned int i ) 00337 { 00338 return (i < (unsigned int)m_count) ? m_a+i : 0; 00339 } 00340 00341 template <class T> 00342 const T* ON_SimpleArray<T>::At( int i) const 00343 { 00344 return (i >= 0 && i < m_count) ? m_a+i : 0; 00345 } 00346 00347 template <class T> 00348 const T* ON_SimpleArray<T>::At( unsigned int i) const 00349 { 00350 return (i < (unsigned int)m_count) ? m_a+i : 0; 00351 } 00352 00353 template <class T> 00354 T* ON_SimpleArray<T>::At( ON__INT64 i ) 00355 { 00356 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0; 00357 } 00358 00359 template <class T> 00360 T* ON_SimpleArray<T>::At( ON__UINT64 i ) 00361 { 00362 return (i < (ON__UINT64)m_count) ? m_a+i : 0; 00363 } 00364 00365 template <class T> 00366 const T* ON_SimpleArray<T>::At( ON__INT64 i) const 00367 { 00368 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0; 00369 } 00370 00371 template <class T> 00372 const T* ON_SimpleArray<T>::At( ON__UINT64 i) const 00373 { 00374 return (i < (ON__UINT64)m_count) ? m_a+i : 0; 00375 } 00376 00377 template <class T> 00378 T* ON_SimpleArray<T>::Last() 00379 { 00380 return (m_count > 0) ? m_a+(m_count-1) : 0; 00381 } 00382 00383 template <class T> 00384 const T* ON_SimpleArray<T>::Last() const 00385 { 00386 return (m_count > 0) ? m_a+(m_count-1) : 0; 00387 } 00388 00389 // array operations //////////////////////////////////////////////////// 00390 00391 template <class T> 00392 void ON_SimpleArray<T>::Move( int dest_i, int src_i, int ele_cnt ) 00393 { 00394 // private function for moving blocks of array memory 00395 // caller is responsible for updating m_count. 00396 if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i || 00397 src_i + ele_cnt > m_count || dest_i > m_count ) 00398 return; 00399 00400 int capacity = dest_i + ele_cnt; 00401 if ( capacity > m_capacity ) { 00402 if ( capacity < 2*m_capacity ) 00403 capacity = 2*m_capacity; 00404 SetCapacity( capacity ); 00405 } 00406 00407 memmove( &m_a[dest_i], &m_a[src_i], ele_cnt*sizeof(T) ); 00408 } 00409 00410 template <class T> 00411 T& ON_SimpleArray<T>::AppendNew() 00412 { 00413 if ( m_count == m_capacity ) 00414 { 00415 int new_capacity = NewCapacity(); 00416 Reserve( new_capacity ); 00417 } 00418 memset( &m_a[m_count], 0, sizeof(T) ); 00419 return m_a[m_count++]; 00420 } 00421 00422 template <class T> 00423 void ON_SimpleArray<T>::Append( const T& x ) 00424 { 00425 if ( m_count == m_capacity ) 00426 { 00427 const int newcapacity = NewCapacity(); 00428 if (m_a) 00429 { 00430 const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers 00431 if ( s >= 0 && s < m_capacity ) 00432 { 00433 // 26 Sep 2005 Dale Lear 00434 // User passed in an element of the m_a[] 00435 // that will get reallocated by the call 00436 // to Reserve(newcapacity). 00437 T temp; // ON_*Array<> templates do not require robust copy constructor. 00438 temp = x; // ON_*Array<> templates require a robust operator=. 00439 Reserve( newcapacity ); 00440 m_a[m_count++] = temp; 00441 return; 00442 } 00443 } 00444 Reserve(newcapacity); 00445 } 00446 m_a[m_count++] = x; 00447 } 00448 00449 template <class T> 00450 void ON_SimpleArray<T>::Append( int count, const T* p ) 00451 { 00452 if ( count > 0 && p ) 00453 { 00454 if ( count + m_count > m_capacity ) 00455 { 00456 int newcapacity = NewCapacity(); 00457 if ( newcapacity < count + m_count ) 00458 newcapacity = count + m_count; 00459 Reserve( newcapacity ); 00460 } 00461 memcpy( m_a + m_count, p, count*sizeof(T) ); 00462 m_count += count; 00463 } 00464 } 00465 00466 template <class T> 00467 void ON_SimpleArray<T>::Insert( int i, const T& x ) 00468 { 00469 if( i >= 0 && i <= m_count ) 00470 { 00471 if ( m_count == m_capacity ) 00472 { 00473 int newcapacity = NewCapacity(); 00474 Reserve( newcapacity ); 00475 } 00476 m_count++; 00477 Move( i+1, i, m_count-1-i ); 00478 m_a[i] = x; 00479 } 00480 } 00481 00482 template <class T> 00483 void ON_SimpleArray<T>::Remove() 00484 { 00485 Remove(m_count-1); 00486 } 00487 00488 template <class T> 00489 void ON_SimpleArray<T>::Remove( int i ) 00490 { 00491 if ( i >= 0 && i < m_count ) { 00492 Move( i, i+1, m_count-1-i ); 00493 m_count--; 00494 memset( &m_a[m_count], 0, sizeof(T) ); 00495 } 00496 } 00497 00498 template <class T> 00499 void ON_SimpleArray<T>::Empty() 00500 { 00501 if ( m_a ) 00502 memset( m_a, 0, m_capacity*sizeof(T) ); 00503 m_count = 0; 00504 } 00505 00506 template <class T> 00507 void ON_SimpleArray<T>::Reverse() 00508 { 00509 // NOTE: 00510 // If anything in "T" depends on the value of this's address, 00511 // then don't call Reverse(). 00512 T t; 00513 int i = 0; 00514 int j = m_count-1; 00515 for ( /*empty*/; i < j; i++, j-- ) { 00516 t = m_a[i]; 00517 m_a[i] = m_a[j]; 00518 m_a[j] = t; 00519 } 00520 } 00521 00522 template <class T> 00523 void ON_SimpleArray<T>::Swap( int i, int j ) 00524 { 00525 if ( i != j ) { 00526 const T t(m_a[i]); 00527 m_a[i] = m_a[j]; 00528 m_a[j] = t; 00529 } 00530 } 00531 00532 template <class T> 00533 int ON_SimpleArray<T>::Search( const T& key ) const 00534 { 00535 const T* p = &key; 00536 for ( int i = 0; i < m_count; i++ ) { 00537 if (!memcmp(p,m_a+i,sizeof(T))) 00538 return i; 00539 } 00540 return -1; 00541 } 00542 00543 template <class T> 00544 int ON_SimpleArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const 00545 { 00546 for ( int i = 0; i < m_count; i++ ) { 00547 if (!compar(key,m_a+i)) 00548 return i; 00549 } 00550 return -1; 00551 } 00552 00553 template <class T> 00554 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const 00555 { 00556 const T* found = (key&&m_a&&m_count>0) 00557 ? (const T*)bsearch( key, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ) 00558 : 0; 00559 00560 // This worked on a wide range of 32 bit compilers. 00561 00562 int rc; 00563 if ( 0 != found ) 00564 { 00565 // Convert "found" pointer to array index. 00566 00567 #if defined(ON_COMPILER_MSC1300) 00568 rc = ((int)(found - m_a)); 00569 #elif 8 == ON_SIZEOF_POINTER 00570 // In an ideal world, return ((int)(found - m_a)) would work everywhere. 00571 // In practice, this should work any 64 bit compiler and we can hope 00572 // the optimzer generates efficient code. 00573 const ON__UINT64 fptr = (ON__UINT64)found; 00574 const ON__UINT64 aptr = (ON__UINT64)m_a; 00575 const ON__UINT64 sz = (ON__UINT64)sizeof(T); 00576 const ON__UINT64 i = (fptr - aptr)/sz; 00577 rc = (int)i; 00578 #else 00579 // In an ideal world, return ((int)(found - m_a)) would work everywhere. 00580 // In practice, this should work any 32 bit compiler and we can hope 00581 // the optimzer generates efficient code. 00582 const ON__UINT32 fptr = (ON__UINT32)found; 00583 const ON__UINT32 aptr = (ON__UINT32)m_a; 00584 const ON__UINT32 sz = (ON__UINT32)sizeof(T); 00585 const ON__UINT32 i = (fptr - aptr)/sz; 00586 rc = (int)i; 00587 #endif 00588 } 00589 else 00590 { 00591 // "key" not found 00592 rc = -1; 00593 } 00594 00595 return rc; 00596 00597 } 00598 00599 template <class T> 00600 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const 00601 { 00602 if ( count > m_count ) 00603 count = m_count; 00604 if ( count <= 0 ) 00605 return -1; 00606 const T* found = (key&&m_a&&m_count>0) 00607 ? (const T*)bsearch( key, m_a, count, sizeof(T), (int(*)(const void*,const void*))compar ) 00608 : 0; 00609 00610 // This worked on a wide range of 32 bit compilers. 00611 00612 int rc; 00613 if ( 0 != found ) 00614 { 00615 // Convert "found" pointer to array index. 00616 00617 #if defined(ON_COMPILER_MSC1300) 00618 rc = ((int)(found - m_a)); 00619 #elif 8 == ON_SIZEOF_POINTER 00620 // In an ideal world, return ((int)(found - m_a)) would work everywhere. 00621 // In practice, this should work any 64 bit compiler and we can hope 00622 // the optimzer generates efficient code. 00623 const ON__UINT64 fptr = (ON__UINT64)found; 00624 const ON__UINT64 aptr = (ON__UINT64)m_a; 00625 const ON__UINT64 sz = (ON__UINT64)sizeof(T); 00626 const ON__UINT64 i = (fptr - aptr)/sz; 00627 rc = (int)i; 00628 #else 00629 // In an ideal world, return ((int)(found - m_a)) would work everywhere. 00630 // In practice, this should work any 32 bit compiler and we can hope 00631 // the optimzer generates efficient code. 00632 const ON__UINT32 fptr = (ON__UINT32)found; 00633 const ON__UINT32 aptr = (ON__UINT32)m_a; 00634 const ON__UINT32 sz = (ON__UINT32)sizeof(T); 00635 const ON__UINT32 i = (fptr - aptr)/sz; 00636 rc = (int)i; 00637 #endif 00638 } 00639 else 00640 { 00641 // "key" not found 00642 rc = -1; 00643 } 00644 return rc; 00645 } 00646 00647 00648 00649 template <class T> 00650 bool ON_SimpleArray<T>::HeapSort( int (*compar)(const T*,const T*) ) 00651 { 00652 bool rc = false; 00653 if ( m_a && m_count > 0 && compar ) { 00654 if ( m_count > 1 ) 00655 ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 00656 rc = true; 00657 } 00658 return rc; 00659 } 00660 00661 template <class T> 00662 bool ON_SimpleArray<T>::QuickSort( int (*compar)(const T*,const T*) ) 00663 { 00664 bool rc = false; 00665 if ( m_a && m_count > 0 && compar ) { 00666 if ( m_count > 1 ) 00667 ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 00668 rc = true; 00669 } 00670 return rc; 00671 } 00672 00673 template <class T> 00674 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const 00675 { 00676 bool rc = false; 00677 if ( m_a && m_count > 0 && compar && index ) { 00678 if ( m_count > 1 ) 00679 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 00680 else if ( m_count == 1 ) 00681 index[0] = 0; 00682 rc = true; 00683 } 00684 return rc; 00685 } 00686 00687 template <class T> 00688 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const 00689 { 00690 bool rc = false; 00691 if ( m_a && m_count > 0 && compar && index ) { 00692 if ( m_count > 1 ) 00693 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p ); 00694 else if ( m_count == 1 ) 00695 index[0] = 0; 00696 rc = true; 00697 } 00698 return rc; 00699 } 00700 00701 template <class T> 00702 bool ON_SimpleArray<T>::Permute( const int* index ) 00703 { 00704 bool rc = false; 00705 if ( m_a && m_count > 0 && index ) { 00706 int i; 00707 T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0])); 00708 memcpy( buffer, m_a, m_count*sizeof(T) ); 00709 for (i = 0; i < m_count; i++ ) 00710 memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator= 00711 onfree(buffer); 00712 rc = true; 00713 } 00714 return rc; 00715 } 00716 00717 template <class T> 00718 void ON_SimpleArray<T>::Zero() 00719 { 00720 if ( m_a && m_capacity > 0 ) { 00721 memset( m_a, 0, m_capacity*sizeof(T) ); 00722 } 00723 } 00724 00725 template <class T> 00726 void ON_SimpleArray<T>::MemSet( unsigned char value ) 00727 { 00728 if ( m_a && m_capacity > 0 ) { 00729 memset( m_a, value, m_capacity*sizeof(T) ); 00730 } 00731 } 00732 00733 // memory managment //////////////////////////////////////////////////// 00734 00735 template <class T> 00736 void ON_SimpleArray<T>::Reserve( int newcap ) 00737 { 00738 if( m_capacity < newcap ) 00739 SetCapacity( newcap ); 00740 } 00741 00742 template <class T> 00743 void ON_SimpleArray<T>::Shrink() 00744 { 00745 SetCapacity( m_count ); 00746 } 00747 00748 template <class T> 00749 void ON_SimpleArray<T>::Destroy() 00750 { 00751 SetCapacity( 0 ); 00752 } 00753 00754 // low level memory managment ////////////////////////////////////////// 00755 00756 template <class T> 00757 void ON_SimpleArray<T>::SetCount( int count ) 00758 { 00759 if ( count >= 0 && count <= m_capacity ) 00760 m_count = count; 00761 } 00762 00763 template <class T> 00764 void ON_SimpleArray<T>::SetCapacity( int capacity ) 00765 { 00766 // sets capacity to input value 00767 if ( capacity != m_capacity ) { 00768 if( capacity > 0 ) { 00769 if ( m_count > capacity ) 00770 m_count = capacity; 00771 // NOTE: Realloc() does an allocation if the first argument is NULL. 00772 m_a = Realloc( m_a, capacity ); 00773 if ( m_a ) { 00774 if ( capacity > m_capacity ) { 00775 // zero new memory 00776 memset( m_a + m_capacity, 0, (capacity-m_capacity)*sizeof(T) ); 00777 } 00778 m_capacity = capacity; 00779 } 00780 else { 00781 // out of memory 00782 m_count = m_capacity = 0; 00783 } 00784 } 00785 else if (m_a) { 00786 Realloc(m_a,0); 00787 m_a = 0; 00788 m_count = m_capacity = 0; 00789 } 00790 } 00791 } 00792 00793 template <class T> 00794 int ON_SimpleArray<T>::NewCapacity() const 00795 { 00796 // Note: 00797 // This code appears in ON_SimpleArray<T>::NewCapacity() 00798 // and ON_ClassArray<T>::NewCapacity(). Changes made to 00799 // either function should be made to both functions. 00800 // Because this code is template code that has to 00801 // support dynamic linking and the code is defined 00802 // in a header, I'm using copy-and-paste rather 00803 // than a static. 00804 00805 // This function returns 2*m_count unless that will 00806 // result in an additional allocation of more than 00807 // cap_size bytes. The cap_size concept was added in 00808 // January 2010 because some calculations on enormous 00809 // models were slightly underestimating the initial 00810 // Reserve() size and then wasting gigabytes of memory. 00811 00812 // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os 00813 const size_t cap_size = 32*sizeof(void*)*1024*1024; 00814 if (m_count*sizeof(T) <= cap_size || m_count < 8) 00815 return ((m_count <= 2) ? 4 : 2*m_count); 00816 00817 // Growing the array will increase the memory 00818 // use by more than cap_size. 00819 int delta_count = 8 + cap_size/sizeof(T); 00820 if ( delta_count > m_count ) 00821 delta_count = m_count; 00822 return (m_count + delta_count); 00823 } 00824 00825 template <class T> 00826 int ON_ClassArray<T>::NewCapacity() const 00827 { 00828 // Note: 00829 // This code appears in ON_SimpleArray<T>::NewCapacity() 00830 // and ON_ClassArray<T>::NewCapacity(). Changes made to 00831 // either function should be made to both functions. 00832 // Because this code is template code that has to 00833 // support dynamic linking and the code is defined 00834 // in a header, I'm using copy-and-paste rather 00835 // than a static. 00836 00837 // This function returns 2*m_count unless that will 00838 // result in an additional allocation of more than 00839 // cap_size bytes. The cap_size concept was added in 00840 // January 2010 because some calculations on enormous 00841 // models were slightly underestimating the initial 00842 // Reserve() size and then wasting gigabytes of memory. 00843 00844 // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os 00845 const size_t cap_size = 32*sizeof(void*)*1024*1024; 00846 if (m_count*sizeof(T) <= cap_size || m_count < 8) 00847 return ((m_count <= 2) ? 4 : 2*m_count); 00848 00849 // Growing the array will increase the memory 00850 // use by more than cap_size. 00851 int delta_count = 8 + cap_size/sizeof(T); 00852 if ( delta_count > m_count ) 00853 delta_count = m_count; 00854 return (m_count + delta_count); 00855 } 00856 00857 ///////////////////////////////////////////////////////////////////////////////////// 00858 // Class ON_ObjectArray<> 00859 ///////////////////////////////////////////////////////////////////////////////////// 00860 00861 template <class T> 00862 ON_ObjectArray<T>::ON_ObjectArray() 00863 { 00864 } 00865 00866 template <class T> 00867 ON_ObjectArray<T>::~ON_ObjectArray() 00868 { 00869 } 00870 00871 template <class T> 00872 ON_ObjectArray<T>::ON_ObjectArray( const ON_ObjectArray<T>& src ) : ON_ClassArray<T>(src) 00873 { 00874 } 00875 00876 template <class T> 00877 ON_ObjectArray<T>& ON_ObjectArray<T>::operator=( const ON_ObjectArray<T>& src) 00878 { 00879 if( this != &src) 00880 { 00881 ON_ClassArray<T>::operator =(src); 00882 } 00883 return *this; 00884 } 00885 00886 00887 template <class T> 00888 ON_ObjectArray<T>::ON_ObjectArray( int c ) 00889 : ON_ClassArray<T>(c) 00890 { 00891 } 00892 00893 template <class T> 00894 T* ON_ObjectArray<T>::Realloc(T* ptr,int capacity) 00895 { 00896 T* reptr = (T*)onrealloc(ptr,capacity*sizeof(T)); 00897 if ( ptr && reptr && reptr != ptr ) 00898 { 00899 // The "this->" in this->m_count and this->m_a 00900 // are needed for gcc 4 to compile. 00901 int i; 00902 for ( i = 0; i < this->m_count; i++ ) 00903 { 00904 reptr[i].MemoryRelocate(); 00905 } 00906 } 00907 return reptr; 00908 } 00909 00910 ///////////////////////////////////////////////////////////////////////////////////// 00911 // Class ON_ClassArray<> 00912 ///////////////////////////////////////////////////////////////////////////////////// 00913 00914 00915 // construction //////////////////////////////////////////////////////// 00916 00917 template <class T> 00918 T* ON_ClassArray<T>::Realloc(T* ptr,int capacity) 00919 { 00920 return (T*)onrealloc(ptr,capacity*sizeof(T)); 00921 } 00922 00923 template <class T> 00924 ON__UINT32 ON_ObjectArray<T>::DataCRC(ON__UINT32 current_remainder) const 00925 { 00926 // The "this->" in this->m_count and this->m_a 00927 // are needed for gcc 4 to compile. 00928 int i; 00929 for ( i = 0; i < this->m_count; i++ ) 00930 { 00931 current_remainder = this->m_a[i].DataCRC(current_remainder); 00932 } 00933 return current_remainder; 00934 } 00935 00936 template <class T> 00937 ON_ClassArray<T>::ON_ClassArray() 00938 : m_a(0), 00939 m_count(0), 00940 m_capacity(0) 00941 {} 00942 00943 template <class T> 00944 ON_ClassArray<T>::ON_ClassArray( int c ) 00945 : m_a(0), 00946 m_count(0), 00947 m_capacity(0) 00948 { 00949 if ( c > 0 ) 00950 SetCapacity( c ); 00951 } 00952 00953 // Copy constructor 00954 template <class T> 00955 ON_ClassArray<T>::ON_ClassArray( const ON_ClassArray<T>& src ) 00956 : m_a(0), 00957 m_count(0), 00958 m_capacity(0) 00959 { 00960 *this = src; // operator= defined below 00961 } 00962 00963 template <class T> 00964 ON_ClassArray<T>::~ON_ClassArray() 00965 { 00966 SetCapacity(0); 00967 } 00968 00969 template <class T> 00970 ON_ClassArray<T>& ON_ClassArray<T>::operator=( const ON_ClassArray<T>& src ) 00971 { 00972 int i; 00973 if( &src != this ) { 00974 if ( src.m_count <= 0 ) { 00975 m_count = 0; 00976 } 00977 else { 00978 if ( m_capacity < src.m_count ) { 00979 SetCapacity( src.m_count ); 00980 } 00981 if ( m_a ) { 00982 m_count = src.m_count; 00983 for ( i = 0; i < m_count; i++ ) { 00984 m_a[i] = src.m_a[i]; 00985 } 00986 } 00987 } 00988 } 00989 return *this; 00990 } 00991 00992 // emergency destroy /////////////////////////////////////////////////// 00993 00994 template <class T> 00995 void ON_ClassArray<T>::EmergencyDestroy(void) 00996 { 00997 m_count = 0; 00998 m_capacity = 0; 00999 m_a = 0; 01000 } 01001 01002 // query /////////////////////////////////////////////////////////////// 01003 01004 template <class T> 01005 int ON_ClassArray<T>::Count() const 01006 { 01007 return m_count; 01008 } 01009 01010 template <class T> 01011 unsigned int ON_ClassArray<T>::UnsignedCount() const 01012 { 01013 return ((unsigned int)m_count); 01014 } 01015 01016 template <class T> 01017 int ON_ClassArray<T>::Capacity() const 01018 { 01019 return m_capacity; 01020 } 01021 01022 template <class T> 01023 unsigned int ON_ClassArray<T>::SizeOfArray() const 01024 { 01025 return ((unsigned int)(m_capacity*sizeof(T))); 01026 } 01027 01028 template <class T> 01029 unsigned int ON_ClassArray<T>::SizeOfElement() const 01030 { 01031 return ((unsigned int)(sizeof(T))); 01032 } 01033 01034 template <class T> 01035 T& ON_ClassArray<T>::operator[]( int i ) 01036 { 01037 #if defined(ON_DEBUG) 01038 if ( i < 0 || i > m_capacity ) 01039 { 01040 ON_ERROR("ON_ClassArray[i]: i out of range."); 01041 } 01042 #endif 01043 return m_a[i]; 01044 } 01045 01046 01047 template <class T> 01048 T& ON_ClassArray<T>::operator[]( ON__INT64 i ) 01049 { 01050 #if defined(ON_DEBUG) 01051 if ( i < 0 || i > (ON__INT64)m_capacity ) 01052 { 01053 ON_ERROR("ON_ClassArray[i]: i out of range."); 01054 } 01055 #endif 01056 return m_a[i]; 01057 } 01058 01059 template <class T> 01060 T& ON_ClassArray<T>::operator[]( unsigned int i ) 01061 { 01062 #if defined(ON_DEBUG) 01063 if ( i > (unsigned int)m_capacity ) 01064 { 01065 ON_ERROR("ON_ClassArray[i]: i out of range."); 01066 } 01067 #endif 01068 return m_a[i]; 01069 } 01070 01071 template <class T> 01072 T& ON_ClassArray<T>::operator[]( ON__UINT64 i ) 01073 { 01074 #if defined(ON_DEBUG) 01075 if ( i > (ON__UINT64)m_capacity ) 01076 { 01077 ON_ERROR("ON_ClassArray[i]: i out of range."); 01078 } 01079 #endif 01080 return m_a[i]; 01081 } 01082 01083 template <class T> 01084 const T& ON_ClassArray<T>::operator[](int i) const 01085 { 01086 #if defined(ON_DEBUG) 01087 if ( i < 0 || i > m_capacity ) 01088 { 01089 ON_ERROR("ON_ClassArray[i]: i out of range."); 01090 } 01091 #endif 01092 return m_a[i]; 01093 } 01094 01095 template <class T> 01096 const T& ON_ClassArray<T>::operator[](ON__INT64 i) const 01097 { 01098 #if defined(ON_DEBUG) 01099 if ( i < 0 || i > (ON__INT64)m_capacity ) 01100 { 01101 ON_ERROR("ON_ClassArray[i]: i out of range."); 01102 } 01103 #endif 01104 return m_a[i]; 01105 } 01106 01107 template <class T> 01108 const T& ON_ClassArray<T>::operator[](unsigned int i) const 01109 { 01110 #if defined(ON_DEBUG) 01111 if ( i > (unsigned int)m_capacity ) 01112 { 01113 ON_ERROR("ON_ClassArray[i]: i out of range."); 01114 } 01115 #endif 01116 return m_a[i]; 01117 } 01118 01119 template <class T> 01120 const T& ON_ClassArray<T>::operator[](ON__UINT64 i) const 01121 { 01122 #if defined(ON_DEBUG) 01123 if ( i > (ON__UINT64)m_capacity ) 01124 { 01125 ON_ERROR("ON_ClassArray[i]: i out of range."); 01126 } 01127 #endif 01128 return m_a[i]; 01129 } 01130 01131 template <class T> 01132 ON_ClassArray<T>::operator T*() 01133 { 01134 return (m_count > 0) ? m_a : 0; 01135 } 01136 01137 template <class T> 01138 ON_ClassArray<T>::operator const T*() const 01139 { 01140 return (m_count > 0) ? m_a : 0; 01141 } 01142 01143 template <class T> 01144 T* ON_ClassArray<T>::Array() 01145 { 01146 return m_a; 01147 } 01148 01149 template <class T> 01150 const T* ON_ClassArray<T>::Array() const 01151 { 01152 return m_a; 01153 } 01154 01155 template <class T> 01156 T* ON_ClassArray<T>::KeepArray() 01157 { 01158 T* p = m_a; 01159 m_a = 0; 01160 m_count = 0; 01161 m_capacity = 0; 01162 return p; 01163 } 01164 01165 template <class T> 01166 void ON_ClassArray<T>::SetArray(T* p) 01167 { 01168 if ( m_a && m_a != p ) 01169 Destroy(); 01170 m_a = p; 01171 } 01172 01173 template <class T> 01174 void ON_ClassArray<T>::SetArray(T* p, int count, int capacity) 01175 { 01176 if ( m_a && m_a != p ) 01177 Destroy(); 01178 m_a = p; 01179 m_count = count; 01180 m_capacity = capacity; 01181 } 01182 01183 template <class T> 01184 T* ON_ClassArray<T>::First() 01185 { 01186 return (m_count > 0) ? m_a : 0; 01187 } 01188 01189 template <class T> 01190 const T* ON_ClassArray<T>::First() const 01191 { 01192 return (m_count > 0) ? m_a : 0; 01193 } 01194 01195 template <class T> 01196 T* ON_ClassArray<T>::At( int i ) 01197 { 01198 return (i >= 0 && i < m_count) ? m_a+i : 0; 01199 } 01200 01201 template <class T> 01202 T* ON_ClassArray<T>::At( unsigned int i ) 01203 { 01204 return (i < (unsigned int)m_count) ? m_a+i : 0; 01205 } 01206 01207 template <class T> 01208 const T* ON_ClassArray<T>::At( int i) const 01209 { 01210 return (i >= 0 && i < m_count) ? m_a+i : 0; 01211 } 01212 01213 template <class T> 01214 const T* ON_ClassArray<T>::At( unsigned int i) const 01215 { 01216 return (i < (unsigned int)m_count) ? m_a+i : 0; 01217 } 01218 01219 01220 template <class T> 01221 T* ON_ClassArray<T>::At( ON__INT64 i ) 01222 { 01223 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0; 01224 } 01225 01226 template <class T> 01227 T* ON_ClassArray<T>::At( ON__UINT64 i ) 01228 { 01229 return (i < (ON__UINT64)m_count) ? m_a+i : 0; 01230 } 01231 01232 template <class T> 01233 const T* ON_ClassArray<T>::At( ON__INT64 i) const 01234 { 01235 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0; 01236 } 01237 01238 template <class T> 01239 const T* ON_ClassArray<T>::At( ON__UINT64 i) const 01240 { 01241 return (i < (ON__UINT64)m_count) ? m_a+i : 0; 01242 } 01243 01244 01245 template <class T> 01246 T* ON_ClassArray<T>::Last() 01247 { 01248 return (m_count > 0) ? m_a+(m_count-1) : 0; 01249 } 01250 01251 template <class T> 01252 const T* ON_ClassArray<T>::Last() const 01253 { 01254 return (m_count > 0) ? m_a+(m_count-1) : 0; 01255 } 01256 01257 // array operations //////////////////////////////////////////////////// 01258 01259 template <class T> 01260 void ON_ClassArray<T>::Move( int dest_i, int src_i, int ele_cnt ) 01261 { 01262 // private function for moving blocks of array memory 01263 // caller is responsible for updating m_count and managing 01264 // destruction/creation. 01265 if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i || 01266 src_i + ele_cnt > m_count || dest_i > m_count ) 01267 return; 01268 01269 int capacity = dest_i + ele_cnt; 01270 if ( capacity > m_capacity ) { 01271 if ( capacity < 2*m_capacity ) 01272 capacity = 2*m_capacity; 01273 SetCapacity( capacity ); 01274 } 01275 01276 // This call to memmove is ok, even when T is a class with a vtable 01277 // because the it doesn't change the vtable for the class. 01278 // Classes that have back pointers, like ON_UserData, are 01279 // handled elsewhere and cannot be in ON_ClassArray<>s. 01280 memmove( (void*)(&m_a[dest_i]), (const void*)(&m_a[src_i]), ele_cnt*sizeof(T) ); 01281 } 01282 01283 template <class T> 01284 void ON_ClassArray<T>::ConstructDefaultElement(T* p) 01285 { 01286 // use placement ( new(size_t,void*) ) to construct 01287 // T in supplied memory 01288 new(p) T; 01289 } 01290 01291 template <class T> 01292 void ON_ClassArray<T>::DestroyElement(T& x) 01293 { 01294 x.~T(); 01295 } 01296 01297 template <class T> 01298 T& ON_ClassArray<T>::AppendNew() 01299 { 01300 if ( m_count == m_capacity ) 01301 { 01302 int newcapacity = NewCapacity(); 01303 Reserve( newcapacity ); 01304 } 01305 else 01306 { 01307 // First destroy what's there .. 01308 DestroyElement(m_a[m_count]); 01309 // and then get a properly initialized element 01310 ConstructDefaultElement(&m_a[m_count]); 01311 } 01312 return m_a[m_count++]; 01313 } 01314 01315 template <class T> 01316 void ON_ClassArray<T>::Append( const T& x ) 01317 { 01318 if ( m_count == m_capacity ) 01319 { 01320 const int newcapacity = NewCapacity(); 01321 if (m_a) 01322 { 01323 const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers 01324 if ( s >= 0 && s < m_capacity ) 01325 { 01326 // 26 Sep 2005 Dale Lear 01327 // User passed in an element of the m_a[] 01328 // that will get reallocated by the call 01329 // to Reserve(newcapacity). 01330 T temp; // ON_*Array<> templates do not require robust copy constructor. 01331 temp = x; // ON_*Array<> templates require a robust operator=. 01332 Reserve( newcapacity ); 01333 m_a[m_count++] = temp; 01334 return; 01335 } 01336 } 01337 Reserve(newcapacity); 01338 } 01339 m_a[m_count++] = x; 01340 } 01341 01342 template <class T> 01343 void ON_ClassArray<T>::Append( int count, const T* p ) 01344 { 01345 int i; 01346 if ( count > 0 && p ) 01347 { 01348 if ( count + m_count > m_capacity ) 01349 { 01350 int newcapacity = NewCapacity(); 01351 if ( newcapacity < count + m_count ) 01352 newcapacity = count + m_count; 01353 Reserve( newcapacity ); 01354 } 01355 for ( i = 0; i < count; i++ ) { 01356 m_a[m_count++] = p[i]; 01357 } 01358 } 01359 } 01360 01361 // Insert called with a reference uses operator = 01362 template <class T> 01363 void ON_ClassArray<T>::Insert( int i, const T& x ) 01364 { 01365 if( i >= 0 && i <= m_count ) 01366 { 01367 if ( m_count == m_capacity ) 01368 { 01369 int newcapacity = NewCapacity(); 01370 Reserve( newcapacity ); 01371 } 01372 DestroyElement( m_a[m_count] ); 01373 m_count++; 01374 if ( i < m_count-1 ) { 01375 Move( i+1, i, m_count-1-i ); 01376 // This call to memset is ok even when T has a vtable 01377 // because in-place construction is used later. 01378 memset( (void*)(&m_a[i]), 0, sizeof(T) ); 01379 ConstructDefaultElement( &m_a[i] ); 01380 } 01381 else { 01382 ConstructDefaultElement( &m_a[m_count-1] ); 01383 } 01384 m_a[i] = x; // uses T::operator=() to copy x to array 01385 } 01386 } 01387 01388 template <class T> 01389 void ON_ClassArray<T>::Remove( ) 01390 { 01391 Remove(m_count-1); 01392 } 01393 01394 template <class T> 01395 void ON_ClassArray<T>::Remove( int i ) 01396 { 01397 if ( i >= 0 && i < m_count ) 01398 { 01399 DestroyElement( m_a[i] ); 01400 // This call to memset is ok even when T has a vtable 01401 // because in-place construction is used later. 01402 memset( (void*)(&m_a[i]), 0, sizeof(T) ); 01403 Move( i, i+1, m_count-1-i ); 01404 // This call to memset is ok even when T has a vtable 01405 // because in-place construction is used later. 01406 memset( (void*)(&m_a[m_count-1]), 0, sizeof(T) ); 01407 ConstructDefaultElement(&m_a[m_count-1]); 01408 m_count--; 01409 } 01410 } 01411 01412 template <class T> 01413 void ON_ClassArray<T>::Empty() 01414 { 01415 int i; 01416 for ( i = m_count-1; i >= 0; i-- ) { 01417 DestroyElement( m_a[i] ); 01418 // This call to memset is ok even when T has a vtable 01419 // because in-place construction is used later. 01420 memset( (void*)(&m_a[i]), 0, sizeof(T) ); 01421 ConstructDefaultElement( &m_a[i] ); 01422 } 01423 m_count = 0; 01424 } 01425 01426 template <class T> 01427 void ON_ClassArray<T>::Reverse() 01428 { 01429 // NOTE: 01430 // If anything in "T" depends on the value of this's address, 01431 // then don't call Reverse(). 01432 char t[sizeof(T)]; 01433 int i = 0; 01434 int j = m_count-1; 01435 for ( /*empty*/; i < j; i++, j-- ) { 01436 memcpy( t, &m_a[i], sizeof(T) ); 01437 memcpy( &m_a[i], &m_a[j], sizeof(T) ); 01438 memcpy( &m_a[j], t, sizeof(T) ); 01439 } 01440 } 01441 01442 template <class T> 01443 void ON_ClassArray<T>::Swap( int i, int j ) 01444 { 01445 if ( i != j && i >= 0 && j >= 0 && i < m_count && j < m_count ) { 01446 char t[sizeof(T)]; 01447 memcpy( t, &m_a[i], sizeof(T) ); 01448 memcpy( &m_a[i], &m_a[j], sizeof(T) ); 01449 memcpy( &m_a[j], t, sizeof(T) ); 01450 } 01451 } 01452 01453 template <class T> 01454 int ON_ClassArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const 01455 { 01456 for ( int i = 0; i < m_count; i++ ) 01457 { 01458 if (!compar(key,m_a+i)) 01459 return i; 01460 } 01461 return -1; 01462 } 01463 01464 template <class T> 01465 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const 01466 { 01467 const T* found = (key&&m_a&&m_count>0) ? (const T*)bsearch( key, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ) : 0; 01468 #if defined(ON_COMPILER_MSC1300) 01469 // for 32 and 64 bit compilers - the (int) converts 64 bit size_t 01470 return found ? ((int)(found - m_a)) : -1; 01471 #else 01472 // for lamer 64 bit compilers 01473 return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1; 01474 #endif 01475 } 01476 01477 template <class T> 01478 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const 01479 { 01480 if ( count > m_count ) 01481 count = m_count; 01482 if ( count <= 0 ) 01483 return -1; 01484 const T* found = (key&&m_a&&m_count>0) ? (const T*)bsearch( key, m_a, count, sizeof(T), (int(*)(const void*,const void*))compar ) : 0; 01485 #if defined(ON_COMPILER_MSC1300) 01486 // for 32 and 64 bit compilers - the (int) converts 64 bit size_t 01487 return found ? ((int)(found - m_a)) : -1; 01488 #else 01489 // for lamer 64 bit compilers 01490 return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1; 01491 #endif 01492 } 01493 01494 template <class T> 01495 bool ON_ClassArray<T>::HeapSort( int (*compar)(const T*,const T*) ) 01496 { 01497 bool rc = false; 01498 if ( m_a && m_count > 0 && compar ) 01499 { 01500 if ( m_count > 1 ) 01501 ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 01502 rc = true; 01503 } 01504 return rc; 01505 } 01506 01507 template <class T> 01508 bool ON_ClassArray<T>::QuickSort( int (*compar)(const T*,const T*) ) 01509 { 01510 bool rc = false; 01511 if ( m_a && m_count > 0 && compar ) 01512 { 01513 if ( m_count > 1 ) 01514 ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 01515 rc = true; 01516 } 01517 return rc; 01518 } 01519 01520 01521 01522 template <class T> 01523 bool ON_ObjectArray<T>::HeapSort( int (*compar)(const T*,const T*) ) 01524 { 01525 bool rc = false; 01526 // The "this->" in this->m_count and this->m_a 01527 // are needed for gcc 4 to compile. 01528 if ( this->m_a && this->m_count > 0 && compar ) 01529 { 01530 if ( this->m_count > 1 ) 01531 { 01532 ON_hsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 01533 01534 // The MemoryRelocate step is required to synch userdata back pointers 01535 // so the user data destructor will work correctly. 01536 int i; 01537 for ( i = 0; i < this->m_count; i++ ) 01538 { 01539 this->m_a[i].MemoryRelocate(); 01540 } 01541 } 01542 rc = true; 01543 } 01544 return rc; 01545 } 01546 01547 template <class T> 01548 bool ON_ObjectArray<T>::QuickSort( int (*compar)(const T*,const T*) ) 01549 { 01550 bool rc = false; 01551 // The "this->" in this->m_count and this->m_a 01552 // are needed for gcc 4 to compile. 01553 if ( this->m_a && this->m_count > 0 && compar ) 01554 { 01555 if ( this->m_count > 1 ) 01556 { 01557 ON_qsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 01558 01559 // The MemoryRelocate step is required to synch userdata back pointers 01560 // so the user data destructor will work correctly. 01561 int i; 01562 for ( i = 0; i < this->m_count; i++ ) 01563 { 01564 this->m_a[i].MemoryRelocate(); 01565 } 01566 } 01567 rc = true; 01568 } 01569 return rc; 01570 } 01571 01572 01573 template <class T> 01574 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const 01575 { 01576 bool rc = false; 01577 if ( m_a && m_count > 0 && compar && index ) 01578 { 01579 if ( m_count > 1 ) 01580 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ); 01581 else if ( m_count == 1 ) 01582 index[0] = 0; 01583 rc = true; 01584 } 01585 return rc; 01586 } 01587 01588 template <class T> 01589 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const 01590 { 01591 bool rc = false; 01592 if ( m_a && m_count > 0 && compar && index ) 01593 { 01594 if ( m_count > 1 ) 01595 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p ); 01596 else if ( m_count == 1 ) 01597 index[0] = 0; 01598 rc = true; 01599 } 01600 return rc; 01601 } 01602 01603 template <class T> 01604 bool ON_ClassArray<T>::Permute( const int* index ) 01605 { 01606 bool rc = false; 01607 if ( m_a && m_count > 0 && index ) 01608 { 01609 int i; 01610 T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0])); 01611 memcpy( buffer, m_a, m_count*sizeof(T) ); 01612 for (i = 0; i < m_count; i++ ) 01613 memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator= 01614 onfree(buffer); 01615 rc = true; 01616 } 01617 return rc; 01618 } 01619 01620 template <class T> 01621 void ON_ClassArray<T>::Zero() 01622 { 01623 int i; 01624 if ( m_a && m_capacity > 0 ) { 01625 for ( i = m_capacity-1; i >= 0; i-- ) { 01626 DestroyElement(m_a[i]); 01627 // This call to memset is ok even when T has a vtable 01628 // because in-place construction is used later. 01629 memset( (void*)(&m_a[i]), 0, sizeof(T) ); 01630 ConstructDefaultElement(&m_a[i]); 01631 } 01632 } 01633 } 01634 01635 // memory managment //////////////////////////////////////////////////// 01636 01637 template <class T> 01638 void ON_ClassArray<T>::Reserve( int newcap ) 01639 { 01640 if( m_capacity < newcap ) 01641 SetCapacity( newcap ); 01642 } 01643 01644 template <class T> 01645 void ON_ClassArray<T>::Shrink() 01646 { 01647 SetCapacity( m_count ); 01648 } 01649 01650 template <class T> 01651 void ON_ClassArray<T>::Destroy() 01652 { 01653 SetCapacity( 0 ); 01654 } 01655 01656 // low level memory managment ////////////////////////////////////////// 01657 01658 template <class T> 01659 void ON_ClassArray<T>::SetCount( int count ) 01660 { 01661 if ( count >= 0 && count <= m_capacity ) 01662 m_count = count; 01663 } 01664 01665 template <class T> 01666 void ON_ClassArray<T>::SetCapacity( int capacity ) 01667 { 01668 // uses "placement" for class construction/destruction 01669 int i; 01670 if ( capacity < 1 ) { 01671 if ( m_a ) { 01672 for ( i = m_capacity-1; i >= 0; i-- ) { 01673 DestroyElement(m_a[i]); 01674 } 01675 Realloc(m_a,0); 01676 m_a = 0; 01677 } 01678 m_count = 0; 01679 m_capacity = 0; 01680 } 01681 else if ( m_capacity < capacity ) { 01682 // growing 01683 m_a = Realloc( m_a, capacity ); 01684 // initialize new elements with default constructor 01685 if ( 0 != m_a ) 01686 { 01687 // even when m_a is an array of classes with vtable pointers, 01688 // this call to memset(..., 0, ...) is what I want to do 01689 // because in-place construction will be used when needed 01690 // on this memory. 01691 memset( (void*)(m_a + m_capacity), 0, (capacity-m_capacity)*sizeof(T) ); 01692 for ( i = m_capacity; i < capacity; i++ ) { 01693 ConstructDefaultElement(&m_a[i]); 01694 } 01695 m_capacity = capacity; 01696 } 01697 else 01698 { 01699 // memory allocation failed 01700 m_capacity = 0; 01701 m_count = 0; 01702 } 01703 } 01704 else if ( m_capacity > capacity ) { 01705 // shrinking 01706 for ( i = m_capacity-1; i >= capacity; i-- ) { 01707 DestroyElement(m_a[i]); 01708 } 01709 if ( m_count > capacity ) 01710 m_count = capacity; 01711 m_capacity = capacity; 01712 m_a = Realloc( m_a, capacity ); 01713 if ( 0 == m_a ) 01714 { 01715 // memory allocation failed 01716 m_capacity = 0; 01717 m_count = 0; 01718 } 01719 } 01720 } 01721 01722 ///////////////////////////////////////////////////////////////////////////////////// 01723 ///////////////////////////////////////////////////////////////////////////////////// 01724 ///////////////////////////////////////////////////////////////////////////////////// 01725 01726 template< class T> 01727 static 01728 int ON_CompareIncreasing( const T* a, const T* b) 01729 { 01730 if( *a < *b ) 01731 return -1; 01732 if( *b < *a ) 01733 return 1; 01734 return 0; 01735 } 01736 01737 template< class T> 01738 static 01739 int ON_CompareDecreasing( const T* a, const T* b) 01740 { 01741 if( *b < *a ) 01742 return -1; 01743 if( *a < *b ) 01744 return 1; 01745 return 0; 01746 } 01747 01748 #if defined(ON_COMPILER_MSC) 01749 #pragma warning(pop) 01750 #endif 01751 01752 #endif