// sort.cpp (Sorting by Successive Selection)

#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <random>
#include <iomanip>

template <class Iterator, class Compare>
void sort1(Iterator first, Iterator last, const Compare & comp)
// Iterator must have operators *, ++, and !=
{
    for (Iterator current = first; current != last; ++current) {
        Iterator cur_min = current;
        for (Iterator i = current; i != last; ++i) {
            if (comp(*i, *cur_min)) {
                cur_min = i;
            }
        }
        std::swap(*cur_min, *current);
    }
}


struct Date {
    Date()                                     // random constructor
    {
        time_t rdate = distribution(generator);
        _time = *localtime(&rdate);
    }

    Date(time_t date): _time (*localtime(&date)) {}     // constructor

    static std::uniform_int_distribution<time_t> distribution;
    static std::default_random_engine generator;
    static time_t today;
    tm _time;
};

time_t Date::today = time(nullptr);
std::uniform_int_distribution<time_t> Date::distribution (1, Date::today);
std::default_random_engine Date::generator (Date::today);


std::ostream & operator<<(std::ostream & os, const Date & date)
{
    static const std::string monthname[12] =  {"Jan", "Feb", "Mar",
        "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
    os << monthname[date._time.tm_mon] << " " << std::setw(2)
       << date._time.tm_mday << ", " << date._time.tm_year + 1900;
    return os;
}


class BirthdayComparison {
public:
    BirthdayComparison(const Date & today) : _today(today) {}
    bool operator()(const Date & b1, const Date & b2) const
    {
        return day_num (b1) < day_num (b2);
    }
private:
    int day_num(const Date & date) const
    {
        return (32 * (12 + date._time.tm_mon - _today._time.tm_mon) +
                date._time.tm_mday  - _today._time.tm_mday) % (12*32);
    }
    Date const & _today;
};


int main()
{
    std::cout << "Today is " << Date(Date::today) << ".\n"
              << "How many random birthdays do you want to sort? ";
    int n;
    std::cin >> n;
    std::vector<Date> dates(n);
    std::cout << "Here are " << n << " random dates:\n";
    for (auto d: dates) {
        std::cout << d << "    ";
    }
    std::cout << "\n\n";

    BirthdayComparison comparison((Date(Date::today)));
    std::cout << "Sorting..." << std::endl;
    clock_t timer = clock();
    sort1(dates.begin(), dates.end(), comparison);
    timer = clock() - timer;

    std::cout << "The upcoming birthdays are, starting today:\n";
    for (auto d: dates) {
        std::cout << d << "    ";
    }
    std::cout << "\n\n" << "Sorting took "
              << static_cast<double>(timer)/CLOCKS_PER_SEC << " seconds.\n";
}