HW 7

#include <iostream>
#include <string>
#include <vector>

class spell;

template<typename T>
void heapSort(std::vector<T>& v);
template<typename T>
void heapify(std::vector<T>& v, const int& end);
template<typename T>
void siftDown(std::vector<T>& v, const int& start, const int& end);
template<typename T>
void heapSortComparator(std::vector<T>& v);
template<typename T>
void heapifyComparator(std::vector<T>& v, const int& end);
template<typename T>
void siftDownComparator(std::vector<T>& v, const int& start, const int& end);
bool lessSpell(const spell& a, const spell& b);

class spell
{
    std::string name;
    int power, cost;
public:
    spell(const std::string& n, const int& p, const int& c) : name(n), power(p), cost(c) {}
    bool operator<(const spell& s)
    {
        return (this->cost < s.cost);
    }
    bool operator<=(const spell& s)
    {
        return (this->cost <= s.cost);
    }
    bool operator>(const spell& s)
    {
        return (this->cost > s.cost);
    }
    bool operator>=(const spell& s)
    {
        return (this->cost >= s.cost);
    }
    const std::string& getName() const
    {
        return this->name;
    }
    const int& getPower() const
    {
        return this->power;
    }
    const int& getCost() const
    {
        return this->cost;
    }
};

int main()
{
    std::vector<spell> v1, v2;
    for (int i = 0; i < 10; i++)
    {
        std::string name;
        int power, cost;
        std::cout << i+1 << ". Enter spell name: ";
        std::getline(std::cin >> std::ws, name);
        std::cout << "Enter spell power: ";
        std::cin >> power;
        std::cout << "Enter spell mana cost: ";
        std::cin >> cost;
        spell o(name, power, cost);
        v1.push_back(o);
    }
    v2 = v1;
    heapSort(v1);
    heapSortComparator(v2);
    std::cout << "Default heapsort:" << std::endl;
    for (auto i : v1)
    {
        std::cout << "Spell <" << i.getName() << "> with power " << i.getPower() << " and mana cost " << i.getCost() << std::endl;
    }
    std::cout << "Comparator heapsort:" << std::endl;
    for (auto i : v2)
    {
        std::cout << "Spell <" << i.getName() << "> with power " << i.getPower() << " and mana cost " << i.getCost() << std::endl;
    }
    return 0;
}

template<typename T>
void heapSort(std::vector<T>& v)
{
    int end = v.size()-1;
    heapify(v, end);
    while (end >= 0)
    {
        std::swap(v[0], v[end]);
        end--;
        siftDown(v, 0, end);
    }
}

template<typename T>
void heapify(std::vector<T>& v, const int& end)
{
    for (int i = end; i >= 0; i--)
    {
        siftDown(v, i, end);
    }
}

template<typename T>
void siftDown(std::vector<T>& v, const int& start, const int& end)
{
    int parent = start, child = parent * 2 + 1, swap;
    while(child <= end)
    {
        swap = parent;
        if (v[child] > v[parent])
        {
            swap = child;
        }
        if ((child + 1) <= end && v[child + 1] > v[swap])
        {
            swap = child + 1;
        }
        if (swap == parent)
            break;
        std::swap(v[parent], v[swap]);
        parent = swap;
        child = parent * 2 + 1;
    }
}

template<typename T>
void heapSortComparator(std::vector<T>& v)
{
    int end = v.size() - 1;
    heapifyComparator(v, end);
    while (end >= 0)
    {
        std::swap(v[0], v[end]);
        end--;
        siftDownComparator(v, 0, end);
    }
}

template<typename T>
void heapifyComparator(std::vector<T>& v, const int& end)
{
    for (int i = end; i >= 0; i--)
    {
        siftDownComparator(v, i, end);
    }
}

template<typename T>
void siftDownComparator(std::vector<T>& v, const int& start, const int& end)
{
    int parent = start, child = parent * 2 + 1, swap;
    while (child <= end)
    {
        swap = parent;
        if (lessSpell(v[parent], v[child]))
        {
            swap = child;
        }
        if ((child + 1) <= end && lessSpell(v[swap], v[child + 1]))
        {
            swap = child + 1;
        }
        if (swap == parent)
            break;
        std::swap(v[parent], v[swap]);
        parent = swap;
        child = parent * 2 + 1;
    }
}

bool lessSpell(const spell& a, const spell& b)
{
    if (a.getPower() < b.getPower())
        return true;
    else if (a.getPower() == b.getPower())
    {
        return (a.getCost() > b.getCost());
    }
    else
        return false;
}