slinkedlist.h

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

//  Description:    removes the head of the list
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void RemoveHead()
    {
        SListNode<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( m_head == 0 )
                m_tail = 0;

            m_count--;
        }
    }


// ----------------------------------------------------------------
//  Name:           RemoveTail
//  Description:    Removes the tail of the list
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void RemoveTail()
    {
        SListNode<Datatype>* node = m_head;

        // if the list isn't empty, then remove a node.
        if( m_head != 0 )
        {
            // if the head is equal to the tail, then 
            // the list has 1 node, and we are removing it.
            if( m_head == m_tail )
            {
                // delete the node, and set both pointers
                // to 0.
                delete m_head;
                m_head = m_tail = 0;
            }
            else
            {
                // skip ahead until we find the node
                // right before the tail node
                while( node->m_next != m_tail )
                    node = node->m_next;

                // make the tail point to the node before the
                // current tail, and delete the old tail.
                m_tail = node;
                delete node->m_next;
                node->m_next = 0;
            }
            m_count--;
        }
    }


// ----------------------------------------------------------------
//  Name:           GetIterator
//  Description:    gets an iterator pointing to the beginning of
//                  the list
//  Arguments:      None
//  Return Value:   an iterator pointing to the beginning of the
//                  list.
// ----------------------------------------------------------------
    SListIterator<Datatype> GetIterator()
    {
        return SListIterator<Datatype>( this, m_head );
    }


// ----------------------------------------------------------------
//  Name:           Size
//  Description:    gets the size of the list
//  Arguments:      None
//  Return Value:   size of the list
// ----------------------------------------------------------------
    int Size()
    {
        return m_count;
    }


// ----------------------------------------------------------------
//  Name:           SaveToDisk
//  Description:    saves the list to disk
//  Arguments:      p_filename: name of the file to save to
//  Return Value:   true if successful
// ----------------------------------------------------------------
    bool SaveToDisk( char* p_filename )
    {
        FILE* outfile = 0;
        SListNode<Datatype>* itr = m_head;

        // open the file
        outfile = fopen( p_filename, "wb" );

        // return if it couldn't be opened
        if( outfile == 0 )
            return false;

        // write the size of the list first
        fwrite( &m_count, sizeof( int ), 1, outfile );

        // now loop through and write the list.
        while( itr != 0 )
        {
            fwrite( &(itr->m_data), sizeof( Datatype ), 1, outfile );
            itr = itr->m_next;
        }

        fclose( outfile );

        // return success.
        return true;
    }


// ----------------------------------------------------------------
//  Name:           ReadFromDisk
//  Description:    reads a list from disk
//  Arguments:      p_filename: name of the file
//  Return Value:   true if successful
// ----------------------------------------------------------------
    bool ReadFromDisk( char* p_filename )
    {
        FILE* infile = 0;
        Datatype buffer;
        int count = 0;

        // open the file
        infile = fopen( p_filename, "rb" );

        // return if it couldn't be opened
        if( infile == 0 )
            return false;

        // read the size of the list first
        fread( &count, sizeof( int ), 1, infile );

        // now loop through and read the list.
        while( count != 0 )
        {
            fread( &buffer, sizeof( Datatype ), 1, infile );
            Append( buffer );
            count--;
        }

        fclose( infile );

        // return success.
        return true;
    }


    SListNode<Datatype>* m_head;
    SListNode<Datatype>* m_tail;
    int m_count;
};




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


// ----------------------------------------------------------------
//  Name:           SListIterator
//  Description:    Constructor, creates an iterator with a given
//                  list and node.
//  Arguments:      p_list: the list the iterator points to
//                  p_node: the node the iterator points to
//  Return Value:   None
// ----------------------------------------------------------------
    SListIterator( SLinkedList<Datatype>* p_list = 0,
                   SListNode<Datatype>* p_node = 0 )
    {
        m_list = p_list;
        m_node = p_node;
    }


// ----------------------------------------------------------------
//  Name:           Start
//  Description:    moves the iterator to the start of the list.
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void Start()
    {
        if( m_list != 0 )
            m_node = m_list->m_head;
    }


// ----------------------------------------------------------------
//  Name:           Forth
//  Description:    Moves the iterator forward
//  Arguments:      None
//  Return Value:   None
// ----------------------------------------------------------------
    void Forth()
    {
        if( m_node != 0 )
            m_node = m_node->m_next;
    }


// ----------------------------------------------------------------
//  Name:           Item
//  Description:    gets the item the iterator points to
//  Arguments:      None
//  Return Value:   a reference to the item.
// ----------------------------------------------------------------
    Datatype& Item()
    {
        return m_node->m_data;
    }


// ----------------------------------------------------------------
//  Name:           Valid
//  Description:    determines if the iterator is valid or not
//  Arguments:      None
//  Return Value:   true if valid
// ----------------------------------------------------------------
    bool Valid()
    {
        return (m_node != 0);
    }


// ----------------------------------------------------------------
//  Name:           m_node
//  Description:    the current node
// ----------------------------------------------------------------
    SListNode<Datatype>* m_node;

// ----------------------------------------------------------------
//  Name:           m_list
//  Description:    the current list
// ----------------------------------------------------------------
    SLinkedList<Datatype>* m_list;
};


#endif