{{indexmenu_n>7}}
======== HW 07 - Fronta spojovým seznamem s řazením ========


^ Termín odevzdání | <wrap important>  21.04.2018 23:59 PDT</wrap> (([[https://www.timeanddate.com/time/zones/pst|PDT]]))|
^ Povinné zadání |  2b |
^ Volitelné zadání |  <wrap tip>2b</wrap>|
^ Bonusové zadání |   Není |
^ Počet uploadů |  20 | 

=====  Povinné zadaní ===== 

Cílem úlohy je seznámit se se strukturou spojového seznamu a procvičit si dynamickou alokaci. Nejdříve je úkolem implementovat datovou strukturu realizující frontu spojovými seznamem pro uložení celých čísel typu ''int''. Spojový seznam bude uložen v globálních proměnných, a proto nebude možné vytvořit více instancí spojového seznamu. Datová struktura fronty poskytuje rozhraní: 
  * Funkce ''push()'' vloží prvek na konec fronty
  * Funkce ''pop()'' vyjme prvek z čela fronty
  * Funkce ''insert()'' vloží prvek před nejbližší menší prvek ve frontě směr od čela fronty na její konec. V případě shodné hodnoty prvků, je nový prvek vložen před první takový prvek fronty. V případě, že žádné takové prvky ve frontě nejsou, je prvek zařazen na konec fronty. Jeli hodnota prvku nejvyšší číslo ve frontě, je prvek umístěn do čela fronty.
  * Funkce ''erase()'' smaže všecny prvky ve frontě jejichž hodnota je identická s hodnotu předávaného prvku. 
  * Funkce ''getEntry()'' vrací hodnotu prvku ve frontě na pozici ''idx'' 
  * Funkce ''size()'' vrací aktuální počet prvků ve frontě.
  * Funkce ''clear()'' smaže všechny prvky ve frontě.

<note important>Abychom při volání funkce ''pop()'' mohli z návratové hodnoty rozlišit, že je fronta prázdná, povolujeme vkládání pouze nezáporných hodnot. Záporná návratová hodnota funkce ''pop()'' a podobně též ''getEntry()'' indikuje, že je fronta prázdná nebo prvek na dané pozici není. Alternativním řešením může být předávání ukazatele pro vyplnění příznaku chyby nebo ukončení program. Pro jednoduchost a přehlednost programu je zvoleno řešení se zápornou hodnotou.</note>

**Spojový seznam implementujte v souboru ''linked_list.c'' s rozhraním definovaným v souboru ''linked_list.h''**.

<note tip>Datovou strukturu pro spojový seznam definujte v souboru ''linked_list.c'' jako modulovou "globální" proměnnou, kterou při deklaraci řádně incializujte.</note>

==== Rozhraní definované v souboru ''linked_list.h'' ====

<code c>
/*
 * Push the entry value to the queue. The value of the entry must be >= 0.
 * return: true on success and false otherwise.
 */
_Bool push(int entry);

/*
 * Pop an entry from the head of the queue
 * return: the stored int value or value less than 0 indicating the queue is empty
 */
int pop(void);

/*
 * Insert the given entry to the queue in the InsertSort style.
 *
 * Since push and insert functions can be combined, it cannot be 
 * guaranteed, the internal structure of the queue is always sorted.
 *
 * The expected behaviour is that insert proceeds from the head of
 * the queue to the tail in such a way that it is insert before the entry 
 * with the lower value, i.e., it becomes a new head if its value is the
 * new maximum or a new tail if its value is a new minimum of the values
 * in the queue.
 *
 * return: true on success; false otherwise
 */
_Bool insert(int entry);

/*
 * Erase all entries with the value entry, if such exists
 * return: true on success; false to indicate no such value has been removed
 */
_Bool erase(int entry);

/*
 * For idx >= 0 and idx < size(queue), it returns the particular item
 * stored at the idx-th position of the queue. The head of the queue
 * is the entry at idx = 0.
 *
 * return: the particular value of the entry at the idx-th position or
 * value less than 0 to indicate the requested position is not presented
 * in the queue 
 */
int getEntry(int idx);

/*
 * return: the number of stored items in the queue
 */
int size(void);

/*
 * Remove all entries in the linked list
 */
void clear();
</code>
===== Volitelné zadání =====

Volitelné zadání generalizuje datovou strukturu pro ukládání obecného datového typu předávaného jako ukazatel na ''void*'' a také zobecňuje použití fronty nikoliv jako globální proměnné, ale jako nově vytvářené datové struktury. Proto jsou pro práci s frontou předepsány funkce:

  * ''create()''      - alokuje potřebnou navrženou datovou strukturu pro uložení spojového seznamu a příslušných proměnných.
  * ''clear()''       - uvolní paměť datové struktury pro spojový seznam a případně uvolní paměť všech vložených datových položek do spojového seznamu.
  * ''setClear()''   - umožňuje nastavit funkci pro uvolnění paměti jednotlivé datové položky ukládané do spojového seznamu
  * ''setCompare()'' - umožňuje nastavit funkci pro porovnání dvou datových položek //dat1// a //dat2//

Samotné rozhraní pro práci s frontou je podobné předchozímu případu jen s tím rozdílem, že funkce:

  * ''insert()'' vloží prvek před první prvek, pro který platí že porovnání prvků funkcí ''compare()''(nový prvek, nějaký prvek fronty) má návratovou hodnotou 1 nebo 0 indikující, že vkládaný prvek je větší než prvek fronty. V případě shody prvků indikované nulovou návratovou hodnotou funkce ''compare()'' je prvek vložen před první takový prvek fronty. V případě, že žádné takové prvky ve frontě nejsou, je prvek zařazen na konec fronty. Máli vkládaný prvek nejvyšší hodnotou  (dle funkce ''compare()'' ) je umístěn do čela fronty. Jeli jeho hodnota naopak nejmenší, je umístěn na konec fronty, tj. bude odebrán z fronty funkcí ''pop()'' jako poslední.

**Spojový seznam pro ukládání obecného datového typu implementujte v souboru ''queue.c'' s rozhraním definovaným v souboru ''queue.h''**.

==== Rozhraní definované v ''souboru queue.h'' ====

<code c>
/* 
 * Allocate a new queue structure or return NULL on an error.
 * Particular type is implementation dependent
 */
void* create();
 
/*
 * Release all memory accessible from the queue, i.e., all dynamic
 * data entries stored in the individual queue entries. The clear 
 * function must be properly set, see setClear() below.
 */
void clear(void *queue);
 
/*
 * Push the given item into the queue. The pointer to the entry
 * should not be NULL, i.e., storing NULL entries is not allowed.
 * return: true on success and false otherwise.
 */
_Bool push(void *queue, void *entry);
 
/*
 * Pop an entry from the head of the queue
 * return: the stored pointer to the entry or NULL if the queue is empty
 */
void* pop(void *queue);
 
/*
 * Insert the given entry to the queue in the InsertSort style using 
 * the set compare function (by the setCompare() ). If such a function
 * is not set or an error occurs during the insertion it returns false.
 *
 * Since push and insert functions can be combined, it cannot be 
 * guaranteed, the internal structure of the queue is always sorted.
 *
 * The expected behaviour is that insert proceeds from the head of
 * the queue to the tail in such a way that it is insert before the entry
 * with the lower value, i.e., it becomes a new head if its value is the
 * new maximum or a new tail if its value is a new minimum of the values
 * in the queue.
 *
 * return: true on success; false otherwise
 */
_Bool insert(void *queue, void *entry);

/*
 * Erase all entries with the value entry, if such exists
 * return: true on success; false to indicate no such value has been removed
 */
_Bool erase(void *queue, void *entry);
 
/*
 * For idx >= 0 and idx < size(queue), it returns the particular item
 * stored at the idx-th position of the queue. The head of the queue
 * is the entry at idx = 0.
 *
 * return: pointer to the stored item at the idx position of the queue
 * or NULL if such an entry does not exists at such a position
 */
void* getEntry(const void *queue, int idx);
 
/*
 * return: the number of stored items in the queue
 */
int size(const void *queue);
 
/*
 * Set a pointer to function for comparing particular inserted items
 * to the queue. It is similar to the function used in qsort, see man qsort:
 * "The comparison function must return an integer less than, equal to, or
 * greater than zero if the first argument is considered to be respectively
 * less than, equal to, or greater than the second."
 */
void setCompare(void *queue, int (*compare)(const void *, const void *));
 
/*
 * Set a pointer to function which can properly delete the inserted 
 * items to the queue. If it is not set, all the items stored in the
 * queue are deleted calling standard free() in the clear() 
 */
void setClear(void *queue, void (*clear)(void *));
</code>
===== Odevzdávané soubory =====

Odevzdávejte pouze soubory linked_list.c a queue.c s implementací fronty int hodnot a obecné fronty. Všechny soubory uložte přímo do zip archivu a **nevytvářejte žádné složky**.  Správnost implementace bude ověřena testovacím programem, který bude využívat odezdané implementace fronty hodnot int a obecné fronty implementované spojovým seznamem.

**<fc #ff0000>Povinné soubory</fc>**:

  * ''linked_list.c'' - implementace rozhraní pro práci se spojovým seznamem hodnot typu ''int'' z poviného zadání

**<fc #008080>Soubory volitelného zadání</fc>**:

  * ''queue.c'' - implementace rozhraní pro práci s frontou implementovanou spojovým seznamem obecných hodnot (typu ''void*'') dle výše uvedeného rozhraní ''queue.h''.

===== Způsob testování =====

Pro jednodušší testování jsme připravili testovací programy, které načtou požadované operace ze standartního vstupu, interpretují je a vypíší vyýsledek. Zatímco v povinné části se pracuje pouze s celými čísly, tak fronta z volitelné části může obsahovat libovolná data. Proto jsme pro volitelnou část připravili hned 3 implementace spolu s odpovídajícími veřejnými příklady:

  * opt-int -- data obsahují celá čísla (obdoba povinné části)
  * opt-str -- data obsahují textové řetěžce
  * opt-stc -- data obsahují strukturu složenou z jednoho celého čísla a jednoho textového řetězce

====== Odevzdání a hodnocení ======

Veřejné příklady + Makefile: {{:courses:b3b36prg:hw:prg-hw07.zip|}}

^  ^  Povinné zadání  ^  Volitelné zadání  ^
^ Název v BRUTE |   HW07  ||
^ Odevzdávané soubory |  linked_list.c  |  queue.c  |
^ Argumenty při spuštění |  žádné  	  ||
^ Kompilace  |  clang -pedantic -Wall -Werror -std=c99  ||
^ Procvičované oblasti |  dynamická alokace paměti \\ práce s ukazately  |  ukazatele na funkce |