#include <algorithm>
#include <cassert>
#include <cmath>
#include <iterator>
#include <list>
#include <set>
#include <string>
#include <vector>

/* implement sort() here */

bool absolute_compare(int a, int b)
{
    return std::abs(a) < std::abs(b);
}

int main()
{
    // std::vector + default comparator
    {
        std::vector<int> prompt { 2, 1, 3 };
        std::vector<int> answer { 1, 2, 3 };

        sort(prompt);
        assert( prompt == answer );
    }

    // std::vector + greater comparator
    {
        std::vector<int> prompt { 2, 1, 3 };
        std::vector<int> answer { 3, 2, 1 };

        sort(prompt, std::greater<int>{});
        assert( prompt == answer );
    }

    // C-array + function comparator
    {
        int prompt[] { -3, 1, -2, 4 };
        int answer[] { 1, -2, -3, 4 };

        sort(prompt, absolute_compare);
        assert( prompt[0] == answer[0] );
        assert( prompt[1] == answer[1] );
        assert( prompt[2] == answer[2] );
        assert( prompt[3] == answer[3] );
    }

    // std::list + default comparator
    {
        std::list<std::string> prompt { "ef", "abcd", "ghi" };
        std::list<std::string> answer { "abcd", "ef", "ghi" };

        sort(prompt);
        assert( prompt == answer );
    }

    // std::list + length
    {
        std::list<std::string> prompt { "ef", "abcd", "ghi" };
        std::list<std::string> answer { "ef", "ghi", "abcd" };

        auto comp = [](std::string const& a, std::string const& b) 
                    { 
                        return a.size() < b.size(); 
                    };

        sort(prompt, comp);
        assert( prompt == answer );
    }

    // std::set + default comparator and then dummy comparator
    {
        std::set<double> prompt { 3.5, 1.3, 7.9, 5.7 };
        std::set<double> answer { 1.3, 3.5, 5.7, 7.9 };

        sort(prompt);
        assert( prompt == answer );

        sort(prompt, [](double const&, double const&) { return true; });
        assert( prompt == answer );
    }
}