Tipuri de date polimorfice

Tipuri de date polimorfice

Curs 10

Containere

• Container = TAD ale carui instante sunt colectii de alte obiecte

• Operatii:– Crearea unui container gol (constructor),– returnarea numarului de obiecte stocate (size), – Stergerea obiectelor din container (clear), – Adaugarea de noi obiecte in container – Stergerea obiectelor – Acces la obiectele stocate

Containere

• C = {c | c grup de elemente de acelasi tip E}• Tipuri de containere:

– Vector array – Lista list – Dictionar map – Coada queue – Multime set – Stiva stack – Tabel table – Arbore tree

• Pentru implementarea containerelor se folosesc diferite structuri de date aflate in relatie de compozitie sau derivare, modalitati de reutilizare a codului

http://en.wikipedia.org/wiki/Array_data_structure

http://en.wikipedia.org/wiki/List_%28computing%29

http://en.wikipedia.org/wiki/Associative_array

http://en.wikipedia.org/wiki/Queue_%28data_structure%29

http://en.wikipedia.org/wiki/Set_%28computer_science%29

http://en.wikipedia.org/wiki/Stack_%28data_structure%29

http://en.wikipedia.org/wiki/Table_%28information%29

http://en.wikipedia.org/wiki/Tree_%28data_structure%29

Container generic

Reprezentare pe vectorReprezentare

inlantuita

IE.h

#ifndef IE_H#define IE_H

class IE{ public: virtual char* toString()=0; virtual bool equals(IE*)=0; virtual ~IE(){}; }; #endif

IE

+toString(): String+equals(: IE): bool<<destroy>>-IE()

ICollection.h#ifndef ICOLLECTION_H#define ICOLLECTION_H#include "IE.h"#include "IIterator.h"

class ICollection{ public: virtual void add(IE*)=0; virtual void del(IE*)=0; virtual int length()=0; virtual bool contains(IE*)=0; virtual IIterator* iterator()=0; virtual bool isEmpty()=0; virtual ~ICollection(){} };#endif

ICollection

+add(: IE): void+del(: IE): void+length(): int+contains(: IE): bool+iterator(): IIterator+isEmpty(): bool

ArrayCollection.h#ifndef ARRAY_COL_H#define ARRAY_COL_H#include "ICollection.h"#include "IIterator.h"

class ArrayCollection:public ICollection{ IE** elem; int dim, cap; void resize(); int position(IE*); IE** toArray(); public: ArrayCollection(); ArrayCollection(int); void add(IE*); void del(IE*); int length(); bool contains(IE*); IIterator* iterator(); bool isEmpty(); ~ArrayCollection(); class ArrayCollectionIterator; friend class ArrayCollectionIterator;

class ArrayCollectionIterator:public IIterator{ ArrayCollection* c; int pos;

public: ArrayCollectionIterator(ArrayCollection* c1)

{c=c1; pos=0; } bool hasNext(){ return pos<c->dim;} IE* next(){ if (pos<c->dim) return c->elem[pos++]; return NULL; } void first(){ pos=0;}

IE* del(){ IE* e = c->elem[pos]; c->elem[pos]=c->elem[--c->dim]; return e; }

}; //sf clasa Iterator};#endif

Clase interioareArrayCollection

-dim: int-cap: int

-resize(): void-position(: IE): int-toArray(): IE<<create>>-ArrayCollection()<<create>>-ArrayCollection(: int)+add(: IE): void+del(: IE): void+length(): int+contains(: IE): bool+iterator(): IIterator+isEmpty(): bool<<destroy>>-ArrayCollection()

ArrayCollectionIterator

-pos: int

<<create>>-ArrayCollectionIterator(c1: ArrayCollection)+hasNext(): bool+next(): IE+first(): void+del(): IE

-c<<CppFriend>> Clasa interioara

Clasa inner

Clasa nested

Folosite pentru a marca explicit relatia dintre doua clase:

•iteratorul apartine containerului (“containerul isi alege iteratorul”)

ArrayCollection.cpp#include "ArrayCollection.h"ArrayCollection::ArrayCollection(){ elem = new IE*[10]; dim=0; cap=10;}

ArrayCollection::ArrayCollection(int d){ elem=new IE*[d]; dim=0; cap=d;}

void ArrayCollection::resize(){ IE** aux = elem; elem = new IE*[2*cap]; for(int i=0;i<cap;i++) elem[i]=aux[i]; cap*=2; delete [] aux; }

int ArrayCollection::position(IE* e){ for(int i=0;i<dim;i++) if (elem[i]->equals(e)) return i; return -1; }

void ArrayCollection::add(IE* e){ if(dim==cap) resize(); elem[dim++]=e;}

void ArrayCollection::del(IE* e){ int pos=position(e); elem[pos]=elem[--dim]; } int ArrayCollection::length(){ return dim; }

bool ArrayCollection::contains(IE* e){ for(int i=0;i<dim;i++) if (elem[i]->equals(e)) return true; return false; }

IIterator* ArrayCollection::iterator(){ return new ArrayCollectionIterator(this);}

bool ArrayCollection::isEmpty(){ return dim==0;}

ArrayCollection::~ArrayCollection(){ delete [] elem; }

IE** ArrayCollection::toArray(){IE** aux = new IE*[length()];int k=0;for(int i=0;i<dim;i++){ aux[k++]=elem[i];}return aux;

}

LinkedCollection

LinkedCollectionIterator

<<create>>-LinkedCollectionIterator(c1: LinkedCollection)+hasNext(): bool+next(): IE+first(): void+del(): IE<<destroy>>-LinkedCollectionIterator()

Nod

-elem: IE-next: Nod

<<create>>+Nod(e: IE, n: Nod)<<create>>+Nod(e: IE)

<<CppFriend>>-c

LinkedCollection

-position(e: IE): Nod<<create>>-LinkedCollection()+add(: IE): void+del(: IE): void+length(): int+contains(: IE): bool+iterator(): IIterator+isEmpty(): bool<<destroy>>-LinkedCollection()

IIterator

+hasNext(): bool+next(): IE+first(): void+del(): IE

ICollection

+add(: IE): void+del(: IE): void+length(): int+contains(: IE): bool+iterator(): IIterator+isEmpty(): bool

IE


-crt

LinkedCollection.h#ifndef LINKED_COLL_H#define LINKED_COLL_H#include "IIterator.h"#include "ICollection.h"class LinkedCollectionIterator;

class LinkedCollection:public ICollection{

class Nod{IE* elem;Nod* next;

public:Nod(IE* e, Nod* n){elem=e;next=n;}Nod(IE* e){elem=e;next=0;}~Nod(){}friend class LinkedCollection;friend class LinkedCollectionIterator;

}* head;

Nod* position(IE* e){Nod* crt=head;while(crt && (!crt->elem->equals(e)))

crt=crt->next;return crt;}

public:

LinkedCollection();void add(IE*);void del(IE*);int length();bool contains(IE*);friend class LinkedCollectionIterator;IIterator* iterator();bool isEmpty();~LinkedCollection();

};

class LinkedCollectionIterator:public IIterator{ LinkedCollection* c; LinkedCollection::Nod* crt;

public: LinkedCollectionIterator(LinkedCollection* c1){ c=c1;

crt =c->head; } bool hasNext(){ return (crt!=0); } IE* next(){

IE* e=crt->elem; crt=crt->next; return e;

} void first(){

crt=c->head; }

IE* del(){ IE* e= crt->elem; LinkedCollection::Nod* ant=c->head; while(ant->next!=crt)

ant=ant->next; ant->next=crt->next; LinkedCollection::Nod* aux=crt;

crt=crt->next; delete aux; return e;

} ~LinkedCollectionIterator(){}};

#endif

Read/write iterator

Modelul Java

LinkedCollection.cpp#include "LinkedCollection.h"#include "IE.h"

LinkedCollection::LinkedCollection(){head=0;}

void LinkedCollection::add(IE* e){head=new Nod(e,head);

}

void LinkedCollection::del(IE* e){Nod* crt=position(e);if (crt) {Nod* ant=head; while(ant->next!=crt) ant=ant->next; ant->next=crt->next;

delete crt; }

}

int LinkedCollection::length(){ int k=0;

Nod* crt=head; while(head){

k++; crt=crt->next;

} return k;}

bool LinkedCollection::contains(IE* e){Nod* p =position(e);return p!=0;

}

IIterator* LinkedCollection::iterator(){ return new

LinkedCollectionIterator(this);}

bool LinkedCollection::isEmpty(){return head==0;

}

LinkedCollection::~LinkedCollection(){Nod* crt;while(head){

crt=head;head=head->next;delete crt;

}}

Integer.h#ifndef INTEGER_H#define INTEGER_H#include <cstdio>#include <cstring>#include "IE.h"

class Integer:public IE{ private: int i; public: Integer(int n=0):i(n){} char* toString(){char* buf=new char[3]; sprintf(buf,"%d",i); return buf;} bool equals(IE* p){ return i==((Integer*)p)->i;} ~Integer(){} };#endif

IE


Integer

-i: int

<<create>>-Integer(n: int)+toString(): char+equals(p: IE): bool<<destroy>>-Integer()

Test.cpp#include "ICollection.h"#include "ArrayCollection.h"#include "LinkedCollection.h"#include "Integer.h"#include <iostream>using namespace std;

int main(){ICollection* c = new ArrayCollection();

c->add(new Integer(4));c->add(new Integer(4));c->add(new Integer(5));

IIterator* it = c->iterator();while(it->hasNext()){ IE* e = it->next();

cout<<e->toString()<<" "; delete e; }delete c;delete it;return 0;}

Singura instantiere concreta

Alocare memorie

Dealocare

Nod si iterator inner#ifndef LINKED_COLL_H#define LINKED_COLL_H#include "IIterator.h"#include "ICollection.h"class LinkedCollectionIterator;

class LinkedCollection:public ICollection{class Nod{

public:IE* elem;Nod* next;

Nod(IE* e, Nod* n){elem=e;next=n;}Nod(IE* e){elem=e;next=0;}~Nod(){}friend class LinkedCollection;

friend class LinkedCollectionIterator;

}* head;

Nod* position(IE* e){Nod* crt=head;while(crt && (!crt->elem->equals(e)))

crt=crt->next;return crt;

}

public:LinkedCollection();void add(IE*);void del(IE*);int length();bool contains(IE*);friend class LinkedCollectionIterator;IIterator* iterator();bool isEmpty();

~LinkedCollection();

class LinkedCollectionIterator;friend class LinkedCollectionIterator;

class LinkedCollectionIterator:public IIterator{ LinkedCollection* c; LinkedCollection::Nod* crt;

public: LinkedCollectionIterator(LinkedCollection* c1){ c=c1; crt =c->head;} bool hasNext(){ return (crt!=0); } IE* next(){

IE* e=crt->elem; crt=crt->next; return e;}

void first(){crt=c->head; }

IE* del(){ IE* e= crt->elem; LinkedCollection::Nod* ant=c->head; while(ant->next!=crt)

ant=ant->next; ant->next=crt->next; LinkedCollection::Nod* aux=crt;

crt=crt->next; delete aux; return e;

} ~LinkedCollectionIterator(){}};};#endif

Referirea la o clasa interioara altei clase

TAD Lista

• Reprezentari posibile:– Static (vector de elemente)– Inlantuit

• Simplu • Dublu

• Accesul la date – prin pozitii– Reprezentare statica (pozitie = index, obiect)– Reprezentare inlantuita (pozitie = nod )

TAD LISTA

Object si Integer #ifndef OBJ_H

#define OBJ_H

class Object{

public:

virtual bool equals(Object*)=0;

virtual char* toString()=0;

virtual ~Object(){}

};

#endif

#ifndef INTEGER_H

#define INTEGER_H

#include <cstdio>

#include <cstring>

#include "Object.h"

using namespace std;

class Integer:public Object{

private:

int i;

public:

Integer(int n=0):i(n){}

char* toString(){char* buf=new char[3]; sprintf(buf,"%d",i); return buf;}

bool equals(Object* p){ return i==((Integer*)p)->i;}

~Integer(){}

};

#endif

Object

+equals(: Object): bool+toString(): char<<destroy>>-Object()

Integer

-i: int

<<create>>-Integer(n: int)+toString(): char+equals(p: Object): bool<<destroy>>-Integer()

IList.h#ifndef ILIST_H#define ILIST_H

class Object;class IPozitie;class Iterator;

class ILista{public:

virtual int dimensiune()=0;virtual bool vida()=0;virtual void adaugaSf(Object*)=0;virtual void adaugaInc(Object*)=0;virtual void adauga(IPozitie*, Object*)=0;virtual void inserare(IPozitie*, Object*)=0;virtual Object* sterge(IPozitie*)=0;virtual IPozitie* prim()=0;virtual IPozitie* urmator(IPozitie*)=0;virtual IPozitie* anterior(IPozitie*)=0;virtual IPozitie* ultim()=0;virtual bool valid(IPozitie*)=0;virtual Iterator* iterator()=0;virtual ~ILista(){};

};#endif

ILista

+dimensiune(): int+vida(): bool+adaugaSf(: Object): void+adaugaInc(: Object): void+adauga(: IPozitie, : Object): void+inserare(: IPozitie, : Object): void+sterge(: IPozitie): Object+prim(): IPozitie+urmator(: IPozitie): IPozitie+anterior(: IPozitie): IPozitie+ultim(): IPozitie+valid(: IPozitie): bool+iterator(): Iterator<<destroy>>-ILista()

IPozitie.h

#ifndef POZ_H

#define POZ_H

class Object;

class IPozitie{

public:

virtual Object* elem()=0;

virtual ~IPozitie(){};

};

#endif

IPozitie

+elem(): Object<<destroy>>-IPozitie()

PozitieNod.h#ifndef POZ_NOD_H#define POZ_NOD_H

#include "IPozitie.h"

class PozitieNod:public IPozitie{Nod* crt;

public:PozitieNod(Nod* n){crt=n;}Object* elem(){return crt->getInfo();}~PozitieNod(){}friend class SLList;friend class DLList;

};#endif

PozitieNod

<<create>>-PozitieNod(n: Nod)+elem(): Object<<destroy>>-PozitieNod()

-crt

Nod

+getInfo(): Object+getNext(): Nod+setNext(: Nod): void<<destroy>>-Nod()

IPozitie


PozitieInt.h#ifndef POZINT_H#define POZINT_H

#include "IPozitie.h"

class PozitieInt:public IPozitie{private:

int crt;Object* info;

public:PozitieInt(int n=0, Object* o=0){crt=n;info=o;}Object* elem(){

return info;}~PozitieInt(){}friend class SLista;

};#endif

PozitieInt

-crt: int

<<create>>-PozitieInt(n: int, o: Object)+elem(): Object<<destroy>>-PozitieInt()

-info

Object


IPozitie


ILista


Nod.h

#ifndef NOD_H#define NOD_Hclass Object;

class Nod{public:

virtual Object* getInfo()=0;virtual Nod* getNext()=0;virtual void setNext(Nod*)=0;~Nod(){}

};#endif

Nod


SNod

<<create>>-SNod(o: Object, n: Nod)+getInfo(): Object+getNext(): Nod+setNext(n: Nod): void<<destroy>>-SNod()

DNod

<<create>>-DNod(o: Object, n: Nod, p: Nod)+getPrev(): Nod+setPrev(p: Nod): void<<destroy>>-DNod()

-prev

-next

SNod.h#ifndef SNOD_H#define SNOD_H#include "Nod.h"

class SNod:public Nod{Object* info;Nod* next;

public:SNod(Object* o=0,Nod* n=0)

{info=o;next=n;}Object* getInfo(){return info;}Nod* getNext(){return next;}void setNext(Nod* n){next=n;}~SNod(){};friend class SLList;

};#endif

SNod


-next

Nod


DNod.h#ifndef DNOD_H#define DNOD_H

#include "SNod.h"

class DNod:public SNod{Nod* prev;

public:DNod(Object*o=0, Nod*n=0, Nod* p=0): SNod(o,n) {prev=p;}

Nod* getPrev(){return prev;}

void setPrev(Nod* p){prev=p;}

~DNod(){}};#endif

DNod


SNod


-next

-prev

Nod


ILinkedList#ifndef LINKED_LIST_H#define LINKED_LIST_H#include "IList.h"

class Nod;

class ILinkedList:public ILista{protected:

Nod* head;public:

virtual ~ILinkedList(){}};#endif

ILista


#head

Nod


ILinkedList

<<destroy>>-ILinkedList()

SLListILista


IPozitie


PozitieNod


-crt

Nod


-next

SNod


ILinkedList


#head

SLList

<<create>>-SLList()+dimensiune(): int+vida(): bool+adaugaSf(o: Object): void+adaugaInc(o: Object): void+adauga(p: IPozitie, o: Object): void+inserare(p: IPozitie, o: Object): void+sterge(p: IPozitie): Object+prim(): IPozitie+urmator(p: IPozitie): IPozitie+anterior(p: IPozitie): IPozitie+ultim(): IPozitie+valid(p: IPozitie): bool+iterator(): Iterator<<destroy>>-SLList()

-info

Object


SLList.h#ifndef SLLIST_H#define SLLIST_H

#include "ILinkedList.h"#include "SNod.h"#include "PozitieNod.h"#include "Iterator.h"

class SLList:public ILinkedList{public:

SLList(){head=0;}int dimensiune(){

Nod* crt=head;int k=0;while(crt){

k++;crt=crt->getNext();

}return k;

}

bool vida(){return head==0;}

void adaugaSf(Object* o){if(head){Nod* crt=head;while(crt->getNext())

crt=crt->getNext();Nod* nou= new SNod(o,0);crt->setNext(nou);}else head=new SNod(o,0);

}

void adaugaInc(Object* o){head=new SNod(o,head);

}

void adauga(IPozitie* p, Object* o){PozitieNod* pn=(PozitieNod*) p;Nod* crt = pn->crt;Nod* nou = new SNod(o,crt->getNext());crt->setNext(nou);

}

void inserare(IPozitie* p, Object* o){Nod* crt=head;PozitieNod* pn=(PozitieNod*)p;if(pn->crt!=head){while(crt->getNext()!=pn->crt)

crt=crt->getNext();Nod * nou=new SNod(o,pn->crt);crt->setNext(nou);}else head=new SNod(o,head);

}

SLList.hObject* sterge(IPozitie* p){

PozitieNod* pn = (PozitieNod*)p;Nod* aux = pn->crt;Object* rez=pn->crt->getInfo();if (pn->crt==head)

head=head->getNext();

else{Nod* crt = head;while(crt->getNext()!=pn->crt){

crt=crt->getNext();

} Nod* aux = pn->crt;

rez=pn->crt->getInfo(); crt->setNext(pn->crt->getNext()); } delete aux;return rez

}

IPozitie* prim(){return new PozitieNod(head);}

IPozitie* urmator(IPozitie* p){PozitieNod* pn=(PozitieNod*)p;return new PozitieNod(pn->crt->getNext());

}

IPozitie* anterior(IPozitie* p){ PozitieNod* pn=(PozitieNod*)p;

Nod* crt=head; while(crt->getNext()!=pn->crt)

crt=crt->getNext(); return new PozitieNod(crt);

}

IPozitie* ultim(){Nod* crt=head;while(crt->getNext())

crt=crt->getNext();return new PozitieNod(crt);

}

bool valid(IPozitie* p){PozitieNod* pn=(PozitieNod*)p;return (pn->crt!=0);

}

Iterator* iterator(){return new Iterator(this);

}

~SLList(){Nod* p;while(head){

p=head;head=head->getNext();delete p;p=head;

}}

};#endif

DLList.h#ifndef DOUBLE_LINKED_LIST_H#define DOUBLE_LINKED_LIST_H

#include "DNod.h"#include "ILinkedList.h"#include "Iterator.h"

class DLList:public ILinkedList{Nod* tail;

public:DLList(){head=tail=0;}int dimensiune(){

Nod* crt=head;int k=0;while(crt){

k++;crt=crt->getNext();

}return k;

}

bool vida(){return (head==0);

}

void adaugaSf(Object* o){Nod* nou;if(head){

nou=new DNod(o,0,tail);tail->setNext(nou);

tail=nou;}else{

head=new DNod(o,0,0);tail=head;

}}

void adaugaInc(Object* o){head=new DNod(o,head,0);

}

void adauga(IPozitie* p, Object* o){PozitieNod* pn =(PozitieNod*)p;

if(pn->crt==tail)tail=new DNod(o,0,tail);

else Nod* nou = new DNod(o,pn->crt->getNext(),

((DNod*)pn->crt)->getPrev());}

void inserare(IPozitie* p, Object* o){ PozitieNod* pn =(PozitieNod*)p;

if (pn->crt==head) head=new DNod(o,head,0);

else{ Nod* nou = new DNod(o,

((DNod*)pn->crt)->getPrev(),pn->crt->getNext()); }

} Object* sterge(IPozitie* p){

PozitieNod* pn =(PozitieNod*)p; if (pn->crt==head) head=head->getNext(); else if (pn->crt==tail) tail=((DNod*)tail)->getPrev(); else {DNod* crt=(DNod*)pn->crt; crt->getPrev()->setNext(crt->getNext());

((DNod*)crt->getNext())->setPrev(crt->getPrev()); } Object* el = pn->crt->getInfo(); delete pn->crt; return el;

}

DLList.hIPozitie* prim(){

return new PozitieNod(head);

}

IPozitie* urmator(IPozitie* p){

PozitieNod* pn=(PozitieNod*)p;

return new PozitieNod(pn->crt->getNext());

}

IPozitie* anterior(IPozitie* p){


return new PozitieNod(((DNod*)pn->crt)->getPrev());

}

IPozitie* ultim(){

return new PozitieNod(tail);

}

bool valid(IPozitie* p){


return pn->crt!=0;

}

Iterator* iterator(){

return new Iterator(this);

}

~DLList(){

Nod* p;

while(head){

p=head;

head=head->getNext();

delete p;

}

}

};

#endif

DLList

DLList

<<create>>-DLList()+dimensiune(): int+vida(): bool+adaugaSf(o: Object): void+adaugaInc(o: Object): void+adauga(p: IPozitie, o: Object): void+inserare(p: IPozitie, o: Object): void+sterge(p: IPozitie): Object+prim(): IPozitie+urmator(p: IPozitie): IPozitie+anterior(p: IPozitie): IPozitie+ultim(): IPozitie+valid(p: IPozitie): bool+iterator(): Iterator<<destroy>>-DLList()

Nod


-tail

ILinkedList


ILista


-crt

PozitieNod


IPozitie


-next

-prev

SNod


DNod


-info

Object


SLista.h (lista static)#ifndef LISTA_STATIC_H#define LISTA_STATIC_H

#include "IList.h"#include "PozitieInt.h"#include "Iterator.h"

class SLista:public ILista{Object** elem;int dim;int cap;

public:SLista(int c=20){

cap=c;dim=0;elem=new Object*[cap];

}

SLista(const SLista& s){cap=s.cap;dim=s.dim;elem=new Object*[cap];for(int i=0;i<dim;i++) elem[i]=s.elem[i];

}

int dimensiune(){return dim;

}bool vida(){

return dim==0;}void adaugaSf(Object* o){

elem[dim++]=o;}

void adaugaInc(Object* o){

for(int i=dim;i>0;i--)elem[i]=elem[i-1];elem[0]=o;dim++;

}

void adauga(IPozitie* p, Object* o){ PozitieInt * pi = (PozitieInt*) p;

int index=pi->crt; for(int j=dim;j>index+1;j--)

elem[j]=elem[j-1]; elem[index+1]=o;

}

void inserare(IPozitie* p, Object* o){ PozitieInt* pi=(PozitieInt*) p; int index=pi->crt;

for(int j=dim;j>=index;j++) elem[j]=elem[j-1]; elem[index-1]=o;

}

Object* sterge(IPozitie * p){ PozitieInt* pi=(PozitieInt*)p; Object* el= elem[pi->crt];

elem[pi->crt]=elem[--dim]; return el;

}

IPozitie* prim(){ return new PozitieInt(0,elem[0]);

}

SLista.hIPozitie* urmator(IPozitie* p){

PozitieInt* pi= (PozitieInt*) p; int index=pi->crt; return new

PozitieInt(index+1,elem[index+1]); }

IPozitie* anterior(IPozitie* p){ PozitieInt* pi= (PozitieInt*) p; int index=pi->crt; return new PozitieInt(index-1,elem[index-1]);

}

IPozitie* ultim(){ return new PozitieInt(dim-1, elem[dim-1]);

}

bool valid(IPozitie* p){ PozitieInt* pi= (PozitieInt*)p; return (pi->crt<dim);

} Iterator* iterator(){

return new Iterator(this); }

~SLista(){ delete [] elem;

}};#endif

PozitieInt

-crt: int


-info

Object


SLista

-dim: int-cap: int

<<create>>-SLista(c: int)<<create>>-SLista(s: SLista)+dimensiune(): int+vida(): bool+adaugaSf(o: Object): void+adaugaInc(o: Object): void+adauga(p: IPozitie, o: Object): void+inserare(p: IPozitie, o: Object): void+sterge(p: IPozitie): Object+prim(): IPozitie+urmator(p: IPozitie): IPozitie+anterior(p: IPozitie): IPozitie+ultim(): IPozitie+valid(p: IPozitie): bool+iterator(): Iterator<<destroy>>-SLista()

-elem

IPozitie


ILista


Iterator.h#ifndef IIT_H#define IIT_H

#include "IList.h"

class Iterator{protected:

ILista* l;IPozitie* crt;

public:Iterator(ILista* il){l=il;crt=il->prim();}void next(){crt=l->urmator(crt);}Object* curent(){return crt->elem();}bool valid(){return l->valid(crt);}~Iterator(){}

};#endif

Abstractizare

IteratorILista


#l

IPozitie


#crt

Iterator

<<create>>-Iterator(il: ILista)+next(): void+curent(): Object+valid(): bool<<destroy>>-Iterator()

PozitieNod


-crt

Nod


PozitieInt

-crt: int


-info

Object


Test.cpp#include "SLista.h"#include "Integer.h"#include "SLinkedList.h"#include "DLinkedList.h"#include <fstream>using namespace std;

void incarcaLista(ILista* il, char* fis){ifstream f(fis);int x;while(!f.eof()){

f>>x;il->adaugaSf(new Integer(x));

}f.close();

}

void printLista(ILista* l, char* fis){ofstream f(fis);Iterator* it = l->iterator();while(it->valid()){

f<<it->curent()->toString()<<endl;it->next();

}f.close();delete it;

}

void dealocare(ILista* il){

IPozitie* crt=il->prim();while(il->valid(crt)){ delete crt->elem(); crt=il->urmator(crt);}

}

int main(){ILista* staticL = new SLista();ILista* sll = new SLList();

ILista* dll = new DLList();

incarcaLista(staticL,"in.txt");incarcaLista(sll,"in.txt");incarcaLista(dll,"in.txt");

printLista(staticL,"static.txt");printLista(sll,"SimpleLinkedList.txt");printLista(dll,"DoubleLinkedList.txt");

IPozitie* p = staticL->prim();staticL->sterge(p);//cout<<"dupa stergere"<<endl;printLista(staticL,"StaticL.txt");

dealocare(staticL);dealocare(sll);dealocare(dll);

delete staticL;delete sll;delete dll;return 0;

}

Structuri de cautare• Permite cautarea eficienta a elementelor

• Elementele sunt ordonate in functie de o relatie

• O noua operatie pentru tipul generic de data – compareTo

• Operatii:– Adaugare– Stergere– Cautare – returneaza un iterator pozitionat pe elementul cautat

• Lista ordonata – este o lista, dar mostenirea nu este o optiune recomandata pentru ca nu ne dorim sa se adauge elemente in orice pozitie

• Daca am folosi mostenire, ar trebui sa fie mostenire privata

• Alegerea potrivita – compozitie – refolosim codul de la listele anterior definite

Structuri de cautare#ifndef IE_H#define IE_H

class IE{ public: virtual char* toString()=0; virtual bool equals(IE*)=0; virtual ~IE(){}; }; #endif

#ifndef ICE_H#define ICE_H

#include "IE.h"

class ICE:public IE{public:

virtual int compareTo(ICE*)=0;virtual ~ICE(){}

};#endif

IE

+toString(): char+equals(: IE): bool<<destroy>>-IE()

ICE

+compareTo(: ICE): int<<destroy>>-ICE()

Integer

-i: int

<<create>>-Integer(n: int)+toString(): char+equals(p: IE): bool+compareTo(e: ICE): int<<destroy>>-Integer()

ISearchStructure

#ifndef ISEARCH_H#define ISEARCH_H#include "IIterator.h"#include "ICE.h"

class ISearchStructure{public:

virtual IIterator* search(ICE*)=0;virtual void add(ICE*)=0;

virtual void del(ICE*)=0; virtual ~ISearchStructure(){};};#endif

IE


ICE


ISearchStructure

+search(: ICE): IIterator+add(: ICE): void+del(: ICE): void

SortedLinkedList#ifndef SORTED_LINKED_LIST_H#define SORTED_LINKED_LIST_H

#include "ISearchStructure.h"#include "ILinkedList.h"

class SortedLinkedList:Public ISearchStructure{

ILinkedList* l;IAddress* searchPos(ICE*);IAddress* insertPosition(ICE*);

public: SortedLinkedList();IIterator* search(ICE*

e);void add(ICE* e);void del(ICE* e);~SortedLinkedList();IIterator* iterator();

};

#endif

ISearchStructure

+search(: ICE): IIterator+add(: ICE): void+del(: ICE): void

SortedLinkedList

-searchPos(: ICE): IAddress-insertPosition(: ICE): IAddress<<create>>-SortedLinkedList()+search(e: ICE): IIterator+add(e: ICE): void+del(e: ICE): void<<destroy>>-SortedLinkedList()+iterator(): IIterator

-l

ILinkedList

+insert(: IE, : IAddress): void+del(: IAddress): IE+addLast(: IE): void+getFirst(): IAddress+getNext(: IAddress): IAddress+getLast(): IAddress+getPrev(: IAddress): IAddress+get(: IAddress): IE+iterator(): IIterator+isEmpty(): int<<destroy>>-ILinkedList()

ILinkedList

#ifndef I_LINKED_LIST_H#define I_LINKED_LIST_H

#include "IAddress.h"#include "IIterator.h"

class ILinkedList{ public: virtual void insert(IE*, IAddress*)=0; virtual IE* del(IAddress*)=0; virtual void addLast(IE*)=0; virtual IAddress* getFirst()=0; virtual IAddress* getNext(IAddress*)=0; virtual IAddress* getLast()=0; virtual IAddress* getPrev(IAddress*)=0; virtual IE* get(IAddress*)=0; virtual IIterator* iterator()=0; virtual int isEmpty()=0; virtual ~ILinkedList(){}; };#endif

ILinkedList


IE


ICE


IAddress

+getNext(): IAddress+getElem(): IE<<destroy>>-IAddress()

IAddress.h#ifndef IADRESS_H#define IADRESS_H#include "ICE.h"

class IAddress{public: virtual IAddress* getNext()=0; virtual IE* getElem()=0; virtual ~IAddress(){} }; class IDAddress:public IAddress{ public: virtual IAddress* getPrev()=0;}; #endif

IAddress


SNode

<<create>>-SNode()<<create>>-SNode(i: IE, n: SNode)+getElem(): IE+getNext(): IAddress

IDAddress

+getPrev(): IAddress

IIteratorIIterator

+hasNext(): bool+elem(): IE+next(): void+first(): void+del(): IE

DLLIterator

<<create>>-DLLIterator(dl: DLList)+hasNext(): bool+elem(): IE+next(): void+first(): void+del(): IE

SLLIterator

<<create>>-SLLIterator(sl: SLList)+hasNext(): bool+elem(): IE+next(): void+first(): void+del(): IE

-s-d

DLList

<<create>>-DLList()+del(a: IAddress): IE+addLast(e: IE): void+getFirst(): IAddress+getNext(a: IAddress): IAddress+getPrev(a: IAddress): IAddress+getLast(): IAddress+insert(e: IE, a: IAddress): void+get(a: IAddress): IE<<destroy>>-DLList()+iterator(): IIterator+isEmpty(): int

SLList

<<create>>-SLList()+del(a: IAddress): IE+addLast(e: IE): void+getFirst(): IAddress+getNext(a: IAddress): IAddress+getPrev(a: IAddress): IAddress+set(e: IE, a: IAddress): void+get(a: IAddress): IE<<destroy>>-SLList()+isEmpty(): int+insert(e: IE, a: IAddress): void+getLast(): IAddress+iterator(): IIterator

-crt

SNode


#next

-crt

DNode

<<create>>-DNode()<<create>>-DNode(i: IE, p: DNode, n: DNode)+getPrev(): IAddress

-tail

IAddress


SLListILinkedList


IIterator


SLLIterator

<<create>>-SLLIterator(sl: SLList)+hasNext(): bool+elem(): IE+next(): void+first(): void+del(): IE

-s

-crt

-crt-head

SNode


#next

#info

IE


ICE


SLList

<<create>>-SLList()+del(a: IAddress): IE+addLast(e: IE): void+getFirst(): IAddress+getNext(a: IAddress): IAddress+getPrev(a: IAddress): IAddress+set(e: IE, a: IAddress): void+get(a: IAddress): IE<<destroy>>-SLList()+isEmpty(): int+insert(e: IE, a: IAddress): void+getLast(): IAddress+iterator(): IIterator

SLList + SLIterator#ifndef SLLIST_H

#define SLLIST_H

#include "Node.h"

#include "ILinkedList.h"

class SLLIterator;

class SLList:public ILinkedList{

SNode* head;

public:

friend class SLLIterator;

SLList();

IE* del(IAddress* a);

void addLast(IE* e);

IAddress* getFirst();

IAddress* getNext(IAddress* a);

IAddress* getPrev(IAddress* a);

void set (IE* e, IAddress* a);

IE* get(IAddress* a);

~SLList();

int isEmpty();

void insert(IE* e, IAddress* a);

IAddress* getLast();

IIterator* iterator();

};

class SLLIterator: public IIterator{

SLList* s;

SNode* crt;

public:

SLLIterator(SLList* sl){s=sl;crt=(SNode*)s->getFirst();}

bool hasNext(){return crt!=NULL;}

IE* elem(){

return crt->getElem();

}

void next(){

crt=(SNode*)s->getNext(crt);

}

void first(){crt=(SNode*)s->getFirst();}

IE* del(){

SNode* aux = crt;

crt=(SNode*)s->getNext(crt);

IE* val = crt->getElem();

s->del(aux);

return val;

}

};

#endif

DLList+DLLIterator#ifndef DLLIST_H#define DLLIST_H

#include "ILinkedList.h"#include "Node.h"

class DLList:public ILinkedList{DNode* head;DNode* tail;

public: DLList(); IE* del(IAddress* a); void addLast(IE* e); IAddress* getFirst(); IAddress* getNext(IAddress* a); IAddress* getPrev(IAddress* a); IAddress* getLast(); void insert(IE* e, IAddress* a); IE* get(IAddress* a); ~DLList(); IIterator* iterator(); int isEmpty();

};

class DLLIterator:public IIterator{DLList* d;

DNode* crt;

public:

DLLIterator(DLList* dl){d=dl;crt=(DNode*)d->getFirst();}

bool hasNext(){return crt!=0;}

IE* elem(){return crt->getElem();}

void next(){crt=(DNode*)crt->getNext();}

void first(){crt=(DNode*)d->getFirst();}

IE* del(){ DNode* aux = crt; crt=(DNode*)d->getNext(crt); IE* val = crt->getElem(); d->del(aux); return val;}};

#endif

ILinkedList


DLList

<<create>>-DLList()+del(a: IAddress): IE+addLast(e: IE): void+getFirst(): IAddress+getNext(a: IAddress): IAddress+getPrev(a: IAddress): IAddress+getLast(): IAddress+insert(e: IE, a: IAddress): void+get(a: IAddress): IE<<destroy>>-DLList()+iterator(): IIterator+isEmpty(): int

-d

DLLIterator

<<create>>-DLLIterator(dl: DLList)+hasNext(): bool+elem(): IE+next(): void+first(): void+del(): IE

IIterator


IE


#info

ICE


DNode

<<create>>-DNode()<<create>>-DNode(i: IE, p: DNode, n: DNode)+getPrev(): IAddress

-prev

IAddress


-tail

#next

-crt

SNode


-head

SortedLinkedList.cpp#include "SortedLinkedList.h"#include "DLList.h"

SortedLinkedList::SortedLinkedList(){

l = new DLList();}

IIterator* SortedLinkedList::search(ICE* e){DLLIterator* it =(DLLIterator*) l->iterator();int found = 0;while (it->hasNext() && ! found ){

ICE* ec = (ICE*) it->elem(); // cast conv!!!if (e->compareTo(ec)==0) found = 1;

else it->next();}if (found==1) return it;return NULL;

}

IAddress* SortedLinkedList::searchPos(ICE* e){

IAddress* a = l->getFirst();while(l->getNext(a)){

ICE* ec = (ICE*)l->get(a);if (ec->compareTo(e)==0) return a;a = l->getNext(a);

}return NULL;

}

void SortedLinkedList::del(ICE* e){IAddress* a = searchPos(e);if(a){ l->del(a); }

}

IAddress* SortedLinkedList::insertPosition(ICE* e){IAddress* a = l->getFirst();IAddress* ant=NULL;cout<<"caut pozitie pentru "<<e->toString()<<" ";while (e->compareTo((ICE*)l->get(a))>0){

ant = a;cout<<"actual "<<a->getElem()->toString()<<endl;a = l->getNext(a);

}return ant;}

void SortedLinkedList::add(ICE* e){ if (l->isEmpty()) {

l->addLast(e); return; }IAddress* crt = l->getFirst();ICE* ec= (ICE*)l->get(crt);if(e->compareTo(ec)<0) {l->insert(e,NULL);return;}

while((e->compareTo(ec)>=0)&&(crt)){crt=l->getNext(crt);

if(crt) ec= (ICE*)l->get(crt);} if(!crt) l->addLast(e);else{

IAddress* ant=l->getPrev(crt);l->insert(e,ant);}

}

SortedLinkedList::~SortedLinkedList(){ delete l;}

IIterator* SortedLinkedList::iterator() { return new DLLIterator((DLList*)l);}

SearchStructure

Test.cpp#include "ISearchStructure.h"#include "SortedLinkedList.h"#include "Integer.h"#include <iostream>using namespace std;

int main(){ ISearchStructure* is = new SortedLinkedList();

is->add(new Integer(5));is->add(new Integer(7));is->add(new Integer(3));

is->add(new Integer(4));is->add(new Integer(9));

Integer* p = new Integer(4);IIterator* it =is->search(p);

if (it){

while(it->hasNext()){cout<<it->elem()->toString()<<" ";it->next();

} delete is;

delete it; } else cout<<"Nu exista "<<endl;

return 0;}

Structuri de cautare

• Ierarhia poate fi extinsa cu ARBORI, DICTIONARE, etc

• In functie de contextul problemei se va alege cea mai potrivita instantiere (implementare concreta)

Tipuri de date polimorfice

Documents

Transcript of Tipuri de date polimorfice