Point Cloud Library (PCL)  1.9.1-dev
opennurbs_array_defs.h
1 /* $NoKeywords: $ */
2 /*
3 //
4 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
5 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
6 // McNeel & Associates.
7 //
8 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
9 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
10 // MERCHANTABILITY ARE HEREBY DISCLAIMED.
11 //
12 // For complete openNURBS copyright information see <http://www.opennurbs.org>.
13 //
14 ////////////////////////////////////////////////////////////////
15 */
16 
17 #if !defined(ON_ARRAY_DEFS_INC_)
18 #define ON_ARRAY_DEFS_INC_
19 
20 #if defined(ON_COMPILER_MSC)
21 
22 // When this file is parsed with /W4 warnings, two bogus warnings
23 // are generated.
24 #pragma warning(push)
25 
26 // The ON_ClassArray<T>::DestroyElement template function generates a
27 // C4100: 'x' : unreferenced formal parameter
28 // warning.
29 // This appears to be caused by a bug in the compiler warning code
30 // or the way templates are expanded. This pragma is needed squelch the
31 // bogus warning.
32 #pragma warning(disable:4100)
33 
34 // The ON_CompareIncreasing and ON_CompareDecreasing templates generate a
35 // C4211: nonstandard extension used : redefined extern to static
36 // warning. Microsoft's compiler appears to have a little trouble
37 // when static functions are declared before they are defined in a
38 // single .cpp file. This pragma is needed squelch the bogus warning.
39 #pragma warning(disable:4211)
40 #endif
41 
42 // The main reason the definitions of the functions for the
43 // ON_SimpleArray and ON_ClassArray templates are in this separate
44 // file is so that the Microsoft developer studio autocomplete
45 // functions will work on these classes.
46 //
47 // This file is included by opennurbs_array.h in the appropriate
48 // spot. If you need the definitions in the file, then you
49 // should include opennurbs_array.h and let it take care of
50 // including this file.
51 
52 /////////////////////////////////////////////////////////////////////////////////////
53 // Class ON_SimpleArray<>
54 /////////////////////////////////////////////////////////////////////////////////////
55 
56 // construction ////////////////////////////////////////////////////////
57 
58 template <class T>
59 T* ON_SimpleArray<T>::Realloc(T* ptr,int capacity)
60 {
61  return (T*)onrealloc(ptr,capacity*sizeof(T));
62 }
63 
64 template <class T>
66  : m_a(0),
67  m_count(0),
68  m_capacity(0)
69 {}
70 
71 template <class T>
73  : m_a(0),
74  m_count(0),
75  m_capacity(0)
76 {
77  if ( c > 0 )
78  SetCapacity( c );
79 }
80 
81 // Copy constructor
82 template <class T>
84  : m_a(0),
85  m_count(0),
86  m_capacity(0)
87 {
88  *this = src; // operator= defined below
89 }
90 
91 template <class T>
93 {
94  SetCapacity(0);
95 }
96 
97 template <class T>
99 {
100  if( &src != this ) {
101  if ( src.m_count <= 0 ) {
102  m_count = 0;
103  }
104  else {
105  if ( m_capacity < src.m_count ) {
106  SetCapacity( src.m_count );
107  }
108  if ( m_a ) {
109  m_count = src.m_count;
110  memcpy( m_a, src.m_a, m_count*sizeof(T) );
111  }
112  }
113  }
114  return *this;
115 }
116 
117 // emergency destroy ///////////////////////////////////////////////////
118 
119 template <class T>
121 {
122  m_count = 0;
123  m_capacity = 0;
124  m_a = 0;
125 }
126 
127 // query ///////////////////////////////////////////////////////////////
128 
129 template <class T>
131 {
132  return m_count;
133 }
134 
135 template <class T>
137 {
138  return ((unsigned int)m_count);
139 }
140 
141 template <class T>
143 {
144  return m_capacity;
145 }
146 
147 template <class T>
148 unsigned int ON_SimpleArray<T>::SizeOfArray() const
149 {
150  return ((unsigned int)(m_capacity*sizeof(T)));
151 }
152 
153 template <class T>
155 {
156  return ((unsigned int)(sizeof(T)));
157 }
158 
159 
160 template <class T>
161 ON__UINT32 ON_SimpleArray<T>::DataCRC(ON__UINT32 current_remainder) const
162 {
163  return ON_CRC32(current_remainder,m_count*sizeof(m_a[0]),m_a);
164 }
165 
166 template <class T>
168 {
169 #if defined(ON_DEBUG)
170  if ( i < 0 || i > m_capacity )
171  {
172  ON_ERROR("ON_SimpleArray[i]: i out of range.");
173  }
174 #endif
175  return m_a[i];
176 }
177 
178 template <class T>
179 T& ON_SimpleArray<T>::operator[]( unsigned int i )
180 {
181 #if defined(ON_DEBUG)
182  if ( i > (unsigned int)m_capacity )
183  {
184  ON_ERROR("ON_SimpleArray[i]: i out of range.");
185  }
186 #endif
187  return m_a[i];
188 }
189 
190 
191 template <class T>
193 {
194 #if defined(ON_DEBUG)
195  if ( i < 0 || i > (ON__INT64)m_capacity )
196  {
197  ON_ERROR("ON_SimpleArray[i]: i out of range.");
198  }
199 #endif
200  return m_a[i];
201 }
202 
203 template <class T>
205 {
206 #if defined(ON_DEBUG)
207  if ( i > (ON__UINT64)m_capacity )
208  {
209  ON_ERROR("ON_SimpleArray[i]: i out of range.");
210  }
211 #endif
212  return m_a[i];
213 }
214 
215 template <class T>
216 const T& ON_SimpleArray<T>::operator[](int i) const
217 {
218 #if defined(ON_DEBUG)
219  if ( i < 0 || i > m_capacity )
220  {
221  ON_ERROR("ON_SimpleArray[i]: i out of range.");
222  }
223 #endif
224  return m_a[i];
225 }
226 
227 template <class T>
228 const T& ON_SimpleArray<T>::operator[](unsigned int i) const
229 {
230 #if defined(ON_DEBUG)
231  if ( i > (unsigned int)m_capacity )
232  {
233  ON_ERROR("ON_SimpleArray[i]: i out of range.");
234  }
235 #endif
236  return m_a[i];
237 }
238 
239 
240 template <class T>
241 const T& ON_SimpleArray<T>::operator[](ON__INT64 i) const
242 {
243 #if defined(ON_DEBUG)
244  if ( i < 0 || i > ((ON__INT64)m_capacity) )
245  {
246  ON_ERROR("ON_SimpleArray[i]: i out of range.");
247  }
248 #endif
249  return m_a[i];
250 }
251 
252 template <class T>
253 const T& ON_SimpleArray<T>::operator[](ON__UINT64 i) const
254 {
255 #if defined(ON_DEBUG)
256  if ( i > (ON__UINT64)m_capacity )
257  {
258  ON_ERROR("ON_SimpleArray[i]: i out of range.");
259  }
260 #endif
261  return m_a[i];
262 }
263 
264 
265 template <class T>
267 {
268  return (m_count > 0) ? m_a : 0;
269 }
270 
271 template <class T>
273 {
274  return (m_count > 0) ? m_a : 0;
275 }
276 
277 template <class T>
279 {
280  return m_a;
281 }
282 
283 template <class T>
284 const T* ON_SimpleArray<T>::Array() const
285 {
286  return m_a;
287 }
288 
289 template <class T>
291 {
292  T* p = m_a;
293  m_a = 0;
294  m_count = 0;
295  m_capacity = 0;
296  return p;
297 }
298 
299 template <class T>
301 {
302  if ( m_a && m_a != p )
303  onfree(m_a);
304  m_a = p;
305 }
306 
307 template <class T>
308 void ON_SimpleArray<T>::SetArray(T* p, int count, int capacity)
309 {
310  if ( m_a && m_a != p )
311  onfree(m_a);
312  m_a = p;
313  m_count = count;
314  m_capacity = capacity;
315 }
316 
317 template <class T>
319 {
320  return (m_count > 0) ? m_a : 0;
321 }
322 
323 template <class T>
324 const T* ON_SimpleArray<T>::First() const
325 {
326  return (m_count > 0) ? m_a : 0;
327 }
328 
329 template <class T>
331 {
332  return (i >= 0 && i < m_count) ? m_a+i : 0;
333 }
334 
335 template <class T>
336 T* ON_SimpleArray<T>::At( unsigned int i )
337 {
338  return (i < (unsigned int)m_count) ? m_a+i : 0;
339 }
340 
341 template <class T>
342 const T* ON_SimpleArray<T>::At( int i) const
343 {
344  return (i >= 0 && i < m_count) ? m_a+i : 0;
345 }
346 
347 template <class T>
348 const T* ON_SimpleArray<T>::At( unsigned int i) const
349 {
350  return (i < (unsigned int)m_count) ? m_a+i : 0;
351 }
352 
353 template <class T>
354 T* ON_SimpleArray<T>::At( ON__INT64 i )
355 {
356  return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
357 }
358 
359 template <class T>
360 T* ON_SimpleArray<T>::At( ON__UINT64 i )
361 {
362  return (i < (ON__UINT64)m_count) ? m_a+i : 0;
363 }
364 
365 template <class T>
366 const T* ON_SimpleArray<T>::At( ON__INT64 i) const
367 {
368  return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
369 }
370 
371 template <class T>
372 const T* ON_SimpleArray<T>::At( ON__UINT64 i) const
373 {
374  return (i < (ON__UINT64)m_count) ? m_a+i : 0;
375 }
376 
377 template <class T>
379 {
380  return (m_count > 0) ? m_a+(m_count-1) : 0;
381 }
382 
383 template <class T>
384 const T* ON_SimpleArray<T>::Last() const
385 {
386  return (m_count > 0) ? m_a+(m_count-1) : 0;
387 }
388 
389 // array operations ////////////////////////////////////////////////////
390 
391 template <class T>
392 void ON_SimpleArray<T>::Move( int dest_i, int src_i, int ele_cnt )
393 {
394  // private function for moving blocks of array memory
395  // caller is responsible for updating m_count.
396  if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i ||
397  src_i + ele_cnt > m_count || dest_i > m_count )
398  return;
399 
400  int capacity = dest_i + ele_cnt;
401  if ( capacity > m_capacity ) {
402  if ( capacity < 2*m_capacity )
403  capacity = 2*m_capacity;
404  SetCapacity( capacity );
405  }
406 
407  memmove( &m_a[dest_i], &m_a[src_i], ele_cnt*sizeof(T) );
408 }
409 
410 template <class T>
412 {
413  if ( m_count == m_capacity )
414  {
415  int new_capacity = NewCapacity();
416  Reserve( new_capacity );
417  }
418  memset( &m_a[m_count], 0, sizeof(T) );
419  return m_a[m_count++];
420 }
421 
422 template <class T>
423 void ON_SimpleArray<T>::Append( const T& x )
424 {
425  if ( m_count == m_capacity )
426  {
427  const int newcapacity = NewCapacity();
428  if (m_a)
429  {
430  const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers
431  if ( s >= 0 && s < m_capacity )
432  {
433  // 26 Sep 2005 Dale Lear
434  // User passed in an element of the m_a[]
435  // that will get reallocated by the call
436  // to Reserve(newcapacity).
437  T temp; // ON_*Array<> templates do not require robust copy constructor.
438  temp = x; // ON_*Array<> templates require a robust operator=.
439  Reserve( newcapacity );
440  m_a[m_count++] = temp;
441  return;
442  }
443  }
444  Reserve(newcapacity);
445  }
446  m_a[m_count++] = x;
447 }
448 
449 template <class T>
450 void ON_SimpleArray<T>::Append( int count, const T* p )
451 {
452  if ( count > 0 && p )
453  {
454  if ( count + m_count > m_capacity )
455  {
456  int newcapacity = NewCapacity();
457  if ( newcapacity < count + m_count )
458  newcapacity = count + m_count;
459  Reserve( newcapacity );
460  }
461  memcpy( m_a + m_count, p, count*sizeof(T) );
462  m_count += count;
463  }
464 }
465 
466 template <class T>
467 void ON_SimpleArray<T>::Insert( int i, const T& x )
468 {
469  if( i >= 0 && i <= m_count )
470  {
471  if ( m_count == m_capacity )
472  {
473  int newcapacity = NewCapacity();
474  Reserve( newcapacity );
475  }
476  m_count++;
477  Move( i+1, i, m_count-1-i );
478  m_a[i] = x;
479  }
480 }
481 
482 template <class T>
484 {
485  Remove(m_count-1);
486 }
487 
488 template <class T>
490 {
491  if ( i >= 0 && i < m_count ) {
492  Move( i, i+1, m_count-1-i );
493  m_count--;
494  memset( &m_a[m_count], 0, sizeof(T) );
495  }
496 }
497 
498 template <class T>
500 {
501  if ( m_a )
502  memset( m_a, 0, m_capacity*sizeof(T) );
503  m_count = 0;
504 }
505 
506 template <class T>
508 {
509  // NOTE:
510  // If anything in "T" depends on the value of this's address,
511  // then don't call Reverse().
512  T t;
513  int i = 0;
514  int j = m_count-1;
515  for ( /*empty*/; i < j; i++, j-- ) {
516  t = m_a[i];
517  m_a[i] = m_a[j];
518  m_a[j] = t;
519  }
520 }
521 
522 template <class T>
523 void ON_SimpleArray<T>::Swap( int i, int j )
524 {
525  if ( i != j ) {
526  const T t(m_a[i]);
527  m_a[i] = m_a[j];
528  m_a[j] = t;
529  }
530 }
531 
532 template <class T>
533 int ON_SimpleArray<T>::Search( const T& key ) const
534 {
535  const T* p = &key;
536  for ( int i = 0; i < m_count; i++ ) {
537  if (!memcmp(p,m_a+i,sizeof(T)))
538  return i;
539  }
540  return -1;
541 }
542 
543 template <class T>
544 int ON_SimpleArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const
545 {
546  for ( int i = 0; i < m_count; i++ ) {
547  if (!compar(key,m_a+i))
548  return i;
549  }
550  return -1;
551 }
552 
553 template <class T>
554 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const
555 {
556  const T* found = (key&&m_a&&m_count>0)
557  ? (const T*)bsearch( key, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar )
558  : 0;
559 
560  // This worked on a wide range of 32 bit compilers.
561 
562  int rc;
563  if ( 0 != found )
564  {
565  // Convert "found" pointer to array index.
566 
567 #if defined(ON_COMPILER_MSC1300)
568  rc = ((int)(found - m_a));
569 #elif 8 == ON_SIZEOF_POINTER
570  // In an ideal world, return ((int)(found - m_a)) would work everywhere.
571  // In practice, this should work any 64 bit compiler and we can hope
572  // the optimzer generates efficient code.
573  const ON__UINT64 fptr = (ON__UINT64)found;
574  const ON__UINT64 aptr = (ON__UINT64)m_a;
575  const ON__UINT64 sz = (ON__UINT64)sizeof(T);
576  const ON__UINT64 i = (fptr - aptr)/sz;
577  rc = (int)i;
578 #else
579  // In an ideal world, return ((int)(found - m_a)) would work everywhere.
580  // In practice, this should work any 32 bit compiler and we can hope
581  // the optimzer generates efficient code.
582  const ON__UINT32 fptr = (ON__UINT32)found;
583  const ON__UINT32 aptr = (ON__UINT32)m_a;
584  const ON__UINT32 sz = (ON__UINT32)sizeof(T);
585  const ON__UINT32 i = (fptr - aptr)/sz;
586  rc = (int)i;
587 #endif
588  }
589  else
590  {
591  // "key" not found
592  rc = -1;
593  }
594 
595  return rc;
596 
597 }
598 
599 template <class T>
600 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const
601 {
602  if ( count > m_count )
603  count = m_count;
604  if ( count <= 0 )
605  return -1;
606  const T* found = (key&&m_a&&m_count>0)
607  ? (const T*)bsearch( key, m_a, count, sizeof(T), (int(*)(const void*,const void*))compar )
608  : 0;
609 
610  // This worked on a wide range of 32 bit compilers.
611 
612  int rc;
613  if ( 0 != found )
614  {
615  // Convert "found" pointer to array index.
616 
617 #if defined(ON_COMPILER_MSC1300)
618  rc = ((int)(found - m_a));
619 #elif 8 == ON_SIZEOF_POINTER
620  // In an ideal world, return ((int)(found - m_a)) would work everywhere.
621  // In practice, this should work any 64 bit compiler and we can hope
622  // the optimzer generates efficient code.
623  const ON__UINT64 fptr = (ON__UINT64)found;
624  const ON__UINT64 aptr = (ON__UINT64)m_a;
625  const ON__UINT64 sz = (ON__UINT64)sizeof(T);
626  const ON__UINT64 i = (fptr - aptr)/sz;
627  rc = (int)i;
628 #else
629  // In an ideal world, return ((int)(found - m_a)) would work everywhere.
630  // In practice, this should work any 32 bit compiler and we can hope
631  // the optimzer generates efficient code.
632  const ON__UINT32 fptr = (ON__UINT32)found;
633  const ON__UINT32 aptr = (ON__UINT32)m_a;
634  const ON__UINT32 sz = (ON__UINT32)sizeof(T);
635  const ON__UINT32 i = (fptr - aptr)/sz;
636  rc = (int)i;
637 #endif
638  }
639  else
640  {
641  // "key" not found
642  rc = -1;
643  }
644  return rc;
645 }
646 
647 
648 
649 template <class T>
650 bool ON_SimpleArray<T>::HeapSort( int (*compar)(const T*,const T*) )
651 {
652  bool rc = false;
653  if ( m_a && m_count > 0 && compar ) {
654  if ( m_count > 1 )
655  ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
656  rc = true;
657  }
658  return rc;
659 }
660 
661 template <class T>
662 bool ON_SimpleArray<T>::QuickSort( int (*compar)(const T*,const T*) )
663 {
664  bool rc = false;
665  if ( m_a && m_count > 0 && compar ) {
666  if ( m_count > 1 )
667  ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
668  rc = true;
669  }
670  return rc;
671 }
672 
673 template <class T>
674 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const
675 {
676  bool rc = false;
677  if ( m_a && m_count > 0 && compar && index ) {
678  if ( m_count > 1 )
679  ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
680  else if ( m_count == 1 )
681  index[0] = 0;
682  rc = true;
683  }
684  return rc;
685 }
686 
687 template <class T>
688 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const
689 {
690  bool rc = false;
691  if ( m_a && m_count > 0 && compar && index ) {
692  if ( m_count > 1 )
693  ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p );
694  else if ( m_count == 1 )
695  index[0] = 0;
696  rc = true;
697  }
698  return rc;
699 }
700 
701 template <class T>
702 bool ON_SimpleArray<T>::Permute( const int* index )
703 {
704  bool rc = false;
705  if ( m_a && m_count > 0 && index ) {
706  int i;
707  T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0]));
708  memcpy( buffer, m_a, m_count*sizeof(T) );
709  for (i = 0; i < m_count; i++ )
710  memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator=
711  onfree(buffer);
712  rc = true;
713  }
714  return rc;
715 }
716 
717 template <class T>
719 {
720  if ( m_a && m_capacity > 0 ) {
721  memset( m_a, 0, m_capacity*sizeof(T) );
722  }
723 }
724 
725 template <class T>
726 void ON_SimpleArray<T>::MemSet( unsigned char value )
727 {
728  if ( m_a && m_capacity > 0 ) {
729  memset( m_a, value, m_capacity*sizeof(T) );
730  }
731 }
732 
733 // memory managment ////////////////////////////////////////////////////
734 
735 template <class T>
736 void ON_SimpleArray<T>::Reserve( int newcap )
737 {
738  if( m_capacity < newcap )
739  SetCapacity( newcap );
740 }
741 
742 template <class T>
744 {
745  SetCapacity( m_count );
746 }
747 
748 template <class T>
750 {
751  SetCapacity( 0 );
752 }
753 
754 // low level memory managment //////////////////////////////////////////
755 
756 template <class T>
757 void ON_SimpleArray<T>::SetCount( int count )
758 {
759  if ( count >= 0 && count <= m_capacity )
760  m_count = count;
761 }
762 
763 template <class T>
764 void ON_SimpleArray<T>::SetCapacity( int capacity )
765 {
766  // sets capacity to input value
767  if ( capacity != m_capacity ) {
768  if( capacity > 0 ) {
769  if ( m_count > capacity )
770  m_count = capacity;
771  // NOTE: Realloc() does an allocation if the first argument is NULL.
772  m_a = Realloc( m_a, capacity );
773  if ( m_a ) {
774  if ( capacity > m_capacity ) {
775  // zero new memory
776  memset( m_a + m_capacity, 0, (capacity-m_capacity)*sizeof(T) );
777  }
778  m_capacity = capacity;
779  }
780  else {
781  // out of memory
782  m_count = m_capacity = 0;
783  }
784  }
785  else if (m_a) {
786  Realloc(m_a,0);
787  m_a = 0;
788  m_count = m_capacity = 0;
789  }
790  }
791 }
792 
793 template <class T>
795 {
796  // Note:
797  // This code appears in ON_SimpleArray<T>::NewCapacity()
798  // and ON_ClassArray<T>::NewCapacity(). Changes made to
799  // either function should be made to both functions.
800  // Because this code is template code that has to
801  // support dynamic linking and the code is defined
802  // in a header, I'm using copy-and-paste rather
803  // than a static.
804 
805  // This function returns 2*m_count unless that will
806  // result in an additional allocation of more than
807  // cap_size bytes. The cap_size concept was added in
808  // January 2010 because some calculations on enormous
809  // models were slightly underestimating the initial
810  // Reserve() size and then wasting gigabytes of memory.
811 
812  // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os
813  const size_t cap_size = 32*sizeof(void*)*1024*1024;
814  if (m_count*sizeof(T) <= cap_size || m_count < 8)
815  return ((m_count <= 2) ? 4 : 2*m_count);
816 
817  // Growing the array will increase the memory
818  // use by more than cap_size.
819  int delta_count = 8 + cap_size/sizeof(T);
820  if ( delta_count > m_count )
821  delta_count = m_count;
822  return (m_count + delta_count);
823 }
824 
825 template <class T>
827 {
828  // Note:
829  // This code appears in ON_SimpleArray<T>::NewCapacity()
830  // and ON_ClassArray<T>::NewCapacity(). Changes made to
831  // either function should be made to both functions.
832  // Because this code is template code that has to
833  // support dynamic linking and the code is defined
834  // in a header, I'm using copy-and-paste rather
835  // than a static.
836 
837  // This function returns 2*m_count unless that will
838  // result in an additional allocation of more than
839  // cap_size bytes. The cap_size concept was added in
840  // January 2010 because some calculations on enormous
841  // models were slightly underestimating the initial
842  // Reserve() size and then wasting gigabytes of memory.
843 
844  // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os
845  const size_t cap_size = 32*sizeof(void*)*1024*1024;
846  if (m_count*sizeof(T) <= cap_size || m_count < 8)
847  return ((m_count <= 2) ? 4 : 2*m_count);
848 
849  // Growing the array will increase the memory
850  // use by more than cap_size.
851  int delta_count = 8 + cap_size/sizeof(T);
852  if ( delta_count > m_count )
853  delta_count = m_count;
854  return (m_count + delta_count);
855 }
856 
857 /////////////////////////////////////////////////////////////////////////////////////
858 // Class ON_ObjectArray<>
859 /////////////////////////////////////////////////////////////////////////////////////
860 
861 template <class T>
863 {
864 }
865 
866 template <class T>
868 {
869 }
870 
871 template <class T>
873 {
874 }
875 
876 template <class T>
878 {
879  if( this != &src)
880  {
882  }
883  return *this;
884 }
885 
886 
887 template <class T>
889  : ON_ClassArray<T>(c)
890 {
891 }
892 
893 template <class T>
894 T* ON_ObjectArray<T>::Realloc(T* ptr,int capacity)
895 {
896  T* reptr = (T*)onrealloc(ptr,capacity*sizeof(T));
897  if ( ptr && reptr && reptr != ptr )
898  {
899  // The "this->" in this->m_count and this->m_a
900  // are needed for gcc 4 to compile.
901  int i;
902  for ( i = 0; i < this->m_count; i++ )
903  {
904  reptr[i].MemoryRelocate();
905  }
906  }
907  return reptr;
908 }
909 
910 /////////////////////////////////////////////////////////////////////////////////////
911 // Class ON_ClassArray<>
912 /////////////////////////////////////////////////////////////////////////////////////
913 
914 
915 // construction ////////////////////////////////////////////////////////
916 
917 template <class T>
918 T* ON_ClassArray<T>::Realloc(T* ptr,int capacity)
919 {
920  return (T*)onrealloc(ptr,capacity*sizeof(T));
921 }
922 
923 template <class T>
924 ON__UINT32 ON_ObjectArray<T>::DataCRC(ON__UINT32 current_remainder) const
925 {
926  // The "this->" in this->m_count and this->m_a
927  // are needed for gcc 4 to compile.
928  int i;
929  for ( i = 0; i < this->m_count; i++ )
930  {
931  current_remainder = this->m_a[i].DataCRC(current_remainder);
932  }
933  return current_remainder;
934 }
935 
936 template <class T>
938  : m_a(0),
939  m_count(0),
940  m_capacity(0)
941 {}
942 
943 template <class T>
945  : m_a(0),
946  m_count(0),
947  m_capacity(0)
948 {
949  if ( c > 0 )
950  SetCapacity( c );
951 }
952 
953 // Copy constructor
954 template <class T>
956  : m_a(0),
957  m_count(0),
958  m_capacity(0)
959 {
960  *this = src; // operator= defined below
961 }
962 
963 template <class T>
965 {
966  SetCapacity(0);
967 }
968 
969 template <class T>
971 {
972  int i;
973  if( &src != this ) {
974  if ( src.m_count <= 0 ) {
975  m_count = 0;
976  }
977  else {
978  if ( m_capacity < src.m_count ) {
979  SetCapacity( src.m_count );
980  }
981  if ( m_a ) {
982  m_count = src.m_count;
983  for ( i = 0; i < m_count; i++ ) {
984  m_a[i] = src.m_a[i];
985  }
986  }
987  }
988  }
989  return *this;
990 }
991 
992 // emergency destroy ///////////////////////////////////////////////////
993 
994 template <class T>
996 {
997  m_count = 0;
998  m_capacity = 0;
999  m_a = 0;
1000 }
1001 
1002 // query ///////////////////////////////////////////////////////////////
1003 
1004 template <class T>
1006 {
1007  return m_count;
1008 }
1009 
1010 template <class T>
1012 {
1013  return ((unsigned int)m_count);
1014 }
1015 
1016 template <class T>
1018 {
1019  return m_capacity;
1020 }
1021 
1022 template <class T>
1023 unsigned int ON_ClassArray<T>::SizeOfArray() const
1024 {
1025  return ((unsigned int)(m_capacity*sizeof(T)));
1026 }
1027 
1028 template <class T>
1030 {
1031  return ((unsigned int)(sizeof(T)));
1032 }
1033 
1034 template <class T>
1036 {
1037 #if defined(ON_DEBUG)
1038  if ( i < 0 || i > m_capacity )
1039  {
1040  ON_ERROR("ON_ClassArray[i]: i out of range.");
1041  }
1042 #endif
1043  return m_a[i];
1044 }
1045 
1046 
1047 template <class T>
1049 {
1050 #if defined(ON_DEBUG)
1051  if ( i < 0 || i > (ON__INT64)m_capacity )
1052  {
1053  ON_ERROR("ON_ClassArray[i]: i out of range.");
1054  }
1055 #endif
1056  return m_a[i];
1057 }
1058 
1059 template <class T>
1060 T& ON_ClassArray<T>::operator[]( unsigned int i )
1061 {
1062 #if defined(ON_DEBUG)
1063  if ( i > (unsigned int)m_capacity )
1064  {
1065  ON_ERROR("ON_ClassArray[i]: i out of range.");
1066  }
1067 #endif
1068  return m_a[i];
1069 }
1070 
1071 template <class T>
1073 {
1074 #if defined(ON_DEBUG)
1075  if ( i > (ON__UINT64)m_capacity )
1076  {
1077  ON_ERROR("ON_ClassArray[i]: i out of range.");
1078  }
1079 #endif
1080  return m_a[i];
1081 }
1082 
1083 template <class T>
1084 const T& ON_ClassArray<T>::operator[](int i) const
1085 {
1086 #if defined(ON_DEBUG)
1087  if ( i < 0 || i > m_capacity )
1088  {
1089  ON_ERROR("ON_ClassArray[i]: i out of range.");
1090  }
1091 #endif
1092  return m_a[i];
1093 }
1094 
1095 template <class T>
1096 const T& ON_ClassArray<T>::operator[](ON__INT64 i) const
1097 {
1098 #if defined(ON_DEBUG)
1099  if ( i < 0 || i > (ON__INT64)m_capacity )
1100  {
1101  ON_ERROR("ON_ClassArray[i]: i out of range.");
1102  }
1103 #endif
1104  return m_a[i];
1105 }
1106 
1107 template <class T>
1108 const T& ON_ClassArray<T>::operator[](unsigned int i) const
1109 {
1110 #if defined(ON_DEBUG)
1111  if ( i > (unsigned int)m_capacity )
1112  {
1113  ON_ERROR("ON_ClassArray[i]: i out of range.");
1114  }
1115 #endif
1116  return m_a[i];
1117 }
1118 
1119 template <class T>
1120 const T& ON_ClassArray<T>::operator[](ON__UINT64 i) const
1121 {
1122 #if defined(ON_DEBUG)
1123  if ( i > (ON__UINT64)m_capacity )
1124  {
1125  ON_ERROR("ON_ClassArray[i]: i out of range.");
1126  }
1127 #endif
1128  return m_a[i];
1129 }
1130 
1131 template <class T>
1133 {
1134  return (m_count > 0) ? m_a : 0;
1135 }
1136 
1137 template <class T>
1139 {
1140  return (m_count > 0) ? m_a : 0;
1141 }
1142 
1143 template <class T>
1145 {
1146  return m_a;
1147 }
1148 
1149 template <class T>
1150 const T* ON_ClassArray<T>::Array() const
1151 {
1152  return m_a;
1153 }
1154 
1155 template <class T>
1157 {
1158  T* p = m_a;
1159  m_a = 0;
1160  m_count = 0;
1161  m_capacity = 0;
1162  return p;
1163 }
1164 
1165 template <class T>
1167 {
1168  if ( m_a && m_a != p )
1169  Destroy();
1170  m_a = p;
1171 }
1172 
1173 template <class T>
1174 void ON_ClassArray<T>::SetArray(T* p, int count, int capacity)
1175 {
1176  if ( m_a && m_a != p )
1177  Destroy();
1178  m_a = p;
1179  m_count = count;
1180  m_capacity = capacity;
1181 }
1182 
1183 template <class T>
1185 {
1186  return (m_count > 0) ? m_a : 0;
1187 }
1188 
1189 template <class T>
1190 const T* ON_ClassArray<T>::First() const
1191 {
1192  return (m_count > 0) ? m_a : 0;
1193 }
1194 
1195 template <class T>
1197 {
1198  return (i >= 0 && i < m_count) ? m_a+i : 0;
1199 }
1200 
1201 template <class T>
1202 T* ON_ClassArray<T>::At( unsigned int i )
1203 {
1204  return (i < (unsigned int)m_count) ? m_a+i : 0;
1205 }
1206 
1207 template <class T>
1208 const T* ON_ClassArray<T>::At( int i) const
1209 {
1210  return (i >= 0 && i < m_count) ? m_a+i : 0;
1211 }
1212 
1213 template <class T>
1214 const T* ON_ClassArray<T>::At( unsigned int i) const
1215 {
1216  return (i < (unsigned int)m_count) ? m_a+i : 0;
1217 }
1218 
1219 
1220 template <class T>
1221 T* ON_ClassArray<T>::At( ON__INT64 i )
1222 {
1223  return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
1224 }
1225 
1226 template <class T>
1227 T* ON_ClassArray<T>::At( ON__UINT64 i )
1228 {
1229  return (i < (ON__UINT64)m_count) ? m_a+i : 0;
1230 }
1231 
1232 template <class T>
1233 const T* ON_ClassArray<T>::At( ON__INT64 i) const
1234 {
1235  return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
1236 }
1237 
1238 template <class T>
1239 const T* ON_ClassArray<T>::At( ON__UINT64 i) const
1240 {
1241  return (i < (ON__UINT64)m_count) ? m_a+i : 0;
1242 }
1243 
1244 
1245 template <class T>
1247 {
1248  return (m_count > 0) ? m_a+(m_count-1) : 0;
1249 }
1250 
1251 template <class T>
1252 const T* ON_ClassArray<T>::Last() const
1253 {
1254  return (m_count > 0) ? m_a+(m_count-1) : 0;
1255 }
1256 
1257 // array operations ////////////////////////////////////////////////////
1258 
1259 template <class T>
1260 void ON_ClassArray<T>::Move( int dest_i, int src_i, int ele_cnt )
1261 {
1262  // private function for moving blocks of array memory
1263  // caller is responsible for updating m_count and managing
1264  // destruction/creation.
1265  if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i ||
1266  src_i + ele_cnt > m_count || dest_i > m_count )
1267  return;
1268 
1269  int capacity = dest_i + ele_cnt;
1270  if ( capacity > m_capacity ) {
1271  if ( capacity < 2*m_capacity )
1272  capacity = 2*m_capacity;
1273  SetCapacity( capacity );
1274  }
1275 
1276  // This call to memmove is ok, even when T is a class with a vtable
1277  // because the it doesn't change the vtable for the class.
1278  // Classes that have back pointers, like ON_UserData, are
1279  // handled elsewhere and cannot be in ON_ClassArray<>s.
1280  memmove( (void*)(&m_a[dest_i]), (const void*)(&m_a[src_i]), ele_cnt*sizeof(T) );
1281 }
1282 
1283 template <class T>
1285 {
1286  // use placement ( new(size_t,void*) ) to construct
1287  // T in supplied memory
1288  new(p) T;
1289 }
1290 
1291 template <class T>
1293 {
1294  x.~T();
1295 }
1296 
1297 template <class T>
1299 {
1300  if ( m_count == m_capacity )
1301  {
1302  int newcapacity = NewCapacity();
1303  Reserve( newcapacity );
1304  }
1305  else
1306  {
1307  // First destroy what's there ..
1309  // and then get a properly initialized element
1310  ConstructDefaultElement(&m_a[m_count]);
1311  }
1312  return m_a[m_count++];
1313 }
1314 
1315 template <class T>
1316 void ON_ClassArray<T>::Append( const T& x )
1317 {
1318  if ( m_count == m_capacity )
1319  {
1320  const int newcapacity = NewCapacity();
1321  if (m_a)
1322  {
1323  const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers
1324  if ( s >= 0 && s < m_capacity )
1325  {
1326  // 26 Sep 2005 Dale Lear
1327  // User passed in an element of the m_a[]
1328  // that will get reallocated by the call
1329  // to Reserve(newcapacity).
1330  T temp; // ON_*Array<> templates do not require robust copy constructor.
1331  temp = x; // ON_*Array<> templates require a robust operator=.
1332  Reserve( newcapacity );
1333  m_a[m_count++] = temp;
1334  return;
1335  }
1336  }
1337  Reserve(newcapacity);
1338  }
1339  m_a[m_count++] = x;
1340 }
1341 
1342 template <class T>
1343 void ON_ClassArray<T>::Append( int count, const T* p )
1344 {
1345  int i;
1346  if ( count > 0 && p )
1347  {
1348  if ( count + m_count > m_capacity )
1349  {
1350  int newcapacity = NewCapacity();
1351  if ( newcapacity < count + m_count )
1352  newcapacity = count + m_count;
1353  Reserve( newcapacity );
1354  }
1355  for ( i = 0; i < count; i++ ) {
1356  m_a[m_count++] = p[i];
1357  }
1358  }
1359 }
1360 
1361 // Insert called with a reference uses operator =
1362 template <class T>
1363 void ON_ClassArray<T>::Insert( int i, const T& x )
1364 {
1365  if( i >= 0 && i <= m_count )
1366  {
1367  if ( m_count == m_capacity )
1368  {
1369  int newcapacity = NewCapacity();
1370  Reserve( newcapacity );
1371  }
1373  m_count++;
1374  if ( i < m_count-1 ) {
1375  Move( i+1, i, m_count-1-i );
1376  // This call to memset is ok even when T has a vtable
1377  // because in-place construction is used later.
1378  memset( (void*)(&m_a[i]), 0, sizeof(T) );
1380  }
1381  else {
1382  ConstructDefaultElement( &m_a[m_count-1] );
1383  }
1384  m_a[i] = x; // uses T::operator=() to copy x to array
1385  }
1386 }
1387 
1388 template <class T>
1390 {
1391  Remove(m_count-1);
1392 }
1393 
1394 template <class T>
1396 {
1397  if ( i >= 0 && i < m_count )
1398  {
1399  DestroyElement( m_a[i] );
1400  // This call to memset is ok even when T has a vtable
1401  // because in-place construction is used later.
1402  memset( (void*)(&m_a[i]), 0, sizeof(T) );
1403  Move( i, i+1, m_count-1-i );
1404  // This call to memset is ok even when T has a vtable
1405  // because in-place construction is used later.
1406  memset( (void*)(&m_a[m_count-1]), 0, sizeof(T) );
1408  m_count--;
1409  }
1410 }
1411 
1412 template <class T>
1414 {
1415  int i;
1416  for ( i = m_count-1; i >= 0; i-- ) {
1417  DestroyElement( m_a[i] );
1418  // This call to memset is ok even when T has a vtable
1419  // because in-place construction is used later.
1420  memset( (void*)(&m_a[i]), 0, sizeof(T) );
1422  }
1423  m_count = 0;
1424 }
1425 
1426 template <class T>
1428 {
1429  // NOTE:
1430  // If anything in "T" depends on the value of this's address,
1431  // then don't call Reverse().
1432  char t[sizeof(T)];
1433  int i = 0;
1434  int j = m_count-1;
1435  for ( /*empty*/; i < j; i++, j-- ) {
1436  memcpy( t, &m_a[i], sizeof(T) );
1437  memcpy( &m_a[i], &m_a[j], sizeof(T) );
1438  memcpy( &m_a[j], t, sizeof(T) );
1439  }
1440 }
1441 
1442 template <class T>
1443 void ON_ClassArray<T>::Swap( int i, int j )
1444 {
1445  if ( i != j && i >= 0 && j >= 0 && i < m_count && j < m_count ) {
1446  char t[sizeof(T)];
1447  memcpy( t, &m_a[i], sizeof(T) );
1448  memcpy( &m_a[i], &m_a[j], sizeof(T) );
1449  memcpy( &m_a[j], t, sizeof(T) );
1450  }
1451 }
1452 
1453 template <class T>
1454 int ON_ClassArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const
1455 {
1456  for ( int i = 0; i < m_count; i++ )
1457  {
1458  if (!compar(key,m_a+i))
1459  return i;
1460  }
1461  return -1;
1462 }
1463 
1464 template <class T>
1465 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const
1466 {
1467  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;
1468 #if defined(ON_COMPILER_MSC1300)
1469  // for 32 and 64 bit compilers - the (int) converts 64 bit size_t
1470  return found ? ((int)(found - m_a)) : -1;
1471 #else
1472  // for lamer 64 bit compilers
1473  return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1;
1474 #endif
1475 }
1476 
1477 template <class T>
1478 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const
1479 {
1480  if ( count > m_count )
1481  count = m_count;
1482  if ( count <= 0 )
1483  return -1;
1484  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;
1485 #if defined(ON_COMPILER_MSC1300)
1486  // for 32 and 64 bit compilers - the (int) converts 64 bit size_t
1487  return found ? ((int)(found - m_a)) : -1;
1488 #else
1489  // for lamer 64 bit compilers
1490  return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1;
1491 #endif
1492 }
1493 
1494 template <class T>
1495 bool ON_ClassArray<T>::HeapSort( int (*compar)(const T*,const T*) )
1496 {
1497  bool rc = false;
1498  if ( m_a && m_count > 0 && compar )
1499  {
1500  if ( m_count > 1 )
1501  ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1502  rc = true;
1503  }
1504  return rc;
1505 }
1506 
1507 template <class T>
1508 bool ON_ClassArray<T>::QuickSort( int (*compar)(const T*,const T*) )
1509 {
1510  bool rc = false;
1511  if ( m_a && m_count > 0 && compar )
1512  {
1513  if ( m_count > 1 )
1514  ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1515  rc = true;
1516  }
1517  return rc;
1518 }
1519 
1520 
1521 
1522 template <class T>
1523 bool ON_ObjectArray<T>::HeapSort( int (*compar)(const T*,const T*) )
1524 {
1525  bool rc = false;
1526  // The "this->" in this->m_count and this->m_a
1527  // are needed for gcc 4 to compile.
1528  if ( this->m_a && this->m_count > 0 && compar )
1529  {
1530  if ( this->m_count > 1 )
1531  {
1532  ON_hsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1533 
1534  // The MemoryRelocate step is required to synch userdata back pointers
1535  // so the user data destructor will work correctly.
1536  int i;
1537  for ( i = 0; i < this->m_count; i++ )
1538  {
1539  this->m_a[i].MemoryRelocate();
1540  }
1541  }
1542  rc = true;
1543  }
1544  return rc;
1545 }
1546 
1547 template <class T>
1548 bool ON_ObjectArray<T>::QuickSort( int (*compar)(const T*,const T*) )
1549 {
1550  bool rc = false;
1551  // The "this->" in this->m_count and this->m_a
1552  // are needed for gcc 4 to compile.
1553  if ( this->m_a && this->m_count > 0 && compar )
1554  {
1555  if ( this->m_count > 1 )
1556  {
1557  ON_qsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1558 
1559  // The MemoryRelocate step is required to synch userdata back pointers
1560  // so the user data destructor will work correctly.
1561  int i;
1562  for ( i = 0; i < this->m_count; i++ )
1563  {
1564  this->m_a[i].MemoryRelocate();
1565  }
1566  }
1567  rc = true;
1568  }
1569  return rc;
1570 }
1571 
1572 
1573 template <class T>
1574 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const
1575 {
1576  bool rc = false;
1577  if ( m_a && m_count > 0 && compar && index )
1578  {
1579  if ( m_count > 1 )
1580  ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1581  else if ( m_count == 1 )
1582  index[0] = 0;
1583  rc = true;
1584  }
1585  return rc;
1586 }
1587 
1588 template <class T>
1589 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const
1590 {
1591  bool rc = false;
1592  if ( m_a && m_count > 0 && compar && index )
1593  {
1594  if ( m_count > 1 )
1595  ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p );
1596  else if ( m_count == 1 )
1597  index[0] = 0;
1598  rc = true;
1599  }
1600  return rc;
1601 }
1602 
1603 template <class T>
1604 bool ON_ClassArray<T>::Permute( const int* index )
1605 {
1606  bool rc = false;
1607  if ( m_a && m_count > 0 && index )
1608  {
1609  int i;
1610  T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0]));
1611  memcpy( buffer, m_a, m_count*sizeof(T) );
1612  for (i = 0; i < m_count; i++ )
1613  memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator=
1614  onfree(buffer);
1615  rc = true;
1616  }
1617  return rc;
1618 }
1619 
1620 template <class T>
1622 {
1623  int i;
1624  if ( m_a && m_capacity > 0 ) {
1625  for ( i = m_capacity-1; i >= 0; i-- ) {
1626  DestroyElement(m_a[i]);
1627  // This call to memset is ok even when T has a vtable
1628  // because in-place construction is used later.
1629  memset( (void*)(&m_a[i]), 0, sizeof(T) );
1631  }
1632  }
1633 }
1634 
1635 // memory managment ////////////////////////////////////////////////////
1636 
1637 template <class T>
1638 void ON_ClassArray<T>::Reserve( int newcap )
1639 {
1640  if( m_capacity < newcap )
1641  SetCapacity( newcap );
1642 }
1643 
1644 template <class T>
1646 {
1647  SetCapacity( m_count );
1648 }
1649 
1650 template <class T>
1652 {
1653  SetCapacity( 0 );
1654 }
1655 
1656 // low level memory managment //////////////////////////////////////////
1657 
1658 template <class T>
1659 void ON_ClassArray<T>::SetCount( int count )
1660 {
1661  if ( count >= 0 && count <= m_capacity )
1662  m_count = count;
1663 }
1664 
1665 template <class T>
1666 void ON_ClassArray<T>::SetCapacity( int capacity )
1667 {
1668  // uses "placement" for class construction/destruction
1669  int i;
1670  if ( capacity < 1 ) {
1671  if ( m_a ) {
1672  for ( i = m_capacity-1; i >= 0; i-- ) {
1673  DestroyElement(m_a[i]);
1674  }
1675  Realloc(m_a,0);
1676  m_a = 0;
1677  }
1678  m_count = 0;
1679  m_capacity = 0;
1680  }
1681  else if ( m_capacity < capacity ) {
1682  // growing
1683  m_a = Realloc( m_a, capacity );
1684  // initialize new elements with default constructor
1685  if ( 0 != m_a )
1686  {
1687  // even when m_a is an array of classes with vtable pointers,
1688  // this call to memset(..., 0, ...) is what I want to do
1689  // because in-place construction will be used when needed
1690  // on this memory.
1691  memset( (void*)(m_a + m_capacity), 0, (capacity-m_capacity)*sizeof(T) );
1692  for ( i = m_capacity; i < capacity; i++ ) {
1694  }
1695  m_capacity = capacity;
1696  }
1697  else
1698  {
1699  // memory allocation failed
1700  m_capacity = 0;
1701  m_count = 0;
1702  }
1703  }
1704  else if ( m_capacity > capacity ) {
1705  // shrinking
1706  for ( i = m_capacity-1; i >= capacity; i-- ) {
1707  DestroyElement(m_a[i]);
1708  }
1709  if ( m_count > capacity )
1710  m_count = capacity;
1711  m_capacity = capacity;
1712  m_a = Realloc( m_a, capacity );
1713  if ( 0 == m_a )
1714  {
1715  // memory allocation failed
1716  m_capacity = 0;
1717  m_count = 0;
1718  }
1719  }
1720 }
1721 
1722 /////////////////////////////////////////////////////////////////////////////////////
1723 /////////////////////////////////////////////////////////////////////////////////////
1724 /////////////////////////////////////////////////////////////////////////////////////
1725 
1726 template< class T>
1727 static
1728 int ON_CompareIncreasing( const T* a, const T* b)
1729 {
1730  if( *a < *b )
1731  return -1;
1732  if( *b < *a )
1733  return 1;
1734  return 0;
1735 }
1736 
1737 template< class T>
1738 static
1739 int ON_CompareDecreasing( const T* a, const T* b)
1740 {
1741  if( *b < *a )
1742  return -1;
1743  if( *a < *b )
1744  return 1;
1745  return 0;
1746 }
1747 
1748 #if defined(ON_COMPILER_MSC)
1749 #pragma warning(pop)
1750 #endif
1751 
1752 #endif
void EmergencyDestroy(void)
void Append(const T &)
void Move(int, int, int)
int NewCapacity() const
unsigned int SizeOfArray() const
virtual ON_SimpleArray< T > & operator=(const ON_SimpleArray< T > &)
void Swap(int, int)
bool Permute(const int *)
virtual bool QuickSort(int(*)(const T *, const T *))
int BinarySearch(const T *, int(*)(const T *, const T *)) const
void ConstructDefaultElement(T *)
int BinarySearch(const T *, int(*)(const T *, const T *)) const
int Search(const T &) const
virtual T * Realloc(T *, int)
void Move(int, int, int)
bool Sort(ON::sort_algorithm sort_algorithm, int *, int(*)(const T *, const T *)) const
T * Realloc(T *, int)
virtual bool HeapSort(int(*)(const T *, const T *))
void Insert(int, const T &)
void MemSet(unsigned char)
ON__UINT32 DataCRC(ON__UINT32 current_remainder) const
bool QuickSort(int(*)(const T *, const T *))
void Insert(int, const T &)
bool QuickSort(int(*)(const T *, const T *))
bool HeapSort(int(*)(const T *, const T *))
ON_ClassArray< T > & operator=(const ON_ClassArray< T > &)
bool Permute(const int *)
unsigned int UnsignedCount() const
void Append(const T &)
bool Sort(ON::sort_algorithm sort_algorithm, int *, int(*)(const T *, const T *)) const
void Swap(int, int)
ON__UINT32 DataCRC(ON__UINT32 current_remainder) const
virtual T * Realloc(T *, int)
unsigned int SizeOfElement() const
unsigned int SizeOfArray() const
unsigned int SizeOfElement() const
ON_ObjectArray< T > & operator=(const ON_ObjectArray< T > &)
void EmergencyDestroy(void)
bool HeapSort(int(*)(const T *, const T *))
int Search(const T *, int(*)(const T *, const T *)) const
unsigned int UnsignedCount() const