dlinkedlist.h

游戏开发数据结构Data Structures for Game Programmers

// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// DLinkedList.h
// This is the Doubly-Linked List class
// ============================================================================
#ifndef DLINKEDLIST_H
#define DLINKEDLIST_H




// forward declarations of all the classes in this file
template<class Datatype> class DListNode;
template<class Datatype> class DLinkedList;
template<class Datatype> class DListIterator;



// -------------------------------------------------------
// Name:        DListNode
// Description: This is the Doubly-linked list node class.
// -------------------------------------------------------
template<class Datatype>
class DListNode
{
public:


// ----------------------------------------------------------------
//  Name:           m_data
//  Description:    This is the data in the node.
// ----------------------------------------------------------------
    Datatype m_data;

// ----------------------------------------------------------------
//  Name:           m_next
//  Description:    This is a pointer to the next node in the list
// ----------------------------------------------------------------
    DListNode<Datatype>* m_next;

// ----------------------------------------------------------------
//  Name:           m_previous
//  Description:    This is a pointer to the last node in the list
// ----------------------------------------------------------------
    DListNode<Datatype>* m_previous;


// ----------------------------------------------------------------
//  Name:           DeLink
//  Description:    This delinks this node from the list it is in.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Delink()
    {
        // if a previous node exists, then make the previous
        // node point to the next node.
        if( m_previous != 0 )
            m_previous->m_next = m_next;

        // if the next node exists, then make the next node
        // point to the previous node.
        if( m_next != 0 )
            m_next->m_previous = m_previous;
    }


// ----------------------------------------------------------------
//  Name:           InsertAfter
//  Description:    This adds a node after the current node.
//  Arguments:      p_data - The data to store in the new node.
//  Return Value:   None.
// ----------------------------------------------------------------
    void InsertAfter( Datatype p_data )
    {
        // create the new node.
        DListNode<Datatype>* newnode = new DListNode<Datatype>;
        newnode->m_data = p_data;

        // set up newnode's pointers.
        newnode->m_next     = m_next;
        newnode->m_previous = this;

        // if there is a node after this one, make it point to
        // newnode
        if( m_next != 0 )
            m_next->m_previous = newnode;

        // make the current node point to newnode.
        m_next = newnode;
    }


// ----------------------------------------------------------------
//  Name:           InsertBefore
//  Description:    This adds a node before the current node.
//  Arguments:      p_data - The data to store in the new node.
//  Return Value:   None.
// ----------------------------------------------------------------
    void InsertBefore( Datatype p_data )
    {
        // create the new node.
        DListNode<Datatype>* newnode = new DListNode<Datatype>;
        newnode->m_data = p_data;

        // set up newnode's pointers.
        newnode->m_next     = this;
        newnode->m_previous = m_previous;

        // if there is a node before this one, make it point to
        // newnode
        if( m_previous != 0 )
            m_previous->m_next = newnode;

        // make the current node point to newnode.
        m_previous = newnode;
    }


};



// -------------------------------------------------------
// Name:        DLinkedList
// Description: This is the Doubly-linked list container.
// -------------------------------------------------------
template<class Datatype>
class DLinkedList
{
public:

// ----------------------------------------------------------------
//  Name:           DLinkedList
//  Description:    Constructor; creates an empty list
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    DLinkedList()
    {
        m_head = 0;
        m_tail = 0;
        m_count = 0;
    }

    
// ----------------------------------------------------------------
//  Name:           DLinkedList
//  Description:    Destructor; destroys every node
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    ~DLinkedList()
    {
        // temporary node pointers.
        DListNode<Datatype>* node = m_head;
        DListNode<Datatype>* next;

        while( node != 0 )
        {
            // save the pointer to the next node.
            next = node->m_next;

            // delete the current node.
            delete node;

            // make the next node the current node.
            node = next;
        }
    }


// ----------------------------------------------------------------
//  Name:           Append
//  Description:    Adds a new node to the end of a list
//  Arguments:      p_data - the data to be added.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Append( Datatype p_data )
    {
        // if there is no head node (ie: list is empty)
        if( m_head == 0 )
        {
            // create a new head node.
            m_head = m_tail = new DListNode<Datatype>;
            m_head->m_data = p_data;
            m_head->m_next = 0;
            m_head->m_previous = 0;
        }
        else
        {
            // insert a new node after the tail, and reset the tail.
            m_tail->InsertAfter( p_data );
            m_tail = m_tail->m_next;
        }
        m_count++;
    }


// ----------------------------------------------------------------
//  Name:           Prepend
//  Description:    Addss a new node to the beginning of a list
//  Arguments:      p_data - the data to be added.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Prepend( Datatype p_data )
    {
        // if there is no head node (ie: list is empty)
        if( m_head == 0 )
        {
            // create a new head node.
            m_head = m_tail = new DListNode<Datatype>;
            m_head->m_data = p_data;
            m_head->m_next = 0;
            m_head->m_previous = 0;
        }
        else
        {
            // insert a new node before the head, and reset the head.
            m_head->InsertBefore( p_data );
            m_head = m_head->m_previous;
        }
        m_count++;
    }


// ----------------------------------------------------------------
//  Name:           RemoveHead
//  Description:    This removes the very first node in the list.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void RemoveHead()
    {
        DListNode<Datatype>* node = 0;

        if( m_head != 0 )
        {
            // make node point to the next node.
            node = m_head->m_next;

            // then delete the head, and make the pointer
            // point to node.
            delete m_head;
            m_head = node;

            // if the head is null, then we've just deleted the only node
            // in the list. set the tail to 0.
            // if not, set the previous pointer to 0.
            if( m_head == 0 )
                m_tail = 0;
            else
                m_head->m_previous = 0;

            m_count--;
        }
    }


// ----------------------------------------------------------------
//  Name:           RemoveTail
//  Description:    This removes the very last node in the list.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void RemoveTail()
    {
        DListNode<Datatype>* node = 0;

        if( m_tail != 0 )
        {
            // make node point to the next node.
            node = m_tail->m_previous;

            // then delete the head, and make the pointer
            // point to node.
            delete m_tail;
            m_tail = node;

            // if the tail is null, then we've just deleted the only node
            // in the list. set the head to 0.
            // if not, set the next pointer to 0.
            if( m_tail == 0 )
                m_head = 0;
            else
                m_tail->m_next = 0;

            m_count--;
        }
    }



// ----------------------------------------------------------------
//  Name:           InsertAfter
//  Description:    Inserts data after the iterator, or at the end
//                  of the list if iterator is invalid.
//  Arguments:      p_iterator: The iterator to insert after
//                  p_data: the data to insert
//  Return Value:   None.
// ----------------------------------------------------------------
    void InsertAfter( DListIterator<Datatype>& p_iterator, Datatype p_data )
    {
        if( p_iterator.m_node != 0 )
        {
            // insert the data after the iterator
            p_iterator.m_node->InsertAfter( p_data );

            // if the iterator was the tail of the list,
            // reset the tail pointer
            if( p_iterator.m_node == m_tail )
                m_tail = m_tail->m_next;

            // increment the count
            m_count++;
        }
        else
        {
            Append( p_data );
        }
    }


// ----------------------------------------------------------------
//  Name:           InsertBefore
//  Description:    inserts data before the iterator, or prepends
//                  it to the beginning of the list if invalid.
//  Arguments:      p_iterator: The iterator to insert after
//                  p_data: the data to insert
//  Return Value:   None.