dlinkedlist.h

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

// ----------------------------------------------------------------
    void InsertBefore( DListIterator<Datatype>& p_iterator, Datatype p_data )
    {
        if( p_iterator.m_node != 0 )
        {
            // insert the data before the iterator
            p_iterator.m_node->InsertBefore( p_data );

            // if the iterator was the head of the list,
            // reset the head pointer.
            if( p_iterator.m_node == m_head )
                m_head = m_head->m_previous;

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


// ----------------------------------------------------------------
//  Name:           Remove
//  Description:    Removes the node that the iterator points to.
//                  moves iterator forward to the next node.
//  Arguments:      p_iterator: The iterator to remove
//  Return Value:   None.
// ----------------------------------------------------------------
    void Remove( DListIterator<Datatype>& p_iterator )
    {
        // temporary node pointer.
        DListNode<Datatype>* node;

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


        // save the pointer to the node we want to delete.
        node = p_iterator.m_node;

        // if the node we want to remove is the head or the tail
        // nodes, then move the head or tail to the next or
        // previous node.
        if( node == m_head )
        {
            m_head = m_head->m_next;
        }
        else if( node == m_tail )
        {
            m_tail = m_tail->m_previous;
        }

        // move the iterator forward to the next valid node
        p_iterator.Forth();

        // delink and delete the node.
        node->Delink();
        delete node;

        // if the head is 0, then set the tail to 0 as well.
        if( m_head == 0 )
            m_tail = 0;
        
        m_count--;
    }



// ----------------------------------------------------------------
//  Name:           GetIterator
//  Description:    Gets an iterator pointing to the beginning
//                  of the list.
//  Arguments:      None.
//  Return Value:   iterator pointing to the beginning of the list.
// ----------------------------------------------------------------
    DListIterator<Datatype> GetIterator()
    {
        return DListIterator<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 linked 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;
        DListNode<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 linked list from a file.
//  Arguments:      p_filename: the name of the file to read from
//  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;
    }


// ----------------------------------------------------------------
//  Name:           m_head
//  Description:    The first node in the list
// ----------------------------------------------------------------
    DListNode<Datatype>* m_head;

// ----------------------------------------------------------------
//  Name:           m_tail
//  Description:    The last node in the list
// ----------------------------------------------------------------
    DListNode<Datatype>* m_tail;

// ----------------------------------------------------------------
//  Name:           m_count
//  Description:    The number of nodes in the list
// ----------------------------------------------------------------
    int m_count;
};




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


// ----------------------------------------------------------------
//  Name:           DListIterator
//  Description:    Constructor, creates an iterator that points
//                  to the given list and node. 
//  Arguments:      p_list: pointer to the list the iterator belongs
//                          to.
//                  p_node: pointer to the current node.
//  Return Value:   None.
// ----------------------------------------------------------------
    DListIterator( DLinkedList<Datatype>* p_list = 0,
                   DListNode<Datatype>* p_node = 0 )
    {
        m_list = p_list;
        m_node = p_node;
    }


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

// ----------------------------------------------------------------
//  Name:           End
//  Description:    Resets the iterator to the end of the list
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void End()
    {
        if( m_list != 0 )
            m_node = m_list->m_tail;
    }


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


// ----------------------------------------------------------------
//  Name:           Back
//  Description:    Moves the iterator backward by one position.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Back()
    {
        if( m_node != 0 )
            m_node = m_node->m_previous;
    }


// ----------------------------------------------------------------
//  Name:           Item
//  Description:    Gets the item that the iterator is pointing to.
//  Arguments:      None.
//  Return Value:   Reference to the data in the node.
// ----------------------------------------------------------------
    Datatype& Item()
    {
        return m_node->m_data;
    }


// ----------------------------------------------------------------
//  Name:           Valid
//  Description:    Determines if the node is valid.
//  Arguments:      None.
//  Return Value:   true if valid
// ----------------------------------------------------------------
    bool Valid()
    {
        return (m_node != 0);
    }


// ----------------------------------------------------------------
//  Name:           operator==
//  Description:    Determines if two iterators point to the same
//                  node.
//  Arguments:      None.
//  Return Value:   true if they point to the same node.
// ----------------------------------------------------------------
    bool operator==( DListIterator<Datatype>& p_rhs )
    {
        if( m_node == p_rhs.m_node && m_list == p_rhs.m_list )
        {
            return true;
        }
        return false;
    }



// ----------------------------------------------------------------
//  Name:           m_node
//  Description:    pointer to the current node
// ----------------------------------------------------------------
    DListNode<Datatype>* m_node;


// ----------------------------------------------------------------
//  Name:           m_list
//  Description:    pointer to the current list.
// ----------------------------------------------------------------
    DLinkedList<Datatype>* m_list;
};



#endif