.
Computer Science I Program #6: Priority Hair Salon (Binary Heap) Please check Webcourses for the Due Date Read all the pages and Restrictions before starting to write your code Introduction: For this assignment you have to write a c program that will utilizes binary heap data structure. In some implementations, you may require to use a O(n log n) sorting algorithm What should you submit? Write all the code in a single file and upload the main.c file, leak detector c file, and leak detector header file. You need to submit all of them to mimir. Please include the following commented lines in the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 6 This program is written by: Your Full Name */ Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any part of the code in order to better assess your authorship and for further clarification if needed. Caution!!! Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who shared/posted it. Also, getting a part of code from anywhere will be considered as cheating. Deadline: See the deadline in Webcourses/mimir. No late submission will be accepted. An assignment submitted by email will not be graded and such emails will not be replied according to the course policy. What to do if you need clarification on the problem? I will also create a discussion thread in webcourses, and I highly encourage you to ask your question in the discussion board. Maybe many students might have same question as you. Also, other students can reply, and you might get your answer faster. How to get help if you are stuck? According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email, but we cannot guarantee a timely response. Problem Scenario: A new hair salon has opened up near your house and they need a computer science student to help with their scheduling. You figure a couple extra bucks can't hurt and take the job! The hair salon has several stylists (no more than 10 working at a time). Each customer arrives at a particular time and then gets placed in a line to wait for a stylist. (Each stylist has their own waiting line.) The line in which a customer is placed is based on the following: 1. If the customer has no preference, she gets placed in the line for the stylist with the fewest waiting customers. If there's still a tie (multiple stylists have the same number of customers waiting), then the stylist at the lowest numbered hair-cutting station cuts the customer's hair. 2. If the customer has a preferred stylist AND that stylist is working, she gets placed in her preferred stylist's line, regardless of how big it is. If the customer has a preferred stylist and that stylist is not working, then the customer gets placed according to rule #1. But as the name suggests, the hair salon for which you work gives priority to certain individuals and doesn't work strictly on a first come first served basis. In particular, each line for each stylist is actually a priority queue instead of a standard queue. Whenever a stylist is free to cut hair, he'll choose the customer in his line with the highest priority. Here is how priority is determined: 1. Each customer has a number of loyalty points. The higher the number of loyalty points, the higher the priority for the customer. 2. If two customers have the same number of loyalty points, and only one of those customers has labeled this stylist (the one whose line she is in) as their preferred stylist, then that customer gets priority. 3. If two customers have the same number of loyal points, and either both or neither prefer the stylist whose line they are in, then the tie is broken by name, in alphabetical order. Thus, "SHELLY" would get preference over "YUAN", if the tie isn't broken by the previous items. All customers will have unique names, so this third rule is guaranteed to completely determine priority between a set of waiting customers. When a customer arrives at the salon, they provide the following information: 1. The time in minutes, after the salon opens that they arrive (non-negative integer) 2. Their name (uppercase string of letters, length in between 1 and 20, inclusive) 3. The name of their preferred stylist (or "NONE" if they don't have a preferred stylist) 4. Number of loyalty points (non-negative integer) 5. Time of their hair cut, in minutes (positive integer) The last item is important because it also determines the number of loyalty points earned after the cut. In particular, for a m minute haircut, a customer earns m/10 loyalty points, using integer division. The Problem Your task will be to write a program that takes in information about arriving customers in the order in which they come (each one will come at a distinct minute after the salon opens to avoid concurrency issues), and prints out a log in the order in which the haircuts finish, summarizing each cut. If two cuts end at the same exact time, then the log for the cut made by the stylist at the lower numbered hair cut station should be printed first. The Input (to be read from in.txt file) Note: Your program will be run multiple times, using different in.txt files with different test cases. The first line of input will contain two space-separated integers, n (n ≤ 100000), representing the number of customers, and m (m ≤ 10), representing the number of stylists working at the salon for the input case. (No stylist will have the name "NONE".) The following m lines will each contain a single string. The ith (1 ≤ i < m)="" of="" these="" lines="" will="" store="" the="" name="" of="" the="" hair="" stylist="" at="" the="" ith="" styling="" station.="" each="" of="" these="" strings="" will="" consist="" of="" in="" between="" 1="" and="" 20="" upper="" case="" letters.="" each="" stylist="" is="" ready="" to="" cut="" hair="" at="" time="" t="0" minutes="" after="" the="" salon="" opens.="" the="" last="" n="" lines="" of="" the="" input="" case="" will="" each="" contain="" information="" about="" a="" single="" customer.="" the="" ith="" (1="" ≤="" i="" ≤="" n)="" of="" these="" lines="" will="" store="" the="" following="" space-separated="" information:="" ti="" (0="" ≤="" ti="" ≤="" 109),="" si,="" pi,="" li="" (0="" ≤="" li="" ≤="" 105)="" and="" mi="" (0="" ≤="" mi="" ≤="" 104),="" representing="" the="" time="" the="" customer="" arrives="" (in="" minutes)="" after="" the="" salon="" opens,="" the="" customer's="" name="" (a="" string="" of="" in="" between="" 1="" and="" 20="" uppercase="" letters="" that="" is="" not="" "none",="" the="" preferred="" stylist="" for="" this="" customer="" (if="" this="" string="" is="" "none",="" that="" means="" there="" is="" no="" preferred="" stylist,="" otherwise="" the="" string="" represents="" the="" name="" of="" the="" preferred="" stylist,="" who="" may="" or="" may="" not="" be="" working),="" the="" number="" of="" loyalty="" points="" the="" customer="" currently="" has,="" and="" the="" amount="" of="" time="" in="" minutes="" the="" haircut="" the="" customer="" is="" requesting="" will="" take.="" these="" lines="" of="" input="" will="" in="" strictly="" chronologically="" increasing="" order.="" thus,="" for="" all="" distinct="" pairs="" of="" integers="" i="" and="" j="" with="" 1="" ≤="" i="">< j="" ≤="" n,="" ti="">< tj. each of the customer names will be unique. the output (to be printed to standard out) for each customer, print out a single line in the following format: customer m l stylist where customer is the name of the customer who got their hair cut, m is the number of minutes after the salon opened that the haircut was completed, l is the number of loyalty points the customer has after the haircut and stylist is the name of the stylist who cut the customer's hair. these lines should be ordered by the time after the salon opens that the haircuts complete. if there are two or more haircuts that complete at the same time, print these lines out in order of the haircutting station of the stylists, from smallest to largest. sample input 9 3 dave sandy bella 10 jason sandy 50 77 11 sarah none 0 30 15 cynthia max 44 81 22 ravi sandy 30 42 27 chen sandy 30 99 30 amy dave 5 25 31 wendy sandy 31 15 33 brian none 100 10 37 mac sandy 29 45 sample output sarah 41 3 dave amy 66 7 dave jason 87 57 sandy cynthia 96 52 bella wendy 102 32 sandy brian 106 101 bella chen 201 39 sandy ravi 243 34 sandy mac 288 33 sandy note: please double check the numbers and it will be your first step before writing the code implementation restrictions/ run-time/memory restrictions 1. an appropriate structure should be used to store customer information. 2. a binary heap structure should be declared and used to implement the priority queues necessary to solve the problem. this structure should internally have an array of pointers to struct (customer **). the array itself should also be dynamically allocated. (whenever the heap fills up, the array size storing the heap should be doubled like the way we have learned in the lecture.) 3. appropriate functions should be written for the binary heap structure. 4. writing a compareto function that takes two customer pointers c1 and c2 and returns positive if c1 should get higher priority. otherwise, return negative to indicate c1 will get lower priority 5. a statically allocated array of (size 10) binary heap structures should be declared in main to store the lines for each stylist or stations. out of this 10 heaps, you will only use the required number of heaps based tj.="" each="" of="" the="" customer="" names="" will="" be="" unique.="" the="" output="" (to="" be="" printed="" to="" standard="" out)="" for="" each="" customer,="" print="" out="" a="" single="" line="" in="" the="" following="" format:="" customer="" m="" l="" stylist="" where="" customer="" is="" the="" name="" of="" the="" customer="" who="" got="" their="" hair="" cut,="" m="" is="" the="" number="" of="" minutes="" after="" the="" salon="" opened="" that="" the="" haircut="" was="" completed,="" l="" is="" the="" number="" of="" loyalty="" points="" the="" customer="" has="" after="" the="" haircut="" and="" stylist="" is="" the="" name="" of="" the="" stylist="" who="" cut="" the="" customer's="" hair.="" these="" lines="" should="" be="" ordered="" by="" the="" time="" after="" the="" salon="" opens="" that="" the="" haircuts="" complete.="" if="" there="" are="" two="" or="" more="" haircuts="" that="" complete="" at="" the="" same="" time,="" print="" these="" lines="" out="" in="" order="" of="" the="" haircutting="" station="" of="" the="" stylists,="" from="" smallest="" to="" largest.="" sample="" input="" 9="" 3="" dave="" sandy="" bella="" 10="" jason="" sandy="" 50="" 77="" 11="" sarah="" none="" 0="" 30="" 15="" cynthia="" max="" 44="" 81="" 22="" ravi="" sandy="" 30="" 42="" 27="" chen="" sandy="" 30="" 99="" 30="" amy="" dave="" 5="" 25="" 31="" wendy="" sandy="" 31="" 15="" 33="" brian="" none="" 100="" 10="" 37="" mac="" sandy="" 29="" 45="" sample="" output="" sarah="" 41="" 3="" dave="" amy="" 66="" 7="" dave="" jason="" 87="" 57="" sandy="" cynthia="" 96="" 52="" bella="" wendy="" 102="" 32="" sandy="" brian="" 106="" 101="" bella="" chen="" 201="" 39="" sandy="" ravi="" 243="" 34="" sandy="" mac="" 288="" 33="" sandy="" note:="" please="" double="" check="" the="" numbers="" and="" it="" will="" be="" your="" first="" step="" before="" writing="" the="" code="" implementation="" restrictions/="" run-time/memory="" restrictions="" 1.="" an="" appropriate="" structure="" should="" be="" used="" to="" store="" customer="" information.="" 2.="" a="" binary="" heap="" structure="" should="" be="" declared="" and="" used="" to="" implement="" the="" priority="" queues="" necessary="" to="" solve="" the="" problem.="" this="" structure="" should="" internally="" have="" an="" array="" of="" pointers="" to="" struct="" (customer="" **).="" the="" array="" itself="" should="" also="" be="" dynamically="" allocated.="" (whenever="" the="" heap="" fills="" up,="" the="" array="" size="" storing="" the="" heap="" should="" be="" doubled="" like="" the="" way="" we="" have="" learned="" in="" the="" lecture.)="" 3.="" appropriate="" functions="" should="" be="" written="" for="" the="" binary="" heap="" structure.="" 4.="" writing="" a="" compareto="" function="" that="" takes="" two="" customer="" pointers="" c1="" and="" c2="" and="" returns="" positive="" if="" c1="" should="" get="" higher="" priority.="" otherwise,="" return="" negative="" to="" indicate="" c1="" will="" get="" lower="" priority="" 5.="" a="" statically="" allocated="" array="" of="" (size="" 10)="" binary="" heap="" structures="" should="" be="" declared="" in="" main="" to="" store="" the="" lines="" for="" each="" stylist="" or="" stations.="" out="" of="" this="" 10="" heaps,="" you="" will="" only="" use="" the="" required="" number="" of="" heaps="">