spcollec.h

TTS语音开发示例

    }
    return hr;
}

template<class TYPE, class ARG_TYPE>
void CSPArray<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount)
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( nIndex >= 0 );
    SPDBG_ASSERT( nCount >= 0 );
    SPDBG_ASSERT( nIndex + nCount <= m_nSize );

    // just remove a range
    int nMoveCount = m_nSize - (nIndex + nCount);
    SPDestructElements(&m_pData[nIndex], nCount);
    if (nMoveCount)
        memcpy(&m_pData[nIndex], &m_pData[nIndex + nCount],
            nMoveCount * sizeof(TYPE));
    m_nSize -= nCount;
}

template<class TYPE, class ARG_TYPE>
HRESULT CSPArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CSPArray* pNewArray)
{
    SPASSERT_VALID( this );
    SPASSERT_VALID( pNewArray );
    SPDBG_ASSERT( nStartIndex >= 0 );
    HRESULT hr = S_OK;

    if (pNewArray->GetSize() > 0)
    {
        hr = InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
        for (int i = 0; SUCCEEDED( hr )&& (i < pNewArray->GetSize()); i++)
        {
            SetAt(nStartIndex + i, pNewArray->GetAt(i));
        }
    }
    return hr;
}

template<class TYPE, class ARG_TYPE>
void CSPArray<TYPE, ARG_TYPE>::Sort(int (__cdecl *compare )(const void *elem1, const void *elem2 ))
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( m_pData != NULL );

    qsort( m_pData, m_nSize, sizeof(TYPE), compare );
}

#ifdef _DEBUG
template<class TYPE, class ARG_TYPE>
void CSPArray<TYPE, ARG_TYPE>::AssertValid() const
{
    if (m_pData == NULL)
    {
        SPDBG_ASSERT( m_nSize == 0 );
        SPDBG_ASSERT( m_nMaxSize == 0 );
    }
    else
    {
        SPDBG_ASSERT( m_nSize >= 0 );
        SPDBG_ASSERT( m_nMaxSize >= 0 );
        SPDBG_ASSERT( m_nSize <= m_nMaxSize );
        SPDBG_ASSERT( SPIsValidAddress(m_pData, m_nMaxSize * sizeof(TYPE), TRUE ) );
    }
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CSPList<TYPE, ARG_TYPE>

template<class TYPE, class ARG_TYPE>
class CSPList
{
protected:
    struct CNode
    {
        CNode* pNext;
        CNode* pPrev;
        TYPE data;
    };
public:

// Construction
    CSPList(int nBlockSize = 10);

// Attributes (head and tail)
    // count of elements
    int GetCount() const;
    BOOL IsEmpty() const;

    // peek at head or tail
    TYPE& GetHead();
    TYPE GetHead() const;
    TYPE& GetTail();
    TYPE GetTail() const;

// Operations
    // get head or tail (and remove it) - don't call on empty list !
    TYPE RemoveHead();
    TYPE RemoveTail();

    // add before head or after tail
    SPLISTPOS AddHead(ARG_TYPE newElement);
    SPLISTPOS AddTail(ARG_TYPE newElement);

    // add another list of elements before head or after tail
    void AddHead(CSPList* pNewList);
    void AddTail(CSPList* pNewList);

    // remove all elements
    void RemoveAll();

    // iteration
    SPLISTPOS GetHeadPosition() const;
    SPLISTPOS GetTailPosition() const;
    TYPE& GetNext(SPLISTPOS& rPosition); // return *Position++
    TYPE GetNext(SPLISTPOS& rPosition) const; // return *Position++
    TYPE& GetPrev(SPLISTPOS& rPosition); // return *Position--
    TYPE GetPrev(SPLISTPOS& rPosition) const; // return *Position--

    // getting/modifying an element at a given position
    TYPE& GetAt(SPLISTPOS position);
    TYPE GetAt(SPLISTPOS position) const;
    void SetAt(SPLISTPOS pos, ARG_TYPE newElement);
    void RemoveAt(SPLISTPOS position);

    // inserting before or after a given position
    SPLISTPOS InsertBefore(SPLISTPOS position, ARG_TYPE newElement);
    SPLISTPOS InsertAfter(SPLISTPOS position, ARG_TYPE newElement);

    // helper functions (note: O(n) speed)
    SPLISTPOS Find(ARG_TYPE searchValue, SPLISTPOS startAfter = NULL) const;
        // defaults to starting at the HEAD, return NULL if not found
    SPLISTPOS FindIndex(int nIndex) const;
        // get the 'nIndex'th element (may return NULL)

// Implementation
protected:
    CNode* m_pNodeHead;
    CNode* m_pNodeTail;
    int m_nCount;
    CNode* m_pNodeFree;
    struct CSPPlex* m_pBlocks;
    int m_nBlockSize;

    CNode* NewNode(CNode*, CNode*);
    void FreeNode(CNode*);

public:
    ~CSPList();
#ifdef _DEBUG
    void AssertValid() const;
#endif
};

/////////////////////////////////////////////////////////////////////////////
// CSPList<TYPE, ARG_TYPE> inline functions

template<class TYPE, class ARG_TYPE>
inline int CSPList<TYPE, ARG_TYPE>::GetCount() const
    { return m_nCount; }
template<class TYPE, class ARG_TYPE>
inline BOOL CSPList<TYPE, ARG_TYPE>::IsEmpty() const
    { return m_nCount == 0; }
template<class TYPE, class ARG_TYPE>
inline TYPE& CSPList<TYPE, ARG_TYPE>::GetHead()
    {   SPDBG_ASSERT( m_pNodeHead != NULL );
        return m_pNodeHead->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE CSPList<TYPE, ARG_TYPE>::GetHead() const
    {   SPDBG_ASSERT( m_pNodeHead != NULL );
        return m_pNodeHead->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE& CSPList<TYPE, ARG_TYPE>::GetTail()
    {   SPDBG_ASSERT( m_pNodeTail != NULL );
        return m_pNodeTail->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE CSPList<TYPE, ARG_TYPE>::GetTail() const
    {   SPDBG_ASSERT( m_pNodeTail != NULL );
        return m_pNodeTail->data; }
template<class TYPE, class ARG_TYPE>
inline SPLISTPOS CSPList<TYPE, ARG_TYPE>::GetHeadPosition() const
    { return (SPLISTPOS) m_pNodeHead; }
template<class TYPE, class ARG_TYPE>
inline SPLISTPOS CSPList<TYPE, ARG_TYPE>::GetTailPosition() const
    { return (SPLISTPOS) m_pNodeTail; }
template<class TYPE, class ARG_TYPE>
inline TYPE& CSPList<TYPE, ARG_TYPE>::GetNext(SPLISTPOS& rPosition) // return *Position++
    {   CNode* pNode = (CNode*) rPosition;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        rPosition = (SPLISTPOS) pNode->pNext;
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE CSPList<TYPE, ARG_TYPE>::GetNext(SPLISTPOS& rPosition) const // return *Position++
    {   CNode* pNode = (CNode*) rPosition;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        rPosition = (SPLISTPOS) pNode->pNext;
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE& CSPList<TYPE, ARG_TYPE>::GetPrev(SPLISTPOS& rPosition) // return *Position--
    {   CNode* pNode = (CNode*) rPosition;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        rPosition = (SPLISTPOS) pNode->pPrev;
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE CSPList<TYPE, ARG_TYPE>::GetPrev(SPLISTPOS& rPosition) const // return *Position--
    {   CNode* pNode = (CNode*) rPosition;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        rPosition = (SPLISTPOS) pNode->pPrev;
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE& CSPList<TYPE, ARG_TYPE>::GetAt(SPLISTPOS position)
    {   CNode* pNode = (CNode*) position;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline TYPE CSPList<TYPE, ARG_TYPE>::GetAt(SPLISTPOS position) const
    {   CNode* pNode = (CNode*) position;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        return pNode->data; }
template<class TYPE, class ARG_TYPE>
inline void CSPList<TYPE, ARG_TYPE>::SetAt(SPLISTPOS pos, ARG_TYPE newElement)
    {   CNode* pNode = (CNode*) pos;
        SPDBG_ASSERT( SPIsValidAddress(pNode, sizeof(CNode), TRUE ) );
        pNode->data = newElement; }

/////////////////////////////////////////////////////////////////////////////
// CSPList<TYPE, ARG_TYPE> out-of-line functions

template<class TYPE, class ARG_TYPE>
CSPList<TYPE, ARG_TYPE>::CSPList( int nBlockSize )
{
    SPDBG_ASSERT( nBlockSize > 0 );

    m_nCount = 0;
    m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
    m_pBlocks = NULL;
    m_nBlockSize = nBlockSize;
}

template<class TYPE, class ARG_TYPE>
void CSPList<TYPE, ARG_TYPE>::RemoveAll()
{
    SPASSERT_VALID( this );

    // destroy elements
    CNode* pNode;
    for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
        SPDestructElements(&pNode->data, 1);

    m_nCount = 0;
    m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
    m_pBlocks->FreeDataChain();
    m_pBlocks = NULL;
}

template<class TYPE, class ARG_TYPE>
CSPList<TYPE, ARG_TYPE>::~CSPList()
{
    RemoveAll();
    SPDBG_ASSERT( m_nCount == 0 );
}

/////////////////////////////////////////////////////////////////////////////
// Node helpers
//
// Implementation note: CNode's are stored in CSPPlex blocks and
//  chained together. Free blocks are maintained in a singly linked list
//  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
//  Used blocks are maintained in a doubly linked list using both 'pNext'
//  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
//   as the head/tail.
//
// We never free a CSPPlex block unless the List is destroyed or RemoveAll()
//  is used - so the total number of CSPPlex blocks may grow large depending
//  on the maximum past size of the list.
//

template<class TYPE, class ARG_TYPE>
CSPList<TYPE, ARG_TYPE>::CNode*
CSPList<TYPE, ARG_TYPE>::NewNode(CSPList::CNode* pPrev, CSPList::CNode* pNext)
{
    if (m_pNodeFree == NULL)
    {
        // add another block
        CSPPlex* pNewBlock = CSPPlex::Create(m_pBlocks, m_nBlockSize,sizeof(CNode));

        // chain them into free list
        CNode* pNode = (CNode*) pNewBlock->data();
        // free in reverse order to make it easier to debug
        pNode += m_nBlockSize - 1;
        for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
        {
            pNode->pNext = m_pNodeFree;
            m_pNodeFree = pNode;
        }
    }

    CSPList::CNode* pNode = m_pNodeFree;
    if( pNode )
    {
        if( SUCCEEDED( SPConstructElements(&pNode->data, 1) ) )
        {
            m_pNodeFree  = m_pNodeFree->pNext;
            pNode->pPrev = pPrev;
            pNode->pNext = pNext;
            m_nCount++;
            SPDBG_ASSERT( m_nCount > 0 );  // make sure we don't overflow
        }
    }
    return pNode;
}

template<class TYPE, class ARG_TYPE>
void CSPList<TYPE, ARG_TYPE>::FreeNode(CSPList::CNode* pNode)
{
    SPDestructElements(&pNode->data, 1);
    pNode->pNext = m_pNodeFree;
    m_pNodeFree = pNode;
    m_nCount--;
    SPDBG_ASSERT( m_nCount >= 0 );  // make sure we don't underflow
}

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
{
    SPASSERT_VALID( this );

    CNode* pNewNode = NewNode(NULL, m_pNodeHead);
    if( pNewNode )
    {
        pNewNode->data = newElement;
        if (m_pNodeHead != NULL)
            m_pNodeHead->pPrev = pNewNode;
        else
            m_pNodeTail = pNewNode;
        m_pNodeHead = pNewNode;
    }
    return (SPLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
{
    SPASSERT_VALID( this );

    CNode* pNewNode = NewNode(m_pNodeTail, NULL);
    if( pNewNode )
    {
        pNewNode->data = newElement;
        if (m_pNodeTail != NULL)
            m_pNodeTail->pNext = pNewNode;
        else
            m_pNodeHead = pNewNode;
        m_pNodeTail = pNewNode;
    }
    return (SPLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
void CSPList<TYPE, ARG_TYPE>::AddHead(CSPList* pNewList)
{
    SPASSERT_VALID( this );
    SPASSERT_VALID( pNewList );

    // add a list of same elements to head (maintain order)
    SPLISTPOS pos = pNewList->GetTailPosition();
    while (pos != NULL)
        AddHead(pNewList->GetPrev(pos));
}

template<class TYPE, class ARG_TYPE>
void CSPList<TYPE, ARG_TYPE>::AddTail(CSPList* pNewList)
{
    SPASSERT_VALID( this );
    SPASSERT_VALID( pNewList );

    // add a list of same elements
    SPLISTPOS pos = pNewList->GetHeadPosition();
    while (pos != NULL)
        AddTail(pNewList->GetNext(pos));
}

template<class TYPE, class ARG_TYPE>
TYPE CSPList<TYPE, ARG_TYPE>::RemoveHead()
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( m_pNodeHead != NULL );  // don't call on empty list !!!
    SPDBG_ASSERT( SPIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE ) );

    CNode* pOldNode = m_pNodeHead;
    TYPE returnValue = pOldNode->data;

    m_pNodeHead = pOldNode->pNext;
    if (m_pNodeHead != NULL)
        m_pNodeHead->pPrev = NULL;
    else
        m_pNodeTail = NULL;
    FreeNode(pOldNode);
    return returnValue;
}

template<class TYPE, class ARG_TYPE>
TYPE CSPList<TYPE, ARG_TYPE>::RemoveTail()
{
    SPASSERT_VALID( this );
    SPDBG_ASSERT( m_pNodeTail != NULL );  // don't call on empty list !!!
    SPDBG_ASSERT( SPIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE ) );

    CNode* pOldNode = m_pNodeTail;
    TYPE returnValue = pOldNode->data;

    m_pNodeTail = pOldNode->pPrev;
    if (m_pNodeTail != NULL)
        m_pNodeTail->pNext = NULL;
    else
        m_pNodeHead = NULL;
    FreeNode(pOldNode);
    return returnValue;
}

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::InsertBefore(SPLISTPOS position, ARG_TYPE newElement)
{
    SPASSERT_VALID( this );

    if (position == NULL)
        return AddHead(newElement); // insert before nothing -> head of the list

    // Insert it before position
    CNode* pOldNode = (CNode*) position;
    CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
    if( pNewNode )
    {
        pNewNode->data = newElement;

        if (pOldNode->pPrev != NULL)
        {
            SPDBG_ASSERT( SPIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) );
            pOldNode->pPrev->pNext = pNewNode;
        }
        else
        {
            SPDBG_ASSERT( pOldNode == m_pNodeHead );
            m_pNodeHead = pNewNode;
        }
        pOldNode->pPrev = pNewNode;
    }
    return (SPLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
SPLISTPOS CSPList<TYPE, ARG_TYPE>::InsertAfter(SPLISTPOS position, ARG_TYPE newElement)
{
    SPASSERT_VALID( this );

    if (position == NULL)
        return AddTail(newElement); // insert after nothing -> tail of the list

    // Insert it before position
    CNode* pOldNode = (CNode*) position;
    SPDBG_ASSERT( SPIsValidAddress(pOldNode, sizeof(CNode), TRUE ));
    CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
    if( pNewNode )
    {
        pNewNode->data = newElement;

        if (pOldNode->pNext != NULL)
        {
            SPDBG_ASSERT( SPIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE ));
            pOldNode->pNext->pPrev = pNewNode;
        }
        else
        {
            SPDBG_ASSERT( pOldNode == m_pNodeTail );
            m_pNodeTail = pNewNode;
        }