5 Replies - 568 Views - Last Post: 12 October 2012 - 01:48 AM Rate Topic: -----

#1 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

error with defining nodes in a re-written circular queue class

Posted 10 October 2012 - 03:40 PM

Hello, so I have two questions regarding a queue class I am redefining from a linear queue to a circular queue. This class uses a separate node class which I have included here as well.

1) When I define a node within the queue class, I get the error:`node' undeclared (first use this function) at each instance I am defining a node (Lines 43, 47 etc.). I am not sure why this is as this class should be using the node class.

2) As far as how a circular class works, I am a little confused as to how the queue uses one rear_ptr that points to the end of the list while the node pointer points to the front of the list. As of now when I add a node, I have the data entering at the rear_ptr, and then setting the node pointer to the front like this push function:

//Function to push items to rear of queue
    template <class Item>
    void queue<Item>::push(const Item& entry)
    // Library facilities used: node2.h
    {
        if (empty( ))
        {   // Insert first entry using rear pointer
            list_head_insert(rear_ptr, entry);          
        }
        else
        {   // Insert an entry that is not the first.
            node<Item> *temp = new node<Item> (entry, rear_ptr -> link());
            //Set rear pointer so now it should point to new node which points to first item in list
            rear_ptr -> set_link(temp); 
        }
        
    }

Is this the correct way to set this node pointer? I need the link to set correctly so the rear_ptr can follow the node link back to the front of the list. Full code below:

Queue header:
#ifndef MAIN_SAVITCH_QUEUE2_H     // Prevent duplicate definition
#define MAIN_SAVITCH_QUEUE2_H
#include <cstdlib>   // Provides std::size_t
#include "node2.h"   // Node template class

namespace main_savitch_8C
{
    template <class Item>
    class queue
    {
    public:
        // TYPEDEFS 
        typedef std::size_t size_type;
        typedef Item value_type;
        // CONSTRUCTORS and DESTRUCTOR
        queue( );
	queue(const queue<Item>& source);
	~queue( );
        // MODIFICATION MEMBER FUNCTIONS
        void pop( );
        void push(const Item& entry);
	void operator =(const queue<Item>& source);
        // CONSTANT MEMBER FUNCTIONS
        bool empty( ) const { return (rear_ptr == NULL); }
	Item front( ) const;
    private:
        main_savitch_6B::node<Item> *rear_ptr; 
    };
}
#include "queue3.template" // Include the implementation
     
#endif



Queue template:
// INVARIANT for the Queue class:
//   1. The items in the queue are stored in a linked list, with the front of
//      the queue stored at the final node which links to the front node circularly, 
//      and the rear of the queue stored at the rear node.
//      
//   2. The member variable rear_ptr is the head pointer of the linked list of
//      items and links circulary to the final node as well. For an empty list, we don't care
//      what's stored in rear_ptr.

#include <cassert>   // Provides assert
#include "node2.h"   // Node template class

namespace main_savitch_8C
{
    //Default constructor
    template <class Item>
    queue<Item>::queue( )
    {      
        rear_ptr = NULL;
    }
        
    //Copy Constructor
    template <class Item>
    queue<Item>::queue(const queue<Item>& source)
    // Library facilities used: node2.h
	{
        if (this == &source) // Handle self-assignment
        {    
            return;
        }    
        
             if (empty())
             {
                  return;
             }     
                  else
                  {
                       
                       //New rear_ptr created and data is put at the front of list
                       node<Item> *new_rear_ptr = new node (source -> data(), new_rear_ptr); 
     	               //*******new_rear_ptr -> data() = source.rear_ptr -> data();****Not sure if needed
     	               
  	                   //New pointer to hold current position in list
  	                   node <Item>* position = source.rear_ptr -> link();
  	                   
  	                   //Copy data one at a time inserting at rear
  	                   do
  	                   {
                            node <Item> *temp = new node<Item> (source.rear_ptr -> data(), new_rear_ptr -> link());
                            
                            //Set rear pointer so now it should point to new node which points to first item in list
                            new_rear_ptr -> set_link(temp);                          
                            
                            //Advance all pointers down list
                            new_rear_ptr = new_rear_ptr -> link();
                            source.rear_ptr = source.rear_ptr -> link();
                            position = position -> link(); //Advance position pointer to see if at end of copying       
                              
                       } while (position != source.rear_ptr);                      
                  }              
    }
    
    //Destructor
    template <class Item>
    queue<Item>::~queue( )
    {
        //New pointer to hold current position in list
        node <Item> *position = rear_ptr -> link();
                
        while (rear_ptr != position)
        {
             //Pointer to delete nodes
             node<Item> *remove_ptr;
             
             remove_ptr = head_ptr;
	         rear_ptr = rear_ptr -> link();
	         delete remove_ptr;            
        }     
    }

    //Overloaded comparisson operator
    template <class Item>
    void queue<Item>::operator =(const queue<Item>& source)
    // Library facilities used: node2.h
    {
        if (this == &source) // Handle self-assignment
        {    
            return;
        }    
        
             if (empty())
             {
                  return;
             }     
                  else
                  {
                       //New rear_ptr created and data is put at the front of list
                       node <Item> *new_rear_ptr = new node<Item>(source -> data(), new_rear_ptr); 
     	               //*******new_rear_ptr -> data() = source.rear_ptr -> data();****Not sure if needed
     	               
  	                   //New pointer to hold current position in list
  	                   node <Item> *position = source.rear_ptr -> link();
  	                   
  	                   //Copy data one at a time inserting at rear
  	                   do
  	                   {
                            node<Item> *temp = new node<Item> (source.rear_ptr -> data(), new_rear_ptr -> link());
                            
                            //Set rear pointer so now it should point to new node which points to first item in list
                            new_rear_ptr -> set_link(temp);                          
                            
                            //Advance all pointers down list
                            new_rear_ptr = new_rear_ptr -> link();
                            source.rear_ptr = source.rear_ptr -> link();
                            position = position -> link(); //Advance position pointer to see if at end of copying       
                              
                       } while (position != source.rear_ptr);                      
                  }              
    }
    
    //Function to view data at front of list
    template <class Item>
    Item queue<Item>::front( ) const
    // Library facilities used: cassert
    {
        assert(!empty( ));    
        //Move rear_ptr to the front of linked list
        rear_ptr -> link();
        return rear_ptr -> data( );
    }
    
    //Function to pop items from front of list
    template <class Item>
    void queue<Item>::pop( )
    // Library facilities used: cassert, node2.h
    {
        assert(!empty( ));	    
        //Move rear_ptr to front of list with link() then remove head node
        rear_ptr -> link();
        list_head_remove(rear_ptr);
    }
    
    //Function to push items to rear of queue
    template <class Item>
    void queue<Item>::push(const Item& entry)
    // Library facilities used: node2.h
    {
        if (empty( ))
        {   // Insert first entry using rear pointer
            list_head_insert(rear_ptr, entry);          
        }
        else
        {   // Insert an entry that is not the first.
            node<Item> *temp = new node<Item> (entry, rear_ptr -> link());
            //Set rear pointer so now it should point to new node which points to first item in list
            rear_ptr -> set_link(temp); 
        }
        
    }

}


Node header:
#ifndef MAIN_SAVITCH_NODE2_H  
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

namespace main_savitch_6B
{
    template <class Item>
    class node
    {
    public:
        // TYPEDEF
        typedef Item value_type;
        // CONSTRUCTOR
        node(const Item& init_data=Item( ), node* init_link=NULL)
            { data_field = init_data; link_field = init_link; }
        // MODIFICATION MEMBER FUNCTIONS
        Item& data( ) { return data_field; }
        node* link( ) { return link_field; }
        void set_data(const Item& new_data) { data_field = new_data; }
        void set_link(node* new_link) { link_field = new_link; }
        // CONST MEMBER FUNCTIONS
        const Item& data( ) const { return data_field; }
        const node* link( ) const { return link_field; }
    private:
        Item data_field;
        node *link_field;
    };

    // FUNCTIONS to manipulate a linked list:
    template <class Item>
    void list_clear(node<Item>*& head_ptr);

    template <class Item>
    void list_copy
        (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr);

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry);
 
    template <class Item>
	std::size_t list_length(const node<Item>* head_ptr);

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position);

    template <class Item>
    void list_remove(node<Item>* previous_ptr);
   
    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target);

    // FORWARD ITERATORS to step through the nodes of a linked list
    // A node_iterator of can change the underlying linked list through the
    // * operator, so it may not be used with a const node. The
    // node_const_iterator cannot change the underlying linked list
    // through the * operator, so it may be used with a const node.
    // WARNING:
    // This classes use std::iterator as its base class;
    // Older compilers that do not support the std::iterator class can
    // delete everything after the word iterator in the second line:

    template <class Item>
    class node_iterator
    : public std::iterator<std::forward_iterator_tag, Item>
    {
    public:
    	node_iterator(node<Item>* initial = NULL)
	    { current = initial; }
	Item& operator *( ) const
	    { return current->data( ); }
	node_iterator& operator ++( ) // Prefix ++
	    { 
		current = current->link( );
		return *this;
	    }
	node_iterator operator ++(int) // Postfix ++
	    {
		node_iterator original(current);
		current = current->link( );
		return original;      	  
	    }
	bool operator ==(const node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const node_iterator other) const
	    { return current != other.current; }
    private:
	node<Item>* current;
    };

    template <class Item>
    class const_node_iterator
    : public std::iterator<std::forward_iterator_tag, const Item>
    {
    public:
    	const_node_iterator(const node<Item>* initial = NULL)
	    { current = initial; }
	const Item& operator *( ) const
	    { return current->data( ); }
	const_node_iterator& operator ++( ) // Prefix ++
	    {
		current = current->link( );
		return *this;
	    }
	const_node_iterator operator ++(int) // Postfix ++
	    {
		const_node_iterator original(current);
		current = current->link( );
		return original;
	    }
	bool operator ==(const const_node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const const_node_iterator other) const
	    { return current != other.current; }
    private:
	const node<Item>* current;
    };

}

#include "node2.template"
#endif


Node Template
// FILE: node2.template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
//   Since node is a template class, this file is included in node2.h.
//   Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t

namespace main_savitch_6B
{
    template <class Item>
    void list_clear(node<Item>*& head_ptr)
    // Library facilities used: cstdlib
    {
	while (head_ptr != NULL)
	    list_head_remove(head_ptr);
    }


    template <class Item>
    void list_copy(
	const node<Item>* source_ptr,
	node<Item>*& head_ptr,
	node<Item>*& tail_ptr
	) 
    // Library facilities used: cstdlib
    {
	head_ptr = NULL;
	tail_ptr = NULL;

	// Handle the case of the empty list
	if (source_ptr == NULL)
	    return;	

	// Make the head node for the newly created list, and put data in it
	list_head_insert(head_ptr, source_ptr->data( ));
	tail_ptr = head_ptr; 
	
	// Copy rest of the nodes one at a time, adding at the tail of new list
	source_ptr = source_ptr->link( ); 
        while (source_ptr != NULL)
	{
	    list_insert(tail_ptr, source_ptr->data( ));
	    tail_ptr = tail_ptr->link( );
	    source_ptr = source_ptr->link( );
	}
    }
 
    
    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry)
    {
	head_ptr = new node<Item>(entry, head_ptr);
    }


    template <class Item>
    void list_head_remove(node<Item>*& head_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = head_ptr;
	head_ptr = head_ptr->link( );
	delete remove_ptr;
    }


    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry) 
    {
	node<Item> *insert_ptr;
    
	insert_ptr = new node<Item>(entry, previous_ptr->link( ));
	previous_ptr->set_link(insert_ptr);
    }


    template <class Item>
    std::size_t list_length(const node<Item>* head_ptr)
    // Library facilities used: cstdlib
    {
	const node<Item> *cursor;
	std::size_t answer;
	
	answer = 0;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    ++answer;
	
	return answer;
    }


    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position) 
    // Library facilities used: cassert, cstdlib
    {
	NodePtr cursor;
	SizeType i;
    
	assert(0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); ++i)
	    cursor = cursor->link( );
	return cursor;
    }


    template <class Item>
    void list_remove(node<Item>* previous_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = previous_ptr->link( );
	previous_ptr->set_link(remove_ptr->link( ));
	delete remove_ptr;
    }


    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target) 
    // Library facilities used: cstdlib
    {
	NodePtr cursor;
	
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }
}


Also a couple side notes, because the queue is intended to be circular, it does not have a NULL terminator, so I am limited to using pretty much only the link(), data(), set_link(), and set_data() functions from the node class. Any help is much appreciated!

Is This A Good Question/Topic? 0
  • +

Replies To: error with defining nodes in a re-written circular queue class

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4098
  • View blog
  • Posts: 12,679
  • Joined: 25-December 09

Re: error with defining nodes in a re-written circular queue class

Posted 10 October 2012 - 06:05 PM

Did you have a working class that implemented your circular queue for a single type before you tried the templates. I normally recommend that you get your class working for a single type before you add the complexity of templates, and namespaces. Once you get the class working for the single type it is much easier to convert that class to use templates.

Jim
Was This Post Helpful? 0
  • +
  • -

#3 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: error with defining nodes in a re-written circular queue class

Posted 10 October 2012 - 09:22 PM

This was a template class I was given to convert, it worked fine before I started converting it. The main problem I'm supposed to work around is the NULL pointer no longer being relevant, so in my conversion I need to take the handy functions inside of the node class and reconfigure them within the circular queue. Before the conversion this was just a linear queue, and now I am attempting to make it circular.
Was This Post Helpful? 0
  • +
  • -

#4 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: error with defining nodes in a re-written circular queue class

Posted 11 October 2012 - 09:49 PM

Ok I think I have touched this up a bit, but I am running into an error I don't understand; when I go to compile my test program gives me the error: 'queue' undefined, so I tried compiling the queue class separately and I get the error: " [Build Error] No rule to make target `queue3.o'. Stop. ". What does this mean?
Was This Post Helpful? 0
  • +
  • -

#5 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: error with defining nodes in a re-written circular queue class

Posted 11 October 2012 - 10:29 PM

Templates go in header files.
Was This Post Helpful? 0
  • +
  • -

#6 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: error with defining nodes in a re-written circular queue class

Posted 12 October 2012 - 01:48 AM

Right, I have the line #include "queue3.template" to include the template implementation in the header file for the queue. Is there something else you are referring to?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1