// Copyright Evgeny Panasyuk 2013.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://w...content-available-to-author-only...t.org/LICENSE_1_0.txt)

#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <iostream>
#include <cassert>
#include <cstddef>
#include <string>
#include <vector>

using namespace std;

template<typename Iterator>
using ValueType = typename iterator_traits<Iterator>::value_type;

template<typename I, typename P = less<ValueType<I>>>
/*
requires
(
    ForwardIterator(I) && Mutable(I) &&
    StrictWeakOrdering(P) && Domain(P) == ValueType(I)
)
*/
void quick_sort(I first, I last, P p = P())
{
    while(first != last)
    {
        // naive version
        auto pivot = *first;
        auto first_not_less = partition(first, last, bind2nd(p, pivot));
        quick_sort(first, first_not_less, p);
        first = partition(first_not_less, last, not1(bind1st(p, pivot)));
    }
}

/************************************************************************/

// Generates sorted sequences of given size isomorphic under ordering relation
//    to all other sorted sequences of that size.
// Note, for integer sortings, distance between numbers would also make difference,
//   not just "order".
template<typename I, typename T, typename F>
/*
requires
(
    ForwardIterator(I) && Mutable(I) &&
    Integer(T) && ValueType(I) == T && 
    NullaryFunction(F)
)
*/
void generate_sorted_sequences(I first, I last, T x, F yield)
{
    /*
        For n=3 generates:
        0 1 2
        0 1 1
        0 0 1
        0 0 0
    */
    if(first == last) yield();
    else do
    {
        *first = x;
        ++first;
        generate_sorted_sequences(first, last, x + 1, yield);
    } while(first != last);
}


template<typename I1, typename I2, typename N>
/*
requires
(
    ForwardIterator(I1) && InputIterator(I2) &&
    ValueType(I1) == ValueType(I2) &&
    EqualityComparable( ValueType(I1) ) &&
    Integer(N)
)
*/
void require_equal(I1 first1, I1 last1, I2 first2, N n)
{
    if(equal(first1, last1, first2)) return;

    cout << "sequence #" << n << ", postcondition does not hold: ";
    copy(first1, last1, ostream_iterator<int>(cout, " "));
    cout << endl;
    throw logic_error("fix the code");
}

template<typename T, typename F>
/*
    Regular(T) && SortFunction(F)
*/
void test_sort(unsigned N, F sort)
{
    vector<T> v(N), permutation, tmp;
    size_t total = 0;
    for(auto first=begin(v), last=first; last!=end(v); ++last)
    {
        generate_sorted_sequences(first, last, T{}, [&]
        {
            assert(is_sorted(first, last));
            permutation.assign(first, last);
            do
            {
                tmp = permutation;
                sort(begin(tmp), end(tmp));
                require_equal(begin(tmp), end(tmp), first, total);
                ++total;
            } while(next_permutation(begin(permutation), end(permutation)));
        });
        cout << "tested " << total << " sequences" << endl;
    }
}

/************************************************************************/
struct QuickSort
{
    const string name = "Quicksort";
    template<typename I>
    void operator()(I first, I last) const
    {
        quick_sort(first, last);
    }
};
struct StdSort
{
    const string name = "std::sort";
    template<typename I>
    void operator()(I first, I last) const
    {
        sort(first, last);
    }
};
struct StdStableSort
{
    const string name = "std::stable_sort";
    template<typename I>
    void operator()(I first, I last) const
    {
        stable_sort(first, last);
    }
};
struct StdParialSort
{
    const string name = "std::partial_sort";
    template<typename I>
    void operator()(I first, I last) const
    {
        partial_sort(first, last, last);
    }
};

/************************************************************************/

template<typename SortFunction>
void test()
{
    SortFunction f;
    cout << "Testing " << f.name << endl;
    test_sort<int>(10, f);
    cout << string(32, '_') << endl;
}

template<typename SortFunction, typename Head, typename ...Tail>
void test()
{
    test<SortFunction>();
    test<Head, Tail...>();
}

int main()
{
    test<QuickSort, StdSort, StdStableSort, StdParialSort>();
}