Șablonul arhitectural - MVC ( Model - View - Controller )

MVC ( Model - View - Controller ) reprezintă un model arhitectural în care "logica programului" este separată de operațiunile de input și output. Mai bine zis programul va fi împărțit în trei zone:

• zona Model: unde se vor afla informațiile adică baza de date a programului.
• zona View: aici se va găsi tot ce este legat de afișare precum și operațiile prin care preluăm date de la utilizator ( input și output ).
• zona Controller: zona în care se face legătura dintre Model și View; în Controller se preia date de la utilizator prin intermediul View-ului, se verifică datele și apoi se accesează Modelul folosind date primite de la View.

În programele create până acum nu era făcută o diferență intre ceea ce reprezenta informație de la/pentru utilizator și ceea ce reprezinta logica programului.
Cam așa arată în mod normal dependența dintre datele primite de la utilizator și prelucrarea acestora.

MVC-ul întroduce o nouă componentă care ajuta la separarea legăturii dintre cele două componente.

 
Acum că avem acel controller, acesta se va ocupa gestionarea datelor primite de la View, le va verifica și apoi va accesa modelul furnizând acele date primite de la utilizator.

În continuare vom vedea cum ar trebui să arate un program care este proiectat folosind acest șablon. Vom considera mai departe trei clase Agenda( Model-ul ), Controller( Controller ) și Interfata ( View ) fiecare cu câteva metode și atribute sugestive pentru ce avem noi nevoie momentan.

Mai jos avem câteva metode din clasa Agenda:

...
public:
 void adaugaContact( Contact c );
 void eliminaContact();
...

Și câteva metode din clasa Interfata:

...
public:
 int getUserAction();
 void afisareInterfataAdaugareContact(...);
 void afisareInterfataEliminareContact(...);
...

Acum trecem la clasa Controller care va conține un obiect de tip Interfata și un obiect de tip Agenda pe lângă alte atribute.

Cum spuneam mai sus controller-ul are rol de a media cele două componente. Așadar o metoda, spre exemplu de control asupra adăugării unui contact va arăta cam așa:

...
void Controller::controllerAdaugareContact(void)
{
 interfata->afisareInterfataAdaugareContact(...);

 // urmează partea în care se verifică informațiile primite de la utilizator
 // apoi se crează contactul propriu zis pe baza acestora
 // după care se trimit informațiile Model-ului

 agenda->adaugareContact( c );
}
...

Implementarea este sumară deoarece scopul nostru este să înțelegem cât mai bine cum funcționează acest șablon.

După cum ați observat mai sus, clasa Controller va conține metode în care se va realiza legătura dintre interfață și model. Pentru operații simple asupra Model-ului, cum ar fi afișarea unui contact, se poate accesa direct Model-ul printr-o interogare de stare acesta răspunzând printr-o notificare asupra stării acestuia. Ideea e că pentru chestii legate de afișare nu mai este nevoie de controller să medieze legătura dintre Model și View.

Simularea unei cozi folosind două stive implementate prin clase

Coada reprezintă o structură abstractă de date în care inserarea unui nou element se face într-o parte a cozii, iar eliminarea se face din capătul celălalt. Conceptul de coadă apare în orice sistem în care obiectele sunt servite în ordinea sosirii.

Cele două capete ale cozii îşi iau numele din această paralelă cu rândul de asteptare. Mai precis, capătul de la care sunt eliminate articolele se numeşte cap (head) iar capătul la care se adaugă elementele se numeşte coadă (tail); pentru a evita confuziile, vom folosi în acest scop termenii de început şi sfârşit.

Stiva reprezintă de asemenea o structură abstractă de date, în care singura deosebire faţă de coadă este că inserarea şi eliminarea se fac de la acelaşi capăt.

Principiul folosit pentru a simula o coadă folosindu-ne de cele două stive este următorul:

Considerăm că inserarea, eliminarea şi citirea se fac la capătul de la începutul stivei. Tot ce avem de făcut acum este să încercăm să definim operaţiile de inserare, eliminare şi citire pentru coadă folosindu-ne de cele pentru stivă.

pentru operaţia de inserare consideram că se inserează la începutul cozii deci putem folosi direct funcţia de inserare ( push () ) de la stivă.

pentru operaţiile de eliminare şi citire va trebui să mutăm elementele din prima stivă în cea de-a doua stivă. Pentru a avea o perspectivă cât mai clară în legătură cu această mutare urmăriţi exemplul de mai jos.

acum că avem elementul care trebuie eliminat sau citit apelăm funcţiile referitoare la citire sau eliminare ( top(), pop() ) de la stive.

Pentru fiecare nod din stivă avem nevoie de o structură cu două câmpuri în care un câmp va conţine informaţia din nodul respectiv, iar celălalt va conţine legatura către următorul nod.

typedef int Type; 

//asociem tipului int aliasul Type 

//de asemenea putem asocia orice tip de dată pentru Type 

//singura modificare se va face aici

 typedef struct NodeStack {
 Type info; //informatia continuta in nod
 struct NodeStack *next; //legatura catre nodul urmator
 } NodeStack;

Pentru a nu exista neclarităţi la nivelul codului mai creem o structură care va conţine pointer către primul nod din stivă şi numărul elementelor din stivă.

typedef struct Stack {
 NodeStack *prim; //pointer catre primul element din lista
 int nrElt;  //numarul de elemente in lista
} Stack;

Acum că avem structura definită pentru stivă, trecem la implementarea clasei ce va conţine ca şi metode, operaţiile caracteristice pentru stivă - push(), pop(), top().

class MyStack
{
public:
 MyStack(void);  //constructor
 ~MyStack(void); //destructor
 void pop();       //metodele referitoare la operatiile cu stive
 void push(Type);  //si de asemenea Getters && Setters pentru elementele stivei
 Type top();
 bool isEmpty();
 void setNrElt(int);
 void setPrim(NodeStack*);
 NodeStack* getPrim();
 int getNrElt();
private:
 Stack stack;
};

Având definită clasa MyStack, începem simularea cozii. Pentru aceasta avem nevoie de două obiecte de tip MyStack.

MyStack *stack1 = new MyStack(), *stack2= new MyStack();

Vom stoca informaţiile primite în obiectul stack1 iar obiectul stack2 va fi folosit pentru mutarea elementelor în cazul unei eliminări sau citiri.

Pentru funcţia de înserare în coadă se va folosi funcţia de inserare în stivă:

Type e;
printf("Dati elementul: \n");
scanf("%d",&e);
stack2->push(e);

Pentru funcţiile de eliminare sau citire din coadă avem nevoie sa mutăm elementele din primul obiect în cel de-al doilea şi să afisăm/eliminăm elementul utilizând această secvenţă de cod:

while(!stack1->isEmpty())
{
 stack2->push(stack1->top());
 stack1->pop();
}
printf("Elementul eliminat este %d ",stack2->top());
stack2->pop();
//sau pentru citire
printf("Elementul cel mai vechi este %d",stack2->top());

În cazul în care coada este goala se va afişa un mesaj corespunzător.

Implementarea unui arbore binar folosind liste înlanţuite

Un arbore binar este un arbore în care fiecare nod are cel mult doi fii, arborele din stânga şi arborele din dreapta. Fiecare nod dintr-un arbore binar se reprezintă de obicei printr-o structură în care folosim un câmp pentru a stoca informaţia (eticheta) şi doi pointeri către cele două noduri, pointerul către nodul fiu din stânga si pointerul către nodul fiu din dreapta. Dacă unul sau amândoi fiii unui nod lipsesc, pointerii corespunzători au valoarea zero.

Definim structura cu specificaţiile de mai sus.

typedef struct NodeTree {

    char info;   //informaţia conţinută în nod

    struct NodeTree *stg; //legatura către nodul stang

    struct NodeTree *drp;       //legatura către nodul drept

} NodeTree;

Acum că avem definită structura NodeTree, trecem la funcţia ce va crea un arbore binar dintr-o secvenţa de caractere primită ca parametru. Secvenţa este constituită din litere mari şi caracterele ( , ) $. Seminificaţia acestora este următoarea:

• literele reprezintă informaţia dintr-un nod;
• '(' defineşte un nivel inferior;
• ',' separă sub-arborele stâng de cel drept;
• ')' marchează stârşitul nivelului inferior;
• '$' marchează lipsa sub-arborelui respectiv.

Exemplu: "A ( B , C ( D , E ( F , $ ) )", iar arborele va arăta cam asa:

Funcţia "create(char *)" va primi ca argument secvenţa de caractere şi va returna nodul rădăcină al arborelui. Logica din spatele acestei funcţii este următoarea:

• parcugem secvenţa de caractere şi verificăm dacă caracterul este literă mare. Dacă da, atunci alocăm spaţiu pentru un nod de tip NodeTree, în campul pentru informaţie salvăm caracterul, fii săi vor fi nuli, apoi îl punem pe o stivă.
  
  
  
  
  
  
  
  Cam aşa va arata stiva noastră după ce au fost introduse toate nodurile.


• după ce avem elementele pe stivă începem să facem legăturile dintre noduri şi fii lor.
  
  
  Ultimul element de pe stivă va fi nodul rădăcină pe care funcţia noastă îl va returna.

Legăturile dintre noduri şi fii lor sunt realizate de următoarea scvenţă de cod:

NodeTree *fs, *fd;
     fs=(NodeTree*)malloc(sizeof(NodeTree));
     fd=(NodeTree*)malloc(sizeof(NodeTree));
     fd=top(&S);   //scoatem fiul drept de pe stivă
     pop(&S);      //eliminăm fiul drept
     fs=top(&S);   //scoatem fiul stâng de pe stivă
     pop(&S);      //eliminăm fiul stâng
     v=top(&S);    //scoatem nodul părinte pentru cei doi fii
     pop(&S);      //îl eliminăm de pe stivă
     v->stg=fs;    //realizăm legăturile dintre aceştia
     v->drp=fd;
     push(&S,v);   //îl punem din nou pe stivă

Acum că avem arborele avem nevoie de o modalitate de a-l afişa. Exista 4 modalităţi de afişare a unui arbore binar: PreOrdine, InOrdine, PostOrdine şi parcurgerea BFS( Breadth-first Search ). Primele 3 metode diferă doar prin ordinea în care sunt vizitate cele 3 componente ale arborelui.

• în parcurgerea PreOrdine mai întâi este vizitată rădăcina apoi subarborele stâng apoi cel drept. 

void RSD(NodeTree* v, void viziteaza(NodeTree*))
{
    if (v ==NULL)return;
    else
    {
        viziteaza(v); // o procedură ce afisează informaţia din nod
        RSD(v->stg, viziteaza); // parcurgere recursivă pentru fiecare subarbore
        RSD(v->drp, viziteaza);
    }
}

• în parcurgerea InOrdine mai întâi este vizitat subarborele stâng, rădăcina apoi cel drept.
• în parcurgerea PostOrdine mai întâi este vizitat subarborele stâng, subarborele drept apoi rădăcina.

În ultima metodă de afişare a arborelui parcurgerea este realizată pe nivele, începând cu rădăcina şi continuând cu fiecare nivel.

void BFS(NodeTree *t, void viziteaza(NodeTree*))
{
    if (t==NULL) return;
    else
    {
        Queue q;
  q.prim=NULL;
  q.nrElt=0;
        insert(&q, t);
        while (!isEmpty(&q))
        {
            NodeTree* v;
            v=read(&q);
            viziteaza(v);
            if (v->stg!=NULL)insert(&q, v->stg);
            if (v->drp!=NULL)insert(&q, v->drp);
            remove(&q);
        }
    }
}

ASM - Clase în limbaj de asamblare (notiuni introductive)

O clasă este o construcție prin care se definesc noi tipuri de date prin asocierea unui set de funcții(metode) la o structură de date. Iată un exemplu de clasă:

class Persoana{
private:
 char nume[25]; // vector de caractere unde vom salva numele persoanei
 int size; // variabila ce va memora dimensiunea numelui
public:
 Persoana(); // constructor implicit
 ~Persoana(); // destructor implicit
 void setNume(char*);
};

După cum am văzut mai sus apar niște etichete ce desemnează drepturi de acces asupra acelor elemente și anume: public, private și protected.

• public: toate elementele de sub această etichetă pot fi accesate în interiorul clase cât și în afara acesteia.
• private: elementele de sub această etichetă nu pot fi accesate decât în interiorul clasei.
• protected: elementele din această categorie pot fi accesate doar în clasele ce derivă din această clasă.

Deoarece Assembler-ul nu ține cont de numele variabilelor acesta nu va ține cont nici de restricțiile impuse de aceste etichete. 
 
În principiu pentru a avea acces la un element din clasă trebuie ca cunoaștem practic adresa relativă fată de pointerul this la care se află elementul în memorie. Pentru aceasta avem nevoie să știm dimensiunea clasei. Dimensiunea clasei se calculează fiind suma dimensiunii fiecărui element.

În cazul de față clasa noastră ar avea dimensiunea de 29 de octeți. De fapt aceasta nu este dimensiunea reală deoarece se produce alinierea datelor, adica poziționarea lor în funcție de tipul cel mai mare de dată, în cazul nostru, int. Deci adevărata dimensiune a clasei este de 32 de octeți.

Cam așa arată clasa noastră în memorie.

Deoarece dimensiunea elementului nume este de 25, nefiind un multiplu de 4 (int fiind cel mai mare tip de dată din clasa), s-a produs alinierea datelor la tipul int.

Încă un lucru trebuie să mai știm ca să putem accesa un element din clasă, și anume că pointerul this se află în registrul ecx. Deci când lucrăm cu o clasă în limbaj de asamblare trebuie să avem grijă ca acest registru să nu fie modificat pentru a nu pierde adresa obiectului.

Adresa absolută a unui atribut din clasă se construiește din adresa de început a clasei, care se afla în pointerul this sau, în Assembler, în registrul ecx, și poziția de început atributul în memorie. În cazul nostru atributul size se găsește în memorie la adresa ecx+28, deoarece 28 reprezintă poziția de început a atributului size.

Acum ca avem aceste lucruri lămurite, putem trece să implementăm în limbaj de asamblare metoda din această clasă.

Ca idee de bază, verificăm dimensiunea șirului care este primit ca parametru, comparăm cu dimensiunea maximă a șirului din clasă. În cazul în care dimensiunea șirului primit ca parametru depășește dimensiunea șirului din clasă ieșim din funcție. Dacă dimensiunea este în regulă trecem mai departe la copierea celor șirurilor.

Pentru o bună vizualizare asupra codului, comentariile din partea de Assembler vor începe tot cu "//".

void setNume(char*){
 _asm{
  mov ebx,[ebp+8]
                   // mutăm în ebx valoarea parametrului primit
  xor edi, edi
                   // folosim registrul edi pentru a salva dimensiunea
                   // șirului primit ca argument
dim_param:
                   // calculăm dimensiunea parametrului primit ca argument
  cmp [ebx+edi],'\0'
  je verificare_dim
                   // cât timp nu am ajuns la sfârșitul șirului incrementăm registrul edi
  inc edi
  jmp dim_param
verificare_dim:
                   // verificam dacă depășește dimensiunea vectorului din clasă
  cmp edi,24
                   // comparăm cu dimensiunea maximă a șirului din clasă
  jge final

  xor esi, esi
bucla_1:
                   // copiem în vectorul din clasă șirul primit ca argument
                   // totodată ținând cont și de lungimea acestuia
  cmp [ebx+esi], '\0'
  je final_bucla_1
  mov dl, [ebx+esi]
                   // copiem fiecare caracter din șirul primit
                   // ca argument în șirul din clasa
  mov [ecx+esi], dl
  inc esi
  jmp bucla_1
final_bucla_1:
  mov byte ptr [ecx+esi],'\0'
  mov [ecx+28], esi
                   // punem dimensiunea actuală a șirului în variabila size
  jmp final
final:
 }
}

Mai sunt de explicat câteva lucruri în legătură cu codul de mai sus cum ar fi: folosirea registrului "dl " din instrucțiunea "mov dl, [ebx+esi]" sau de ce se pune "byte ptr" în instrucțiunea "mov byte ptr [ecx+esi],'\0'".

Pentru prima instrucțiune, folosirea registrului "dl" este necesară deoarece elementele din șir sunt de tip "char", dimensiunea lor fiind de 1 octet, avem nevoie de un registru de 1 octet pentru manipularea valorilor.

Cât despre a doua instrucțiune, practic îi spunem să pună "\0" într-un singur byte la adresa specificată.

Minimizarea funcțiilor booleene prin metoda diagramelor Karnaugh

Minimizați cu ajutorul diagramelor Karnaugh funcția logică: Σ(0, 2, 6, 7, 11, 13) + Σ*(3, 8, 9, 14), unde prin Σ* sunt notate combinațiile imposibile.

Pentru aceste tipuri de exerciții trebuie să știm că o diagramă Karnaugh este un tablou bidimensional cu 2ⁿ locații, unde n reprezinta numărul de variabile pe care le are funcția. De asemenea trebuie să mai știm sa generăm codul Gray pentru diagrama noastră. Avem nevoie de codul Gray deoarece in diagramele Karnaugh etichetele nu se scriu în ordinea naturală, ci în ordinea Gray.

O modalitate simpla de a genera codul Gray este metoda asa numită "oglindire + completare". În tabelul de mai jos aveți un exemplu despre cum se generează codul Gray pentru o funcție cu 3 variabile.

z	y	x		y	x		x
0	0	0		0	0		0
0	0	1		0	1		1
0	1	1		1	1
0	1	0		1	0
1	1	0
1	1	1
1	0	1
1	0	0

Rosu - Partea inițială Albastru - Oglidirea Verde - Completarea;

Acum că avem codul lui Gray trebuie să deteminăm câte variabile are funcția noastră. În cazul în care funcția este dată sub forma Σ-notație atunci trebuie să scriem cel mai mare număr ce apare în Σ-notație în baza 2, iar numărul de cifre pe care îl va avea reprezintă numărul de variabile. Observăm că cel mai mare număr din Σ-notație este 14 care în baza 2 este scris sub forma: 0110, deci funcția noastră este de 4 variabile.

Desenăm diagrama Karnaugh pentru 4 variabile și introducem valorile care se dau:

Acum încercăm să cautăm blocuri conţinând numai valori 1 și ajutându-ne de combinațiile imposibile, astfel încât:

• fiecare valoare 1 să fie inclusă în cel puţin un bloc;
• blocurile să fie cât mai mari şi mai puţine;
• un bloc să conţină un număr de locaţii egal cu o putere a lui 2, eventual puterea 0;

Trebuie reținut că minimizările rezultate nu sunt unice!

O posibilă variată de minimizare este reprezentată de următoarea diagramă.

Trebuie doar să scriem funcția rezultată din diagrama Karnaugh de mai sus. Pentru asta trebuie să ținem de următoarele lucruri:

• în termen apar acele variabile ale căror etichete sunt constante pentru toate locațiile din bloc, adică dacă o variabilă apare etichetată cu 1 și apoi apare etichetată și cu 0 nu se mai scrie;
• o variabilă apare negată dacă eticheta sa constantă este 0 și nenegată altfel;
• termenii astfel obținuți (după considerarea tuturor blocurilor) sunt legați prin disjuncție.

După ce considerăm toate blocurile, funcția noastră va arăta cam așa:

F = !A*C + !B*!C*!D + A*!B*D + A*!C*D;

Algoritmul Skolem

Algoritmul Skolem este un algoritm ce servește la restrângerea unei formule la forma normală Skolem. Pentru aceasta formula trebuie să treacă prin mai multe transformări.

Primul pas în rezolvarea acestor tipuri de exerciții este de a trece formula în forma normală rectificată(FNR). O formulă este în FNR dacă nu conține variabile care sunt atât libere cât și legate și nu are cuantificatori care să lege aceeași variabilă dar pe poziții diferite. O variabilă x este considerată legată dacă apare într-o subformulă G a unei subformule a lui F de forma: H = (∀x)(G) (sau (∃x)(G)). În restul cazurilor apariția considerată este numită liberă.

Șablonul arhitectural - Singleton

Singleton reprezintă un model arhitectural care asigură crearea unei singure instanțe a unei clase, totodată oferind și un punct de acces global la aceasta.

Acest model este folosit destul de des în aplicațiile pe care le folosim zi de zi, cum ar fi Winamp, Skype și altele, care nu iți permit să rulezi acea aplicație de mai multe ori pe același calculator.

Structura de bază a unei clase ce respectă aceste șablon este următoarea:

După cum se vede în imaginea de mai sus constructorul este trecut la private: pentru ca să nu fie apelat în afara clasei. Metoda instance() va returna un obiect de tip Singleton nou în cazul în care nu a fost creat încă sau va returna un pointer la instanța deja creată.

Să vedem cum va arata implementarea unei clase proiectată cu ajutorul șablonului Singleton:

class Singleton
{
public:
     static Singleton* instance(void);
     ~Singleton(void);
private:
     Singleton(void);
     static Singleton* uniqueInstance;
}

Acum să vedem cum arată implementarea metodelor acestei clase:

Singleton* Singleton::uniqueInstance = 0;

Singleton::Singleton(void)
{
}

Singleton::~Singleton(void)
{
}

Singleton* Singleton::instance(void)
{
     if(uniqueInstance == 0)
          uniqueInstance = new Singleton();
     return uniqueInstance;
}

Utilizatorii au acces la obiectele de tip Singleton exclusiv prin metoda instance(void). Membrul uniqueInstance este inițializat cu 0 la pornirea programului. Metoda instance(void) verifică dacă instanța noastă este nulă, atunci se crează o instantă a clasei iar dacă nu este va returna instanța deja creată.