Sistemul de monitorizare al navei USS Enterprise constă dintr-o mulțime de serii de timp. O serie de timp corespunde unui parametru monitorizat al navei (de ex., viteza, traiectoria, energia scuturilor, etc.) și constă dintr-o secvență de perechi (t,v), unde v este un număr real reprezentând valoarea parameterului corespunzator seriei de timp, iar t este momentul în care a fost măsurat acest parametru. Vom numi o astfel de pereche (timp,valoare) un “entry”.
Fiecare serie de timp este stocată într-un fișier binar ce conține entry-urile corespunzătoare seriei de timp, precum și, dacă este cazul, alte informații suplimentare. Entry-urile unei serii de timp TS sunt numerotate de la 0 la N(TS)-1, unde N(TS) este numărul total de entry-uri din cadrul seriei de timp TS, în ordinea în care acestea sunt adăugate în seria de timp. Entry-uri noi se adaugă mereu la sfarșitul seriei de timp (după entry-urile deja existente). Entry-urile nu sunt adăugate în cadrul seriei de timp neapărat în ordine crescătoare a momentelor de timp corespunzătoare.
Fiecare serie de timp are asociat un parametru blockSize și un index care este utilizat pentru căutarea mai rapidă a datelor în cadrul seriei de timp. Index-ul unei serii de timp este stocat într-un fișier binar separat. Pentru fiecare blockSize entry-uri din cadrul seriei de timp se creează un entry în cadrul index-ului asociat. Entry-ul de index conține cel puțin momentul de timp minim și momentul de timp maxim dintre cele blockSize entry-uri corespunzătoare lui. Pentru entry-urile de la finalul seriei de timp se creează un entry de index chiar dacă acestea sunt în număr mai mic decât blockSize.
Cerință
Sarcina voastră este să implementați sistemul de monitorizare al navei USS Enterprise, sub forma unui fișier header denumit “ts.h”. Acest fișier trebuie sa conțină definiția următoarelor structuri și implementarea următoarelor funcții:
struct ts_entry { int time; double value; };Această structură reprezintă un entry al unei serii de timp . time este momentul de timp, iar value este valoarea corespunzătoare unui entry al unei serii de timp.
struct ts { int n; struct ts_entry* entries; };Această structură reprezintă o (sub-)serie de timp. n reprezintă numărul de entry-uri, iar entries este un pointer către o zonă de memorie ce conține entry-urile; entry-urile seriei de timp vor fi entries[0], …, entries[n-1].
void Init()
În această funcție puteți inițializa propriile variabile globale declarate în “ts.h” și puteti citi (dacă aveți nevoie) fișiere scrise la utilizări anterioare ale funcțiilor dumneavoastră.
int CreateNewTS(int blockSize)
Această funcție creează o nouă serie de timp (fără vreun entry) și întoarce identificatorul acesteia, care trebuie să fie de tipul int; parametrul blockSize este utilizat pentru calculul index-ului. Identificatorul poate fi calculat cum doriți dumneavoastră, dar trebuie să fie diferit de identificatorii altor serii de timp create anterior.
void WriteNewTSEntries(int tsid, struct ts_entry* entries, int n)
entries este un pointer către un vector ce contine n entry-uri. Aceste entry-uri trebuie adăugate, în ordine, la sfârșitul seriei de timp având identificatorul tsid (identificatorul a fost obținut anterior printr-un apel al funcției CreateNewTS).
struct ts* GetTSEntriesBetweenPositions(int tsid, int pmin, int pmax)
Funcția citește entry-urile numerotate de la pmin la pmax (inclusiv) din cadrul seriei de timp cu identificatorul tsid (obținut anterior printr-un apel al functiei CreateNewTS) și le adaugă într-o structură struct ts în care campul entries conține adresa către un vector cu cele pmax-pmin+1 entry-uri citite, iar campul n este setat la pmax-pmin+1. Se garantează că vor exista suficiente entry-uri în seria de timp tsid. Se întoarce un pointer către structura creată. Intern, va trebui să retineți că pointer-ul întors este asociat pozițiilor de la pmin la pmax din seria de timp tsid.
struct ts* GetSubTS(struct ts* tser, int pstart)
Parametrul tser este un pointer întors de un apel anterior al funcției GetTSEntriesBetweenPositions sau GetSubTS. Funcția va construi o nouă structură struct ts ce va conține entry-urile începând de la poziția pstart până la poziția tser->n-1 dintre entry-urile structurii struct ts către care pointează tser. Mai exact, să considerăm entry-urile din tser->entries numerotate de la 0 la tser->n-1. Noua structură creată va conține în campul său entries un pointer către entry-urile numerotate de la pstart la tser->n-1 dintre entry-urile lui tser. Câmpul n al noii structuri create va fi setat corespunzător (la câte entry-uri conține noua structură). Se întoarce ca rezultat al funcției un pointer către noua structură creată. Intern, va trebui să retineți că pointer-ul întors este asociat aceleiați serii de timp ca și pointer-ul tser, precum și peste ce poziții din această serie de timp se “suprapune”. O cerință suplimentară este ca oricând modificăm un entry (câmpul time sau value) al structurii nou create, entry-ul corespunzător din tser să se modifice, de asemenea.
void RewriteOldTSEntries(struct ts* tser)
Pointer-ul tser este un pointer creat printr-un apel anterior al funcțiilor GetTSEntriesBetweenPositions sau GetSubTS. Să presupunem că entry-urile acestuia se “suprapun” peste pozitiile pmin, …, pmax din cadrul seriei de timp tsid. Această funcție modifică pozițiile pmin, …, pmax ale acestei serii de timp, setându-le la valorile entry-urilor lui tser. Aveți grijă că o dată cu modificarea acestor entry-uri vor trebui modificate și entry-urile de index corespunzătoare.
int GetNumberOfIndexEntries(int tsid)
Întoarce numărul de index-uri de entry ale seriei de timp tsid. De exemplu, dacă tsid conține 10 entry-uri și are blockSize=4, atunci aceasta va avea 3 index-uri de entry: primele două corespunzătoare entry-urilor 0, …, 3, respectiv4, …, 7, iar ultima corespunzătoare entry-urilor 8, 9.
void GetIndexEntryInfo(int tsid, int idxEntry, int* tmin, int* tmax)
Această funcție setează conținutul de la adresa pointer-ilor tmin și tmax la cel mai mic moment de timp, respectiv cel mai mare moment de timp al unui entry corespunzător entry-ului de index idxEntry al seriei de timp tsid. Index-urile de entry ale unei serii de timp sunt numerotate cu numere consecutive, începând de la 0.
int GetNumberOfTSEntriesBetweenTimeMoments(int tsid, int tmin, int tmax)
Această funcție întoarce numărul de entry-uri ale seriei de timp tsid pentru care câmpul time este în intervalul [tmin,tmax]. O metodă ineficientă pentru a calcula rezultatul este să traversați toate entry-urile seriei de timp și să mentineți un contor cu numărul de entry-uri întâlnite care satisfac condiția. O metodă mai eficientă utilizează index-ul asociat seriei de timp pentru a nu trece neaparat prin toate entry-urile seriei de timp tsid.
void Finish()
În cadrul acestei funcții veți salva datele necesare în fișiere (sau, în funcție de implementare, doar veti închide fișierele deschise), pentru a fi disponibile la rulări ulterioare. De asemenea, tot în cadrul acestei funcții va trebui să eliberați toate zonele de memorie alocate dinamic (și nedezalocate încă) de funcțiile dumneavoastră (de ex., zonele de memorie alocate dinamic de funcțiile GetTSEntriesBetweenPositions și GetSubTS; pointer-ii întorși de aceste funcții nu mai sunt valabili pentru rulări ulterioare).
Pe lângă structurile și funcțiile menționate mai sus, fișierul “ts.h” poate conține orice alte structuri, funcții și variabile pe care le veți considera necesare. Pentru declararea unor variabile globale accesibile în functiile din fișierul “ts.h”, le veti declara pur și simplu undeva în interiorul fișierului “ts.h” (dar inaintea definirii funcțiilor ce utilizează variabilele respective).
Exemplu
În această secțiune vor fi prezentate, pentru claritate, câteva exemple de apeluri ale funcțiilor descrise mai sus.
#include "ts.h"
int main() {
int tsid, numIndexEntries, tmin, tmax, numEntries;
struct ts_entry entries[10] = { {10, 0.1}, {7, 0.2}, {6, 0.3}, {4, 0.1}, {7, 0.2}, {2, 0.3}, {4, 1.4}, {1, 10.0}, {9, 8.3}, {6, 6.6} };
struct ts *tser1, *tser2;
tsid = CreateNewTS(4); // Intoarce identificatorul unei noi serii de timp, care nu contine niciun entry.
WriteNewTSEntries(tsid, entries, 10);
/* Seria de timp tsid contine acum entry-urile din vectorul entries.
De asemenea, se creeaza 3 entry-uri de index.
Entry-ul de index 0 corespunde primelor 4 entry-uri, iar momentul sau minim de timp este 4, iar momentul sau maxim de timp este 10.
Entry-ul de index 1 corespunde urmatoarelor 4 entry-uri, iar momentele sale de timp minim și maxim sunt 1 și 7.
Entry-ul de index 2 corespunde ultimelor 2 entry-uri, iar momentele sale de timp minim și maxim sunt 6 și 9. */
tser1 = GetTSEntriesBetweenPositions(tsid, 2, 5);
/* tser1->entries contine entry-urile (6,0.3), (4,0.1), (7,0.2) și (2,0.3), în aceasta ordine. */
tser2 = GetSubTS(tser1, 2);
/* tser2->entries contine entry-urile (7,0.2) și (2,0.3). */
tser2->entries[1].time += 20;
/* tser2->entries[1].time devine egal cu 22. Simultan, tser1->entries[3].time trebuie sa devina egal cu 22, de asemenea. */
RewriteOldTSEntries(tser1);
/* tser1 corespunde pozitiilor 2,...,5 din cadrul seriei de timp tsid.
Entry-urile corespunzatoare acestor pozitii devin egale cu: (6,0.3), (4,0.1), (7,0.2) și (22,0.3).
In urma modificarilor acestor entry-uri se modifica și entry-urile de index.
In acest caz, singurul index de entry care isi modifica valorile este cel numerotat cu 1: momentele sale de timp minim și maxim sunt 1 și 22. */
numIndexEntries = GetNumberOfIndexEntries(tsid);
/* numIndexEntries devine egal cu 3. */
GetIndexEntryInfo(tsid, 1, &tmin, &tmax);
/* tmin devine egal cu 1, iar tmax devine egal cu 22. */
numEntries=GetNumberOfTSEntriesBetweenTimeMoments(tsid, 4, 7);
/* numEntries devine egal cu 6. Cele 6 entry-uri sunt: (7,0.2), (6,0.3), (4,0.1}, (7,0.2), (4,1.4), (6,6.6). */
return 0;
}
Autor: Mugurel Ionuț Andreica
Data: 15.01. 2011