Note:

Red text indicates your entries in the console, your entries will not actually be red. Black text in Example Output and inputs: indicates the output of your program.

task A startup has developed a new messaging service and noticed that they had forgotten a few functions in a hurry: Specifically, it is about implementing a metadata search for the existing service.

The messages are currently stored in a very fast object memory in a hip cloud service and can be 7da5d507-2a76-4980-87cb-400148cb407aloaded at any time using an ID such as, for example . Unfortunately, it is not possible to load the messages by day or date. Since the time to the planned launch is short, the startup is now commissioning you as an external service provider to implement the missing functionality in your own in-memory database. In addition to time, money is also very tight and so only small cloud instances can be rented for your software and you must therefore be very careful with the available memory.

Read the entire information before starting the implementation.

Data You receive the data from your client in the format: tag,year,month,day,id transferred, whereby the day, year, month and day are to be saved as integers and the id is a string. The startup prescribes the following structures as the data structure, as they best match the in-house data structures:

Tags should be represented in the following typedef: typedef enum msgtag { NoTag = 0, Important, Work, Personal, ToDo, Later } msgtag;

For data exchange - i.e. as a response to metadata search queries - the following struct should be used so that as little memory as possible is wasted and only the required data, namely the ID, is actually transmitted back: typedef struct MsgID { char* id; } MsgID;

The ID has a maximum length of 40 characters. The data in your in-memory database should be saved in the following struct: Please note that the ID is saved as a pointer to a string in both types (MsgID and MsgDetails). This means that you have to manage the storage separately. typedef struct MsgDetails { char* id; msgtag tag; int year; int month; int day; } MsgDetails;

The core of your in-memory database should be a linear list in which all MsgDetails should be saved until the end of the program. The following data structure is recommended for this: The pointer points to a struct with the data. This enables you to use it for your database as well as for the result lists. typedef struct Node { void* item; struct Node* next; } Node; itemNode

With these data structures it should be possible to solve the actual core task: to return data appropriately after search or filter requests.

API - programming interface Your client expects you to implement the following interfaces:

Node* addMsgDetails(Node*, MsgDetails*): adds a new message to your database. The order is decisive: The message should be inserted in the list in chronological order (oldest message first). Node* freeMsgDetails(Node*): deletes the internal database and releases all memory again. Please note that you have to release both the string ID and struct MsgDetails and then Node itself so that there is no memory loss. Implement filter functions that can be transferred via a function pointer to the following function: The function then returns a list of MsgIDs that match the search criterion. The messages found are added to the front of the result list in the order in which they were found in the internal database. The internal database must not be changed when creating the result list! To the arguments: Node* filterList(Node*, int(*)(int, MsgDetails*), int, int);

Node* is the head of the internal database int(*)(int, MsgDetails*) is the signature of the filter function int is the comparison value for the search int the value that the filter function must return so that a message is saved in the list of MsgIDs An exemplary call for a filter function that matched the tags might look like this: In this example, the function expected of a return value of 1 if a message of the day was. should generate a new list: the data should only contain the ID of the messages (the data structure MsgID must therefore be used). Since the ID itself is a string pointer and memory should be used sparingly, the same pointer to ID should be used as in the internal database. You should implement the following filter functions: // sucht in der Liste head nach Nachrichten, die das Tag 'Important' haben // und gibt eine neue Liste mit nur den MsgIDs zurck. filterList(head, &matchTag, Important, 1)

filterListmatchTagImportant filterList int matchTag(int, MsgDetails*); returns 1 if the tag is matched. int cmpYear(int, MsgDetails*);returns -1 if the transferred year is less than the year in MsgDetails* , 0 if the year is the same and 1 if the transferred year is greater. int cmpDate(int, MsgDetails*);with return values analogous to cmpYear(). The date can be read in as a number, as is suggested when reading in YYYYMMTT:, for example 20201012. With suitable multiplications and additions, this number can also be calculated from individually stored values: year * 10000 + month * 100 + day. Also provide a function reverseList()that allows a given list to be turned over: Node* reverseList(Node*) You also need a function freeMsgIDs(): which deletes a result list - i.e. struct MsgID and the associated node structs - but not the pointer to the ID string, which is still stored in the database and used there. Node* freeMsgIDs(Node*) Prototype with text interface First of all, your client would like to have a text interface for your database in order to be able to try out whether the database works as required before integrating it directly via API.

General information on inputs: Spaces and line breaks should be ignored. If something invalid was entered, "Error: unknown command!" output and read in again. However, you can be confident that characters are entered when characters are expected and numbers are entered when numbers are expected.

Your program should support the following commands:

r (read), read in a data record in the appropriate format (see example). R (Reverse) to reverse the order of the internal database. p (print), the internal database output (see example). q (quit), quit the program and release all memory again. t (tag), ask the user what tag to filter for ("which tag (0-5)?"), filter the database for the specified tag, then enter the resulting list of IDs and enter the required memory free again. y (year less), ask the user for the year ("which year?"), filter the database by the specified year, then output the list of IDs of messages whose year is less than the one entered and type Free the required memory again. D (Date greater), ask the user for the date ("which date (YYYYMMDD)?"), Filter the database by the specified date, then output the resulting list of messages whose date is greater than the specified and free up the required memory again e (exact date), filter the database by the specified date ("which date (YYYYMMDD)?") for messages with the entered date, then enter the resulting list of message IDs and free up the required memory. Use the functions required above for this! The result lists of the various queries should all look the same: the string '\ nID:' followed by the ID of the message (see also the example below). The internal database should be output in two lines and contain all details: 2 spaces must be output before the date. (As stated further below, it is recommended for the exercises to start each output with a '\ n' and not to output any output at the end of a line.) ID: ID-der-Nachricht (ID-der-Nachricht=ID of the message) YYYY-MM-TT Tag: 0-5

Example outputs and inputs:

MsgDB - test program cmd: r

enter msg metadata (tag, year, month, day, id): 3,2019,02,22,11ea1760-8b0c-4fcd-9f60-f920b3cad2e1

cmd: r

enter msg metadata (tag, year, month, day, id): 3,2020,05,08,21c9107d-24fb-4b6b-ab4e-d93ebd4f66dc

cmd: p

ID: 11ea1760-8b0c-4fcd-9f60-f920b3cad2e1 2019-02-22 Day: 3 ID: 21c9107d- 24fb-4b6b-ab4e-d93ebd4f66dc 2020-05-08 Day: 3 cmd: r

enter msg metadata (tag, year, month, day, id): 4,2020,03,27, c187577a-e9a0-4aa6-9141-ee65cd126111

cmd: t

which tag (0-5)? 3

ID: 21c9107d-24fb-4b6b-ab4e-d93ebd4f66dc ID: 11ea1760-8b0c-4fcd-9f60-f920b3cad2e1 cmd: q

General information on formatting: In Coderunner, each individual entry is confirmed by a line break, which is not visible in the output. If you start the program outside of Coderunner, enter values yourself (see sample output) and produce line breaks in the process, this affects the output (more line breaks than with automatic testing in Coderunner).

General information on output: Always output line breaks before a new line and not at the end. If you do so, it should be easier to bring the formatting into line with the expected output. The program therefore starts with a line break.