slinkedlist.h

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

// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// SLinkedList.h
// This is The basic Singly-Linked List class
// ============================================================================
#ifndef SLINKEDLIST_H
#define SLINKEDLIST_H

#include <stdio.h>



// forward declarations of all the classes in this file
template<class Datatype> class SListNode;
template<class Datatype> class SLinkedList;
template<class Datatype> class SListIterator;



// -------------------------------------------------------
// Name:        SListNode
// Description: This is the basic Singly-linked list node
//              class.
// -------------------------------------------------------
template<class Datatype>
class SListNode
{
public:


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

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


// ----------------------------------------------------------------
//  Name:           SListNode
//  Description:    Constructor, creates an empty node.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    SListNode()
    {
        m_next = 0;
    }

// ----------------------------------------------------------------
//  Name:           InsertAfter
//  Description:    this inserts a new node after the current node
//  Arguments:      p_data: the data to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void InsertAfter( Datatype p_data )
    {
        // create the new node.
        SListNode<Datatype>* newnode = new SListNode<Datatype>;
        newnode->m_data = p_data;

        // make the new node point to the next node.
        newnode->m_next = m_next;

        // make the previous node point to the new node
        m_next = newnode;
    }

};



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

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


// ----------------------------------------------------------------
//  Name:           ~SLinkedList
//  Description:    destructor, deletes every node.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    ~SLinkedList()
    {
        // temporary node pointers.
        SListNode<Datatype>* itr = m_head;
        SListNode<Datatype>* next;

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

            // delete the current node.
            delete itr;

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


// ----------------------------------------------------------------
//  Name:           Append
//  Description:    adds data to the end of the list
//  Arguments:      p_data: the data to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void Append( Datatype p_data )
    {
        // check to make sure the list isn't empty
        if( m_head == 0 )
        {
            // if the list is empty,
            // create a new head node.
            m_head = m_tail = new SListNode<Datatype>;
            m_head->m_data = p_data;
        }
        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:    adds data to the beginning of the list
//  Arguments:      p_data: data to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void Prepend( Datatype p_data )
    {
        // create the new node.
        SListNode<Datatype>* newnode = new SListNode<Datatype>;
        newnode->m_data = p_data;
        newnode->m_next = m_head;

        // set the head node, and the tail node if needed.
        m_head = newnode;
        if( m_tail == 0 )
            m_tail = m_head;

        m_count++;
    }




// ----------------------------------------------------------------
//  Name:           Insert
//  Description:    inserts new data after the given iterator, or
//                  appends it if iterator is invalid.
//  Arguments:      p_iterator: iterator to insert after
//                  p_data: data to insert
//  Return Value:   None
// ----------------------------------------------------------------
    void Insert( SListIterator<Datatype>& p_iterator, Datatype p_data )
    {
        // if the iterator doesn't belong to this list, do nothing.
        if( p_iterator.m_list != this )
            return;
        
        if( p_iterator.m_node != 0 )
        {
            // if the iterator is valid, then insert the node
            p_iterator.m_node->InsertAfter( p_data );

            // if the iterator is the tail node, then
            // update the tail pointer to point to the
            // new node.
            if( p_iterator.m_node == m_tail )
            {
                m_tail = p_iterator.m_node->m_next;
            }
            m_count++;
        }
        else
        {
            // if the iterator is invalid, just append the data
            Append( p_data );
        }
    }


// ----------------------------------------------------------------
//  Name:           Remove
//  Description:    removes the node that the iterator points to
//  Arguments:      p_iterator: points to the node to remove
//  Return Value:   None
// ----------------------------------------------------------------
    void Remove( SListIterator<Datatype>& p_iterator )
    {
        SListNode<Datatype>* node = m_head;

        // if the iterator doesn't belong to this list, do nothing.
        if( p_iterator.m_list != this )
            return;

        // if node is invalid, do nothing.
        if( p_iterator.m_node == 0 )
            return;

        if( p_iterator.m_node == m_head )
        {
            // move the iterator forward, and delete the head.
            p_iterator.Forth();
            RemoveHead();
        }
        else
        {
            // scan forward through the list until we find
            // the node prior to the node we want to remove
            while( node->m_next != p_iterator.m_node )
                node = node->m_next;

            // move the iterator forward.
            p_iterator.Forth();

            // if the node we are deleting is the tail, 
            // update the tail node.
            if( node->m_next == m_tail )
            {
                m_tail = node;
            }

            // delete the node.
            delete node->m_next;

            // re-link the list.
            node->m_next = p_iterator.m_node;
        }
        m_count--;
    }


// ----------------------------------------------------------------
//  Name:           RemoveHead