You have been asked to develop software to help with a competition. Here are the functionalities your software must support:

It should keep track of each participant's name and score.

Since you will not know how many people may participate in a competition, use a double-linked list to keep track of all participants.

Keep the list always sorted in non-increasing order. You can do that by inserting each element at the correct position in the link list after reading it from the file. If duplicate entries exist, only insert the first entry and reject the successive ones.

You may need to keep track of the linked list's head and tail.

After building the linked list, perform an indexing operation on the linked list. That is, declare an Node **arr, and have each pointer pointing to an element of the list. Write a function void build_index() in the class that:

• Creates an array of pointers using the Node **arr variable. The size of the array will be equal to the number of entries in the linked list.
• Then, make each pointer, denoted by arr[i], point to an element of the linked list.

After you build the linked list, you will display a menu with the following options:

1) BinarySearchWithRecursion: which takes a score as input and prints the name of a participant with that score. Implement BinarySearch with recursion and report the first participant the search algorithm encounters with that score. This participant may not be the first in the ordered linked list. Also, report the number of comparisons. Use the recursive algorithm for binary search.

2) HighestScore: Print the names of people with the highest score. Since there can be multiple people with the same score, print all their names.

3) LowestScore: Print the names of people with the lowest score. Since there can be multiple people with the same score, print all their names.

4) DisplayRankedList: Display the list in non-increasing order.

5) Quit

Use a class to contain the linked list. Each node of the linked list can be of structure type.

Declare appropriate Constructor and Destructor functions.

Declare appropriate setter and getter functions, if needed.

 - If no participant has that score, then print a message ```Could not find: Y Number of comparison: X```. Here, Y represents the target score and X represents the number of comparisons performed. - If the score exists, then print the name of the player your BinarySearch algorithm finds first and the number of comparisons. The output will look like this: ```Player Z with score: Y Number of comparison: X```. Here, Z is the player's name, Y is the target score, and X is the number of comparisons. - You may need to implement a string get_name(int index) getting function that takes the index as input, and returns the corresponding player's name as output. This index is the index into the arr array. You can use arr[index]->name to get the player's name. 

Ive already completed part of the code, but when an input such as

2

5

is entered, the output differs from what is expected.

Your output

Menu

1. Lookup by score

2. Display highest scorer

3. Display lowest scorer

4. Display ranked list

5. Quit

Highest score: 358

Santiago Ascacibar

Fisnik Asllani

Menu

1. Lookup by score

2. Display highest scorer

3. Display lowest scorer

4. Display ranked list

5. Quit

Expected output

Menu

1. Lookup by score

2. Display highest scorer

3. Display lowest scorer

4. Display ranked list

5. Quit

Enter your choice:

Fisnik Asllani 358

Santiago Ascacibar 358

Menu

1. Lookup by score

2. Display highest scorer

3. Display lowest scorer

4. Display ranked list

5. Quit

Enter your choice:

Here is my code:

#include #include #include

// Node structure struct Node { std::string name; double score; Node* next; Node* prev; };

// LinkedList class class LinkedList { private: Node* head; Node* tail; int size;

public: // Constructor LinkedList() : head(nullptr), tail(nullptr), size(0) {}

// Destructor ~LinkedList() { Node* current = head; Node* next; while (current != nullptr) { next = current->next; delete current; current = next; } }

// Getter functions Node* getHead() const { return head; } Node* getTail() const { return tail; } int getSize() const { return size; }

// Function to insert a participant into the linked list void insertParticipant(const std::string& name, double score) { // Check for duplicate entries if (!isDuplicate(name, score)) { Node* newNode = new Node{ name, score, nullptr, nullptr }; // Insert at the correct position to maintain non-increasing order insertSorted(newNode); size++; } }

// Function to check for duplicate entries bool isDuplicate(const std::string& name, double score) { Node* current = head; while (current != nullptr) { if (current->name == name && current->score == score) { return true; // Duplicate found } current = current->next; } return false; // No duplicate found }

// Function to insert a node at the correct position in the linked list void insertSorted(Node* newNode) { if (head == nullptr || head->score < newNode->score) { // Insert at the beginning newNode->next = head; newNode->prev = nullptr; if (head != nullptr) { head->prev = newNode; } head = newNode; if (tail == nullptr) { tail = newNode; } } else { // Traverse the list to find the correct position Node* current = head; while (current->next != nullptr && current->next->score >= newNode->score) { current = current->next; } // Insert the new node newNode->next = current->next; newNode->prev = current; if (current->next != nullptr) { current->next->prev = newNode; } current->next = newNode; if (newNode->next == nullptr) { tail = newNode; } } }

// Function to build the index array void buildIndex(Node**& arr) { arr = new Node*[size]; Node* current = head; for (int i = 0; i < size; i++) { arr[i] = current; current = current->next; } }

// Binary search with recursion void binarySearchWithRecursion(Node** arr, int low, int high, double target, int& comparisons) { if (low <= high) { int mid = low + (high - low) / 2; comparisons++; if (arr[mid]->score == target) { std::cout << "Player " << arr[mid]->name << " with score: " << target << " Number of comparisons: " << comparisons << std::endl; } else if (arr[mid]->score > target) { binarySearchWithRecursion(arr, mid + 1, high, target, comparisons); } else { binarySearchWithRecursion(arr, low, mid - 1, target, comparisons); } } else { std::cout << "Could not find: " << target << " Number of comparisons: " << comparisons << std::endl; } }

// Function to display the list in non-increasing order void displayRankedList() { Node* current = head; while (current != nullptr) { std::cout << current->name << ": " << current->score << std::endl; current = current->next; } }

// Function to display the highest score void displayHighestScore() { Node* current = head; double highestScore = head->score; std::cout << "Highest score: " << highestScore << std::endl; while (current != nullptr && current->score == highestScore) { std::cout << current->name << std::endl; current = current->next; } }

// Function to display the names of participants with the lowest score void displayLowestScore() { Node* current = head; double lowestScore = tail->score; std::cout << "Lowest scorers: " << std::endl; while (current != nullptr) { if (current->score == lowestScore) { std::cout << current->name << std::endl; } current = current->next; } } };

// Function to read data from the file and populate the linked list void loadDataFromFile(const std::string& filename, LinkedList& list) { std::ifstream file(filename); if (file.is_open()) { std::string line; while (std::getline(file, line)) { // Parse the line into name and score size_t commaPos = line.find(','); if (commaPos != std::string::npos) { std::string name = line.substr(0, commaPos); double score = std::stod(line.substr(commaPos + 1)); list.insertParticipant(name, score); } } file.close(); } else { std::cerr << "Unable to open file: " << filename << std::endl; } }

int main() { LinkedList participantList; loadDataFromFile("input.txt", participantList); Node** indexArray = nullptr; participantList.buildIndex(indexArray); int choice; do { std::cout << "Menu " << "1. Lookup by score " << "2. Display highest scorer " << "3. Display lowest scorer " << "4. Display ranked list " << "5. Quit "; std::cin >> choice; switch (choice) { case 1: { double targetScore; std::cout << "Enter the target score: "; std::cin >> targetScore; int comparisons = 0; participantList.binarySearchWithRecursion(indexArray, 0, participantList.getSize() - 1, targetScore, comparisons); break; } case 2: { participantList.displayHighestScore(); break; } case 3: { participantList.displayLowestScore(); break; } case 4: { participantList.displayRankedList(); break; } case 5: break; default: std::cout << "Invalid choice. Try again. "; } } while (choice != 5); // Cleanup delete[] indexArray; return 0; }