In this program, you will create an ordered singly linked list for managing timed events. You will simulate arrivals and departures at different "clock" times. You will advance a "clock" based on the next event time.

You have been furnished with an include file and a data file.

Examine the Person, Event, NodeLL, and Simulation typedefs in the cs2123p3.h include file. You may modify it to use a different representation of a linked list.

Input Data: (use stdin)

There are many records (terminated by EOF) that define arrivals:

szName iDeltaDepart iDeltaNextArrival

15s 3d 3d

Consider this input:

Ant,Adam 10 5

Mander,Sally 4 3

King,May 6 6

King,Joe 9 6

Graph,Otto 2 5

Based on that data, we have arrivals at these times:

Arrival Time	Person	Depart Delta	Next Arrival Delta
0	Ant,Adam	+10	+5
5	Mander,Sally	+4	+3
8	King,May	+6	+6
14	King,Joe	+9	+6
20	Graph,Otto	+2	+5
25	End of File (no arrival)	-	-

For this program, there are only two event types (there will be different event types in Program #4):

EVT_ARRIVE - an arrival event

EVT_DEPART - a departure event

You are required to create a runSimulation(Simulation sim) function which is passed a sim (which points to a clock and a timed event list). runSimulation will loop through the timed events (which are placed in order by event time in the linked list) and set the clock to the time of the current timed event. Based on the event, (for now) it prints the time, person, and event. In program #4, the events will do more than just print a message.

(There are more events based on our input file than what is shown below.)

Time	Person	Event
0	Ant,Adam	Arrive
5	Mander,Sally	Arrive
8	King,May	Arrive
9	Mander,Sally	Depart
10	Ant,Adam	Depart
14	King,Joe	Arrive
14	King,May	Depart
20	Graph,Otto	Arrive
22	Graph,Otto	Depart
23	King,Joe	Depart
23	SIMULATION	TERMINATES

Since there aren't any additional events, the simulation terminates.

Notice that some of the events are at the same time, but InsertOrderedLL in the notes didn't allow insertion of duplicates. You must change it.

Your output:

Print the time of each event, the person, and the event type (as text).

Turn in all of your C code, include file, and the output. As usual, your code must be written according to my standards.

c program***********************************

/**************************************************************************************** cs2123p3.c by Sean Calhoun Purpose: This program will use a linked list to manage timed events. It will simulate arrivals and departures at different "clock" times. The clock will be advanced based on the next event. Input: An input file that will be read in one line at a time. The file will have a szName, iDeltaDepart time and iDeltaNextArrival time. These times are deltas, meaning the difference from the last clock time, not the actual time of arrival. Some sample data: Fred 10 5 Daphne 4 3 Velma 6 6 Shaggy 9 6 Scooby 2 5 Scrappy 1 3 Results: Print the time of each event, the person, and the event type (as text): Sample results:***********************************************************************/ #include #include #include #include #include "cs2123p3.h" // Main program int main(int argc, char *argv[]) { // start here...

// Create a simulation and time limit Simulation sim = (Simulation) malloc(sizeof(SimulationImp)); int iTimeLimit = 1000; sim->eventList = newLinkedList();

// run simulation runSimulation(sim, iTimeLimit); //free simulation and list free(sim->eventList); free(sim); return 0; } /**************************runSimulation************************************************** void runSimulation(Simulation simulation, int iTimeLimit) Purpose: Runs through a timed simulation of events and stores those events in a linked list. The linked list will then be displayed to show the simulation. Parameters: i Simulation sim simulation structure containing the LinkedList eventList and iClock variables i int iTimeLimit Time limit for simulation Returns: N/A Notes: If the iClock variable passes the iTimeLimit variable the simulation will terminate *****************************************************************************************/ void runSimulation(Simulation sim, int iTimeLimit) { char szInputBuffer[100]; // entire input line char szTempToken[15]; // temp token variable to use with getToken function int iEvent; // variable for event Event event; // Event variable to hold values to be added to Linked List

sim->iClock = 0; // read text lines containing events until EOF while((fgets(szInputBuffer, 100, stdin) != NULL) && sim->iClock < iTimeLimit) { // get name token from szInputBuffer getToken(szInputBuffer, event.person.szName, MAX_TOKEN); // get other (time) tokens from szInputBuffer getToken(szInputBuffer, szTempToken, MAX_TOKEN); //USLESS ONE // printf("%d ", atoi(szTempToken)); event.person.iDepartUnits = atoi(szTempToken); // delta depart // create arrive node // set iTime = iClock for arrival event.iTime = sim->iClock; event.iEventType = EVT_ARRIVE; insertOrderedLL(sim->eventList, event); // create depart node event.iEventType = EVT_DEPART; // set.iTime = iClock + event.person.iDepartUnits; event.iTime = sim->iClock + event.person.iDepartUnits; insertOrderedLL(sim->eventList, event); // grab last token for next arrival //USLESS TWO getToken(szInputBuffer, szTempToken, MAX_TOKEN);//ULLESS IDFiK // printf("%s ", szTempToken); iEvent = atoi(szTempToken);//ULES I GIVE UP sim->iClock += iEvent; } // Print Results printf("%6s %-12s %-10s ", "Time", "Person", "Event"); // read through and print simulation.eventList NodeLL *p; for(p = sim->eventList->pHead; p != NULL; p = p->pNext) { if((p->event.iEventType) == EVT_ARRIVE) printf("%6d %-12s %-10s ", p->event.iTime, p->event.person.szName, "Arrive"); if((p->event.iEventType) == EVT_DEPART) printf("%6d %-12s %-10s ", p->event.iTime, p->event.person.szName, "Depart"); } printf("%6d %-12s %-10s ", p->event.iTime, "SIMULATION", "TERMINATES"); } /**************************newLinkedList************************************************** LinkedList newLinkedList() Purpose: Creates a Linked List Parameters: N/A Returns: A linked list Notes: N/A *****************************************************************************************/ LinkedList newLinkedList () { LinkedList list = (LinkedList) malloc(sizeof(LinkedListImp)); // Mark the list as empty list->pHead = NULL; // empty list return list; } /*************************searchLL******************************************************* NodeLL *searchLL(LinkedList list, int match, NodeLL **ppPrecedes) Purpose: Searches through a linked list for placement of a node. Returns the node location once found where to insert. Parameters: i LinkedList list Linked list i int match an int (time) that we are trying to match in the linked list i/o NodeLL **ppPrecedes Pointer to the pPrecedes pointer Returns: Position of the node to be inserted (either the actual position or NULL if not found or if at the beginning of list). Notes: returns pPrecedes through parameter list. ****************************************************************************************/ NodeLL *searchLL(LinkedList list, int match, NodeLL **ppPrecedes) { NodeLL *p; // used when the list is empty or we need to insert at the beginning *ppPrecedes = NULL;

// Traverse through the list looking for where the key belongs or // the end of the list. for (p = list->pHead; p != NULL; p = p->pNext) { if (match == p->event.iTime) return p; if (match < p->event.iTime) return NULL; *ppPrecedes = p; }

// Not found return NULL return NULL; } /***************************insertOrderedLL*********************************************** NodeLL *insertOrderedLL(LinkedList list, Event value) Purpose: Inserts a node into an Ordered Linked List Parameters: i LinkedList list Linked List i Event value Event structure that contains the data to be entered into the list Returns: pointer to new node position Notes:

*****************************************************************************************/ NodeLL *insertOrderedLL(LinkedList list, Event value) { NodeLL *pNew, *pFind, *pPrecedes; // see if it already exists pFind = searchLL(list, value.iTime, &pPrecedes); if (pFind != NULL) { // already exists insert node after existing node pNew = allocateNodeLL(list, value); pNew->pNext = pFind->pNext; pFind->pNext = pNew; return pNew; } // doesn't already exist. Allocate a node and insert. pNew = allocateNodeLL(list, value);

// Check for inserting at the beginning of the list // this will also handle when the list is empty if (pPrecedes == NULL) { pNew->pNext = list->pHead; list->pHead = pNew; } else { pNew->pNext = pPrecedes->pNext; pPrecedes->pNext = pNew; } return pNew; } /***************************allocateNode**************************************************** NodeLL *allocateNodeLL(LinkedList list, Event value) Purpose: Creates a new node for the Linked List Parameters: i LinkedList list Linked List i Event value value to be passed into the Event structure in the node Returns: Pointer to a new node Notes:

*******************************************************************************************/ NodeLL *allocateNodeLL(LinkedList list, Event value) { NodeLL *pNew; pNew = (NodeLL *)malloc(sizeof(NodeLL)); if (pNew == NULL) ErrExit(ERR_ALGORITHM, "No available memory for linked list"); pNew->event = value; pNew->pNext = NULL; return pNew; } /***************************removeLL****************************************************** int removeLL(LinkedList list, Event *pValue) Purpose: Removes a node from a Linked List Parameters: i LinkedList list Linked List i/o Event *pValue Pointer to value in the Event Structure of the node Returns: A boolean (int) of if node was removed successfully: TRUE = yes FALSE = no Notes: Also returns the Event Structure via *pValue in the parameter list *****************************************************************************************/ int removeLL(LinkedList list, Event *pValue) { NodeLL *p; if (list->pHead == NULL) return FALSE; *pValue = list->pHead->event; p = list->pHead; list->pHead = list->pHead->pNext; free(p); return TRUE; } /******************** ErrExit ************************************** void ErrExit(int iexitRC, char szFmt[], ... ) Purpose: Prints an error message defined by the printf-like szFmt and the corresponding arguments to that function. The number of arguments after szFmt varies dependent on the format codes in szFmt. It also exits the program with the specified exit return code. Parameters: I int iexitRC Exit return code for the program I char szFmt[] This contains the message to be printed and format codes (just like printf) for values that we want to print. I ... A variable-number of additional arguments which correspond to what is needed by the format codes in szFmt. Notes: - Prints "ERROR: " followed by the formatted error message specified in szFmt. - Prints the file path and file name of the program having the error. This is the file that contains this routine. - Requires including Returns: Returns a program exit return code: the value of iexitRC. **************************************************************************/ void ErrExit(int iexitRC, char szFmt[], ... ) { va_list args; // This is the standard C variable argument list type va_start(args, szFmt); // This tells the compiler where the variable arguments // begins. They begin after szFmt. printf("ERROR: "); vprintf(szFmt, args); // vprintf receives a printf format string and a // va_list argument va_end(args); // let the C environment know we are finished with the // va_list argument printf(" "); exit(iexitRC); } /******************** exitUsage ***************************** void exitUsage(int iArg, char *pszMessage, char *pszDiagnosticInfo) Purpose: In general, this routine optionally prints error messages and diagnostics. It also prints usage information.

If this is an argument error (iArg >= 0), it prints a formatted message showing which argument was in error, the specified message, and supplemental diagnostic information. It also shows the usage. It exits with ERR_COMMAND_LINE.

If this is a usage error (but not specific to the argument), it prints the specific message and its supplemental diagnostic information. It also shows the usage and exist with ERR_COMMAND_LINE.

If this is just asking for usage (iArg will be -1), the usage is shown. It exits with USAGE_ONLY. Parameters: I int iArg command argument subscript or control: > 0 - command argument subscript 0 - USAGE_ONLY - show usage only -1 - USAGE_ERR - show message and usage I char *pszMessage error message to print I char *pszDiagnosticInfo supplemental diagnostic information Notes: This routine causes the program to exit. **************************************************************************/ void exitUsage(int iArg, char *pszMessage, char *pszDiagnosticInfo) { switch (iArg) { case USAGE_ERR: fprintf(stderr, "Error: %s %s " , pszMessage , pszDiagnosticInfo); break; case USAGE_ONLY: break; default: fprintf(stderr, "Error: bad argument #%d. %s %s " , iArg , pszMessage , pszDiagnosticInfo); } // print the usage information for any type of command line error fprintf(stderr, "p2 -c customerFileName -q queryFileName "); if (iArg == USAGE_ONLY) exit(USAGE_ONLY); else exit(ERR_COMMAND_LINE); }

/******************** getToken ************************************** char * getToken (char *pszInputTxt, char szToken[], int iTokenSize) Purpose: Examines the input text to return the next token. It also returns the position in the text after that token. This function does not skip over white space, but it assumes the input uses spaces to separate tokens. Parameters: I char *pszInputTxt input buffer to be parsed O char szToken[] Returned token. I int iTokenSize The size of the token variable. This is used to prevent overwriting memory. The size should be the memory size minus 1 (for the zero byte). Returns: Functionally: Pointer to the next character following the delimiter after the token. NULL - no token found. szToken parm - the returned token. If not found, it will be an empty string. Notes: - If the token is larger than the szToken parm, we return a truncated value. - If a token isn't found, szToken is set to an empty string - This function does not skip over white space occurring prior to the token. **************************************************************************/ char * getToken(char *pszInputTxt, char szToken[], int iTokenSize) { int iDelimPos; // found position of delim int iCopy; // number of characters to copy char szDelims[20] = " "; // delimiters szToken[0] = '\0';

// check for NULL pointer if (pszInputTxt == NULL) ErrExit(ERR_ALGORITHM , "getToken passed a NULL pointer");

// Check for no token if at zero byte if (*pszInputTxt == '\0') return NULL;

// get the position of the first delim //printf("%s\t\t", pszInputTxt); iDelimPos = strcspn(pszInputTxt, szDelims); //printf("%s ", pszInputTxt); // if the delim position is at the first character, return no token. if (iDelimPos == 0) return NULL;

// see if we have more characters than target token, if so, trunc if (iDelimPos > iTokenSize) iCopy = iTokenSize; // truncated size else iCopy = iDelimPos;

// copy the token into the target token variable memcpy(szToken, pszInputTxt, iCopy); szToken[iCopy] = '\0'; // null terminate

// advance the position while(*pszInputTxt == ' ') { // pszInputTxt += iDelimPos; } if (*pszInputTxt == '\0') return pszInputTxt; else return pszInputTxt + 1; }

H file*****************************

/********************************************************************** cs2123p3.h Purpose: Defines constants: max constants error constants event type constants boolean constants Defines typedef for Token Person Event (instead of Element) For Linked List NodeLL LinkedListImp LinkedList For the simulation SimulationImp Simulation Protypes Functions provided by student Other functions provided by Larry previously (program 2) Utility functions provided by Larry previously (program 2) Notes:

**********************************************************************/

/*** constants ***/ // Maximum constants

#define MAX_TOKEN 50 // Maximum number of actual characters for a token #define MAX_LINE_SIZE 100 // Maximum number of character per input line

// Error constants (program exit values) #define ERR_COMMAND_LINE 900 // invalid command line argument #define ERR_ALGORITHM 903 // Error in algorithm - almost anything else #define ERR_BAD_INPUT 503 // Bad input

// Error Messages #define ERR_MISSING_SWITCH "missing switch" #define ERR_EXPECTED_SWITCH "expected switch, found" #define ERR_MISSING_ARGUMENT "missing argument for"

// Event Constants #define EVT_ARRIVE 1 // when a person arrives #define EVT_DEPART 2 // when a person departs the simulation

// exitUsage control #define USAGE_ONLY 0 // user only requested usage information #define USAGE_ERR -1 // usage error, show message and usage information

// boolean constants #define FALSE 0 #define TRUE 1

/*** typedef ***/

// Token typedef used for operators, operands, and parentheses typedef char Token[MAX_TOKEN + 1];

// Person typedef typedef struct { char szName[16]; // Name int iDepartUnits; // time units representing how long he/she stays around } Person;

// Event typedef (aka Element) typedef struct { int iEventType; // The type of event as an integer: // EVT_ARRIVE - arrival event // EVT_DEPART - departure event int iTime; // The time the event will occur Person person; // The person invokved in the event. } Event;

// NodeLL typedef - these are the nodes in the linked list typedef struct NodeLL { Event event; struct NodeLL *pNext; // points to next node in the list } NodeLL;

// typedefs for the ordered link list typedef struct { NodeLL *pHead; // Points to the head of the ordered list } LinkedListImp;

typedef LinkedListImp *LinkedList;

// typedefs for the Simulation typedef struct { int iClock; // clock time LinkedList eventList; } SimulationImp; typedef SimulationImp *Simulation;

/********** prototypes ***********/

// linked list functions - you must provide the code for these (see course notes) int removeLL(LinkedList list, Event *pValue); NodeLL *insertOrderedLL(LinkedList list, Event value); NodeLL *searchLL(LinkedList list, int match, NodeLL **ppPrecedes); LinkedList newLinkedList(); NodeLL *allocateNodeLL(LinkedList list, Event value);

// simulation functions - you must provide code for this void runSimulation(Simulation simulation, int iTimeLimit);

// functions in most programs, but require modifications void exitUsage(int iArg, char *pszMessage, char *pszDiagnosticInfo);

// Utility routines provided by Larry (copy from program #2) void ErrExit(int iexitRC, char szFmt[], ...); char * getToken(char *pszInputTxt, char szToken[], int iTokenSize);

INPUT

Ant,Adam 10 5

Mander,Sally 4 3

King,May 6 6

King,Joe 9 6

Graph,Otto 2 5

Carr,Redd 1 3