[CISP430] pqueue.cpp

#include <iostream>
 
#include "pqueue1.h" // header file for pqueue1
using namespace std;
 
// global prototype 
	void list_copy(const Node* source_ptr, Node*& head_ptr, Node*& tail_ptr);
	void list_head_insert(Node*& head_ptr, const PriorityQueue::Item& entry, unsigned int priority);
	void list_insert(Node* previous_ptr, const PriorityQueue::Item& entry, unsigned int priority);
	void list_clear(Node*& head_ptr);
	void list_head_remove(Node*& head_ptr);
 
 
 
 
PriorityQueue::PriorityQueue( )
//     Postcondition: The PriorityQueue has been initialized with no Items.
{	head_ptr = NULL;	many_nodes = 0;	}
 
PriorityQueue::PriorityQueue(const PriorityQueue& source)
// COPY CONSTRACTOR
{	
	cout << "-------- a.1"<< endl;
	Node* tail_ptr;
	list_copy(source.head_ptr,head_ptr,tail_ptr);
	many_nodes = source.many_nodes;
}
 
PriorityQueue::~PriorityQueue( )
 
// DESTRACTOR
 
{
	cout << "-------- a.2"<< endl;
		// destractor clear the data 
		list_clear(head_ptr);
		head_ptr = NULL;
		many_nodes = 0;
	// I NEED TO ADD LIST_CLEAR() FROM A3 NODE.H
}
 
void PriorityQueue::operator =(const PriorityQueue& source)
// NO DESCRIPTION...
{
	cout << "-------- a.3"<< endl;
	if (this != &source)
	{
		cout << "-------- a.4"<< endl;
	 	Node *tail_ptr;
		list_clear(head_ptr);
		head_ptr = NULL;
		many_nodes = 0;
 
 
		list_copy(source.head_ptr, head_ptr, tail_ptr);
		many_nodes = source.many_nodes;
	}
	cout << "-------- a.5"<< endl;
}
	/*USING QUICKSORT-LIKE ALGORITHM*/
		/*if using quick sort method create cursor, the new node, and an array with
			all the memory locations of each node in the list */
		// Node *locations[many_nodes];
		// Node *cursor_ptr = head_ptr;
		// for (int i=0; i<many_nodes; ++i) {
			// locations[i] = cursor;
			// cursor_ptr = cursor_ptr->link;
		// }
 
 
void PriorityQueue::insert(const Item& entry, unsigned int priority)//PUSH
//     Postcondition: A new copy of entry has been inserted with the specified
//     priority.
{
	cout << "-------- a.6"<< endl;
	//bool spot = false;
	Node *target_ptr = new Node();
 
 
	// SOTORE THE ITEMS
	target_ptr->data = entry;
	target_ptr->priority = priority;
	// NODE IS EMPTY
	if(is_empty())
	{
		cout << "-------- a.7"<< endl;
		head_ptr = target_ptr;
		head_ptr->link = NULL;
	}
 
	// NODE IS NOT EMPTY 
	else if(!is_empty())
	{
		cout << "-------- a.8"<< endl;
		Node *cursor = head_ptr;		
		int counter1=0, counter2=0;
		// FIND A POSITION OF THE NODE
		for (counter1; counter1 < size(); ++counter1)
		{ 
			if(cursor->priority < priority)
			{	
				target_ptr->link = cursor;
				if(cursor == head_ptr)
				{
					head_ptr = target_ptr;
				}
				cursor = head_ptr;
				for(counter2; counter2<counter1;++counter2)
				{
					if(counter2==(counter1-1))
					{
						cursor->link = target_ptr;
						break;
 
					}
					//else{
						cursor = cursor->link;
					//}
 
				}
				break;
			}
			else if(counter1==(size()-1))
			{
				cursor->link = target_ptr;
				target_ptr -> link = NULL;
			}
			cursor = cursor->link;
		}
 
	}
	++many_nodes;
}
 
PriorityQueue::Item PriorityQueue::get_front()
//     Precondition: size( ) > 0.
//     Postcondition: The highest priority item has been returned and has been
//     removed from the PriorityQueue. (If several items have equal priority,
//     then the one that entered first will come out first.)
{
	cout << "-------- a.21"<< endl;
 		if(!is_empty())
 		{
			cout << "-------- a.22"<< endl;
 			Node top;
 			top.data = head_ptr->data;
	 		list_head_remove(head_ptr);
			--many_nodes;
			return top.data;
		}
}
 
 
 
/**************************************************************
 
	HERE ARE TOOLBOX 
 
***************************************************************/
 
void list_copy(const Node* source_ptr, Node*& head_ptr, Node*& 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, source_ptr->priority);
		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, source_ptr->priority);
			tail_ptr = tail_ptr->link;
			source_ptr = source_ptr->link;
		}
}
 
	void list_head_insert(Node*& head_ptr, const PriorityQueue::Item& entry, unsigned int priority) 
	{
		Node *NewNode = new Node();
		NewNode->data = entry;
		NewNode->link = head_ptr;
		NewNode->priority = priority;
		head_ptr = NewNode;
	}
 
	void list_insert(Node* previous_ptr, const PriorityQueue::Item& entry, unsigned int priority) 
	{
		Node *target_ptr = new Node();
		target_ptr->data = entry;
		target_ptr->link = previous_ptr->link;
		target_ptr->priority = priority;
		previous_ptr->link = target_ptr;
	}
 
	void list_clear(Node*& head_ptr) 
	{
	// Library facilities used: cstdlib
		while (head_ptr != NULL)
			list_head_remove(head_ptr);
	}
 
	void list_head_remove(Node*& head_ptr) 
	{
		Node *remove_ptr;
 
		remove_ptr = head_ptr;
		head_ptr = head_ptr->link;
		delete remove_ptr; 
	}