Dnes budete pomáhať pri doručovaní pošty na miestnom úrade v mieste Vašho bydliska.

Starosta rozhodol o založení obecnej poštovej služby - OPS. Obecná poštová služba má za úlohu príjmať a spracovávať zásielky typu list z celej obce.
Na miestnom úrade ale nastal chaos a listy sa pomiešali. Firme ktorá vyhrala verejné obstarávanie sa síce podarilo navrhnúť aplikačné programové rozhranie (API) a jednotkové testy (unit tests), ale tesne pred implementáciou skrachovala.

Vaša úloha je jasná - zachránte projekt a dokončite informačný systém list_ops. Implementujte všetky navrhnuté funkcie tak, aby vyhoveli jednotkovým testom.

Analýza situácie

Najprv si stiahnite šablónu a rozbalte ju do adresára cv4.

Na servri sigma.tuke.sk by malo fungovať toto:

wget https://student.kemt.fei.tuke.sk/pvjc/cvicenia/test/list-ops.zip
unzip list-ops.zip
mv list-ops cv4

V adresári by sa malo objaviť toto:

• list_ops.c - súbor s implementáciou, skoro prázdny. Tu by sme mali niečo doprogramovať.
• list_ops.h - hlavičkový súbor, obsahuje predpisy a pokyny na implementáciu
• makefile - príkazy na zostavenie celého programu
• test-framework - pomocné súbory pre jednotkové testy
• test_list_ops.c - jednotkové testy, teda funkcie ktoré overia, či Vaše funkcie sú v poriadku.

Pozrite si makefile, skúste program preložiť. Výsledný program nebude robiť nič, okrem toho že pomocou jednotkových testov vyskúša Vaše funkcie. Ak budú funkcie v poriadku, bude možné ich využiť v inom programe.

Najdôležitejšia časť celého projektu sú dátové typy. Ich definície sa nachádzajú na začiatku hlavičkového súboru list_ops.h:

typedef int list_element_t;

typedef struct {
   size_t length;
   list_element_t elements[];
} list_t;

Z toho zistíme, že základným prvkom list je typ list_element_t, ktorý je zhodou okolností celé číslo. Ale mohol by to byť aj znak alebo imý typ.

Zaujímavé je, že takto navrhutá štruktúra pre dynamické polia využíva špeciálnu vlastnosť jazyka C99, zvanú flexibilný atribút (flexible array member). V tomto prípade prvok elements sa obsahuje adresu začiatku poľa, ale nie je to smerníková premenná.

V pamäti je tesne za premennou length priamo uložené celé pole elements, nie len smerník na jeho začiatok.

začiatok   pole prvkov  
length     elements   
  |           |       
  v           v       
  | length  | elements[0] | elements[1] ....

Druhým dôležitým typom je list_t. Je to zložený údajový typ (štruktúra), ktorý sa skladá z dvoch častí. Tento typ vyjadruje dynamické pole. V dynamickom poli si vieme uložiť jeden alebo viac údajov typu list_element_t.

• size_t length hovorí o počte prvkov.
• list_element_t elements[] je smerník na začiatok poľa, to je to isté ako list_element_t* elements.

O niečo nižšie sa nachádzajú predpisy funkcíí (deklarácie) funkcií spolu s opisom čo by mali robiť. Pozrite si list_ops.h a zistite aké funkcie treba implementovať:

/// list_ops.h

// constructs a new list
list_t *new_list(size_t length, list_element_t elements[]);

// append entries to a list and return the new list
list_t *append_list(list_t *list1, list_t *list2);

// filter list returning only values that satisfy the filter function
list_t *filter_list(list_t *list, bool (*filter)(list_element_t));

// returns the length of the list
size_t length_list(list_t *list);

// return a list of elements whose values equal the list value transformed by
// the mapping function
list_t *map_list(list_t *list, list_element_t (*map)(list_element_t));

// folds (reduces) the given list from the left with a function
list_element_t foldl_list(list_t *list, list_element_t initial,
                          list_element_t (*foldl)(list_element_t,
                                                  list_element_t));

// folds (reduces) the given list from the right with a function
list_element_t foldr_list(list_t *list, list_element_t initial,
                          list_element_t (*foldr)(list_element_t,
                                                  list_element_t));

// reverse the elements of the list
list_t *reverse_list(list_t *list);

// destroy the entire list
// list will be a dangling pointer after calling this method on it
void delete_list(list_t *list);

Tieto funkcie budú pracovať s definovanými dátovými typmi. Spolu by mali tvoriť modul - niekoľko funkcí pre prácu s dynamickými poliami.

Na štúdium

Pre implementáciu dynamického poľa budeme určite potrebovať tieto funkcie:

• malloc, calloc
• free
• memcpy

Smerník na funkciu

Zaujímavou časťou deklarácií funkcíí sú argumenty typu:

bool (*filter)(list_element_t)

To znamená smerník na funkciu ktorý vyzerá napríklad takto:

bool is_odd(list_element_t a){
  return a % 2;
}

Ak si definujeme takúto funkciu:

list_t *filter_list(list_t *list, bool (*filter)(list_element_t));

Jej správne volanie bude vyzerať takto:

list_t* novy_filtrovany_list = filter_list(moj_stary_list,is_odd);   

Implementácia funkcií

Po teoretickej príprave môžeme implementovať funkcie - doplniť kód tak, aby robil to čo má podľa predpisov.

skopírujte predpisy funkcíí do súboru list_ops.c. Upravte funkcie tak, aby sa dali skompilovať.

Získate tak, súbor ktorý sa v zásade dá preložiť:

#include "list_ops.h"

// constructs a new list
list_t *new_list(size_t length, list_element_t elements[]){
  return NULL;

}

// append entries to a list and return the new list
list_t *append_list(list_t *list1, list_t *list2){
  return NULL;

}

// filter list returning only values that satisfy the filter function
list_t *filter_list(list_t *list, bool (*filter)(list_element_t)){
  return NULL;

}

// returns the length of the list
size_t length_list(list_t *list){
  return 0;

}

// return a list of elements whose values equal the list value transformed by
// the mapping function
list_t *map_list(list_t *list, list_element_t (*map)(list_element_t)){
  return NULL;

}

// folds (reduces) the given list from the left with a function
list_element_t foldl_list(list_t *list, list_element_t initial,
                          list_element_t (*foldl)(list_element_t,
                                                  list_element_t)){
  list_element_t res=0;
  return res;

}

// folds (reduces) the given list from the right with a function
list_element_t foldr_list(list_t *list, list_element_t initial,
                          list_element_t (*foldr)(list_element_t,
                                                  list_element_t)){
  list_element_t res=0;
  return res;

}

// reverse the elements of the list
list_t *reverse_list(list_t *list){
  return NULL;

}

// destroy the entire list
// list will be a dangling pointer after calling this method on it
void delete_list(list_t *list){

} 

Pri preklade sa aj tak vyskytne niekoľko chýb. Je to z toho dôvodu, že prekladač je nastaveý tak aby nepreložil program už pri podozrení na nejakú chybu. V tomto prípade to sú nepoužité premenné. To odstránime v ďalšej práci.

Alokácia dynamického poľa

Začať by ste mali s funkciou, ktorá vytvorí pole.

list_t *new_list(size_t length, list_element_t elements[])

Podľa predpisu by táto funkcia mala vrátiť smerník na novú štruktúru typu list_t. V štruktúre budú uložené informácie o dynamickom poli - jeho začiatok a veľkosť.

Argumenty funkcie sú dáta, ktoré sa majú vložiť do dynamického poľa, zadané adresou a počtom prvkov. Tieto údaje by sme mali nakopírovať do nového poľa.

Najprv si dynamicky vytvoríme novú štruktúru:

list_t* list = (list_t*)malloc(sizeof(list_t) + length * sizeof(list_element_t));

Toto je miesto kde uložíme informácie o novom dynamickom poli. Dynamické pole sa skladá z počtu alokovaných prvkov 'length' a poľa prvkov (elements).

Inicializujeme pole:

list->length = length;

// Nakopírujeme dáta do nového poľa
memcpy(list->elements,elements, length*sizeof(list_element_t));

// Vrátime smerník na alokovanú a inicializovanú pamäť

return list;

Dealokácia dynamického poľa

Každú alokovanú pamäť je potrebné uvoľniť.

free(list);

Pokračuje samostatne

Preložte a otestujte program príkazom make. Doplňte implentáciu do súboru lists_ops.c tak aby vyhovela automatickým testom. Ostatné súbory nemente.

Dbajte o to aby ste nepracovali s nevyhradenou oblasťou. Počet obsadených prvkov musí byť vždy menší ako kapacita dynamického poľa.

Ak chcete vyskúšať zvyšné jednotkové testy, zakomentujte všetky riadky TEST_IGNORE() v súbore test_list_ops.h.

Odovzdanie

Úlohu budete odovzdávať do súboru list_ops.c v adresári cv4 vo Vašom GIT repozitári. Do 14.3., 24:00 za 7 bodov. Na Traktore sa na overenie vykonajú tie isté jednotkové testy.

Previous Post Next Post