{{indexmenu_n>6}}
======== HW 06 - Kruhová fronta ========


^ Termín odevzdání | <wrap important>  14.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 | 
==== Fronta==== 
Fronta je datová struktura, u které jsou definovány operace výběru a vložení prvku. Operace výběr z fronty vybere prvek, který jsme vložili do fronty jako první. Při vkládání prvků do fronty se vkládaná položka vloží na jeho konec. (anglicky enqueue/push a dequeue/pop) Tato struktura se také někdy označuje termínem FIFO (first-in first-out). 

Fronta se dá implementovat polem a to buď polem statické délky s explicitním omezením na počet vložených prvků nebo polem dynamické délky. Alterantivně se dá také realizovat datovou strukturou nazývanou spojový seznam, ale to není v této úloze povolené. Doplňující informace můžete nalézt na  [[https://en.wikipedia.org/wiki/Queue_(abstract_data_type)|Wikipedia - Queue]].

==== Naivní implementace fronty v poli ==== 

Nejjednodušší implementací fronty v poli je ukládání ''i''-tého prvku ve frontě na ''i''-tou pozici v poli. Přidávání nového prvku je velmi snadné. Nicméně vyjímání prvků může tvrvat dlouho, protože (abychom zachovali pořadí) je nutné nejprve vyjmout 1. prvek (z čela) fronty a všechny následující prvky posunout o jednu pozici. **Taková implementace je značně neefektivní pro větší fronty, proto se zpravidla nepoužívá a ani v tomto úkolu nevede na správné řešení.**
==== Kruhová fronta v poli ==== 

{{:courses:b3b36prg:hw:clipboard03.png?250 |}}

Kruhová fronta je efektivní implementace fronty v poli, ve které nedochází k žádnému posouvání prvků při operaci odebírání - ''pop''(). Ve kruhové frontě si můžeme představit, že je alokované pole zacyklené. Nyní již neměníme pozici jednotlivých prvků, ale pouze pohybujeme s ukazateli na začátek a konec oblasti s daty. Při implementaci je potřeba dát pozor speciálně na situaci, kdy je několik prvních prvků ve frontě na konci pole a zbytek je již opět na začátku pole.


===== Povinné zadání ===== 

Implementujte kruhovou frontu v poli (queue.c) podle zadaného hlavičkového souboru (queue.h), ve kterém si vhodně definujte strukturu ''queue_t'' obsahující samotnou frontu. Pokud se vkládaný prvek nevejde do fronty, tak ho nevkládejte a vraťte false ve funkci ''push_to_queue()''. <wrap alert>Odevzdávají se pouze soubory - queue.h a queue.c.</wrap> Abychom mohli správnost řešení vašeho programu otestovat, je nutné implementovat definované rozhraní, tj. zachovat názvy a argumenty zadaných funkcí.

<code c>
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* Queue structure which holds all necessary data */
typedef struct {
   // TODO - Include your data structure here
} queue_t;

/* creates a new queue with a given size */
queue_t* create_queue(int capacity);

/* deletes the queue and all allocated memory */
void delete_queue(queue_t *queue);

/* 
 * inserts a reference to the element into the queue
 * returns: true on success; false otherwise
 */
bool push_to_queue(queue_t *queue, void *data);

/* 
 * gets the first element from the queue and removes it from the queue
 * returns: the first element on success; NULL otherwise
 */
void* pop_from_queue(queue_t *queue);

/* 
 * gets idx-th element from the queue
 * returns the element that will be popped after idx calls of the pop_from_queue() 
 * returns: the idx-th element on success; NULL otherwise
 */
void* get_from_queue(queue_t *queue, int idx);

/* gets number of stored elements */
int get_queue_size(queue_t *queue);

#endif /* __QUEUE_H__ */
</code>

Poznámky:
  * Ve funkci ''delete_queue()'' uvažujeme, že při mazání je fronta již prázdná a není potřeba dealokovat jednotlivé elementy.
  * Funkce ''get_from_queue()'' vrací element, který je ve frontě na indexu idx. Nijak to nesouvisí s vnitřní reprezentací. Neboli na indexu 0 je vždy element na začáteku fronty, který by byl jako první odstraněn funkcí ''pop_from_queue()''.

===== Volitelné zadání =====

Dynamicky měňte velikost alokovaného pole tak, aby fronta využívala adekvátní množství paměti. Je potřeba pole zvětšovat i zmenšovat. Funkce push_to_queue() by se tak měla provést vždy úspěšně a vrátit true, pokud nejde k nějaké výjimečné události. Zvětšovat frontu doporučujeme vždy na dvojnásobek původní velikosti, pokud dojde k zaplnění celé fronty. Zmenšovat doporučujeme vždy na třetinu, když klesne pod tuto hranici. Vyhneme se tak časté změně velikosti.

===== Testování =====

Pro účely testování jsme pro vás připravili jednoduchý testovací program (main.c), který simuluje práci s kruhovou frontou obsahující odkazy (ukazatele) na čísla typu ''int''. Obecně ale může fronta obsahovat ukazatele jakéhokoliv typu a úkolem je napsat obecnou kruhovou frontu. Tato část slouží pouze pro jednodušší testování. Všechny potřebné soubory jsou v archivu {{:courses:b3b36prg:hw:prg-hw06.zip|}}. 

Testovací program očekává na standardním vstupu velikost fronty N. Poté jsou na jednotlivých řádcích pokyny pro simulaci práce se frontou:
  * a value - (push) - Alokuje pamět pro jedno číslo typu ''int'', uloží do něj hodnotu ''value'' a ukazatel na toto číslo vloží na konec fronty zavoláním funkce ''push_to_queue()''.
  * r - (pop) - Zavolá funkci ''pop_from_queue()'' a získá tak ukazatel na první element ve frontě, ze které byl zároveň odstraněn. Vypíše hodnotu čísla, na který odkazuje získaný ukazatel a uvolní jeho paměť.
  * g idx - (get) - Zavolá funkci ''get_from_queue()'' a získá tak ukazatel na element ve frontě na indexu ''idx''. Element nebyl z fronty odstraněn. Následně vypíše hodnotu čísla, na který odkazuje získaný ukazatel.

Na standardním výstupu tento simulátor vypisuje hodnoty pro operace r(pop), g(get). Pokud je dotaz neplatný, vypíše NULL.

<note tip>Podobný způsob testování je použit i v odevzdávacím systému.</note>
/*, kde se navíc kontroluje i správná návratová hodnota funkce ''int get_queue_size(queue_t *queue)'', která vrací aktuální počet prvků ve frontě.*/

=== Příklad 1 - pub01 ====

Vytvoří se kruhová fronta o velikosti 3 a vloží se tam ukazatele na tři celá čísla (1,2,3). Následně se prvky z fronty odstraní pomocí operace r-pop. Následně by fronta měla být prázdná.

^  Standardní vstup  ^  Očekávaný výstup  ^  Očekávaný chybový výstup  ^  Návratová hodnota  ^
| <code c>
3
a 1
a 2
a 3
r
r
r
r
</code> | <code c>
1
2
3
NULL
</code> |  žádný  |  0  |


=== Příklad 2 - pub02 ===

^  Standardní vstup  ^  Očekávaný výstup  ^  Očekávaný chybový výstup  ^  Návratová hodnota  ^
| <code c>
3
a 1
g -1
g 0
g 1
r
</code> | <code java>
NULL
1
NULL
1
</code> |  žádný  |  0  |

(Další příklady jsou v poskytnutém archivu.)
===== Testování v BRUTE =====

Pro některé testy v BRUTE nejsou použity vstupní soubory popsané v předchozí sekci, ale vámi implementované funkce jsou volány přímo ze zdrojového kódu. Je to proto, že by vstupní soubory byly příliš velké a hodnocení by trvalo zbytečně dlouho. Jednotilivé testy fungují následovně:((Doplněno 07. 12. 207))

=== Man03 ===

  - Vytvoří se fronta o velikosti 100
  - Vloží se cca 90 elementů (push)
  - Vyjmou se všechny elementy (pop) a zkontroluje se jejich pořadí
  - Zkontroluje se, že je fronta prázdná (funkce get_queue_size() vrací nulu)

=== Man04 ===

  - Vytvoří se fronta o velikosti 100
  - Zaplní se přibližně do poloviny
  - Vloží se vždy jeden prvek a jeden se odstraní. Zkontroluje se přitom návratová hodnota a hodnota navráceného elementu (pomocí pop). Tento krok se provede 100000-krát.
  - Vyprázdní se zbytek fronty

=== Man05 ===

  - Vytvoří se několik front
  - Částečně se zaplní (push)
  - Vyprázdní se a zkontroluje se jejich obsah (pop)
  - Zkontroluje se, že jsou všechny fronty prázdná (funkce get_queue_size() vrací nulu)
  
=== Opt01 ===

  - Vytvoří se fronta o velikosti 100
  - Vloží se přibližně 1000000 elementů (push)
  - Zkontroluje se obsah (get)
  - Fronta se vyprázdní (pop)
  - Zkontroluje se, že je fronta prázdná (funkce get_queue_size() vrací nulu)
  
=== Opt02 ===

  - Vytvoří se 100 front o iniciální velikosti 10
  - Každá fronta se naplní N elementy a ihned následně vyprázdní
  - Kontroluje se tak správné uvolňování paměti

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

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

^  ^  Povinné zadání  ^  Volitelné zadání  ^
^ Název v BRUTE |  HW06  ||
^ Odevzdávané soubory |  queue.h, queue.c  ||
^ Kompilace pomocí |  clang -pedantic -Wall -Werror -std=c99 ||
^ Očekávaná amortizovaná časová složitost ((pro jednu operaci push, pop a get.)) |  $\mathcal{O}(1)$  |  $\mathcal{O}(1)$  |