#include <stdio.h>
#include <iostream>
using namespace std;

class user {
private:
    string name;
    long int contact;
    float bill_amt;

public:
    user() {
        name = "";
        contact = 0;
        bill_amt = 0;
    }

    friend class record;
};

class record {
public:
    int n;
    user arr[100];
    
void accept() {
    cout << "Enter the number of users: " << endl;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Enter name of the user: ";
        cin >> arr[i].name;
        cout << "Enter mobile number of the user: ";
        cin >> arr[i].contact;
        cout << "Enter bill amount of the user: ";
        cin >> arr[i].bill_amt;
    }
}

void display() {
    for (int i = 0; i < n; i++) {
    	cout<<"NAME \t\t\tCONTACT NO \t\t\t BILL AMOUNT"<<endl;
        cout << arr[i].name << "\t\t\t ";
        cout << arr[i].contact << "\t\t\t ";
        cout << arr[i].bill_amt << endl;
    }
}

void linearSearch() {
    long int data;
    int flag = 0;
    cout << "Enter the mobile number to search using Linear Search: ";
    cin >> data;
    for (int i = 0; i < n; i++) {
        if (data == arr[i].contact) {
            cout << "Found user: " << arr[i].name << " with bill amount: " << arr[i].bill_amt << endl;
            flag = 1;
            return;
        }
    }

    if(flag = 0) cout << "User not found!" << endl;

    cout << "Mobile number not found!" << endl;
}

void binarySearch_recursive(int l, int r, long int data) {
    if (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid].contact == data) {
            cout << "Found user: " << arr[mid].name << " with bill amount: " << arr[mid].bill_amt << endl;
            return;
        } else if (arr[mid].contact < data) {
            binarySearch_recursive(mid + 1, r, data);
        } else {
            binarySearch_recursive(l, mid - 1, data);
        }
    } else {
        cout << "Mobile number not found!" << endl;
    }
}

void binarySearch() {
    long int data;
    int l = 0, r = n - 1;
    cout << "Enter the mobile number to search using Binary Search: ";
    cin >> data;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid].contact == data) {
            cout << "Found user: " << arr[mid].name << " with bill amount: " << arr[mid].bill_amt << endl;
            return;
        } else if (arr[mid].contact < data) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << "Mobile number not found!" << endl;
}

void heapify(int n, int i) {
    int high = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l].bill_amt > arr[high].bill_amt)
        high = l;

    if (r < n && arr[r].bill_amt > arr[high].bill_amt)
        high = r;

    if (high != i) {
        swap(arr[i], arr[high]);
        heapify(n, high);
    }
}

void heapSort() {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(i, 0);
    }
}

int partition(int l, int r) {
    long int pivot = arr[l].contact;
    int i = l;
    int j = r;

    while (i < j) {
        while (arr[i].contact <= pivot) i++;
        while (arr[j].contact > pivot) j--;

        if (i < j) {
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

void quickSort(int l, int r) {
    if (l < r) {
        int pI = partition(l, r);
        quickSort(l, pI - 1);
        quickSort(pI + 1, r);
    }
}
};


int main() {
    record r1;
    int choice;

    while (true) {
        cout<<"\t MENU \t"<<endl;
	cout<<"\t 1: Accept Data \t"<<endl;
	cout<<"\t 2: Display Data \t"<<endl;
	cout<<"\t 3: Heap sort According to phone number  \t"<<endl;
	cout<<"\t 4: Quick sort According to phone number \t"<<endl;
	cout<<"\t 5: Binary Search According to phone number  \t"<<endl;
	cout<<"\t 6: EXIT \t"<<endl;
	cout<<"Enter Your choice"<<endl;
	cin>>choice;
        switch (choice) {
            case 1:
                cout << "Accept User Records:\n";
		r1.accept();
                break;
            case 2:
		cout << "Displaying all records:\n";               
                r1.display();
                break;
            case 3:
                r1.heapSort();
                cout << "Data sorted by bill amount using Heap Sort:\n";
                break;
            case 4:
            	r1.quickSort(0, r1.n - 1);
                cout << "Data sorted by contact number using Quick Sort:\n";
                r1.display();    
                break;
            case 5:r1.binarySearch();
             
            case 6:
 		 cout << "Exiting program. Goodbye!\n";
                return 0;
                
                break;
           default:
                cout << "Invalid choice! Please try again.\n";
        }
    }
    return 0;
}