Assignment1_Khaled

#include <iostream>
using namespace std;

// ================== Class Node ========================

template<typename T>
class Node
{
private :
	T item;	
	Node<T>* next;	
public :

	Node( )
	{
		next= nullptr;
	} 

	Node( T newItem) 
	{
		item = newItem;
		next= nullptr;

	}

	void setItem( T newItem)
	{
		item = newItem;
	} 

	void setNext(Node<T>* nextNodePtr)
	{
		next = nextNodePtr;
	} 

	T getItem() const
	{
		return item;
	} 

	Node<T>* getNext() const
	{
		return next;
	}
}; // end Node

// ================== Class Linked List ========================

template <typename T>
class LinkedList
{
private:
	Node<T> *Head;

public:

	LinkedList()
	{
		Head = nullptr;
	}

	~LinkedList()
	{
		DeleteAll(); 
	}

	// Prints the linked list in the required format
	// DON'T CHANGE ANYTHING INSIDE THIS FUNCTION *********
	// BECAUSE THE AUTOMATIC JUDGE COMPARES FOR THIS FORMAT
	void PrintList()	const
	{
		Node<T> *p = Head;
		while(p)
		{
			cout << p->getItem() << " ";
			p = p->getNext();
		}
		cout << endl;
	}

	// DO NOT CHANGE ANYTHING IN THIS FUNCTION *********
	void ReadList() 
	{
		int val;
		cin>>val;
		while(val != -1)
		{
			this->InsertEnd(val);
			cin>>val;
		}
	}

	// you should NOT change this function
	void InsertEnd(const T &data)
	{
		Node<T> *R = new Node<T>(data);
		if (!Head)
		{
			Head = R;
			return;
		}
		Node<T> *p = Head;
		while (p->getNext())
			p = p->getNext();
		p->setNext(R);
	}

	void DeleteAll()
	{
		Node<T> *P = Head;
		while (Head)
		{
			P = Head->getNext();
			delete Head;
			Head = P;
		}
	}


	//////////////////////////////////////////

	/// TODO: ADD ANY REQUIRED FUNCTIONS HERE

	int countAnomalies() {
		int c = 0;
		Node<T>* ptr1 = Head;
		if (ptr1) {
			Node<T>* ptr2 = ptr1->getNext();
			if (ptr2) {
				Node<T>* ptr3 = ptr2->getNext();

				while (ptr3) {
					
					if ((ptr1->getItem() + ptr2->getItem()) < ptr3->getItem())
						c++;
					ptr1 = ptr2;
					ptr2 = ptr3;
					ptr3 = ptr3->getNext();
				}

			}
		}
		return c;
	}

	void insertBeforePositive() {
		Node<T>* curr = Head;
		Node<T>* prev = Head;
		while (curr) {
			if (curr->getItem() > 0) {
				Node<T>* Negative = new Node<T>;
				Negative->setItem(-1 * curr->getItem());
				Negative->setNext(curr);
				if (curr == Head)
					Head = Negative;
				else
					prev->setNext(Negative);
			}
			prev = curr;
			curr = curr->getNext();
		}
	}

	void deleteSecondLargest() {
		Node<T>* curr = Head;
		int max1 = 0, max2 = 0;
		if (Head) {
			max1 = curr->getItem();
			max2 = max1;
		}

		// Find Second Largest Element
		while (curr) {
			if (curr->getItem() > max1) {
				max2 = max1;
				max1 = curr->getItem();
			}
			else if (curr->getItem() != max1 && curr->getItem() > max2) {
				max2 = curr->getItem();
			}
			curr = curr->getNext();
		}
		if (max1 == max2)
			return;

		// Deleting Second Largest Element
		curr = Head;
		Node<T>* prev = NULL;
		while (curr) {
			if (curr->getItem() == max2) {
				Node<T>* tmp = curr;
				curr = curr->getNext();
				if (tmp == Head) {
					Head = curr;
				}
				else
					prev->setNext(curr);
				delete tmp;
			}
			else {
				prev = curr;
				curr = curr->getNext();
			}
		}
	}

	void reverseHalf() {
		Node<T>* curr = Head;
		int c = 0;
		while (curr) {
			curr = curr->getNext();
			c++;
		}
		int half;
		if ((c % 2) == 1)
			half = (c / 2) + 1;
		else
			half = c / 2;

		if (c < 2)
			return;

		c = 0;
		curr = Head;
		Node<T>* prev = NULL;
		Node<T>* next = NULL;
		Node<T>* oldHead = Head;
		while (c < half) {
			next = curr->getNext();
			curr->setNext(prev);
			prev = curr;
			curr = next;
			c++;
		}
		oldHead->setNext(curr);
		Head = prev;

	}

	
	void sortedOddsAndEvens(LinkedList<T>* L2) {
		Node<T>* prev1 = NULL;
		Node<T>* prev2 = NULL;
		Node<T>* curr1 = this->Head;
		Node<T>* curr2 = L2->Head;
		
		LinkedList<T>* evenL = new LinkedList<T>;
		LinkedList<T>* oddL = new LinkedList<T>;

		while (curr1 || curr2) {
			if (curr1 && curr1->getItem() % 2 != 0 && curr1 != prev1) {
				oddL->InsertEnd(curr1->getItem());
				prev1 = curr1;
			}
			else if (curr1 && curr1->getItem() % 2 == 0 && curr1 != prev1)
			{
				evenL->InsertEnd(curr1->getItem());
				prev1 = curr1;
			}
			if (curr2 && curr2->getItem() % 2 != 0 && curr2 != prev2) {
				oddL->InsertEnd(curr2->getItem());
				prev2 = curr2;
			}
			else if (curr2 && curr2->getItem() % 2 == 0 && curr2 != prev2)
			{
				evenL->InsertEnd(curr2->getItem());
				prev2 = curr2;
			}

			
			if (curr1) {
				if (curr2 && curr2->getNext() && curr1->getNext()) {
					if (curr1->getNext()->getItem() <= curr2->getNext()->getItem()) {
						curr1 = curr1->getNext();
					}
				}
				else
					curr1 = curr1->getNext();
			}

			if (curr2) {
				if (curr1 && curr1->getNext() && curr2->getNext()) {
					if (curr1->getNext()->getItem() >= curr2->getNext()->getItem()) {
						curr2 = curr2->getNext();
					}
				}
				else
					curr2 = curr2->getNext();
			}
		}

		this->Head = oddL->Head;
		L2->Head = evenL->Head;
		
	}

	//////////////////////////////////////////


}; // end of class LinkedList


// ================== The Main Function ========================

/// TODO: This main is partially implemented, complete it to be exactly as specified in the requirements' document
int main()
{

	//Don’t use any cin or cout in the code 
	// (except in [“choice” equals 1] part in the main function and must be exactly the same as required). 
	// Whenever you want to read or print linked list elements, just use:
	//-	 L.PrintList ( ) when you want to print the elements of linked list L to the user.
	//-	 L.ReadList ( ) when you want to read the elements of linked list L from the user.
	// Note: you must NOT change the implementation of these functions: L.PrintList() or L.ReadList().
	try {
		int choice;
		cin >> choice;
		if (choice == 1)
		{
			/// TODO: Put the needed code here
			LinkedList<int> L1;
			L1.ReadList();
			int ca = L1.countAnomalies();
			std::cout << ca;

		}
		else if (choice == 2)
		{
			/// TODO: Put the needed code here
			LinkedList<int> L1;
			L1.ReadList();
			L1.insertBeforePositive();
			L1.PrintList();
		}
		else if (choice == 3)
		{
			/// TODO: Put the needed code here
			LinkedList<int> L1;
			L1.ReadList();
			L1.deleteSecondLargest();
			L1.PrintList();

		}
		else if (choice == 4)
		{
			/// TODO: Put the needed code here
			LinkedList<int> L1;
			L1.ReadList();
			L1.reverseHalf();
			L1.PrintList();
		}
		else if (choice == 5)
		{
			/// TODO: Put the needed code here
			LinkedList<int> L1;
			LinkedList<int> L2;
			L1.ReadList();
			L2.ReadList();
			L1.sortedOddsAndEvens(&L2);
			L1.PrintList();
			L2.PrintList();

		}
	}
	catch (...) {
		cout << "Exception";
	}

	
	// Note: Do [NOT] write system("pause") or cin >> c; or anything similar to halt execution
	return 0;
}