Zadanie 4

Zadanie 4

Nezabudnite zadanie nahrať do AIS do príslušného miesta odovzdania (odovzdajte len príslušné zdrojové .c a hlavičkové .h súbory). Súbory je nutné následne v AIS potvrdiť tlačidlom niekoľkokrát za sebou až pokiaľ neuvidíte oznam o úspešnom odovzdaní.

Dôležité informácie

  • Termín odovzdania: Odovzdajte do AIS, 6. máj 2020, 23:59
  • Počet bodov: 10
  • Odovzdávané súbory a formát ich pomenovania (ID nahraďte vašim AIS ID číslom):
    • ID.main.z4.c (hlavný testovací zdroják obsahujúci main funkciu)
    • ID.gps.z4.c (zdroják s implementáciou potrebných funkcií)
    • ID.gps.z4.h (hlavičkový súbor obsahujúci deklarácie potrebných funkcií a definície vlastných dátových typov, konštánt a pod.)
  • Podmienkou získania bodov za zadanie je, aby bol váš kód kompilovateľný prekladačom gcc s prepínačom -Wall bez chýb a upozornení (teda 0 errors, 0 warnings). Na otestovanie tejto nutnej podmienky máte rôzne možnosti:
  • Nezabudnite dodržať termín odovzdania do AIS, oneskorené odovzdanie nebude akceptované.

Obsah


Príprava

  • Prednáška o štruktúrach a súboroch (autor Pavol Zajac)

  • Tí, ktorí pracujete vo Visual Studio nezabudnite na:

    • makro _CRT_SECURE_NO_WARNINGS povolí používanie funkcií ako scanf a pod. (treba ho napísať úplne na začiatok programu pred miesto vloženia ostatných .h súborov)
    • makro _USE_MATH_DEFINES povolí používanie matematických konštánt z math.h
  • Online zdroje

Cieľ zadania

Naprogramujte v jazyku C command-line nástroj (konzolovú aplikáciu) na prácu s lokalizačnými údajmi. Účelom tohto nástroja je podpora vyhľadávania v súbore lokalizačných dát (riadky textu v dohodnutom formáte) a detekcia potenciálneho šírenia infekcie na základe týchto dát. Hlavným poslaním tohto zadania je naučiť sa správne pracovať so štruktúrami a súbormi (viď priložené prednášky na tému štruktúry a súbory).

Nástroj za bude spúšťať z terminálu a jeho správanie bude určené pomocou zadaných prepínačov (využijete osvojené znalosti z predošlého zadania). Výstup programu je smerovaný štandardne na obrazovku (stdout) alebo do výstupného súboru. Štruktúra príkazu, ktorým váš nástroj spustíte:

./z4 -i input_file [-o output_file] [-u|-l|-t|-s params]

Popis:

  • z4

    Predstavuje názov skompilovaného programu.

  • -i input_file

    Povinný prepínač spolu s jeho povinným parametrom. Prepínač -i signalizuje načítanie vstupného súboru s lokalizačnými dátami. Parameter input_file určuje cestu k súboru. Bez zadania tohto prepínača spolu s jeho povinným parametrom sa váš program ukončí bez výstupu. Formát vstupného súboru je definovaný nižšie v zadaní.

  • [-o output_file]

    Voliteľný prepínač určujúci výstupný súbor na zápis výsledkov vykonaných operácií (vtedy program nič nevypisuje na obrazovku, ale do tohto súboru). Ak nie je zadaný, tak výstup/výpis vášho programu ide na stdout (štandardný výstup).

  • [-u|-l|-t|-s params]

    Časť príkazu, kde sa môže uviesť prepínač, ktorý definuje operáciu, ktorá sa vykoná s lokalizačnými dátami (čítaj nižšie). Jednotlivé operácie sú špecifikované nižšie v zadaní.

Časti príkazu, ktoré sú v hranatých zátvorkách sú voliteľné, t.j. program funguje s nimi aj bez nich.

Hlavné body zadania

  • Využiť oddelený preklad. Vaše vypracované riešenie bude zložené z 3 súborov (2 zdrojové a 1 hlavičkový). Osvojíte si prácu s oddelením jednotlivých logických častí zdrojového kódu do samostatných súborov a vytvoríte tak prehľadnú štruktúru.
  • Načítať súbor s lokalizačnými dátami a uložiť jeho obsah do vhodnej dátovej štruktúry (ideálne do poľa štruktúr) a následne s nimi vedieť narábať pomocou vlastných funkcií.
  • Vykonať jednotlivé operácie s lokalizačnými dátami, ktoré sú zamerané na usporiadanie, vyhľadávanie, alebo pokročilejšie filtrovanie načítaných údajov.
  • Vypísať výsledky operácií v stanovenom formáte na stdout alebo do výstupného súboru.

Ukážka (video)

Demonštrácia oddeleného prekladu a práce so štruktúrami. Obsahom ukážky je jednoduchý program na načítanie GPS súradníc a výpočtu ich vzdialenosti. GPS súradnica je programátorsky reprezentovaná ako štruktúra. Vo videu môžete vidieť hlavný testovací zdrojový súbor obsahujúci funkciu main, z ktorej sú volané funkcie na získanie GPS súradníc a výpočet ich vzdialenosti (tie sú implementované v samostatnom .c súbore). Deklarácia vlastného dátového typu pre GPS súradnicu a deklarácie používaných funkcií sú v hlavičkovom súbore. Funkcie sú implementované v samostatnom zdrojovom súbore. Tento materiál slúži ako dobrý štartovací bod pre pochopenie základov štruktúr a písania funkcií, ktoré pracujú so štruktúrami. Autorom ukážky je prednášajúci, prof. Zajac.

Priebežne môžu byť pridávané ďalšie video ukážky na demonštráciu správania sa programu pri rôznych variantách spustenia z terminálu (rôzne prepínače).

Postup

1. Súbor s lokalizačnými dátami

Váš program bude pracovať s lokalizačnými údajmi uloženými v textovom súbore. Jedná sa o súbor, ktorý obsahuje záznamy o polohách jednotlivých používateľov v čase. Textový súbor obsahuje riadky, kde jeden riadok predstavuje jeden lokalizačný záznam, ktorý má nasledovný formát:

TIMESTAMP IMEI GPS_LAT GPS_LON

Popis:

  • TIMESTAMP je časová pečiatka informujúca o tom, kedy vznikol lokalizačný záznam. Časová pečiatka je vo formáte yyyy-MM-dd, t.j. napríklad 2017-08-19.
  • IMEI je číselný identifikátor používateľa. Jedná sa o 8-miestne číslo (pôvodne sa jedná o 15-miestne číslo, ale kvôli možnosti jeho reprezentovania pomocou premennej typu int bola dĺžka skrátená). Predstavuje jedinečný identifikátor mobilného telefónu používateľa. V zadaní netreba hlbšie skúmať vlastnosti tohto čísla, v tomto zadaní slúži len na označenie používateľa.
  • GPS_LAT je zemepisná šírka vyjadrená desatinným číslom s presnosťou 5 desatinných miest. Ak je toto číslo kladné, tak sa jedná o severnú zemepisnú šírku. Ak je záporné, tak sa jedná o južnú zemepisnú šírku.
  • GPS_LON je zemepisná dĺžka vyjadrená desatinným číslom s presnosťou 5 desatinných miest. Ak je toto číslo kladné, tak sa jedná o východnú zemepisnú dĺžku. Ak je záporné, tak sa jedná o západnú zemepisnú dĺžku.

Použitý formát značenia GPS súradníc (GPS_LON a GPS_LAT) je tzv. decimal degrees. Netreba ošetrovať správnosť formátu vstupného súboru. Budete pracovať vždy len so súborom, v ktorom budú údaje v dohodnutom formáte.

Náhľad súboru s lokalizačnými dátami

2019-07-13 94412072 48.20892 17.29569
2019-03-04 80233938 48.16927 17.13499
2020-03-18 69827772 48.09442 16.99770
2020-02-23 68163483 48.14603 17.23415
2020-03-10 13708614 48.16371 17.19290
2019-09-30 47439116 48.13398 17.08041
2019-12-24 82545032 48.10724 17.26021
2020-02-25 60897161 48.14946 17.17756
2020-03-27 88955224 48.09623 17.21499
2020-02-09 66320378 48.10982 17.15538

Testovacie súbory na stiahnutie:

  • new_gps.txt (celkom 100 000 záznamov: z toho 1 000 unikátnych IMEI, 100 záznamov pre každé IMEI, platí, že rovnaké IMEI sa nemôže vyskytnúť v ľubovoľnom dni viac ako 1-krát)
  • gps.txt (celkom 100 000 záznamov: z toho 1 000 unikátnych IMEI, 100 záznamov pre každé IMEI)
  • gps_10K.txt (celkom 1 000 000 záznamov: z toho 10 000 unikátnych IMEI, 100 záznamov pre každé IMEI)

Súbory obsahujú umelo vygenerované lokalizačné záznamy používateľov v geografickej oblasti zachytávajúcej Bratislavu + okolie. Záznamy sú vygenerované pre obdobie 1.3.2019 až 31.3.2020. Odskúšajte si fungovanie vášho programu s obidvomi vstupnými súbormi. Pri väčšom zo súborov si overíte efektívnosť vami naprogramovaných algoritmov.

Užitočné zdroje:

2. Operácie

Pripomeňme si štruktúru príkazu na spustenie programu:

./z4 -i input_file [-o output_file] [-u|-l|-t|-s params]

Program môže na základe poskytnutých prepínačov -u|-l|-t|-s vykonať operácie opísané v nasledujúcich sekciách. Program vždy vykoná len jednu operáciu podľa zadaného prepínača -u|-l|-t|-s alebo default operáciu ak nebude zadaný žiadny prepínač.

2.1 Default operácia

Ak používateľ pri spustení v termináli nešpecifikuje žiadny z prepínačov -u|-l|-t|-s, tak program usporiada všetky načítané lokalizačné záznamy podľa času (t.j. podľa TIMESTAMP) a vypíše ich. Usporiadanie bude od najnovšieho záznamu (prvý výpis) po najstarší záznam (posledný výpis).

  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt, usporiada ich podľa času a vypíše na obrazovku.
    ./z4 -i gps.txt
  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt, usporiada ich podľa času a zapíše ich do výstupného súboru result.txt (na stdout sa nevypíše nič).
    ./z4 -i gps.txt -o result.txt

2.2 Operácia -u imei

Vypíše lokalizačné záznamy len pre konkrétneho používateľa s daným číslom IMEI. Parameter prepínača je povinný.

  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt a vypíše na obrazovku len záznamy používateľa s číslom 50503462.
    ./z4 -i gps.txt -u 50503462
  • Podobné ako predošlý príklad len výpis bude zrealizovaný do výstupného súboru result.txt.
    ./z4 -i gps.txt -o result.txt -u 50503462

2.3 Operácia -l gps_lat gps_lon distance

Vypíše všetky lokalizačné záznamy v okolí zadaného GPS bodu so súradnicami gps_lat (zemepisná šírka - decimal degree notácia) a gps_lon (zemepisná dĺžka - decimal degree notácia) do vzdialenosti maximálne distance (vrátane). Vzdialenosť je vyjadrená v metroch. Parametre prepínača sú povinné.

  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt a vypíše na obrazovku len tie lokalizačné záznamy, ktoré boli od GPS bodu (lat=48.12345, lon=17.12345) vzdialené maximálne 50 000 metrov.
    ./z4 -i gps.txt -l 48.12345 17.12345 50000

Na výpočet vzdialenosti dvoch GPS súradníc použite Haversine formula. Správnosť výpočtu vzdialenosti medzi dvomi GPS súradnicami si viete overiť na stránke https://gps-coordinates.org.

2.4 Operácia -t start stop

Vypíše iba záznamy v danom časovom intervale <start,stop>. Parametre start a stop sú vyjadrené v rovnakom tvare ako TIMESTAMP, t.j. yyyy-MM-dd. Parametre prepínača sú povinné.

  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt a vypíše na obrazovku len tie záznamy, ktoré boli zozbierané od času 2019-01-01 (vrátane) do 2019-12-31 (vrátane).
    ./z4 -i gps.txt -t 2019-01-01 2019-12-31

2.5 Operácia -s imei time distance

Jedná sa o relatívne náročnú operáciu (čo sa prejavuje aj vo výslednom bodovaní). Operácia -s imei time distance hovorí, že v nejakom čase time sa nakazil používateľ s identifikátorom imei a úlohou je vypísať všetky záznamy, kedy s ním od času nakazenia prišiel do kontaktu nejaký iný používateľ vo vzdialenosti menšej ako distance (vyjadrená v metroch). Predpokladá sa, že používateľ sa stále nachádza na nejakej GPS pozícii od konkrétnej časovej pečiatky až po ďalšiu zaznamenanú časovú pečiatku (t.j. neuvažujeme, že by sa používateľ medzi dvoma po sebe idúcimi časovými pečiatkami hýbal). Parametre prepínača sú povinné.

  • Príklad spustenia, kedy program načíta údaje zo vstupného súboru gps.txt a vypíše na obrazovku len tie záznamy, kedy prišli ostatní používatelia vo vzdialenosti menšej ako 8000 metrov do kontaktu s používateľom s IMEI=50503462, ktorý sa nakazil v čase 2019-04-15.
    ./z4 -i gps.txt -s 50503462 2019-04-15 8000

3. Spracovanie prepínačov

Na spracovanie prepínačov môžete použiť funkciu getopt. Vzhľadom na fakt, že niektoré prepínače (-l,-t a -s) majú viac ako jeden povinný parameter, napr. operácia -s imei time distance má až 3 povinné parametre, nie je použitie funkcie getopt úplne ideálne. Parameter prepínača je vždy uložený na adrese danej globálnou premennou optarg (ak je prepínač na pozícii argv[i], tak optarg ukazuje na jeho parameter argv[i+1] ). Avšak ak má prepínač viac ako jeden povinný parameter, vtedy nám optarg veľmi nepomôže.

Jedným z možných riešení ako načítať viaceré parametre prepínača je nechať spracovať všetky argumenty programu funkciou getopt vo while cykle. Po skončení while cyklu zostane globálna premenná optind nastavená na prvý parameter prepínača (-l,-t alebo -s). Zvyšné parametre prepínača vieme prečítať jednoduchým for cyklom nasledovne:

int index;
for (index = optind; index < argc; index++)
{
   // konkretny parameter posledneho prepinaca je argv[index]
   printf("%s\n",argv[index]);
}

Príklad

Ak by sme spustili program nasledovným príkazom

./z4 -i gps.txt -s 50503462 2019-04-15 8000

potom by nasledovný kód

int c, index;
while ((c = getopt (argc, argv, "i:s")) != -1)
{
  // klasicke spracovanie prepinacov
}
for (index = optind; index < argc; index++)
{
   // konkretny parameter posledneho prepinaca je argv[index]
   printf("[%d] %s\n",index,argv[index]);
}

vypísal tento text

[4] 50503462
[5] 2019-04-15 
[6] 8000

4. Oddelený preklad

Vaše riešenie bude pozostávať z 3 súborov:

  • ID.main.z4.c
    Hlavný zdrojový súbor obsahujúci funkciu main. Mal by byť zodpovedný za správne načítanie obsahu súboru s lokalizačnými dátami a spracovanie prepínačov z príkazového riadku (napr. pomocou funkcie getopt, ktorú ste využívali v predošlom zadaní). Z funkcie main by mali byt volané funkcie, ktoré zabezpečia vykonanie jednotlivých operácií podľa zadaných prepínačov. Odporúčam si spraviť takisto vlastnú funkciu na načítanie obsahu súboru, ktorá prečíta súbor a uloží si jeho obsah do vhodne zvolenej dátovej štruktúry, ideálne do poľa štruktúr, kde jedna štruktúra bude reprezentovať jeden lokalizačný záznam. Tento zdrojový súbor by mal byť relatívne krátky, nakoľko obsahuje nosnú kostru riešenia a spolieha sa na funkcie naprogramované v súbore ID.gps.z4.c.

  • ID.gps.z4.c
    Obsahom tohto súboru budú definície všetkých vlastných funkcií, ktoré slúžia na vykonanie operácií asociovaných s jednotlivými prepínačmi + ďalšie pomocné funkcie k nim

  • ID.gps.z4.h
    Obsahom tohto súboru budú:

    • vlastné makrá a konštanty
    • definície vlastných dátových typov, napr. vlastná štruktúra na reprezentáciu celého lokalizačného záznamu, GPS pozície alebo aj času (zamyslite sa nad tým, aké entity v zadaní vyžadujú byť modelované zloženým dátovým typom)
    • deklarácie všetkých funkcií, ktoré sú implementované v súbore ID.gps.z4.c

Nezabudnite súbory medzi sebou správne prepojiť pomocou hlavičkového súboru (inšpirujte sa zverejnenou video ukážkou).

5. Ukončenie programu

Program skončí:

  • keď vykoná operáciu podľa zadaných prepínačov a vypíše výsledok operácie (na stdout alebo do výstupného súboru)
  • keď nebude zadaný povinný prepínač -i spolu s jeho parametrom
  • keď objaví neplatný prepínač
  • keď prepínač nebude mať zadaný jeho povinný parameter
  • ked nebude parameter prepínača zadaný v správnom tvare, napr. ak niekto spustí program pomocou ./z4 -i gps.txt -t ahoj ahoj (boli zadané neplatné parametre prepínača -t)
  • keď zadaná cesta k vstupnému súboru bude neplatná

6. Ukážky výstupov

Všetky ukážky sú platné pre vstupný súbor gps.txt.

6.1 Default operácia

Bez ukážky. Nakoľko každý z vás môže použiť iný triediaci algoritmus (stabilný alebo nestabilný), tak sa môže líšiť poradie záznamov, ktoré majú rovnaký dátum. Z toho dôvodu sa nedá zverejniť jediná správna ukážka výstupu. Výstup máte správny vtedy, ak máte všetky záznamy zotriedené od najnovšieho (prvý výpis) po najstarší (posledný výpis). Skontrolovať usporiadanosť záznamov si viete sami vo vlastnej réžii.

Nasledovná ukážka možného správneho výstupu default operácie vznikla pri použití funkcie qsort na triedenie poľa. Avšak ako sa v jej dokumentácii píše, poradie prvkov s rovnakou hodnotou je nedefinované a preto berte túto ukážku len za jedno z možných riešení (doležité je, že všetky záznamy sú správne usporiadané).

6.2 Operácia -u imei

6.3 Operácia -l gps_lat gps_lon distance

6.4 Operácia -t start stop

6.5 Operácia -s imei time distance

Ukážky sú na Discorde, v kanáli #zadanie4.

Testovanie a bodovanie

Zadanie bude hodnotené pomocou automatizovaných testov (otestuje sa séria rôznych prepínačov) a preto je potrebné, aby váš program vypisoval na štandardný výstup len výsledok operácie určenej prepínačmi - žiadne iné znaky, slová, pomocné hlásenia, dekoračné výpisy a pod. (toto bola dosť častá chyba študentov pri zadaní 3). Ak túto podmienku váš program nesplní, je dosť možné, že za zadanie nezískate žiadne body. Preto výrazne odporúčam dôkladne si kontrolovať vaše výstupy/výpisy.

Body sú orientačne rozdelené nasledovne:

  • [2b] Za správne fungovanie default operácie.
  • [1b] Za správne fungovanie operácie -u imei.
  • [2b] Za správne fungovanie operácie -l gps distance.
  • [2b] Za správne fungovanie operácie -t start stop.
  • [3b] Za správne fungovanie operácie -s imei time distance.

Nezabudnite, že nutnou podmienkou je, aby bol váš program kompilovateľný prekladačom gcc so zapnutým prepínačom -Wall bez chýb a upozornení (0 errors a 0 warnings). Vo vlastnom záujme si toto otestujte.

Konzultovanie zadania

Všetky vaše otázky smerujúce k zadaniu č.4 môžete zasielať na STUBA e-mailové adresy svojich cvičiacich alebo sa zapojiť do živej diskusie na našom Discord serveri (invite linka bola poslaná cez AIS) v kanáli #zadanie4.

Stay tuned.