/* ******************************* c203.c *********************************** */
/*  Předmět: Algoritmy (IAL) - FIT VUT v Brně                                 */
/*  Úkol: c203 - Fronta znaků v poli                                          */
/*  Referenční implementace: Petr Přikryl, 1994                               */
/*  Přepis do jazyka C: Václav Topinka, září 2005                             */
/*  Úpravy: Bohuslav Křena, říjen 2014                                        */
/* ************************************************************************** */
/*
** Implementujte frontu znaků v poli. Přesnou definici typů naleznete
** v hlavičkovém souboru c203.h (ADT fronta je reprezentována strukturou tQueue,
** která obsahuje pole 'arr' pro uložení hodnot ve frontě a indexy f_index
** a b_index. Všechny implementované funkce musí předpokládat velikost pole
** QUEUE_SIZE, i když ve skutečnosti jsou rozměry statického pole definovány
** MAX_QUEUE. Hodnota QUEUE_SIZE slouží k simulaci fronty v různě velkém poli
** a nastavuje se v testovacím skriptu c203-test.c před testováním
** implementovaných funkcí. Hodnota QUEUE_SIZE může nabývat hodnot v rozsahu
** 1 až MAX_QUEUE.
**
** Index f_index ukazuje vždy na první prvek ve frontě. Index b_index
** ukazuje na první volný prvek ve frontě. Pokud je fronta prázdná, ukazují
** oba indexy na stejné místo. Po inicializaci ukazují na první prvek pole,
** obsahují tedy hodnotu 0. Z uvedených pravidel vyplývá, že v poli je vždy
** minimálně jeden prvek nevyužitý.
**
** Při libovolné operaci se žádný z indexů (f_index i b_index) nesnižuje
** vyjma případu, kdy index přesáhne hranici QUEUE_SIZE. V tom případě
** se "posunuje" znovu na začátek pole. Za tímto účelem budete deklarovat
** pomocnou funkci NextIndex, která pro kruhový pohyb přes indexy pole
** využívá operaci "modulo".
**
** Implementujte následující funkce:
**
**    nextIndex ..... pomocná funkce - viz popis výše
**    queueInit ..... inicializace fronty
**    queueEmpty .... test na prázdnost fronty
**    queueFull ..... test, zda je fronta zaplněna (vyčerpána kapacita)
**    queueFront .... přečte hodnoty prvního prvku z fronty
**    queueRemove ... odstraní první prvek fronty
**    queueGet ...... přečte a odstraní první prvek fronty
**    queueUp ....... zařazení prvku na konec fronty
**
** Své řešení účelně komentujte!
**
** Terminologická poznámka: Jazyk C nepoužívá pojem procedura.
** Proto zde používáme pojem funkce i pro operace, které by byly
** v algoritmickém jazyce Pascalovského typu implemenovány jako
** procedury (v jazyce C procedurám odpovídají funkce vracející typ void).
**
**/

#include "c203.h"

void queueError (int error_code) {
/*
** Vytiskne upozornění na to, že došlo k chybě.
** Tato funkce bude volána z některých dále implementovaných operací.
**
** TUTO FUNKCI, PROSÍME, NEUPRAVUJTE!
*/
    static const char* QERR_STRINGS[MAX_QERR+1] = {"Unknown error","Queue error: UP","Queue error: FRONT","Queue error: REMOVE","Queue error: GET","Queue error: INIT"};
    if ( error_code <= 0 || error_code > MAX_QERR )
        error_code = 0;
    printf ( "%s\n", QERR_STRINGS[error_code] );
    err_flag = 1;
}

void queueInit (tQueue* q) {
/*
** Inicializujte frontu následujícím způsobem:
** - všechny hodnoty v poli q->arr nastavte na '*',
** - index na začátek fronty nastavte na 0,
** - index prvního volného místa nastavte také na 0.
**
** V případě, že funkce dostane jako parametr q == NULL, volejte funkci
** queueError(QERR_INIT).
*/

    if (q == NULL)                  /* Pokud je seznam q == NULL, vrátíme požadovanou chybu */
        queueError(QERR_INIT);
    else
    {
        for (int I = 0; I < QUEUE_SIZE; I++)        /* Projdeme celý seznam a postupně přiřadíme na všechny pozice '*' */
        {
            q->arr[I] = '*';
        }

        q->f_index = 0;                 /* Index na začátek fronty nastavíme na nulu */
        q->b_index = 0;                 /* Index na první volné místo nastavíme též na nulu */
    }
}

int nextIndex (int index) {
/*
** Pomocná funkce, která vrací index následujícího prvku v poli.
** Funkci implementujte jako jediný prikaz využívající operace '%'.
** Funkci nextIndex budete využívat v dalších implementovaných funkcích.
*/

    return ((index + 1) % QUEUE_SIZE);
}

int queueEmpty (const tQueue* q) {
/*
** Vrací nenulovou hodnotu, pokud je frona prázdná, jinak vrací hodnotu 0.
** Funkci implementujte jako jediný příkaz.
*/

    /* Použil jsem ternární operátory */
    /* Pokud se pozice prvního prvku rovná zároveň pozici prvního prázdného místa, je seznam prázdný */
    return ((q->f_index == q->b_index) ? 1 : 0);
}

int queueFull (const tQueue* q) {
/*
** Vrací nenulovou hodnotu, je-li fronra plná, jinak vrací hodnotu 0.
** Funkci implementujte jako jediný příkaz s využitím pomocné funkce nextIndex.
*/

    /* Použil jsem ternární operátory */
    /* Pokud další index prvního volného prvku se rovná zároveň prvnímu prvku, je fronta plná */
    /* Jde o to, že fronta se na posledním místě odkáže zpět na první místo */
    return (nextIndex(q->b_index) == q->f_index) ? 1 : 0;
}

void queueFront (const tQueue* q, char* c) {
/*
** Prostřednictvím parametru c crátí znak ze začátku fronty q.
** Pokud je fronta prázdná, ošetřete to voláním funkce queueError(QERR_FRONT).
** Volání této funkce při prázdné frontě je vždy nutné považovat za nekorektní.
** Bývá to totiž důsledek špatného návrhu algoritmu, ve kterém je fronta
** použita. O takové situaci se proto musí programátor-vývojář dozvědět.
** V opačném případě je ladění programů obtížnější!
**
** Při implementaci využijte dříve definované funkce queueEmpty.
*/
    /* Pokud je fronta prázdná, vrátíme požadované chybové hlášení */
    if (queueEmpty(q))
        queueError(QERR_FRONT);
    /* Vrátíme znak, který se nacházím na začátku fronty */
    else
        *c = q->arr[q->f_index];
}

void queueRemove (tQueue* q) {
/*
** Odstraní znak ze začátku fronty q. Pokud je fronta prázdná, ošetřete
** vzniklou chybu voláním funkce queueError(QERR_REMOVE).
** Hodnotu na uvolněné pozici ve frontě nijak neošetřujte (nepřepisujte).
** Při implementaci využijte dříve definované funkce queueEmpty a nextIndex.
*/

    /* Pokud je fronta prázdná, vrátíme požadované chybové hlášení */
    if (queueEmpty(q))
        queueError(QERR_REMOVE);
    /* Odstraníme znak ze začátku fronty, ale tento znak nebude přímo odstraněnt, spíše se pouze posuneme */
    else
        q->f_index = nextIndex(q->f_index);
}

void queueGet (tQueue* q, char* c) {
/*
** Odstraní znak ze začátku fronty a vrátí ho prostřednictvím parametru c.
** Pokud je fronta prázdná, ošetřete to voláním funkce queueError(QERR_GET).
**
** Při implementaci využijte dříve definovaných funkcí queueEmpty,
** queueFront a queueRemove.
*/
    /* Pokud je fronta prázdná, vrátíme požadované chybové hlášení */
    if (queueEmpty(q))
        queueError(QERR_GET);
    /* Vrátíme první znak z fronty do proměnné c a následně tento první znak vymažeme */
    else
    {
        queueFront(q, c);
        queueRemove(q);
    }
}

void queueUp (tQueue* q, char c) {
/*
** Vloží znak c do fronty. Pokud je fronta plná, ošetřete chybu voláním
** funkce queueError(QERR_UP). Vkládání do plné fronty se považuje za
** nekorektní operaci. Situace by mohla být řešena i tak, že by operace
** neprováděla nic, ale v případě použití takto definované abstrakce by se
** obtížně odhalovaly chyby v algoritmech, které by abstrakci využívaly.
**
** Při implementaci využijte dříve definovaných funkcí queueFull a nextIndex.
*/
    /* Pokud je fronta plná, vrátíme požadované chybové hlášení */
    if (queueFull(q))
        queueError(QERR_UP);
    /* Vložíme znak na první volné místo ve frontě a posuneme index volného místa o jeden dále */
    else
    {
        q->arr[q->b_index] = c;
        q->b_index = nextIndex(q->b_index);
    }
}
/* Konec příkladu c203.c */