Objektum elvű alkalmazások fejlesztése Verem típus osztály-sablonja Készítette:
Gregorics Tibor
Készítsünk olyan újra-felhasználható kódot, amellyel vermeket lehet létrehozni és használni. Egy verem-objektum reprezentációját az határozza meg, hogy adunk-e felső korlátot a verem méretére. Ha igen, akkor statikus (tömbös azaz aritmetikai), ha nem, akkor dinamikus (szétszórt azaz láncolt) ábrázolást alkalmazunk majd. A verem osztályának példányosításnál tetszőlegesen választhassuk meg a verem elemeinek típusát.
Absztrakt ábrázolások:
Időbélyeges elemek halmaza: push
pop
Elején változtatható sorozat: push
pop
(e3, 5) top (e2, 2)
(e1, 0)
empty
e3 top e2 e1
empty
Dinamikus reprezentáció
Statikus reprezentáció 0
vect e1
size-1
e2
e3
h
e3
e2
e1 nil
top 2 1. Rögzített a lefoglalt memória mérete, ami sokszor vagy feleslegesen nagy vagy kevés. 2. Tömbnyi szabad memória kell. 3. Adatelemek (top illetve vect[top]) elérési ideje konstans.
1. Valódi mérethez igazodik a lefoglalt memória (de a címeket is tárolja) 2. Sok kisméretű memória szelet kell. 3. Adatelemek elérési ideje általában lineáris, de itt csak az első elem kell, tehát konstans.
Stack
Item
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
Stack
Stack<string> Stack
si1; ss; st;
Stack si2(20); verem maximális mérete statikus reprezentációhoz
si1.push(4); ss.push("alma"); st.push(new Kup(2.0, 4.5)); Stack- osztály-sablon példányosításai ahol Item az elemi-típus paramétere
main.cpp
Stack template class Stack { public: Stack(int max = 0); ~Stack(); void Item Item bool
Item
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
push(const Item &e); pop(); top() const; empty() const;
private: … };
Hogyan írható le mindkét reprezentáció?
stack.hpp
<>
Stack
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
Item
ArrayStackRepr -vect : Item[] -top : int +ArrayReprStack() +push(Item) : void +pop() : Item +top() : Item +empty() : bool
Item Interfész : a „tisztán absztrakt” osztály
Sajnos a példányosításnál nem írhatunk Stack v(20) vagy Stack v -t. Helyettük az ArrayReprStack v(20) illetve LinkedReprStack v használható. Item
LinkedStackRepr -head : Node* +LinkedReprStack() +push(Item) : void +pop() : Item +top() : Item +empty() : bool
Stack
Item
<>
StackRepr
- *repr +Stack(int max=0) +push(Item): void +pop() : Item +top() : Item +empty() : bool
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
if (max==0) repr = new LinkedStackRepr- (); else repr = new ArrayStackRepr
- (max);
Item
ArrayStackRepr repr>push(e) return repr>pop() return repr>top() return repr>empty()
Item
-vect : Item[] -top : int +ArrayStackRepr() +push(Item): void +pop() : Item +top() : Item +empty() : bool
Ez esetben használható a Stack v(20) illetve a Stack v
Item
LinkedStackRepr -head : Node* +LinkedStackRepr() +push(Item): void +pop() : Item +top() : Item +empty() : bool
template class Stack { public: Stack(int max = 0){ if (max==0) _repr else _repr } void push(const Item Item pop() { Item top() const { bool empty() const {
= new LinkedStackRepr - (); = new ArrayStackRepr
- (max); &e) { return return return
_repr->push(e); _repr->pop(); _repr->top(); _repr->empty();
} } } }
private: StackRepr- *_repr; };
stack.hpp
<>
Item
StackRepr
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
enum StackExceptions {EMPTYSTACK, FULLSTACK}; template class StackRepr { public: virtual void push(const Item &e) virtual Item pop() virtual Item top() const virtual bool empty() const virtual ~StackRepr(){}; };
= = = =
0 0 0 0
; ; ; ;
stackrepr.hpp
<>
Item
StackRepr
+push(Item) : void +pop() : Item +top() : Item +empty() : bool
template class ArrayStackRepr : public StackRepr- { public: ArrayStackRepr(int max){ Item try { _vect.resize(max); } ArrayStackRepr catch(std::bad_alloc o){throw FULLSTACK;} -top : int _top=-1; } void push(const Item &e); Item pop(); -vect Item top() const; Item bool empty() const; A vector is egy sablon
private: std::vector- _vect; int _top; };
Array
arraystackrepr.hpp
template void ArrayStackRepr- ::push(const Item& e){ if(_top+1==(int)_vect.size()) throw FULLSTACK; _vect[++_top] = e; } template Item ArrayStackRepr
- ::pop(){ if(_top==-1) throw EMPTYSTACK; --_top; }
template Item ArrayStackRepr- ::top() const{ if(_top==-1) throw EMPTYSTACK; return _vect[_top]; } template bool ArrayStackRepr
- ::empty() const { return _top==-1; }
arraystackrepr.hpp
<>
Item
StackRepr
template class LinkedStackRepr : public StackRepr- { +push(Item) : void public: +pop() : Item LinkedStackRepr(){ _head = NULL;} +top() : Item +empty() : bool LinkedStackRepr(const LinkedStackRepr&); LinkedStackRepr& operator=(const LinkedStackRepr&); ~LinkedStackRepr(){ destroy(); } Item
LinkedStackRepr
void push(const Item &e); -destroy() : void Item pop(); -copy() : void Item top() const; bool empty() const; - *head Item private: A Node is egy sablon: Node struct Node{ Node- +val : Item Item val; Node *next; Node(const Item &e, Node *n):val(e), next(n){}; }; + *next Node *_head; void destroy(); void copy(const LinkedStackRepr&); linkedstackrepr.hpp };
template void LinkedStackRepr- ::push(const Item& e) { try{ _head = new Node(e,_head); } catch(std::bad_alloc o) { throw FULLSTACK; } } template Item LinkedStackRepr
- ::pop() { if(_head==NULL) throw EMPTYSTACK; Node *p = _head; _head = _head->next; Item e = p->val; delete p; return e; } template Item LinkedStackRepr
- ::top() const { if(_head==NULL) throw EMPTYSTACK; return _head->val; } template bool LinkedStackRepr
- ::empty() const { return _head==NULL; linkedstackrepr.hpp }
template LinkedStackRepr- :: LinkedStackRepr(const LinkedStackRepr& r) { copy(r); } template LinkedStackRepr
- & LinkedStackRepr
- :: operator=(const LinkedStackRepr& r) { if(this==&r) return *this; destroy(); copy(r); return *this; }
linkedstackrepr.hpp
template void LinkedStackRepr- ::copy(const LinkedStackRepr& r){ if(r._head==NULL) _head = NULL; else { try{ _head = new Node(r._head->value,NULL); Node *q = _head; Node *p = r._head->next; while(p!=NULL){ q->next = new Node(p->value,NULL); q = q->next; p = p->next; } }catch(std::bad_alloc o){ destroy(); template throw FULLSTACK; void } félig felépített LinkedStackRepr
- ::destroy(){ } lista lebontása while(_head!=NULL){ } Node *p = _head; _head = _head->next; delete p; } linkedstackrepr.hpp }
main.cpp int main() { … }
stack.hpp
stackrepr.hpp
enum StackExceptions { … };
enum StackReprExceptions { … };
template class Stack { … };
template class StackRepr { … };
linkedstackrepr.hpp
arraystackrepr.hpp
template class LinkedStackRepr : public StackRepr { … };
template class ArrayStackRepr : public StackRepr { … };
int main() { Stack s; // Stack s(10); try{ int i; while( cin >> i ){ s.push(i); } }catch (StackExceptions e){ if (e == FULLSTACK) cout << "…"; } while(!s.Empty()){ cout << s.pop() << endl;} } return 0; }
main.cpp
- *repr
StackRepr
Stack return repr->createEnumerator() +Stack(int max=0) ... + createEnumerator() : Enumerator*
Item
<>
Enumerator
...
(first, next, end, current)
+ createEnumerator()
Item LinkedStackRepr … + createEnumerator()
Item ArrayStackRepr … + createEnumerator()
bejár return new LinkedStackEnum(this)
Item
bejár
Item LinkedStackEnum - p : Node*
Item ArrayStackEnum - ind : int
…
…
(first, next, end, current)
(first, next, end, current)
* -*ref return new ArrayStackEnum(this)
* -*ref
template class Enumerator{ public: virtual ~Enumerator() {}; virtual void first() virtual void next() virtual Item current() const virtual bool end() const };
= = = =
0; 0; 0; 0;
enumerator.hpp
template class ArrayStackRepr : public StackRepr- { ... public: class ArrayStackEnumerator : public Enumerator
- { public: ArrayStackEnumerator(ArrayStackRepr *r){ _ref = r; } void first() { _i = 0; } void next() { ++_i; } Item current() const { return _ref->_vect[_i]; } bool end() const { return _i > _ref->_top; } private: ArrayStackRepr *_ref; int _i; };
Enumerator- * createEnumerator() { return new ArrayStackEnumerator(this); } };
arraystackrepr.hpp
template class LinkedStackRepr : public StackRepr- { ... public: class LinkedStackEnumerator : public Enumerator
- { public: LinkedStackEnumerator(LinkedStackRepr *r){ _ref = r; } void first() { _p = _ref->_head; } void next() { _p = _p->next; } Item current() const { return _p->val; } bool end() const { return _p == NULL; } private: LinkedStackRepr *_ref; LinkedStackRepr::Node *_p; };
Enumerator- * createEnumerator() { return new LinkedStackEnumerator(this); } };
linkedstackrepr.hpp
template class Stack; template std::ostream& operator<<(std::ostream& out, Stack- & s);
template class Stack { public: friend std::ostream& operator<< <> (std::ostream& out, Stack& s); … template }; std::ostream& operator<< (std::ostream& out, Stack- & s) { out << "["; Enumerator
- *t = s.createEnumerator(); t->first(); if(! t->end()) out << " " << t->current(); for( t->next(); !t->end(); t->next()) out << ", " << t->current(); out << " ]"; return out; stack.hpp }
int main() { Stack s; // Stack s(10); try{ int i; while( cin >> i ){ s.push(i); } }catch (StackExceptions e){ if (e == FULLSTACK) cout << "…"; } cout << s << endl;
return 0; }
main.cpp
template class Stack{ public: … };
Stack y; Stack<> y; Stack y;
template class ArrayRepr{ public: ArrayRepr(int max = 0) { try{ vect.resize(maxsize); } catch(std::bad_alloc o){ throw FULLSTACK;} top=-1; Stack y; } Stack y; … };
