00001 
00002 //
00003 // Copyright (c) 2006 Audiokinetic Inc. / All Rights Reserved
00004 //
00006 
00007 // AkListBare.h
00008 
00009 #ifndef _AKLISTBARE_H
00010 #define _AKLISTBARE_H
00011 
00012 // this one lets you define the structure
00013 // only requirement is that T must have member pNextItem (if using the default AkListBareNextItem policy struct).
00014 // client is responsible for allocation/deallocation of T.
00015 
00016 // WATCH OUT !
00017 // - remember that removeall/term can't delete the elements for you.
00018 // - be sure to destroy elements AFTER removing them from the list, as remove will
00019 // access members of the element.
00020 
00021 /* Usage: List of AkMyType.
00022 
00023 - With default AkMyType::pNextItem, no count (Length() is not available):
00024 typedef AkListBare<AkMyType> AkMyList1;
00025 
00026 - With custom AkMyType::pNextItemCustom, no count:
00027 struct AkListBareNextItemCustom
00028 {
00029     static AkForceInline AkMyType *& Get( AkMyType * in_pItem ) 
00030     {
00031         return in_pItem->pNextItemCustom;
00032     }
00033 };
00034 typedef AkListBare<AkMyType,AkListBareNextItemCustom> AkMyList2;
00035 
00036 - With default AkMyType::pNextItem, WITH count (Length() is available):
00037 typedef AkListBare<AkMyType,AkListBareNextItem,AkCountPolicyWithCount> AkMyList3;
00038 
00039 */
00040 
00041 //
00042 // List bare policy classes.
00043 //
00044 
00046 template <class T> struct AkListBareNextItem
00047 {
00049     static AkForceInline T *& Get( T * in_pItem ) 
00050     {
00051         return in_pItem->pNextItem;
00052     }
00053 };
00054 
00057 template <class T> 
00058 class AkCountPolicyNoCount
00059 {
00060 protected:
00061     AkForceInline void ResetCount( T* ) {}
00062     AkForceInline void IncrementCount( T* ) {}
00063     AkForceInline void DecrementCount( T* ) {}
00064 };
00065 
00066 template <class T> 
00067 class AkCountPolicyWithCount
00068 {
00069 public:
00071     AkForceInline unsigned int Length() const
00072     {
00073         return m_ulNumListItems;
00074     }
00075 
00076 protected:
00077     AkCountPolicyWithCount() :m_ulNumListItems( 0 ) {}
00078 
00079     AkForceInline void ResetCount( T* ) { m_ulNumListItems = 0; }
00080     AkForceInline void IncrementCount( T* ) { ++m_ulNumListItems; }
00081     AkForceInline void DecrementCount( T* ) { --m_ulNumListItems; }
00082 
00083 private:
00084     unsigned int    m_ulNumListItems;           
00085 };
00086 
00089 template <class T> 
00090 class AkLastPolicyWithLast
00091 {
00092 public:
00094     AkForceInline T * Last()
00095     {
00096         return m_pLast;
00097     }
00098 
00099 protected:
00100     AkForceInline AkLastPolicyWithLast() : m_pLast( NULL ) {}
00101 
00102     // Policy interface:
00103     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00104     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00105     // otherwise it must not be implemented.
00106     AkForceInline void UpdateLast( T * in_pLast ) { m_pLast = in_pLast; }
00107     AkForceInline void SetLast( T * in_pLast ) { m_pLast = in_pLast; }
00108     AkForceInline void RemoveItem( T * in_pItem, T * in_pPrevItem )
00109     {
00110         // Is it the last one ?
00111         if( in_pItem == m_pLast )
00112         {
00113             // new last one is the previous one
00114             m_pLast = in_pPrevItem;
00115         }
00116     }
00117     AkForceInline void AddItem( T * in_pItem, T * in_pNextItem )
00118     {
00119         // Update tail.
00120         // Note: will never occur since it is used with iteratorEx (have EndEx?).
00121         if ( in_pNextItem == NULL )   
00122             m_pLast = in_pItem;
00123     }
00124 
00125 protected:
00126     T *             m_pLast;                    
00127 };
00128 
00129 template <class T> 
00130 class AkLastPolicyNoLast
00131 {
00132 protected:
00133     // Policy interface:
00134     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00135     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00136     // otherwise it must not be implemented.
00137     AkForceInline void UpdateLast( T * ) {}
00138     // SetLast is voluntarily left undefined so that calling AkListBare::AddLast() with this policy results in a compile-time error.
00139     //AkForceInline void SetLast( T * in_pLast );
00140     AkForceInline void RemoveItem( T *, T * ) {}
00141     AkForceInline void AddItem( T *, T * ) {}
00142 };
00143 
00144 
00146 template <class T, template <class> class U_NEXTITEM = AkListBareNextItem, template <class> class COUNT_POLICY = AkCountPolicyNoCount, template <class> class LAST_POLICY = AkLastPolicyWithLast > class AkListBare : public COUNT_POLICY< T >, public LAST_POLICY< T >
00147 {
00148 public:
00150     struct Iterator
00151     {
00152         T* pItem;   
00153 
00155         inline Iterator& operator++()
00156         {
00157             AKASSERT( pItem );
00158             pItem = U_NEXTITEM<T>::Get( pItem );
00159             return *this;
00160         }
00161 
00163         inline T * operator*() const
00164         {
00165             AKASSERT( pItem );
00166             return pItem;
00167         }
00168 
00170         bool operator !=( const Iterator& in_rOp ) const
00171         {
00172             return ( pItem != in_rOp.pItem );
00173         }
00174         
00176         bool operator ==( const Iterator& in_rOp ) const
00177         {
00178             return ( pItem == in_rOp.pItem );
00179         }
00180     };
00181 
00184     struct IteratorEx : public Iterator
00185     {
00186         T* pPrevItem;   
00187 
00189         IteratorEx& operator++()
00190         {
00191             AKASSERT( this->pItem );
00192             
00193             pPrevItem = this->pItem;
00194             this->pItem = U_NEXTITEM<T>::Get( this->pItem );
00195             
00196             return *this;
00197         }
00198     };
00199 
00201     IteratorEx Erase( const IteratorEx& in_rIter )
00202     {
00203         IteratorEx returnedIt;
00204         returnedIt.pItem = U_NEXTITEM<T>::Get( in_rIter.pItem );
00205         returnedIt.pPrevItem = in_rIter.pPrevItem;
00206 
00207         RemoveItem( in_rIter.pItem, in_rIter.pPrevItem );
00208 
00209         return returnedIt;
00210     }
00211 
00213     IteratorEx Insert( const IteratorEx& in_rIter,
00214                        T * in_pItem )
00215     {
00216         IteratorEx returnedIt;
00217         AddItem( in_pItem, in_rIter.pItem, in_rIter.pPrevItem );
00218         returnedIt = in_rIter;
00219         returnedIt.pPrevItem = in_pItem;
00220         return returnedIt;
00221     }
00222 
00224     inline Iterator End()
00225     {
00226         Iterator returnedIt;
00227         returnedIt.pItem = NULL;
00228         return returnedIt;
00229     }
00230 
00232     inline IteratorEx BeginEx()
00233     {
00234         IteratorEx returnedIt;
00235         
00236         returnedIt.pItem = m_pFirst;
00237         returnedIt.pPrevItem = NULL;
00238         
00239         return returnedIt;
00240     }
00241 
00243     inline Iterator Begin()
00244     {
00245         Iterator returnedIt;
00246         
00247         returnedIt.pItem = m_pFirst;
00248         
00249         return returnedIt;
00250     }
00251 
00253     inline IteratorEx FindEx( T *  in_pItem )
00254     {
00255         IteratorEx it = BeginEx();
00256         for ( ; it != End(); ++it )
00257         {
00258             if ( it.pItem == in_pItem )
00259                 break;
00260         }
00261 
00262         return it;
00263     }
00264 
00266     AkListBare()
00267     : m_pFirst( NULL )
00268     {
00269     }
00270     
00272     ~AkListBare()
00273     {
00274     }
00275 
00277     void Term()
00278     {
00279         RemoveAll();
00280     }
00281 
00283     void AddFirst( T * in_pItem )
00284     {
00285         if ( m_pFirst == NULL )
00286         {
00287             m_pFirst = in_pItem;
00288             LAST_POLICY<T>::UpdateLast( in_pItem );
00289             U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00290         }
00291         else
00292         {
00293             U_NEXTITEM<T>::Get( in_pItem ) = m_pFirst;
00294             m_pFirst = in_pItem;
00295         }
00296 
00297         COUNT_POLICY<T>::IncrementCount( in_pItem );
00298     }
00299 
00301     void AddLast( T * in_pItem )
00302     {
00303         U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00304 
00305         if ( m_pFirst == NULL )
00306         {
00307             m_pFirst = in_pItem;
00308         }
00309         else
00310         {
00311             U_NEXTITEM<T>::Get( LAST_POLICY<T>::Last() ) = in_pItem;
00312         }
00313 
00314         LAST_POLICY<T>::SetLast( in_pItem );
00315 
00316         COUNT_POLICY<T>::IncrementCount( in_pItem );
00317     }
00318 
00320     AKRESULT Remove( T * in_pItem )
00321     {
00322         IteratorEx it = FindEx( in_pItem );
00323         if ( it != End() )
00324         {
00325             Erase( it );
00326             return AK_Success;
00327         }
00328 
00329         return AK_Fail;
00330     }
00331 
00333     AKRESULT RemoveFirst()
00334     {
00335         if( m_pFirst == NULL )
00336             return AK_Fail;
00337 
00338         if ( U_NEXTITEM<T>::Get( m_pFirst ) == NULL )
00339         {
00340             m_pFirst = NULL;
00341             LAST_POLICY<T>::UpdateLast( NULL );
00342         }
00343         else
00344         {
00345             m_pFirst = U_NEXTITEM<T>::Get( m_pFirst );
00346         }
00347 
00348         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00349 
00350         return AK_Success;
00351     }
00352 
00354     AkForceInline void RemoveAll()
00355     {
00356         // Items being externally managed, all we need to do here is clear our members.
00357         m_pFirst = NULL;
00358         LAST_POLICY<T>::UpdateLast( NULL );
00359         COUNT_POLICY<T>::ResetCount( m_pFirst );
00360     }
00361 
00363     AkForceInline T * First()
00364     {
00365         return m_pFirst;
00366     }
00367 
00369     AkForceInline bool IsEmpty() const
00370     {
00371         return m_pFirst == NULL;
00372     }
00373 
00375     void RemoveItem( T * in_pItem, T * in_pPrevItem )
00376     {
00377         // Is it the first one ?
00378 
00379         if( in_pItem == m_pFirst )
00380         {
00381             // new first one is the next one
00382             m_pFirst = U_NEXTITEM<T>::Get( in_pItem );
00383         }
00384         else
00385         {
00386             // take it out of the used space
00387             U_NEXTITEM<T>::Get( in_pPrevItem ) = U_NEXTITEM<T>::Get( in_pItem );
00388         }
00389 
00390         LAST_POLICY<T>::RemoveItem( in_pItem, in_pPrevItem );
00391 
00392         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00393     }
00394 
00396     void AddItem( T * in_pItem, T * in_pNextItem, T * in_pPrevItem )
00397     {
00398         U_NEXTITEM<T>::Get( in_pItem ) = in_pNextItem;
00399 
00400         if ( in_pPrevItem == NULL )
00401             m_pFirst = in_pItem;
00402         else
00403             U_NEXTITEM<T>::Get( in_pPrevItem ) = in_pItem;
00404 
00405         LAST_POLICY<T>::AddItem( in_pItem, in_pNextItem );
00406         
00407         COUNT_POLICY<T>::IncrementCount( in_pItem );
00408     }
00409 
00410 protected:
00411     T *             m_pFirst;                   
00412 };
00413 
00414 #endif // _AKLISTBARE_H