Point Cloud Library (PCL) 1.13.0
Loading...
Searching...
No Matches
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
20class ON_2dPointArray;
21class ON_3dPointArray;
22class ON_4dPointArray;
23
26
27class ON_2fPointArray;
28class ON_3fPointArray;
29class ON_4fPointArray;
30
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
46template <class T> class ON_SimpleArray
47{
48public:
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
348protected:
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
367ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool>;
368ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char>;
369ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char>;
370ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short>;
371ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short>;
372ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int>;
373ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int>;
374ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float>;
375ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double>;
376
377ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool*>;
378ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char*>;
379ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char*>;
380ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short*>;
381ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short*>;
382ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int*>;
383ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int*>;
384ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float*>;
385ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double*>;
386
387ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dPoint>;
388ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dPoint>;
389ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4dPoint>;
390ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dVector>;
391ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dVector>;
392
393ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fPoint>;
394ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fPoint>;
395ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4fPoint>;
396ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fVector>;
397ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fVector>;
398
399ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Color>;
400ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_SurfaceCurvature>;
401ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Interval>;
402
403ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dex>;
404ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dex>;
405
406ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_COMPONENT_INDEX>;
407#pragma warning( pop )
408#endif
409
410
411/////////////////////////////////////////////////////////////////
412//
413
415{
416public:
417 // see ON_SimpleArray class definition comments for constructor documentation
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{
439public:
440 // see ON_SimpleArray class definition comments for constructor documentation
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{
461public:
462 // see ON_SimpleArray class definition comments for constructor documentation
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.
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.
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
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 */
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.
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.
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.
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 */
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{
665public:
666 // see ON_SimpleArray class definition comments for constructor documentation
671
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{
689public:
690 // see ON_SimpleArray class definition comments for constructor documentation
695
696 bool Transform( const ON_Xform& );
697 bool SwapCoordinates(int,int);
698};
699
700
701/////////////////////////////////////////////////////////////////
702//
703
705{
706public:
707 // see ON_SimpleArray class definition comments for constructor documentation
712
713 bool Transform( const ON_Xform& );
714 bool SwapCoordinates(int,int);
715};
716
717
718/////////////////////////////////////////////////////////////////
719//
720
722{
723public:
724 // see ON_SimpleArray class definition comments for constructor documentation
729
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{
746public:
747 // see ON_SimpleArray class definition comments for constructor documentation
752
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{
769public:
774
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{
790public:
795
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//
821template <class T> class ON_ClassArray
822{
823public:
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
835 ON_ClassArray<T>& operator=( const ON_ClassArray<T>& );
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
1101protected:
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/*
1113Description:
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*/
1120template <class T> class ON_ObjectArray : public ON_ClassArray<T>
1121{
1122public:
1123 ON_ObjectArray();
1124 ~ON_ObjectArray(); // override for struct member deallocation, etc.
1125 ON_ObjectArray( int ); // int = initial capacity
1127 ON_ObjectArray<T>& operator=( const ON_ObjectArray<T>& );
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
1148class ON_CLASS ON_UuidPair
1149{
1150public:
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
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 )
1183ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UUID>;
1184ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidIndex>;
1185ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_DisplayMaterialRef>;
1186ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_LinetypeSegment>;
1187ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidPair>;
1188ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_PlaneEquation>;
1189ON_DLL_TEMPLATE template class ON_CLASS ON_ClassArray<ON_SimpleArray<int> >;
1190#pragma warning( pop )
1191
1192#endif
1193
1194
1195/*
1196Description:
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*/
1202class ON_CLASS ON_UuidList : private ON_SimpleArray<ON_UUID>
1203{
1204public:
1206 ON_UuidList(int capacity);
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 */
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 */
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 */
1342 const ON_SimpleArray<ON_UuidPair>& uuid_remap
1343 );
1344
1345private:
1346 void SortHelper();
1347 ON_UUID* SearchHelper(const ON_UUID*) const;
1348 int m_sorted_count;
1349 int m_removed_count;
1350};
1351
1352/*
1353Description:
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*/
1360class ON_CLASS ON_UuidIndexList : private ON_SimpleArray<ON_UuidIndex>
1361{
1362public:
1364 ON_UuidIndexList(int capacity);
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 */
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 */
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 */
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 */
1466
1467private:
1468 ON_UuidIndex* SearchHelper(const ON_UUID*) const;
1469 unsigned int m_sorted_count;
1470 unsigned int m_removed_count;
1471};
1472
1473/*
1474Description:
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*/
1481class ON_CLASS ON_UuidPairList : private ON_SimpleArray<ON_UuidPair>
1482{
1483public:
1485 ON_UuidPairList(int capacity);
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 */
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 */
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 */
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 */
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 */
1605
1606private:
1607 ON_UuidPair* SearchHelper(const ON_UUID*) const;
1608 unsigned int m_sorted_count;
1609 unsigned int m_removed_count;
1610};
1611
1612class ON_CLASS ON_2dexMap : private ON_SimpleArray<ON_2dex>
1613{
1614public:
1616 ON_2dexMap(int capacity);
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 */
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 */
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 */
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 */
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 */
1714 int i
1715 );
1716
1717 const ON_2dex* Find2dex(int i) const;
1718
1719private:
1720 bool m_bSorted;
1721};
1722
1723/*
1724Description:
1725 Compare function for Sort and Search methods.
1726Returns:
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
1730Details:
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.
1736Example:
1737
1738 ON_SimpleArray<int> A;
1739 A = ...;
1740 // Sort A in increasing order
1741 A.QuickSort( ON_CompareIncreasing<double> );
1742
1743See Also:
1744 ON_CompareDecreasing
1745*/
1746template< class T>
1747static
1748int ON_CompareIncreasing( const T* a, const T* b);
1749
1750/*
1751Description:
1752 Compare function for Sort and Search methods.
1753Returns:
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
1757Details:
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.
1763Example:
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
1777See Also:
1778 ON_CompareIncreasing
1779*/
1780template< class T>
1781static
1782int 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
bool Transform(const ON_Xform &)
bool GetBBox(double boxmin[2], double boxmax[2], int bGrowBox=false) const
ON_2dPointArray & operator=(const ON_2dPointArray &)
ON_2dPointArray(const ON_2dPointArray &)
bool SwapCoordinates(int, int)
bool GetBBox(double boxmin[2], double boxmax[2], int bGrowBox=false) const
bool SwapCoordinates(int, int)
ON_2dVectorArray(const ON_2dVectorArray &)
bool Transform(const ON_Xform &)
ON_2dVectorArray & operator=(const ON_2dVectorArray &)
bool AddIndex(int i, int j)
const ON_2dex * Find2dex(int i) const
int FindIndex(int i, int not_found_rc) const
int Count() const
bool SetIndex(int i, int j)
void Create(int count, int i0, int j)
const ON_2dex * Array() const
ON_2dexMap(int capacity)
ON_2dex operator[](int i) const
void Reserve(int capacity)
bool RemoveIndex(int i)
void SetOrAddIndex(int i, int j)
ON_2fPointArray & operator=(const ON_2fPointArray &)
bool SwapCoordinates(int, int)
bool Transform(const ON_Xform &)
ON_2fPointArray(const ON_2fPointArray &)
bool GetBBox(float boxmin[2], float boxmax[2], int bGrowBox=false) const
bool SwapCoordinates(int, int)
bool Transform(const ON_Xform &)
bool GetBBox(float boxmin[2], float boxmax[2], bool=false) const
ON_2fVectorArray(const ON_2fVectorArray &)
ON_2fVectorArray & operator=(const ON_2fVectorArray &)
ON_3dPointArray & operator=(const ON_SimpleArray< ON_3fPoint > &)
bool SwapCoordinates(int i, int j)
bool GetBBox(double boxmin[3], double boxmax[3], int bGrowBox=false) const
ON_3dPointArray & operator=(const ON_3dPointArray &)
bool GetTightBoundingBox(ON_BoundingBox &tight_bbox, int bGrowBox=false, const ON_Xform *xform=0) const
bool Rotate(double sin_angle, double cos_angle, const ON_3dVector &axis_of_rotation, const ON_3dPoint &center_of_rotation)
bool Translate(const ON_3dVector &delta)
bool Rotate(double angle_in_radians, const ON_3dVector &axis_of_rotation, const ON_3dPoint &center_of_rotation)
ON_3dPointArray(const ON_SimpleArray< ON_3fPoint > &)
ON_3dPointArray(const ON_SimpleArray< ON_3dPoint > &)
bool GetClosestPoint(ON_3dPoint P, int *closest_point_index, double maximum_distance=0.0) const
ON_BoundingBox BoundingBox() const
bool Create(int point_dimension, int bRational, int point_count, int point_stride, const double *points)
bool Create(int point_dimension, int bRational, int point_count, int point_stride, const float *points)
bool GetBoundingBox(ON_BoundingBox &bbox, int bGrowBox=false) const
bool Transform(const ON_Xform &xform)
bool GetBBox(double boxmin[3], double boxmax[3], bool bGrowBow=false) const
bool SwapCoordinates(int, int)
ON_3dVectorArray(const ON_3dVectorArray &)
ON_3dVectorArray & operator=(const ON_3dVectorArray &)
bool Transform(const ON_Xform &)
bool GetBBox(float boxmin[3], float boxmax[3], int bGrowBox=false) const
ON_3fPointArray(const ON_3fPointArray &)
ON_3fPointArray & operator=(const ON_3fPointArray &)
bool SwapCoordinates(int, int)
bool Transform(const ON_Xform &)
ON_3fVectorArray(const ON_3fVectorArray &)
bool Transform(const ON_Xform &)
bool SwapCoordinates(int, int)
ON_3fVectorArray & operator=(const ON_3fVectorArray &)
bool GetBBox(float boxmin[3], float boxmax[3], int bGrowBox=false) const
bool Transform(const ON_Xform &)
ON_4dPointArray(const ON_4dPointArray &)
ON_4dPointArray & operator=(const ON_4dPointArray &)
bool SwapCoordinates(int, int)
bool Transform(const ON_Xform &)
ON_4fPointArray(const ON_4fPointArray &)
ON_4fPointArray & operator=(const ON_4fPointArray &)
bool SwapCoordinates(int, int)
bool Sort(ON::sort_algorithm sort_algorithm, int *, int(*)(const T *, const T *)) const
void Append(const T &)
void Insert(int, const T &)
unsigned int UnsignedCount() const
unsigned int SizeOfArray() const
bool HeapSort(int(*)(const T *, const T *))
bool QuickSort(int(*)(const T *, const T *))
void Move(int, int, int)
void MemSet(unsigned char)
ON__UINT32 DataCRC(ON__UINT32 current_remainder) const
int Search(const T &) const
virtual T * Realloc(T *, int)
bool Permute(const int *)
virtual ON_SimpleArray< T > & operator=(const ON_SimpleArray< T > &)
int BinarySearch(const T *, int(*)(const T *, const T *)) const
unsigned int SizeOfElement() const
bool RemoveUuid(ON_UUID uuid)
bool FindUuidIndex(ON_UUID uuid, int index) const
bool AddUuidIndex(ON_UUID uuid, int index, bool bCheckForDupicates=true)
int GetUuids(ON_SimpleArray< ON_UUID > &uuid_list) const
ON_UuidIndexList(int capacity)
void ImproveSearchSpeed()
bool FindUuid(ON_UUID uuid, int *index=NULL) const
ON_UuidIndexList(const ON_UuidIndexList &src)
ON_UuidIndexList & operator=(const ON_UuidIndexList &src)
int Count() const
void Reserve(int capacity)
void RemapUuids(const ON_SimpleArray< ON_UuidPair > &uuid_remap)
bool AddUuid(ON_UUID uuid, bool bCheckForDupicates=true)
int Count() const
int GetUuids(ON_SimpleArray< ON_UUID > &uuid_list) const
static int CompareUuid(const ON_UUID *a, const ON_UUID *b)
const ON_UUID * Array() const
void Reserve(int capacity)
ON_UuidList & operator=(const ON_UuidList &src)
bool Write(class ON_BinaryArchive &archive) const
void Empty()
ON_UuidList(const ON_UuidList &src)
bool RemoveUuid(ON_UUID uuid)
ON_UuidList(int capacity)
void Compact()
bool FindUuid(ON_UUID uuid) const
bool Read(class ON_BinaryArchive &archive)
void Destroy()
static int Compare(const class ON_UuidPair *, const class ON_UuidPair *)
static int CompareSecondUuid(const class ON_UuidPair *, const class ON_UuidPair *)
static int CompareFirstUuid(const class ON_UuidPair *, const class ON_UuidPair *)
bool FindId1(ON_UUID id1, ON_UUID *id2=0) const
void Reserve(int capacity)
ON_UuidPairList & operator=(const ON_UuidPairList &src)
ON_UuidPairList(const ON_UuidPairList &src)
bool RemovePair(ON_UUID id1, ON_UUID id2)
int Count() const
bool FindPair(ON_UUID id1, ON_UUID id2) const
bool RemovePair(ON_UUID id1)
void ImproveSearchSpeed()
int GetId1s(ON_SimpleArray< ON_UUID > &uuid_list) const
ON_UuidPairList(int capacity)
bool AddPair(ON_UUID id1, ON_UUID id2, bool bCheckForDupicates=true)