Point Cloud Library (PCL)  1.9.1-dev
opennurbs_array.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_INC_)
18 #define ON_ARRAY_INC_
19 
20 class ON_2dPointArray;
21 class ON_3dPointArray;
22 class ON_4dPointArray;
23 
24 class ON_2dVectorArray;
25 class ON_3dVectorArray;
26 
27 class ON_2fPointArray;
28 class ON_3fPointArray;
29 class ON_4fPointArray;
30 
31 class ON_2fVectorArray;
32 class ON_3fVectorArray;
33 
34 ////////////////////////////////////////////////////////////////
35 //
36 // The ON_SimpleArray<> template is more efficient than the
37 // ON_ClassArray<> template, but ON_SimpleArray<> should not
38 // be used for arrays of classes that require explicit
39 // construction, destruction, or copy operators.
40 //
41 // By default, ON_SimpleArray<> uses onrealloc() to manage
42 // the dynamic array memory. If you want to use something
43 // besides onrealloc() to manage the array memory, then override
44 // ON_SimpleArray::Realloc().
45 
46 template <class T> class ON_SimpleArray
47 {
48 public:
49  // construction ////////////////////////////////////////////////////////
50 
51  // These constructors create an array that uses onrealloc() to manage
52  // the array memory.
54  ON_SimpleArray( int ); // int = initial capacity
55 
56  // Copy constructor
58 
59  virtual
61 
62  // Assignment operator
63  virtual
65 
66  // emergency bailout ///////////////////////////////////////////////////
67  void EmergencyDestroy(void); // call only when memory used by this array
68  // may have become invalid for reasons beyond
69  // your control. EmergencyDestroy() zeros
70  // anything that could possibly cause
71  // ~ON_SimpleArray() to crash.
72 
73  // query ///////////////////////////////////////////////////////////////
74 
75  int Count() const; // number of elements in array
76  unsigned int UnsignedCount() const;
77 
78  int Capacity() const; // capacity of array
79 
80  unsigned int SizeOfArray() const; // amount of memory in the m_a[] array
81 
82  unsigned int SizeOfElement() const; // amount of memory in an m_a[] array element
83 
84  ON__UINT32 DataCRC(ON__UINT32 current_remainder) const;
85 
86  // The operator[] does to not check for valid indices.
87  // The caller is responsibile for insuring that 0 <= i < Capacity()
88  T& operator[]( int );
89  T& operator[]( unsigned int );
90  T& operator[]( ON__INT64 );
91  T& operator[]( ON__UINT64 );
92  const T& operator[]( int ) const;
93  const T& operator[]( unsigned int ) const;
94  const T& operator[]( ON__INT64 ) const;
95  const T& operator[]( ON__UINT64 ) const;
96 
97  operator T*(); // The cast operators return a pointer
98  operator const T*() const; // to the array. If Count() is zero,
99  // this pointer is NULL.
100 
101  T* First();
102  const T* First() const; // returns NULL if count = 0
103 
104  // At(index) returns NULL if index < 0 or index >= count
105  T* At( int );
106  T* At( unsigned int );
107  T* At( ON__INT64 );
108  T* At( ON__UINT64 );
109  const T* At( int ) const;
110  const T* At( unsigned int ) const;
111  const T* At( ON__INT64 ) const;
112  const T* At( ON__UINT64 ) const;
113 
114  T* Last();
115  const T* Last() const; // returns NULL if count = 0
116 
117 
118  // array operations ////////////////////////////////////////////////////
119 
120  T& AppendNew(); // Most efficient way to add a new element
121  // to the array. Increases count by 1.
122 
123  void Append( const T& ); // Append copy of element.
124  // Increments count by 1.
125 
126  void Append( int, const T* ); // Append copy of an array T[count]
127 
128 
129  void Insert( int, const T& ); // Insert copy of element. Uses
130  // memmove() to perform any
131  // necessary moving.
132  // Increases count by 1.
133 
134  void Remove(); // Removes last element. Decrements
135  // count by 1. Does not change capacity.
136 
137  virtual
138  void Remove( int ); // Removes element. Uses memmove() to
139  // perform any necessary shifting.
140  // Decrements count by 1. Does not change
141  // capacity
142 
143  void Empty(); // Sets count to 0, leaves capacity untouched.
144 
145  void Reverse(); // reverse order
146 
147  void Swap(int,int); // swap elements i and j
148 
149  //////////
150  // Search( e ) does a SLOW search of the array starting at array[0]
151  // and returns the index "i" of the first element that satisfies
152  // e == array[i]. (== is really memcmp()). If the search is not
153  // successful, then Search() returns -1. For Search(T) to work
154  // correctly, T must be a simple type. Use Search(p,compare())
155  // for Ts that are structs/classes that contain pointers. Search()
156  // is only suitable for performing infrequent searchs of small
157  // arrays. Sort the array and use BinarySearch() for performing
158  // efficient searches.
159  int Search( const T& ) const;
160 
161  //////////
162  // Search( p, compare ) does a SLOW search of the array starting
163  // at array[0] and returns the index "i" of the first element
164  // that satisfies compare(p,&array[i])==0. If the search is not
165  // successful, then Search() returns -1. Search() is only suitable
166  // for performing infrequent searches of small arrays. Sort the
167  // array and use BinarySearch() for performing efficient searches.
168  // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
169  int Search( const T*, int (*)(const T*,const T*) ) const;
170 
171  //////////
172  // BinarySearch( p, compare ) does a fast search of a sorted array
173  // and returns the smallest index "i" of the element that satisifies
174  // 0==compare(p,&array[i]).
175  //
176  // BinarySearch( p, compare, count ) does a fast search of the first
177  // count element sorted array and returns the smallest index "i" of
178  // the element that satisifies 0==compare(p,&array[i]). The version
179  // that takes a "count" is useful when elements are being appended
180  // during a calculation and the appended elements are not sorted.
181  //
182  // If the search is successful,
183  // BinarySearch() returns the index of the element (>=0).
184  // If the search is not successful, BinarySearch() returns -1.
185  // Use QuickSort( compare ) or, in rare cases and after meaningful
186  // performance testing using optimzed release builds,
187  // HeapSort( compare ) to sort the array.
188  // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
189  int BinarySearch( const T*, int (*)(const T*,const T*) ) const;
190  int BinarySearch( const T*, int (*)(const T*,const T*), int ) const;
191 
192  //////////
193  // Sorts the array using the heap sort algorithm.
194  // QuickSort() is generally the better choice.
195  bool HeapSort( int (*)(const T*,const T*) );
196 
197  //////////
198  // Sorts the array using the quick sort algorithm.
199  // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
200  bool QuickSort( int (*)(const T*,const T*) );
201 
202  /*
203  Description:
204  Sort() fills in the index[] array so that
205  array[index[i]] <= array[index[i+1]].
206  The array is not modified.
207 
208  Parameters:
209  sort_algorithm - [in]
210  ON::quick_sort (best in general) or ON::heap_sort
211  Use ON::heap_sort only if you have done extensive testing with
212  optimized release builds and are confident heap sort is
213  significantly faster.
214  index - [out] an array of length Count() that is returned with
215  some permutation of (0,1,...,Count()-1).
216  compare - [in] compare function compare(a,b,p) should return
217  <0 if a<b, 0, if a==b, and >0 if a>b.
218  Returns:
219  true if successful
220  */
221  bool Sort(
222  ON::sort_algorithm sort_algorithm,
223  int* /* index[] */ ,
224  int (*)(const T*,const T*)
225  ) const;
226 
227  /*
228  Description:
229  Sort() fills in the index[] array so that
230  array[index[i]] <= array[index[i+1]].
231  The array is not modified.
232 
233  Parameters:
234  sort_algorithm - [in]
235  ON::quick_sort (best in general) or ON::heap_sort
236  Use ON::heap_sort only if you have done extensive testing with
237  optimized release builds and are confident heap sort is
238  significantly faster.
239  index - [out] an array of length Count() that is returned with
240  some permutation of (0,1,...,Count()-1).
241  compare - [in] compare function compare(a,b,p) should return
242  <0 if a<b, 0, if a==b, and >0 if a>b.
243  p - [in] pointer passed as third argument to compare.
244 
245  Returns:
246  true if successful
247  */
248  bool Sort(
249  ON::sort_algorithm sort_algorithm,
250  int*, // index[]
251  int (*)(const T*,const T*,void*), // int compare(const T*,const T*,void* p)
252  void* // p
253  ) const;
254 
255  //////////
256  // Permutes the array so that output[i] = input[index[i]].
257  // The index[] array should be a permutation of (0,...,Count()-1).
258  bool Permute( const int* /*index[]*/ );
259 
260  //////////
261  // Zeros all array memory.
262  // Count and capacity are not changed.
263  void Zero();
264 
265  //////////
266  // Sets all bytes in array memory to value.
267  // Count and capacity are not changed.
268  void MemSet(unsigned char);
269 
270  // memory managment ////////////////////////////////////////////////////
271 
272  void Reserve( int ); // increase capacity to at least the requested value
273 
274  void Shrink(); // remove unused capacity
275 
276  void Destroy(); // onfree any memory and set count and capacity to zero
277 
278  // low level memory managment //////////////////////////////////////////
279 
280  // By default, ON_SimpleArray<> uses onrealloc() to manage
281  // the dynamic array memory. If you want to use something
282  // besides onrealloc() to manage the array memory, then override
283  // Realloc(). The T* Realloc(ptr, capacity) should do the following:
284  //
285  // 1) If ptr and capacity are zero, return NULL.
286  // 2) If ptr is NULL, an capacity > 0, allocate a memory block of
287  // capacity*sizeof(T) bytes and return a pointer to this block.
288  // If the allocation request fails, return NULL.
289  // 3) If ptr is not NULL and capacity is 0, free the memory block
290  // pointed to by ptr and return NULL.
291  // 4) If ptr is not NULL and capacity > 0, then reallocate the memory
292  // block and return a pointer to the reallocated block. If the
293  // reallocation request fails, return NULL.
294  //
295  // NOTE WELL:
296  // Microsoft's VC 6.0 realloc() contains a bug that can cause
297  // crashes and should be avoided. See MSDN Knowledge Base article
298  // ID Q225099 for more information.
299  virtual
300  T* Realloc(T*,int); // (re)allocated capacity*sizeof(T) bytes
301 
302  T* Array(); // The Array() function return the
303 
304  const T* Array() const; // m_a pointer value.
305 
306  void SetCount( int ); // If value is <= Capacity(), then
307  // sets count to specified value.
308 
309  void SetCapacity( int ); // Shrink/grows capacity. If value
310  // is < current Count(), then count
311  // is reduced to value.
312  //
313 
314  int NewCapacity() const; // When the dynamic array needs to grow,
315  // this calculates the new value for m_capacity.
316 
317  /*
318  Description:
319  Expert user tool to take charge of the memory used by
320  the dyanmic array.
321  Returns:
322  A pointer to the array and zeros out this class.
323  The returned pointer is on the heap and must be
324  deallocated by calling onfree().
325  */
326  T* KeepArray();
327 
328  /*
329  Description:
330  Do not use this version of SetArray(). Use the one that takes
331  a pointer, count and capacity.
332  */
333  void SetArray(T*);
334 
335  /*
336  Description:
337  Expert user tool to set the memory used by the dyanmic array.
338  Parameters:
339  T* pointer - [in]
340  int count [in]
341  int capacity - [in]
342  m_a is set to pointer, m_count is set to count, and m_capacity
343  is set to capacity. It is critical that the pointer be one
344  returned by onmalloc(sz), where sz >= capacity*sizeof(T[0]).
345  */
346  void SetArray(T*, int, int);
347 
348 protected:
349  // implimentation //////////////////////////////////////////////////////
350  void Move( int /* dest index*/, int /* src index */, int /* element count*/ );
351  T* m_a; // pointer to array memory
352  int m_count; // 0 <= m_count <= m_capacity
353  int m_capacity; // actual length of m_a[]
354 };
355 
356 
357 ////////////////////////////////////////////////////////////////
358 //
359 
360 #if defined(ON_DLL_TEMPLATE)
361 // This stuff is here because of a limitation in the way Microsoft
362 // handles templates and DLLs. See Microsoft's knowledge base
363 // article ID Q168958 for details.
364 #pragma warning( push )
365 #pragma warning( disable : 4231 )
366 
367 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool>;
368 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char>;
369 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char>;
370 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short>;
371 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short>;
372 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int>;
373 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int>;
374 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float>;
375 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double>;
376 
377 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool*>;
378 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char*>;
379 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char*>;
380 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short*>;
381 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short*>;
382 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int*>;
383 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int*>;
384 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float*>;
385 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double*>;
386 
387 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dPoint>;
388 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dPoint>;
389 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4dPoint>;
390 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dVector>;
391 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dVector>;
392 
393 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fPoint>;
394 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fPoint>;
395 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4fPoint>;
396 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fVector>;
397 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fVector>;
398 
399 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Color>;
400 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_SurfaceCurvature>;
401 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Interval>;
402 
403 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dex>;
404 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dex>;
405 
406 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_COMPONENT_INDEX>;
407 #pragma warning( pop )
408 #endif
409 
410 
411 /////////////////////////////////////////////////////////////////
412 //
413 
415 {
416 public:
417  // see ON_SimpleArray class definition comments for constructor documentation
418  ON_2dPointArray();
419  ON_2dPointArray(int);
422 
423  bool GetBBox( // returns true if successful
424  double boxmin[2],
425  double boxmax[2],
426  int bGrowBox = false // true means grow box
427  ) const;
428 
429  bool Transform( const ON_Xform& );
430  bool SwapCoordinates(int,int);
431 };
432 
433 
434 /////////////////////////////////////////////////////////////////
435 //
436 
438 {
439 public:
440  // see ON_SimpleArray class definition comments for constructor documentation
441  ON_2fPointArray();
442  ON_2fPointArray(int);
445 
446  bool GetBBox( // returns true if successful
447  float boxmin[2],
448  float boxmax[2],
449  int bGrowBox = false // true means grow box
450  ) const;
451  bool Transform( const ON_Xform& );
452  bool SwapCoordinates(int,int);
453 };
454 
455 
456 /////////////////////////////////////////////////////////////////
457 //
458 
460 {
461 public:
462  // see ON_SimpleArray class definition comments for constructor documentation
463  ON_3dPointArray();
464  ON_3dPointArray(int);
469 
470  // Description:
471  // Create 3d point list
472  // Parameters:
473  // point_dimension - [in] dimension of input points (2 or 3)
474  // bRational - [in] true if points are in homogenous rational form
475  // point_count - [in] number of points
476  // point_stride - [in] number of doubles to skip between points
477  // points - [in] array of point coordinates
478  bool Create(
479  int point_dimension,
480  int bRational,
481  int point_count,
482  int point_stride,
483  const double* points
484  );
485 
486  // Description:
487  // Create 3d point list
488  // Parameters:
489  // point_dimension - [in] dimension of input points (2 or 3)
490  // bRational - [in] true if points are in homogenous rational form
491  // point_count - [in] number of points
492  // point_stride - [in] number of doubles to skip between points
493  // points - [in] array of point coordinates
494  bool Create(
495  int point_dimension,
496  int bRational,
497  int point_count,
498  int point_stride,
499  const float* points
500  );
501 
502  // Description:
503  // Get 3d axis aligned bounding box.
504  // Returns:
505  // 3d bounding box of point list.
506  ON_BoundingBox BoundingBox() const;
507 
508  // Description:
509  // Get 3d axis aligned bounding box or the union
510  // of the input box with the point list's bounding box.
511  // Parameters:
512  // bbox - [in/out] 3d axis aligned bounding box
513  // bGrowBox - [in] (default=false)
514  // If true, then the union of the input bbox and the
515  // point list's bounding box is returned in bbox.
516  // If false, the point list's bounding box is returned in bbox.
517  // Returns:
518  // true if successful.
519  bool GetBoundingBox(
520  ON_BoundingBox& bbox,
521  int bGrowBox = false
522  ) const;
523 
524  // Description:
525  // Get axis aligned bounding box.
526  // Parameters:
527  // boxmin - [in/out] array of 3 doubles
528  // boxmax - [in/out] array of 3 doubles
529  // bGrowBox - [in] (default=false)
530  // If true, then the union of the input bounding box and the
531  // object's bounding box is returned.
532  // If false, the object's bounding box is returned.
533  // Returns:
534  // true if object has bounding box and calculation was successful
535  bool GetBBox(
536  double boxmin[3],
537  double boxmax[3],
538  int bGrowBox = false
539  ) const;
540 
541  /*
542  Description:
543  Get tight bounding box of the point list.
544  Parameters:
545  tight_bbox - [in/out] tight bounding box
546  bGrowBox -[in] (default=false)
547  If true and the input tight_bbox is valid, then returned
548  tight_bbox is the union of the input tight_bbox and the
549  tight bounding box of the point list.
550  xform -[in] (default=NULL)
551  If not NULL, the tight bounding box of the transformed
552  point list is calculated. The point list is not modified.
553  Returns:
554  True if the returned tight_bbox is set to a valid
555  bounding box.
556  */
557  bool GetTightBoundingBox(
558  ON_BoundingBox& tight_bbox,
559  int bGrowBox = false,
560  const ON_Xform* xform = 0
561  ) const;
562 
563  // Description:
564  // Transform points by applying xform to each point.
565  // Parameters:
566  // xform - [in] transformation matrix
567  // Returns:
568  // true if successful.
569  bool Transform(
570  const ON_Xform& xform
571  );
572 
573  // Description:
574  // Swaps point coordinate values with indices i and j.
575  // Parameters:
576  // i - [in] coordinate index
577  // j - [in] coordinate index
578  // Returns:
579  // true if successful.
580  // Example:
581  // The call SwapCoordinates(0,2) would swap the x and z
582  // coordinates of each point in the array.
583  bool SwapCoordinates(
584  int i,
585  int j
586  );
587 
588  // Description:
589  // Rotate points about a center and axis. A positive angle
590  // results in a counter-clockwise rotation about the axis
591  // of rotation.
592  // Parameters:
593  // sin_angle - [in] sine of rotation angle
594  // cos_angle - [in] cosine of rotation angle
595  // axis_of_rotation - [in] axis of rotation
596  // center_of_rotation - [in] center (fixed point) of rotation
597  // Returns:
598  // true if successful.
599  bool Rotate(
600  double sin_angle,
601  double cos_angle,
602  const ON_3dVector& axis_of_rotation,
603  const ON_3dPoint& center_of_rotation
604  );
605 
606  // Description:
607  // Rotate points about a center and axis. A positive angle
608  // results in a counter-clockwise rotation about the axis
609  // of rotation.
610  // Parameters:
611  // angle - [in] angle in radians. Polsine of rotation angle
612  // cos_angle - [in] cosine of rotation angle
613  // axis_of_rotation - [in] axis of rotation
614  // center_of_rotation - [in] center (fixed point) of rotation
615  // Returns:
616  // true if successful.
617  bool Rotate(
618  double angle_in_radians,
619  const ON_3dVector& axis_of_rotation,
620  const ON_3dPoint& center_of_rotation
621  );
622 
623  // Description:
624  // Translate a polyline
625  // Parameters:
626  // delta - [in] translation vectorsine of rotation angle
627  // Returns:
628  // true if successful.
629  bool Translate(
630  const ON_3dVector& delta
631  );
632 
633  /*
634  Description:
635  Get the index of the point in the array that is closest
636  to P.
637  Parameters:
638  P - [in]
639  closest_point_index - [out]
640  maximum_distance - [in] optional distance constraint.
641  If maximum_distance > 0, then only points Q with
642  |P-Q| <= maximum_distance are returned.
643  Returns:
644  True if a point is found; in which case *closest_point_index
645  is the index of the point. False if no point is found
646  or the input is not valid.
647  See Also:
648  ON_GetClosestPointInPointList
649  ON_PointCloud::GetClosestPoint
650  */
651  bool GetClosestPoint(
652  ON_3dPoint P,
653  int* closest_point_index,
654  double maximum_distance = 0.0
655  ) const;
656 
657 };
658 
659 
660 /////////////////////////////////////////////////////////////////
661 //
662 
664 {
665 public:
666  // see ON_SimpleArray class definition comments for constructor documentation
667  ON_3fPointArray();
668  ON_3fPointArray(int);
671 
672  bool GetBBox(
673  float boxmin[3],
674  float boxmax[3],
675  int bGrowBox = false
676  ) const;
677 
678  bool Transform( const ON_Xform& );
679 
680  bool SwapCoordinates(int,int);
681 };
682 
683 
684 /////////////////////////////////////////////////////////////////
685 //
686 
688 {
689 public:
690  // see ON_SimpleArray class definition comments for constructor documentation
691  ON_4dPointArray();
692  ON_4dPointArray(int);
695 
696  bool Transform( const ON_Xform& );
697  bool SwapCoordinates(int,int);
698 };
699 
700 
701 /////////////////////////////////////////////////////////////////
702 //
703 
705 {
706 public:
707  // see ON_SimpleArray class definition comments for constructor documentation
708  ON_4fPointArray();
709  ON_4fPointArray(int);
712 
713  bool Transform( const ON_Xform& );
714  bool SwapCoordinates(int,int);
715 };
716 
717 
718 /////////////////////////////////////////////////////////////////
719 //
720 
722 {
723 public:
724  // see ON_SimpleArray class definition comments for constructor documentation
726  ON_2dVectorArray(int);
729 
730  bool GetBBox(
731  double boxmin[2],
732  double boxmax[2],
733  int bGrowBox = false
734  ) const;
735 
736  bool Transform( const ON_Xform& );
737  bool SwapCoordinates(int,int);
738 };
739 
740 
741 /////////////////////////////////////////////////////////////////
742 //
743 
745 {
746 public:
747  // see ON_SimpleArray class definition comments for constructor documentation
749  ON_2fVectorArray(int);
752 
753  bool GetBBox(
754  float boxmin[2],
755  float boxmax[2],
756  bool = false
757  ) const;
758 
759  bool Transform( const ON_Xform& );
760  bool SwapCoordinates(int,int);
761 };
762 
763 
764 /////////////////////////////////////////////////////////////////
765 //
766 
768 {
769 public:
771  ON_3dVectorArray(int);
774 
775  bool GetBBox(
776  double boxmin[3],
777  double boxmax[3],
778  bool bGrowBow = false
779  ) const;
780 
781  bool Transform( const ON_Xform& );
782  bool SwapCoordinates(int,int);
783 };
784 
785 /////////////////////////////////////////////////////////////////
786 //
787 
789 {
790 public:
792  ON_3fVectorArray(int);
795 
796  bool GetBBox(
797  float boxmin[3],
798  float boxmax[3],
799  int bGrowBox = false
800  ) const;
801 
802  bool Transform( const ON_Xform& );
803  bool SwapCoordinates(int,int);
804 };
805 
806 ////////////////////////////////////////////////////////////////
807 //
808 // The ON_ClassArray<> template is designed to be used with
809 // classes that require non-trivial construction or destruction.
810 // Any class used with the ON_ClassArray<> template must have a
811 // robust operator=().
812 //
813 // By default, ON_ClassArray<> uses onrealloc() to manage
814 // the dynamic array memory. If you want to use something
815 // besides onrealloc() to manage the array memory, then override
816 // ON_ClassArray::Realloc(). In practice this means that if your
817 // class has members with back-pointers, then you cannot use
818 // it in the defaule ON_ClassArray. See ON_ObjectArray
819 // for an example.
820 //
821 template <class T> class ON_ClassArray
822 {
823 public:
824  // construction ////////////////////////////////////////////////////////
825  ON_ClassArray();
826  ON_ClassArray( int ); // int = initial capacity
827 
828  // Copy constructor
830 
831  virtual
832  ~ON_ClassArray(); // override for struct member deallocation, etc.
833 
834  // Assignment operator
836 
837  // emergency bailout ///////////////////////////////////////////////////
838  void EmergencyDestroy(void); // call only when memory used by this array
839  // may have become invalid for reasons beyond
840  // your control. EmergencyDestroy() zeros
841  // anything that could possibly cause
842  // ~ON_ClassArray() to crash.
843 
844  // query ///////////////////////////////////////////////////////////////
845 
846  int Count() const; // number of elements in array
847  unsigned int UnsignedCount() const;
848 
849  int Capacity() const; // capacity of array
850 
851  unsigned int SizeOfArray() const; // amount of memory in the m_a[] array
852 
853  unsigned int SizeOfElement() const; // amount of memory in an m_a[] array element
854 
855  // The operator[] does to not check for valid indices.
856  // The caller is responsibile for insuring that 0 <= i < Capacity()
857  T& operator[]( int );
858  T& operator[]( unsigned int );
859  T& operator[]( ON__INT64 );
860  T& operator[]( ON__UINT64 );
861  const T& operator[]( int ) const;
862  const T& operator[]( unsigned int ) const;
863  const T& operator[]( ON__INT64 ) const;
864  const T& operator[]( ON__UINT64 ) const;
865 
866  operator T*(); // The cast operators return a pointer
867  operator const T*() const; // to the array. If Count() is zero,
868  // this pointer is NULL.
869  T* First();
870  const T* First() const; // returns NULL if count = 0
871 
872  // At(index) returns NULL if index < 0 or index >= count
873  T* At( int );
874  T* At( unsigned int );
875  T* At( ON__INT64 );
876  T* At( ON__UINT64 );
877  const T* At( int ) const;
878  const T* At( unsigned int ) const;
879  const T* At( ON__INT64 ) const;
880  const T* At( ON__UINT64 ) const;
881 
882  T* Last();
883  const T* Last() const; // returns NULL if count = 0
884 
885 
886  // array operations ////////////////////////////////////////////////////
887 
888  T& AppendNew(); // Most efficient way to add a new class
889  // to the array. Increases count by 1.
890 
891  void Append( const T& ); // Append copy of element.
892  // Increments count by 1.
893 
894  void Append( int, const T*); // Append copy of an array T[count]
895 
896  void Insert( int, const T& ); // Insert copy of element. Uses
897  // memmove() to perform any
898  // necessary moving.
899  // Increases count by 1.
900 
901  void Remove(); // Removes last element. Decrements
902  // count by 1. Does not change capacity.
903 
904  void Remove( int ); // Removes element. Uses memmove() to
905  // perform any necessary shifting.
906  // Decrements count by 1. Does not change
907  // capacity
908 
909  void Empty(); // Sets count to 0, leaves capacity untouched.
910 
911  void Reverse(); // reverse order
912 
913  void Swap(int,int); // swap elements i and j
914 
915  //////////
916  // Search( p, compare ) does a SLOW search of the array starting
917  // at array[0] and returns the index "i" of the first element
918  // that satisfies compare(p,&array[i])==0. If the search is not
919  // successful, then Search() returns -1. Search() is only suitable
920  // for performing infrequent searches of small arrays. Sort the
921  // array and use BinarySearch() for performing efficient searches.
922  int Search( const T*, int (*)(const T*,const T*) ) const;
923 
924  //////////
925  // BinarySearch( p, compare ) does a fast search of a sorted array
926  // and returns the smallest index "i" of the element that satisifies
927  // 0==compare(p,&array[i]).
928  //
929  // BinarySearch( p, compare, count ) does a fast search of the first
930  // count element sorted array and returns the smallest index "i" of
931  // the element that satisifies 0==compare(p,&array[i]). The version
932  // that takes a "count" is useful when elements are being appended
933  // during a calculation and the appended elements are not sorted.
934  //
935  // If the search is successful,
936  // BinarySearch() returns the index of the element (>=0).
937  // If the search is not successful, BinarySearch() returns -1.
938  // Use QuickSort( compare ) or, in rare cases and after meaningful
939  // performance testing using optimzed release builds,
940  // HeapSort( compare ) to sort the array.
941  // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
942  int BinarySearch( const T*, int (*)(const T*,const T*) ) const;
943  int BinarySearch( const T*, int (*)(const T*,const T*), int ) const;
944 
945  //////////
946  // Sorts the array using the heap sort algorithm.
947  // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
948  // QuickSort() is generally the better choice.
949  virtual
950  bool HeapSort( int (*)(const T*,const T*) );
951 
952  //////////
953  // Sorts the array using the heap sort algorithm.
954  virtual
955  bool QuickSort( int (*)(const T*,const T*) );
956 
957  /*
958  Description:
959  Sort() fills in the index[] array so that
960  array[index[i]] <= array[index[i+1]].
961  The array is not modified.
962 
963  Parameters:
964  sort_algorithm - [in]
965  ON::quick_sort (best in general) or ON::heap_sort
966  Use ON::heap_sort only if you have done extensive testing with
967  optimized release builds and are confident heap sort is
968  significantly faster.
969  index - [out] an array of length Count() that is returned with
970  some permutation of (0,1,...,Count()-1).
971  compare - [in] compare function compare(a,b) should return
972  <0 if a<b, 0, if a==b, and >0 if a>b.
973 
974  Returns:
975  true if successful
976  */
977  bool Sort(
978  ON::sort_algorithm sort_algorithm,
979  int* /* index[] */ ,
980  int (*)(const T*,const T*)
981  ) const;
982 
983  /*
984  Description:
985  Sort() fills in the index[] array so that
986  array[index[i]] <= array[index[i+1]].
987  The array is not modified.
988 
989  Parameters:
990  sort_algorithm - [in]
991  ON::quick_sort (best in general) or ON::heap_sort
992  Use ON::heap_sort only if you have done extensive testing with
993  optimized release builds and are confident heap sort is
994  significantly faster.
995  index - [out] an array of length Count() that is returned with
996  some permutation of (0,1,...,Count()-1).
997  compare - [in] compare function compare(a,b,p) should return
998  <0 if a<b, 0, if a==b, and >0 if a>b.
999  p - [in] pointer passed as third argument to compare.
1000 
1001  Returns:
1002  true if successful
1003  */
1004  bool Sort(
1005  ON::sort_algorithm sort_algorithm,
1006  int*, // index[]
1007  int (*)(const T*,const T*,void*), // int compare(const T*,const T*,void* p)
1008  void* // p
1009  ) const;
1010 
1011  //////////
1012  // Permutes the array so that output[i] = input[index[i]].
1013  // The index[] array should be a permutation of (0,...,Count()-1).
1014  bool Permute( const int* /*index[]*/ );
1015 
1016  //////////
1017  // Destroys all elements and fills them with values
1018  // set by the defualt constructor.
1019  // Count and capacity are not changed.
1020  void Zero();
1021 
1022  // memory managment /////////////////////////////////////////////////
1023 
1024  void Reserve( int ); // increase capacity to at least the requested value
1025 
1026  void Shrink(); // remove unused capacity
1027 
1028  void Destroy(); // onfree any memory and set count and capacity to zero
1029 
1030  // low level memory managment ///////////////////////////////////////
1031 
1032  // By default, ON_ClassArray<> uses onrealloc() to manage
1033  // the dynamic array memory. If you want to use something
1034  // besides onrealloc() to manage the array memory, then override
1035  // Realloc(). The T* Realloc(ptr, capacity) should do the following:
1036  //
1037  // 1) If ptr and capacity are zero, return NULL.
1038  // 2) If ptr is NULL, an capacity > 0, allocate a memory block of
1039  // capacity*sizeof(T) bytes and return a pointer to this block.
1040  // If the allocation request fails, return NULL.
1041  // 3) If ptr is not NULL and capacity is 0, free the memory block
1042  // pointed to by ptr and return NULL.
1043  // 4) If ptr is not NULL and capacity > 0, then reallocate the memory
1044  // block and return a pointer to the reallocated block. If the
1045  // reallocation request fails, return NULL.
1046  //
1047  // NOTE WELL:
1048  // Microsoft's VC 6.0 realloc() contains a bug that can cause
1049  // crashes and should be avoided. See MSDN Knowledge Base article
1050  // ID Q225099 for more information.
1051  virtual
1052  T* Realloc(T*,int); // (re)allocated capacity*sizeof(T) bytes
1053 
1054  T* Array(); // The Array() function return the
1055 
1056  const T* Array() const; // m_a pointer value.
1057 
1058  void SetCount( int ); // If value is <= Capacity(), then
1059  // sets count to specified value.
1060 
1061  void SetCapacity( int ); // Shrink/grows capacity. If value
1062  // is < current Count(), then count
1063  // is reduced to value.
1064 
1065  int NewCapacity() const; // When the dynamic array needs to grow,
1066  // this calculates the new value for m_capacity.
1067 
1068  T* KeepArray(); // returns pointer to array and zeros
1069  // out this class. Caller is responsible
1070  // for calling destructor on each element
1071  // and then using onfree() to release array
1072  // memory. E.g.,
1073  //
1074  // for (int i=capacity;i>=0;i--) {
1075  // array[i].~T();
1076  // }
1077  // onfree(array);
1078 
1079  /*
1080  Description:
1081  Do not use this version of SetArray(). Use the one that takes
1082  a pointer, count and capacity: SetArray(pointer,count,capacity)
1083  */
1084  void SetArray(T*);
1085 
1086  /*
1087  Description:
1088  Expert user tool to set the memory used by the dyanmic array.
1089  Parameters:
1090  T* pointer - [in]
1091  int count - [in] 0 <= count <= capacity
1092  int capacity - [in]
1093  m_a is set to pointer, m_count is set to count, and m_capacity
1094  is set to capacity. It is critical that the pointer be one
1095  returned by onmalloc(sz), where sz >= capacity*sizeof(T[0]),
1096  and that the in-place operator new has been used to initialize
1097  each element of the array.
1098  */
1099  void SetArray(T*, int, int);
1100 
1101 protected:
1102  // implimentation //////////////////////////////////////////////////////
1103  void Move( int /* dest index*/, int /* src index */, int /* element count*/ );
1104  void ConstructDefaultElement(T*);
1105  void DestroyElement(T&);
1106  T* m_a; // pointer to array memory
1107  int m_count; // 0 <= m_count <= m_capacity
1108  int m_capacity; // actual length of m_a[]
1109 };
1110 
1111 
1112 /*
1113 Description:
1114  ON_Object array is used to store lists of classes that are
1115  derived from ON_Object. It differs from ON_ClassArray in
1116  that the virtual ON_Object::MemoryRelocate function is called
1117  when growing the dynamic array requires changing the location
1118  of the memory buffer used to store the elements in the array.
1119 */
1120 template <class T> class ON_ObjectArray : public ON_ClassArray<T>
1121 {
1122 public:
1123  ON_ObjectArray();
1124  ~ON_ObjectArray(); // override for struct member deallocation, etc.
1125  ON_ObjectArray( int ); // int = initial capacity
1128 
1129  ON__UINT32 DataCRC(ON__UINT32 current_remainder) const;
1130 
1131  // virtual ON_ClassArray<T> override that
1132  // calls MemoryRelocate on each element after
1133  // the reallocation.
1134  T* Realloc(T*,int);
1135 
1136  // virtual ON_ClassArray<T> override that
1137  // calls MemoryRelocate on each element after
1138  // the heap sort.
1139  // QuickSort() is generally the better choice.
1140  bool HeapSort( int (*)(const T*,const T*) );
1141 
1142  // virtual ON_ClassArray<T> override that
1143  // calls MemoryRelocate on each element after
1144  // the quick sort.
1145  bool QuickSort( int (*)(const T*,const T*) );
1146 };
1147 
1148 class ON_CLASS ON_UuidPair
1149 {
1150 public:
1151  /*
1152  Description:
1153  Compares m_uuid[0] and ignores m_uuid[1]
1154  */
1155  static
1156  int CompareFirstUuid(const class ON_UuidPair*,const class ON_UuidPair*);
1157 
1158  /*
1159  Description:
1160  Compares m_uuid[1] and ignores m_uuid[0]
1161  */
1162  static
1163  int CompareSecondUuid(const class ON_UuidPair*,const class ON_UuidPair*);
1164 
1165  /*
1166  Description:
1167  Compares m_uuid[0] then m_uuid[1].
1168  */
1169  static
1170  int Compare(const class ON_UuidPair*,const class ON_UuidPair*);
1171 
1172  ON_UuidPair();
1173  ON_UUID m_uuid[2];
1174 };
1175 
1176 #if defined(ON_DLL_TEMPLATE)
1177 
1178 // This stuff is here because of a limitation in the way Microsoft
1179 // handles templates and DLLs. See Microsoft's knowledge base
1180 // article ID Q168958 for details.
1181 #pragma warning( push )
1182 #pragma warning( disable : 4231 )
1183 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UUID>;
1184 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidIndex>;
1185 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_DisplayMaterialRef>;
1186 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_LinetypeSegment>;
1187 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidPair>;
1188 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_PlaneEquation>;
1189 ON_DLL_TEMPLATE template class ON_CLASS ON_ClassArray<ON_SimpleArray<int> >;
1190 #pragma warning( pop )
1191 
1192 #endif
1193 
1194 
1195 /*
1196 Description:
1197  The ON_UuidList class provides a tool to efficiently
1198  maintain a list of uuids and determine if a uuid is
1199  in the list. This class is based on the premise that
1200  there are no duplicate uuids in the list.
1201 */
1202 class ON_CLASS ON_UuidList : private ON_SimpleArray<ON_UUID>
1203 {
1204 public:
1205  ON_UuidList();
1206  ON_UuidList(int capacity);
1207  ~ON_UuidList();
1208  ON_UuidList(const ON_UuidList& src);
1209  ON_UuidList& operator=(const ON_UuidList& src);
1210 
1211  /*
1212  Description:
1213  Fast uuid compare. Not necessarily the same
1214  as ON_UuidCompare().
1215  */
1216  static
1217  int CompareUuid( const ON_UUID* a, const ON_UUID* b );
1218 
1219  /*
1220  Returns:
1221  Number of active uuids in the list.
1222  */
1223  int Count() const;
1224 
1225  /*
1226  Returns:
1227  Array of uuids in the list. Sorted with
1228  respect to ON_UuidList::CompareUuid().
1229  Remarks:
1230  Calling AddUuid() may grow the dynamic array
1231  and make the pointer invalid.
1232  */
1233  const ON_UUID* Array() const;
1234 
1235  /*
1236  Description:
1237  Provides an efficient way to empty a list so that it
1238  can be used again.
1239  */
1240  void Empty();
1241 
1242  /*
1243  Description:
1244  Destroy list. If list will be reused, Empty() is more
1245  efficient.
1246  */
1247  void Destroy();
1248 
1249  void Reserve(int capacity);
1250 
1251  /*
1252  Description:
1253  Makes the uuid list as efficent as possible in both search
1254  speed and memory usage. Use Compact() when a uuid list
1255  will be in use but is not likely to be modifed. A list
1256  that has been compacted can still be modified.
1257  */
1258  void Compact();
1259 
1260  /*
1261  Description:
1262  Adds a uuid to the list.
1263  Parameters:
1264  uuid - [in] id to add.
1265  bCheckForDupicates - [in] if true, then the uuid
1266  is not added if it is already in the list.
1267  If you are certain that the uuid is not in the
1268  list and you are going to have a large list of uuids,
1269  then setting bCheckForDupicates=false will
1270  speed up the addition of uuids.
1271  Returns:
1272  True if uuid was added. False if uuid was not added
1273  because it is already in the collection.
1274  */
1275  bool AddUuid(ON_UUID uuid, bool bCheckForDupicates=true);
1276 
1277  /*
1278  Description:
1279  Removes a uuid from the list.
1280  Parameters:
1281  uuid - [in] id to remove
1282  Returns:
1283  True if uuid was in the list and was removed.
1284  False if uuid was not in the list.
1285  */
1286  bool RemoveUuid(ON_UUID uuid);
1287 
1288  /*
1289  Description:
1290  Determine if a uuid is in the list.
1291  Returns:
1292  True if uuid is in the list.
1293  */
1294  bool FindUuid(ON_UUID uuid) const;
1295 
1296  /*
1297  Description:
1298  Saves the uuid list in an archive.
1299  Parameters:
1300  archive - [in] archive to write to.
1301  Returns:
1302  true if write was successful.
1303  */
1304  bool Write(
1305  class ON_BinaryArchive& archive
1306  ) const;
1307 
1308  /*
1309  Description:
1310  Read the uuid list from an archive.
1311  Parameters:
1312  archive - [in] archive to read from.
1313  Returns:
1314  true if the read was successful.
1315  */
1316  bool Read(
1317  class ON_BinaryArchive& archive
1318  );
1319 
1320  /*
1321  Description:
1322  Append the uuids in this class to uuid_list.
1323  Parameters:
1324  uuid_list - [in/out]
1325  Returns:
1326  Number of uuids added to uuid_list.
1327  */
1328  int GetUuids(
1329  ON_SimpleArray<ON_UUID>& uuid_list
1330  ) const;
1331 
1332  /*
1333  Description:
1334  This tool is used in rare situations when the object ids
1335  stored in the uuid list need to be remapped.
1336  Parameters:
1337  uuid_remap - [in]
1338  Is it critical that uuid_remap[] be sorted with respect
1339  to ON_UuidPair::CompareFirstUuid.
1340  */
1341  void RemapUuids(
1342  const ON_SimpleArray<ON_UuidPair>& uuid_remap
1343  );
1344 
1345 private:
1346  void SortHelper();
1347  ON_UUID* SearchHelper(const ON_UUID*) const;
1348  int m_sorted_count;
1349  int m_removed_count;
1350 };
1351 
1352 /*
1353 Description:
1354  The ON_UuidList class provides a tool
1355  to efficiently maintain a list of uuid-index
1356  pairs and determine if a uuid is in the list.
1357  This class is based on the premise that there are
1358  no duplicate uuids in the list.
1359 */
1360 class ON_CLASS ON_UuidIndexList : private ON_SimpleArray<ON_UuidIndex>
1361 {
1362 public:
1363  ON_UuidIndexList();
1364  ON_UuidIndexList(int capacity);
1365  ~ON_UuidIndexList();
1366  ON_UuidIndexList(const ON_UuidIndexList& src);
1368 
1369  /*
1370  Returns:
1371  Number of active uuids in the list.
1372  */
1373  int Count() const;
1374 
1375  /*
1376  Description:
1377  Provides an efficient way to empty a list so that it
1378  can be used again.
1379  */
1380  void Empty();
1381 
1382  void Reserve( int capacity );
1383 
1384  /*
1385  Description:
1386  Adds a uuid-index pair to the list.
1387  Parameters:
1388  uuid - [in] id to add.
1389  This uuid cannot be ON_max_uuid because ON_max_uuid
1390  is
1391  bCheckForDupicates - [in] if true, then the uuid
1392  is not added if it is already in the list.
1393  If you are certain that the uuid is not in the list
1394  and you have a have a large collection of uuids,
1395  then setting bCheckForDupicates=false will
1396  speed up the addition of uuids.
1397  Returns:
1398  True if uuid was added. False if uuid was not added
1399  because it is already in the collection.
1400  */
1401  bool AddUuidIndex(
1402  ON_UUID uuid,
1403  int index,
1404  bool bCheckForDupicates=true);
1405 
1406  /*
1407  Description:
1408  Removes an element with a matching uuid from the list.
1409  Parameters:
1410  uuid - [in] id to remove
1411  Returns:
1412  True if an element was removed. False if the uuid
1413  was not in the list.
1414  */
1415  bool RemoveUuid(
1416  ON_UUID uuid
1417  );
1418 
1419  /*
1420  Description:
1421  Determine if an element with a uuid is in the list.
1422  Parameters:
1423  index - [out] if not NULL and a matching uuid is found,
1424  then *index is set to the value of the index.
1425  Returns:
1426  True if an element was found. Returns false if
1427  the uuid is not in the list.
1428  */
1429  bool FindUuid(ON_UUID uuid, int* index=NULL) const;
1430 
1431  /*
1432  Description:
1433  Determine if a uuid-index pair is in the list.
1434  Returns:
1435  True if the uuid-index pair is in the list.
1436  Returns false if the uuid-index pair is not
1437  in the list.
1438  */
1439  bool FindUuidIndex(ON_UUID uuid, int index) const;
1440 
1441  /*
1442  Description:
1443  Append the uuids in this class to uuid_list.
1444  Parameters:
1445  uuid_list - [in/out]
1446  Returns:
1447  Number of uuids added to uuid_list.
1448  */
1449  int GetUuids(
1450  ON_SimpleArray<ON_UUID>& uuid_list
1451  ) const;
1452 
1453  /*
1454  Description:
1455  If you will perform lots of searches before the next
1456  change to the list, then calling ImproveSearchSpeed()
1457  will speed up the searches by culling removed objects
1458  and completely sorting the list so only a binary search
1459  is required. You may edit the list at any time after
1460  calling ImproveSearchSpeed(). If you are performing
1461  a few searches between edits, then excessive calling
1462  of ImproveSearchSpeed() may actually decrease overall
1463  program performance.
1464  */
1465  void ImproveSearchSpeed();
1466 
1467 private:
1468  ON_UuidIndex* SearchHelper(const ON_UUID*) const;
1469  unsigned int m_sorted_count;
1470  unsigned int m_removed_count;
1471 };
1472 
1473 /*
1474 Description:
1475  The ON_UuidPairList class provides a tool
1476  to efficiently maintain a list of uuid pairs
1477  and determine if a uuid is in the list.
1478  This class is based on the premise that there are
1479  no duplicate uuids in the list.
1480 */
1481 class ON_CLASS ON_UuidPairList : private ON_SimpleArray<ON_UuidPair>
1482 {
1483 public:
1484  ON_UuidPairList();
1485  ON_UuidPairList(int capacity);
1486  ~ON_UuidPairList();
1487  ON_UuidPairList(const ON_UuidPairList& src);
1489 
1490  /*
1491  Returns:
1492  Number of active uuids in the list.
1493  */
1494  int Count() const;
1495 
1496  /*
1497  Description:
1498  Provides an efficient way to empty a list so that it
1499  can be used again.
1500  */
1501  void Empty();
1502 
1503  void Reserve( int capacity );
1504 
1505  /*
1506  Description:
1507  Adds a uuid-index pair to the list.
1508  Parameters:
1509  id1 - [in] id to add.
1510  id2 - [in] id to add.
1511  bCheckForDupicates - [in] if true, then the pair
1512  is not added if id1 is already in the list.
1513  If you are certain that the id1 is not in the list
1514  and you have a have a large collection of uuids,
1515  then setting bCheckForDupicates=false will
1516  speed up the addition of uuids.
1517  Returns:
1518  True if the pair was added. False if the pair was not added
1519  because it is already in the collection.
1520  Remarks:
1521  You cannot add the pair value ( ON_max_uuid, ON_max_uuid ). This
1522  pair value is used to mark removed elements in the ON_UuidPairList[].
1523  */
1524  bool AddPair(
1525  ON_UUID id1,
1526  ON_UUID id2,
1527  bool bCheckForDupicates=true
1528  );
1529 
1530  /*
1531  Description:
1532  Removes an element with a matching id1 from the list.
1533  Parameters:
1534  id1 - [in] id to remove
1535  Returns:
1536  True if an element was removed. False if the id1
1537  was not in the list.
1538  */
1539  bool RemovePair(
1540  ON_UUID id1
1541  );
1542 
1543  /*
1544  Description:
1545  Removes an element with a matching id pair from the list.
1546  Parameters:
1547  id1 - [in]
1548  id2 - [in]
1549  Returns:
1550  True if an element was removed. False if the id pair
1551  does not appear in the list.
1552  */
1553  bool RemovePair(
1554  ON_UUID id1,
1555  ON_UUID id2
1556  );
1557 
1558  /*
1559  Description:
1560  Determine if an element with a uuid is in the list.
1561  Parameters:
1562  id1 - [in]
1563  id2 - [out] if not NULL and a matching id1 is found,
1564  then *id2 is set to the value of the second uuid.
1565  Returns:
1566  True if an element was found. Returns false if
1567  the id1 is not in the list.
1568  */
1569  bool FindId1(ON_UUID id1, ON_UUID* id2=0) const;
1570 
1571  /*
1572  Description:
1573  Determine if an id pair is in the list.
1574  Returns:
1575  True if the id pair is in the list.
1576  False if the id pair is not in the list.
1577  */
1578  bool FindPair(ON_UUID id1, ON_UUID id2) const;
1579 
1580  /*
1581  Description:
1582  Append the value of the first id in each pair to uuid_list[].
1583  Parameters:
1584  uuid_list - [in/out]
1585  Returns:
1586  Number of ids appended to uuid_list[].
1587  */
1588  int GetId1s(
1589  ON_SimpleArray<ON_UUID>& uuid_list
1590  ) const;
1591 
1592  /*
1593  Description:
1594  If you will perform lots of searches before the next
1595  change to the list, then calling ImproveSearchSpeed()
1596  will speed up the searches by culling removed objects
1597  and completely sorting the list so only a binary search
1598  is required. You may edit the list at any time after
1599  calling ImproveSearchSpeed(). If you are performing
1600  a few searches between edits, then excessive calling
1601  of ImproveSearchSpeed() may actually decrease overall
1602  program performance.
1603  */
1604  void ImproveSearchSpeed();
1605 
1606 private:
1607  ON_UuidPair* SearchHelper(const ON_UUID*) const;
1608  unsigned int m_sorted_count;
1609  unsigned int m_removed_count;
1610 };
1611 
1612 class ON_CLASS ON_2dexMap : private ON_SimpleArray<ON_2dex>
1613 {
1614 public:
1615  ON_2dexMap();
1616  ON_2dexMap(int capacity);
1617  ~ON_2dexMap();
1618 
1619  int Count() const;
1620 
1621  void Reserve(int capacity);
1622 
1623  const ON_2dex* Array() const;
1624 
1625  ON_2dex operator[](int i) const;
1626 
1627  /*
1628  Description:
1629  Creates an index map with the values
1630  (i0,j),...,(i0+count-1,j)
1631  Parameters:
1632  count - [in]
1633  number of elements
1634  i0 - [in]
1635  i value of first element
1636  j - [in]
1637  j value for all elements
1638  */
1639  void Create(int count, int i0, int j);
1640 
1641  /*
1642  Description:
1643  Searches for an element with a matching i
1644  and returns its j value. If no matching
1645  element is found, then not_found_rc is returned.
1646  Parameters:
1647  i - [in]
1648  value of i to search for
1649  not_found_rc - [in]
1650  value to return if there is not a match.
1651  Returns:
1652  j value
1653  */
1654  int FindIndex(
1655  int i,
1656  int not_found_rc
1657  ) const;
1658 
1659  /*
1660  Description:
1661  Adds and element (i,j). If there is already an entry with
1662  value (i,*), then no element is added.
1663  Parameters:
1664  i - [in]
1665  i - [in]
1666  Returns:
1667  True if and element it added.
1668  */
1669  bool AddIndex(
1670  int i,
1671  int j
1672  );
1673 
1674  /*
1675  Description:
1676  Searches for an element (i,*) and sets its j value to j.
1677  If there is no element with a matching i, then false
1678  is returned.
1679  Parameters:
1680  i - [in]
1681  j - [in]
1682  Returns:
1683  True if and element exists and was set.
1684  */
1685  bool SetIndex(
1686  int i,
1687  int j
1688  );
1689 
1690  /*
1691  Description:
1692  If an element (i,*) exists, its j value is set. Otherwise
1693  a new element with value (i,j) is added.
1694  Parameters:
1695  i - [in]
1696  j - [in]
1697  */
1698  void SetOrAddIndex(
1699  int i,
1700  int j
1701  );
1702 
1703  /*
1704  Description:
1705  If an element (i,*) exists, it is removed. If there is
1706  not an element with a matching i value, then false
1707  is returned.
1708  Parameters:
1709  i - [in]
1710  Returns:
1711  True if the element was removed
1712  */
1713  bool RemoveIndex(
1714  int i
1715  );
1716 
1717  const ON_2dex* Find2dex(int i) const;
1718 
1719 private:
1720  bool m_bSorted;
1721 };
1722 
1723 /*
1724 Description:
1725  Compare function for Sort and Search methods.
1726 Returns:
1727  -1 if *a < *b is true
1728  1 if *b < *a is true
1729  0 if niether *a <*b nor *b<*a is true
1730 Details:
1731  Use this template functions to sort ON_SimpleArray and
1732  ON_ClassArray objects into increasing order. The elements
1733  of the arrays must be a type with an operator < defined.
1734  In particular it works with built in types like double,
1735  int and pointers.
1736 Example:
1737 
1738  ON_SimpleArray<int> A;
1739  A = ...;
1740  // Sort A in increasing order
1741  A.QuickSort( ON_CompareIncreasing<double> );
1742 
1743 See Also:
1744  ON_CompareDecreasing
1745 */
1746 template< class T>
1747 static
1748 int ON_CompareIncreasing( const T* a, const T* b);
1749 
1750 /*
1751 Description:
1752  Compare function for Sort and Search methods.
1753 Returns:
1754  -1 if *b < *a is true
1755  1 if *a < *b is true
1756  0 if niether *a < *b nor *b < *a is true
1757 Details:
1758  Use this template functions to sort ON_SimpleArray and
1759  ON_ClassArray objects into decreasing order. The elements
1760  of the arrays must be a type with an operator < defined.
1761  In particular it works with built in types like double,
1762  int and pointers.
1763 Example:
1764 
1765  class C
1766  {
1767  public:
1768  ...
1769  bool operator<(const C&) const;
1770  };
1771  ...
1772  ON_ClassArray<C> A;
1773  A = ...;
1774  // Sort A in descrasing order
1775  A.QuickSort( ON_CompareDecreasing<C> );
1776 
1777 See Also:
1778  ON_CompareIncreasing
1779 */
1780 template< class T>
1781 static
1782 int ON_CompareDecreasing( const T* a, const T* b);
1783 
1784 
1785 // definitions of the template functions are in a different file
1786 // so that Microsoft's developer studio's autocomplete utility
1787 // will work on the template functions.
1788 #include "opennurbs_array_defs.h"
1789 
1790 
1791 #endif
void Move(int, int, int)
virtual ON_SimpleArray< T > & operator=(const ON_SimpleArray< T > &)
void Swap(int, int)
int BinarySearch(const T *, int(*)(const T *, const T *)) const
int Search(const T &) const
virtual T * Realloc(T *, int)
void MemSet(unsigned char)
bool QuickSort(int(*)(const T *, const T *))
void Insert(int, const 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
ON__UINT32 DataCRC(ON__UINT32 current_remainder) const
unsigned int SizeOfElement() const
unsigned int SizeOfArray() const
void EmergencyDestroy(void)
bool HeapSort(int(*)(const T *, const T *))