wxlist.cpp

用DirectX制作高级动画-[Advanced.Animation.with.DirectX]

       that otherwise we will have to create a new one */

    pNode = (CNode *) m_Cache.RemoveFromCache();
    if (pNode == NULL) {
        pNode = new CNode;
    }

    /* Check we have a valid object */

    if (pNode == NULL) {
        return NULL;
    }

    /* Initialise all the CNode object
       just in case it came from the cache
    */

    pNode->SetData(pObject);

    /* chain it in (set four pointers) */
    pNode->SetPrev(NULL);
    pNode->SetNext(m_pFirst);

    if (m_pFirst == NULL) {
        m_pLast = pNode;
    } else {
        m_pFirst->SetPrev(pNode);
    }
    m_pFirst = pNode;

    ++m_Count;

    return (POSITION) pNode;
} // AddHead(object)



/* Add all the elements in *pList to the tail of this list.
   Return TRUE if it all worked, FALSE if it didn't.
   If it fails some elements may have been added.
*/
BOOL CBaseList::AddTail(CBaseList *pList)
{
    /* lock the object before starting then enumerate
       each entry in the source list and add them one by one to
       our list (while still holding the object lock)
       Lock the other list too.
    */
    POSITION pos = pList->GetHeadPositionI();

    while (pos) {
       if (NULL == AddTailI(pList->GetNextI(pos))) {
           return FALSE;
       }
    }
    return TRUE;
} // AddTail(list)



/* Add all the elements in *pList to the head of this list.
   Return TRUE if it all worked, FALSE if it didn't.
   If it fails some elements may have been added.
*/
BOOL CBaseList::AddHead(CBaseList *pList)
{
    /* lock the object before starting then enumerate
       each entry in the source list and add them one by one to
       our list (while still holding the object lock)
       Lock the other list too.

       To avoid reversing the list, traverse it backwards.
    */

    POSITION pos;

    INTERNALREVERSETRAVERSELIST(*pList, pos) {
        if (NULL== AddHeadI(pList->GetI(pos))){
            return FALSE;
        }
    }
    return TRUE;
} // AddHead(list)



/* Add the object after position p
   p is still valid after the operation.
   AddAfter(NULL,x) adds x to the start - same as AddHead
   Return the position of the new object, NULL if it failed
*/
POSITION  CBaseList::AddAfterI(POSITION pos, void * pObj)
{
    if (pos==NULL)
        return AddHeadI(pObj);

    /* As someone else might be furkling with the list -
       Lock the critical section before continuing
    */
    CNode *pAfter = (CNode *) pos;
    ASSERT(pAfter != NULL);
    if (pAfter==m_pLast)
        return AddTailI(pObj);

    /* set pnode to point to a new node, preferably from the cache */

    CNode *pNode = (CNode *) m_Cache.RemoveFromCache();
    if (pNode == NULL) {
        pNode = new CNode;
    }

    /* Check we have a valid object */

    if (pNode == NULL) {
        return NULL;
    }

    /* Initialise all the CNode object
       just in case it came from the cache
    */

    pNode->SetData(pObj);

    /* It is to be added to the middle of the list - there is a before
       and after node.  Chain it after pAfter, before pBefore.
    */
    CNode * pBefore = pAfter->Next();
    ASSERT(pBefore != NULL);

    /* chain it in (set four pointers) */
    pNode->SetPrev(pAfter);
    pNode->SetNext(pBefore);
    pBefore->SetPrev(pNode);
    pAfter->SetNext(pNode);

    ++m_Count;

    return (POSITION) pNode;

} // AddAfter(object)



BOOL CBaseList::AddAfter(POSITION p, CBaseList *pList)
{
    POSITION pos;
    INTERNALTRAVERSELIST(*pList, pos) {
        /* p follows along the elements being added */
        p = AddAfterI(p, pList->GetI(pos));
        if (p==NULL) return FALSE;
    }
    return TRUE;
} // AddAfter(list)



/* Mirror images:
   Add the element or list after position p.
   p is still valid after the operation.
   AddBefore(NULL,x) adds x to the end - same as AddTail
*/
POSITION CBaseList::AddBeforeI(POSITION pos, void * pObj)
{
    if (pos==NULL)
        return AddTailI(pObj);

    /* set pnode to point to a new node, preferably from the cache */

    CNode *pBefore = (CNode *) pos;
    ASSERT(pBefore != NULL);
    if (pBefore==m_pFirst)
        return AddHeadI(pObj);

    CNode * pNode = (CNode *) m_Cache.RemoveFromCache();
    if (pNode == NULL) {
        pNode = new CNode;
    }

    /* Check we have a valid object */

    if (pNode == NULL) {
        return NULL;
    }

    /* Initialise all the CNode object
       just in case it came from the cache
    */

    pNode->SetData(pObj);

    /* It is to be added to the middle of the list - there is a before
       and after node.  Chain it after pAfter, before pBefore.
    */

    CNode * pAfter = pBefore->Prev();
    ASSERT(pAfter != NULL);

    /* chain it in (set four pointers) */
    pNode->SetPrev(pAfter);
    pNode->SetNext(pBefore);
    pBefore->SetPrev(pNode);
    pAfter->SetNext(pNode);

    ++m_Count;

    return (POSITION) pNode;

} // Addbefore(object)



BOOL CBaseList::AddBefore(POSITION p, CBaseList *pList)
{
    POSITION pos;
    INTERNALREVERSETRAVERSELIST(*pList, pos) {
        /* p follows along the elements being added */
        p = AddBeforeI(p, pList->GetI(pos));
        if (p==NULL) return FALSE;
    }
    return TRUE;
} // AddBefore(list)



/* Split *this after position p in *this
   Retain as *this the tail portion of the original *this
   Add the head portion to the tail end of *pList
   Return TRUE if it all worked, FALSE if it didn't.

   e.g.
      foo->MoveToTail(foo->GetHeadPosition(), bar);
          moves one element from the head of foo to the tail of bar
      foo->MoveToTail(NULL, bar);
          is a no-op
      foo->MoveToTail(foo->GetTailPosition, bar);
          concatenates foo onto the end of bar and empties foo.

   A better, except excessively long name might be
       MoveElementsFromHeadThroughPositionToOtherTail
*/
BOOL CBaseList::MoveToTail
        (POSITION pos, CBaseList *pList)
{
    /* Algorithm:
       Note that the elements (including their order) in the concatenation
       of *pList to the head of *this is invariant.
       1. Count elements to be moved
       2. Join *pList onto the head of this to make one long chain
       3. Set first/Last pointers in *this and *pList
       4. Break the chain at the new place
       5. Adjust counts
       6. Set/Reset any events
    */

    if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.


    /* Make cMove the number of nodes to move */
    CNode * p = (CNode *)pos;
    int cMove = 0;            // number of nodes to move
    while(p!=NULL) {
       p = p->Prev();
       ++cMove;
    }


    /* Join the two chains together */
    if (pList->m_pLast!=NULL)
        pList->m_pLast->SetNext(m_pFirst);
    if (m_pFirst!=NULL)
        m_pFirst->SetPrev(pList->m_pLast);


    /* set first and last pointers */
    p = (CNode *)pos;

    if (pList->m_pFirst==NULL)
        pList->m_pFirst = m_pFirst;
    m_pFirst = p->Next();
    if (m_pFirst==NULL)
        m_pLast = NULL;
    pList->m_pLast = p;


    /* Break the chain after p to create the new pieces */
    if (m_pFirst!=NULL)
        m_pFirst->SetPrev(NULL);
    p->SetNext(NULL);


    /* Adjust the counts */
    m_Count -= cMove;
    pList->m_Count += cMove;

    return TRUE;

} // MoveToTail



/* Mirror image of MoveToTail:
   Split *this before position p in *this.
   Retain in *this the head portion of the original *this
   Add the tail portion to the start (i.e. head) of *pList
   Return TRUE if it all worked, FALSE if it didn't.

   e.g.
      foo->MoveToHead(foo->GetTailPosition(), bar);
          moves one element from the tail of foo to the head of bar
      foo->MoveToHead(NULL, bar);
          is a no-op
      foo->MoveToHead(foo->GetHeadPosition, bar);
          concatenates foo onto the start of bar and empties foo.
*/
BOOL CBaseList::MoveToHead
        (POSITION pos, CBaseList *pList)
{

    /* See the comments on the algorithm in MoveToTail */

    if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.

    /* Make cMove the number of nodes to move */
    CNode * p = (CNode *)pos;
    int cMove = 0;            // number of nodes to move
    while(p!=NULL) {
       p = p->Next();
       ++cMove;
    }


    /* Join the two chains together */
    if (pList->m_pFirst!=NULL)
        pList->m_pFirst->SetPrev(m_pLast);
    if (m_pLast!=NULL)
        m_pLast->SetNext(pList->m_pFirst);


    /* set first and last pointers */
    p = (CNode *)pos;


    if (pList->m_pLast==NULL)
        pList->m_pLast = m_pLast;

    m_pLast = p->Prev();
    if (m_pLast==NULL)
        m_pFirst = NULL;
    pList->m_pFirst = p;


    /* Break the chain after p to create the new pieces */
    if (m_pLast!=NULL)
        m_pLast->SetNext(NULL);
    p->SetPrev(NULL);


    /* Adjust the counts */
    m_Count -= cMove;
    pList->m_Count += cMove;

    return TRUE;

} // MoveToHead



/* Reverse the order of the [pointers to] objects in *this
*/
void CBaseList::Reverse()
{
    /* algorithm:
       The obvious booby trap is that you flip pointers around and lose
       addressability to the node that you are going to process next.
       The easy way to avoid this is do do one chain at a time.

       Run along the forward chain,
       For each node, set the reverse pointer to the one ahead of us.
       The reverse chain is now a copy of the old forward chain, including
       the NULL termination.

       Run along the reverse chain (i.e. old forward chain again)
       For each node set the forward pointer of the node ahead to point back
       to the one we're standing on.
       The first node needs special treatment,
       it's new forward pointer is NULL.
       Finally set the First/Last pointers

    */
    CNode * p;

    // Yes we COULD use a traverse, but it would look funny!
    p = m_pFirst;
    while (p!=NULL) {
        CNode * q;
        q = p->Next();
        p->SetNext(p->Prev());
        p->SetPrev(q);
        p = q;
    }

    p = m_pFirst;
    m_pFirst = m_pLast;
    m_pLast = p;


#if 0     // old version

    if (m_pFirst==NULL) return;          // empty list
    if (m_pFirst->Next()==NULL) return;  // single node list


    /* run along forward chain */
    for ( p = m_pFirst
        ; p!=NULL
        ; p = p->Next()
        ){
        p->SetPrev(p->Next());
    }


    /* special case first element */
    m_pFirst->SetNext(NULL);     // fix the old first element


    /* run along new reverse chain i.e. old forward chain again */
    for ( p = m_pFirst           // start at the old first element
        ; p->Prev()!=NULL        // while there's a node still to be set
        ; p = p->Prev()          // work in the same direction as before
        ){
        p->Prev()->SetNext(p);
    }


    /* fix forward and reverse pointers
       - the triple XOR swap would work but all the casts look hideous */
    p = m_pFirst;
    m_pFirst = m_pLast;
    m_pLast = p;
#endif

} // Reverse