The Horsey Parade You are in charge of The Parade of Horses, the premier horsey parade East of the Rockies. The parade will take place through downtown Dallasville promptly at 10am next Saturday morning. You have sent out a call to hooves, requesting that the cloppiest residents of Dallasville arrive just before the parade for final preparations. You plan on arranging the horses in a single file line, by weight, from smallest to largest, with the intention of the mighty Peruna leading the way (rumor has it that Peruna will be wearing his favorite sheepskin coat, which he acquired last year during the incident at Fordhamsville). Because you will not have much time between the participants arriving and the start of the parade, you plan to pre-arrange the horses as they arrive. You estimate that the average horse will be 500kg in size. For each horse that arrives, if they are less than (or equal to 500kg), then you will put them at the front of the line. If they are greater than 500kg, then you will put them at the end of the line. Once all the horses have arrived, you will perform a sort to put them in the correct parade order, from smallest to largest. Implementation Details To complete this assignment, you will implement the interfaces that are found in at the bottom of this document. You must implement your program using link-lists similar to those as discussed in class. You may NOT use vectors or any of the other STL container classes. Your program will be driven by user input. Phase 1 The Arrival You will ask the user if they want to add a new horse to the parade. You will add the horse to the end of the parade if it is greater than 500kg. You will add the horse to the beginning of the parade otherwise. You will also give the user the option of removing a horse from the beginning or the end of the parade. What can I say? Some horses are too rowdy for parades.... Phase 2 The Parade Once all the horses have arrived, the horses will be sorted into their final configuration. You may use whatever sorting methodology you prefer, but you MAY NOT use the algorithms library from the STL. Phase 3 After the Parade You MUST free any memory that you have dynamically allocated when you perform any pop or clear operations. Sample Output Welcome to the Horsey Parade! The horses are arriving!! What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 500 The horse is less than or equal to 500 kg. Adding to the beginning of the parade. Current parade arrangement: List: 500 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 25 The horse is less than or equal to 500 kg. Adding to the beginning of the parade. Current parade arrangement: List: 25 500 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 65 The horse is less than or equal to 500 kg. Adding to the beginning of the parade. Current parade arrangement: List: 65 25 500 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 5000 The horse is greater than 500 kg. Adding to the end of the parade. Current parade arrangement: List: 65 25 500 5000 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 950 The horse is greater than 500 kg. Adding to the end of the parade. Current parade arrangement: List: 65 25 500 5000 950 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 1 Enter the size (kg) of the next horse to arrive: 499 The horse is less than or equal to 500 kg. Adding to the beginning of the parade. Current parade arrangement: List: 499 65 25 500 5000 950 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 3 Removing the horse from the back of the parade. The horse's size was 950 kg. Current parade arrangement: List: 499 65 25 500 5000 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 2 Removing the horse from the front of the parade. The horse's size was 499 kg. Current parade arrangement: List: 65 25 500 5000 What would you like to do? (1) Add a horse to the parade (2) Remove a horse from the front the parade (3) Remove a horse from the back the parade (4) Start the parade Choice: 4 Current parade arrangement: List: 65 25 500 5000 The parade is starting. Performing final sort. Final parade arrangement: List: 25 65 500 5000 The parade has ended. Emptying parade. The parade has been emptied. Interfaces class IntegerNode{ public: IntegerNode(); int getData(); void setData(int); IntegerNode* getNext() const; void setNext(IntegerNode*); private: int data; IntegerNode* nextNode; }; class IntegerList{ public: IntegerList(); unsigned int getSize() const; bool listEmpty() const; // determines if the list is empty void displayList(); void pushBack(int); // adds an IntegerNode to the end of the list int popBack(); // removes an Integer node from the end of the list, returning the data from the node void pushFront(int); // adds an IntegerNode to the beginning of the list int popFront(); // removes an Integer node from the beginning of the list, returning the data from the node void clearList(); void sortList(); private: unsigned int listSize; IntegerNode* head; };