Assignment 2 (Phase 1, Sprint 2)

In Assignment 2, we are going to put the data structures we implemented in Assignment 1 to use as we build a small program that pretends to be a back-end for a shopping website, which draws upon Labs 4 and 5. Like the labs, the program will be an interactive TUI program (TUI = Text User Interface or Terminal User Interface). The reason for going with an interactive program is because it tends to make things easier – if the program segfaults right after I hit “edit item”, then it is quite easy to know where to start looking for bugs.

During the course of this assignment, feel free to pretend that we are coding (part of) the logic for the backend of a website that sells stuff. We will focus on what goods are in stock, the quantities, the locations for these in a warehouse, and management of shopping carts. (There is of course tons more in the backend than what we will implement, like recommendations, search, tracking user’s movements through the store for A/B testing, etc.)

To test the interaction of all the parts of our program, we are going to build a small frontend in the form of a text user interface. We could easily imagine the commands being issued by a store front. Some good news is that lots of the frontend work is already done – by you, during the labs. We have infrastructure for reading user inputs and parsing them.

We can pretend that the frontend is queries and information going back and forth between some fancy website interface and the backend, which holds all the logic of the system.

The above specification details the functional requirements i.e., what the software does. In contrast, non-functional requirements are about how the software does what it does, and its constraints.

Non-functional requirements are often every bit as important for a piece of software as the functional requirements. For example, if we must fit the program withing 1 Mb or memory, or always respond within 10 milliseconds, etc. – it may well be that a functionally perfect software is unusable for the customer if we fail to deliver on these.

In this assignment, the non-functional requirements are a bit unusual in that they come in the form of constraints on your implementation which are meant to guide to write good code, or face interesting situations. Nevertheless, these requirements are indeed non-functional ones.

I UNIX-miljö kan indata till ett program komma från en textfil. När programmet körs läses svaren till programmets frågor från en fil istället för att matas in för hand. Detta kommer att vara nyttigt för att testa ditt program i denna uppgift eftersom det kommer att krävas många inmatningar för att fylla programmet med intressant data.

Du kan t.ex. pröva att styra en minimal interaktion med programmet så här. Nedanstående antar att menyvalen är Q för Quit, A för Add Item, L för List Items, och att ordningen på indata i Add Item är namn, beskrivning och pris.

1. Skapa en fil test.txt med innehållet Q och en radbrytning. (Q för att avsluta programmet – byt till annat tecken om du gjort ändringar.)
2. Kör programmet så här: ./myprog < test.txt där myprog är det kompilerade programmet.

Nu kan du pröva att ändra i test.txt. T.ex. så här:

A
Kritor
Vita kritor
20
L
Q

Detta skall lägga till en vara (kritor), lista hela varukatalogen, och sedan avsluta. (Notera att ditt program kanske tar emot indata i en annan ordning!)

Implementing support for undoing actions is possible by maintaining a LIFO stack of actions in the program (we call this the undo stack). Every time the user performs an undoable action through the frontend, we push its counter-action to the undo stack. When the user wants to undo, we simply pop the last counter-action from the undo stack and perform it.

Some actions might require that we reset the undo stack. For example, support for opening another database file could be such an event.

Note that we can use our list to implement a LIFO stack – push using prepend and pop using remove with index 0.

Examples:

• The counter-action for adding a merchandise \(m\) is the removal of \(m\).
• The counter-action for the removal of shopping cart \(c\) is adding \(c\) back to the carts list.
• The counter-action for checkout of shopping cart \(c\) is adding \(c\) back to the carts list, and replenishing the stock for all merchandise that was removed when \(c\) was checked-out.
• There is no counter-action for calculating the costs of a shopping cart.

One possible design is to create a struct action which holds a pointer to an undo function that should be called, all the arguments to this function, and a pointer to the next action to be performed in case the undo action requires several function calls. Because different functions take different arguments, the arguments part of action should probably be a union.

Here is an incomplete sketch of how we could implement undo functionality. It adds a type for the undo stack, and create, push and pop functions for it. It shows how the add merchandise backend function – in addition to adding a merchandise to the database – creates an undo action datum, populates it, and pushes it to the undo stack. Last, it shows the undo function that pops from the undo stack, and calls the function of the popped action.

typedef undo_stack_t list_t;

undo_stack_t *undo_stack_create()
{
  return ioopm_linked_list_create();
}

action_t *undo_stack_pop(undo_stack_t *undo_stack)
{
  if (ioopm_hash_table_size(undo_stack) > 0)
    {
      elem_t e = ioopm_linked_list_remove(undo_stack, 0);
      return e.pointer; 
    }
  else
    {
      return NULL;
    }
}

void undo_stack_push(undo_stack_t *undo_stack, action_t *action)
{
  ioopm_linked_list_prepend(undo_stack, action);

  /// if the size of the stack is > 16, remove from the end and 
  /// free actions and (possibly) their associated memory 
}

bool add_merch(db_t *db, undo_stack_t *undo_stack, merch_t *m) 
{
  ioopm_hash_table_insert(db, m.name, m);

  action_t *undo = calloc(1, sizeof(action_t)); /// FIXME: move to a create function
  undo->func = undo_add_merch; 
  undo->args.db = db;
  undo->args.merch_id = m.name;

  undo_stack_push(undo_stack):
}

bool undo(undo_stack_t *undo_stack)
{
  action_t *action = pop_undo(undo_stack);
  if (action == NULL) return false; /// Nothing to undo

  do 
   {
     action.func(action.args); /// call the undo function with its arguments
     action_t *tmp = action; 
     action = action->next;

     free(tmp); 
   }
  while (action); //7 to support several linked actions

  return true;
}

void undo_add_merch(undo_args_t *args)
{
  remove_merch(args->db, args->merch_id); 
  /// any calls to free necessary
}

typedef%20undo_stack_t%20list_t%3B%0A%0Aundo_stack_t%20%2Aundo_stack_create%28%29%0A%7B%0A%20%20return%20ioopm_linked_list_create%28%29%3B%0A%7D%0A%0Aaction_t%20%2Aundo_stack_pop%28undo_stack_t%20%2Aundo_stack%29%0A%7B%0A%20%20if%20%28ioopm_hash_table_size%28undo_stack%29%20%3E%200%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20elem_t%20e%20%3D%20ioopm_linked_list_remove%28undo_stack%2C%200%29%3B%0A%20%20%20%20%20%20return%20e.pointer%3B%20%0A%20%20%20%20%7D%0A%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20%7D%0A%7D%0A%0Avoid%20undo_stack_push%28undo_stack_t%20%2Aundo_stack%2C%20action_t%20%2Aaction%29%0A%7B%0A%20%20ioopm_linked_list_prepend%28undo_stack%2C%20action%29%3B%0A%0A%20%20%2F%2F%2F%20if%20the%20size%20of%20the%20stack%20is%20%3E%2016%2C%20remove%20from%20the%20end%20and%20%0A%20%20%2F%2F%2F%20free%20actions%20and%20%28possibly%29%20their%20associated%20memory%20%0A%7D%0A%0Abool%20add_merch%28db_t%20%2Adb%2C%20undo_stack_t%20%2Aundo_stack%2C%20merch_t%20%2Am%29%20%0A%7B%0A%20%20ioopm_hash_table_insert%28db%2C%20m.name%2C%20m%29%3B%0A%0A%20%20action_t%20%2Aundo%20%3D%20calloc%281%2C%20sizeof%28action_t%29%29%3B%20%2F%2F%2F%20FIXME%3A%20move%20to%20a%20create%20function%0A%20%20undo-%3Efunc%20%3D%20undo_add_merch%3B%20%0A%20%20undo-%3Eargs.db%20%3D%20db%3B%0A%20%20undo-%3Eargs.merch_id%20%3D%20m.name%3B%0A%0A%20%20undo_stack_push%28undo_stack%29%3A%0A%7D%0A%0Abool%20undo%28undo_stack_t%20%2Aundo_stack%29%0A%7B%0A%20%20action_t%20%2Aaction%20%3D%20pop_undo%28undo_stack%29%3B%0A%20%20if%20%28action%20%3D%3D%20NULL%29%20return%20false%3B%20%2F%2F%2F%20Nothing%20to%20undo%0A%0A%20%20do%20%0A%20%20%20%7B%0A%20%20%20%20%20action.func%28action.args%29%3B%20%2F%2F%2F%20call%20the%20undo%20function%20with%20its%20arguments%0A%20%20%20%20%20action_t%20%2Atmp%20%3D%20action%3B%20%0A%20%20%20%20%20action%20%3D%20action-%3Enext%3B%0A%0A%20%20%20%20%20free%28tmp%29%3B%20%0A%20%20%20%7D%0A%20%20while%20%28action%29%3B%20%2F%2F7%20to%20support%20several%20linked%20actions%0A%0A%20%20return%20true%3B%0A%7D%0A%0Avoid%20undo_add_merch%28undo_args_t%20%2Aargs%29%0A%7B%0A%20%20remove_merch%28args-%3Edb%2C%20args-%3Emerch_id%29%3B%20%0A%20%20%2F%2F%2F%20any%20calls%20to%20free%20necessary%0A%7D%0A

Nu skall vi lägga till stöd för att spara databasen på fil och läsa upp den igen. Börja med att bekanta dig med hur funktionerna fopen, fread och fclose fungerar, lämpligen genom att implementera en egen version av UNIX-programmet cat (skriv man cat om du inte känner till programmet).

Programmet skall ta som kommandoradsargument, namnet på den fil som innehåller databasen. Om denna fil inte finns skall den skapas och databasen skall vara tom. När programmet avslutas skall databasen sparas ned på filen så att den kan läsas upp igen nästa gång programmet startar. Det finns inga kommandon i programmet för att spara eller ladda databasen – det sker automatiskt.

För att spara datat i databasen har du två val:

1. Spara datat som radorienterad text där varje vara tar upp minst 3 rader (namn, beskrivning, pris, …); en lagerplats tar upp minst tre rader (lagerplats, vilken vara, vilken kvantitet, …), och motsvarande för en shopping cart. För enkelhets skull kan du ha en separat fil för varje typ av data du vill spara (varor, lagerplatser, kundvagnar, …) – så kan du läsa rätt antal rader och skapar en post i databasen från den. När man når EOF – end of file – är du klar med en fil.
2. Definiera ett binärt filformat på motsvarande sätt. En hyfsat bra start för varor är detta:

int siz;             // antal bytes i posten
int name_siz;        // antal tecken i nästföljande sträng
char[name_siz] name; // namnet
int desc_siz;        // antal tecken i nästföljande sträng
char[desc_siz] desc; // beskrivningen
int price;           // pris

int%20siz%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20antal%20bytes%20i%20posten%0Aint%20name_siz%3B%20%20%20%20%20%20%20%20%2F%2F%20antal%20tecken%20i%20n%C3%A4stf%C3%B6ljande%20str%C3%A4ng%0Achar%5Bname_siz%5D%20name%3B%20%2F%2F%20namnet%0Aint%20desc_siz%3B%20%20%20%20%20%20%20%20%2F%2F%20antal%20tecken%20i%20n%C3%A4stf%C3%B6ljande%20str%C3%A4ng%0Achar%5Bdesc_siz%5D%20desc%3B%20%2F%2F%20beskrivningen%0Aint%20price%3B%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20pris%0A

Man kan till och med tänka sig att själva filen startar med en int som berättar hur många poster den innehåller, men det går förstås också bra att leta efter EOF – end of file.

These are meant for those who like to tinker with the assignment, wants to do more, or needs an idea for an extension to demonstrate something.

1. Find the cheapest or most expensive merchendise
2. Print the sum of all items in stock
3. Compaction: move all items of the same merchendise to a single storage location
4. Support for multiple sort orders when printing merchendise
5. Search for a certain merchendise and see all storage locations for that
6. Support some degree of “fuzzy matching” for 5.
7. Add an upper limit on how many items can be stored on a storage location. Note the interaction with this and 3. above – make sure that all items of a single merchendise are stored consequtively.
8. Make the program case insensitive, meaning the following will be considered three different merches: “foo”, “Foo” and “FOO”.
9. Support changing the name of a merchendise – this might affect its key!
10. Support for saving the database to file and opening a different database file while the program is running.
11. Merge two merches into one, with one name, description and all the stock of the original two.

1. At the end, go over your backlog of cheats and dodges and see which ones need taking care of. Ideally this stack should be empty. If you have made any special deals for some parts of your code, make sure these are documented somewhere (in the repo).
2. As the first section of README.md, add instructions for how to build the program and run its tests. Ideally this should be as easy as make test. In this section, also state the line coverage and branch coverage per .c file and what tool you used to obtain these numbers.
3. Write a minimal documentation of how to use your program – after building it, how does one start it, and what files etc. (if anything) must be present. Put this in a README.md in the top-level directory for this assignment.
4. Prepare a demonstration of z101 to give at the next lab. In addition to z101, pick another 2-3 achievements to tick off, and include these in your demonstration preparation. To back up your presentation, present evidence like places in your code where relevant things show up, documentation, paper drawings, etc. – things that support your demonstration. Think carefully about what things fit together (ask for help if you feel uncertain after trying) and what achievements tell a good story together. Make sure that not one person dominates the demonstration or answers all questions to avoid someone failing the demonstration because there was no evidence of achievements mastery.
5. Send an email to z101@wrigstad.com with your names and usernames, a link to the GitHub repository where the code can be checked out.
6. Create a final commit for the assignment and check it into GitHub. Tag the commit with assignment2_done.
7. Optional Please take time to feedback on the assignment.

Note: Don’t expect any feedback on your program over what you have got from the oral presentations. If you want more feedback on specific things, ask questions in conjunction with your presentations, or add your name to the help list.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, ran by Tobias Wrigstad.