//=============================================================================
// MergeSort.cpp
// Written by:    Unknown, 
//
// Last Modified: Fall 2020
//
// Description: This sample demonstrates how to use STL's vectors container 
//              to implement a mergeSort (mostly 'by-hand') 
//
// Do NOT use std::list::sort  (defeats the gain in understanding)
// You may use std::list::merge (saves some time)
//
// Tasks: find the TODOs and do them
//
//=============================================================================
#include <iostream>
#include <vector>

using namespace std;

// ------------------------------------------------------------------------
// TODO:
// First create a new type, which represents a sequence of ints
// using type std::vector.
// This reduces code clutter and helps in maintaining code
// ------------------------------------------------------------------------
typedef vector< int > myVectorType;



// ------------------------------------------------------------------------
// ProtoTypes of global functions
// ------------------------------------------------------------------------
// TODO: create a prototype declaration of printContents as defined (far) below
void printContents( myVectorType v, bool withHeader  );
void mergeSortInPlace(myVectorType& seqPtr, int startIdx, int endIdx);
void merge(myVectorType& seqPtr, int startIdx, int midIdx, int endIdx);

// ------------------------------------------------------------------------
// main function - it all begins here
// ------------------------------------------------------------------------
int main( void )
{
    //---------------------------------------------------------------------
    // TODO: Create the initial vector 
    myVectorType myNumberList;

    // TODO: Initialize the first few numbers in our list
    //       Use the vector function push_back
    myNumberList.push_back( 7 );
    myNumberList.push_back( 2 );
    myNumberList.push_back( 9 );
    myNumberList.push_back( 4 );
    myNumberList.push_back( 3 );
    myNumberList.push_back( 8 );
    myNumberList.push_back( 6 );
    myNumberList.push_back( 1 );

    // Print out the contents for inspection
    printContents( myNumberList, true );
    
    // TODO:
    // Call the mergeSort function
    mergeSortInPlace(myNumberList, 0, myNumberList.size() -1 );

    // Print out the contents for inspection
    printContents( myNumberList, true );

    // TODO: Repeat with a  different set of numbers
    cout << "\n---------------------------------------- next\n\n";
    myVectorType numList2;
    numList2.push_back( 23 );
    numList2.push_back( 56 );
    numList2.push_back( 732 );
    numList2.push_back( 2 );
    numList2.push_back( 338 );
    numList2.push_back( 25 );
    numList2.push_back( -45 );
    numList2.push_back( 18 );
    printContents( numList2, true );
    mergeSortInPlace(numList2, 0, numList2.size() -1 );
    printContents( numList2, true );

    return 0;   // zero indicates program success to the operating system

} // end main()

//-------------------------------------------------------------------------
// printContents
//-------------------------------------------------------------------------
void printContents( myVectorType v, bool withHeader )
{
    //---------------------------------------------------------------------
    // Using iterators, 
    // which point to the beginning and ending of the vector,  
    // loop through the vector and print out its contents

    // TODO: use the vector functions begin and end to initialize the below correctly
    myVectorType::iterator it_cur   = v.begin();
    myVectorType::iterator it_end   = v.end();

    if (true == withHeader)
    {
       cout << "Contents of the vector: \n     ";
   }

    // TODO: loop until it_cur equals it_end
    while (it_cur != it_end)
    {
        cout << *it_cur << " " ;
        
        // TODO: increment the it_cur iterator
        ++it_cur;
    }
    cout << endl;
}

//-------------------------------------------------------------------------
// mergeSort
//
//Algorithm mergeSort(S, C)
//	Input sequence S, comparator C 
//	Output sequence S sorted
//	according to C
//if S.size() > 1 {
//	(S1, S2) := partition(S, S.size()/2) 
//	S1 := mergeSort(S1, C)
//	S2 := mergeSort(S2, C)
//	S := merge(S1, S2)
//} 
//return(S)
//
//
// TODO: implement this function
//
//-------------------------------------------------------------------------
void mergeSortInPlace(myVectorType& theSeq, int startIdx, int endIdx)
{
   // TODO:
   // Do some simple error checks
   if (endIdx - startIdx <= 0 ) {  return;  }  // 1 or fewer to sort so done
   
   // Partion into two halves -> [startIdx to midIdx-1] and [midIdx to endIdx]
   int midIdx = startIdx + ( (endIdx - startIdx + 1) / 2 );
   
   mergeSortInPlace(theSeq, startIdx, midIdx-1);
   mergeSortInPlace(theSeq, midIdx, endIdx);
   
   merge(theSeq, startIdx, midIdx, endIdx);

   printContents( theSeq, false );
}

//-------------------------------------------------------------------------
// merge
//Algorithm merge(A, B)
//	Input sequences A and B with n/2 elements each 
//	Output sorted sequence of A and B
//
//S <-- empty sequence
//while not A.isEmpty()  AND not B.isEmpty()
//	if A.first() < B.first()
//		S.insertLast(A.removeFirst())
//	else
//		S.insertLast(B.removeFirst())
//while not A.isEmpty()		
//      S.insertLast(A.removeFirst())
//while not B.isEmpty()		
//     S.insertLast(B.removeFirst())
//return S
//
//-------------------------------------------------------------------------
void merge(myVectorType& theSeq, int startIdx, int midIdx, int endIdx)
{
	myVectorType tempV;
	int leftIdx = startIdx;
	int rightIdx = midIdx;
	
	while ((leftIdx < midIdx) && (rightIdx <= endIdx))
	{
		if (theSeq[leftIdx] <= theSeq[rightIdx])
		{
			tempV.push_back(theSeq[leftIdx]);
			leftIdx++;
		}
		else
		{
			tempV.push_back(theSeq[rightIdx]);
			rightIdx++;
		}
	} // end while both seqs have stuff in them
	
	// at this point at least 1 of the seqs is empty
	// So only one of the below 2 whiles should execute
	while (leftIdx < midIdx)
	{
		tempV.push_back(theSeq[leftIdx]);
		leftIdx++;
	}
	while (rightIdx <= endIdx)
	{
		tempV.push_back(theSeq[rightIdx]);
		rightIdx++;
	}
	
	// error check
	if (tempV.size() != endIdx - startIdx + 1)
	{
		cout << "merge ERROR --- size failed check\n";
	}
	
	// instead of returning resulting sequence 
	// we copy over the elements in the original vector
	for (int i = startIdx; i <= endIdx; i++)
	{
		theSeq[i] = tempV[i - startIdx];
	}
}


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
// end file