/*
** The C++ <algorithm> has method named: next_permutation(), 
**		it is nice to validate our program with this method
**
** To solve this problem, we just need 3 steps:
**		1. search from bottom to top, find the first place where the element(say A) is not decreasely,
**		2. sort the elements after A increasely,
**		3. replace the A with element which is just larger than A in the array after A.
**
*/
#include <vector>
using namespace std;

void Swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

//find first element that is larger than target in array which range is [low, high]
int BSearchUpper(vector<int>& array, int low, int high, int target)
{
    if (low > high || array[high] < target) return -1;

    int mid = (low + high) / 2;
    while(low < high)
    {
        if (array[mid] <= target)
            low = mid + 1;
        else
            high = mid;
		mid = (low + high) / 2;
    }

    return mid;
}

//reverse the array elements range in [low, high]
void ReverseArray(vector<int>& array, int low, int high)
{
    while(low < high)
    {
        //swap two elements
        Swap(array[low], array[high]);
        ++ low;
        -- high; 
    }
}

void NextPermutation(vector<int> &array) 
{
    int length = array.size()-1;
    int i = array.size();
    while(--i > 0 && array[i-1] >= array [i]);

    ReverseArray(array,i,length);

    //if array is last permutation, we just reverse array,
    //otherwise, swap the elements with the one that is just larger than it
    if (i >= 0)
    {
        int upper = BSearchUpper(array,i,length, array[i-1]);
        Swap(array[i-1], array[upper]);
    }
}


#include <iostream>

using namespace std;
template<typename T>
void PrintVector(T v, size_t size)
{
    for (size_t i = 0; i < size; ++i)
        cout << v[i]<<", ";

    cout << endl;
}

int main(int argc, char** argv)
{
    vector<int> v;
    v.push_back(3);
    v.push_back(4);
    v.push_back(1);
    v.push_back(2);

    
	PrintVector(v,4);
    NextPermutation(v);
    PrintVector(v,4);
	
    return 0;
}