2011年6月28日星期二

CSet模板类

template < typename itemType >
int fnCompare( itemType *pitem1, itemType *pitem2 )
{
return pitem1->fnCompare( pitem2 );
};

template
class CSet
{
public:
int m_iMaxNumItems;
int m_iNumIncrementalItems;
int m_iNumItems;
itemType **m_paItems;

public:
CSet( int iMaxNumItems, int iNumIncrementalItems )
{
m_iMaxNumItems = iMaxNumItems;
m_iNumIncrementalItems = iNumIncrementalItems;
m_iNumItems = 0;

int I;

m_paItems = new itemType * [ m_iMaxNumItems ];
for( I = 0; I < m_iMaxNumItems; I ++ )
{
m_paItems[ I ] = NULL;
}
}
~CSet( )
{
int I;

for( I = 0; I < m_iNumItems; I ++ )
{
delete m_paItems[ I ];
m_paItems[ I ] = NULL;
}
delete [] m_paItems;
}

void fnClear( void )
{
int I;
for( I = 0; I < m_iNumItems; I ++ ){
delete m_paItems[ I ];
m_paItems[ I ] = NULL;
}
m_iNumItems = 0;
}

bool fnInsert( itemType *pItem )
{
if( m_iNumItems == 0
|| ( m_iNumItems < m_iMaxNumItems && fnCompare( m_paItems[ m_iNumItems - 1 ], pItem ) ) )
{
m_paItems[ m_iNumItems ] = pItem;

m_iNumItems++;
return true;
}

int I;

//insert the item
int iB, iE, iM;
float fC = -1;
iB = 0;
iE = m_iNumItems - 1;
iM = (iB + iE ) / 2;
do{
if( iE < iB )
break;

iM = (iB + iE ) / 2;
fC = fnCompare( m_paItems[ iM ], pItem );
if( fC == 0 )
{
iE = iM;
break;
}
if( fC < 0 )
iE = iM - 1;
if( fC > 0 )
iB = iM + 1;
}while( true );


if( fC > 0 )
iM ++;//iM is the position need to insert

if( m_iMaxNumItems == m_iNumItems )
{ //when the table is full
if( m_iNumIncrementalItems <= 0 )
{ //no incremental items are allowed
if ( iM >= m_iNumItems )
return false;//
delete m_paItems[ m_iNumItems - 1 ];
for( I = m_iNumItems - 2; I >= iM; I-- )
{
m_paItems[ I + 1 ] = m_paItems[ I ];
}
m_paItems[ I + 1 ] = pItem;
return true;
}
else
{ //incremental items are allowed

//increase the table size
itemType **paNewItems = new itemType * [ m_iMaxNumItems + m_iNumIncrementalItems ];
for( I = 0; I < m_iMaxNumItems; I ++ )
{
paNewItems[ I ] = m_paItems[ I ];
}

for( I = m_iMaxNumItems; I < m_iMaxNumItems + m_iNumIncrementalItems; I ++ )
paNewItems[ I ] = NULL;

delete [] m_paItems;
m_paItems = paNewItems;

m_iMaxNumItems += m_iNumIncrementalItems;
}
}

for( I = m_iNumItems - 1; I >= iM; I -- )
{
m_paItems[ I + 1 ] = m_paItems[ I ];
}
m_paItems[ I + 1 ] = pItem;

m_iNumItems ++;
return true;
}

bool fnDelete( int iBeginItemID, int iNumDeleteItems )
{
int I;

if( ( iBeginItemID < 0 )
|| ( iBeginItemID >= m_iNumItems )
|| ( iNumDeleteItems < 0 ) )
return false;
if( ( iBeginItemID + iNumDeleteItems ) > m_iNumItems )
iNumDeleteItems = m_iNumItems - iBeginItemID;

for( I = 0; I < iNumDeleteItems; I ++ ){
delete m_paItems[ iBeginItemID + I ];
m_paItems[ iBeginItemID + I ] = NULL;
}
for( I = iBeginItemID; I < m_iNumItems - iNumDeleteItems; I ++ ){
m_paItems[ I ] = m_paItems[ I + iNumDeleteItems ];
m_paItems[ I + iNumDeleteItems ] = NULL;
}
m_iNumItems -= iNumDeleteItems;
return true;
}
};

实例化CSet的类itemType需要实现fnCompare( itemType pitem2 )方法.

没有评论: