//Singly Linked List: Integers with insertion sorting, selection sorting and bubble sorting
#include <iostream>
using std::cout;
using std::endl;
using std::cin;

class Node
{
public:
	Node( int );
	~Node();
	void updateData( int );
	
	int data;
	Node* next;

};

Node::Node( int newData )
{
	data = newData;
	
	next = NULL;
}

Node::~Node()
{
	next = NULL;
}

void Node::updateData( int n )
{
	data = n;
}

class LinkedList
{
public:
	LinkedList();
	~LinkedList();
	
	void addLast( int );
	void addFirst( int );
	
	
	/******* Call By Refernce *******/
	void addNodeBefore( int sd, int nd ) { addNodeBefore( sd, nd, firstPtr ); }
	void addNodeBefore( int, int, Node*& );
 	/******* Call By Refernce *******/
	
	
	//void addNodeBefore( int, int );
	
	//void deleteList();
	//void deleteNode( int );
	
	bool isEmpty() const;
	int getSize() const;
	void print() const;
	Node* getLast() const;
	
	void compress();
	
	//##SORTING FUNCTIONS##
	void insertionSort();
	void selectionSort();
	void bubbleSort();
	void quickSort( Node*, Node* );
	void quickSortRE( Node*, Node* ); // big -> small 
	void mergeSort( Node*, Node* );
	
	Node* partition( Node*, Node* );
	Node* partitionRE( Node*, Node* ); // big -> small 
	int getIndex( Node* );
	
	Node* getNode( int, Node* );
	void mergeTwoSortedLL( Node*, Node*, Node*, Node* );
	//##SORTING FUNCTIONS##
	
	/* SEARCH FUNCTION: Binary Search */
	//Node* binarySearch( int );
	Node* getMiddle( Node*, Node* );

	void reverse();
	void duplicate();
	void swap( Node*, Node* );// swap data only
	
	Node* getPrev( Node* );
	
	// ###NEW FUNCTION###
	bool binarySearch( int );
	bool isSorted();
	void deleteAll();
	// ###NEW FUNCTION###

//private:
	Node* firstPtr;
};

LinkedList::LinkedList()
{
	firstPtr = NULL;
}

LinkedList::~LinkedList()
{
	firstPtr = NULL;
}

void LinkedList::addLast( int nd )
{
	Node* newNode = new Node( nd );
	Node* currentPtr = firstPtr;
	
	if ( currentPtr != NULL )
		{
		while ( currentPtr -> next != NULL )
			currentPtr = currentPtr -> next;
		
		currentPtr -> next = newNode;
		}
	else
		firstPtr = newNode;
}

void LinkedList::addFirst( int nd )
{
	Node* newNode = new Node( nd );
	
	if ( firstPtr != NULL )
		{
		newNode -> next = firstPtr;
		firstPtr = newNode;
		}
	else
		firstPtr = newNode;
}

//void LinkedList::addNodeAfter()
//void LinkedList::addNodeBefore()
//void LinkedList::deleteList()
//void LinkedList::deleteNode()

bool LinkedList::isEmpty() const
{
	return firstPtr == NULL;
}

int LinkedList::getSize() const
{
	int count=0;
	Node* currentPtr = firstPtr;
	
	while ( currentPtr != NULL )
		{
		currentPtr = currentPtr -> next;
		count++;
		}
	
	return count;
}

void LinkedList::print() const
{
	Node* currentPtr = firstPtr;
	if ( currentPtr != NULL )
		{
		while ( currentPtr != NULL )
			{
			cout << currentPtr -> data << endl;
			currentPtr = currentPtr -> next;
			}
		}
	else
		cout <<"The list is empty.\n";
}

Node* LinkedList::getLast() const
{
	Node* currentPtr = firstPtr;
	
	while ( currentPtr -> next != NULL )
		currentPtr = currentPtr -> next;
	
	return currentPtr;	
}

void LinkedList::compress()
{
	if ( firstPtr != NULL )
		{
		Node* currentPtr = firstPtr -> next;
		Node* prevPtr = firstPtr;
		
		while ( currentPtr != NULL )
			{
			if ( prevPtr -> data == currentPtr -> data )
				{
				prevPtr -> next = currentPtr -> next;
				delete currentPtr;
				currentPtr = prevPtr -> next;
				}
			else
				{
				prevPtr = currentPtr;
				currentPtr = currentPtr -> next;
				}
			}
		}
}

void LinkedList::swap( Node* n1, Node* n2 )// swap data only
{
	int tempValue;
    tempValue = n1 -> data;
	n1 -> updateData( n2 -> data );
	n2 -> updateData( tempValue );
}

Node* LinkedList::getPrev( Node* currentPtr )
{
	Node* current = firstPtr;
	
	while ( current != NULL )
		{
		if ( current -> next == currentPtr )
			break;
		
		current = current -> next;
		}
	
	return current;
}

void LinkedList::insertionSort()
{
	int n = getSize();
	int i;
	int j;
	
	Node* currentPtr = NULL;
	Node* currentRecord = firstPtr;
	Node* tempPrev;
	
	if ( currentRecord != NULL && currentRecord -> next != NULL ) // do not sort if there is only one or 0 node
		{
		for ( i = 1 ; i < n ; i++ )
			{
			
			currentRecord = currentRecord -> next;
			currentPtr = currentRecord;
			
			for(  j = 0 ; j < i ; j++ )
				{
				tempPrev = getPrev( currentPtr );
				
				if ( currentPtr -> data < tempPrev -> data )
					swap( currentPtr, tempPrev );
					
				currentPtr = tempPrev;
				}
			}
		}
}

void LinkedList::selectionSort()
{
	Node* currentPtr = firstPtr;
	Node* miniPtr = NULL;
	Node* searchPtr = NULL;
	
	int n = getSize();
	int i;
	int j;
	
	for ( i = 0 ; i < n ; i++ )
		{
		miniPtr = currentPtr;
		searchPtr = currentPtr -> next;
		
		for ( j = i + 1 ; j < n ; j++ )
			{
			if ( ( searchPtr -> data ) < ( miniPtr -> data ) )
				miniPtr = searchPtr;
			
			searchPtr = searchPtr -> next;
			}
		
		swap( currentPtr, miniPtr );
			
		currentPtr = currentPtr -> next;
		}
}

void LinkedList::bubbleSort()
{
	Node* currentPtr = firstPtr -> next;
	Node* prevPtr = firstPtr;
	
	int n = getSize();
	
	bool stillSwapping = true;
	
	for ( int i = 0 ; i < n - 1 && stillSwapping ; i++ )
		{
		stillSwapping = false;
		
		prevPtr = firstPtr;
		currentPtr = firstPtr -> next;
		
		for ( int j = 0 ; j < n - 1 - i ; j++ )
			{
			if ( ( prevPtr -> data ) > ( currentPtr -> data ) )
				{
				swap( currentPtr, prevPtr );
				stillSwapping = true;
				}
			
			prevPtr = prevPtr -> next;
			currentPtr = currentPtr -> next;
			}
		}
}

Node* LinkedList::partition( Node* low, Node* high )
{
	Node* left;
	Node* right;
	Node* pivot;
	
	int pivotValue;
	
	pivotValue = low -> data;
	
	left = low;
	pivot = left;
	
	right = high;
	
	while ( getIndex( left ) < getIndex( right ) )
		{
		while ( left -> data <= pivotValue && getIndex( left ) <= getIndex( high ) )
			left = left -> next;

		while ( right -> data > pivotValue && getIndex( right ) >= getIndex( low ) )
			right = getPrev( right );

		if ( getIndex( left ) < getIndex( right ) )
			swap( left, right );
		}
	low -> data = right -> data;
	right -> data = pivotValue;
	
	return right;
}

void LinkedList::quickSort( Node* first, Node* last )
{
	Node* pivot;
	if ( getIndex( last ) > getIndex( first ) )
		{
		pivot = partition( first, last );
		quickSort( first, getPrev( pivot ) );
		quickSort( pivot -> next, last );
		}
}

Node* LinkedList::partitionRE( Node* first, Node* last )
{
	Node* left;
	Node* right;
	Node* pivot;
	
	int pivotValue;
	
	pivotValue = first -> data;
	
	left = first;
	pivot = left;
	
	right = last;
	
	while ( getIndex( left ) < getIndex( right ) )
		{
		while ( left -> data >= pivotValue && getIndex( left ) <= getIndex( last ) )
			left = left -> next;

		while ( right -> data < pivotValue && getIndex( right ) >= getIndex( first ) )
			right = getPrev( right );

		if ( getIndex( left ) < getIndex( right ) )
			swap( left, right );
		}
	first -> data = right -> data;
	right -> data = pivotValue;
	
	return right;
}

void LinkedList::quickSortRE( Node* first, Node* last )
{
	Node* pivot;
	if ( getIndex( last ) > getIndex( first ) )
		{
		pivot = partitionRE( first, last );
		quickSortRE( pivot -> next, last );
		quickSortRE( first, getPrev( pivot ) );
		}
}

/*
void LinkedList::mergeSort( Node* low, Node* high )
{
	if ( getIndex( low ) == getIndex( high ) )
		return;
	
	int length = getIndex( high ) - getIndex( low ) + 1;
	Node* pivot = getNode( ( getIndex( high ) + getIndex( low ) ) / 2, low );
	mergeSort( low, pivot );
	mergeSort( pivot -> next, high );
	
	Node* m1 = firstPtr;
	Node* m2 = getNode( getIndex( pivot) - getIndex( low ) + 1, firstPtr );
	
	mergeTwoSortedLL(lop,pivot, pivot->next,high);

	
}*/

int LinkedList::getIndex( Node* sd )
{
	Node* current = firstPtr;
	int count = 0;
	
	if ( sd == NULL ) 
		return -1;
	
	while ( current != NULL )
		{
		if ( ( current -> data ) == ( sd -> data ) )
			break;
		
		count++;
		current = current -> next;
		}
	return count;
}

/*
Node* LinkedList::getNode( int n , Node* firstNode )
{
	Node* currentPtr = firstNode;
	for ( int i = 0 ; i < n ; i++ )
		currentPtr = currentPtr -> next;
	
	return currentPtr;
}*/
/*
Node* LinkedList::binarySearch( int key )
{
	Node* first = firstPtr;
	Node* last = firstPtr;
	
	while ( last -> next != NULL )
		last = last -> next;
	
	if ( key < first -> data || key > last -> data )
		return NULL;
	
	while ( getIndex( first ) <= getIndex( last ) )// 
		{
		Node* middle = getMiddle( first, last );
		
		if ( key == middle -> data )
			return middle;
		
		if ( key < middle -> data )
			last = getPrev( middle );
		
		if ( key > middle -> data )
			first = middle -> next;
		}
	
	return NULL;
}*/

Node* LinkedList::getMiddle( Node* n1, Node* n2 )
{
	Node* currentPtr = firstPtr;
	
	int index1 = getIndex( n1 );
	int index2 = getIndex( n2 );
	
	int middleIndex = ( index1 + index2 ) /2;
	
	for ( int i=0 ; i < middleIndex ; i++ )
		currentPtr = currentPtr -> next;
	
	return currentPtr;
}

void LinkedList::addNodeBefore( int sd, int nd, Node*& nodePtr )
{
	if ( nodePtr -> data == sd )
		{
		Node* newNode = new Node( nd );
		newNode -> next = nodePtr;
		nodePtr = newNode;
		}
	else
		addNodeBefore( sd, nd, nodePtr -> next );
}

void LinkedList::duplicate()
{
	/*Node* currentPtr = firstPtr;

	while ( currentPtr != NULL )
		{
		Node* newNode = new Node( currentPtr->data );
		newNode ->next = currentPtr->next;
		currentPtr->next = newNode;
		currentPtr = currentPtr->next->next;
		}
	*/
	/********************************************************
	*/
	Node* currentPtr = firstPtr;
	
	while ( currentPtr != NULL )
		addNodeBefore(currentPtr->data,currentPtr->data);
	/*	
	********************************************************/
}

void LinkedList::reverse()
{
	if ( firstPtr != NULL )
		{
		if ( firstPtr -> next == NULL )
			cout <<"Cannot reverse, there is one node.\n";
		else
			{
			Node* prevPtr = firstPtr;
			Node* currentPtr = firstPtr -> next;
			Node* temp = currentPtr -> next;
			
			if ( temp != NULL )
				{
				prevPtr -> next = NULL;
				currentPtr -> next = prevPtr;
			
				prevPtr = currentPtr;
				currentPtr = temp;
				temp = temp -> next;
			
				while ( temp != NULL )
					{
					currentPtr -> next = prevPtr;
					prevPtr = currentPtr;
					currentPtr = temp;
					temp = temp -> next;
					}
				
				currentPtr -> next = prevPtr;
				firstPtr = currentPtr;
				}
			else
				{
				firstPtr = currentPtr;
				currentPtr -> next = prevPtr;
				prevPtr -> next = NULL;
				}
			}
		}
	else
		cout <<"Cannot reverse, there is no nodes.\n";
	
}

bool LinkedList::isSorted()
{
	Node* currentPtr = firstPtr;
	
	while ( currentPtr -> next != NULL )
		if ( currentPtr -> data > currentPtr -> next -> data )
			return false;
		else
			currentPtr = currentPtr -> next;
	
	return true;
}

bool LinkedList::binarySearch( int k )
{
	if ( isSorted() )
		{
		Node* first = firstPtr;
		Node* last = getLast();
		Node* middle;
		
		if ( k < first -> data || k > last -> data )
			return false;
		else
			{
			while( getIndex( first ) <= getIndex( last ) )
				{
				middle = getMiddle( first, last );
				if ( k == middle -> data )
					return true;
				else
					if ( k < middle -> data )
						last = getPrev( middle );
					else
						if ( k > middle -> data )
							first = middle -> next;
				}
			return false;
			}
		}
	else
		return false;
}

void LinkedList::deleteAll()
{
	Node* currentPtr = firstPtr;
	Node* temp = NULL;
	
	while ( currentPtr != NULL )
		{
		temp = currentPtr -> next;
		delete currentPtr;
		currentPtr = temp;
		}
	
	firstPtr = NULL;
}

int main()
{
	LinkedList list1;
	//cout << list1.isEmpty() << endl;
	
	list1.addLast( 3 );
    list1.addLast( 15 );
	list1.addLast( 22 );
	list1.addLast( 24 );
	list1.addLast( 48 );
	list1.addLast( 60 );
	//list1.addLast( 67 );
	
	//list1.addLast( 13 );
	//list1.addNodeBefore( 22, 101 );

	cout <<"\nNumber of nodes: " << list1.getSize() << endl;
	list1.print();
    
	int sd = 22;
	
    if ( list1.binarySearch( sd ) )
		cout << sd <<" found!\n";
    
    //list1.reverse();
    
    
	//list1.compress();
	//list1.insertionSort();
	//list1.selectionSort();
	//list1.bubbleSort();
	//Node* first = list1.firstPtr;
	//Node* last = list1.getLast();
	//list1.quickSort( first, last );
	//list1.quickSortRE( first, last );
	//if ( list1.binarySearch( 67 ) )
	//	cout <<"Found!\n";
	//else
	//	cout <<"Not found :(\n";
	
	list1.deleteAll();
	
	cout <<"\nNumber of nodes: " << list1.getSize() << endl;
	list1.print();
	//cout << list1.isEmpty() << endl;
	
	//int i;
	//cin >>i;
	
	system("PAUSE");
	return 0;
}