SIBCArray.h

00001 //***************************************************************************************
00002 //
00003 // File supervisor: Crosswalk team
00004 //
00005 // Copyright 2008 Autodesk, Inc.  All rights reserved.  
00006 // Use of this software is subject to the terms of the Autodesk license agreement 
00007 // provided at the time of installation or download, or which otherwise accompanies 
00008 // this software in either electronic or hard copy form.
00009 //
00010 //***************************************************************************************
00011 
00012 //***************************************************************************************
00013 // Defines
00014 //***************************************************************************************
00015 #ifndef __CSIBCArray_H__
00016 #define __CSIBCArray_H__
00017 
00018 #ifdef _DEBUG
00019 #include <assert.h>
00020 #define _SI_ASSERT(x) assert(x) 
00021 #else
00022 #define _SI_ASSERT(exp)
00023 #endif
00024 
00025 #include "SIBCUtil.h"
00026 #include <string.h>
00027 
00028 // Disable "identifier was truncated to '255' characters in the debug information" warning.
00029 #if defined(_WIN32) || defined(_WIN32_WCE) || defined( _XBOX )
00030 #pragma warning( disable : 4786 )
00031 #endif
00032 
00033 //***************************************************************************************
00034 // CSIBCArray | Simple, all-purpose chunked array used by other classes.
00035 //***************************************************************************************
00036 
00038 
00041 template < class CElemType > 
00042 class CSIBCArray
00043 {
00044     private :
00045         LONG        m_lNbUsedElem;      // Number of elements used in the array
00046         LONG        m_lNbAllocElem;     // Number of elements allocated to the array
00047         CElemType   *m_pElem;           // Array of elements
00048 
00049     public:
00050 
00055         inline CSIBCArray( const LONG in_lNbElem = 0 );
00056         inline ~CSIBCArray() { DisposeData(); }
00057 
00063         inline LONG GetUsed() const;
00064 
00070         inline LONG GetSize() const;
00071 
00077         inline LONG UsedMem() const;
00078 
00085         inline LONG AllocatedMem() const;
00086 
00096         inline LONG Reserve( const LONG in_lNbElem );
00097 
00108         inline LONG Resize( const LONG in_lNewNbElem );
00109 
00119         inline LONG Extend( const LONG in_lNbElem );
00120 
00130         inline LONG Add(CElemType   in_Elem);
00131 
00142         inline LONG InsertAt(const LONG idx, const LONG nb);
00143 
00150         inline void DeleteAt(const LONG idx, const LONG nb);
00151 
00158         inline CElemType & operator [] ( const ULONG in_lIndex ) const;
00159 
00166         inline CElemType & operator [] ( const ULONG in_lIndex );
00167 
00175         inline LONG Pack( LONG i_MaxWasted = 4 );
00176 
00181         inline void DisposeData( void );
00182 
00191         inline int Become( CSIBCArray<CElemType>& in_rSrcObject );
00192 
00201         inline int Copy( const CSIBCArray<CElemType>& in_rSrcObject );
00202 
00209         inline CSIBCArray<CElemType>& operator = ( const CSIBCArray<CElemType>& in_rSrcObject );
00210 
00214         inline CElemType * ArrayPtr( void ) { return m_pElem; }         
00215 
00220         inline CElemType * * ArrayPtrPtr( void ) { return &m_pElem; }
00221 
00228         inline void Set( LONG start, LONG nb, CElemType value );
00229 
00230     private:
00231 
00232 };
00233 
00234 // Constructor
00235 template <class CElemType>
00236 inline CSIBCArray<CElemType>::CSIBCArray
00237 (
00238     const LONG in_lNbElem
00239 ) : m_lNbUsedElem( 0 ),
00240     m_pElem( NULL ),
00241     m_lNbAllocElem( 0 )
00242 {   
00243     if ( in_lNbElem > 0 )
00244         Resize( in_lNbElem );
00245 }
00246 
00247 //***************************************************************************************
00248 //
00249 // Author : Softimage Games Team
00250 // Date   : 
00251 //
00252 // Gets the current number of elements used in the array.
00253 //
00254 // class | CElemType | Type of element.
00255 //
00256 // Returns the number of used elements in the array.
00257 //
00258 //***************************************************************************************
00259 template <class CElemType>
00260 inline LONG  CSIBCArray<CElemType>::GetUsed() const
00261 {
00262     return m_lNbUsedElem;
00263 }
00264 
00265 //***************************************************************************************
00266 //
00267 // Author : Softimage Games Team
00268 // Date   : 
00269 //
00270 // Gets the current number of elements allocated for the array.
00271 //
00272 // class | CElemType | Type of element.
00273 //
00274 // Returns the number of elements allocated in the array.
00275 //
00276 //***************************************************************************************
00277 template <class CElemType>
00278 inline LONG  CSIBCArray<CElemType>::GetSize() const
00279 {
00280     return m_lNbAllocElem;
00281 }
00282 
00283 //***************************************************************************************
00284 //
00285 // Author : Softimage Games Team
00286 // Date   : 
00287 //
00288 // Returns how much memory used by the used array elements.
00289 //
00290 // class | CElemType | Type of element.
00291 //
00292 // Returns how much memory is used by used array elements.
00293 //***************************************************************************************
00294 template <class CElemType>
00295 inline LONG CSIBCArray<CElemType>::UsedMem() const
00296 {
00297     return m_lNbUsedElem * sizeof( CElemType );
00298 }
00299 
00300 //***************************************************************************************
00301 //
00302 // Author : Softimage Games Team
00303 // Date   : 
00304 //
00305 // Returns how much memory is allocated for the array.
00306 //
00307 // class | CElemType | Type of element.
00308 //
00309 // Returns how much memory is allocated for the array.
00310 //***************************************************************************************
00311 template <class CElemType>
00312 inline LONG CSIBCArray<CElemType>::AllocatedMem() const
00313 {
00314     return m_lNbAllocElem * sizeof( CElemType );
00315 }
00316 
00317 //***************************************************************************************
00318 //
00319 // Author : Softimage Games Team
00320 // Date   : 
00321 //
00322 // Like Resize, but allocates only the requested amount. If the requested amount is
00323 //          greater than the specified one, it marks the number of used objects but
00324 //          does not allocate any more.
00325 //
00326 // LONG | in_lNbElem | number of elements to allocate.
00327 //
00328 // class | CElemType | Type of element.
00329 //
00330 // returns the number of used elements.
00331 //
00332 //***************************************************************************************
00333 template <class CElemType>
00334 inline LONG CSIBCArray<CElemType>::Reserve( const LONG in_lNbElem )
00335 {
00336     CElemType * l_pTmp;
00337     int loop;
00338 
00339     //If we've got allocated elements that are unused
00340     //use one of them instead of allocating more memory
00341     if ( m_lNbAllocElem >= in_lNbElem )
00342     {
00343         return ( m_lNbUsedElem = in_lNbElem );
00344     }
00345     else
00346     {
00347         //Create the new array consisting of the desired number of elements
00348         l_pTmp = new CElemType[in_lNbElem];
00349         
00350         //If it was successful, copy the old array over
00351         if (l_pTmp != NULL )
00352         {
00353             //Copy and remove memory
00354             if (m_pElem)
00355             {
00356 /*
00357                 memcpy( l_pTmp, m_pElem, m_lNbUsedElem * sizeof( CElemType ));
00358 */
00359                 for (loop = 0; loop < m_lNbUsedElem; loop++)
00360                     l_pTmp[loop] = m_pElem[loop];
00361                 
00362                 delete [] m_pElem;
00363             }
00364 
00365             //Assign member array to the newly created array.
00366             m_pElem = l_pTmp;
00367 
00368 
00369             //Number allocated is different than the number used.
00370             m_lNbAllocElem = in_lNbElem;
00371 
00372             return ( m_lNbUsedElem = in_lNbElem );
00373         }
00374 
00375         return m_lNbUsedElem;
00376     }
00377 }
00378 
00379 //***************************************************************************************
00380 //
00381 // Author : Softimage Games Team
00382 // Date   : 
00383 //
00384 // Resizes changes the number of used cells in the array.  This is the primary device
00385 //          to change the size of the array.  If we already have enough space for the 
00386 //          number requested, the array is not resized, just the number of used elements is changed.
00387 //          If we need to allocate more space, we allocate double the requested amount and set the
00388 //          the amount used to the number requested.  This prevents us from having to allocate more
00389 //          frequently.
00390 //
00391 // LONG | in_lNewNbElem | number of elements to allocate.
00392 //
00393 // class | CElemType | Type of element.
00394 //
00395 // Returns the number of used elements
00396 //
00397 //***************************************************************************************
00398 template <class CElemType>
00399 inline LONG CSIBCArray<CElemType>::Resize( const LONG in_lNewNbElem )
00400 {
00401     CElemType * l_pTmp;
00402     int i;
00403 
00404     //If we've got allocated elements that are unused
00405     //use one of them instead of allocating more memory
00406     if ( m_lNbAllocElem >= in_lNewNbElem )
00407     {
00408         return ( m_lNbUsedElem = in_lNewNbElem );
00409     }
00410     else
00411     {
00412         //Add 100% onto the array in order to buffer
00413         LONG l_lNbAlloc = in_lNewNbElem + in_lNewNbElem;
00414         
00415         //Create the new array consisting of the desired number of elements
00416         l_pTmp = new CElemType[l_lNbAlloc];
00417 
00418         //If it was successful, copy the old array over
00419         if (l_pTmp != NULL )
00420         {
00421             //Copy and remove memory
00422             if (m_pElem)
00423             {
00424                 for ( i = 0; i < m_lNbUsedElem; i++ )
00425                 {
00426                     l_pTmp[i] = m_pElem[i];
00427                 }
00428 
00429                 delete [] m_pElem;
00430             }
00431 
00432             //Assign member array to the newly created array.
00433             m_pElem = l_pTmp;
00434 
00435 
00436             //Number allocated is different than the number used.
00437             m_lNbAllocElem = l_lNbAlloc;
00438 
00439             return ( m_lNbUsedElem = in_lNewNbElem );
00440         }
00441 
00442         return m_lNbUsedElem;
00443     }
00444 }
00445 
00446 //***************************************************************************************
00447 //
00448 // Author : Softimage Games Team
00449 // Date   : 
00450 //
00451 // Calls resize with the current number used + the number requested.
00452 //
00453 // LONG | in_lNbElem | number of elements requested.
00454 //
00455 // class | CElemType | Type of element.
00456 //
00457 // rdesc    Returns the number of used elements.
00458 //
00459 //***************************************************************************************
00460 template <class CElemType>
00461 inline LONG CSIBCArray<CElemType>::Extend( const LONG in_lNbElem )
00462 {
00463     return Resize( m_lNbUsedElem + in_lNbElem );
00464 }
00465 
00466 
00467 //***************************************************************************************
00468 //
00469 // Author : Softimage Games Team
00470 // Date   : 
00471 //
00472 // Copies another array.
00473 //
00474 // class | CElemType | Type of element.
00475 //
00476 // Returns the number of used elements.
00477 //
00478 //***************************************************************************************
00479 template <class CElemType>
00480 inline int CSIBCArray<CElemType>::Copy
00481 (
00482     const CSIBCArray<CElemType> & in_rSrcObject
00483 )
00484 {
00485     int     loop;
00486     DisposeData();
00487 
00488 
00489 
00490     if (in_rSrcObject.GetUsed() > 0)
00491     {
00492         //Pre-allocate needed memory
00493         Reserve( in_rSrcObject.GetUsed() );
00494 
00495         //Say that we will use all of it.
00496         Resize( in_rSrcObject.GetUsed() );
00497 
00498         //Check to see that everything worked correctly
00499         if (m_lNbUsedElem >= in_rSrcObject.GetUsed())
00500         {
00501             //Copy over data from other object
00502             for (loop = 0; loop < m_lNbUsedElem; loop++)
00503                 m_pElem[loop] = in_rSrcObject.m_pElem[loop];
00504 
00505 
00506             //Return the number of elements in the array
00507             return m_lNbUsedElem;
00508         }
00509     }
00510 
00511     return 0;
00512 }
00513 
00514 //***************************************************************************************
00515 //
00516 // Author : Softimage Games Team
00517 // Date   : 
00518 //
00519 // Moves the array data from in_rSrcObject to this CSIBArray and sets in_rSrcObject to null.
00520 //
00521 // class | CElemType | Type of element.
00522 //
00523 // Returns 0.
00524 //***************************************************************************************
00525 template <class CElemType>
00526 inline int CSIBCArray<CElemType>::Become( CSIBCArray<CElemType>& in_rSrcObject )
00527 {
00528     DisposeData();
00529 
00530     //Copy values
00531     m_pElem         = in_rSrcObject.m_pElem;
00532     m_lNbUsedElem   = in_rSrcObject.m_lNbUsedElem;
00533     m_lNbAllocElem  = in_rSrcObject.m_lNbAllocElem;
00534 
00535     //kill source
00536     in_rSrcObject.m_pElem           = NULL;
00537     in_rSrcObject.m_lNbUsedElem     = 0;
00538     in_rSrcObject.m_lNbAllocElem    = 0;
00539 
00540     return 0;
00541 }
00542 
00543 //***************************************************************************************
00544 //
00545 // Author : Softimage Games Team
00546 // Date   : 
00547 //
00548 // Copies another array.
00549 //
00550 // class | CElemType | Type of element.
00551 //
00552 // Returns a pointer to the array.
00553 //
00554 //***************************************************************************************
00555 template <class CElemType>
00556 inline CSIBCArray<CElemType> & CSIBCArray<CElemType>::operator = 
00557 (
00558     const CSIBCArray<CElemType> & i_That
00559 )
00560 {
00561     this->Copy( i_That );
00562 
00563     return *this;
00564 }
00565 
00566 //***************************************************************************************
00567 //
00568 // Author : Softimage Games Team
00569 // Date   : 
00570 //
00571 // Deletes all the data allocated to the object and sets the number used/allocated to 0.
00572 //
00573 // class | CElemType | Type of element.
00574 //
00575 // Returns void.
00576 //
00577 //***************************************************************************************
00578 
00579 template <class CElemType> 
00580 inline void CSIBCArray<CElemType>::DisposeData()
00581 {
00582     //If the elements exist, delete them
00583     if ( m_pElem != NULL )
00584     {
00585         //Delete the array pointer and set it to null for reference
00586         delete [] m_pElem;
00587     }
00588 
00589     //Eliminate the counts to 0.
00590     m_lNbUsedElem = 0;
00591     m_lNbAllocElem = 0;
00592     m_pElem = NULL;
00593 }
00594 
00595 //***************************************************************************************
00596 //
00597 // Author : Softimage Games Team
00598 // Date   : 
00599 //
00600 // Removes the excess space after the array by allocating a new one of the same length
00601 //  and then copying the old one over.  To be used after major array resizing only.
00602 //
00603 // LONG | i_MaxWasted | number of elements in array.
00604 //
00605 // class | CElemType | Type of element.
00606 //
00607 // Returns the number possible based on the used elements.
00608 //
00609 //***************************************************************************************
00610 
00611 template <class CElemType> 
00612 LONG CSIBCArray<CElemType>::Pack( LONG i_MaxWasted )
00613 {
00614     int loop;
00615 
00616     //Check to see if packing is neccesary
00617     if (( m_lNbAllocElem - m_lNbUsedElem ) > i_MaxWasted )
00618     {
00619         
00620         //Update the number of allocated element count
00621         m_lNbAllocElem = m_lNbUsedElem;     
00622 
00623         //Create the new array
00624         CElemType * l_pTmp = new CElemType[m_lNbUsedElem];        
00625 
00626         //If we were successful, copy the old elements over
00627         if ( l_pTmp != NULL )
00628         {
00629             //If there are old elements, copy them
00630             if (m_pElem)
00631             {
00632                 //Byte copy old elements (number * size)
00633 /*
00634                 memcpy( l_pTmp, m_pElem, m_lNbUsedElem * sizeof(CElemType) );
00635 */
00636                 for (loop = 0; loop < m_lNbUsedElem; loop++)
00637                     l_pTmp[loop] = m_pElem[loop];
00638                 
00639                 //Delete original array
00640                 delete [] m_pElem;
00641             }
00642 
00643             //copy pointer to new array since old was deleted or null
00644             m_pElem = l_pTmp;
00645         }
00646 
00647     }
00648 
00649     //Return the number possible based on the used elements
00650     return m_lNbUsedElem;
00651 
00652 }
00653 
00654 //***************************************************************************************
00655 //
00656 // Author : Softimage Games Team
00657 // Date   : 
00658 //
00659 // Indexes into the array.
00660 //
00661 // class | CElemType | Type of element.
00662 //
00663 // Returns a reference to the element in the array.
00664 //
00665 //***************************************************************************************
00666 template <class CElemType>
00667 inline CElemType & CSIBCArray<CElemType>::operator []
00668 (
00669     const ULONG in_lIndex
00670 ) const
00671 {
00672     _SI_ASSERT(in_lIndex < ((ULONG)m_lNbUsedElem));
00673     _SI_ASSERT(in_lIndex >= 0);
00674     return m_pElem[in_lIndex];
00675 }
00676 
00677 // Operator [] overload
00678 template <class CElemType>
00679 inline CElemType & CSIBCArray<CElemType>::operator []
00680 (
00681     const ULONG in_lIndex
00682 )
00683 {
00684     _SI_ASSERT(in_lIndex < ((ULONG)m_lNbUsedElem));
00685     _SI_ASSERT(in_lIndex >= 0);
00686     return m_pElem[in_lIndex];
00687 }
00688 
00689 //***************************************************************************************
00690 //
00691 // Author : Softimage Games Team
00692 // Date   : 
00693 //
00694 // Sets a range of elements to the specified value.
00695 //
00696 // LONG | start | first element in the array.
00697 // LONG | nb     | number of elements in the array.
00698 //
00699 // class | CElemType | Type of element.
00700 //
00701 // Returns void
00702 //
00703 //***************************************************************************************
00704 template <class CElemType> 
00705 inline void CSIBCArray<CElemType>::Set
00706 ( 
00707  
00708     LONG start, 
00709     LONG nb, 
00710     CElemType value 
00711 )
00712 {
00713     //Make sure elements exist
00714     if ( m_pElem != NULL )
00715     {
00716         LONG    l_lEnd = start + nb;
00717 
00718         if ( l_lEnd > m_lNbUsedElem )
00719             l_lEnd = m_lNbUsedElem;
00720 
00721         for ( LONG i = start; i < l_lEnd; i++ )
00722             m_pElem[i] = value;
00723     }
00724 }
00725 
00726 //***************************************************************************************
00727 //
00728 // Author : Softimage Games Team
00729 // Date   : 
00730 //
00731 // Inserts elements at the specified location.
00732 //
00733 // LONG | in_lIndex | index location.
00734 // LONG | in_lNbElem | number of elements.
00735 //
00736 // class | CElemType | Type of element.
00737 //
00738 // Returns the number of used elements.
00739 //
00740 //***************************************************************************************
00741 template <class CElemType>
00742 inline LONG CSIBCArray<CElemType>::InsertAt
00743 (
00744     const LONG in_lIndex,
00745     const LONG in_lNbElem
00746 )
00747 {
00748     LONG    l_lOldNb    = m_lNbUsedElem;
00749     LONG    l_lNb       = m_lNbUsedElem + in_lNbElem;
00750     LONG    l_lInsert   = in_lIndex;
00751 
00752     //Check to make sure it's inside the boudns
00753     if (l_lInsert > m_lNbUsedElem)
00754         l_lInsert = m_lNbUsedElem;
00755 
00756     //Ensure we have enough space
00757     Reserve( l_lNb );
00758 
00759     //Use all of it
00760     Resize( l_lNb );
00761 
00762     if (l_lOldNb > in_lIndex)   
00763         memmove(&m_pElem[in_lIndex + in_lNbElem], &m_pElem[in_lIndex], (unsigned int) (sizeof(CElemType) *  (l_lOldNb - in_lIndex)));
00764 
00765     return m_lNbUsedElem;    
00766 }
00767 
00768 //***************************************************************************************
00769 //
00770 // Author : Softimage Games Team
00771 // Date   : 
00772 //
00773 // Removes some cells at the place specified.
00774 //
00775 // LONG | in_lIndex | index location.
00776 // LONG | in_lNbElem | number of elements in the array.
00777 //
00778 // class | CElemType | Type of element.
00779 //
00780 // Returns void.
00781 //
00782 //***************************************************************************************
00783 template <class CElemType>
00784 inline void CSIBCArray<CElemType>::DeleteAt
00785 (
00786     const LONG in_lIndex,
00787     const LONG in_lNbElem
00788 )
00789 {
00790     LONG l_lToDelete = in_lNbElem;
00791 
00792     if ( l_lToDelete > m_lNbUsedElem  )
00793         l_lToDelete = m_lNbUsedElem;
00794 
00795     if ((in_lIndex + in_lNbElem) < m_lNbUsedElem )
00796         memmove( &m_pElem[ in_lIndex ], &m_pElem [ in_lIndex + l_lToDelete ], (unsigned int) (sizeof(CElemType) * (m_lNbUsedElem -  (in_lIndex + l_lToDelete ))));
00797 
00798     m_lNbUsedElem -= l_lToDelete;
00799 }
00800 
00801 //***************************************************************************************
00802 //
00803 // Author : Softimage Games Team
00804 // Date   : 
00805 //
00806 // adds a new element
00807 //
00808 // CElemType | in_Elem | element to add at the end of the array
00809 //
00810 // class | CElemType | Type of element.
00811 //
00812 // Returns the number of used elements.
00813 //
00814 //***************************************************************************************
00815 template <class CElemType>
00816 inline LONG CSIBCArray<CElemType>::Add
00817 (
00818     CElemType in_Elem
00819 )
00820 {
00821     Extend(1);
00822     m_pElem[m_lNbUsedElem - 1] = in_Elem;
00823     return m_lNbUsedElem;    
00824 
00825 }
00826 
00827 #ifdef _WIN32
00828 #pragma warning(disable:4251)
00829 #endif
00830                             
00831 #endif // ALREADY_INCLUDED_CSIBCArray