[]
readme
course(s)
preface
I
1
2
II
3
4
III
5
6
7
IV
8
9
10
V
11
12
afterthought(s)
appendix
reference(s)
example(s)
resource(s)
_

object-oriented programming

Abstract data types allow the programmer to define a complex data structure and an associated collection of functions, operating on that structure, in a consistent way. Historically, the idea of data abstraction was originally not type-oriented but arose from a more pragmatic concern with information hiding and representation abstraction, see

** ADT**

typedef int element; struct list; extern list* nil(); extern list* cons(element e, list* l); extern element head(list* l); extern list* tail(list* l); extern bool equal(list* l, list* m);

** OOP**

template< class E > class list { public: list() { } virtual ~list() { } virtual bool empty() = 0; virtual E head() = 0; virtual list* tail() = 0; virtual bool operator==(list * m) = 0; };

** ADT**

typedef int element; enum { NIL, CONS }; struct list { int tag; element e; list* next; };

list* nil() {## list* l = new list; l->tag = NIL; return l; } list* cons( element e, list* l) {

nil## list* x = new list; x->tag = CONS; x->e = e; x->next = l; return x; }

cons

** ADT**

int empty(list* lst) { return !lst || lst->tag == NIL; } element head(list* l) {## require( ! empty(l) ); return l->e; } list* tail(list* l) {

head## require( ! empty(l) ); return l->next; } bool equal(list* l, list* m) {

tail## switch( l->tag) { case NIL: return empty(m); case CONS: return !empty(m) && head(l) == head(m) && tail(l) == tail(m); } }

equal

list* r = cons(1,cons(2,nil())); while (!empty(r)) { cout << head(r) << endl; r = tail(r); }

** OOP**

template< class E > class nil : public list< E > {## public: nil() {} bool empty() { return 1; } E head() { require( false ); return E(); } list< E >* tail() { require( 0 ); return 0; } bool operator==(list

nil* m) { return m->empty(); } }; template< class E > class cons : public list< E > { ## public: cons(E e, list

cons* l) : _e(e), next(l) {} ~cons() { delete next; } bool empty() { return 0; } E head() { return _e; } list * tail() { return next; } bool operator==(list * m); protected: E _e; list * next; };

list<int>* r = new cons<int>(1, new cons<int>(2, new nil<int>)); while (! r->empty()) { cout << r->head() << endl; r = r->tail(); } delete r;

** ADT**

typedef int element; enum { NIL, CONS, INTERVAL }; struct list { int tag; element e; union { element z; list* next; }; };

list* interval( element x, element y ) { list* l = new list; if ( x <= y ) { l->tag = INTERVAL; l->e = x; l->z = y; } else l->tag = NIL; return l; }

** ADT**

element head(list* l) {## require( ! empty(l) ); return l->e;

head// for both CONS and INTERVAL} list* tail(list* l) {## require( ! empty(l) ); switch( l->tag ) { case CONS: return l->next; case INTERVAL: return interval((l->e)+1,l->z); } }

tail

** OOP**

class interval : public list<int> {## public: interval(int x, int y) : _x(x), _y(y) { require( x <= y ); } bool empty() { return 0; } int head() { return _x; } list< int >* tail() { return (_x+1 <= _y)? new interval(_x+1,_y): new nil<int>; } bool operator==(list@lt;int>* m) { return !m->empty() && _x == m->head() && tail() == m->tail(); } protected: int _x; int _y; };

interval

** ADT**

int length( list* l ) {## switch( l->tag ) { case NIL: return 0; case CONS: return 1 + length(l->next); case INTERVAL: return l->z - l->e + 1; }; }

length

** OOP**

template< class E > int length(list< E >* l) {## return l->empty() ? 0 : 1 + length( l->tail() ); } template< class E > class listWL : public list<E> {

length## public: int length() { return ::length( this ); } };

listWL

list<int>* r = new cons<int>(1,new cons<int>(2,new interval(3,7))); while (! r->empty()) { cout << ((listWL< int >*)r)->length() << endl; r = r->tail(); } delete r;

[]
readme
course(s)
preface
I
1
2
II
3
4
III
5
6
7
IV
8
9
10
V
11
12
afterthought(s)
appendix
reference(s)
example(s)
resource(s)
_

(C) Æliens 04/09/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.