opennurbs_array.h
Go to the documentation of this file.
00001 /* $NoKeywords: $ */
00002 /*
00003 //
00004 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
00005 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
00006 // McNeel & Associates.
00007 //
00008 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
00009 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
00010 // MERCHANTABILITY ARE HEREBY DISCLAIMED.
00011 //                              
00012 // For complete openNURBS copyright information see <http://www.opennurbs.org>.
00013 //
00015 */
00016 
00017 #if !defined(ON_ARRAY_INC_)
00018 #define ON_ARRAY_INC_
00019 
00020 class ON_2dPointArray;
00021 class ON_3dPointArray;
00022 class ON_4dPointArray;
00023 
00024 class ON_2dVectorArray;
00025 class ON_3dVectorArray;
00026 
00027 class ON_2fPointArray;
00028 class ON_3fPointArray;
00029 class ON_4fPointArray;
00030 
00031 class ON_2fVectorArray;
00032 class ON_3fVectorArray;
00033 
00035 //
00036 // The ON_SimpleArray<> template is more efficient than the
00037 // ON_ClassArray<> template, but ON_SimpleArray<> should not
00038 // be used for arrays of classes that require explicit
00039 // construction, destruction, or copy operators.
00040 //
00041 // By default, ON_SimpleArray<> uses onrealloc() to manage
00042 // the dynamic array memory. If you want to use something 
00043 // besides onrealloc() to manage the array memory, then override
00044 // ON_SimpleArray::Realloc().
00045 
00046 template <class T> class ON_SimpleArray
00047 {
00048 public:
00049   // construction ////////////////////////////////////////////////////////
00050 
00051   // These constructors create an array that uses onrealloc() to manage
00052   // the array memory.
00053   ON_SimpleArray();
00054   ON_SimpleArray( int ); // int = initial capacity
00055 
00056   // Copy constructor
00057   ON_SimpleArray( const ON_SimpleArray<T>& );
00058 
00059   virtual
00060   ~ON_SimpleArray();
00061 
00062   // Assignment operator
00063   virtual
00064   ON_SimpleArray<T>& operator=( const ON_SimpleArray<T>& );
00065   
00066   // emergency bailout ///////////////////////////////////////////////////
00067   void EmergencyDestroy(void); // call only when memory used by this array
00068                                // may have become invalid for reasons beyond
00069                                // your control. EmergencyDestroy() zeros
00070                                // anything that could possibly cause
00071                                // ~ON_SimpleArray() to crash.
00072 
00073   // query ///////////////////////////////////////////////////////////////
00074   
00075         int Count() const;      // number of elements in array
00076   unsigned int UnsignedCount() const;
00077         
00078         int Capacity() const;  // capacity of array
00079 
00080   unsigned int SizeOfArray() const; // amount of memory in the m_a[] array
00081 
00082   unsigned int SizeOfElement() const; // amount of memory in an m_a[] array element
00083 
00084   ON__UINT32 DataCRC(ON__UINT32 current_remainder) const;
00085 
00086   // The operator[] does to not check for valid indices.
00087   // The caller is responsibile for insuring that 0 <= i < Capacity()
00088   T& operator[]( int );
00089   T& operator[]( unsigned int );
00090   T& operator[]( ON__INT64 );
00091   T& operator[]( ON__UINT64 );
00092   const T& operator[]( int ) const;
00093   const T& operator[]( unsigned int ) const;  
00094   const T& operator[]( ON__INT64 ) const;
00095   const T& operator[]( ON__UINT64 ) const;  
00096 
00097   operator T*();                     // The cast operators return a pointer
00098   operator const T*() const;         // to the array.  If Count() is zero,
00099                                      // this pointer is NULL.
00100 
00101   T* First();
00102   const T* First() const;             // returns NULL if count = 0
00103 
00104   // At(index) returns NULL if index < 0 or index >= count
00105   T* At( int );
00106   T* At( unsigned int );
00107   T* At( ON__INT64 );
00108   T* At( ON__UINT64 );
00109   const T* At( int ) const;
00110   const T* At( unsigned int ) const;
00111   const T* At( ON__INT64 ) const;
00112   const T* At( ON__UINT64 ) const;
00113 
00114   T* Last();
00115   const T* Last() const;             // returns NULL if count = 0
00116 
00117   
00118   // array operations ////////////////////////////////////////////////////
00119 
00120   T& AppendNew();                    // Most efficient way to add a new element 
00121                                      // to the array.  Increases count by 1.
00122 
00123   void Append( const T& );           // Append copy of element.
00124                                      // Increments count by 1.
00125 
00126   void Append( int, const T* );      // Append copy of an array T[count]
00127 
00128 
00129   void Insert( int, const T& );      // Insert copy of element. Uses
00130                                      // memmove() to perform any
00131                                      // necessary moving.
00132                                      // Increases count by 1.
00133 
00134   void Remove();                     // Removes last element.  Decrements
00135                                      // count by 1.  Does not change capacity.
00136 
00137   virtual
00138   void Remove( int );                // Removes element. Uses memmove() to
00139                                      // perform any necessary shifting.
00140                                      // Decrements count by 1.  Does not change
00141                                      // capacity
00142 
00143   void Empty();           // Sets count to 0, leaves capacity untouched.
00144 
00145   void Reverse();         // reverse order
00146 
00147   void Swap(int,int);     // swap elements i and j
00148 
00150   // Search( e ) does a SLOW search of the array starting at array[0]
00151   // and returns the index "i" of the first element that satisfies 
00152   // e == array[i]. (== is really memcmp()).  If the search is not 
00153   // successful, then Search() returns -1.  For Search(T) to work 
00154   // correctly, T must be a simple type.  Use Search(p,compare())
00155   // for Ts that are structs/classes that contain pointers.  Search()
00156   // is only suitable for performing infrequent searchs of small 
00157   // arrays.  Sort the array and use BinarySearch() for performing
00158   // efficient searches.
00159   int Search( const T& ) const;
00160 
00162   // Search( p, compare ) does a SLOW search of the array starting
00163   // at array[0] and returns the index "i" of the first element 
00164   // that satisfies  compare(p,&array[i])==0.  If the search is not
00165   // successful, then Search() returns -1.  Search() is only suitable
00166   // for performing infrequent searches of small arrays.  Sort the
00167   // array and use BinarySearch() for performing efficient searches.
00168         // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
00169   int Search( const T*, int (*)(const T*,const T*) ) const;
00170 
00172   // BinarySearch( p, compare ) does a fast search of a sorted array
00173   // and returns the smallest index "i" of the element that satisifies
00174   // 0==compare(p,&array[i]).  
00175   //
00176   // BinarySearch( p, compare, count ) does a fast search of the first
00177   // count element sorted array and returns the smallest index "i" of 
00178   // the element that satisifies 0==compare(p,&array[i]).  The version
00179   // that takes a "count" is useful when elements are being appended
00180   // during a calculation and the appended elements are not sorted.
00181   //
00182   // If the search is successful, 
00183   // BinarySearch() returns the index of the element (>=0).
00184   // If the search is not successful, BinarySearch() returns -1.  
00185   // Use QuickSort( compare ) or, in rare cases and after meaningful
00186   // performance testing using optimzed release builds, 
00187   // HeapSort( compare ) to sort the array.
00188         // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
00189   int BinarySearch( const T*, int (*)(const T*,const T*) ) const;
00190   int BinarySearch( const T*, int (*)(const T*,const T*), int ) const;
00191 
00193   // Sorts the array using the heap sort algorithm.
00194   // QuickSort() is generally the better choice.
00195   bool HeapSort( int (*)(const T*,const T*) );
00196 
00198   // Sorts the array using the quick sort algorithm.
00199         // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
00200   bool QuickSort( int (*)(const T*,const T*) );
00201 
00202   /*
00203   Description:
00204     Sort() fills in the index[] array so that 
00205     array[index[i]] <= array[index[i+1]].  
00206     The array is not modified.  
00207 
00208   Parameters:
00209     sort_algorithm - [in]  
00210       ON::quick_sort (best in general) or ON::heap_sort
00211       Use ON::heap_sort only if you have done extensive testing with
00212       optimized release builds and are confident heap sort is 
00213       significantly faster.
00214     index - [out] an array of length Count() that is returned with
00215         some permutation of (0,1,...,Count()-1). 
00216     compare - [in] compare function compare(a,b,p) should return
00217         <0 if a<b, 0, if a==b, and >0 if a>b.
00218   Returns:
00219     true if successful
00220   */
00221   bool Sort( 
00222     ON::sort_algorithm sort_algorithm, 
00223     int* /* index[] */ ,
00224     int (*)(const T*,const T*) 
00225     ) const; 
00226 
00227   /*
00228   Description:
00229     Sort() fills in the index[] array so that 
00230     array[index[i]] <= array[index[i+1]].  
00231     The array is not modified.  
00232 
00233   Parameters:
00234     sort_algorithm - [in]  
00235       ON::quick_sort (best in general) or ON::heap_sort
00236       Use ON::heap_sort only if you have done extensive testing with
00237       optimized release builds and are confident heap sort is 
00238       significantly faster.
00239     index - [out] an array of length Count() that is returned with
00240         some permutation of (0,1,...,Count()-1). 
00241     compare - [in] compare function compare(a,b,p) should return
00242         <0 if a<b, 0, if a==b, and >0 if a>b.
00243     p - [in] pointer passed as third argument to compare.
00244 
00245   Returns:
00246     true if successful
00247   */
00248   bool Sort( 
00249     ON::sort_algorithm sort_algorithm,
00250     int*, // index[] 
00251     int (*)(const T*,const T*,void*), // int compare(const T*,const T*,void* p)
00252     void* // p
00253     ) const; 
00254 
00256   // Permutes the array so that output[i] = input[index[i]].
00257   // The index[] array should be a permutation of (0,...,Count()-1).
00258   bool Permute( const int* /*index[]*/ );
00259 
00261   // Zeros all array memory. 
00262   // Count and capacity are not changed.
00263   void Zero();
00264 
00266   // Sets all bytes in array memory to value. 
00267   // Count and capacity are not changed.
00268   void MemSet(unsigned char); 
00269   
00270   // memory managment ////////////////////////////////////////////////////
00271 
00272   void Reserve( int );    // increase capacity to at least the requested value
00273 
00274   void Shrink();          // remove unused capacity
00275 
00276   void Destroy();         // onfree any memory and set count and capacity to zero
00277     
00278   // low level memory managment //////////////////////////////////////////
00279 
00280   // By default, ON_SimpleArray<> uses onrealloc() to manage
00281   // the dynamic array memory. If you want to use something 
00282   // besides onrealloc() to manage the array memory, then override 
00283   // Realloc(). The T* Realloc(ptr, capacity) should do the following:
00284   //
00285   // 1) If ptr and capacity are zero, return NULL.
00286   // 2) If ptr is NULL, an capacity > 0, allocate a memory block of 
00287   //    capacity*sizeof(T) bytes and return a pointer to this block.
00288   //    If the allocation request fails, return NULL.
00289   // 3) If ptr is not NULL and capacity is 0, free the memory block
00290   //    pointed to by ptr and return NULL.
00291   // 4) If ptr is not NULL and capacity > 0, then reallocate the memory
00292   //    block and return a pointer to the reallocated block.  If the 
00293   //    reallocation request fails, return NULL.
00294   //
00295   // NOTE WELL: 
00296   //    Microsoft's VC 6.0 realloc() contains a bug that can cause
00297   //    crashes and should be avoided. See MSDN Knowledge Base article
00298   //    ID Q225099 for more information.
00299   virtual
00300   T* Realloc(T*,int); // (re)allocated capacity*sizeof(T) bytes
00301 
00302   T* Array();                         // The Array() function return the 
00303   
00304   const T* Array() const;             // m_a pointer value.
00305 
00306   void SetCount( int );               // If value is <= Capacity(), then
00307                                       // sets count to specified value.
00308 
00309   void SetCapacity( int );            // Shrink/grows capacity.  If value
00310                                       // is < current Count(), then count
00311                                       // is reduced to value.
00312                                       //
00313 
00314   int NewCapacity() const;            // When the dynamic array needs to grow,
00315                                       // this calculates the new value for m_capacity.
00316 
00317   /*
00318   Description:
00319     Expert user tool to take charge of the memory used by 
00320     the dyanmic array.
00321   Returns:
00322      A pointer to the array and zeros out this class.
00323      The returned pointer is on the heap and must be
00324      deallocated by calling onfree().
00325   */
00326   T* KeepArray();
00327 
00328   /*
00329   Description:
00330     Do not use this version of SetArray().  Use the one that takes
00331     a pointer, count and capacity.
00332   */
00333   void SetArray(T*);
00334 
00335   /*
00336   Description:
00337     Expert user tool to set the memory used by the dyanmic array.
00338   Parameters:
00339     T* pointer - [in]
00340     int count [in]
00341     int capacity - [in]
00342        m_a is set to pointer, m_count is set to count, and m_capacity
00343        is set to capacity.  It is critical that the pointer be one 
00344        returned by onmalloc(sz), where sz >= capacity*sizeof(T[0]).
00345   */
00346   void SetArray(T*, int, int);
00347 
00348 protected:
00349   // implimentation //////////////////////////////////////////////////////
00350   void Move( int /* dest index*/, int /* src index */, int /* element count*/ );
00351         T*   m_a;        // pointer to array memory
00352         int  m_count;    // 0 <= m_count <= m_capacity
00353         int  m_capacity; // actual length of m_a[]
00354 };
00355 
00356 
00358 //
00359 
00360 #if defined(ON_DLL_TEMPLATE)
00361 // This stuff is here because of a limitation in the way Microsoft
00362 // handles templates and DLLs.  See Microsoft's knowledge base 
00363 // article ID Q168958 for details.
00364 #pragma warning( push )
00365 #pragma warning( disable : 4231 )
00366 
00367 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool>;
00368 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char>;
00369 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char>;
00370 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short>;
00371 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short>;
00372 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int>;
00373 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int>;
00374 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float>;
00375 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double>;
00376 
00377 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<bool*>;
00378 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<char*>;
00379 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned char*>;
00380 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<short*>;
00381 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned short*>;
00382 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<int*>;
00383 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<unsigned int*>;
00384 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<float*>;
00385 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<double*>;
00386 
00387 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dPoint>;
00388 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dPoint>;
00389 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4dPoint>;
00390 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dVector>;
00391 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dVector>;
00392 
00393 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fPoint>;
00394 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fPoint>;
00395 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_4fPoint>;
00396 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2fVector>;
00397 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3fVector>;
00398 
00399 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Color>;
00400 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_SurfaceCurvature>;
00401 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_Interval>;
00402 
00403 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_2dex>;
00404 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_3dex>;
00405 
00406 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_COMPONENT_INDEX>;
00407 #pragma warning( pop )
00408 #endif
00409 
00410 
00412 //
00413 
00414 class ON_CLASS ON_2dPointArray : public ON_SimpleArray<ON_2dPoint>
00415 {
00416 public:
00417   // see ON_SimpleArray class definition comments for constructor documentation
00418   ON_2dPointArray();
00419   ON_2dPointArray(int);
00420   ON_2dPointArray( const ON_2dPointArray& );
00421   ON_2dPointArray& operator=( const ON_2dPointArray& );
00422 
00423   bool GetBBox( // returns true if successful
00424          double boxmin[2],
00425          double boxmax[2],
00426          int bGrowBox = false  // true means grow box
00427          ) const;
00428 
00429   bool Transform( const ON_Xform& );
00430   bool SwapCoordinates(int,int);
00431 };
00432 
00433 
00435 //
00436 
00437 class ON_CLASS ON_2fPointArray : public ON_SimpleArray<ON_2fPoint>
00438 {
00439 public:
00440   // see ON_SimpleArray class definition comments for constructor documentation
00441   ON_2fPointArray();
00442   ON_2fPointArray(int);
00443   ON_2fPointArray(const ON_2fPointArray&);
00444   ON_2fPointArray& operator=( const ON_2fPointArray& );
00445 
00446   bool GetBBox( // returns true if successful
00447          float boxmin[2],
00448          float boxmax[2],
00449          int bGrowBox = false  // true means grow box
00450          ) const;
00451   bool Transform( const ON_Xform& );
00452   bool SwapCoordinates(int,int);
00453 };
00454 
00455 
00457 //
00458 
00459 class ON_CLASS ON_3dPointArray : public ON_SimpleArray<ON_3dPoint>
00460 {
00461 public:
00462   // see ON_SimpleArray class definition comments for constructor documentation
00463   ON_3dPointArray();
00464   ON_3dPointArray(int);
00465   ON_3dPointArray(const ON_SimpleArray<ON_3dPoint>&);
00466   ON_3dPointArray& operator=( const ON_3dPointArray& );
00467   ON_3dPointArray(const ON_SimpleArray<ON_3fPoint>&);
00468   ON_3dPointArray& operator=( const ON_SimpleArray<ON_3fPoint>& );
00469 
00470   // Description:
00471   //   Create 3d point list
00472   // Parameters:
00473   //   point_dimension - [in] dimension of input points (2 or 3)
00474   //   bRational - [in] true if points are in homogenous rational form
00475   //   point_count - [in] number of points
00476   //   point_stride - [in] number of doubles to skip between points
00477   //   points - [in] array of point coordinates
00478   bool Create(
00479     int point_dimension,
00480     int bRational,
00481     int point_count,
00482     int point_stride,
00483     const double* points
00484     );
00485 
00486   // Description:
00487   //   Create 3d point list
00488   // Parameters:
00489   //   point_dimension - [in] dimension of input points (2 or 3)
00490   //   bRational - [in] true if points are in homogenous rational form
00491   //   point_count - [in] number of points
00492   //   point_stride - [in] number of doubles to skip between points
00493   //   points - [in] array of point coordinates
00494   bool Create(
00495     int point_dimension,
00496     int bRational,
00497     int point_count,
00498     int point_stride,
00499     const float* points
00500     );
00501 
00502   // Description: 
00503   //   Get 3d axis aligned bounding box.
00504   // Returns:
00505   //   3d bounding box of point list.
00506   ON_BoundingBox BoundingBox() const;
00507 
00508   // Description:
00509   //   Get 3d axis aligned bounding box or the union
00510   //   of the input box with the point list's bounding box.
00511   // Parameters:
00512   //   bbox - [in/out] 3d axis aligned bounding box
00513   //   bGrowBox - [in] (default=false) 
00514   //     If true, then the union of the input bbox and the 
00515   //     point list's bounding box is returned in bbox.  
00516   //     If false, the point list's bounding box is returned in bbox.
00517   // Returns:
00518   //   true if successful.
00519   bool GetBoundingBox( 
00520     ON_BoundingBox& bbox,
00521     int bGrowBox = false
00522     ) const;
00523 
00524   // Description:
00525   //   Get axis aligned bounding box.
00526   // Parameters:
00527   //   boxmin - [in/out] array of 3 doubles
00528   //   boxmax - [in/out] array of 3 doubles
00529   //   bGrowBox - [in] (default=false) 
00530   //     If true, then the union of the input bounding box and the 
00531   //     object's bounding box is returned.
00532   //     If false, the object's bounding box is returned.
00533   // Returns:
00534   //   true if object has bounding box and calculation was successful
00535   bool GetBBox(
00536          double boxmin[3],
00537          double boxmax[3],
00538          int bGrowBox = false
00539          ) const;
00540 
00541   /*
00542         Description:
00543     Get tight bounding box of the point list.
00544         Parameters:
00545                 tight_bbox - [in/out] tight bounding box
00546                 bGrowBox -[in]  (default=false)                 
00547       If true and the input tight_bbox is valid, then returned
00548       tight_bbox is the union of the input tight_bbox and the 
00549       tight bounding box of the point list.
00550                 xform -[in] (default=NULL)
00551       If not NULL, the tight bounding box of the transformed
00552       point list is calculated.  The point list is not modified.
00553         Returns:
00554     True if the returned tight_bbox is set to a valid 
00555     bounding box.
00556   */
00557         bool GetTightBoundingBox( 
00558                         ON_BoundingBox& tight_bbox, 
00559       int bGrowBox = false,
00560                         const ON_Xform* xform = 0
00561       ) const;
00562 
00563   // Description:
00564   //   Transform points by applying xform to each point.
00565   // Parameters:
00566   //   xform - [in] transformation matrix
00567   // Returns:
00568   //   true if successful.
00569   bool Transform( 
00570     const ON_Xform& xform 
00571     );
00572 
00573   // Description:
00574   //   Swaps point coordinate values with indices i and j.
00575   // Parameters:
00576   //   i - [in] coordinate index
00577   //   j - [in] coordinate index
00578   // Returns:
00579   //   true if successful.
00580   // Example:
00581   //   The call SwapCoordinates(0,2) would swap the x and z
00582   //   coordinates of each point in the array.
00583   bool SwapCoordinates(
00584     int i,
00585     int j
00586     );
00587 
00588   // Description:
00589   //   Rotate points about a center and axis.  A positive angle
00590   //   results in a counter-clockwise rotation about the axis
00591   //   of rotation.
00592   // Parameters:
00593   //   sin_angle - [in] sine of rotation angle
00594   //   cos_angle - [in] cosine of rotation angle
00595   //   axis_of_rotation - [in] axis of rotation
00596   //   center_of_rotation - [in] center (fixed point) of rotation
00597   // Returns:
00598   //   true if successful.
00599   bool Rotate(
00600         double sin_angle,
00601         double cos_angle,
00602         const ON_3dVector& axis_of_rotation,
00603         const ON_3dPoint& center_of_rotation
00604         );
00605 
00606   // Description:
00607   //   Rotate points about a center and axis.  A positive angle
00608   //   results in a counter-clockwise rotation about the axis
00609   //   of rotation.
00610   // Parameters:
00611   //   angle - [in] angle in radians.  Polsine of rotation angle
00612   //   cos_angle - [in] cosine of rotation angle
00613   //   axis_of_rotation - [in] axis of rotation
00614   //   center_of_rotation - [in] center (fixed point) of rotation
00615   // Returns:
00616   //   true if successful.
00617   bool Rotate(
00618         double angle_in_radians,
00619         const ON_3dVector& axis_of_rotation,
00620         const ON_3dPoint& center_of_rotation
00621         );
00622 
00623   // Description:
00624   //   Translate a polyline
00625   // Parameters:
00626   //   delta - [in] translation vectorsine of rotation angle
00627   // Returns:
00628   //   true if successful.
00629   bool Translate(
00630         const ON_3dVector& delta
00631         );
00632 
00633   /*
00634   Description:
00635     Get the index of the point in the array that is closest
00636     to P.
00637   Parameters:
00638     P - [in]
00639     closest_point_index - [out]
00640     maximum_distance - [in] optional distance constraint.
00641         If maximum_distance > 0, then only points Q with
00642         |P-Q| <= maximum_distance are returned.
00643   Returns:
00644     True if a point is found; in which case *closest_point_index
00645     is the index of the point.  False if no point is found
00646     or the input is not valid.
00647   See Also:
00648     ON_GetClosestPointInPointList
00649     ON_PointCloud::GetClosestPoint
00650   */
00651   bool GetClosestPoint( 
00652           ON_3dPoint P,
00653           int* closest_point_index,
00654           double maximum_distance = 0.0
00655           ) const;
00656 
00657 };
00658 
00659 
00661 //
00662 
00663 class ON_CLASS ON_3fPointArray : public ON_SimpleArray<ON_3fPoint>
00664 {
00665 public:
00666   // see ON_SimpleArray class definition comments for constructor documentation
00667   ON_3fPointArray();
00668   ON_3fPointArray(int);
00669   ON_3fPointArray(const ON_3fPointArray&);
00670   ON_3fPointArray& operator=( const ON_3fPointArray& );
00671 
00672   bool GetBBox(
00673          float boxmin[3],
00674          float boxmax[3],
00675          int bGrowBox = false
00676          ) const;
00677 
00678   bool Transform( const ON_Xform& );
00679 
00680   bool SwapCoordinates(int,int);
00681 };
00682 
00683 
00685 //
00686 
00687 class ON_CLASS ON_4dPointArray : public ON_SimpleArray<ON_4dPoint>
00688 {
00689 public:
00690   // see ON_SimpleArray class definition comments for constructor documentation
00691   ON_4dPointArray();
00692   ON_4dPointArray(int);
00693   ON_4dPointArray(const ON_4dPointArray&);
00694   ON_4dPointArray& operator=( const ON_4dPointArray& );
00695 
00696   bool Transform( const ON_Xform& );
00697   bool SwapCoordinates(int,int);
00698 };
00699 
00700 
00702 //
00703 
00704 class ON_CLASS ON_4fPointArray : public ON_SimpleArray<ON_4fPoint>
00705 {
00706 public:
00707   // see ON_SimpleArray class definition comments for constructor documentation
00708   ON_4fPointArray();
00709   ON_4fPointArray(int);
00710   ON_4fPointArray(const ON_4fPointArray&);
00711   ON_4fPointArray& operator=( const ON_4fPointArray& );
00712 
00713   bool Transform( const ON_Xform& );
00714   bool SwapCoordinates(int,int);
00715 };
00716 
00717 
00719 //
00720 
00721 class ON_CLASS ON_2dVectorArray : public ON_SimpleArray<ON_2dVector>
00722 {
00723 public:
00724   // see ON_SimpleArray class definition comments for constructor documentation
00725   ON_2dVectorArray();
00726   ON_2dVectorArray(int);
00727   ON_2dVectorArray(const ON_2dVectorArray&);
00728   ON_2dVectorArray& operator=( const ON_2dVectorArray& );
00729 
00730   bool GetBBox(
00731          double boxmin[2],
00732          double boxmax[2],
00733          int bGrowBox = false
00734          ) const;
00735 
00736   bool Transform( const ON_Xform& );
00737   bool SwapCoordinates(int,int);
00738 };
00739 
00740 
00742 //
00743 
00744 class ON_CLASS ON_2fVectorArray : public ON_SimpleArray<ON_2fVector>
00745 {
00746 public:
00747   // see ON_SimpleArray class definition comments for constructor documentation
00748   ON_2fVectorArray();
00749   ON_2fVectorArray(int);
00750   ON_2fVectorArray(const ON_2fVectorArray&);
00751   ON_2fVectorArray& operator=( const ON_2fVectorArray& );
00752 
00753   bool GetBBox(
00754          float boxmin[2],
00755          float boxmax[2],
00756          bool = false
00757          ) const;
00758 
00759   bool Transform( const ON_Xform& );
00760   bool SwapCoordinates(int,int);
00761 };
00762 
00763 
00765 //
00766 
00767 class ON_CLASS ON_3dVectorArray : public ON_SimpleArray<ON_3dVector>
00768 {
00769 public:
00770   ON_3dVectorArray();
00771   ON_3dVectorArray(int);
00772   ON_3dVectorArray(const ON_3dVectorArray&);
00773   ON_3dVectorArray& operator=( const ON_3dVectorArray& );
00774 
00775   bool GetBBox(
00776          double boxmin[3],
00777          double boxmax[3],
00778          bool bGrowBow = false
00779          ) const;
00780 
00781   bool Transform( const ON_Xform& );
00782   bool SwapCoordinates(int,int);
00783 };
00784 
00786 //
00787 
00788 class ON_CLASS ON_3fVectorArray : public ON_SimpleArray<ON_3fVector>
00789 {
00790 public:
00791   ON_3fVectorArray();
00792   ON_3fVectorArray(int);
00793   ON_3fVectorArray(const ON_3fVectorArray&);
00794   ON_3fVectorArray& operator=( const ON_3fVectorArray& );
00795 
00796   bool GetBBox(
00797          float boxmin[3],
00798          float boxmax[3],
00799          int bGrowBox = false
00800          ) const;
00801 
00802   bool Transform( const ON_Xform& );
00803   bool SwapCoordinates(int,int);
00804 };
00805 
00807 //
00808 // The ON_ClassArray<> template is designed to be used with
00809 // classes that require non-trivial construction or destruction.
00810 // Any class used with the ON_ClassArray<> template must have a
00811 // robust operator=().
00812 //
00813 // By default, ON_ClassArray<> uses onrealloc() to manage
00814 // the dynamic array memory. If you want to use something 
00815 // besides onrealloc() to manage the array memory, then override
00816 // ON_ClassArray::Realloc().  In practice this means that if your
00817 // class has members with back-pointers, then you cannot use
00818 // it in the defaule ON_ClassArray.  See ON_ObjectArray
00819 // for an example.
00820 //
00821 template <class T> class ON_ClassArray
00822 {
00823 public:
00824   // construction ////////////////////////////////////////////////////////
00825   ON_ClassArray(); 
00826   ON_ClassArray( int ); // int = initial capacity
00827 
00828   // Copy constructor
00829   ON_ClassArray( const ON_ClassArray<T>& );
00830 
00831   virtual
00832   ~ON_ClassArray(); // override for struct member deallocation, etc.
00833 
00834   // Assignment operator
00835   ON_ClassArray<T>& operator=( const ON_ClassArray<T>& );
00836   
00837   // emergency bailout ///////////////////////////////////////////////////
00838   void EmergencyDestroy(void); // call only when memory used by this array
00839                                // may have become invalid for reasons beyond
00840                                // your control. EmergencyDestroy() zeros
00841                                // anything that could possibly cause
00842                                // ~ON_ClassArray() to crash.
00843 
00844   // query ///////////////////////////////////////////////////////////////
00845   
00846         int Count() const;      // number of elements in array
00847         unsigned int UnsignedCount() const;
00848 
00849         int Capacity() const;  // capacity of array
00850 
00851   unsigned int SizeOfArray() const; // amount of memory in the m_a[] array
00852 
00853   unsigned int SizeOfElement() const; // amount of memory in an m_a[] array element
00854 
00855   // The operator[] does to not check for valid indices.
00856   // The caller is responsibile for insuring that 0 <= i < Capacity()
00857   T& operator[]( int );
00858   T& operator[]( unsigned int );
00859   T& operator[]( ON__INT64 );
00860   T& operator[]( ON__UINT64 );
00861   const T& operator[]( int ) const;
00862   const T& operator[]( unsigned int ) const;  
00863   const T& operator[]( ON__INT64 ) const;
00864   const T& operator[]( ON__UINT64 ) const;  
00865 
00866   operator T*();                     // The cast operators return a pointer
00867   operator const T*() const;         // to the array.  If Count() is zero,
00868                                      // this pointer is NULL.
00869   T* First();
00870   const T* First() const;             // returns NULL if count = 0
00871 
00872   // At(index) returns NULL if index < 0 or index >= count
00873   T* At( int );
00874   T* At( unsigned int );
00875   T* At( ON__INT64 );
00876   T* At( ON__UINT64 );
00877   const T* At( int ) const;
00878   const T* At( unsigned int ) const;
00879   const T* At( ON__INT64 ) const;
00880   const T* At( ON__UINT64 ) const;
00881 
00882   T* Last();
00883   const T* Last() const;             // returns NULL if count = 0
00884 
00885   
00886   // array operations ////////////////////////////////////////////////////
00887 
00888   T& AppendNew();                    // Most efficient way to add a new class 
00889                                      // to the array.  Increases count by 1.
00890 
00891   void Append( const T& );           // Append copy of element.
00892                                      // Increments count by 1.
00893 
00894   void Append( int, const T*);       // Append copy of an array T[count]
00895 
00896   void Insert( int, const T& );      // Insert copy of element. Uses
00897                                      // memmove() to perform any
00898                                      // necessary moving.
00899                                      // Increases count by 1.
00900 
00901   void Remove();                     // Removes last element.  Decrements
00902                                      // count by 1.  Does not change capacity.
00903 
00904   void Remove( int );                // Removes element. Uses memmove() to
00905                                      // perform any necessary shifting.
00906                                      // Decrements count by 1.  Does not change
00907                                      // capacity
00908 
00909   void Empty();           // Sets count to 0, leaves capacity untouched.
00910 
00911   void Reverse();         // reverse order
00912 
00913   void Swap(int,int);     // swap elements i and j
00914 
00916   // Search( p, compare ) does a SLOW search of the array starting
00917   // at array[0] and returns the index "i" of the first element 
00918   // that satisfies  compare(p,&array[i])==0.  If the search is not
00919   // successful, then Search() returns -1.  Search() is only suitable
00920   // for performing infrequent searches of small arrays.  Sort the
00921   // array and use BinarySearch() for performing efficient searches.
00922   int Search( const T*, int (*)(const T*,const T*) ) const;
00923 
00925   // BinarySearch( p, compare ) does a fast search of a sorted array
00926   // and returns the smallest index "i" of the element that satisifies
00927   // 0==compare(p,&array[i]).
00928   //
00929   // BinarySearch( p, compare, count ) does a fast search of the first
00930   // count element sorted array and returns the smallest index "i" of 
00931   // the element that satisifies 0==compare(p,&array[i]).  The version
00932   // that takes a "count" is useful when elements are being appended
00933   // during a calculation and the appended elements are not sorted.
00934   //
00935   // If the search is successful, 
00936   // BinarySearch() returns the index of the element (>=0).
00937   // If the search is not successful, BinarySearch() returns -1.
00938   // Use QuickSort( compare ) or, in rare cases and after meaningful
00939   // performance testing using optimzed release builds, 
00940   // HeapSort( compare ) to sort the array.
00941         // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
00942   int BinarySearch( const T*, int (*)(const T*,const T*) ) const;
00943   int BinarySearch( const T*, int (*)(const T*,const T*), int ) const;
00944 
00946   // Sorts the array using the heap sort algorithm.
00947         // See Also: ON_CompareIncreasing<T> and ON_CompareDeccreasing<T>
00948   // QuickSort() is generally the better choice.
00949   virtual
00950   bool HeapSort( int (*)(const T*,const T*) );
00951 
00953   // Sorts the array using the heap sort algorithm.
00954   virtual
00955   bool QuickSort( int (*)(const T*,const T*) );
00956 
00957   /*
00958   Description:
00959     Sort() fills in the index[] array so that 
00960     array[index[i]] <= array[index[i+1]].  
00961     The array is not modified.  
00962 
00963   Parameters:
00964     sort_algorithm - [in]  
00965       ON::quick_sort (best in general) or ON::heap_sort
00966       Use ON::heap_sort only if you have done extensive testing with
00967       optimized release builds and are confident heap sort is 
00968       significantly faster.
00969     index - [out] an array of length Count() that is returned with
00970         some permutation of (0,1,...,Count()-1). 
00971     compare - [in] compare function compare(a,b) should return
00972         <0 if a<b, 0, if a==b, and >0 if a>b.
00973 
00974   Returns:
00975     true if successful
00976   */
00977   bool Sort( 
00978     ON::sort_algorithm sort_algorithm, 
00979     int* /* index[] */ ,
00980     int (*)(const T*,const T*)
00981     ) const; 
00982 
00983   /*
00984   Description:
00985     Sort() fills in the index[] array so that 
00986     array[index[i]] <= array[index[i+1]].  
00987     The array is not modified.  
00988 
00989   Parameters:
00990     sort_algorithm - [in]  
00991       ON::quick_sort (best in general) or ON::heap_sort
00992       Use ON::heap_sort only if you have done extensive testing with
00993       optimized release builds and are confident heap sort is 
00994       significantly faster.
00995     index - [out] an array of length Count() that is returned with
00996         some permutation of (0,1,...,Count()-1). 
00997     compare - [in] compare function compare(a,b,p) should return
00998         <0 if a<b, 0, if a==b, and >0 if a>b.
00999     p - [in] pointer passed as third argument to compare.
01000 
01001   Returns:
01002     true if successful
01003   */
01004   bool Sort( 
01005     ON::sort_algorithm sort_algorithm,
01006     int*, // index[] 
01007     int (*)(const T*,const T*,void*), // int compare(const T*,const T*,void* p)
01008     void* // p
01009     ) const; 
01010 
01012   // Permutes the array so that output[i] = input[index[i]].
01013   // The index[] array should be a permutation of (0,...,Count()-1).
01014   bool Permute( const int* /*index[]*/ );
01015 
01017   // Destroys all elements and fills them with values
01018   // set by the defualt constructor.
01019   // Count and capacity are not changed.
01020   void Zero();
01021 
01022   // memory managment /////////////////////////////////////////////////
01023 
01024   void Reserve( int ); // increase capacity to at least the requested value
01025 
01026   void Shrink();       // remove unused capacity
01027 
01028   void Destroy();      // onfree any memory and set count and capacity to zero
01029     
01030   // low level memory managment ///////////////////////////////////////
01031 
01032   // By default, ON_ClassArray<> uses onrealloc() to manage
01033   // the dynamic array memory. If you want to use something 
01034   // besides onrealloc() to manage the array memory, then override 
01035   // Realloc(). The T* Realloc(ptr, capacity) should do the following:
01036   //
01037   // 1) If ptr and capacity are zero, return NULL.
01038   // 2) If ptr is NULL, an capacity > 0, allocate a memory block of 
01039   //    capacity*sizeof(T) bytes and return a pointer to this block.
01040   //    If the allocation request fails, return NULL.
01041   // 3) If ptr is not NULL and capacity is 0, free the memory block
01042   //    pointed to by ptr and return NULL.
01043   // 4) If ptr is not NULL and capacity > 0, then reallocate the memory
01044   //    block and return a pointer to the reallocated block.  If the 
01045   //    reallocation request fails, return NULL.
01046   //
01047   // NOTE WELL: 
01048   //    Microsoft's VC 6.0 realloc() contains a bug that can cause
01049   //    crashes and should be avoided. See MSDN Knowledge Base article
01050   //    ID Q225099 for more information.
01051   virtual
01052   T* Realloc(T*,int); // (re)allocated capacity*sizeof(T) bytes
01053 
01054   T* Array();                         // The Array() function return the 
01055   
01056   const T* Array() const;             // m_a pointer value.
01057 
01058   void SetCount( int );               // If value is <= Capacity(), then
01059                                       // sets count to specified value.
01060 
01061   void SetCapacity( int );            // Shrink/grows capacity.  If value
01062                                       // is < current Count(), then count
01063                                       // is reduced to value.
01064 
01065   int NewCapacity() const;            // When the dynamic array needs to grow,
01066                                       // this calculates the new value for m_capacity.
01067 
01068   T* KeepArray();                     // returns pointer to array and zeros
01069                                       // out this class.  Caller is responsible
01070                                       // for calling destructor on each element
01071                                       // and then using onfree() to release array
01072                                       // memory.  E.g.,
01073                                       //
01074                                       //   for (int i=capacity;i>=0;i--) {
01075                                       //     array[i].~T();
01076                                       //   }
01077                                       //   onfree(array);
01078 
01079   /*
01080   Description:
01081     Do not use this version of SetArray().  Use the one that takes
01082     a pointer, count and capacity: SetArray(pointer,count,capacity)
01083   */
01084   void SetArray(T*);
01085 
01086   /*
01087   Description:
01088     Expert user tool to set the memory used by the dyanmic array.
01089   Parameters:
01090     T* pointer - [in]
01091     int count - [in]  0 <= count <= capacity
01092     int capacity - [in]
01093        m_a is set to pointer, m_count is set to count, and m_capacity
01094        is set to capacity.  It is critical that the pointer be one 
01095        returned by onmalloc(sz), where sz >= capacity*sizeof(T[0]),
01096        and that the in-place operator new has been used to initialize
01097        each element of the array.  
01098   */
01099   void SetArray(T*, int, int);
01100 
01101 protected:
01102   // implimentation //////////////////////////////////////////////////////
01103   void Move( int /* dest index*/, int /* src index */, int /* element count*/ );
01104   void ConstructDefaultElement(T*);
01105   void DestroyElement(T&);
01106         T*   m_a;        // pointer to array memory
01107         int  m_count;    // 0 <= m_count <= m_capacity
01108         int  m_capacity; // actual length of m_a[]
01109 };
01110 
01111 
01112 /*
01113 Description:
01114   ON_Object array is used to store lists of classes that are
01115   derived from ON_Object.  It differs from ON_ClassArray in
01116   that the virtual ON_Object::MemoryRelocate function is called
01117   when growing the dynamic array requires changing the location
01118   of the memory buffer used to store the elements in the array.
01119 */
01120 template <class T> class ON_ObjectArray : public ON_ClassArray<T>
01121 {
01122 public:
01123   ON_ObjectArray(); 
01124   ~ON_ObjectArray(); // override for struct member deallocation, etc.
01125   ON_ObjectArray( int ); // int = initial capacity
01126   ON_ObjectArray( const ON_ObjectArray<T>& );
01127   ON_ObjectArray<T>& operator=( const ON_ObjectArray<T>& );
01128 
01129   ON__UINT32 DataCRC(ON__UINT32 current_remainder) const;
01130 
01131   // virtual ON_ClassArray<T> override that 
01132   // calls MemoryRelocate on each element after
01133   // the reallocation.
01134   T* Realloc(T*,int);
01135 
01136   // virtual ON_ClassArray<T> override that 
01137   // calls MemoryRelocate on each element after
01138   // the heap sort.
01139   // QuickSort() is generally the better choice.
01140   bool HeapSort( int (*)(const T*,const T*) );
01141 
01142   // virtual ON_ClassArray<T> override that 
01143   // calls MemoryRelocate on each element after
01144   // the quick sort.
01145   bool QuickSort( int (*)(const T*,const T*) );
01146 };
01147 
01148 class ON_CLASS ON_UuidPair
01149 {
01150 public:
01151   /*
01152   Description:
01153     Compares m_uuid[0] and ignores m_uuid[1]
01154   */
01155   static 
01156   int CompareFirstUuid(const class ON_UuidPair*,const class ON_UuidPair*);
01157 
01158   /*
01159   Description:
01160     Compares m_uuid[1] and ignores m_uuid[0]
01161   */
01162   static 
01163   int CompareSecondUuid(const class ON_UuidPair*,const class ON_UuidPair*);
01164 
01165   /*
01166   Description:
01167     Compares m_uuid[0] then m_uuid[1].
01168   */
01169   static 
01170   int Compare(const class ON_UuidPair*,const class ON_UuidPair*);
01171 
01172   ON_UuidPair();
01173   ON_UUID m_uuid[2];
01174 };
01175 
01176 #if defined(ON_DLL_TEMPLATE)
01177 
01178 // This stuff is here because of a limitation in the way Microsoft
01179 // handles templates and DLLs.  See Microsoft's knowledge base 
01180 // article ID Q168958 for details.
01181 #pragma warning( push )
01182 #pragma warning( disable : 4231 )
01183 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UUID>;
01184 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidIndex>;
01185 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_DisplayMaterialRef>;
01186 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_LinetypeSegment>;
01187 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_UuidPair>;
01188 ON_DLL_TEMPLATE template class ON_CLASS ON_SimpleArray<ON_PlaneEquation>;
01189 ON_DLL_TEMPLATE template class ON_CLASS ON_ClassArray<ON_SimpleArray<int> >;
01190 #pragma warning( pop )
01191 
01192 #endif
01193 
01194 
01195 /*
01196 Description:
01197   The ON_UuidList class provides a tool to efficiently 
01198   maintain a list of uuids and determine if a uuid is 
01199   in the list. This class is based on the premise that 
01200   there are no duplicate uuids in the list.
01201 */
01202 class ON_CLASS ON_UuidList : private ON_SimpleArray<ON_UUID>
01203 {
01204 public:
01205   ON_UuidList();
01206   ON_UuidList(int capacity);
01207   ~ON_UuidList();
01208   ON_UuidList(const ON_UuidList& src);
01209   ON_UuidList& operator=(const ON_UuidList& src);
01210 
01211   /*
01212   Description:
01213     Fast uuid compare.  Not necessarily the same
01214     as ON_UuidCompare().
01215   */
01216   static
01217   int CompareUuid( const ON_UUID* a, const ON_UUID* b );
01218 
01219   /*
01220   Returns:
01221     Number of active uuids in the list.
01222   */
01223   int Count() const;
01224 
01225   /*
01226   Returns:
01227     Array of uuids in the list.  Sorted with
01228     respect to ON_UuidList::CompareUuid().
01229   Remarks:
01230     Calling AddUuid() may grow the dynamic array
01231     and make the pointer invalid.
01232   */
01233   const ON_UUID* Array() const;
01234 
01235   /*
01236   Description:
01237     Provides an efficient way to empty a list so that it
01238     can be used again.
01239   */
01240   void Empty();
01241 
01242   /*
01243   Description:
01244     Destroy list.  If list will be reused, Empty() is more
01245     efficient.
01246   */
01247   void Destroy();
01248 
01249   void Reserve(int capacity);
01250 
01251   /*
01252   Description:
01253     Makes the uuid list as efficent as possible in both search
01254     speed and memory usage.  Use Compact() when a uuid list
01255     will be in use but is not likely to be modifed.  A list 
01256     that has been compacted can still be modified.
01257   */
01258   void Compact();
01259 
01260   /*
01261   Description:
01262     Adds a uuid to the list.
01263   Parameters:
01264     uuid - [in] id to add.
01265     bCheckForDupicates - [in] if true, then the uuid
01266        is not added if it is already in the list.
01267        If you are certain that the uuid is not in the
01268        list and you are going to have a large list of uuids,
01269        then setting bCheckForDupicates=false will
01270        speed up the addition of uuids.
01271   Returns:
01272     True if uuid was added.  False if uuid was not added
01273     because it is already in the collection.
01274   */
01275   bool AddUuid(ON_UUID uuid, bool bCheckForDupicates=true);
01276 
01277   /*
01278   Description:
01279     Removes a uuid from the list.
01280   Parameters:
01281     uuid - [in] id to remove
01282   Returns:
01283     True if uuid was in the list and was removed.
01284     False if uuid was not in the list.
01285   */
01286   bool RemoveUuid(ON_UUID uuid);
01287 
01288   /*
01289   Description:
01290     Determine if a uuid is in the list.
01291   Returns:
01292     True if uuid is in the list.
01293   */
01294   bool FindUuid(ON_UUID uuid) const;
01295 
01296   /*
01297   Description:
01298     Saves the uuid list in an archive.
01299   Parameters:
01300     archive - [in] archive to write to.
01301   Returns:
01302     true if write was successful.
01303   */
01304   bool Write( 
01305     class ON_BinaryArchive& archive 
01306     ) const;
01307 
01308   /*
01309   Description:
01310     Read the uuid list from an archive.
01311   Parameters:
01312     archive - [in] archive to read from.
01313   Returns:
01314     true if the read was successful.
01315   */
01316   bool Read( 
01317     class ON_BinaryArchive& archive 
01318     );
01319 
01320   /*
01321   Description:
01322     Append the uuids in this class to uuid_list.
01323   Parameters:
01324     uuid_list - [in/out]
01325   Returns:
01326     Number of uuids added to uuid_list.
01327   */
01328   int GetUuids(
01329      ON_SimpleArray<ON_UUID>& uuid_list
01330      ) const;
01331 
01332   /*
01333   Description:
01334     This tool is used in rare situations when the object ids 
01335     stored in the uuid list need to be remapped.
01336   Parameters:
01337     uuid_remap - [in]
01338       Is it critical that uuid_remap[] be sorted with respect
01339       to ON_UuidPair::CompareFirstUuid.
01340   */
01341   void RemapUuids( 
01342     const ON_SimpleArray<ON_UuidPair>& uuid_remap 
01343     );
01344 
01345 private:
01346   void SortHelper();
01347   ON_UUID* SearchHelper(const ON_UUID*) const;
01348   int m_sorted_count;
01349   int m_removed_count;
01350 };
01351 
01352 /*
01353 Description:
01354   The ON_UuidList class provides a tool
01355   to efficiently maintain a list of uuid-index
01356   pairs and determine if a uuid is in the list.
01357   This class is based on the premise that there are
01358   no duplicate uuids in the list.
01359 */
01360 class ON_CLASS ON_UuidIndexList : private ON_SimpleArray<ON_UuidIndex>
01361 {
01362 public:
01363   ON_UuidIndexList();
01364   ON_UuidIndexList(int capacity);
01365   ~ON_UuidIndexList();
01366   ON_UuidIndexList(const ON_UuidIndexList& src);
01367   ON_UuidIndexList& operator=(const ON_UuidIndexList& src);
01368 
01369   /*
01370   Returns:
01371     Number of active uuids in the list.
01372   */
01373   int Count() const;
01374 
01375   /*
01376   Description:
01377     Provides an efficient way to empty a list so that it
01378     can be used again.
01379   */
01380   void Empty();
01381 
01382   void Reserve( int capacity );
01383 
01384   /*
01385   Description:
01386     Adds a uuid-index pair to the list.
01387   Parameters:
01388     uuid - [in] id to add.  
01389       This uuid cannot be ON_max_uuid because ON_max_uuid
01390       is 
01391     bCheckForDupicates - [in] if true, then the uuid
01392        is not added if it is already in the list.
01393        If you are certain that the uuid is not in the list
01394        and you have a have a large collection of uuids,
01395        then setting bCheckForDupicates=false will
01396        speed up the addition of uuids.
01397   Returns:
01398     True if uuid was added.  False if uuid was not added
01399     because it is already in the collection.
01400   */
01401   bool AddUuidIndex(
01402     ON_UUID uuid, 
01403     int index, 
01404     bool bCheckForDupicates=true);
01405 
01406   /*
01407   Description:
01408     Removes an element with a matching uuid from the list.
01409   Parameters:
01410     uuid - [in] id to remove
01411   Returns:
01412     True if an element was removed.  False if the uuid
01413     was not in the list.
01414   */
01415   bool RemoveUuid(
01416     ON_UUID uuid
01417     );
01418 
01419   /*
01420   Description:
01421     Determine if an element with a uuid is in the list.
01422   Parameters:
01423     index - [out] if not NULL and a matching uuid is found,
01424        then *index is set to the value of the index.
01425   Returns:
01426     True if an element was found.  Returns false if
01427     the uuid is not in the list.
01428   */
01429   bool FindUuid(ON_UUID uuid, int* index=NULL) const;
01430 
01431   /*
01432   Description:
01433     Determine if a uuid-index pair is in the list.
01434   Returns:
01435     True if the uuid-index pair is in the list.
01436     Returns false if the uuid-index pair is not
01437     in the list.
01438   */
01439   bool FindUuidIndex(ON_UUID uuid, int index) const;
01440 
01441   /*
01442   Description:
01443     Append the uuids in this class to uuid_list.
01444   Parameters:
01445     uuid_list - [in/out]
01446   Returns:
01447     Number of uuids added to uuid_list.
01448   */
01449   int GetUuids(
01450      ON_SimpleArray<ON_UUID>& uuid_list
01451      ) const;
01452 
01453   /*
01454   Description:
01455     If you will perform lots of searches before the next
01456     change to the list, then calling ImproveSearchSpeed()
01457     will speed up the searches by culling removed objects
01458     and completely sorting the list so only a binary search
01459     is required. You may edit the list at any time after 
01460     calling ImproveSearchSpeed().  If you are performing 
01461     a few searches between edits, then excessive calling
01462     of ImproveSearchSpeed() may actually decrease overall
01463     program performance.
01464   */
01465   void ImproveSearchSpeed();
01466 
01467 private:
01468   ON_UuidIndex* SearchHelper(const ON_UUID*) const;
01469   unsigned int m_sorted_count;
01470   unsigned int m_removed_count;
01471 };
01472 
01473 /*
01474 Description:
01475   The ON_UuidPairList class provides a tool
01476   to efficiently maintain a list of uuid pairs 
01477   and determine if a uuid is in the list.
01478   This class is based on the premise that there are
01479   no duplicate uuids in the list.
01480 */
01481 class ON_CLASS ON_UuidPairList : private ON_SimpleArray<ON_UuidPair>
01482 {
01483 public:
01484   ON_UuidPairList();
01485   ON_UuidPairList(int capacity);
01486   ~ON_UuidPairList();
01487   ON_UuidPairList(const ON_UuidPairList& src);
01488   ON_UuidPairList& operator=(const ON_UuidPairList& src);
01489 
01490   /*
01491   Returns:
01492     Number of active uuids in the list.
01493   */
01494   int Count() const;
01495 
01496   /*
01497   Description:
01498     Provides an efficient way to empty a list so that it
01499     can be used again.
01500   */
01501   void Empty();
01502 
01503   void Reserve( int capacity );
01504 
01505   /*
01506   Description:
01507     Adds a uuid-index pair to the list.
01508   Parameters:
01509     id1 - [in] id to add.
01510     id2 - [in] id to add.
01511     bCheckForDupicates - [in] if true, then the pair
01512        is not added if id1 is already in the list.
01513        If you are certain that the id1 is not in the list
01514        and you have a have a large collection of uuids,
01515        then setting bCheckForDupicates=false will
01516        speed up the addition of uuids.
01517   Returns:
01518     True if the pair was added.  False if the pair was not added
01519     because it is already in the collection.
01520   Remarks:
01521     You cannot add the pair value ( ON_max_uuid, ON_max_uuid ). This
01522     pair value is used to mark removed elements in the ON_UuidPairList[].
01523   */
01524   bool AddPair(
01525     ON_UUID id1, 
01526     ON_UUID id2, 
01527     bool bCheckForDupicates=true
01528     );
01529 
01530   /*
01531   Description:
01532     Removes an element with a matching id1 from the list.
01533   Parameters:
01534     id1 - [in] id to remove
01535   Returns:
01536     True if an element was removed.  False if the id1
01537     was not in the list.
01538   */
01539   bool RemovePair(
01540     ON_UUID id1
01541     );
01542 
01543   /*
01544   Description:
01545     Removes an element with a matching id pair from the list.
01546   Parameters:
01547     id1 - [in]
01548     id2 - [in]
01549   Returns:
01550     True if an element was removed.  False if the id pair
01551     does not appear in the list.
01552   */
01553   bool RemovePair(
01554     ON_UUID id1,
01555     ON_UUID id2
01556     );
01557 
01558   /*
01559   Description:
01560     Determine if an element with a uuid is in the list.
01561   Parameters:
01562     id1 - [in]
01563     id2 - [out] if not NULL and a matching id1 is found,
01564        then *id2 is set to the value of the second uuid.
01565   Returns:
01566     True if an element was found.  Returns false if
01567     the id1 is not in the list.
01568   */
01569   bool FindId1(ON_UUID id1, ON_UUID* id2=0) const;
01570 
01571   /*
01572   Description:
01573     Determine if an id pair is in the list.
01574   Returns:
01575     True if the id pair is in the list.
01576     False if the id pair is not in the list.
01577   */
01578   bool FindPair(ON_UUID id1, ON_UUID id2) const;
01579 
01580   /*
01581   Description:
01582     Append the value of the first id in each pair to uuid_list[].
01583   Parameters:
01584     uuid_list - [in/out]
01585   Returns:
01586     Number of ids appended to uuid_list[].
01587   */
01588   int GetId1s(
01589      ON_SimpleArray<ON_UUID>& uuid_list
01590      ) const;
01591 
01592   /*
01593   Description:
01594     If you will perform lots of searches before the next
01595     change to the list, then calling ImproveSearchSpeed()
01596     will speed up the searches by culling removed objects
01597     and completely sorting the list so only a binary search
01598     is required. You may edit the list at any time after 
01599     calling ImproveSearchSpeed().  If you are performing 
01600     a few searches between edits, then excessive calling
01601     of ImproveSearchSpeed() may actually decrease overall
01602     program performance.
01603   */
01604   void ImproveSearchSpeed();
01605 
01606 private:
01607   ON_UuidPair* SearchHelper(const ON_UUID*) const;
01608   unsigned int m_sorted_count;
01609   unsigned int m_removed_count;
01610 };
01611 
01612 class ON_CLASS ON_2dexMap : private ON_SimpleArray<ON_2dex>
01613 {
01614 public:
01615   ON_2dexMap();
01616   ON_2dexMap(int capacity);
01617   ~ON_2dexMap();
01618 
01619   int Count() const;
01620 
01621   void Reserve(int capacity);
01622 
01623   const ON_2dex* Array() const;
01624 
01625   ON_2dex operator[](int i) const;
01626 
01627   /*
01628   Description:
01629     Creates an index map with the values
01630     (i0,j),...,(i0+count-1,j)
01631   Parameters:
01632     count - [in]
01633        number of elements
01634     i0 - [in]
01635        i value of first element
01636     j - [in]
01637        j value for all elements
01638   */
01639   void Create(int count, int i0, int j);
01640 
01641   /*
01642   Description:
01643     Searches for an element with a matching i
01644     and returns its j value.  If no matching
01645     element is found, then not_found_rc is returned. 
01646   Parameters:
01647     i - [in]
01648        value of i to search for
01649     not_found_rc - [in]
01650        value to return if there is not a match.
01651   Returns:
01652     j value
01653   */
01654   int FindIndex( 
01655           int i, 
01656           int not_found_rc
01657           ) const;
01658 
01659   /*
01660   Description:
01661     Adds and element (i,j).  If there is already an entry with
01662     value (i,*), then no element is added.
01663   Parameters:
01664     i - [in]
01665     i - [in]
01666   Returns:
01667     True if and element it added.
01668   */
01669   bool AddIndex( 
01670           int i, 
01671           int j
01672           );
01673 
01674   /*
01675   Description:
01676     Searches for an element (i,*) and sets its j value to j.
01677     If there is no element with a matching i, then false
01678     is returned.
01679   Parameters:
01680     i - [in]
01681     j - [in]
01682   Returns:
01683     True if and element exists and was set.
01684   */
01685   bool SetIndex( 
01686           int i, 
01687           int j
01688           );
01689 
01690   /*
01691   Description:
01692     If an element (i,*) exists, its j value is set.  Otherwise
01693     a new element with value (i,j) is added.
01694   Parameters:
01695     i - [in]
01696     j - [in]
01697   */
01698   void SetOrAddIndex( 
01699           int i, 
01700           int j
01701           );
01702 
01703   /*
01704   Description:
01705     If an element (i,*) exists, it is removed.  If there is
01706     not an element with a matching i value, then false
01707     is returned.
01708   Parameters:
01709     i - [in]
01710   Returns:
01711     True if the element was removed
01712   */
01713   bool RemoveIndex( 
01714           int i
01715           );
01716 
01717   const ON_2dex* Find2dex(int i) const;
01718 
01719 private:
01720   bool m_bSorted;
01721 };
01722 
01723 /* 
01724 Description:
01725         Compare function for Sort and Search methods.
01726 Returns:
01727    -1 if *a < *b is true
01728     1 if *b < *a is true
01729     0 if niether *a <*b nor *b<*a is true 
01730 Details:
01731         Use this template functions to sort ON_SimpleArray and
01732   ON_ClassArray objects into increasing order.  The elements
01733   of the arrays must be a type with an operator < defined.
01734         In particular it works with built in types like double, 
01735   int and pointers.
01736 Example:
01737 
01738           ON_SimpleArray<int> A;
01739           A = ...;
01740           // Sort A in increasing order
01741           A.QuickSort( ON_CompareIncreasing<double> );          
01742 
01743 See Also:
01744   ON_CompareDecreasing
01745 */
01746 template< class T>
01747 static
01748 int ON_CompareIncreasing( const T* a, const T* b);
01749 
01750 /* 
01751 Description:
01752         Compare function for Sort and Search methods.
01753 Returns:
01754    -1 if *b < *a is true
01755     1 if *a < *b is true
01756     0 if niether *a < *b nor *b < *a is true 
01757 Details:
01758         Use this template functions to sort ON_SimpleArray and
01759   ON_ClassArray objects into decreasing order.  The elements
01760   of the arrays must be a type with an operator < defined.
01761         In particular it works with built in types like double, 
01762   int and pointers.
01763 Example:
01764 
01765           class C
01766           {
01767           public:
01768             ...
01769             bool operator<(const C&) const;
01770           };
01771           ...
01772           ON_ClassArray<C> A;
01773           A = ...;
01774           // Sort A in descrasing order
01775           A.QuickSort( ON_CompareDecreasing<C> );               
01776 
01777 See Also:
01778   ON_CompareIncreasing
01779 */
01780 template< class T>
01781 static
01782 int ON_CompareDecreasing( const T* a, const T* b);
01783 
01784 
01785 // definitions of the template functions are in a different file
01786 // so that Microsoft's developer studio's autocomplete utility
01787 // will work on the template functions.
01788 #include "opennurbs_array_defs.h"
01789 
01790 
01791 #endif


pcl
Author(s): Open Perception
autogenerated on Wed Aug 26 2015 15:26:59