PR20he - Online C++ Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
/*template<typename ItemType>
class Node {
public:
	ItemType data; // data
	Node* next; // pointer to next
};

template<typename ItemType>
class List {
private:
	Node<ItemType>* head;

public:
	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
	List(void);

	// Destructor
	~List(void);

	// Function: Determines whether the list is empty.
	// Pre:  List has been initialized.
	// Post: Function value = (list is empty)
	bool IsEmpty();

	// Function: Adds newItem to the list at a specific place and returns the created node.
	// Pre:  List has been initialized.
	// Post: New item is added and the created node are returned.
	Node<ItemType>* InsertNode(int index, ItemType x);

	// Function: Searches the list for a specific value.
	// Pre:  List has been initialized.
	// Post: Location of the value is returned if found otherwise 0 is returned
	int FindNode(ItemType x);

	// Function: Deletes a node by its value
	// Pre:  List has been initialized.
	// Post: Node is deleted from the list.
	int DeleteNode(ItemType x);

	int GetLength();

	List<ItemType>* CopyList();

	void DisplayList(void);

};

template<typename ItemType>
List<ItemType>::List(void)
{
	head = NULL;
}

template<typename ItemType>
List<ItemType>::~List(void)
{
	Node<ItemType>* currNode = head;
	Node<ItemType>* nextNode = NULL;
	while (currNode != NULL) {
		nextNode = currNode->next;
		delete currNode; // destroy the current node
		currNode = nextNode;
	}
}

template<typename ItemType>
bool List<ItemType>::IsEmpty()
{
	return head == NULL;
}

template<typename ItemType>
Node<ItemType>* List<ItemType>::InsertNode(int index, ItemType x)
{
	if (index < 0)
		return NULL;
	int currIndex = 1;
	Node<ItemType>* currNode = head;
	while (currNode && index > currIndex) {
		//Try to locate index'th node. If it doesn't exist, return NULL
		currNode = currNode->next;
		currIndex++;
	}
	if (index > 0 && currNode == NULL)
		return NULL;
	Node<ItemType>* newNode = new Node<ItemType>;
	newNode->data = x;
	if (index == 0) {
		newNode->next = head;
		head = newNode;
	}
	else {
		newNode->next = currNode->next;
		currNode->next = newNode;
	}
	return newNode;
}

template<typename ItemType>
int List<ItemType>::FindNode(ItemType x)
{
	Node<ItemType>* currNode = head;
	int currIndex = 1;
	while (currNode && currNode->data != x) {
		currNode = currNode->next;
		currIndex++;
	}
	if (currNode)
		return currIndex;
	return 0;
}

template<typename ItemType>
int List<ItemType>::DeleteNode(ItemType x)
{
	Node<ItemType>* prevNode = NULL;
	Node<ItemType>* currNode = head;
	int currIndex = 1;
	while (currNode && currNode->data != x) {
		prevNode = currNode;
		currNode = currNode->next;
		currIndex++;
	}
	if (currNode) {
		if (prevNode) {
			prevNode->next = currNode->next;
			delete currNode;
		}
		else {
			head = currNode->next;
			delete currNode;
		}
		return currIndex;
	}
	return 0;
}

template<typename ItemType>
void List<ItemType>::DisplayList(void)
{
	int num = 0;
	Node<ItemType>* currNode = head;
	while (currNode != NULL) {
		cout << currNode->data << endl;
		currNode = currNode->next;
		num++;
	}
	cout << "Number of nodes in the list: " << num << endl;
}
===============================================================================================*/
/*
template<typename ItemType>
struct Node {
public:
	ItemType data; // data
	Node* next; // pointer to next
};

template<typename ItemType>
class CircularLinkedList {
private:
	Node<ItemType>* rear;

public:
	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
	CircularLinkedList();

	// Destructor
	~CircularLinkedList();

	void insertNode(ItemType item);

	void deleteNode(ItemType item);

	void Print();

	void Rotate(int n);

	int Count();
};

template <typename ItemType>
CircularLinkedList<ItemType>::CircularLinkedList()
{
	rear = NULL;
}

template <typename ItemType>
CircularLinkedList<ItemType>::~CircularLinkedList()
{
	//TODO: by students
	if (rear == NULL) // If the list is already empty, nothing to do
		return;

	Node<ItemType>* current = rear->next; // Start from the first node
	Node<ItemType>* nextNode;

	while (current != rear) {
		nextNode = current->next; // Store the next node
		delete current; // Delete the current node
		current = nextNode; // Move to the next node
	}

	// Delete the last node (rear) and set rear to nullptr
	delete rear;
	rear = NULL;
}

template <typename ItemType>
void CircularLinkedList<ItemType>::insertNode(ItemType item)
{
	Node<ItemType>* Cur = NULL;
	Node<ItemType>* Prev = NULL;
	Node<ItemType>* New = new Node<ItemType>;
	New->data = item;
	if (rear == NULL) {	// insert into empty list
		rear = New;
		rear->next = rear;
		return;
	}

	Prev = rear;
	Cur = rear->next;
	do {				// find Prev and Cur
		if (item <= Cur->data)
			break;
		Prev = Cur;
		Cur = Cur->next;
	} while (Cur != rear->next);

	New->next = Cur;	// revise pointers
	Prev->next = New;
	if (item > rear->data)	//revise Rear pointer if adding to end
		rear = New;
}

template <typename ItemType>
void CircularLinkedList<ItemType>::deleteNode(ItemType item)
{
	Node<ItemType>* Cur = NULL;
	Node<ItemType>* Prev = NULL;
	if (rear == NULL) {
		cout << "Trying to delete empty list" << endl;
		return;
	}

	Prev = rear;
	Cur = rear->next;

	do {				// find Prev and Cur
		if (item <= Cur->data)  break;
		Prev = Cur;
		Cur = Cur->next;
	} while (Cur != rear->next);

	if (Cur->data != item) {	// data does not exist
		cout << "Data Not Found" << endl;
		return;
	}

	if (Cur == Prev) {		// delete single-node list
		rear = NULL;
		delete Cur;
		return;
	}

	if (Cur == rear)		// revise Rear pointer if deleting end
		rear = Prev;
	Prev->next = Cur->next;	// revise pointers
	delete Cur;
}

template <typename ItemType>
void CircularLinkedList<ItemType>::Print() {

	if (rear != NULL) {
		Node<ItemType>* curr = rear->next;

		do
		{
			cout << curr->data << " ";
			curr = curr->next;
		} while (curr != rear->next);

		cout << endl;
	}
}

template <typename ItemType>
int CircularLinkedList<ItemType>::Count() {

	if (rear == NULL)
		return 0;

	Node<ItemType>* curr = rear->next;
	int count = 0;
	do
	{
		count++;
		curr = curr->next;
	} while (curr != rear->next);

	return count;
}

template <typename ItemType>
void CircularLinkedList<ItemType>::Rotate(int n) {

	if (n == 0)
		return;

	if (rear != NULL) {
		n = Count() - n;
		Node<ItemType>* curr = rear->next;

		for (int i = 0; i < n - 1; i++)
		{
			curr = curr->next;
		}
		rear = curr;
	}
}
==========================================================================================*/
/*
template<typename ItemType>
struct Node {
public:
	ItemType data; // data
	Node* next; // pointer to next
	Node* prev; // pointer to previous
};

//Doubly Linked Lists with Dummy Head Node
template<typename ItemType>
class DoublyLinkedList {
private:
	Node<ItemType>* head;
public:
	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
	DoublyLinkedList(void);

	// Destructor
	~DoublyLinkedList(void);

	bool isEmpty();

	Node<ItemType>* searchNode(ItemType item);

	void insertNode(ItemType item);

	void deleteNode(ItemType item);

	void Print();

	int Count();

	void Rotate(int n);
};

template <typename ItemType>
void DoublyLinkedList<ItemType>::Print()
{
	Node<ItemType>* curr = head->next;
	while (curr != head) {
		cout << curr->data << " ";
		curr = curr->next;
	}
	cout << endl;
}

template <typename ItemType>
int DoublyLinkedList<ItemType>::Count()
{
	int count = 0;
	Node<ItemType>* curr = head->next;
	while (curr != head) {
		count++;
		curr = curr->next;
	}
	return count;
}

template <typename ItemType>
void DoublyLinkedList<ItemType>::Rotate(int n)
{
	if (n == 0)
		return;

	Node<ItemType>* firstNode = head->next;
	Node<ItemType>* lastNode = head->prev;

	Node<ItemType>* curr = head->prev;
	for (int i = 0; i < n; i++)
	{
		curr = curr->prev;
	}

	firstNode->prev = lastNode;
	lastNode->next = firstNode;

	head->prev = curr;
	head->next = curr->next;

	curr->next->prev = head;
	curr->next = head;
}

template <typename ItemType>
bool DoublyLinkedList<ItemType>::isEmpty()
{
	return (head->next == head);
}

template <typename ItemType>
Node<ItemType>* DoublyLinkedList<ItemType>::searchNode(ItemType item)
{
	Node<ItemType>* Cur = head->next;

	while (Cur != head) {

		if (Cur->data == item)
			return Cur;

		if ((Cur->data) < item)
			Cur = Cur->next;
		else
			break;
	}

	return NULL;
}

template <typename ItemType>
DoublyLinkedList<ItemType>::DoublyLinkedList()
{
	head = new Node<ItemType>;
	head->next = head;
	head->prev = head;
}

template <typename ItemType>
DoublyLinkedList<ItemType>::~DoublyLinkedList()
{
	//TODO: By students.

	// Start from the node after the head
	Node<ItemType>* current = head->next;
	Node<ItemType>* nextNode;

	// Traverse the list until we reach the head node again
	while (current != head) {
		nextNode = current->next; // Store the next node
		delete current; // Delete the current node
		current = nextNode; // Move to the next node
	}

	// Delete the head node
	delete head;
}

template <typename ItemType>
void DoublyLinkedList<ItemType>::insertNode(ItemType item)
{
	Node<ItemType>* New = NULL;
	Node<ItemType>* Cur = NULL;
	New = new Node<ItemType>;
	New->data = item;

	Cur = head->next;
	while (Cur != head) { //position Cur for insertion
		if ((Cur->data) < item)
			Cur = Cur->next;
		else
			break;
	}

	New->next = Cur;
	New->prev = Cur->prev;
	Cur->prev = New;
	(New->prev)->next = New;
}

template <typename ItemType>
void DoublyLinkedList<ItemType>::deleteNode(ItemType item)
{
	Node<ItemType>* Cur;
	Cur = searchNode(item);

	if (Cur != NULL) {
		Cur->prev->next = Cur->next;
		Cur->next->prev = Cur->prev;
		delete Cur;
	}
}
=======================================================================================*/
/*
// The class definition for QueueType using templates
class FullQueue
	// Exception class thrown by enqueue when Queue is full.
{
};

class EmptyQueue
	// Exception class thrown by dequeue and first when Queue is empty.
{
};
template<typename ItemType>
class QueueType
{
private:
	int front;
	int rear;
	ItemType* items;
	int maxQue;
	int counter;

public:

	// Class constructor.
	QueueType();

	// Parameterized constructor.
	QueueType(int max);

	// Destructor
	~QueueType();

	// Function: Determines whether the queue is full.
	// Pre:  Queue has been initialized.
	// Post: Function value = (queue is full)
	bool IsFull() const;

	// Function: Determines whether the queue is empty.
	// Pre:  Queue has been initialized.
	// Post: Function value = (queue is empty)
	bool IsEmpty() const;

	// Function: makes the queue empty.
	// Pre:  Queue has been initialized.
	// Post: Queue is empty
	void MakeEmpty();

	// Function: Adds newItem to the end of the queue.
	// Pre:  Queue has been initialized.
	// Post: If (Queue is full), FullQueue exception is thrown;
	//       otherwise, newItem is at the end of the queue.
	void Enqueue(ItemType);

	// Function: Removes item from the queue that was inserted.
	// Pre:  Queue has been initialized.
	// Post: If (Queue is empty), EmptyQueue exception is thrown;
	//       otherwise, Removes item from the queue that was inserted
	ItemType Dequeue();

	// Function: Returns a copy of item on the queue.
	// Pre:  Queue has been initialized.
	// Post: If (queue is empty), EmptyQueue exception is thrown;
	//       otherwise, Removes item from the queue that was inserted
	ItemType First();

	int GetLength();

	void DisplayQueue();
};

template<typename ItemType>
QueueType<ItemType>::QueueType()
{
	maxQue = 501; //Default
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue];
	counter = 0;
}

template<typename ItemType>
QueueType<ItemType>::QueueType(int max)
{
	maxQue = max;
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue];
	counter = 0;
}

template<typename ItemType>
QueueType<ItemType>::~QueueType()
{
	delete[] items;
}

template<typename ItemType>
bool QueueType<ItemType>::IsFull() const
{
	//return ((rear + 1) % maxQue == front);
	return counter == maxQue;
}

template<typename ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
	//return (rear == front);
	return counter == 0;
}

template<typename ItemType>
void QueueType<ItemType>::MakeEmpty()
{
	front = maxQue - 1;
	rear = maxQue - 1;
	counter = 0;
}

template<typename ItemType>
void QueueType<ItemType>::Enqueue(ItemType newItem)
{
	if (IsFull())
	{
		throw FullQueue();
	}
	else
	{
		rear = (rear + 1) % maxQue;
		counter++;
		items[rear] = newItem;
	}
}

template<typename ItemType>
ItemType QueueType<ItemType>::Dequeue()
{
	if (IsEmpty())
	{
		throw EmptyQueue();
	}
	else
	{
		front = (front + 1) % maxQue;
		counter--;
		return items[front];
	}
}

template<typename ItemType>
ItemType QueueType<ItemType>::First()
{
	if (IsEmpty())
	{
		throw EmptyQueue();
	}
	else
	{
		return items[(front + 1) % maxQue];
	}
}

template<typename ItemType>
int QueueType<ItemType>::GetLength()
{
	return counter;
}

template<typename ItemType>
void QueueType<ItemType>::DisplayQueue() {

	for (int i = 1; i <= GetLength(); i++)
	{
		ItemType temp = Dequeue();
		cout << temp << " ";
		Enqueue(temp);
	}
	cout << endl;

}
===========================================================================================*/

/*
template<class ItemType>
class QueueTypeLinked {
public:
	QueueTypeLinked();
	~QueueTypeLinked();
	void MakeEmpty();
	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(ItemType);
	ItemType Dequeue();
	int Length();
private:
	Node<ItemType>* qFront;
	Node<ItemType>* qRear;
};

template<class ItemType>
QueueTypeLinked<ItemType>::QueueTypeLinked()
{
	qFront = NULL;
	qRear = NULL;
}

template<class ItemType>
void QueueTypeLinked<ItemType>::MakeEmpty()
{
	Node<ItemType>* tempPtr;

	while (qFront != NULL) {
		tempPtr = qFront;
		qFront = qFront->next;
		delete tempPtr;
	}
	qRear = NULL;
}

template<class ItemType>
QueueTypeLinked<ItemType>::~QueueTypeLinked()
{
	MakeEmpty();
}

template<class ItemType>
bool QueueTypeLinked<ItemType>::IsEmpty() const
{
	return(qFront == NULL);
}

template<class ItemType>
bool QueueTypeLinked<ItemType>::IsFull() const
{
	Node<ItemType>* ptr;

	//We test to create a node in the memory (It its created then the memory isn't full)
	ptr = new Node<ItemType>;
	if (ptr == NULL)
		return true;
	else {
		delete ptr;
		return false;
	}
}

template<class ItemType>
void QueueTypeLinked<ItemType>::Enqueue(ItemType newItem)
{
	Node<ItemType>* newNode;

	newNode = new Node<ItemType>;
	newNode->data = newItem;
	newNode->next = NULL;
	if (qRear == NULL)
		qFront = newNode;
	else
		qRear->next = newNode;
	qRear = newNode;
}

template<class ItemType>
ItemType QueueTypeLinked<ItemType>::Dequeue()
{
	Node<ItemType>* tempPtr;

	tempPtr = qFront;
	ItemType item = qFront->data;
	qFront = qFront->next;
	if (qFront == NULL)
		qRear = NULL;
	delete tempPtr;
	return item;
}

template<class ItemType>
int QueueTypeLinked<ItemType>::Length()
{
	QueueTypeLinked<ItemType> tempQ;
	ItemType item;
	int length = 0;

	while (!IsEmpty())
	{
		item=Dequeue();
		tempQ.Enqueue(item);
		length++;
	}

	while (!tempQ.IsEmpty())
	{
		item=tempQ.Dequeue();
		Enqueue(item);
	}

	return length;
}
=====================================================================================*/
/*
// The class definition for StackType using templates
class FullStack
	// Exception class thrown by Push when stack is full.
{
};

class EmptyStack
	// Exception class thrown by Pop and Top when stack is empty.
{
};


template<typename ItemType>
class StackType
{
private:
	int top;
	int maxStack;
	ItemType* items;

public:

	// Class constructor.
	StackType();

	// Parameterized constructor.
	StackType(int max);

	// Destructor
	~StackType();

	// Function: Determines whether the stack is full.
	// Pre:  Stack has been initialized.
	// Post: Function value = (stack is full)
	bool IsFull() const;

	// Function: Determines whether the stack is empty.
	// Pre:  Stack has been initialized.
	// Post: Function value = (stack is empty)
	bool IsEmpty() const;

	// Function: makes the stack empty.
	// Pre:  Stack has been initialized.
	// Post: Stack is empty
	void MakeEmpty() const;

	// Function: Adds newItem to the top of the stack.
	// Pre:  Stack has been initialized.
	// Post: If (stack is full), FullStack exception is thrown;
	//       otherwise, newItem is at the top of the stack.
	void Push(ItemType item);

	// Function: Removes top item from the stack.
	// Pre:  Stack has been initialized.
	// Post: If (stack is empty), EmptyStack exception is thrown;
	//       otherwise, top element has been removed from stack.
	ItemType Pop();

	// Function: Returns a copy of top item on the stack.
	// Pre:  Stack has been initialized.
	// Post: If (stack is empty), EmptyStack exception is thrown;
	//       otherwise, top element has been removed from stack.
	ItemType Top();

	int GetLength();

	void Print();
};

// The function definitions for class StackType.

template<typename ItemType>
StackType<ItemType>::StackType(int max)
{
	maxStack = max;
	top = -1;
	items = new ItemType[maxStack];
}

template<typename ItemType>
StackType<ItemType>::StackType()
{
	maxStack = 500;  //Default
	top = -1;
	items = new ItemType[maxStack];
}

template<typename ItemType>
bool StackType<ItemType>::IsEmpty() const
{
	return (top == -1);
}

template<typename ItemType>
void StackType<ItemType>::MakeEmpty() const
{
	top = -1;
}

template<typename ItemType>
bool StackType<ItemType>::IsFull() const
{
	return (top == maxStack - 1);
}

template<typename ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{

	if (IsFull())
		throw FullStack();
	top++;
	items[top] = newItem;
}

template<typename ItemType>
ItemType StackType<ItemType>::Pop()
{
	if (IsEmpty())
		throw EmptyStack();
	return items[top--];
}

template<typename ItemType>
ItemType StackType<ItemType>::Top()
{
	if (IsEmpty())
		throw EmptyStack();
	return items[top];
}

template<typename ItemType>
int StackType<ItemType>::GetLength()
{
	return top + 1;
}

template<typename ItemType>
StackType<ItemType>::~StackType()
{
	delete[] items;
}
================================================================================================*/
/*
template<class ItemType>
class StackTypeLinked {
public:
	StackTypeLinked();
	~StackTypeLinked();
	void MakeEmpty();
	bool IsEmpty() const;
	bool IsFull() const;
	void Push(ItemType);
	ItemType Pop();
private:
	Node<ItemType>* topPtr;
};

template<class ItemType>
StackTypeLinked<ItemType>::StackTypeLinked()
{
	topPtr = NULL;
}

template<class ItemType>
void StackTypeLinked<ItemType>::MakeEmpty()
{
	Node<ItemType>* tempPtr;

	while (topPtr != NULL) {
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}

template<class ItemType>
StackTypeLinked<ItemType>::~StackTypeLinked()
{
	MakeEmpty();
}

template<class ItemType>
bool StackTypeLinked<ItemType>::IsEmpty() const
{
	return(topPtr == NULL);
}

template<class ItemType>
bool StackTypeLinked<ItemType>::IsFull() const
{
	Node<ItemType>* location;

	//We test to create a node in the memory (It its created then the memory isn't full)
	location = new Node<ItemType>;
	if (location == NULL)
		return true;
	else {
		delete location;
		return false;
	}
}

template<class ItemType>
void StackTypeLinked<ItemType>::Push(ItemType newItem)
{
	Node<ItemType>* location;

	location = new Node<ItemType>;
	location->data = newItem;
	location->next = topPtr;
	topPtr = location;
}

template<class ItemType>
ItemType StackTypeLinked<ItemType>::Pop()
{
	Node<ItemType>* tempPtr;

	ItemType item = topPtr->data;
	tempPtr = topPtr;
	topPtr = topPtr->next;
	delete tempPtr;
	return item;
}


========================================================================================*/

int main(){

    return 0;
}