Iurii Tatishchev
701d84242d
Now that you have a working implementation of the Heap class, you will convert it to a template. In this assignment we will create and process a heap of Customer objects. You are encouraged to reuse as much code as possible from previous assignments/labs. The assignment consists of the following classes/files: - Customer.cpp (incomplete) - Customer.h (incomplete) - Heap.h (template, incomplete) - main.cpp (incomplete) Project: An airline company uses the formula shown below to determine the priority of the passengers on the waiting list for overbooked flights. Priority number = A / 1000 + B – C Where - A is the customer’s total mileage in the past year - B is the customer’s number of years in the flier program - C is the sequence number representing the customer’s arrival position when the flight was booked (the first customer’s sequence number is 1, second in the file is 2, and so on). Two or more customers could have the same priority number. For instance, Robert Hill and Tom Martin have the same priority number: Robert Hill’s priority number: 53000 / 1000 + 5 – 1 = 57 Tom Martin’s priority number: 56000/1000 + 5 – 4 = 57 Customers with the same priority number must be served on a first come first serve basis, therefore build the heap based on a unique serial number determined using the following formula: serial number = priority * 100 + (100 – C) In the above example: Robert Hill’s serial number is: 57 * 100 + (100 – 1) = 5799 Tom Martin’s serial number is: 57 * 100 + (100 – 4) = 5796 Given a file with overbooked customers, write a program that reads the file and determines each customer’s priority number, serial number, and prints a list of waiting customers in priority sequence, including the total number of customers served/rejected. There are two types of lines in the input file: line that begins with 'A' or 'S': - the letter 'A' represents the arrival of a new customer and it is followed by: - the number of years in the frequent flier program, - total mileage in the past year, and the - name of the customer (see below). A 5 53000 Robert Hill // insert into the heap A 3 89000 Amanda Trapp // insert into the heap A 3 90000 Jonathan Nguyen // insert into the heap S // delete from the heap and print A 5 56000 Tom Martin // insert into the heap The letter 'S' stands for "Serve" and indicates that the next customer from the waiting list will be served (in priority sequence). Finally, display the overbooked customers that did not get a plain ticket. For each overbooked customer display the number of years in the frequent flier program, total mileage in the past year, the serial number within (), and the name of the customer within [], as shown in the following example. Example: Input file name: 3 89000 (9098) [Amanda Trapp] Served overbooked customers: 1 3 90000 (9097) [Jonathan Nguyen] 5 53000 (5799) [Robert Hill] 5 56000 (5796) [Tom Martin] Rejected overbooked customers: 3
136 lines
3.6 KiB
C++
136 lines
3.6 KiB
C++
/* *~*~*
|
|
Specification file for the Heap class: min- or max-heap of integers
|
|
Written By: Iurii Tatishchev
|
|
Changed by: Iurii Tatishchev
|
|
IDE: CLion
|
|
*~**/
|
|
|
|
#ifndef HEAP_H_
|
|
#define HEAP_H_
|
|
|
|
template<typename T>
|
|
class Heap {
|
|
private:
|
|
T *heapAry;
|
|
int heapSize;
|
|
int count;
|
|
|
|
void _reHeapUp(int lastndx, int (compareFunc)(const T&, const T&));
|
|
|
|
void _reHeapDown(int rootndx, int (compareFunc)(const T&, const T&));
|
|
|
|
int _findParent(int index) { return (index <= 0) ? (-1) : (index - 1) / 2; }
|
|
|
|
int _findLeftChild(int index) { return (2 * index + 1 >= count) ? (-1) : (2 * index + 1); }
|
|
|
|
int _findRightChild(int index) { return (2 * index + 2 >= count) ? (-1) : (2 * index + 2); }
|
|
|
|
public:
|
|
Heap() {
|
|
count = 0;
|
|
heapSize = 128;
|
|
heapAry = new T[heapSize];
|
|
}
|
|
|
|
Heap(int n) {
|
|
count = 0;
|
|
heapSize = n;
|
|
heapAry = static_cast<int *>(new T[heapSize]);
|
|
}
|
|
|
|
~Heap() { delete[] heapAry; }
|
|
|
|
int getCount() const { return count; }
|
|
|
|
int getSize() const { return heapSize; }
|
|
|
|
bool isEmpty() const { return count == 0; }
|
|
|
|
bool isFull() const { return count == heapSize; }
|
|
|
|
bool insertHeap(T &itemIn, int (compareFunc)(const T&, const T&));
|
|
|
|
bool deleteHeap(T &itemOut, int (compareFunc)(const T&, const T&));
|
|
|
|
};
|
|
|
|
template <typename T>
|
|
void Heap<T>::_reHeapUp(int lastndx, int (compareFunc)(const T&, const T&)) {
|
|
|
|
// base case, newElement is heap's root
|
|
if (lastndx == 0) return;
|
|
|
|
int parentIndex = _findParent(lastndx);
|
|
// base case, newElement satisfies heap property
|
|
// min heap - child not less than parent
|
|
// max heap - child not greater than parent
|
|
if (compareFunc(heapAry[lastndx], heapAry[parentIndex]) != -1) return;
|
|
|
|
// swap and continue recursing
|
|
std::swap(heapAry[lastndx], heapAry[parentIndex]);
|
|
_reHeapUp(parentIndex, compareFunc);
|
|
}
|
|
|
|
/* *~*~*
|
|
The private member function _reHeapDown rearranges the heap after delete by moving the
|
|
data in the root down to the correct location in the heap
|
|
*~**/
|
|
template <typename T>
|
|
void Heap<T>::_reHeapDown(int rootdex, int (compareFunc)(const T&, const T&)) {
|
|
int maxChildIndex = -1;
|
|
|
|
int left = _findLeftChild(rootdex);
|
|
int right = _findRightChild(rootdex);
|
|
|
|
// if there is a left child
|
|
if (left != -1) {
|
|
// if there is a right child that is
|
|
// min heap - less than the left child
|
|
// max heap - greater than the left child
|
|
if (right != -1 && compareFunc(heapAry[right], heapAry[left]) == -1) maxChildIndex = right;
|
|
else maxChildIndex = left;
|
|
}
|
|
|
|
// base case, heap property satisfied
|
|
// min heap - children greater than parent
|
|
// max heap - children less than parent
|
|
if (maxChildIndex == -1 || compareFunc(heapAry[rootdex], heapAry[maxChildIndex]) == -1) return;
|
|
|
|
// swap and continue recursing
|
|
std::swap(heapAry[rootdex], heapAry[maxChildIndex]);
|
|
_reHeapDown(maxChildIndex, compareFunc);
|
|
}
|
|
|
|
/* *~*~*
|
|
The public member function insertHeap inserts a new item into a heap.
|
|
It calls _reheapUp.
|
|
*~**/
|
|
template <typename T>
|
|
bool Heap<T>::insertHeap(T& newItem, int (compareFunc)(const T&, const T&)) {
|
|
if (isFull()) return false;
|
|
|
|
heapAry[count] = newItem;
|
|
_reHeapUp(count, compareFunc);
|
|
count++;
|
|
|
|
return true;
|
|
}
|
|
|
|
/* *~*~*
|
|
The public member function deleteHeap deletes the root of the heap and
|
|
passes back the root's data. It calls _reheapDown.
|
|
*~**/
|
|
template <typename T>
|
|
bool Heap<T>::deleteHeap(T& returnItem, int (compareFunc)(const T&, const T&)) {
|
|
if (isEmpty()) return false;
|
|
|
|
returnItem = heapAry[0];
|
|
heapAry[0] = heapAry[count - 1];
|
|
count--;
|
|
_reHeapDown(0, compareFunc);
|
|
|
|
return true;
|
|
}
|
|
|
|
#endif
|