/*
 * Copyright (c) 24 ottobre 2011, Luca Risolia
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY <copyright holder> ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <iterator>

template <class RandomAccessIterator, class Compare>
void qsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
    if (last - first > 1) {
        RandomAccessIterator piv = first, l = first + 1, r = last;
        while (l < r) {
            if (!comp(*piv, *l))
                l++;
            else
                std::swap(*l, *--r);
        }
        std::swap(*--l, *first);
        qsort(first, l, comp);
        qsort(r, last, comp);
    }
}

struct Record {
    int count, price;

    Record(int c, int p) : count(c), price(p) { }

    bool operator<(const Record & a) const {
        return count < a.count || (count == a.count && price < a.price);
    }

    bool operator==(const Record & a) const {
        return count == a.count && price == a.price;
    }

    bool operator>(const Record & a) const {
        return count > a.count || (count == a.count && price > a.price);
    }

    bool operator>=(const Record & a) const {
        return !(*this < a);
    }

    bool operator<=(const Record & a) const {
        return !(*this > a);
    }

    bool operator!=(const Record & a) const {
        return !(*this != a);
    }
};

std::ostream& operator<<(std::ostream& o, const Record& r) {
    o << "Count: " << r.count << " Price: " << r.price << '\n';
    return o;
}

int main(int argc, char** argv) {
    std::vector<Record> v;
    v.push_back(Record(5, 1000));
    v.push_back(Record(4, 2000));
    v.push_back(Record(3, 5000));
    v.push_back(Record(4, 2000));
    qsort(v.begin(), v.end(), std::greater<Record > ());
    std::ostream_iterator<Record> o(std::cout);
    std::copy(v.begin(), v.end(), o);
    return 0;
}