dxtmpl.h

希望我上传的这些东西可以对搞编程的程序员有点小小的帮助！谢谢！

    m_nSize -= nCount;
}

template<class TYPE, class ARG_TYPE>
void CDXArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CDXArray* pNewArray)
{
    DXASSERT_VALID( this );
    DXASSERT_VALID( pNewArray );
    _ASSERT( nStartIndex >= 0 );

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

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CDXList<TYPE, ARG_TYPE>

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

// Construction
    CDXList(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
    DXLISTPOS AddHead(ARG_TYPE newElement);
    DXLISTPOS AddTail(ARG_TYPE newElement);

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

    // remove all elements
    void RemoveAll();

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

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

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

    // helper functions (note: O(n) speed)
    DXLISTPOS Find(ARG_TYPE searchValue, DXLISTPOS startAfter = NULL) const;
        // defaults to starting at the HEAD, return NULL if not found
    DXLISTPOS 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 CDXPlex* m_pBlocks;
    int m_nBlockSize;

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

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

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

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

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

template<class TYPE, class ARG_TYPE>
CDXList<TYPE, ARG_TYPE>::CDXList( int nBlockSize )
{
    _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 CDXList<TYPE, ARG_TYPE>::RemoveAll()
{
    DXASSERT_VALID( this );

    // destroy elements
    CNode* pNode;
    for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
        DXDestructElements(&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>
CDXList<TYPE, ARG_TYPE>::~CDXList()
{
    RemoveAll();
    _ASSERT( m_nCount == 0 );
}

/////////////////////////////////////////////////////////////////////////////
// Node helpers
//
// Implementation note: CNode's are stored in CDXPlex 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 CDXPlex block unless the List is destroyed or RemoveAll()
//  is used - so the total number of CDXPlex blocks may grow large depending
//  on the maximum past size of the list.
//

template<class TYPE, class ARG_TYPE>
CDXList<TYPE, ARG_TYPE>::CNode*
CDXList<TYPE, ARG_TYPE>::NewNode(CDXList::CNode* pPrev, CDXList::CNode* pNext)
{
    if (m_pNodeFree == NULL)
    {
        // add another block
        CDXPlex* pNewBlock = CDXPlex::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;
        }
    }
    _ASSERT( m_pNodeFree != NULL );  // we must have something

    CDXList::CNode* pNode = m_pNodeFree;
    m_pNodeFree = m_pNodeFree->pNext;
    pNode->pPrev = pPrev;
    pNode->pNext = pNext;
    m_nCount++;
    _ASSERT( m_nCount > 0 );  // make sure we don't overflow

    DXConstructElements(&pNode->data, 1);
    return pNode;
}

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

template<class TYPE, class ARG_TYPE>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
{
    DXASSERT_VALID( this );

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

template<class TYPE, class ARG_TYPE>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
{
    DXASSERT_VALID( this );

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

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

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

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

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

template<class TYPE, class ARG_TYPE>
TYPE CDXList<TYPE, ARG_TYPE>::RemoveHead()
{
    DXASSERT_VALID( this );
    _ASSERT( m_pNodeHead != NULL );  // don't call on empty list !!!
    _ASSERT( DXIsValidAddress(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 CDXList<TYPE, ARG_TYPE>::RemoveTail()
{
    DXASSERT_VALID( this );
    _ASSERT( m_pNodeTail != NULL );  // don't call on empty list !!!
    _ASSERT( DXIsValidAddress(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>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::InsertBefore(DXLISTPOS position, ARG_TYPE newElement)
{
    DXASSERT_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);
    pNewNode->data = newElement;

    if (pOldNode->pPrev != NULL)
    {
        _ASSERT( DXIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) );
        pOldNode->pPrev->pNext = pNewNode;
    }
    else
    {
        _ASSERT( pOldNode == m_pNodeHead );
        m_pNodeHead = pNewNode;
    }
    pOldNode->pPrev = pNewNode;
    return (DXLISTPOS) pNewNode;
}

template<class TYPE, class ARG_TYPE>
DXLISTPOS CDXList<TYPE, ARG_TYPE>::InsertAfter(DXLISTPOS position, ARG_TYPE newElement)
{
    DXASSERT_VALID( this );

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

    // Insert it before position
    CNode* pOldNode = (CNode*) position;
    _ASSERT( DXIsValidAddress(pOldNode, sizeof(CNode), TRUE ));
    CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
    pNewNode->data = newElement;

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