Homework III variant: Abstract data structures

Task description

This variant is based on the existing homework 2 variant. There are additional requirements by adding more complexity from using abstract data structures and additional features.

Requirements for the program

The code must adhere to all of the best practices introduced during Programming 1 and Programming 2.

Your solution can include topics that have not been covered, as long as they are used correctly and well documented. You need to provide motivation why those concepts were used so that it clear, that you have mastered those topics.

Requirements for the standards and environment

The program must be written in the C programming language. You are permitted to use the C90 and C99 standards. Upon an agreement, you can also use newer standards such as C11,  C17 or C23.

In addition to using the standard C libraries, you are allowed to use C POSIX and GNU C libraries. Any libraries outside of this must be agreed upon separately.

Your program will be compiled and tested in a Linux environment, equivalent to the one in the lab computers (OpenSUSE SLED-15 SP5, using GCC-12) or the recommendation for home setup  (Ubuntu Linux 24.04, using GCC-13 compiler or later). The software does not need to be compatible with other operating systems such as Windows or MacOS.

Task-specific requirements

For this task, all requirements for homework 2 apply for both the documentation and the code. In addition, the following has to be done:

  • All user input must be checked. If the input is incorrect, you must show an error and re-prompt the user. Invalid input format must be handled gracefully (e.g. user enters a string instead of a number).
  • It must be possible to return from any submenu and action at any time. E.g. if the user accidentally enters deletion of a record, they must be able to return to the previous menu without specifying anything for deletion.
  • Task should be separated out into multiple .c and .h files in a meaningful way. A Makefile should be included to build the solution.
  • Must use CSV (comma separated values). In addition, the field itself must be able to allow for the same symbol as is the separator.
  • You must use a doubly linked list when reading the data file, which only contains a primary key (e.g. movies, books, phones, accounts), to memory. You can change this to use any type of trees, if you feel this will improve your program. In this case the benefit must be documented.
  • Items for the second data file can be read to the data structure of your choosing that makes sense for the task.  It is required that PK-FK relation will be handled by pointers. This means that from any item in the first data structure, you must be able to go directly to the related items in the second data structure by dereferencing a pointer. The association must be done while reading in the data from the files or right after it.
    • You can combine multiple accessing methods if this makes sense for your task.
    • Some ideas:
      • A pointer to a linked list
      • A pointer to a tree
      • A pointer to a dynamic array of pointers which reference the items.
      • A pointer to a hash table
      • …
  • You must be able to delete any entry from either data structure through the program
    • The removal must immediately take place in the program while it’s still running.
    • The removed row(s) must also be removed from the file(s), so the next time the program runs, they will not exist any more. This can be done either immediately when deleting or after the user decides to exit the program.
    • Removal must be done by their respective unique IDs.
    • Data integrity must be enforced.
      This means that you cannot delete an item from the primary file which still has PK-FK relations to the second file. Once all items have been deleted which have a PK-FK relationship, then the item from the main data structure can be deleted
      E.g. If a movie has ratings, the movie cannot be deleted before all of the ratings for that movie have been deleted.
  • You must be able to add any entry to either file through the program.
    • Application must support input that consist of multiple words. Input correctness must be validated (i.e. does it match the expected data type).
    • The addition must immediately take place in the program while it’s still running
    • The added row(s) must also be added to the file(s), so the next time the program runs, they will also be read in. This can be done either immediately when adding or after the user decides to exit the program.
    • Data integrity must be enforced (E.g. you cannot add ratings to a movie that doesn’t exist yet).
    • All fields must be checked to match the format.
    • The generated ID value must be unique (typically a sequential value). Only in the case of using well-known values such as ISBN codes for books, Estonian ID codes for people, international IBAN numbers for bank accounts etc. can such a number be entered manually while adding entries.
  • The new functionality must be added to the menu.

Documentation

  • All requirements set for the Homework 2 documentation apply. Extend your current documentation to cover all the updates and improvements from Homework 3.
  • Visualize the data structure in the files
    • Use either UML class diagram or ERD (entity relationship diagram).
    • Make sure to show data types, primary keys and PK-FK relationship.
  • Visualize your data structure that you built in the application.

Note: Function documentation also a part of the documentation requirement, which must be written into the code. For every function, detail its purpose, parameters, requirements for parameters, return value and possible side effects.

Submitting your task

The supervisor for this task is Eeva-Maria Tšernova  (Mattermost: @eeva). 

Submitting of the homework is in two stages:

  1. Upload your solution to Moodle: https://moodle.taltech.ee/mod/assign/view.php?id=339483
  2. Write a message to the task supervisor using their preferred method of contact to let them know that the solution has been uploaded. It’s also recommended to include the solution in the message!

You need to submit two files:

  1. The documentation (pdf document)
  2. All necessary files for your project as a .zip archive (source code, data files, Makefile. If necessary, configuration files).

The supervisor can ask for an on-site defense of the solution.