#include <vector>
#include<iostream>

using namespace std;


class Bid
{
public:
    string _name;
    int _bet;
    Bid(int bet = 0, string _name = "noname") {
        _bet = bet;
    }
};

void BuildHeap(vector <Bid>& A);
void Heapify(vector <Bid>& A, int i);
void Insert(vector <Bid>& A, Bid newbid);
void PrintHigestBid(vector <Bid>& A);
void RadixSort(vector <Bid>& A);


void main() {
    vector <Bid> A;
    Bid a(78);
    Bid b(25);
    Bid c(53);
    Bid d(59);
    Bid e(46);
    Bid f(37);
    Bid g(29);
    Bid h(17);
    Bid i(41);
    Bid j(21);
    Bid k(30);
    Bid l(8);
    A.push_back(a);
    A.push_back(b);
    A.push_back(c);
    A.push_back(d);
    A.push_back(e);
    A.push_back(f);
    A.push_back(g);
    A.push_back(h);
    A.push_back(i);
    A.push_back(j);
    A.push_back(k);
    A.push_back(l);
    for (int i = 0; i < A.size(); i++)
    {
        cout << A[i]._bet << " ";
    }
    BuildHeap(A);
    cout << endl;
    for (int i = 0; i < A.size(); i++)
    {
        cout << A[i]._bet << " ";
    }
    Bid m(38);
    Insert(A, m);
    cout << endl;
    for (int i = 0; i < A.size(); i++)
    {
        cout << A[i]._bet << " ";
    }
    cout << endl;

    cout << "Add evar 11 " << endl;
    Bid n(30);
    Insert(A, n);
    cout << endl;
    for (int i = 0; i < A.size(); i++)
    {
        cout << A[i]._bet << " ";
    }
    cout << endl;

    PrintHigestBid(A);

    system("pause");
}


void BuildHeap(vector <Bid>& A)
{ // מקבלת מערך מסוג A
    int heapsize = A.size();
    for (int i = (heapsize / 2) - 1; i >= 0; i--)
    {
        Heapify(A, i);
    }
}

void Heapify(vector <Bid>& A, int i)
{
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int largest;
    // בודק אם הבן שמאלי גדול מהאבא
    if (l < A.size() && A[l]._bet >  A[i]._bet)
    {
        largest = l;
    }
    else {
        largest = i;
    }
    // בודק אם הבן הימני גדול מהאבא
    if (r < A.size() && A[r]._bet > A[largest]._bet)
    {
        largest = r;
    }
    // אם הגודל הוא אחד מהילדים אז תחליף עם האבא
    if (largest != i)
    {
        Bid temp(4);
        temp._bet = A[i]._bet;
        temp._name = A[i]._name;
        A[i]._bet = A[largest]._bet;
        A[i]._name = A[largest]._name;
        A[largest]._bet = temp._bet;
        A[largest]._name = temp._name;
        Heapify(A, largest);
    }
}

void Insert(vector <Bid>& A, Bid newbid)
{
    int asize = A.size();
    int fatherloc;
    A.push_back(newbid);
    if ((asize - 1) % 2 == 0) // אם ה
    {
        // אז הוא בן שמאלי
        fatherloc = (asize - 1) / 2; //מיקום של האבא
    }
    else {
        // אז הוא בן ימני
        fatherloc = (asize - 2) / 2; //מיקום של האבא
    }
    Heapify(A, fatherloc);
}


void PrintHigestBid(vector <Bid>& A)
{
    if (A[0]._bet != 0)
    {
        cout << "The higest bid for now is: " << endl << A[0]._bet;
        cout << endl << "and it's go for: " << A[0]._name << endl;
    }
    else {
        cout << "There is no bid at this moment" << endl;
    }
}

void RadixSort(vector <Bid>& A)
{
    // the "length" of 0 is 1:
    int len = 1;
    // and for numbers greater than 0:
    if (A[0]._bet > 0) {
        // we count how many times it can be divided by 10:
        // (how many times we can cut off the last digit until we end up with 0)
        for (len = 0; A[0]._bet > 0; len++) {
            A[0]._bet = (A[0]._bet) / 10;
        }
    }
    //
    //נבצע RADIXSORT
    int d = len; // נרוץ בלולאה על המספר הכי גבוה ונשמור במשתנה אינטי את מספר הספרות שלו
    // ניצור מערך בי והוא יהיה המערך
    // A
    // רק ממויין

    int* B;
    B = new int[A.size()]; //לא לשכוח לעשות Delete

    // בגודל A.size
    //ונשלח אותו לקאונטינ סורט
    for (int i = 1; i < d; i++)
    {
        CountingSort
        //  use Counting - Sort to sort A on digit i
    }

}

void CountingSort(vector <Bid>& A, int& B) //a,b,k - K זה התחום
{
    int* C;
    C = new int[A[0]._bet+1]; // Create C arr in size K + 1
    for (int i = 0; i < A[0]._bet; i++) // Inisilazie arr C to Zero
            {
                C[i] = 0;
            }
        //מכניס איבר במערך C
    // במיקום מסויים לפי איבר A
    for (int j = 0; j < A.size(); j++) //Check how much the number show in A arr and put it in the number position in C arr
    {
        C[A[j]._bet] = C[A[j]._bet] + 1;
    }
    for (int i = 1; 1 < A[0]._bet; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (int i = A.size(); i > 1; i--)
    {
        B[C[A[i]._bet]] = A[i]._bet;
        C[A[i]._bet]] = C[A[i]._bet] - 1;
    }




}