HW3: Todo
Odevzdávání částí A a B je ukončeno.
Autor zadání Dávid Šutor
Odevzdávané soubory src/*
Konec odevzdání části A 2026-03-30 24:00
Konec odevzdání části B 2026-04-29 24:00
Kostru k úkolu nelze stáhnout

Predstavenie úlohy

V tejto úlohe navrhnete a implementujete malú knižnicu na správu zoznamu úloh. Kolegovia vo firme si totiž žiadali „jednoduchý interný todo list“, čo je tradične prvý krok k tomu, aby z neho časom vznikol kritický systém. Kým sa tak stane, stačí rozumne navrhnutá knižnica s presne definovaným správaním.

Verejné rozhranie knižnice máte špecifikované. Vnútornú reprezentáciu dát si však navrhnete sami.

Prvá časť (A)

Knižnica bude spravovať úlohy v dvoch stavoch:

  • pending – úloha ešte nie je dokončená,

  • done – úloha je dokončená.

Každá úloha má tieto atribúty:

  • task_id – identifikátor úlohy,

  • desc – textový popis úlohy,

  • due – termín úlohy reprezentovaný celým nezáporným číslom,

  • stav pending alebo done.

Okrem toho má každá pending úloha aj hodnotu pending_number, ktorá slúži ako číslo vhodné na výpis alebo ovládanie z používateľského rozhrania.

Opaque kontext

Typ todo_context predstavuje celú inštanciu zoznamu úloh. Používateľ knižnice nepozná jeho vnútornú reprezentáciu a môže s ním pracovať iba cez verejné funkcie.

typedef struct context todo_context;

todo_context *todo_create();
void todo_destroy(todo_context *ctx);

Funkcia todo_create() vytvorí nový prázdny kontext a vráti ukazovateľ naň. Ak sa kontext nepodarí vytvoriť, vráti nullptr.

Funkcia todo_destroy() uvoľní všetku pamäť patriacu kontextu. Ak je ctx == nullptr, funkcia neurobí nič.

Identifikátor úlohy

typedef uint64_t task_id;

Hodnota typu task_id predstavuje identifikátor konkrétnej úlohy. Platí, že medzi aktuálne existujúcimi úlohami v jednom kontexte nemajú dve rôzne úlohy rovnaké task_id. Hodnota 0 nie je platný identifikátor a používa sa na signalizáciu chyby.

Nie je potrebné, aby task_id bolo malé alebo používateľsky prívetivé číslo. Je to identifikátor určený pre API knižnice, nie pre koncového používateľa.

Pridávanie úloh

task_id todo_add_task(todo_context *ctx, const char *desc, unsigned due);

Funkcia pridá novú pending úlohu s popisom desc a termínom due.

  • desc je textový reťazec, ktorého obsah si knižnica musí skopírovať, teda sa nesmie spoliehať na to, že volajúci ponechá pôvodný reťazec platný,

  • due je číselný termín úlohy,

  • due == 0 znamená, že úloha nemá termín.

Návratová hodnota je task_id novej úlohy. Ak sa úlohu nepodarí vytvoriť, funkcia vráti 0.

Zmena stavu a odstránenie úlohy

bool todo_mark_done(todo_context *ctx, task_id id);
bool todo_remove_task(todo_context *ctx, task_id id);

Funkcia todo_mark_done() označí existujúcu pending úlohu ako done. Ak už je úloha hotová, alebo nastane očakávateľná chyba, funkcia vráti false. Inak vráti true.

Funkcia todo_remove_task() úlohu natrvalo odstráni. Odstránená úloha sa už viac nesmie objaviť pri iterácii. Pri očakávateľnej chybe vráti funkcia false. Inak vráti true.

Ak funkcie dostanú nevalidný task_id, tak správanie je nedefinované.

To čo sa považuje za očakávateľnú chybu u týchto funkcií závisí od vašej implementácie.

Gettery

const char *todo_task_get_desc(todo_context *ctx, task_id id);
unsigned todo_task_get_due(todo_context *ctx, task_id id);

Tieto funkcie vracajú atribúty úlohy identifikovanej hodnotou task_id. Volania týchto getterov by mali byť rozumne efektívne.

Priorita a poradie úloh

Úlohy sa pri iterácii usporadúvajú prioritne vzostupne. Priorita sa určuje podľa nasledujúcich pravidiel:

  1. úloha s menším due má vyššiu prioritu,

  2. úloha s due == 0 má najnižšiu prioritu,

  3. ak majú dve úlohy rovnaké due, skôr ide tá, ktorá bola pridaná skôr.

Inými slovami, úlohy sú zoradené vzostupne podľa dvojice (due, poradie pridania), pričom due == 0 sa považuje za najväčšiu možnú hodnotu.

Úlohy done sú zoradené medzi sebou iba podľa poradia pridania a sú až za pending.

Iterácia

enum todo_filter
{
    TODO_FILTER_PENDING,
    TODO_FILTER_ALL,
};

typedef void (*todo_iter_fn)(todo_context *ctx, task_id id, uint64_t pending_number);

void todo_iter_tasks(todo_context *ctx, todo_iter_fn fn, enum todo_filter filter, size_t limit);

Funkcia todo_iter_tasks prejde úlohy v poradí popísanom vyššie a pre každú navštívenú úlohu zavolá callback fn.

Parameter filter určuje, ktoré úlohy sa majú navštíviť:

  • TODO_FILTER_PENDING – iba úlohy v stave pending,

  • TODO_FILTER_ALL – všetky úlohy, teda pending aj done.

Parameter limit určuje maximálny počet navštívených úloh. Ak je limit == 0, počet navštívených úloh nie je obmedzený.

Hodnota pending_number má tento význam:

  • pri pending úlohe je to jej poradové číslo medzi všetkými pending úlohami,

  • tieto čísla vždy tvoria súvislý rozsah od 1 po počet pending úloh, pričom platí, že pending úloha s číslom 1 bola vložená pred úlohou s číslom 2, atď.,

  • pri iterácii s TODO_FILTER_ALL dostane callback pre done úlohu hodnotu 0.

Ak sa pending úloha označí ako done alebo odstráni, pri ďalšom volaní todo_iter_tasks() musia byť pending_number ostatných pending úloh znovu také, ako je napísané vyššie.

Volanie todo_iter_tasks musí mať časovú zložitosť $O(min(\text{limit}, n))$, kde $n$ je počet úloh. Teda nemala by sa tu prepočítavať priorita s každým volaním.

Príklad

Nech v prázdnom kontexte postupne pridáte tieto úlohy:

task_id a = todo_add_task(ctx, "Nakrmit rybicky", 5);
task_id b = todo_add_task(ctx, "Kupit rybicky", 2);
task_id c = todo_add_task(ctx, "Navstivit tvoju mamku", 0);

Potom budú úlohy pri iterácii zoradené takto:

  1. b – má najmenšie due s pending_number == 2,

  2. a – má väčšie due s pending_number == 1, keďže bola vložená ako prvá,

  3. c – nemá termín, preto ide až na koniec s pending_number == 3.

Ak následne zavoláte todo_mark_done(ctx, b), potom:

  • pri TODO_FILTER_PENDING sa budú iterovať už len úlohy a, c,

  • ich pending_number budú postupne 1, 2,

  • pri TODO_FILTER_ALL sa objavia všetky tri úlohy v poradí a, c, b, pričom callback dostane pre b hodnotu pending_number == 0.

Druhá časť (B)

Knižnica si získala obľubu a kolegovia začali požadovať pokročilejšie funkcie. Nestačí už len termín a popis. Ľudia chcú vyjadriť, ako veľmi im na úlohe záleží, kedy má byť úloha vôbec viditeľná, a predovšetkým: niektoré úlohy jednoducho nemôžu začať skôr, než sú dokončené iné.

V druhej časti preto rozhranie rozšírime o:

  • atribút naliehavosti (urgency), ktorý ovplyvňuje poradie pending úloh,

  • atribút podmienky zobrazenia (after), ktorý skryje úlohu až do zadaného okamihu,

  • závislosti medzi úlohami, ktoré vynucujú poradie ich spracovania.

Pôvodné funkcie prvej časti zostávajú k dispozícii, sú však označené ako [[deprecated]]. Ich správanie je zachované a je ekvivalentné volaniu nových funkcií s hodnotami after = 0 a urgency = TODO_URGENCY_NONE. Podrobnosti sú uvedené pri každej novej funkcii.

Nové dátové typy

Štruktúra todo_task_view

struct todo_task_view {
    const char      *description;
    unsigned         due;
    unsigned         after;
    enum todo_urgency urgency;
};

Štruktúra todo_task_view zoskupuje všetky atribúty úlohy do jednej hodnoty. Používa sa pri pridávaní úloh aj pri ich čítaní.

  • description – textový popis úlohy; knižnica si ho interne skopíruje, volajúci nemusí udržiavať pôvodný reťazec platný,

  • due – termín úlohy; due == 0 znamená, že úloha nemá termín,

  • after – minimálny čas, od ktorého je úloha viditeľná pri iterácii; podrobnosti viď Atribút after a iterácia s časom,

  • urgency – naliehavosť úlohy; podrobnosti viď Naliehavosť a nové zoraďovanie.

Výčtový typ todo_urgency

enum todo_urgency {
    TODO_URGENCY_NONE,
    TODO_URGENCY_LOW,
    TODO_URGENCY_MEDIUM,
    TODO_URGENCY_HIGH,
};

Hodnoty sú zoradené od najnižšej po najvyššiu naliehavosť:

Hodnota Význam

TODO_URGENCY_NONE

Bez naliehavosti (predvolená hodnota)

TODO_URGENCY_LOW

Nízka naliehavosť

TODO_URGENCY_MEDIUM

Stredná naliehavosť

TODO_URGENCY_HIGH

Vysoká naliehavosť

Pridávanie úloh — todo_v2_add_task

task_id todo_v2_add_task(todo_context *ctx, struct todo_task_view task);

Funkcia pridá novú pending úlohu so všetkými atribútmi zadanými v štruktúre task. Návratová hodnota je task_id novej úlohy, alebo 0 ak sa úlohu nepodarilo vytvoriť, alebo ak sú vstupné hodnoty neplatné.

Platí nasledujúca validácia atribútu after:

  • ak due != 0, musí platiť after <= due; v opačnom prípade funkcia vráti 0 a kontext zostane nezmenený,

  • ak due == 0 (úloha bez termínu), hodnota after môže byť ľubovoľná.

Getter — todo_get_task

struct todo_task_view todo_get_task(todo_context *ctx, task_id id);

Funkcia vráti všetky atribúty úlohy identifikovanej hodnotou id naraz, ako vyplnenú štruktúru todo_task_view. Platí, že pole description ukazuje na interne spravovaný reťazec; volajúci ho nesmie uvoľniť ani modifikovať, a jeho platnosť zanikne po akomkoľvek volaní, ktoré môže úlohu zmeniť alebo odstrániť.

Naliehavosť a nové zoraďovanie

Atribút urgency je primárnym kritériom zoradenia pending úloh. Úlohy sú teraz zoradené podľa nasledujúcich pravidiel (v tomto poradí):

  1. Úloha s vyššou naliehavosťou (urgency) ide skôr.

  2. Pri rovnakej naliehavosti ide skôr úloha s menším due; due == 0 sa považuje za najväčšiu možnú hodnotu (teda ide ako posledná v rámci rovnakej naliehavosti).

  3. Pri rovnakej naliehavosti aj due rozhoduje poradie pridania, skôr pridaná úloha ide skôr.

Zoraďovanie done úloh zostáva nezmenené, sú zoradené výhradne podľa poradia pridania, atribút urgency sa na ne nevzťahuje.

Atribút after a iterácia s časom

Atribút after

Hodnota after určuje minimálny čas, od ktorého je úloha viditeľná pri iterácii. Úloha existuje v kontexte od okamihu svojho pridania a má pridelené pending_number bez ohľadu na hodnotu after. Atribút after nemá žiadny vplyv na poradie úloh ani na prideľovanie pending_number. Ovplyvňuje výlučne to, či je úloha odovzdaná callbacku počas iterácie.

todo_v2_iter_tasks

void todo_v2_iter_tasks(todo_context *ctx, todo_iter_fn fn, enum todo_filter filter,
                        size_t limit, unsigned current_time);

Funkcia sa správa rovnako ako todo_iter_tasks z prvej časti, s tým rozdielom, že pri iterácii preskočí každú úlohu, pre ktorú platí after > current_time. Parametre filter a limit majú rovnaký význam ako v todo_iter_tasks.

Deprecated funkcia todo_iter_tasks(ctx, fn, filter, limit) je ekvivalentná volaniu todo_v2_iter_tasks s current_time = 0.

Závislosti

Koncept

Závislosť medzi úlohami vyjadruje, že jedna úloha nemôže byť spracovaná skôr, než je dokončená iná. Ak zavoláte todo_add_dependency(ctx, a, b), hovoríte: "úloha a závisí od úlohy b "; pri iterácii sa a musí objaviť až po b.

Závislosť môže existovať iba medzi dvoma pending úlohami.

Závislosti sú tranzitívne: ak a závisí od b a b závisí od c, potom a musí byť v zozname až za c, a to aj bez toho, aby ste explicitne pridali závislosť a → c.

Pridávanie závislostí — todo_add_dependency

bool todo_add_dependency(todo_context *ctx, task_id id, task_id dependency);

Funkcia zaregistruje závislosť: úloha id závisí od úlohy dependency. Po úspešnom zavolaní sa id vo výpise objaví až po dependency.

Funkcia vráti false (a kontext zostane nezmenený) ak:

  • niektorá z úloh je v stave done,

  • id == dependency (seba-závislosť nie je povolená),

  • závislosť medzi id a dependency už existuje,

  • pridanie závislosti by vytvorilo cyklus, priamy (b → a pri existujúcom a → b) alebo tranzitívny (a → b → c a pokus o c → a).

Vo všetkých ostatných prípadoch vráti true.

Odoberanie závislostí — todo_remove_dependency

bool todo_remove_dependency(todo_context *ctx, task_id id, task_id dependency);

Funkcia odoberie skôr zaregistrovanú závislosť medzi id a dependency. Po úspešnom odobratí sa id môže v zozname presunúť na skoršiu pozíciu, ak to jeho prirodzená priorita umožňuje.

Funkcia vráti false ak:

  • niektorá z úloh je v stave done,

  • závislosť medzi id a dependency neexistuje.

Vo všetkých ostatných prípadoch vráti true.

Poradie po pridaní závislosti

Po pridaní závislosti a → b sa a umiestni na neskôr z dvoch pozícií:

  • prirodzená prioritná pozícia: miesto, kde by a stálo bez závislostí podľa pravidiel urgency → due → poradie pridania,

  • pozícia za posledným predkom: bezprostredne za poslednou z úloh, od ktorých a tranzitívne závisí (teda za tou z nich, ktorá stojí v zozname najneskoršie).

Ak je prirodzená pozícia a už za všetkými jeho predkami, poradie sa nezmení.

Životný cyklus závislostí

Závislosti existujú iba medzi pending úlohami. Keď je úloha b označená ako done (volaním todo_mark_done) alebo natrvalo odstránená (volaním todo_remove_task), nastanú automaticky tieto udalosti:

  1. Úloha b je vymazaná zo zoznamov závislostí všetkých pending úloh, ktoré od nej záviseli.

  2. Každá takto dotknutá úloha sa môže presunúť na skoršiu pozíciu v zozname, podľa svojej prirodzenej priority a zostávajúcich závislostí.

  3. Vlastný zoznam závislostí úlohy b je vyčistený.

Volajúci teda nemusí pred todo_mark_done alebo todo_remove_task manuálne odoberať závislosti.

Iterácia závislostí — todo_iter_deps

typedef void (*todo_dep_iter_fn)(todo_context *ctx, task_id dependency);

void todo_iter_deps(todo_context *ctx, task_id id, todo_dep_iter_fn fn);

Funkcia todo_iter_deps zavolá callback fn pre každú priamu závislosť úlohy id, teda pre každú úlohu b, pre ktorú bolo explicitne zavolané todo_add_dependency(ctx, id, b) a závislosť nebola od tej doby odobratá.

Tranzitívne závislosti (napr. c v reťazci a → b → c) todo_iter_deps nezahrnie, sú síce vynútené pri zoraďovaní, ale todo_iter_deps vystavuje iba priamy graf závislostí, aby mal volajúci možnosť prechádzať ho sám podľa potreby.

Poradie, v akom sú závislosti odovzdané callbacku, zodpovedá poradiu ich pridania.

Táto funkcia vyžaduje platné vstupy: ctx != nullptr, id != 0 a fn != nullptr; porušenie niektorej z týchto podmienok je porušením kontraktu API.

Príklad závislostí

Nech v prázdnom kontexte postupne pridáte tieto úlohy a závislosti:

task_id nakup   = todo_v2_add_task(ctx, (struct todo_task_view){
    .description = "Nakupit akvarium",
    .due = 3, .after = 0, .urgency = TODO_URGENCY_LOW
});
task_id ryby    = todo_v2_add_task(ctx, (struct todo_task_view){
    .description = "Kupit rybicky",
    .due = 5, .after = 0, .urgency = TODO_URGENCY_LOW
});
task_id nakrmit = todo_v2_add_task(ctx, (struct todo_task_view){
    .description = "Nakrmit rybicky",
    .due = 0, .after = 0, .urgency = TODO_URGENCY_HIGH
});

todo_add_dependency(ctx, ryby,    nakup);   /* ryby až po nákupe akvária  */
todo_add_dependency(ctx, nakrmit, ryby);    /* kŕmenie až po kúpe rybičiek */

Bez závislostí by sa nakrmit objavilo ako prvé (má urgency = HIGH). Po pridaní závislostí musí platiť nakrmit až po ryby, a ryby až po nakup. Výsledné poradie pri iterácii teda bude:

  1. nakup: termín 3, LOW naliehavosť, žiadna závislosť,

  2. ryby: termín 5, LOW naliehavosť, závisí od nakup,

  3. nakrmit: bez termínu, HIGH naliehavosť, ale závisí (tranzitívne) od nakup aj ryby.

Ak následne zavoláte todo_mark_done(ctx, nakup), závislosť ryby → nakup sa automaticky vymaže a ryby sa presunie na svoju prirodzenú prioritnú pozíciu. Závislosť nakrmit → ryby zostáva aktívna.

Poznámky

Časť A

  • Vaša implementácia musí korektne pracovať s dynamicky alokovanou pamäťou.

  • Použite assert na overenie vstupných podmienok verejných funkcií tam, kde ide o porušenie kontraktu API. Za porušenie kontraktu sa považujú najmä vstupy reprezentujúce nevalidné hodnoty, napr. nullptr a 0.

  • Verejné rozhranie knižnice je dané súborom include/todo.h.

  • Súbor cli/cli.c obsahuje jednoduchý REPL program, ktorý používa vaše rozhranie. Môžete ho využiť na vlastné interaktívne testovanie.

Časť B

  • Súbor cli/cli-v2.c obsahuje REPL program ako v cli.c, ktorý je rozšírený o nové príkazy a využíva nové funkcie.

vygenerováno 2026-07-05 13:01 upravit